Take trusted files' modules from the cache instead of crawling

Before its first check, dmypy turns each source path into a module by
crawling up its directories for __init__ files. With the cache trusted for
files not named in --changed-since-cache-file, that is the one look left
at each source's directories, and over a network or FUSE filesystem the
largest part of a cold start.

The cache already says it: each module's metadata has its path and id,
and a module's components are the directories above the file, so its
base directory follows without looking. A file's module is as when the
cache was made unless the file, or an __init__ in a directory above it,
changed since, so for every other file the first check takes its module
from the cache; create_source_list takes these as known_modules, and
crawls for the rest and for any path whose directories do not match its
module.
diff --git a/mypy/build.py b/mypy/build.py
index 5e5059f..8e4a283 100644
--- a/mypy/build.py
+++ b/mypy/build.py
@@ -1764,6 +1764,32 @@
         return None
 
 
+def read_cached_modules(options: Options) -> dict[str, str]:
+    """Map the path of each module in the cache to the module's id."""
+    metastore = create_metastore(options, parallel_worker=False)
+    modules = {}
+    try:
+        for name in metastore.list_all():
+            if name.startswith("@") or not name.endswith((".meta.ff", ".meta.json")):
+                continue
+            try:
+                data = metastore.read(name)
+            except OSError:
+                continue
+            meta: CacheMeta | None
+            if name.endswith(".meta.ff"):
+                if data[0] != cache_version() or data[1] != CACHE_VERSION:
+                    continue
+                meta = CacheMeta.read(ReadBuffer(data[2:]), data_file="")
+            else:
+                meta = CacheMeta.deserialize(json_loads(data), data_file="")
+            if meta is not None:
+                modules[meta.path] = meta.id
+    finally:
+        metastore.close()
+    return modules
+
+
 def read_quickstart_file(
     options: Options, stdout: TextIO
 ) -> dict[str, tuple[float, int, str]] | None:
diff --git a/mypy/dmypy_server.py b/mypy/dmypy_server.py
index aeac31d..5ad0530 100644
--- a/mypy/dmypy_server.py
+++ b/mypy/dmypy_server.py
@@ -364,11 +364,48 @@
     ) -> dict[str, object]:
         """Check a list of files."""
         try:
-            sources = create_source_list(files, self.options, self.fscache)
+            sources = create_source_list(
+                files, self.options, self.fscache, known_modules=self.trusted_cached_modules()
+            )
         except InvalidSourceList as err:
             return {"out": "", "err": str(err), "status": 2}
         return self.check(sources, export_types, is_tty, terminal_width)
 
+    def trusted_cached_modules(self) -> dict[str, str] | None:
+        """The module of each file a first check trusts the cache for.
+
+        A file's module is as when the cache was made unless the file, or an __init__ in a
+        directory above it, has changed since: so the first check of a daemon trusting its
+        cache need not crawl up each file's directories to find its module.
+        """
+        if self.fine_grained_manager or not self.options.use_fine_grained_cache:
+            return None
+        # The build warns, if need be, of a file it cannot read.
+        changed = mypy.build.read_changed_since_cache_file(self.options, io.StringIO())
+        if changed is None:
+            return None
+        changed_packages = {
+            os.path.dirname(path)
+            for path in changed
+            if os.path.basename(path) in ("__init__.py", "__init__.pyi")
+        }
+
+        def under_changed_package(path: str) -> bool:
+            dir = os.path.dirname(path)
+            while True:
+                if dir in changed_packages:
+                    return True
+                parent = os.path.dirname(dir)
+                if parent == dir:
+                    return False
+                dir = parent
+
+        return {
+            path: module
+            for path, module in mypy.build.read_cached_modules(self.options).items()
+            if path not in changed and not under_changed_package(path)
+        }
+
     def cmd_recheck(
         self,
         is_tty: bool,
diff --git a/mypy/find_sources.py b/mypy/find_sources.py
index e1edebe..c00930b 100644
--- a/mypy/find_sources.py
+++ b/mypy/find_sources.py
@@ -4,7 +4,7 @@
 
 import functools
 import os
-from collections.abc import Sequence
+from collections.abc import Mapping, Sequence
 from typing import Final
 
 from mypy.fscache import FileSystemCache
@@ -29,9 +29,13 @@
     options: Options,
     fscache: FileSystemCache | None = None,
     allow_empty_dir: bool = False,
+    known_modules: Mapping[str, str] | None = None,
 ) -> list[BuildSource]:
     """From a list of source files/directories, makes a list of BuildSources.
 
+    known_modules maps files to their modules, known already, as from a cache: such a
+    file's module and base directory come from it, without crawling up its directories.
+
     Raises InvalidSourceList on errors.
     """
     fscache = fscache or FileSystemCache()
@@ -41,6 +45,11 @@
     for path in paths:
         path = os.path.normpath(path)
         if path.endswith(PY_EXTENSIONS):
+            module = known_modules.get(path) if known_modules else None
+            base_dir = base_dir_of(path, module) if module is not None else None
+            if module is not None and base_dir is not None:
+                sources.append(BuildSource(path, module, None, base_dir))
+                continue
             # Can raise InvalidSourceList if a directory doesn't have a valid module name.
             name, base_dir = finder.crawl_up(path)
             sources.append(BuildSource(path, name, None, base_dir))
