[Preamble] Invalidate preamble when missing headers become present.

[sammccall]

Summary

To avoid excessive extra stat()s, only check the possible locations of
headers that weren't found at all (leading to a compile error).
For headers that *were* found, we don't check for files earlier on the
search path that could override them.

[sammccall]

At first I thought this would be easy to test via clang/test/PCH, but the outer layers of PrecompiledPreamble seem to be totally distinct from PCHGenerator etc. This is only used in ASTUnit and clangd.
Maybe it's reachable in libclang but I couldn't easily work out how.

[kadircet]

It is unfortunate that we are testing PrecompiledPreamble through clangd rather than its own unittest :/

clang/lib/Frontend/PrecompiledPreamble.cpp

101

is there a common recovery logic implemented in clang that makes this logic worth it?
because none of the existing clients seems to be implementing it.

I would rather check for File == nullptr in InclusionDirective and maybe put a fixme saying that this might still be set by a "recovering ppcallback".

Up to you though.

137

nit: braces

589

i believe it can also be provided by an overridefile. maybe also check this above while going over RemappedFiles. i.e:

for(... &R : ..RemappedFiles) {
   if(!stat(R.second)) return false;
   // A missing file has been remapped into an existing file.
   if(MissingFiles.count(R.first)) return false;
 ....
}

590

i am not sure if this works in all cases.

Assume there's a mapped buffer for "a.h", which is relative to main file.

I suppose this will be recorded with fullpath in MissingFiles, hence this lookup will fail.

[sammccall]

Finally address comments

clang/lib/Frontend/PrecompiledPreamble.cpp

101

Done. I think a fixme is disingenuous though if we deliberately un-fixed it :-)
Left a non-committal comment.

589

Decided to just add a new set containing abs paths for everything that got overridden.

[kadircet]

mostly LG, sorry for not noticing regularfile check(or maybe forgetting a discussion ...) at previous revision

clang/lib/Frontend/PrecompiledPreamble.cpp

108

um, shouldn't this be

if (File != nullptr)
  return;

? as we are only interested in not-found files?

529

128 seems to be more widely used :P

595

what about others? at least symlinks ?

[sammccall]

clang/lib/Frontend/PrecompiledPreamble.cpp

108

Yeah, I guess I should have run the tests :-)

595

RealFileSystem::status() resolves symlinks (calls fs::status() with no resolve arg, defaults to true). That's the most important case, and other VFSes that support symlinks should really do the same for compatibility.

[sammccall]

address comments

[kadircet]

LGTM, thanks! Let's build more preambles !

clang-tools-extra/clangd/unittests/ClangdLSPServerTests.cpp

