[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

145

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.

154

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

161

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

250–265

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.

260

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 ↗

(On Diff #389131)

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

260

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

260

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 ↗

(On Diff #389183)

no need for static here (and other places below)

clang-tools-extra/clangd/SourceCode.h

332 ↗

(On Diff #389183)

i'd suggest AllowIO rather than ExpensiveCheck

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

283 ↗

(On Diff #389183)

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 ↗

(On Diff #389457)

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

clang-tools-extra/clangd/SourceCode.h

330 ↗

(On Diff #389457)

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 IncludeStructure &Includes,
                                            const SourceManager &SM);
 
 /// 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);
 

clang-tools-extra/clangd/IncludeCleaner.cpp

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 IncludeStructure &Includes, const SourceManager &SM) {
   std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
   llvm::sort(Sorted); // Group by FileID.
-  ReferencedFiles Result(SM);
+  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 &&
+         !Includes.isSelfContained(*Includes.getID(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.getIncludeStructure(),
+                                               AST.getSourceManager());
   auto ReferencedHeaders =
       translateToHeaderIDs(ReferencedFileIDs, AST.getIncludeStructure(), SM);
   return getUnused(AST, ReferencedHeaders);
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   const Config &Cfg = Config::current();

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), Includes, SM);
   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(
+    #ifndef FOO_H
+    #define FOO_H
+    namespace foo {
+    #include "unguarded.h"
+    }
+    #endif // FOO_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.getIncludeStructure(), AST.getSourceManager());
+  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.
+  EXPECT_THAT(ReferencedFileNames.keys(),
+              UnorderedElementsAre(testPath("bar.h"), testPath("foo.h")));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang