Repository: python/mypy
Pull request: Rework cache to key on hash of file contents instead of mtime
Attempt to fix #3403 

At present, I'm only adding the ability to validate the cache using a hash even though the module file mtime doesn't match the meta mtime.

However, I'm NOT getting rid of the use of `data_mtime` (modified time of the cache file) for the purpose of finding dependencies that tell us that a given module needs to be reparsed. This is much more complex than I thought, and it may also be possible to work around that by using @JukkaL  suggestion of putting the enitre cache into a tarball to preserve cache mtimes.

To verify that the approach works, I first create a failing test by changing the tests runner to touch all the source files before running mypy for incremental tests. Then in the second commit, I fix the broken tests.

How this whole thing should be tested is something that I'd like feedback on (running the tests twice is too time consuming I think?). As it stands, this PR only tests the new approach, and loses the tests for the old approach (with mtime/size). Maybe some kind of combination of the two would be good?

Problem statement:
Rework cache to key on hash of file contents instead of mtime
The key of the cache is currently the mtime (and size) of the source file. A problem here is that it's impossible to share a "pre-warmed" cache between users because the mtimes of files are different for each users. I propose to change the cache to be keyed on a hash instead. It should probably be sha1, or perhaps md5 if it's significantly faster.

Hashing all files in a large tree is pretty efficient. But just to make it more efficient we could add a "meta cache" that is keyed by mtime, where if we've already got a hash for a file and its mtime isn't changed, we bypass computation of the hash. If the mtime changed (but the size matches that in the cache) we re-hash the file and if that hash matches the hash from the cache we update the mtime in the "meta cache".

Once we have all this in place we can think about sharing copies of the cache between users (using a mechanism outside mypy, so mypy won't have to worry about authentication and security).

Hints from issue discussion:
I'll work on it.
It seems we may also need to calculate the hash of the cache (.json) file because there's a risk that the meta file is no longer in sync with the cache file. Currently, this is ensured by checking the modified time of the data file; this won't work when files are moved between users.

Our options are:

(1) verify that the modified date of the cache file matches the corresponding field of the meta file
(2) assume that meta and cache files are always in sync (by using atomic multiple file writes) and hoping no one finds a way to use a inconsistent cache file
(3) merge meta and cache file into one
Option (1) is ok, but may increase the hashing overhead.

Option (2) is unacceptable because *multiple file* atomic write is unavailable without file locking, and even if it wasn't a problem, other problems might cause meta and cache files to go out of sync.

Option (3) seems the most attractive. We can separate the meta into the header section of the file in order to avoid reading the entire file when the header already tells us that it's not fresh; as a result, there's no performance impact (in fact it may even be slightly faster than the current approach, since we'll open fewer file).
Summarizing the discussion at the sprint:

Currently we use `mtime_data` (the time the cache file was last modified) to do two things:

- validate that the cache file is in sync with the source file
- validate that the cache file is in sync with the dependencies

The first bullet point is solved by using file content hashes. The second bullet point can be solved by using the same approach as git: include the immediate parent hashes inside the file hash. (This is probably a cleaner approach than adding generation ids with its history dependence.)

We need to make sure that our approach addresses cycles (which don't exist in git). Hopefully the fact that we aggregate them into SCCs is enough, but we should double check cases like this: `A(SCC1) <- B(SCC2) <- C(SCC3)`, `C` changed after `A` cache was generated. Note that we do not want to worry about recursive dependencies, everything should work just based on direct ancestors.
@JukkaL  suggested to not merge meta and data files yet, and do everything else as the first PR. Whether or not merging the files is worthwhile can be discussed later.

Also, we need to make sure the optimizations that involve `interface_hash` aren't lost; therefore, `interface_hash` should not be changed to depend on any additional information (that's why `mtime` and `interface_hash` are separated).

Commit message: CR: optimize source hash calculation

Patch to review:
diff --git a/mypy/build.py b/mypy/build.py
index f803929a8fdf..8356e3f897bb 100644
--- a/mypy/build.py
+++ b/mypy/build.py
@@ -294,6 +294,7 @@ def default_lib_path(data_dir: str,
                         ('path', str),
                         ('mtime', float),
                         ('size', int),
+                        ('hash', str),
                         ('dependencies', List[str]),  # names of imported modules
                         ('data_mtime', float),  # mtime of data_json
                         ('data_json', str),  # path of <id>.data.json
@@ -684,8 +685,12 @@ def verify_module(id: str, path: str) -> bool:
     return True
 
 
-def read_with_python_encoding(path: str, pyversion: Tuple[int, int]) -> str:
-    """Read the Python file with while obeying PEP-263 encoding detection"""
+def read_with_python_encoding(path: str, pyversion: Tuple[int, int]) -> Tuple[str, str]:
+    """Read the Python file with while obeying PEP-263 encoding detection.
+
+    Returns:
+      A tuple: the source as a string, and the hash calculated from the binary representation.
+    """
     source_bytearray = bytearray()
     encoding = 'utf8' if pyversion[0] >= 3 else 'ascii'
 
@@ -710,7 +715,7 @@ def read_with_python_encoding(path: str, pyversion: Tuple[int, int]) -> str:
             source_bytearray.decode(encoding)
         except LookupError as lookuperr:
             raise DecodeError(str(lookuperr))
-        return source_bytearray.decode(encoding)
+        return source_bytearray.decode(encoding), hashlib.md5(source_bytearray).hexdigest()
 
 
 def get_cache_names(id: str, path: str, cache_dir: str,
@@ -766,6 +771,7 @@ def find_cache_meta(id: str, path: str, manager: BuildManager) -> Optional[Cache
         meta.get('path'),
         meta.get('mtime'),
         meta.get('size'),
+        meta.get('hash'),
         meta.get('dependencies', []),
         meta.get('data_mtime'),
         data_json,
@@ -809,8 +815,11 @@ def is_meta_fresh(meta: Optional[CacheMeta], id: str, path: str, manager: BuildM
     # TODO: Share stat() outcome with find_module()
     st = manager.get_stat(path)  # TODO: Errors
     if st.st_mtime != meta.mtime or st.st_size != meta.size:
-        manager.log('Metadata abandoned for {}: file {} is modified'.format(id, path))
-        return False
+        with open(path, 'rb') as f:
+            source_hash = hashlib.md5(f.read()).hexdigest()
+        if source_hash != meta.hash:
+            manager.log('Metadata abandoned for {}: file {} is modified'.format(id, path))
+            return False
 
     # It's a match on (id, path, mtime, size).
     # Check data_json; assume if its mtime matches it's good.
@@ -836,7 +845,7 @@ def compute_hash(text: str) -> str:
 def write_cache(id: str, path: str, tree: MypyFile,
                 dependencies: List[str], suppressed: List[str],
                 child_modules: List[str], dep_prios: List[int],
-                old_interface_hash: str, manager: BuildManager) -> str:
+                old_interface_hash: str, source_hash: str, manager: BuildManager) -> str:
     """Write cache files for a module.
 
     Note that this mypy's behavior is still correct when any given
@@ -926,10 +935,12 @@ def write_cache(id: str, path: str, tree: MypyFile,
     mtime = st.st_mtime
     size = st.st_size
     options = manager.options.clone_for_module(id)
+    assert source_hash is not None
     meta = {'id': id,
             'path': path,
             'mtime': mtime,
             'size': size,
+            'hash': source_hash,
             'data_mtime': data_mtime,
             'dependencies': dependencies,
             'suppressed': suppressed,
@@ -1116,6 +1127,7 @@ class State:
     path = None  # type: Optional[str]  # Path to module source
     xpath = None  # type: str  # Path or '<string>'
     source = None  # type: Optional[str]  # Module source code
+    source_hash = None  # type: str  # Hash calculated based on the source code
     meta = None  # type: Optional[CacheMeta]
     data = None  # type: Optional[str]
     tree = None  # type: Optional[MypyFile]
@@ -1421,7 +1433,8 @@ def parse_file(self) -> None:
             if self.path and source is None:
                 try:
                     path = manager.maybe_swap_for_shadow_path(self.path)
-                    source = read_with_python_encoding(path, self.options.python_version)
+                    source, self.source_hash = read_with_python_encoding(path,
+                                                                      self.options.python_version)
                 except IOError as ioerr:
                     raise CompileError([
                         "mypy: can't read file '{}': {}".format(self.path, ioerr.strerror)])
@@ -1572,7 +1585,7 @@ def write_cache(self) -> None:
         new_interface_hash = write_cache(
             self.id, self.path, self.tree,
             list(self.dependencies), list(self.suppressed), list(self.child_modules),
-            dep_prios, self.interface_hash,
+            dep_prios, self.interface_hash, self.source_hash,
             self.manager)
         if new_interface_hash == self.interface_hash:
             self.manager.log("Cached module {} has same interface".format(self.id))


Code review comments:
diff_hunk: @@ -710,7 +715,7 @@ def read_with_python_encoding(path: str, pyversion: Tuple[int, int]) -> str:
             source_bytearray.decode(encoding)
         except LookupError as lookuperr:
             raise DecodeError(str(lookuperr))
-        return source_bytearray.decode(encoding)
+        return source_bytearray.decode(encoding), hashlib.md5(source_bytearray).hexdigest()
path: mypy/build.py
text: @user1:
This is incorrect if a BOM marker is present, since on line 705 above the BOM marker is removed from source_bytearray.

@author:
Fixed in c115f139de74811d0635df50a946f3cab3a22b4c. I'm not sure why we make decision about encoding and BOM after just 2 lines rather than after reading the entire file; is it just because `source_bytearray = source_bytearray[3:]` is expensive when `source_bytearray` contains the entire file? Anyway, I assume that's the reason, so to avoid calling `f.read()` twice, I use `hashlib.md5.update()`.

diff_hunk: @@ -809,8 +815,11 @@ def is_meta_fresh(meta: Optional[CacheMeta], id: str, path: str, manager: BuildM
     # TODO: Share stat() outcome with find_module()
     st = manager.get_stat(path)  # TODO: Errors
     if st.st_mtime != meta.mtime or st.st_size != meta.size:
-        manager.log('Metadata abandoned for {}: file {} is modified'.format(id, path))
-        return False
+        with open(path, 'rb') as f:
path: mypy/build.py
text: @user1:
You only need to compare the hash when the sizes are equal.

There's another subtle issue here: if the mtime differs but the size and hash match, we don't rewrite the meta.json file (AFAICT), so that means that from then on we *always* hash the file. Now, the hashing seems so fast that this barely matters, but I want to use this for a huge codebase, so I'm still worried about this (else why bother with the mtime check). 

Also I'd like to see a log message if the mtime differs, but the size and hash are the same (this helps validating that it works).

@author:
> You only need to compare the hash when the sizes are equal.

Ah right, I left it as a placeholder but then forgot about it. Originally, I was thinking that maybe we should use a slightly more intelligent hash that ignores comments and ~~indentation~~ non-semantic whitespace (in which case size change doesn't necessarily imply that the file is invalid).  Do you think it's worth doing that, or I should just leave the simple hash in place?

Edit: given that interface hash is not too expensive and will take care of simple modifications in the file; and given that removing comments is not super fast (need to use `tokenize` module); I suppose the "smart hash" isn't worth it.

@author:
> There's another subtle issue here: if the mtime differs but the size and hash match, we don't rewrite the meta.json file (AFAICT), so that means that from then on we always hash the file.

Ah that *is* very subtle. We should either completely remove `mtime` from the cache logic, or we should update it in this scenario. I prefer the latter because writing `meta.json` is faster than reading and hashing the source file, and I'm guessing on average we can expect at least one additional read of the source file before it's completely invalidated.

@author:
I attempted to do the mtime optimization in 52a5888.

@user1:
FWIW "smart hash" sounds like a terrible idea, since it essentially comes down to parsing. People are used to the concept of hashing the contents of a file, and understand it to be some hash of the bytes.