EXPECT_THAT(Client.diagnostics("foo.cpp"),
                               "an lvalue of type 'const char [3]'"))));
 
   Client.didClose("foo.cpp");
   EXPECT_THAT(Client.diagnostics("foo.cpp"), llvm::ValueIs(testing::IsEmpty()));
 }
 
 TEST_F(LSPTest, DiagnosticsHeaderSaved) {
   auto &Client = start();
-  FS.Files["foo.h"] = "#define VAR original";
   Client.didOpen("foo.cpp", R"cpp(
     #include "foo.h"
     int x = VAR;
   )cpp");
   EXPECT_THAT(Client.diagnostics("foo.cpp"),
               llvm::ValueIs(testing::ElementsAre(
+                  DiagMessage("'foo.h' file not found"),
+                  DiagMessage("Use of undeclared identifier 'VAR'"))));
+  // Now create the header.
+  FS.Files["foo.h"] = "#define VAR original";
+  Client.notify(
+      "textDocument/didSave",
+      llvm::json::Object{{"textDocument", Client.documentID("foo.h")}});
+  EXPECT_THAT(Client.diagnostics("foo.cpp"),
+              llvm::ValueIs(testing::ElementsAre(
                   DiagMessage("Use of undeclared identifier 'original'"))));
   // Now modify the header from within the "editor".
   FS.Files["foo.h"] = "#define VAR changed";
   Client.notify(
       "textDocument/didSave",
       llvm::json::Object{{"textDocument", Client.documentID("foo.h")}});
   // Foo.cpp should be rebuilt with new diagnostics.
   EXPECT_THAT(Client.diagnostics("foo.cpp"),

clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp

TEST_F(TUSchedulerTests, NoopOnEmptyChanges) {
   // Update to the compile commands should also cause a rebuild.
   CDB.ExtraClangFlags.push_back("-DSOMETHING");
   ASSERT_TRUE(DoUpdate(SourceContents));
   ASSERT_FALSE(DoUpdate(SourceContents));
   ASSERT_EQ(S.fileStats().lookup(Source).ASTBuilds, 4u);
   ASSERT_EQ(S.fileStats().lookup(Source).PreambleBuilds, 3u);
 }
 
-TEST_F(TUSchedulerTests, ForceRebuild) {
+// We rebuild if a completely missing header exists, but not if one is added
+// on a higher-priority include path entry (for performance).
+// (Previously we wouldn't automatically rebuild when files were added).
+TEST_F(TUSchedulerTests, MissingHeader) {
+  CDB.ExtraClangFlags.push_back("-I" + testPath("a"));
+  CDB.ExtraClangFlags.push_back("-I" + testPath("b"));
+  // Force both directories to exist so they don't get pruned.
+  Files.try_emplace("a/__unused__");
+  Files.try_emplace("b/__unused__");
   TUScheduler S(CDB, optsForTest(), captureDiags());
 
   auto Source = testPath("foo.cpp");
-  auto Header = testPath("foo.h");
+  auto HeaderA = testPath("a/foo.h");
+  auto HeaderB = testPath("b/foo.h");
 
   auto SourceContents = R"cpp(
       #include "foo.h"
-      int b = a;
+      int c = b;
     )cpp";
 
   ParseInputs Inputs = getInputs(Source, SourceContents);
   std::atomic<size_t> DiagCount(0);
 
   // Update the source contents, which should trigger an initial build with
   // the header file missing.
   updateWithDiags(
       S, Source, Inputs, WantDiagnostics::Yes,
       [&DiagCount](std::vector<Diag> Diags) {
         ++DiagCount;
         EXPECT_THAT(Diags,
                     ElementsAre(Field(&Diag::Message, "'foo.h' file not found"),
                                 Field(&Diag::Message,
-                                      "use of undeclared identifier 'a'")));
+                                      "use of undeclared identifier 'b'")));
       });
 
   // Add the header file. We need to recreate the inputs since we changed a
   // file from underneath the test FS.
-  Files[Header] = "int a;";
-  Timestamps[Header] = time_t(1);
+  Files[HeaderB] = "int b;";
+  Timestamps[HeaderB] = time_t(1);
   Inputs = getInputs(Source, SourceContents);
 
-  // The addition of the missing header file shouldn't trigger a rebuild since
-  // we don't track missing files.
+  // The addition of the missing header file triggers a rebuild, no errors.
   updateWithDiags(
       S, Source, Inputs, WantDiagnostics::Yes,
       [&DiagCount](std::vector<Diag> Diags) {
         ++DiagCount;
-        ADD_FAILURE() << "Did not expect diagnostics for missing header update";
+        EXPECT_THAT(Diags, IsEmpty());
       });
 
-  // Forcing the reload should should cause a rebuild which no longer has any
-  // errors.
+  // Add the high-priority header file, which should reintroduce the error.
+  Files[HeaderA] = "int a;";
+  Timestamps[HeaderA] = time_t(1);
+  Inputs = getInputs(Source, SourceContents);
+
+  // This isn't detected: we don't stat a/foo.h to validate the preamble.
+  updateWithDiags(S, Source, Inputs, WantDiagnostics::Yes,
+                  [&DiagCount](std::vector<Diag> Diags) {
+                    ++DiagCount;
+                    ADD_FAILURE()
+                        << "Didn't expect new diagnostics when adding a/foo.h";
+                  });
+
+  // Forcing the reload should should cause a rebuild.
   Inputs.ForceRebuild = true;
   updateWithDiags(S, Source, Inputs, WantDiagnostics::Yes,
                   [&DiagCount](std::vector<Diag> Diags) {
                     ++DiagCount;
-                    EXPECT_THAT(Diags, IsEmpty());
+                    ElementsAre(Field(&Diag::Message,
+                                      "use of undeclared identifier 'b'"));
                   });
 
   ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
-  EXPECT_EQ(DiagCount, 2U);
+  EXPECT_EQ(DiagCount, 3U);
 }
+
 TEST_F(TUSchedulerTests, NoChangeDiags) {
   trace::TestTracer Tracer;
   TUScheduler S(CDB, optsForTest(), captureDiags());
 
   auto FooCpp = testPath("foo.cpp");
   const auto *Contents = "int a; int b;";
 
   EXPECT_THAT(Tracer.takeMetric("ast_access_read", "hit"), SizeIs(0));

clang/include/clang/Frontend/PrecompiledPreamble.h

public:
   /// If this preamble does not match the file, it may parse differently.
   void OverridePreamble(CompilerInvocation &CI,
                         IntrusiveRefCntPtr<llvm::vfs::FileSystem> &VFS,
                         llvm::MemoryBuffer *MainFileBuffer) const;
 
 private:
   PrecompiledPreamble(PCHStorage Storage, std::vector<char> PreambleBytes,
                       bool PreambleEndsAtStartOfLine,
-                      llvm::StringMap<PreambleFileHash> FilesInPreamble);
+                      llvm::StringMap<PreambleFileHash> FilesInPreamble,
+                      llvm::StringSet<> MissingFiles);
 
   /// A temp file that would be deleted on destructor call. If destructor is not
   /// called for any reason, the file will be deleted at static objects'
   /// destruction.
   /// An assertion will fire if two TempPCHFiles are created with the same name,
   /// so it's not intended to be used outside preamble-handling.
   class TempPCHFile {
   public:
private:
   /// Manages the memory buffer or temporary file that stores the PCH.
   PCHStorage Storage;
   /// Keeps track of the files that were used when computing the
   /// preamble, with both their buffer size and their modification time.
   ///
   /// If any of the files have changed from one compile to the next,
   /// the preamble must be thrown away.
   llvm::StringMap<PreambleFileHash> FilesInPreamble;
+  /// Files that were not found during preamble building. If any of these now
+  /// exist then the preamble should not be reused.
+  ///
+  /// Storing *all* the missing files that could invalidate the preamble would
+  /// make it too expensive to revalidate (when the include path has many
+  /// entries, each #include will miss half of them on average).
+  /// Instead, we track only files that could have satisfied an #include that
+  /// was ultimately not found.
+  llvm::StringSet<> MissingFiles;
   /// The contents of the file that was used to precompile the preamble. Only
   /// contains first PreambleBounds::Size bytes. Used to compare if the relevant
   /// part of the file has not changed, so that preamble can be reused.
   std::vector<char> PreambleBytes;
   /// See PreambleBounds::PreambleEndsAtStartOfLine
   bool PreambleEndsAtStartOfLine;
 };
 

clang/lib/Frontend/PrecompiledPreamble.cpp

 #include "clang/AST/DeclObjC.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangStandard.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Frontend/FrontendOptions.h"
+#include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #include "clang/Serialization/ASTWriter.h"
+#include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSet.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/CrashRecoveryContext.h"
 #include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include <limits>
 #include <mutex>
 #include <utility>
 
 using namespace clang;
 
public:
   // We want to collect all dependencies for correctness. Avoiding the real
   // system dependencies (e.g. stl from /usr/lib) would probably be a good idea,
   // but there is no way to distinguish between those and the ones that can be
   // spuriously added by '-isystem' (e.g. to suppress warnings from those
   // headers).
   bool needSystemDependencies() override { return true; }
 };
 