@@ -55,6 +64,29 @@
     return sources
 
 
+def base_dir_of(path: str, module: str) -> str | None:
+    """The base directory crawl_up would find for a file holding module, without looking.
+
+    Each component of a module but its last is a directory above the file, so the base
+    directory is as many directories up. None if the path's directories do not match the
+    module's components.
+    """
+    dir = os.path.dirname(os.path.abspath(path))
+    components = module.split(".")
+    stem = strip_py(os.path.basename(path))
+    if stem == "__init__":
+        packages = components
+    elif components[-1] == stem:
+        packages = components[:-1]
+    else:
+        return None
+    for package in reversed(packages):
+        dir, name = os.path.split(dir)
+        if name.removesuffix("-stubs") != package:
+            return None
+    return dir
+
+
 def keyfunc(name: str) -> tuple[bool, int, str]:
     """Determines sort order for directory listing.
 
diff --git a/mypy/test/test_find_sources.py b/mypy/test/test_find_sources.py
index 321f340..462a81c 100644
--- a/mypy/test/test_find_sources.py
+++ b/mypy/test/test_find_sources.py
@@ -7,7 +7,7 @@
 
 import pytest
 
-from mypy.find_sources import InvalidSourceList, SourceFinder, create_source_list
+from mypy.find_sources import InvalidSourceList, SourceFinder, base_dir_of, create_source_list
 from mypy.fscache import FileSystemCache
 from mypy.modulefinder import BuildSource
 from mypy.options import Options
@@ -374,3 +374,38 @@
             }
             fscache = FakeFSCache(files)
             assert len(find_sources(["."], options, fscache)) == len(files)
+
+    def test_base_dir_of_matches_crawl_up(self) -> None:
+        files = {
+            "/a/pkg/__init__.py",
+            "/a/pkg/sub/__init__.py",
+            "/a/pkg/sub/mod.py",
+            "/a/pkg/mod.pyi",
+            "/a/top.py",
+            "/a/foo-stubs/__init__.pyi",
+            "/a/foo-stubs/bar.pyi",
+        }
+        finder = SourceFinder(FakeFSCache(files), Options())
+        for f in files:
+            module, base_dir = finder.crawl_up(f)
+            assert base_dir_of(f, module) == base_dir, f
+
+    def test_base_dir_of_mismatch(self) -> None:
+        assert base_dir_of("/a/pkg/mod.py", "pkg.other") is None
+        assert base_dir_of("/a/pkg/mod.py", "other.mod") is None
+        assert base_dir_of("/a/pkg/__init__.py", "other") is None
+
+    def test_known_modules_need_no_crawl(self) -> None:
+        class NoFS(FakeFSCache):
+            def isfile(self, path: str) -> bool:
+                raise AssertionError(f"looked at {path}")
+
+        sources = create_source_list(
+            ["/a/pkg/sub/mod.py"],
+            Options(),
+            NoFS(set()),
+            known_modules={"/a/pkg/sub/mod.py": "pkg.sub.mod"},
+        )
+        assert [(s.module, normalise_path(s.base_dir or "")) for s in sources] == [
+            ("pkg.sub.mod", "/a")
+        ]
diff --git a/test-data/unit/daemon.test b/test-data/unit/daemon.test
index 871a81b..d924a2f 100644
--- a/test-data/unit/daemon.test
+++ b/test-data/unit/daemon.test
@@ -369,6 +369,29 @@
 $ dmypy stop
 Daemon stopped
 
+-- The first check takes the modules of files it trusts the cache for from the cache, but not
+-- of those under an __init__ that changed: without pkg/__init__.py, pkg/a.py is module a.
+[case testDaemonChangedSinceCacheModules]
+$ {python} -c "import os; os.makedirs('pkg'); os.makedirs('other')"
+$ {python} -c "print('')" >pkg/__init__.py
+$ {python} -c "print('x = 1')" >pkg/a.py
+$ {python} -c "print('')" >other/__init__.py
+$ {python} -c "print('y = 1')" >other/b.py
+$ {python} -c "print('from pkg.a import x; from other.b import y')" >c.py
+$ mypy --local-partial-types --cache-fine-grained --follow-imports=error --no-sqlite-cache --python-version=3.11 -- pkg/__init__.py pkg/a.py other/__init__.py other/b.py c.py
+Success: no issues found in 5 source files
+$ {python} -c "import os; os.remove('pkg/__init__.py')"
+$ {python} -c "print('pkg/__init__.py')" >changed.txt
+$ dmypy start -- --local-partial-types --follow-imports=error --use-fine-grained-cache --no-sqlite-cache --python-version=3.11 --changed-since-cache-file changed.txt
+Daemon started
+$ dmypy check pkg/a.py other/__init__.py other/b.py c.py
+c.py:1: error: Import of "pkg.a" ignored  [misc]
+c.py:1: note: (Using --follow-imports=error, module not passed on command line)
+Found 1 error in 1 file (checked 4 source files)
+== Return code: 1
+$ dmypy stop
+Daemon stopped
+
 [case testDaemonSuggest]
 $ dmypy start --log-file log.txt -- --follow-imports=error --no-error-summary
 Daemon started