[clangd] Fix header-guard check for include insertion, and don't index header guards.

[sammccall]

Summary

Both of these attempt to check whether a header guard exists while parsing the
file. However the file is only marked as guarded once clang finishes processing
it. We defer the checks and work until SymbolCollector::finish().

This is ugly and ad-hoc, deferring *all* work might be cleaner.

[kadircet]

Thanks!

mostly LGTM, only confused about changing symbolcollector to produce a unique header per symbol(where as it was(could) produce multiple headers before).
What is the rationale behind that one?

clangd/index/SymbolCollector.h

130

This is losing ability to store multiple header files. Is that intentional?

clangd/unittests/SymbolCollectorTests.cpp

1043

can you also add a case where we first see MACRO and then decl.

[sammccall]

Extract setIncludeLocation() and call it from a more obvious point in the code.
Tweak test to make it harder.

clangd/index/SymbolCollector.h

130

Careful reading of the code shows that ability never existed :-) addDeclaration always creates a new Symbol, sometimes populates its IncludeHeaders, and then replaces the existing symbol. We always find a single decl of the symbol we prefer in the TU (though sometimes it takes us a few attempts).

Of course, I never read the code that carefully - I wrote this as a vector<pair<SymbolID, FileID>> to "preserve" the ability to add multiple headers... and then the tests failed :-)

clangd/unittests/SymbolCollectorTests.cpp

1043

IIUC the idea is that macros are "eager-er" than decls so more likely to break the caching. That makes sense.

WDYT about just putting the macro first, so we *only* test the "hard" case.

[kadircet]

clangd/index/SymbolCollector.h

130

Ah, ok I see. Thanks for pointing this out!

clangd/unittests/SymbolCollectorTests.cpp

1043

exactly, SGTM

clangd/index/Symbol.h

public:
   class Builder {
   public:
     Builder() : UniqueStrings(Arena) {}
 
     /// Adds a symbol, overwriting any existing one with the same ID.
     /// This is a deep copy: underlying strings will be owned by the slab.
     void insert(const Symbol &S);
 
-    /// Returns the symbol with an ID, if it exists. Valid until next insert().
+    /// Removes the symbol with an ID, if it exists.
+    void erase(const SymbolID &ID) { Symbols.erase(ID); }
+
+    /// Returns the symbol with an ID, if it exists. Valid until insert/remove.
     const Symbol *find(const SymbolID &ID) {
-      auto I = SymbolIndex.find(ID);
-      return I == SymbolIndex.end() ? nullptr : &Symbols[I->second];
+      auto I = Symbols.find(ID);
+      return I == Symbols.end() ? nullptr : &I->second;
     }
 
     /// Consumes the builder to finalize the slab.
     SymbolSlab build() &&;
 
   private:
     llvm::BumpPtrAllocator Arena;
     /// Intern table for strings. Contents are on the arena.
     llvm::UniqueStringSaver UniqueStrings;
-    std::vector<Symbol> Symbols;
     /// Values are indices into Symbols vector.
-    llvm::DenseMap<SymbolID, size_t> SymbolIndex;
+    llvm::DenseMap<SymbolID, Symbol> Symbols;
   };
 
 private:
   SymbolSlab(llvm::BumpPtrAllocator Arena, std::vector<Symbol> Symbols)
       : Arena(std::move(Arena)), Symbols(std::move(Symbols)) {}
 
   llvm::BumpPtrAllocator Arena; // Owns Symbol data that the Symbols do not.
   std::vector<Symbol> Symbols;  // Sorted by SymbolID to allow lookup.
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOL_H

clangd/index/Symbol.cpp

 }
 
 // Copy the underlying data of the symbol into the owned arena.
 static void own(Symbol &S, llvm::UniqueStringSaver &Strings) {
   visitStrings(S, [&](llvm::StringRef &V) { V = Strings.save(V); });
 }
 
 void SymbolSlab::Builder::insert(const Symbol &S) {
-  auto R = SymbolIndex.try_emplace(S.ID, Symbols.size());
-  if (R.second) {
-    Symbols.push_back(S);
-    own(Symbols.back(), UniqueStrings);
-  } else {
-    auto &Copy = Symbols[R.first->second] = S;
-    own(Copy, UniqueStrings);
-  }
+  own(Symbols[S.ID] = S, UniqueStrings);
 }
 
 SymbolSlab SymbolSlab::Builder::build() && {
-  Symbols = {Symbols.begin(), Symbols.end()}; // Force shrink-to-fit.
-  // Sort symbols so the slab can binary search over them.
-  llvm::sort(Symbols,
+  // Sort symbols into vector so the slab can binary search over them.
+  std::vector<Symbol> SortedSymbols;
+  SortedSymbols.reserve(Symbols.size());
+  for (auto &Entry : Symbols)
+    SortedSymbols.push_back(std::move(Entry.second));
+  llvm::sort(SortedSymbols,
              [](const Symbol &L, const Symbol &R) { return L.ID < R.ID; });
   // We may have unused strings from overwritten symbols. Build a new arena.
   llvm::BumpPtrAllocator NewArena;
   llvm::UniqueStringSaver Strings(NewArena);
-  for (auto &S : Symbols)
+  for (auto &S : SortedSymbols)
     own(S, Strings);
-  return SymbolSlab(std::move(NewArena), std::move(Symbols));
+  return SymbolSlab(std::move(NewArena), std::move(SortedSymbols));
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.h

private:
 
   llvm::Optional<std::string> getIncludeHeader(llvm::StringRef QName, FileID);
   bool isSelfContainedHeader(FileID);
   // Heuristically headers that only want to be included via an umbrella.
   static bool isDontIncludeMeHeader(llvm::StringRef);
 
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
+  // File IDs for Symbol.IncludeHeaders.
+  // The final spelling is calculated in finish().
+  llvm::DenseMap<SymbolID, FileID> IncludeFiles;
+  void setIncludeLocation(const Symbol &S, SourceLocation);
+  // Indexed macros, to be erased if they turned out to be include guards.
+  llvm::DenseSet<const IdentifierInfo *> IndexedMacros;
   // All refs collected from the AST.
   // Only symbols declared in preamble (from #include) and referenced from the
   // main file will be included.
   RefSlab::Builder Refs;
   ASTContext *ASTCtx;
   std::shared_ptr<Preprocessor> PP;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
   std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo;

clangd/index/SymbolCollector.cpp

bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
                                            SourceLocation Loc) {
   if (!Opts.CollectMacro)
     return true;
   assert(PP.get());
 
   const auto &SM = PP->getSourceManager();
   auto DefLoc = MI->getDefinitionLoc();
 
-  // Header guards are not interesting in index. Builtin macros don't have
-  // useful locations and are not needed for code completions.
-  if (MI->isUsedForHeaderGuard() || MI->isBuiltinMacro())
+  // Builtin macros don't have useful locations and aren't needed in completion.
+  if (MI->isBuiltinMacro())
     return true;
 
   // Skip main-file symbols if we are not collecting them.
   bool IsMainFileSymbol = SM.isInMainFile(SM.getExpansionLoc(DefLoc));
   if (IsMainFileSymbol && !Opts.CollectMainFileSymbols)
     return false;
 
   // Also avoid storing predefined macros like __DBL_MIN__.
if (auto DeclLoc =
     S.CanonicalDeclaration = *DeclLoc;
 
   CodeCompletionResult SymbolCompletion(Name);
   const auto *CCS = SymbolCompletion.CreateCodeCompletionStringForMacro(
       *PP, *CompletionAllocator, *CompletionTUInfo);
   std::string Signature;
   std::string SnippetSuffix;
   getSignature(*CCS, &Signature, &SnippetSuffix);
-
-  std::string Include;
-  if (Opts.CollectIncludePath && shouldCollectIncludePath(S.SymInfo.Kind)) {
-    if (auto Header = getIncludeHeader(
-            Name->getName(), SM.getDecomposedExpansionLoc(DefLoc).first))
-      Include = std::move(*Header);
-  }
   S.Signature = Signature;
   S.CompletionSnippetSuffix = SnippetSuffix;
-  if (!Include.empty())
-    S.IncludeHeaders.emplace_back(Include, 1);
 
+  IndexedMacros.insert(Name);
+  setIncludeLocation(S, DefLoc);
   Symbols.insert(S);
   return true;
 }
 
+void SymbolCollector::setIncludeLocation(const Symbol &S,
+                                         SourceLocation Loc) {
+  if (Opts.CollectIncludePath)
+    if (shouldCollectIncludePath(S.SymInfo.Kind))
+      // Use the expansion location to get the #include header since this is
+      // where the symbol is exposed.
+      IncludeFiles[S.ID] =
+          PP->getSourceManager().getDecomposedExpansionLoc(Loc).first;
+}
+
 void SymbolCollector::finish() {
   // At the end of the TU, add 1 to the refcount of all referenced symbols.
   auto IncRef = [this](const SymbolID &ID) {
     if (const auto *S = Symbols.find(ID)) {
       Symbol Inc = *S;
       ++Inc.References;
       Symbols.insert(Inc);
     }
   };
   for (const NamedDecl *ND : ReferencedDecls) {
     if (auto ID = getSymbolID(ND)) {
       IncRef(*ID);
     }
   }
   if (Opts.CollectMacro) {
     assert(PP);
+    // First, drop header guards. We can't identify these until EOF.
+    for (const IdentifierInfo *II : IndexedMacros) {
+      if (const auto *MI = PP->getMacroDefinition(II).getMacroInfo())
+        if (auto ID = getSymbolID(*II, MI, PP->getSourceManager()))
+          if (MI->isUsedForHeaderGuard())
+            Symbols.erase(*ID);
+    }
+    // Now increment refcounts.
     for (const IdentifierInfo *II : ReferencedMacros) {
       if (const auto *MI = PP->getMacroDefinition(II).getMacroInfo())
         if (auto ID = getSymbolID(*II, MI, PP->getSourceManager()))
           IncRef(*ID);
     }
   }
 
+  // Fill in IncludeHeaders.
+  // We delay this until end of TU so header guards are all resolved.
+  // Symbols in slabs aren' mutable, so insert() has to walk all the strings :-(
+  llvm::SmallString<256> QName;
+  for (const auto &Entry : IncludeFiles)
+    if (const Symbol *S = Symbols.find(Entry.first)) {
+      QName = S->Scope;
+      QName.append(S->Name);
+      if (auto Header = getIncludeHeader(QName, Entry.second)) {
+        Symbol NewSym = *S;
+        NewSym.IncludeHeaders.push_back({*Header, 1});
+        Symbols.insert(NewSym);
+      }
+    }
+
   const auto &SM = ASTCtx->getSourceManager();
   llvm::DenseMap<FileID, std::string> URICache;
   auto GetURI = [&](FileID FID) -> llvm::Optional<std::string> {
     auto Found = URICache.find(FID);
     if (Found == URICache.end()) {
       if (auto *FileEntry = SM.getFileEntryForID(FID)) {
         auto FileURI = toURI(SM, FileEntry->getName(), Opts);
         Found = URICache.insert({FID, FileURI}).first;
       } else {
         // Ignore cases where we can not find a corresponding file entry
         // for the loc, thoses are not interesting, e.g. symbols formed
         // via macro concatenation.
         return None;
       }
     }
     return Found->second;
   };
-
+  // Populate Refs slab from DeclRefs.
   if (auto MainFileURI = GetURI(SM.getMainFileID())) {
     for (const auto &It : DeclRefs) {
       if (auto ID = getSymbolID(It.first)) {
         for (const auto &LocAndRole : It.second) {
           auto FileID = SM.getFileID(LocAndRole.first);
           // FIXME: use the result to filter out references.
           shouldIndexFile(SM, FileID, Opts, &FilesToIndexCache);
           if (auto FileURI = GetURI(FileID)) {
if (auto MainFileURI = GetURI(SM.getMainFileID())) {
     }
   }
 
   ReferencedDecls.clear();
   ReferencedMacros.clear();
   DeclRefs.clear();
   FilesToIndexCache.clear();
   HeaderIsSelfContainedCache.clear();
+  IncludeFiles.clear();
 }
 
 const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, SymbolID ID,
                                               bool IsMainFileOnly) {
   auto &Ctx = ND.getASTContext();
   auto &SM = Ctx.getSourceManager();
 
   Symbol S;
const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, SymbolID ID,
   std::string Signature;
   std::string SnippetSuffix;
   getSignature(*CCS, &Signature, &SnippetSuffix);
   S.Signature = Signature;
   S.CompletionSnippetSuffix = SnippetSuffix;
   std::string ReturnType = getReturnType(*CCS);
   S.ReturnType = ReturnType;
 
-  std::string Include;
-  if (Opts.CollectIncludePath && shouldCollectIncludePath(S.SymInfo.Kind)) {
-    // Use the expansion location to get the #include header since this is
-    // where the symbol is exposed.
-    if (auto Header = getIncludeHeader(
-            QName, SM.getDecomposedExpansionLoc(ND.getLocation()).first))
-      Include = std::move(*Header);
-  }
-  if (!Include.empty())
-    S.IncludeHeaders.emplace_back(Include, 1);
-
   llvm::Optional<OpaqueType> TypeStorage;
   if (S.Flags & Symbol::IndexedForCodeCompletion) {
     TypeStorage = OpaqueType::fromCompletionResult(*ASTCtx, SymbolCompletion);
     if (TypeStorage)
       S.Type = TypeStorage->raw();
   }
 
   Symbols.insert(S);
+  setIncludeLocation(S, ND.getLocation());
   return Symbols.find(S.ID);
 }
 
 void SymbolCollector::addDefinition(const NamedDecl &ND,
                                     const Symbol &DeclSym) {
   if (DeclSym.Definition)
     return;
   // If we saw some forward declaration, we end up copying the symbol.

clangd/unittests/SymbolCollectorTests.cpp

 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/VirtualFileSystem.h"
+#include "gmock/gmock-matchers.h"
 #include "gmock/gmock-more-matchers.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 #include <memory>
 #include <string>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using testing::_;
 using testing::AllOf;
 using testing::Contains;
+using testing::Each;
 using testing::ElementsAre;
 using testing::Field;
-using testing::IsEmpty;
 using testing::Not;
 using testing::Pair;
 using testing::UnorderedElementsAre;
 using testing::UnorderedElementsAreArray;
 
 // GMock helpers for matching Symbol.
 MATCHER_P(Labeled, Label, "") {
   return (arg.Name + arg.Signature).str() == Label;
TEST_F(SymbolCollectorTest, IncFileInNonHeader) {
   runSymbolCollector("", R"cpp(
     #include "test.inc"
   )cpp",
                      /*ExtraArgs=*/{"-I", testRoot()});
   EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(QName("X"), DeclURI(IncURI),
                                                   Not(IncludeHeader()))));
 }
 
+// Features that depend on header-guards are fragile. Header guards are only
+// recognized when the file ends, so we have to defer checking for them.
+TEST_F(SymbolCollectorTest, HeaderGuardDetected) {
+  CollectorOpts.CollectIncludePath = true;
+  CollectorOpts.CollectMacro = true;
+  runSymbolCollector(R"cpp(
+    #ifndef HEADER_GUARD_
+    #define HEADER_GUARD_
+
+    // Symbols are seen before the header guard is complete.
+    #define MACRO
+    int decl();
+
+    #endif // Header guard is recognized here.
+  )cpp",
+                     "");
+  EXPECT_THAT(Symbols, Not(Contains(QName("HEADER_GUARD_"))));
+  EXPECT_THAT(Symbols, Each(IncludeHeader()));
+}
+
 TEST_F(SymbolCollectorTest, NonModularHeader) {
   auto TU = TestTU::withHeaderCode("int x();");
   EXPECT_THAT(TU.headerSymbols(), ElementsAre(IncludeHeader()));
 
   // Files missing include guards aren't eligible for insertion.
   TU.ImplicitHeaderGuard = false;
   EXPECT_THAT(TU.headerSymbols(), ElementsAre(Not(IncludeHeader())));