+// Collects files whose existence would invalidate the preamble.
+// Collecting *all* of these would make validating it too slow though, so we
+// just find all the candidates for 'file not found' diagnostics.
+//
+// A caveat that may be significant for generated files: we'll omit files under
+// search path entries whose roots don't exist when the preamble is built.
+// These are pruned by InitHeaderSearch and so we don't see the search path.
+// It would be nice to include them but we don't want to duplicate all the rest
+// of the InitHeaderSearch logic to reconstruct them.
+class MissingFileCollector : public PPCallbacks {
+  llvm::StringSet<> &Out;
+  const HeaderSearch &Search;
+  const SourceManager &SM;
+
+public:
+  MissingFileCollector(llvm::StringSet<> &Out, const HeaderSearch &Search,
+                       const SourceManager &SM)
+      : Out(Out), Search(Search), SM(SM) {}
+
+  void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
+                          StringRef FileName, bool IsAngled,
+                          CharSourceRange FilenameRange, const FileEntry *File,
+                          StringRef SearchPath, StringRef RelativePath,
+                          const Module *Imported,
+                          SrcMgr::CharacteristicKind FileType) override {
+    // File is null if it wasn't found.
+    // (We have some false negatives if PP recovered e.g. <foo> -> "foo")
+    if (File != nullptr)
+      return;
+
+    // If it's a rare absolute include, we know the full path already.
+    if (llvm::sys::path::is_absolute(FileName)) {
+      Out.insert(FileName);
+      return;
+    }
+
+    // Reconstruct the filenames that would satisfy this directive...
+    llvm::SmallString<256> Buf;
+    auto NotFoundRelativeTo = [&](const DirectoryEntry *DE) {
+      Buf = DE->getName();
+      llvm::sys::path::append(Buf, FileName);
+      llvm::sys::path::remove_dots(Buf, /*remove_dot_dot=*/true);
+      Out.insert(Buf);
+    };
+    // ...relative to the including file.
+    if (!IsAngled) {
+      if (const FileEntry *IncludingFile =
+              SM.getFileEntryForID(SM.getFileID(IncludeTok.getLocation())))
+        if (IncludingFile->getDir())
+          NotFoundRelativeTo(IncludingFile->getDir());
+    }
+    // ...relative to the search paths.
+    for (const auto &Dir : llvm::make_range(
+             IsAngled ? Search.angled_dir_begin() : Search.search_dir_begin(),
+             Search.search_dir_end())) {
+      // No support for frameworks or header maps yet.
+      if (Dir.isNormalDir())
+        NotFoundRelativeTo(Dir.getDir());
+    }
+  }
+};
+
 /// Keeps a track of files to be deleted in destructor.
 class TemporaryFiles {
 public:
   // A static instance to be used by all clients.
   static TemporaryFiles &getInstance();
 
 private:
   // Disallow constructing the class directly.
if (!Act->BeginSourceFile(*Clang.get(), Clang->getFrontendOpts().Inputs[0]))
     return BuildPreambleError::BeginSourceFileFailed;
 
   std::unique_ptr<PPCallbacks> DelegatedPPCallbacks =
       Callbacks.createPPCallbacks();
   if (DelegatedPPCallbacks)
     Clang->getPreprocessor().addPPCallbacks(std::move(DelegatedPPCallbacks));
   if (auto CommentHandler = Callbacks.getCommentHandler())
     Clang->getPreprocessor().addCommentHandler(CommentHandler);
+  llvm::StringSet<> MissingFiles;
+  Clang->getPreprocessor().addPPCallbacks(
+      std::make_unique<MissingFileCollector>(
+          MissingFiles, Clang->getPreprocessor().getHeaderSearchInfo(),
+          Clang->getSourceManager()));
 
   if (llvm::Error Err = Act->Execute())
     return errorToErrorCode(std::move(Err));
 
   // Run the callbacks.
   Callbacks.AfterExecute(*Clang);
 
   Act->EndSourceFile();
if (time_t ModTime = File->getModificationTime()) {
                                                                ModTime);
     } else {
       const llvm::MemoryBuffer *Buffer = SourceMgr.getMemoryBufferForFile(File);
       FilesInPreamble[File->getName()] =
           PrecompiledPreamble::PreambleFileHash::createForMemoryBuffer(Buffer);
     }
   }
 
-  return PrecompiledPreamble(std::move(Storage), std::move(PreambleBytes),
-                             PreambleEndsAtStartOfLine,
-                             std::move(FilesInPreamble));
+  return PrecompiledPreamble(
+      std::move(Storage), std::move(PreambleBytes), PreambleEndsAtStartOfLine,
+      std::move(FilesInPreamble), std::move(MissingFiles));
 }
 
 PreambleBounds PrecompiledPreamble::getBounds() const {
   return PreambleBounds(PreambleBytes.size(), PreambleEndsAtStartOfLine);
 }
 
 std::size_t PrecompiledPreamble::getSize() const {
   switch (Storage.getKind()) {
if (PreambleBytes.size() != Bounds.Size ||
     return false;
   // The preamble has not changed. We may be able to re-use the precompiled
   // preamble.
 
   // Check that none of the files used by the preamble have changed.
   // First, make a record of those files that have been overridden via
   // remapping or unsaved_files.
   std::map<llvm::sys::fs::UniqueID, PreambleFileHash> OverriddenFiles;
+  llvm::StringSet<> OverriddenAbsPaths; // Either by buffers or files.
   for (const auto &R : PreprocessorOpts.RemappedFiles) {
     llvm::vfs::Status Status;
     if (!moveOnNoError(VFS->status(R.second), Status)) {
       // If we can't stat the file we're remapping to, assume that something
       // horrible happened.
       return false;
     }
+    // If a mapped file was previously missing, then it has changed.
+    llvm::SmallString<128> MappedPath(R.first);
+    if (!VFS->makeAbsolute(MappedPath))
+      OverriddenAbsPaths.insert(MappedPath);
 
     OverriddenFiles[Status.getUniqueID()] = PreambleFileHash::createForFile(
         Status.getSize(), llvm::sys::toTimeT(Status.getLastModificationTime()));
   }
 
   // OverridenFileBuffers tracks only the files not found in VFS.
   llvm::StringMap<PreambleFileHash> OverridenFileBuffers;
   for (const auto &RB : PreprocessorOpts.RemappedFileBuffers) {
     const PrecompiledPreamble::PreambleFileHash PreambleHash =
         PreambleFileHash::createForMemoryBuffer(RB.second);
     llvm::vfs::Status Status;
     if (moveOnNoError(VFS->status(RB.first), Status))
       OverriddenFiles[Status.getUniqueID()] = PreambleHash;
     else
       OverridenFileBuffers[RB.first] = PreambleHash;
+
+    llvm::SmallString<128> MappedPath(RB.first);
+    if (!VFS->makeAbsolute(MappedPath))
+      OverriddenAbsPaths.insert(MappedPath);
   }
 
   // Check whether anything has changed.
   for (const auto &F : FilesInPreamble) {
     auto OverridenFileBuffer = OverridenFileBuffers.find(F.first());
     if (OverridenFileBuffer != OverridenFileBuffers.end()) {
       // The file's buffer was remapped and the file was not found in VFS.
       // Check whether it matches up with the previous mapping.
for (const auto &F : FilesInPreamble) {
 
     // Neither the file's buffer nor the file itself was remapped;
     // check whether it has changed on disk.
     if (Status.getSize() != uint64_t(F.second.Size) ||
         llvm::sys::toTimeT(Status.getLastModificationTime()) !=
             F.second.ModTime)
       return false;
   }
+  for (const auto &F : MissingFiles) {
+    // A missing file may be "provided" by an override buffer or file.
+    if (OverriddenAbsPaths.count(F.getKey()))
+      return false;
+    // If a file previously recorded as missing exists as a regular file, then
+    // consider the preamble out-of-date.
+    if (auto Status = VFS->status(F.getKey())) {
+      if (Status->isRegularFile())
+        return false;
+    }
+  }
   return true;
 }
 
 void PrecompiledPreamble::AddImplicitPreamble(
     CompilerInvocation &CI, IntrusiveRefCntPtr<llvm::vfs::FileSystem> &VFS,
     llvm::MemoryBuffer *MainFileBuffer) const {
   PreambleBounds Bounds(PreambleBytes.size(), PreambleEndsAtStartOfLine);
   configurePreamble(Bounds, CI, VFS, MainFileBuffer);
 }
 
 void PrecompiledPreamble::OverridePreamble(
     CompilerInvocation &CI, IntrusiveRefCntPtr<llvm::vfs::FileSystem> &VFS,
     llvm::MemoryBuffer *MainFileBuffer) const {
   auto Bounds = ComputePreambleBounds(*CI.getLangOpts(), MainFileBuffer, 0);
   configurePreamble(Bounds, CI, VFS, MainFileBuffer);
 }
 
 PrecompiledPreamble::PrecompiledPreamble(
     PCHStorage Storage, std::vector<char> PreambleBytes,
     bool PreambleEndsAtStartOfLine,
-    llvm::StringMap<PreambleFileHash> FilesInPreamble)
+    llvm::StringMap<PreambleFileHash> FilesInPreamble,
+    llvm::StringSet<> MissingFiles)
     : Storage(std::move(Storage)), FilesInPreamble(std::move(FilesInPreamble)),
+      MissingFiles(std::move(MissingFiles)),
       PreambleBytes(std::move(PreambleBytes)),
       PreambleEndsAtStartOfLine(PreambleEndsAtStartOfLine) {
   assert(this->Storage.getKind() != PCHStorage::Kind::Empty);
 }
 
 llvm::ErrorOr<PrecompiledPreamble::TempPCHFile>
 PrecompiledPreamble::TempPCHFile::CreateNewPreamblePCHFile() {
   // FIXME: This is a hack so that we can override the preamble file during