[clangd] Record information about non self-contained headers in IncludeStructure

[kbobyrev]

Summary

This will be useful for IncludeCleaner.

[kadircet]

thanks, LG in general, just a couple polishing touches

clang-tools-extra/clangd/IncludeCleaner.cpp

146

this returns true even after inserting mainfile id, is that intended? I suppose it won't hurt too much, but means we'll go one step further for macros.

155

can you lift the isSelfContainedHeader into SourceCode.h and make use of it in both places (while updating the signature to accept a PP, through which you can access the SM).

162

we already have access to SM from the members, can you do the same for PP (stash as a member during construction) rather than plumbing at each call?

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

350

is this part of the check even relevant? let's drop this completely?

355

maybe make this an UnorderedElementsAre, do we have any ordering guarantees in this API's contract?

[sammccall]

The ReferencedFiles is designed to make add() as cheap as possible, and do any per-file logic after folding the fileIDs together.
This keeps that loop tighter and also isolates the complexity of the symbol vs file logic.
Any reason we can't do that here?

[kbobyrev]

Address review comments.

[kbobyrev]

In D114370#3148143, @sammccall wrote:

The ReferencedFiles is designed to make add() as cheap as possible, and do any per-file logic after folding the fileIDs together.
This keeps that loop tighter and also isolates the complexity of the symbol vs file logic.
Any reason we can't do that here?

Good point, thanks!

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

252–268

This comment seems a bit unclear:

• what the problem is you're solving
• whether you're describing the behavior you *want* rather than the behavior you're trying to avoid.
• which part of this is "filtering"
• what the "later" option is you're contrasting to

Maybe something like:

// If a header is not self-contained, we consider its symbols a logical part of the including file.
// Therefore, mark the parents of all used non-self-contained FileIDs as used.
// Perform this on FileIDs rather than HeaderIDs, as each inclusion of a non-self-contained file is distinct.

262

it seems like we'd be better off storing the "is-self-contained" in the IncludeStructure and looking up the HeaderID here rather than asking the preprocessor. That way we rely on info that's better obtained at preamble build time.

clang-tools-extra/clangd/SourceCode.h

330

This helper checks e.g. for "don't include me", which is going to read source code of preamble files - we shouldn't do that, it's too slow and racy to do for every file in the preamble.

(It would be nice to handle those cases at some point, if we want to do that we need to do it at preamble build time and record the results in the IncludeStructure)

[kbobyrev]

Resolve most comments.

clang-tools-extra/clangd/IncludeCleaner.cpp

262

I am slightly confused: we don't really have the IncludeStructure here and it is logically detached from the IncludeStructure processing. We'd still have to unroll the chain of FIDs in here, so the only difference would be querying IncludeStructure data for the cached isSelfContainedHeader value, is that right? Why is obtaining that info at preamble build time better?

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.cpp

262

the call-site has access to ParsedAST, hence the IncludeStructure. I believe the main reasoning behind Sam's suggestion is performing these lookups once while building the preamble and sharing it afterwards (we can even do the IO there).

clang-tools-extra/clangd/SourceCode.cpp

56

no need for static here (and other places below)

clang-tools-extra/clangd/SourceCode.h

332

i'd suggest AllowIO rather than ExpensiveCheck

clang-tools-extra/clangd/index/SymbolCollector.cpp

283

can you also delete this and the other helpers?

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

346

looks like a debug artifact

[kbobyrev]

Resolve review comments. This turned into a rather large refactoring change.

[kbobyrev]

Untangle BeforeExecute call ordering change.

[sammccall]

Thanks, this mostly LG now.
I'd consider splitting out the new infra change (IncludeStructure) from the feature change (include-cleaner treatment).
In case the latter causes some problems...

clang-tools-extra/clangd/Headers.cpp

92 ↗

