[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

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

28

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

33

s/enteries/entries

44

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

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

63

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

72

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

125

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

149

NIT: maybe remove != nullptr?

unittests/clangd/IndexActionTests.cpp

80

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

105

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?

127

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

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.

125

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

unittests/clangd/IndexActionTests.cpp

127

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

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.

125

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

unittests/clangd/IndexActionTests.cpp

127

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

NIT: maybe call it toURI?

23

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

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

152

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

unittests/clangd/IndexActionTests.cpp

28

Maybe inline this? This looks simple enough.

32

Why not simply return arg.IsTU?

38

Why not return arg.Digest == Digest?

88

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

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

149

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

162

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

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

[ilya-biryukov]

clangd/index/IndexAction.cpp

31

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

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

28

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

53

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

110

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?

129

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

[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

169

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

212

Is there a way to make this format nicer?

226

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

169

Is it that important?

226

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

169

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.

226

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

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

unittests/clangd/IndexActionTests.cpp

53

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

[kadircet]

• Address comments

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 = nullptr);
 
 } // namespace clangd
 } // namespace clang
 
 #endif

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> URIFromFileEntry(const FileEntry *File) {
+  if (!File)
+    return llvm::None;
+  auto AbsolutePath = File->tryGetRealPathName();
+  if (AbsolutePath.empty())
+    return llvm::None;
+  auto U = URI::create(AbsolutePath);
+  return U.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 the following fields of the corresponding node for a new include:
+  // - Digest -> SHA1 hash of the file.
+  // - IsTU -> true if the file is the main file the indexing action has been
+  //   started on.
+  // - URI -> Reference to the key for this node in the include graph.
+  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 = URIFromFileEntry(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 = URIFromFileEntry(File);
+    if (!IncludeURI)
+      return;
+
+    auto IncludingURI =
+        URIFromFileEntry(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 = URIFromFileEntry(&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
+      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

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

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 PathToURI(llvm::StringRef Path) {
+  return URI::create(Path).toString();
+}
+
+MATCHER(IsTU, "") {
+  const IncludeGraphNode &Node = arg;
+  return Node.IsTU;
+}
+
+MATCHER_P(HasDigest, Digest, "") {
+  const IncludeGraphNode &Node = arg;
+  return Node.Digest == Digest;
+}
+
+MATCHER(HasSameURI, "") {
+  llvm::StringRef URI = testing::get<0>(arg);
+  const std::string &Path = testing::get<1>(arg);
+  return PathToURI(Path) == URI;
+}
+
+testing::Matcher<const IncludeGraphNode &>
+IncludesAre(const std::vector<std::string> &Includes) {
+  return ::testing::Field(&IncludeGraphNode::DirectIncludes,
+                          UnorderedPointwise(HasSameURI(), Includes));
+}
+
+class IndexActionTest : public ::testing::Test {
+public:
+  IndexActionTest() : InMemoryFileSystem(new llvm::vfs::InMemoryFileSystem) {}
+
+  void runIndexingAction(llvm::StringRef MainFilePath,
+                         const std::vector<std::string> &ExtraArgs = {}) {
+    IntrusiveRefCntPtr<FileManager> Files(
+        new FileManager(FileSystemOptions(), InMemoryFileSystem));
+
+    auto Action = createStaticIndexingAction(
+        SymbolCollector::Options(),
+        [&](SymbolSlab S) { Symbols = std::move(S); },
+        [&](RefSlab R) { Refs = std::move(R); },
+        [&](IncludeGraph IG) { this->IG = 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();
+  }
+
+  void addFile(llvm::StringRef Path, llvm::StringRef Content) {
+    InMemoryFileSystem->addFile(Path, 0,
+                                llvm::MemoryBuffer::getMemBuffer(Content));
+  }
+
+protected:
+  IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem;
+  SymbolSlab Symbols;
+  RefSlab Refs;
+  IncludeGraph IG;
+  SymbolCollector::Options CollectorOpts;
+};
+
+TEST_F(IndexActionTest, CollectIncludeGraph) {
+  std::string MainFilePath = testPath("main.cpp");
+  std::pair<std::string, std::string> Level1Header = {testPath("level1.h"),
+                                                      "#include \"level2.h\""};
+  std::pair<std::string, std::string> Level2Header = {testPath("level2.h"), ""};
+
+  std::string MainCode = R"cpp(
+  #include "level1.h"
+  )cpp";
+  addFile(MainFilePath, MainCode);
+  addFile(Level1Header.first, Level1Header.second);
+  addFile(Level2Header.first, Level2Header.second);
+
+  runIndexingAction(MainFilePath);
+  std::vector<std::pair<std::string, IncludeGraphNode>> IGFlattened;
+  for (auto &I : IG)
+    IGFlattened.push_back({I.getKey(), I.getValue()});
+
+  EXPECT_THAT(IGFlattened,
+              UnorderedElementsAre(
+                  Pair(PathToURI(MainFilePath),
+                       AllOf(IsTU(), IncludesAre({Level1Header.first}),
+                             HasDigest(digest(MainCode)))),
+                  Pair(PathToURI(Level1Header.first),
+                       AllOf(Not(IsTU()), IncludesAre({Level2Header.first}),
+                             HasDigest(digest(Level1Header.second)))),
+                  Pair(PathToURI(Level2Header.first),
+                       AllOf(Not(IsTU()), IncludesAre({}),
+                             HasDigest(digest(Level2Header.second))))));
+
+  for (const auto &Path :
+       {MainFilePath, Level1Header.first, Level2Header.first}) {
+    auto URI = PathToURI(Path);
+    const auto &Node = IG.lookup(URI);
+    EXPECT_EQ(Node.URI.data(), IG.find(URI)->getKeyData());
+  }
+}
+
+TEST_F(IndexActionTest, IncludeGraphSelfInclude) {
+  std::string MainFilePath = testPath("main.cpp");
+  std::pair<std::string, std::string> Header = {testPath("header.h"),
+                                                R"cpp(
+                                                #ifndef _GUARD_
+                                                #define _GUARD_
+                                                #include "header.h"
+                                                #endif
+                                                )cpp"};
+  std::string MainCode = R"cpp(
+  #include "header.h"
+  )cpp";
+
+  addFile(MainFilePath, MainCode);
+  addFile(Header.first, Header.second);
+
+  runIndexingAction(MainFilePath);
+  std::vector<std::pair<std::string, IncludeGraphNode>> IGFlattened;
+  for (auto &I : IG)
+    IGFlattened.push_back({I.getKey(), I.getValue()});
+
+  EXPECT_THAT(
+      IGFlattened,
+      UnorderedElementsAre(Pair(PathToURI(MainFilePath),
+                                AllOf(IsTU(), IncludesAre({Header.first}),
+                                      HasDigest(digest(MainCode)))),
+                           Pair(PathToURI(Header.first),
+                                AllOf(Not(IsTU()), IncludesAre({Header.first}),
+                                      HasDigest(digest(Header.second))))));
+
+  for (const auto &Path : {MainFilePath, Header.first}) {
+    auto URI = PathToURI(Path);
+    const auto &Node = IG.lookup(URI);
+    EXPECT_EQ(Node.URI.data(), IG.find(URI)->getKeyData());
+  }
+}
+
+TEST_F(IndexActionTest, IncludeGraphSkippedFile) {
+  std::string MainFilePath = testPath("main.cpp");
+  std::pair<std::string, std::string> CommonHeader = {testPath("common.h"),
+                                                      R"cpp(
+                                                #ifndef _GUARD_
+                                                #define _GUARD_
+                                                void f();
+                                                #endif
+                                                )cpp"};
+  std::pair<std::string, std::string> Header = {testPath("header.h"),
+                                                R"cpp(
+                                                #include "common.h"
+                                                void g();
+                                                )cpp"};
+  std::string MainCode = R"cpp(
+  #include "common.h"
+  #include "header.h"
+  )cpp";
+
+  addFile(MainFilePath, MainCode);
+  addFile(Header.first, Header.second);
+  addFile(CommonHeader.first, CommonHeader.second);
+
+  runIndexingAction(MainFilePath);
+  std::vector<std::pair<std::string, IncludeGraphNode>> IGFlattened;
+  for (auto &I : IG)
+    IGFlattened.push_back({I.getKey(), I.getValue()});
+
+  EXPECT_THAT(
+      IGFlattened,
+      UnorderedElementsAre(
+          Pair(PathToURI(MainFilePath),
+               AllOf(IsTU(), IncludesAre({Header.first, CommonHeader.first}),
+                     HasDigest(digest(MainCode)))),
+          Pair(PathToURI(Header.first),
+               AllOf(Not(IsTU()), IncludesAre({CommonHeader.first}),
+                     HasDigest(digest(Header.second)))),
+          Pair(PathToURI(CommonHeader.first),
+               AllOf(Not(IsTU()), IncludesAre({}),
+                     HasDigest(digest(CommonHeader.second))))));
+
+  for (const auto &Path : {MainFilePath, Header.first, CommonHeader.first}) {
+    auto URI = PathToURI(Path);
+    const auto &Node = IG.lookup(URI);
+    EXPECT_EQ(Node.URI.data(), IG.find(URI)->getKeyData());
+  }
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang