Rework cache to key on hash of file contents instead of mtime

[gvanrossum]

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).

[pkch]

I'll work on it.

[pkch]

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

[pkch]

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).

[pkch]

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.

[pkch]

@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).