(On Diff #389457)

nit: at the file exit time -> at file exit time

clang-tools-extra/clangd/Headers.h

65 ↗

(On Diff #389457)

Why redundantly track this on Inclusion? It's already available via IncludeStructure.SelfContained.contains(*HeaderID)

128 ↗

(On Diff #389457)

Maybe it's neater just to pass the CompilerInstance& - there's no other practical way to use this.

158 ↗

(On Diff #389457)

I think i'd prefer to see this private with an isSelfContained accessor, because the representation isn't the only sensible one.

Case in point: almost all headers in practice are self-contained, so in fact storing the set of non-self-contained headers seems preferable.

clang-tools-extra/clangd/SourceCode.cpp

53

these helpers are 1000 lines away from the only place they're used, please move them closer

clang-tools-extra/clangd/SourceCode.h

329

This still doesn't really describe the situation:

• if you're not getting the header from a preamble, it won't have to read anything as it'll be in-memory already
• if you are, then the fact that the content may have changed is at least as big a problem
• the string scanning itself is not ideal to do redundantly from a performance POV

I'd rather say:
"This scans source code, and should not be called when using a preamble.
Prefer to access the cache in IncludeStructure::isSelfContained if you can."

[kbobyrev]

Address review comments. Next step: split this patch into two, as suggested.

[kbobyrev]

Leave the feature changes (IncludeCleaner bits) out of this patch

[kbobyrev]

[clangd] IncludeCleaner: Attribute symbols from non self-contained headers to their parents

When a symbol comes from the non self-contained header, we recursively uplift
the file we consider used to the first includer that has a header guard. We
need to do this while we still have FileIDs because every time a non
self-contained header is included, it gets a new FileID but is later
deduplicated by HeaderID and it's not possible to understand where it was
included from.

[kbobyrev]

Change base to D114370.

[kbobyrev]

Get the changes back to this patch.

[sammccall]

Thanks!

clang-tools-extra/clangd/Headers.h

167 ↗

(On Diff #389953)

could consider friend class RecordHeaders, either is ugly, up to you

[kbobyrev]

clang-tools-extra/clangd/Headers.h

167 ↗

(On Diff #389953)

That was the original problem I had the public field in the previous iteration: RecordHeaders is defined in anonymous namespace, so IIUC I can not friend it from here unless I make it a subclass or somehow visible from here, otherwise it wouldn't work, would it? Is there any clean way to do the friend here?

[sammccall]

clang-tools-extra/clangd/Headers.h

167 ↗

(On Diff #389953)

No, you need to move it out of the anonymous namespace. Which is part of the ugliness, though not harmful in practice.

(If you're worried about namespace pollution you can make it a nested class of IncludeStructure. You have to forward declare it in the header. In that case you don't have to friend it)

[kbobyrev]

Get rid of the setter in IncludeStructure.

clang-tools-extra/clangd/Headers.h

167 ↗

(On Diff #389953)

I see, thanks!

clang-tools-extra/clangd/IncludeCleaner.h

 ///   ambiguous cases (e.g. implicitly used symbols, multiple declarations)
 /// - err on the side of reporting all possible locations
 ReferencedLocations findReferencedLocations(ParsedAST &AST);
 
 /// Retrieves IDs of all files containing SourceLocations from \p Locs.
 /// The output only includes things SourceManager sees as files (not macro IDs).
 /// This can include <built-in>, <scratch space> etc that are not true files.
 llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
-                                           const SourceManager &SM);
+                                           const Preprocessor &PP);
 
 /// Maps FileIDs to the internal IncludeStructure representation (HeaderIDs).
 /// FileIDs that are not true files (<built-in> etc) are dropped.
 llvm::DenseSet<IncludeStructure::HeaderID>
 translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
                      const IncludeStructure &Includes, const SourceManager &SM);
 
 /// Retrieves headers that are referenced from the main file but not used.

clang-tools-extra/clangd/IncludeCleaner.cpp

 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
struct ReferencedFiles {
   llvm::DenseSet<FileID> Macros;
   const SourceManager &SM;
 
   void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
 
   void add(FileID FID, SourceLocation Loc) {
     if (FID.isInvalid())
       return;
     assert(SM.isInFileID(Loc, FID));
     if (Loc.isFileID()) {
       Files.insert(FID);
       return;
     }
     // Don't process the same macro FID twice.
     if (!Macros.insert(FID).second)
       return;
     const auto &Exp = SM.getSLocEntry(FID).getExpansion();
     add(Exp.getSpellingLoc());
     add(Exp.getExpansionLocStart());
     add(Exp.getExpansionLocEnd());
   }
 };
 
 // Returns the range starting at '#' and ending at EOL. Escaped newlines are not
 // handled.
 clangd::Range getDiagnosticRange(llvm::StringRef Code, unsigned HashOffset) {
   clangd::Range Result;
   Result.end = Result.start = offsetToPosition(Code, HashOffset);
 
   // Span the warning until the EOL or EOF.
   Result.end.character +=
       lspLength(Code.drop_front(HashOffset).take_until([](char C) {
         return C == '\n' || C == '\r';
ReferencedLocations findReferencedLocations(ParsedAST &AST) {
   ReferencedLocationCrawler Crawler(Result);
   Crawler.TraverseAST(AST.getASTContext());
   findReferencedMacros(AST, Result);
   return Result;
 }
 
 llvm::DenseSet<FileID>
 findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
-                    const SourceManager &SM) {
+                    const Preprocessor &PP) {
   std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
   llvm::sort(Sorted); // Group by FileID.
-  ReferencedFiles Result(SM);
+  const SourceManager &SM = PP.getSourceManager();
+  ReferencedFiles Files(SM);
   for (auto It = Sorted.begin(); It < Sorted.end();) {
     FileID FID = SM.getFileID(*It);
-    Result.add(FID, *It);
+    Files.add(FID, *It);
     // Cheaply skip over all the other locations from the same FileID.
     // This avoids lots of redundant Loc->File lookups for the same file.
     do
       ++It;
     while (It != Sorted.end() && SM.isInFileID(*It, FID));
   }
-  return std::move(Result.Files);
+  // If a header is not self-contained, we consider its symbols a logical part
+  // of the including file. Therefore, mark the parents of all used
+  // non-self-contained FileIDs as used. Perform this on FileIDs rather than
+  // HeaderIDs, as each inclusion of a non-self-contained file is distinct.
+  llvm::DenseSet<FileID> Result;
+  for (FileID ID : Files.Files) {
+    // Unroll the chain of non self-contained headers to get to the first one
+    // with the header guard.
+    for (const FileEntry *FE = SM.getFileEntryForID(ID);
+         ID != SM.getMainFileID() && FE &&
+         !isSelfContainedHeader(PP, ID, FE);) {
+      ID = SM.getFileID(SM.getIncludeLoc(ID));
+      FE = SM.getFileEntryForID(ID);
+    }
+    Result.insert(ID);
+  }
+  return Result;
 }
 
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
   trace::Span Tracer("IncludeCleaner::getUnused");
   std::vector<const Inclusion *> Unused;
   for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
   }
   return TranslatedHeaderIDs;
 }
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
   const auto &SM = AST.getSourceManager();
 
   auto Refs = findReferencedLocations(AST);
-  // FIXME(kirillbobyrev): Attribute the symbols from non self-contained
-  // headers to their parents while the information about respective
-  // SourceLocations and FileIDs is not lost. It is not possible to do that
-  // later when non-guarded headers included multiple times will get same
-  // HeaderID.
-  auto ReferencedFileIDs = findReferencedFiles(Refs, SM);
+  auto ReferencedFileIDs = findReferencedFiles(Refs, AST.getPreprocessor());
   auto ReferencedHeaders =
       translateToHeaderIDs(ReferencedFileIDs, AST.getIncludeStructure(), SM);
   return getUnused(AST, ReferencedHeaders);
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   trace::Span Tracer("IncludeCleaner::issueUnusedIncludesDiagnostics");

clang-tools-extra/clangd/SourceCode.h

 /// Infers whether this is a header from the FileName and LangOpts (if
 /// presents).
 bool isHeaderFile(llvm::StringRef FileName,
                   llvm::Optional<LangOptions> LangOpts = llvm::None);
 
 /// Returns true if the given location is in a generated protobuf file.
 bool isProtoFile(SourceLocation Loc, const SourceManager &SourceMgr);
 
+/// Use heuristics to check whether the header is self-contained (has header
+/// guard, does not rely on preprocessor state).
+/// When \p ExpensiveCheck is true, this will read a portion of the file which
+/// be discouraged in performance-sensitive context.
+bool isSelfContainedHeader(const Preprocessor &PP, FileID FID,
+                           const FileEntry *FE, bool ExpensiveCheck = false);
+
 } // namespace clangd
 } // namespace clang
 #endif

clang-tools-extra/clangd/SourceCode.cpp

 #include <algorithm>
 #include <cstddef>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
+namespace {
+
+// Is Line an #if or #ifdef directive?
+static bool isIf(llvm::StringRef Line) {
+  Line = Line.ltrim();
+  if (!Line.consume_front("#"))
+    return false;
+  Line = Line.ltrim();
+  return Line.startswith("if");
+}
+
+// Is Line an #error directive mentioning includes?
+static bool isErrorAboutInclude(llvm::StringRef Line) {
+  Line = Line.ltrim();
+  if (!Line.consume_front("#"))
+    return false;
+  Line = Line.ltrim();
+  if (!Line.startswith("error"))
+    return false;
+  return Line.contains_insensitive(
+      "includ"); // Matches "include" or "including".
+}
+
+// Heuristically headers that only want to be included via an umbrella.
+static bool isDontIncludeMeHeader(llvm::StringRef Content) {
+  llvm::StringRef Line;
+  // Only sniff up to 100 lines or 10KB.
+  Content = Content.take_front(100 * 100);
+  for (unsigned I = 0; I < 100 && !Content.empty(); ++I) {
+    std::tie(Line, Content) = Content.split('\n');
+    if (isIf(Line) && isErrorAboutInclude(Content.split('\n').first))
+      return true;
+  }
+  return false;
+}
+
+} // namespace
+
 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
 
 // Iterates over unicode codepoints in the (UTF-8) string. For each,
 // invokes CB(UTF-8 length, UTF-16 length), and breaks if it returns true.
 // Returns true if CB returned true, false if we hit the end of string.
 //
 // If the string is not valid UTF-8, we log this error and "decode" the
bool isProtoFile(SourceLocation Loc, const SourceManager &SM) {
   auto FID = SM.getFileID(Loc);
   // All proto generated headers should start with this line.
   static const char *PROTO_HEADER_COMMENT =
       "// Generated by the protocol buffer compiler.  DO NOT EDIT!";
   // Double check that this is an actual protobuf header.
   return SM.getBufferData(FID).startswith(PROTO_HEADER_COMMENT);
 }
 
+bool isSelfContainedHeader(const Preprocessor &PP, FileID FID,
+                           const FileEntry *FE, bool ExpensiveCheck) {
+  // FIXME: Should files that have been #import'd be considered
+  // self-contained? That's really a property of the includer,
+  // not of the file.
+  if (!PP.getHeaderSearchInfo().isFileMultipleIncludeGuarded(FE) &&
+      !PP.getHeaderSearchInfo().hasFileBeenImported(FE))
+    return false;
+  // This pattern indicates that a header can't be used without
+  // particular preprocessor state, usually set up by another header.
+  if (ExpensiveCheck)
+    return !isDontIncludeMeHeader(PP.getSourceManager().getBufferData(FID));
+  return true;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/SymbolCollector.cpp

if (Includes) {
       llvm::StringRef Canonical = Includes->mapHeader(Filename);
       if (!Canonical.empty()) {
         // If we had a mapping, always use it.
         if (Canonical.startswith("<") || Canonical.startswith("\""))
           return Canonical;
         return toURI(Canonical);
       }
     }
-    if (!isSelfContainedHeader(FID, FE)) {
+    if (!isSelfContainedHeader(*PP, FID, FE, /*ExpensiveCheck=*/true)) {
       // A .inc or .def file is often included into a real header to define
       // symbols (e.g. LLVM tablegen files).
       if (Filename.endswith(".inc") || Filename.endswith(".def"))
         // Don't use cache reentrantly due to iterator invalidation.
         return getIncludeHeaderUncached(SM.getFileID(SM.getIncludeLoc(FID)));
       // Conservatively refuse to insert #includes to files without guards.
       return "";
     }
     // Standard case: just insert the file itself.
     return toURI(FE);
   }
 
-  bool isSelfContainedHeader(FileID FID, const FileEntry *FE) {
-    // FIXME: Should files that have been #import'd be considered
-    // self-contained? That's really a property of the includer,
-    // not of the file.
-    if (!PP->getHeaderSearchInfo().isFileMultipleIncludeGuarded(FE) &&
-        !PP->getHeaderSearchInfo().hasFileBeenImported(FE))
-      return false;
-    // This pattern indicates that a header can't be used without
-    // particular preprocessor state, usually set up by another header.
-    if (isDontIncludeMeHeader(SM.getBufferData(FID)))
-      return false;
-    return true;
-  }
-
   // Is Line an #if or #ifdef directive?
   static bool isIf(llvm::StringRef Line) {
     Line = Line.ltrim();
     if (!Line.consume_front("#"))
       return false;
     Line = Line.ltrim();
     return Line.startswith("if");
   }
 
   // Is Line an #error directive mentioning includes?

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

TU.AdditionalFiles["macros.h"] = R"cpp(
 
     #endif // MACROS_H
     )cpp";
   TU.ExtraArgs = {"-DCLI=42"};
   ParsedAST AST = TU.build();
   auto &SM = AST.getSourceManager();
   auto &Includes = AST.getIncludeStructure();
 
-  auto ReferencedFiles = findReferencedFiles(findReferencedLocations(AST), SM);
+  auto ReferencedFiles =
+      findReferencedFiles(findReferencedLocations(AST), AST.getPreprocessor());
   llvm::StringSet<> ReferencedFileNames;
   for (FileID FID : ReferencedFiles)
     ReferencedFileNames.insert(
         SM.getPresumedLoc(SM.getLocForStartOfFile(FID)).getFilename());
   // Note we deduped the names as _number_ of <built-in>s is uninteresting.
   EXPECT_THAT(ReferencedFileNames.keys(),
               UnorderedElementsAre("<built-in>", "<scratch space>",
                                    testPath("macros.h")));
 
   // Should not crash due to FileIDs that are not headers.
   auto ReferencedHeaders = translateToHeaderIDs(ReferencedFiles, Includes, SM);
   std::vector<llvm::StringRef> ReferencedHeaderNames;
   for (IncludeStructure::HeaderID HID : ReferencedHeaders)
     ReferencedHeaderNames.push_back(Includes.getRealPath(HID));
   // Non-header files are gone at this point.
   EXPECT_THAT(ReferencedHeaderNames, ElementsAre(testPath("macros.h")));
 
   // Sanity check.
   EXPECT_THAT(getUnused(AST, ReferencedHeaders), ::testing::IsEmpty());
 }
 
+TEST(IncludeCleaner, NonSelfContainedHeaders) {
+  TestTU TU;
+  TU.Code = R"cpp(
+    #include "bar.h"
+    #include "foo.h"
+
+    int LocalFoo = foo::Variable,
+        LocalBar = bar::Variable;
+    )cpp";
+  TU.AdditionalFiles["bar.h"] = R"cpp(
+    #pragma once
+    namespace bar {
+    #include "indirection.h"
+    }
+    )cpp";
+  TU.AdditionalFiles["foo.h"] = R"cpp(
+    #pragma once
+    namespace foo {
+    #include "unguarded.h"
+    }
+    )cpp";
+  TU.AdditionalFiles["indirection.h"] = R"cpp(
+    #include "unguarded.h"
+    )cpp";
+  TU.AdditionalFiles["unguarded.h"] = R"cpp(
+    constexpr int Variable = 42;
+    )cpp";
+
+  ParsedAST AST = TU.build();
+
+  auto ReferencedFiles =
+      findReferencedFiles(findReferencedLocations(AST), AST.getPreprocessor());
+  llvm::StringSet<> ReferencedFileNames;
+  auto &SM = AST.getSourceManager();
+  for (FileID FID : ReferencedFiles)
+    ReferencedFileNames.insert(
+        SM.getPresumedLoc(SM.getLocForStartOfFile(FID)).getFilename());
+  // Note that we have uplifted the referenced files from non self-contained
+  // headers to header-guarded ones.
+  for (const auto &Key : ReferencedFileNames.keys()) {
+    llvm::outs() << "Key: " << Key << '\n';
+  }
+  EXPECT_THAT(ReferencedFileNames.keys(),
+              UnorderedElementsAre(testPath("bar.h"), testPath("foo.h")));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang