[clangd] Populate include graph during static indexing action.

[kadircet]

Summary

This is the second part for introducing include hierarchy into index
files produced by clangd. You can see the base patch that introduces structures
and discusses the future of the patches in D54817

[ilya-biryukov]

clangd/index/IndexAction.cpp

23 ↗

(On Diff #175664)

Could we add an assertion that the final graph does not contain uninitialized nodes?

28 ↗

(On Diff #175664)

Maybe expand a bit on what a node is? I.e. mention file digests, URIs, etc.

33 ↗

(On Diff #175664)

s/enteries/entries

44 ↗

(On Diff #175664)

Is there a way to check the node has already been populated? Can we do this and avoid recomputing the hashes for the same file/assert they're the same in assertion mode?
E.g. by looking at URI.empty()?

45 ↗

(On Diff #175664)

What happens if we can't compute a digest for a file? Are we left with an uninitialized memory?

63 ↗

(On Diff #175664)

Maybe convert both URIs before adding anything to IG?
To make sure we don't change IG unless both URIs can be parsed

72 ↗

(On Diff #175664)

Maybe move the if block into the function body? To make sure we're be producing compiler errors on changes to the base function signature regardless of the compile configuration

109 ↗

(On Diff #175664)

NIT: maybe remove != nullptr? the callback is a function, not a pointer, so nullptr might be a bit confusing

133 ↗

(On Diff #175664)

NIT: maybe remove != nullptr?

unittests/clangd/IndexActionTests.cpp

79 ↗

(On Diff #175664)

Why 3 headers on each level? 1 or 2, would probably read a but simpler.

104 ↗

(On Diff #175664)

Directly looking at the graph to capture the include structure might be more straightforward, e.g.

EXPECT_THAT(graph, 
 UnorderedElementsAre(Pair(Main, IncludersAre("level1", ....)))

This won't work on StringMap, but converting to std::map<string, node> should be simple. Other invariants can be tested separately (e.g. values of IsTU)
Maybe try that?

126 ↗

(On Diff #175664)

Could we also test a few corner cases?

• Self-includes (with and without include guards).
• Skipped files (multiple includes of the same file with #pragma once or include guards)

[kadircet]

• Address comments.

clangd/index/IndexAction.cpp

45 ↗

(On Diff #175664)

Yes, we'll be left with some random digest in the node.

But I believe it is as good as any sentinel value, this field is used for consistency checks. Absence of digest implies we will always(well almost always) have an inconsistent(~stale) version of the file in the current structure and will re-trigger indexing action next time.

Therefore, having this digest initialized to some sentinel or random gibberish has the same probability of colliding with the actual hash. So I believe it is OK to leave it like that.

109 ↗

(On Diff #175664)

yeah but this was the convention in the file, is it ok if I change the other usages as well?

unittests/clangd/IndexActionTests.cpp

126 ↗

(On Diff #175664)

I've added a self-include test with header guards, I don't think it is possible to do that without a guard. Wouldn't it cause an infinite loop? I end up getting abort with:
/clangd-test/header.h:1:10: error: #include nested too deeply
Did you mean something else?

[ilya-biryukov]

clangd/index/IndexAction.cpp

45 ↗

(On Diff #175664)

Reading those values is undefined behavior, which is not the same as reading a random digest.
But anyway, the best way to avoid UB is to make the default constructor initialize it to some value, which can be done independently of this patch.

109 ↗

(On Diff #175664)

Keeping it for consistency LG. Not sure changing the whole file is worth the trouble

unittests/clangd/IndexActionTests.cpp

126 ↗

(On Diff #175664)

Yeah, we'll need some cut-off, in might be in a form that's different from the include guard to test this.
The idea was to test a different behavior in the compiler, I believe it will optimize away include-guarded files and call FileSkipped, while it would actually visit the same file twice when it cannot detect an include guard. Something like this should trigger this behavior:

#ifndef FOO
#define FOO "main.cpp"
#else
#define FOO "header.h"
#endif

#include FOO

Granted, the test-case is obscure, but there's so much C++ code out there, that someone will eventually run clangd on the code doing something like this.

To be clear, I don't think testing anything other than clangd does not crash on this is useful, not saying we should think too much about those cases :-)

[ilya-biryukov]

clangd/index/IndexAction.cpp

12 ↗

(On Diff #175684)

NIT: maybe call it toURI?

23 ↗

(On Diff #175684)

I think this comment would also be useful on the IncludeGraph definition itself, most of the readers won't see the code building the graph

34 ↗

(On Diff #175684)

NIT: maybe add a note mentioning why we have to do this separately from InclusionDirective?

152 ↗

(On Diff #175684)

NIT: maybe add a comment that we are checking for the absence of the uninitialized values here?

unittests/clangd/IndexActionTests.cpp

28 ↗

(On Diff #175684)

Maybe inline this? This looks simple enough.

32 ↗

(On Diff #175684)

Why not simply return arg.IsTU?

38 ↗

(On Diff #175684)

Why not return arg.Digest == Digest?

88 ↗

(On Diff #175684)

Maybe return all outputs in runIndexingAction in a dedicated struct?
To make the inputs for the tests more explicit.

Unless this has also been copied from some other test, in which case you could argue it's consistent with how we did things before.

124 ↗

(On Diff #175684)

NIT: Maybe use StringRef? i.e. for (StringRef Path : ...)

149 ↗

(On Diff #175684)

Maybe directly store map<string, IncludeGraphNode> to avoid the flattenning code in every test?

162 ↗

(On Diff #175684)

Maybe move to the common code? Repeating these in every test does not seem ideal, it's a common invariant.

[kadircet]

• Address comments.

[kadircet]

unittests/clangd/IndexActionTests.cpp

28 ↗

(On Diff #175684)

yeah but repeating all of that over and over again looks really ugly.

[ilya-biryukov]

clangd/index/IndexAction.cpp

31 ↗

(On Diff #175831)

No need to duplicate the comments here, one can always look at the struct definition.
Mentioning it populates everything except the include structure should be enough.

36 ↗

(On Diff #175831)

No need to mention IO, something like the following should convey the same message: we cannot populate the fields in InclusionDirective because it does not have access to the contents of the target file

unittests/clangd/IndexActionTests.cpp

52 ↗

(On Diff #175831)

NIT: add a comment that uninitialized nodes will have an empty URI?

109 ↗

(On Diff #175831)

Do we ever use anything but the include graph?
Maybe create a helper function that return vector<pair<string, IncludeGraphNode>> (or even map<string, IncludeGraphNode>) to avoid repeating the conversion code in every test?

128 ↗

(On Diff #175831)

Could we move these checks into the body of runIndexingAction to avoid repeating them in every test?

28 ↗

(On Diff #175684)

Maybe call it toUri to make it even shorther then?
Or at least pathToURI to follow the naming conventions.

[kadircet]

• Address comments

[ilya-biryukov]

clangd/Headers.h

64 ↗

(On Diff #175878)

And multi-edges too, right? Even though they're not useful.

unittests/clangd/IndexActionTests.cpp

168 ↗

(On Diff #175878)

Maybe have two variables instead? Would format better and HeaderPath is arguably more readable than Header.first

211 ↗

(On Diff #175878)

Is there a way to make this format nicer?

225 ↗

(On Diff #175878)

Why not auto Nodes = toMap(*runIndexingAction(MainFilePath).Sources)?
Optional has an assertion, so we'll catch empty results anyway, no need to make the test more verbose

[kadircet]

• Address comments.

[kadircet]

unittests/clangd/IndexActionTests.cpp

168 ↗

(On Diff #175878)

Is it that important?

225 ↗

(On Diff #175878)

because toMap doesn't modify the contents of the nodes(to make sure we don't change behaviour during the process), and all the strings are still referring to the keys of the graph. Therefore the graph needs to be kept alive.

[ilya-biryukov]

unittests/clangd/IndexActionTests.cpp

168 ↗

(On Diff #175878)

I think it is of minor importance.

Creating a pair that is deconstructed at every use site anyway hurts readability.
If the purpose is grouping the variables together, putting them close to each other and giving them similar names solves the same purpose.

I would also expect the raw strings to format better and not have a very long indent if we put them into separate variables.

225 ↗

(On Diff #175878)

I missed this. It makes sense, thanks for clarifying. It's ok to have the boilerplate then.
Would still remove ASSERT_TRUE(IndexFile.Sources), asserts in optional will catch those anyway. But up to you.

[kadircet]

• Address comments.

[ilya-biryukov]

Thank, LGTM. A few NITs.

clangd/index/IndexAction.h

31 ↗

(On Diff #176065)

We have only two call sites, maybe leave out the default arg and specify null explicitly where needed?

unittests/clangd/IndexActionTests.cpp

52 ↗

(On Diff #176065)

Maybe also check the size of IndexFile.Sources is the same as Paths? To make sure we didn't miss any

[kadircet]

• Address comments

clang-tools-extra/trunk/clangd/Headers.h

 // An #include directive that we found in the main file.
 struct Inclusion {
   Range R;             // Inclusion range.
   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 #.
   SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User;
 };
-llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion&);
+llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &);
 
 // Contains information about one file in the build grpah and its direct
 // dependencies. Doesn't own the strings it references (IncludeGraph is
 // self-contained).
 struct IncludeGraphNode {
   // True if current file is a main file rather than a header.
   bool IsTU;
   llvm::StringRef URI;
   FileDigest Digest;
   std::vector<llvm::StringRef> DirectIncludes;
 };
 // FileURI and FileInclusions are references to keys of the map containing
 // them.
+// Important: The graph generated by those callbacks might contain cycles, self
+// edges and multi edges.
 using IncludeGraph = llvm::StringMap<IncludeGraphNode>;
 
 // Information captured about the inclusion graph in a translation unit.
 // This includes detailed information about the direct #includes, and summary
 // information about all transitive includes.
 //
 // It should be built incrementally with collectIncludeStructureCallback().
 // When we build the preamble, we capture and store its include structure along

clang-tools-extra/trunk/clangd/index/Background.cpp

Error BackgroundIndex::index(tooling::CompileCommand Cmd,
 
   SymbolCollector::Options IndexOpts;
   StringMap<FileDigest> FilesToUpdate;
   IndexOpts.FileFilter = createFileFilter(DigestsSnapshot, FilesToUpdate);
   SymbolSlab Symbols;
   RefSlab Refs;
   auto Action = createStaticIndexingAction(
       IndexOpts, [&](SymbolSlab S) { Symbols = std::move(S); },
-      [&](RefSlab R) { Refs = std::move(R); });
+      [&](RefSlab R) { Refs = std::move(R); },
+      /*IncludeGraphCallback=*/nullptr);
 
   // We're going to run clang here, and it could potentially crash.
   // We could use CrashRecoveryContext to try to make indexing crashes nonfatal,
   // but the leaky "recovery" is pretty scary too in a long-running process.
   // If crashes are a real problem, maybe we should fork a child process.
 
   const FrontendInputFile &Input = Clang->getFrontendOpts().Inputs.front();
   if (!Action->BeginSourceFile(*Clang, Input))

clang-tools-extra/trunk/clangd/index/IndexAction.h

 //===--- IndexAction.h - Run the indexer as a frontend action ----*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_ACTION_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_ACTION_H
+#include "Headers.h"
 #include "SymbolCollector.h"
 #include "clang/Frontend/FrontendActions.h"
 
 namespace clang {
 namespace clangd {
 
 // Creates an action that indexes translation units and delivers the results
 // for SymbolsCallback (each slab corresponds to one TU).
 //
 // Only a subset of SymbolCollector::Options are respected:
 //   - include paths are always collected, and canonicalized appropriately
 //   - references are always counted
 //   - all references are collected (if RefsCallback is non-null)
 //   - the symbol origin is always Static
-std::unique_ptr<FrontendAction>
-createStaticIndexingAction(SymbolCollector::Options Opts,
-                           std::function<void(SymbolSlab)> SymbolsCallback,
-                           std::function<void(RefSlab)> RefsCallback);
+std::unique_ptr<FrontendAction> createStaticIndexingAction(
+    SymbolCollector::Options Opts,
+    std::function<void(RefSlab)> RefsCallback,
+    std::function<void(IncludeGraph)> IncludeGraphCallback);
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/trunk/clangd/index/IndexAction.cpp

 #include "IndexAction.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Tooling/Tooling.h"
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 namespace {
 
+llvm::Optional<std::string> toURI(const FileEntry *File) {
+  if (!File)
+    return llvm::None;
+  auto AbsolutePath = File->tryGetRealPathName();
+  if (AbsolutePath.empty())
+    return llvm::None;
+  return URI::create(AbsolutePath).toString();
+}
+
+// Collects the nodes and edges of include graph during indexing action.
+// Important: The graph generated by those callbacks might contain cycles and
+// self edges.
+struct IncludeGraphCollector : public PPCallbacks {
+public:
+  IncludeGraphCollector(const SourceManager &SM, IncludeGraph &IG)
+      : SM(SM), IG(IG) {}
+
+  // Populates everything except direct includes for a node, which represents
+  // edges in the include graph and populated in inclusion directive.
+  // We cannot populate the fields in InclusionDirective because it does not
+  // have access to the contents of the included file.
+  void FileChanged(SourceLocation Loc, FileChangeReason Reason,
+                   SrcMgr::CharacteristicKind FileType,
+                   FileID PrevFID) override {
+    // We only need to process each file once. So we don't care about anything
+    // but entries.
+    if (Reason != FileChangeReason::EnterFile)
+      return;
+
+    const auto FileID = SM.getFileID(Loc);
+    const auto File = SM.getFileEntryForID(FileID);
+    auto URI = toURI(File);
+    if (!URI)
+      return;
+    auto I = IG.try_emplace(*URI).first;
+
+    auto &Node = I->getValue();
+    // Node has already been populated.
+    if (Node.URI.data() == I->getKeyData()) {
+#ifndef NDEBUG
+      auto Digest = digestFile(SM, FileID);
+      assert(Digest && Node.Digest == *Digest &&
+             "Same file, different digest?");
+#endif
+      return;
+    }
+    if (auto Digest = digestFile(SM, FileID))
+      Node.Digest = std::move(*Digest);
+    Node.IsTU = FileID == SM.getMainFileID();
+    Node.URI = I->getKey();
+  }
+
+  // Add edges from including files to includes.
+  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 {
+    auto IncludeURI = toURI(File);
+    if (!IncludeURI)
+      return;
+
+    auto IncludingURI = toURI(SM.getFileEntryForID(SM.getFileID(HashLoc)));
+    if (!IncludingURI)
+      return;
+
+    auto NodeForInclude = IG.try_emplace(*IncludeURI).first->getKey();
+    auto NodeForIncluding = IG.try_emplace(*IncludingURI);
+
+    NodeForIncluding.first->getValue().DirectIncludes.push_back(NodeForInclude);
+  }
+
+  // Sanity check to ensure we have already populated a skipped file.
+  void FileSkipped(const FileEntry &SkippedFile, const Token &FilenameTok,
+                   SrcMgr::CharacteristicKind FileType) override {
+#ifndef NDEBUG
+    auto URI = toURI(&SkippedFile);
+    if (!URI)
+      return;
+    auto I = IG.try_emplace(*URI);
+    assert(!I.second && "File inserted for the first time on skip.");
+    assert(I.first->getKeyData() == I.first->getValue().URI.data() &&
+           "Node have not been populated yet");
+#endif
+  }
+
+private:
+  const SourceManager &SM;
+  IncludeGraph &IG;
+};
+
 // Wraps the index action and reports index data after each translation unit.
 class IndexAction : public WrapperFrontendAction {
 public:
   IndexAction(std::shared_ptr<SymbolCollector> C,
               std::unique_ptr<CanonicalIncludes> Includes,
               const index::IndexingOptions &Opts,
               std::function<void(SymbolSlab)> SymbolsCallback,
-              std::function<void(RefSlab)> RefsCallback)
+              std::function<void(RefSlab)> RefsCallback,
+              std::function<void(IncludeGraph)> IncludeGraphCallback)
       : WrapperFrontendAction(index::createIndexingAction(C, Opts, nullptr)),
         SymbolsCallback(SymbolsCallback), RefsCallback(RefsCallback),
-        Collector(C), Includes(std::move(Includes)),
+        IncludeGraphCallback(IncludeGraphCallback), Collector(C),
+        Includes(std::move(Includes)),
         PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {}
 
   std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &CI,
                                                  StringRef InFile) override {
     CI.getPreprocessor().addCommentHandler(PragmaHandler.get());
+    if (IncludeGraphCallback != nullptr)
+      CI.getPreprocessor().addPPCallbacks(
+          llvm::make_unique<IncludeGraphCollector>(CI.getSourceManager(), IG));
     return WrapperFrontendAction::CreateASTConsumer(CI, InFile);
   }
 
   bool BeginInvocation(CompilerInstance &CI) override {
     // We want all comments, not just the doxygen ones.
     CI.getLangOpts().CommentOpts.ParseAllComments = true;
     return WrapperFrontendAction::BeginInvocation(CI);
   }
 
   void EndSourceFileAction() override {
     WrapperFrontendAction::EndSourceFileAction();
 
     const auto &CI = getCompilerInstance();
     if (CI.hasDiagnostics() &&
         CI.getDiagnostics().hasUncompilableErrorOccurred()) {
       errs() << "Skipping TU due to uncompilable errors\n";
       return;
     }
     SymbolsCallback(Collector->takeSymbols());
     if (RefsCallback != nullptr)
       RefsCallback(Collector->takeRefs());
+    if (IncludeGraphCallback != nullptr) {
+#ifndef NDEBUG
+      // This checks if all nodes are initialized.
+      for (const auto &Node : IG)
+        assert(Node.getKeyData() == Node.getValue().URI.data());
+#endif
+      IncludeGraphCallback(std::move(IG));
+    }
   }
 
 private:
   std::function<void(SymbolSlab)> SymbolsCallback;
   std::function<void(RefSlab)> RefsCallback;
+  std::function<void(IncludeGraph)> IncludeGraphCallback;
   std::shared_ptr<SymbolCollector> Collector;
   std::unique_ptr<CanonicalIncludes> Includes;
   std::unique_ptr<CommentHandler> PragmaHandler;
+  IncludeGraph IG;
 };
 
 } // namespace
 
-std::unique_ptr<FrontendAction>
-createStaticIndexingAction(SymbolCollector::Options Opts,
-                           std::function<void(SymbolSlab)> SymbolsCallback,
-                           std::function<void(RefSlab)> RefsCallback) {
+std::unique_ptr<FrontendAction> createStaticIndexingAction(
+    SymbolCollector::Options Opts,
+    std::function<void(RefSlab)> RefsCallback,
+    std::function<void(IncludeGraph)> IncludeGraphCallback) {
   index::IndexingOptions IndexOpts;
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
   Opts.CollectIncludePath = true;
   Opts.CountReferences = true;
   Opts.Origin = SymbolOrigin::Static;
   if (RefsCallback != nullptr) {
     Opts.RefFilter = RefKind::All;
     Opts.RefsInHeaders = true;
   }
   auto Includes = llvm::make_unique<CanonicalIncludes>();
   addSystemHeadersMapping(Includes.get());
   Opts.Includes = Includes.get();
   return llvm::make_unique<IndexAction>(
       std::make_shared<SymbolCollector>(std::move(Opts)), std::move(Includes),
-      IndexOpts, SymbolsCallback, RefsCallback);
+      IndexOpts, SymbolsCallback, RefsCallback, IncludeGraphCallback);
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/indexer/IndexerMain.cpp

return createStaticIndexingAction(
                },
                [&](RefSlab S) {
                  std::lock_guard<std::mutex> Lock(SymbolsMu);
                  for (const auto &Sym : S) {
                    // No need to merge as currently all Refs are from main file.
                    for (const auto &Ref : Sym.second)
                      Refs.insert(Sym.first, Ref);
                  }
-               })
+               },
+               /*IncludeGraphCallback=*/nullptr)
         .release();
   }
 
   // Awkward: we write the result in the destructor, because the executor
   // takes ownership so it's the easiest way to get our data back out.
   ~IndexActionFactory() {
     Result.Symbols = std::move(Symbols).build();
     Result.Refs = std::move(Refs).build();

clang-tools-extra/trunk/unittests/clangd/CMakeLists.txt

add_extra_unittest(ClangdTests
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
   FSTests.cpp
   FunctionTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
+  IndexActionTests.cpp
   IndexTests.cpp
   JSONTransportTests.cpp
   QualityTests.cpp
   RIFFTests.cpp
   SerializationTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SymbolInfoTests.cpp

clang-tools-extra/trunk/unittests/clangd/IndexActionTests.cpp

+//===------ IndexActionTests.cpp  -------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestFS.h"
+#include "index/IndexAction.h"
+#include "clang/Tooling/Tooling.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using ::testing::AllOf;
+using ::testing::ElementsAre;
+using ::testing::Not;
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+using ::testing::UnorderedPointwise;
+
+std::string toUri(llvm::StringRef Path) { return URI::create(Path).toString(); }
+
+MATCHER(IsTU, "") { return arg.IsTU; }
+
+MATCHER_P(HasDigest, Digest, "") { return arg.Digest == Digest; }
+
+MATCHER(HasSameURI, "") {
+  llvm::StringRef URI = testing::get<0>(arg);
+  const std::string &Path = testing::get<1>(arg);
+  return toUri(Path) == URI;
+}
+
+testing::Matcher<const IncludeGraphNode &>
+IncludesAre(const std::vector<std::string> &Includes) {
+  return ::testing::Field(&IncludeGraphNode::DirectIncludes,
+                          UnorderedPointwise(HasSameURI(), Includes));
+}
+
+void checkNodesAreInitialized(const IndexFileIn &IndexFile,
+                              const std::vector<std::string> &Paths) {
+  EXPECT_THAT(Paths.size(), IndexFile.Sources->size());
+  for (llvm::StringRef Path : Paths) {
+    auto URI = toUri(Path);
+    const auto &Node = IndexFile.Sources->lookup(URI);
+    // Uninitialized nodes will have an empty URI.
+    EXPECT_EQ(Node.URI.data(), IndexFile.Sources->find(URI)->getKeyData());
+  }
+}
+
+std::map<std::string, const IncludeGraphNode &> toMap(const IncludeGraph &IG) {
+  std::map<std::string, const IncludeGraphNode &> Nodes;
+  for (auto &I : IG)
+    Nodes.emplace(I.getKey(), I.getValue());
+  return Nodes;
+}
+
+class IndexActionTest : public ::testing::Test {
+public:
+  IndexActionTest() : InMemoryFileSystem(new llvm::vfs::InMemoryFileSystem) {}
+
+  IndexFileIn
+  runIndexingAction(llvm::StringRef MainFilePath,
+                    const std::vector<std::string> &ExtraArgs = {}) {
+    IndexFileIn IndexFile;
+    IntrusiveRefCntPtr<FileManager> Files(
+        new FileManager(FileSystemOptions(), InMemoryFileSystem));
+
+    auto Action = createStaticIndexingAction(
+        SymbolCollector::Options(),
+        [&](SymbolSlab S) { IndexFile.Symbols = std::move(S); },
+        [&](RefSlab R) { IndexFile.Refs = std::move(R); },
+        [&](IncludeGraph IG) { IndexFile.Sources = std::move(IG); });
+
+    std::vector<std::string> Args = {"index_action", "-fsyntax-only",
+                                     "-xc++",        "-std=c++11",
+                                     "-iquote",      testRoot()};
+    Args.insert(Args.end(), ExtraArgs.begin(), ExtraArgs.end());
+    Args.push_back(MainFilePath);
+
+    tooling::ToolInvocation Invocation(
+        Args, Action.release(), Files.get(),
+        std::make_shared<PCHContainerOperations>());
+
+    Invocation.run();
+
+    checkNodesAreInitialized(IndexFile, FilePaths);
+    return IndexFile;
+  }
+
+  void addFile(llvm::StringRef Path, llvm::StringRef Content) {
+    InMemoryFileSystem->addFile(Path, 0,
+                                llvm::MemoryBuffer::getMemBuffer(Content));
+    FilePaths.push_back(Path);
+  }
+
+protected:
+  std::vector<std::string> FilePaths;
+  IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem;
+};
+
+TEST_F(IndexActionTest, CollectIncludeGraph) {
+  std::string MainFilePath = testPath("main.cpp");
+  std::string MainCode = "#include \"level1.h\"";
+  std::string Level1HeaderPath = testPath("level1.h");
+  std::string Level1HeaderCode = "#include \"level2.h\"";
+  std::string Level2HeaderPath = testPath("level2.h");
+  std::string Level2HeaderCode = "";
+
+  addFile(MainFilePath, MainCode);
+  addFile(Level1HeaderPath, Level1HeaderCode);
+  addFile(Level2HeaderPath, Level2HeaderCode);
+
+  IndexFileIn IndexFile = runIndexingAction(MainFilePath);
+  auto Nodes = toMap(*IndexFile.Sources);
+
+  EXPECT_THAT(Nodes,
+              UnorderedElementsAre(
+                  Pair(toUri(MainFilePath),
+                       AllOf(IsTU(), IncludesAre({Level1HeaderPath}),
+                             HasDigest(digest(MainCode)))),
+                  Pair(toUri(Level1HeaderPath),
+                       AllOf(Not(IsTU()), IncludesAre({Level2HeaderPath}),
+                             HasDigest(digest(Level1HeaderCode)))),
+                  Pair(toUri(Level2HeaderPath),
+                       AllOf(Not(IsTU()), IncludesAre({}),
+                             HasDigest(digest(Level2HeaderCode))))));
+}
+
+TEST_F(IndexActionTest, IncludeGraphSelfInclude) {
+  std::string MainFilePath = testPath("main.cpp");
+  std::string MainCode = "#include \"header.h\"";
+  std::string HeaderPath = testPath("header.h");
+  std::string HeaderCode = R"cpp(
+      #ifndef _GUARD_
+      #define _GUARD_
+      #include "header.h"
+      #endif)cpp";
+
+  addFile(MainFilePath, MainCode);
+  addFile(HeaderPath, HeaderCode);
+
+  IndexFileIn IndexFile = runIndexingAction(MainFilePath);
+  auto Nodes = toMap(*IndexFile.Sources);
+
+  EXPECT_THAT(
+      Nodes,
+      UnorderedElementsAre(
+          Pair(toUri(MainFilePath), AllOf(IsTU(), IncludesAre({HeaderPath}),
+                                          HasDigest(digest(MainCode)))),
+          Pair(toUri(HeaderPath), AllOf(Not(IsTU()), IncludesAre({HeaderPath}),
+                                        HasDigest(digest(HeaderCode))))));
+}
+
+TEST_F(IndexActionTest, IncludeGraphSkippedFile) {
+  std::string MainFilePath = testPath("main.cpp");
+  std::string MainCode = R"cpp(
+      #include "common.h"
+      #include "header.h"
+      )cpp";
+
+  std::string CommonHeaderPath = testPath("common.h");
+  std::string CommonHeaderCode = R"cpp(
+      #ifndef _GUARD_
+      #define _GUARD_
+      void f();
+      #endif)cpp";
+
+  std::string HeaderPath = testPath("header.h");
+  std::string HeaderCode = R"cpp(
+      #include "common.h"
+      void g();)cpp";
+
+  addFile(MainFilePath, MainCode);
+  addFile(HeaderPath, HeaderCode);
+  addFile(CommonHeaderPath, CommonHeaderCode);
+
+  IndexFileIn IndexFile = runIndexingAction(MainFilePath);
+  auto Nodes = toMap(*IndexFile.Sources);
+
+  EXPECT_THAT(
+      Nodes, UnorderedElementsAre(
+                 Pair(toUri(MainFilePath),
+                      AllOf(IsTU(), IncludesAre({HeaderPath, CommonHeaderPath}),
+                            HasDigest(digest(MainCode)))),
+                 Pair(toUri(HeaderPath),
+                      AllOf(Not(IsTU()), IncludesAre({CommonHeaderPath}),
+                            HasDigest(digest(HeaderCode)))),
+                 Pair(toUri(CommonHeaderPath),
+                      AllOf(Not(IsTU()), IncludesAre({}),
+                            HasDigest(digest(CommonHeaderCode))))));
+}
+
+TEST_F(IndexActionTest, IncludeGraphDynamicInclude) {
+  std::string MainFilePath = testPath("main.cpp");
+  std::string MainCode = R"cpp(
+      #ifndef FOO
+      #define FOO "main.cpp"
+      #else
+      #define FOO "header.h"
+      #endif
+
+      #include FOO)cpp";
+  std::string HeaderPath = testPath("header.h");
+  std::string HeaderCode = "";
+
+  addFile(MainFilePath, MainCode);
+  addFile(HeaderPath, HeaderCode);
+
+  IndexFileIn IndexFile = runIndexingAction(MainFilePath);
+  auto Nodes = toMap(*IndexFile.Sources);
+
+  EXPECT_THAT(
+      Nodes,
+      UnorderedElementsAre(
+          Pair(toUri(MainFilePath),
+               AllOf(IsTU(), IncludesAre({MainFilePath, HeaderPath}),
+                     HasDigest(digest(MainCode)))),
+          Pair(toUri(HeaderPath), AllOf(Not(IsTU()), IncludesAre({}),
+                                        HasDigest(digest(HeaderCode))))));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang