Modules: Invalidate out-of-date PCMs as they're discovered

Leverage the InMemoryModuleCache to invalidate a module the first time
it fails to import (and to lock a module as soon as it's built or
imported successfully).  For implicit module builds, this optimizes
importing deep graphs where the leaf module is out-of-date; see example
near the end of the commit message.

Previously the cache finalized ("locked in") all modules imported so far
when starting a new module build.  This was sufficient to prevent
loading two versions of the same module, but was somewhat arbitrary and
hard to reason about.

Now the cache explicitly tracks module state, where each module must be
one of:

- Unknown: module not in the cache (yet).
- Tentative: module in the cache, but not yet fully imported.
- ToBuild: module found on disk could not be imported; need to build.
- Final: module in the cache has been successfully built or imported.

Preventing repeated failed imports avoids variation in builds based on
shifting filesystem state.  Now it's guaranteed that a module is loaded
from disk exactly once.  It now seems safe to remove
FileManager::invalidateCache, but I'm leaving that for a later commit.

The new, precise logic uncovered a pre-existing problem in the cache:
the map key is the module filename, and different contexts use different
filenames for the same PCM file.  (In particular, the test
Modules/relative-import-path.c does not build without this commit.
r223577 started using a relative path to describe a module's base
directory when importing it within another module.  As a result, the
module cache sees an absolute path when (a) building the module or
importing it at the top-level, and a relative path when (b) importing
the module underneath another one.)

The "obvious" fix is to resolve paths using FileManager::getVirtualFile
and change the map key for the cache to a FileEntry, but some contexts
(particularly related to ASTUnit) have a shorter lifetime for their
FileManager than the InMemoryModuleCache.  This is worth pursuing
further in a later commit; perhaps by tying together the FileManager and
InMemoryModuleCache lifetime, or moving the in-memory PCM storage into a
VFS layer.

For now, use the PCM's base directory as-written for constructing the
filename to check the ModuleCache.

Example
=======

To understand the build optimization, first consider the build of a
module graph TU -> A -> B -> C -> D with an empty cache:

    TU builds A'
       A' builds B'
          B' builds C'
             C' builds D'
                imports D'
          B' imports C'
             imports D'
       A' imports B'
          imports C'
          imports D'
    TU imports A'
       imports B'
       imports C'
       imports D'

If we build TU again, where A, B, C, and D are in the cache and D is
out-of-date, we would previously get this build:

    TU imports A
       imports B
       imports C
       imports D (out-of-date)
    TU builds A'
       A' imports B
          imports C
          imports D (out-of-date)
          builds B'
          B' imports C
             imports D (out-of-date)
             builds C'
             C' imports D (out-of-date)
                builds D'
                imports D'
          B' imports C'
             imports D'
       A' imports B'
          imports C'
          imports D'
     TU imports A'
        imports B'
        imports C'
        imports D'

After this commit, we'll immediateley invalidate A, B, C, and D when we
first observe that D is out-of-date, giving this build:

    TU imports A
       imports B
       imports C
       imports D (out-of-date)
    TU builds A' // The same graph as an empty cache.
       A' builds B'
          B' builds C'
             C' builds D'
                imports D'
          B' imports C'
             imports D'
       A' imports B'
          imports C'
          imports D'
    TU imports A'
       imports B'
       imports C'
       imports D'

The new build matches what we'd naively expect, pretty closely matching
the original build with the empty cache.

rdar://problem/48545366

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@355778 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 58 insertions, 29 deletions

diff --git a/include/clang/Serialization/ASTReader.h b/include/clang/Serialization/ASTReader.h
index 58a3b6594c..423313ea56 100644
--- a/include/clang/Serialization/ASTReader.h
+++ b/include/clang/Serialization/ASTReader.h
@@ -2231,6 +2231,10 @@ public:
   // Read a path
   std::string ReadPath(ModuleFile &F, const RecordData &Record, unsigned &Idx);
 
+  // Read a path
+  std::string ReadPath(StringRef BaseDirectory, const RecordData &Record,
+                       unsigned &Idx);
+
   // Skip a path
   static void SkipPath(const RecordData &Record, unsigned &Idx) {
     SkipString(Record, Idx);
diff --git a/include/clang/Serialization/InMemoryModuleCache.h b/include/clang/Serialization/InMemoryModuleCache.h
index aea4a8d60b..6d31e46b24 100644
--- a/include/clang/Serialization/InMemoryModuleCache.h
+++ b/include/clang/Serialization/InMemoryModuleCache.h
@@ -30,54 +30,79 @@ namespace clang {
 /// Critically, it ensures that a single process has a consistent view of each
 /// PCM.  This is used by \a CompilerInstance when building PCMs to ensure that
 /// each \a ModuleManager sees the same files.
-///
-/// \a finalizeCurrentBuffers() should be called before creating a new user.
-/// This locks in the current PCMs, ensuring that no PCM that has already been
-/// accessed can be purged, preventing use-after-frees.
 class InMemoryModuleCache : public llvm::RefCountedBase<InMemoryModuleCache> {
   struct PCM {
     std::unique_ptr<llvm::MemoryBuffer> Buffer;
 
-    /// Track the timeline of when this was added to the cache.
-    unsigned Index;
+    /// Track whether this PCM is known to be good (either built or
+    /// successfully imported by a CompilerInstance/ASTReader using this
+    /// cache).
+    bool IsFinal = false;
+
+    PCM() = default;
+    PCM(std::unique_ptr<llvm::MemoryBuffer> Buffer)
+        : Buffer(std::move(Buffer)) {}
   };
 
   /// Cache of buffers.
   llvm::StringMap<PCM> PCMs;
 
-  /// Monotonically increasing index.
-  unsigned NextIndex = 0;
-
-  /// Bumped to prevent "older" buffers from being removed.
-  unsigned FirstRemovableIndex = 0;
-
 public:
-  /// Store the Buffer under the Filename.
+  /// There are four states for a PCM.  It must monotonically increase.
+  ///
+  ///  1. Unknown: the PCM has neither been read from disk nor built.
+  ///  2. Tentative: the PCM has been read from disk but not yet imported or
+  ///     built.  It might work.
+  ///  3. ToBuild: the PCM read from disk did not work but a new one has not
+  ///     been built yet.
+  ///  4. Final: indicating that the current PCM was either built in this
+  ///     process or has been successfully imported.
+  enum State { Unknown, Tentative, ToBuild, Final };
+
+  /// Get the state of the PCM.
+  State getPCMState(llvm::StringRef Filename) const;
+
+  /// Store the PCM under the Filename.
   ///
-  /// \pre There is not already buffer is not already in the cache.
+  /// \pre state is Unknown
+  /// \post state is Tentative
   /// \return a reference to the buffer as a convenience.
-  llvm::MemoryBuffer &addBuffer(llvm::StringRef Filename,
-                                std::unique_ptr<llvm::MemoryBuffer> Buffer);
+  llvm::MemoryBuffer &addPCM(llvm::StringRef Filename,
+                             std::unique_ptr<llvm::MemoryBuffer> Buffer);
+
+  /// Store a just-built PCM under the Filename.
+  ///
+  /// \pre state is Unknown or ToBuild.
+  /// \pre state is not Tentative.
+  /// \return a reference to the buffer as a convenience.
+  llvm::MemoryBuffer &addBuiltPCM(llvm::StringRef Filename,
+                                  std::unique_ptr<llvm::MemoryBuffer> Buffer);
+
+  /// Try to remove a buffer from the cache.  No effect if state is Final.
+  ///
+  /// \pre state is Tentative/Final.
+  /// \post Tentative => ToBuild or Final => Final.
+  /// \return false on success, i.e. if Tentative => ToBuild.
+  bool tryToDropPCM(llvm::StringRef Filename);
 
-  /// Try to remove a buffer from the cache.
+  /// Mark a PCM as final.
   ///
-  /// \return false on success, iff \c !isBufferFinal().
-  bool tryToRemoveBuffer(llvm::StringRef Filename);
+  /// \pre state is Tentative or Final.
+  /// \post state is Final.
+  void finalizePCM(llvm::StringRef Filename);
 
-  /// Get a pointer to the buffer if it exists; else nullptr.
-  llvm::MemoryBuffer *lookupBuffer(llvm::StringRef Filename);
+  /// Get a pointer to the pCM if it exists; else nullptr.
+  llvm::MemoryBuffer *lookupPCM(llvm::StringRef Filename) const;
 
-  /// Check whether the buffer is final.
+  /// Check whether the PCM is final and has been shown to work.
   ///
-  /// \return true iff \a finalizeCurrentBuffers() has been called since the
-  /// buffer was added.  This prevents buffers from being removed.
-  bool isBufferFinal(llvm::StringRef Filename);
+  /// \return true iff state is Final.
+  bool isPCMFinal(llvm::StringRef Filename) const;
 
-  /// Finalize the current buffers in the cache.
+  /// Check whether the PCM is waiting to be built.
   ///
-  /// Should be called when creating a new user to ensure previous uses aren't
-  /// invalidated.
-  void finalizeCurrentBuffers();
+  /// \return true iff state is ToBuild.
+  bool shouldBuildPCM(llvm::StringRef Filename) const;
 };
 
 } // end namespace clang