[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

147

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.

156

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

163

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

351

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

356

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–267

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

331

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

333

i'd suggest AllowIO rather than ExpensiveCheck

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

281–282

can you also delete this and the other helpers?

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

347

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

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

clang-tools-extra/clangd/Headers.h

65

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

128

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

158

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

330

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

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

[kbobyrev]

clang-tools-extra/clangd/Headers.h

167

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

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

I see, thanks!

clang-tools-extra/clangd/CodeComplete.cpp

bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
   // They don't fall nicely into our index/Sema dichotomy:
   //  - they're not indexed for completion (they're not available across files)
   //  - but Sema code complete won't see them: as part of the preamble, they're
   //    deserialized only when mentioned.
   // Force them to be deserialized so SemaCodeComplete sees them.
   loadMainFilePreambleMacros(Clang->getPreprocessor(), Input.Preamble);
   if (Includes)
     Clang->getPreprocessor().addPPCallbacks(
-        Includes->collect(Clang->getSourceManager()));
+        Includes->collect(Clang->getSourceManager(),
+                          Clang->getPreprocessor().getHeaderSearchInfo()));
   if (llvm::Error Err = Action.Execute()) {
     log("Execute() failed when running codeComplete for {0}: {1}",
         Input.FileName, toString(std::move(Err)));
     return false;
   }
   Action.EndSourceFile();
 
   return true;

clang-tools-extra/clangd/Headers.h

 #include "support/Path.h"
 #include "clang/Basic/FileEntry.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Format/Format.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem/UniqueID.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include <string>
 
 namespace clang {

 // An #include directive that we found in the main file.
 struct Inclusion {
   tok::PPKeywordKind Directive; // Directive used for inclusion, e.g. import
   std::string Written;          // Inclusion name as written e.g. <vector>.
   Path Resolved; // Resolved path of included file. Empty if not resolved.
   unsigned HashOffset = 0; // Byte offset from start of file to #.
   int HashLine = 0;        // Line number containing the directive, 0-indexed.
   SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User;
+  bool SelfContained = true;
   llvm::Optional<unsigned> HeaderID;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &);
 bool operator==(const Inclusion &LHS, const Inclusion &RHS);
 
 // Contains information about one file in the build graph and its direct
 // dependencies. Doesn't own the strings it references (IncludeGraph is
 // self-contained).

 public:
   IncludeStructure() {
     // Reserve HeaderID = 0 for the main file.
     RealPathNames.emplace_back();
   }
 
   // Returns a PPCallback that visits all inclusions in the main file and
   // populates the structure.
-  std::unique_ptr<PPCallbacks> collect(const SourceManager &SM);
+  std::unique_ptr<PPCallbacks> collect(const SourceManager &SM,
+                                       HeaderSearch &HeaderInfo);
 
   // HeaderID identifies file in the include graph. It corresponds to a
   // FileEntry rather than a FileID, but stays stable across preamble & main
   // file builds.
   enum class HeaderID : unsigned {};
 
   llvm::Optional<HeaderID> getID(const FileEntry *Entry) const;
   HeaderID getOrCreateID(const FileEntry *Entry);
public:
   // Root --> 0, #included file --> 1, etc.
   // Root is the ID of the header being visited first.
   llvm::DenseMap<HeaderID, unsigned>
   includeDepth(HeaderID Root = MainFileID) const;
 
   // Maps HeaderID to the ids of the files included from it.
   llvm::DenseMap<HeaderID, SmallVector<HeaderID>> IncludeChildren;
 
+  // Contains HeaderIDs of all self-contained entries in the IncludeStructure.
+  llvm::DenseSet<HeaderID> SelfContained;
+
   std::vector<Inclusion> MainFileIncludes;
 
   // We reserve HeaderID(0) for the main file and will manually check for that
   // in getID and getOrCreateID because the UniqueID is not stable when the
   // content of the main file changes.
   static const HeaderID MainFileID = HeaderID(0u);
 
 private:
   // MainFileEntry will be used to check if the queried file is the main file
   // or not.
   const FileEntry *MainFileEntry = nullptr;
 
   std::vector<std::string> RealPathNames; // In HeaderID order.
   // FileEntry::UniqueID is mapped to the internal representation (HeaderID).
   // Identifying files in a way that persists from preamble build to subsequent
   // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),

clang-tools-extra/clangd/Headers.cpp

 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 class RecordHeaders : public PPCallbacks {
 public:
-  RecordHeaders(const SourceManager &SM, IncludeStructure *Out)
-      : SM(SM), Out(Out) {}
+  RecordHeaders(const SourceManager &SM, HeaderSearch &HeaderInfo,
+                IncludeStructure *Out)
+      : SM(SM), HeaderInfo(HeaderInfo), Out(Out) {}
 
   // Record existing #includes - both written and resolved paths. Only #includes
   // in the main file are collected.
   void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
                           llvm::StringRef FileName, bool IsAngled,
                           CharSourceRange /*FilenameRange*/,
                           const FileEntry *File, llvm::StringRef /*SearchPath*/,
                           llvm::StringRef /*RelativePath*/,
void FileChanged(SourceLocation Loc, FileChangeReason Reason,
                    FileID PrevFID) override {
     switch (Reason) {
     case PPCallbacks::EnterFile:
       if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
         BuiltinFile = SM.getFileID(Loc);
         InBuiltinFile = true;
       }
       break;
-    case PPCallbacks::ExitFile:
+    case PPCallbacks::ExitFile: {
       if (PrevFID == BuiltinFile)
         InBuiltinFile = false;
+      // At the file exit time HeaderSearchInfo is valid and can be used to
+      // determine whether the file was a self-contained header or not.
+      if (const FileEntry *FE = SM.getFileEntryForID(PrevFID))
+        if (isSelfContainedHeader(FE, PrevFID, SM, HeaderInfo))
+          Out->SelfContained.insert(*Out->getID(SM.getFileEntryForID(PrevFID)));
       break;
+    }
     case PPCallbacks::RenameFile:
     case PPCallbacks::SystemHeaderPragma:
       break;
     }
   }
 
 private:
   const SourceManager &SM;
+  HeaderSearch &HeaderInfo;
   // Set after entering the <built-in> file.
   FileID BuiltinFile;
   // Indicates whether <built-in> file is part of include stack.
   bool InBuiltinFile = false;
 
   IncludeStructure *Out;
 };
 
llvm::SmallVector<llvm::StringRef, 1> getRankedIncludes(const Symbol &Sym) {
   });
   llvm::SmallVector<llvm::StringRef, 1> Headers;
   for (const auto &Include : Includes)
     Headers.push_back(Include.IncludeHeader);
   return Headers;
 }
 
 std::unique_ptr<PPCallbacks>
-IncludeStructure::collect(const SourceManager &SM) {
+IncludeStructure::collect(const SourceManager &SM, HeaderSearch &HeaderInfo) {
   MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
-  return std::make_unique<RecordHeaders>(SM, this);
+  return std::make_unique<RecordHeaders>(SM, HeaderInfo, this);
 }
 
 llvm::Optional<IncludeStructure::HeaderID>
 IncludeStructure::getID(const FileEntry *Entry) const {
   // HeaderID of the main file is always 0;
   if (Entry == MainFileEntry) {
     return static_cast<IncludeStructure::HeaderID>(0u);
   }

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

 //===--- IncludeCleaner.cpp - Unused/Missing Headers Analysis ---*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "IncludeCleaner.h"
 #include "Config.h"
+#include "Headers.h"
 #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 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.SelfContained.contains(*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) {
   trace::Span Tracer("IncludeCleaner::issueUnusedIncludesDiagnostics");

clang-tools-extra/clangd/ParsedAST.cpp

if (Preamble) {
     // Replay the preamble includes so that clang-tidy checks can see them.
     ReplayPreamble::attach(Patch->preambleIncludes(), *Clang,
                            Patch->modifiedBounds());
   }
   // Important: collectIncludeStructure is registered *after* ReplayPreamble!
   // Otherwise we would collect the replayed includes again...
   // (We can't *just* use the replayed includes, they don't have Resolved path).
   Clang->getPreprocessor().addPPCallbacks(
-      Includes.collect(Clang->getSourceManager()));
+      Includes.collect(Clang->getSourceManager(),
+                       Clang->getPreprocessor().getHeaderSearchInfo()));
   // Copy over the macros in the preamble region of the main file, and combine
   // with non-preamble macros below.
   MainFileMacros Macros;
   if (Preamble)
     Macros = Preamble->Macros;
   Clang->getPreprocessor().addPPCallbacks(
       std::make_unique<CollectMainFileMacros>(Clang->getSourceManager(),
                                               Macros));

clang-tools-extra/clangd/Preamble.cpp

 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticLex.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
+#include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
IsMainFileIncludeGuarded =
         CI.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
             MainFE);
   }
 
   void BeforeExecute(CompilerInstance &CI) override {
     CanonIncludes.addSystemHeadersMapping(CI.getLangOpts());
     LangOpts = &CI.getLangOpts();
     SourceMgr = &CI.getSourceManager();
+    HeaderInfo = &CI.getPreprocessor().getHeaderSearchInfo();
   }
 
   std::unique_ptr<PPCallbacks> createPPCallbacks() override {
     assert(SourceMgr && LangOpts &&
            "SourceMgr and LangOpts must be set at this point");
 
     return std::make_unique<PPChainedCallbacks>(
-        Includes.collect(*SourceMgr),
+        Includes.collect(*SourceMgr, *HeaderInfo),
         std::make_unique<PPChainedCallbacks>(
             std::make_unique<CollectMainFileMacros>(*SourceMgr, Macros),
             collectPragmaMarksCallback(*SourceMgr, Marks)));
   }
 
   CommentHandler *getCommentHandler() override {
     IWYUHandler = collectIWYUHeaderMaps(&CanonIncludes);
     return IWYUHandler.get();
private:
   IncludeStructure Includes;
   CanonicalIncludes CanonIncludes;
   MainFileMacros Macros;
   std::vector<PragmaMark> Marks;
   bool IsMainFileIncludeGuarded = false;
   std::unique_ptr<CommentHandler> IWYUHandler = nullptr;
   const clang::LangOptions *LangOpts = nullptr;
   const SourceManager *SourceMgr = nullptr;
+  HeaderSearch *HeaderInfo = nullptr;
 };
 
 // Represents directives other than includes, where basic textual information is
 // enough.
 struct TextualPPDirective {
   unsigned DirectiveLine;
   // Full text that's representing the directive, including the `#`.
   std::string Text;
scanPreamble(llvm::StringRef Contents, const tooling::CompileCommand &Cmd) {
   // We are only interested in main file includes.
   Clang->getPreprocessorOpts().SingleFileParseMode = true;
   PreprocessOnlyAction Action;
   if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]))
     return error("failed BeginSourceFile");
   const auto &SM = Clang->getSourceManager();
   Preprocessor &PP = Clang->getPreprocessor();
   IncludeStructure Includes;
-  PP.addPPCallbacks(Includes.collect(SM));
+  PP.addPPCallbacks(Includes.collect(SM, PP.getHeaderSearchInfo()));
   ScannedPreamble SP;
   SP.Bounds = Bounds;
   PP.addPPCallbacks(
       std::make_unique<DirectiveCollector>(PP, SP.TextualDirectives));
   if (llvm::Error Err = Action.Execute())
     return std::move(Err);
   Action.EndSourceFile();
   SP.Includes = std::move(Includes.MainFileIncludes);

clang-tools-extra/clangd/SourceCode.h

 #include "Protocol.h"
 #include "support/Context.h"
 #include "support/ThreadsafeFS.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Format/Format.h"
+#include "clang/Lex/HeaderSearch.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/SHA1.h"
 #include <string>
 

 /// 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). This will read a portion of the
+/// file which might be discouraged in performance-sensitive context.
+bool isSelfContainedHeader(const FileEntry *FE, FileID ID,
+                           const SourceManager &SM, HeaderSearch &HeaderInfo);
+
 } // 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?
+// FIXME: This makes headers with #ifdef LINUX/WINDOWS/MACOS marked as non
+// self-contained and is probably not what we want.
+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?
+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.
+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 FileEntry *FE, FileID FID,
+                           const SourceManager &SM, HeaderSearch &HeaderInfo) {
+  // 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 (!HeaderInfo.isFileMultipleIncludeGuarded(FE) &&
+      !HeaderInfo.hasFileBeenImported(FE))
+    return false;
+  // This pattern indicates that a header can't be used without
+  // particular preprocessor state, usually set up by another header.
+  return !isDontIncludeMeHeader(SM.getBufferData(FID));
+}
+
 } // 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(FE, FID, PP->getSourceManager(),
+                               PP->getHeaderSearchInfo())) {
       // 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?
-  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;
-  }
 };
 
 // Return the symbol location of the token at \p TokLoc.
 llvm::Optional<SymbolLocation>
 SymbolCollector::getTokenLocation(SourceLocation TokLoc) {
   const auto &SM = ASTCtx->getSourceManager();
   auto *FE = SM.getFileEntryForID(SM.getFileID(TokLoc));
   if (!FE)
     return None;

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

protected:
 
   IncludeStructure collectIncludes() {
     Clang = setupClang();
     PreprocessOnlyAction Action;
     EXPECT_TRUE(
         Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]));
     IncludeStructure Includes;
     Clang->getPreprocessor().addPPCallbacks(
-        Includes.collect(Clang->getSourceManager()));
+        Includes.collect(Clang->getSourceManager(),
+                         Clang->getPreprocessor().getHeaderSearchInfo()));
     EXPECT_FALSE(Action.Execute());
     Action.EndSourceFile();
     return Includes;
   }
 
   // Calculates the include path, or returns "" on error or header should not be
   // inserted.
   std::string calculate(PathRef Original, PathRef Preferred = "",
#include <a.h>)cpp";
   EXPECT_THAT(collectIncludes().MainFileIncludes,
               Not(Contains(Written("<a.h>"))));
 
   // Now include through built-in file.
   CDB.ExtraClangFlags = {"-include", testPath(HeaderFile)};
   EXPECT_THAT(collectIncludes().MainFileIncludes,
               Contains(AllOf(IncludeLine(2), Written("<a.h>"))));
 }
+
+TEST_F(HeadersTest, SelfContainedHeaders) {
+  // Including through non-builtin file has no effects.
+  FS.Files[MainFile] = R"cpp(
+#include "includeguarded.h"
+#include "nonguarded.h"
+#include "pp_depend.h"
+#include "pragmaguarded.h"
+)cpp";
+  FS.Files["pragmaguarded.h"] = R"cpp(
+#pragma once
+)cpp";
+  FS.Files["includeguarded.h"] = R"cpp(
+#ifndef INCLUDE_GUARDED_H
+#define INCLUDE_GUARDED_H
+void foo();
+#endif // INCLUDE_GUARDED_H
+)cpp";
+  FS.Files["nonguarded.h"] = R"cpp(
+)cpp";
+  FS.Files["pp_depend.h"] = R"cpp(
+  #ifndef REQUIRED_PP_DIRECTIVE
+  # error You have to have PP directive set to include this one!
+  #endif
+)cpp";
+
+  auto Includes = collectIncludes();
+  EXPECT_THAT(Includes.SelfContained,
+              UnorderedElementsAre(getID("pragmaguarded.h", Includes),
+                                   getID("includeguarded.h", Includes)));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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.getIncludeStructure(), AST.getSourceManager());
   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

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

auto Clang =
                               PI.TFS->view(PI.CompileCommand.Directory), Diags);
   PreprocessOnlyAction Action;
   if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])) {
     ADD_FAILURE() << "failed begin source file";
     return {};
   }
   IncludeStructure Includes;
   Clang->getPreprocessor().addPPCallbacks(
-      Includes.collect(Clang->getSourceManager()));
+      Includes.collect(Clang->getSourceManager(),
+                       Clang->getPreprocessor().getHeaderSearchInfo()));
   if (llvm::Error Err = Action.Execute()) {
     ADD_FAILURE() << "failed to execute action: " << std::move(Err);
     return {};
   }
   Action.EndSourceFile();
   return Includes;
 }