[clangd] Use URIs instead of paths in the index file list

[ArcsinX]

Summary

Without this patch the file list of the preamble index contains URIs, but other indexes file lists contain file paths.
This makes indexedFiles() always returns IndexContents::None for the preamble index, because current implementation expects file paths inside the file list of the index.

This patch fixes this problem and also helps to avoid a lot of URI to path conversions during indexes merge.

[ArcsinX]

Initial discussion D94952#inline-892421

[kadircet]

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

279

iterating over all the symbols here (and refs below) seems really unfortunate. But looking at the previous discussions that seems to be best of both worlds until we populate a file list in SymbolCollector. However, I think it would be better to do the looping after releasing the lock (we already have the information copied over to our snapshots).

moreover we seem to be still inserting keys of the Symbol and RefSlabs into Files, but not doing that for RelationSlabs, why? (i believe we shouldn't be inserting the keys at all, if we indeed want to just insert URIs and keep treating the keys as opaque objects).

[ArcsinX]

• Do not insert the keys into the file list
• Iterate through refs and symbols to create the file list after releasing the lock

[ArcsinX]

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

279

However, I think it would be better to do the looping after releasing the lock (we already have the information copied over to our snapshots).

Done

we seem to be still inserting keys of the Symbol and RefSlabs into Files, but not doing that for RelationSlabs

Forgot to remove these insertions, thanks, fixed.

[kadircet]

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

297

it feels weird to choose one or the other here, why not just insert both (after checking if definition exists, ofc).

We are likely to have a merged symbol information anyway, and the logic here will likely result in no index owning the header files, unless there are some symbols *defined* (not just declared) in it.

This will likely result in some overshooting as knowing about a symbols declaration location doesn't mean indexing that particular file. But so does the current version, as knowing about definition location might be because of a merged symbol, rather than indexing of particular file.

[ArcsinX]

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

297

I will try to explain on example:

• test.h

void f();

• test.c

#include "test.h"
void f() { }

• compile_commands.json contains a command for test.c compilation.

Scenario:

• open test.c
• try to find all references for f()

For that scenario result for find all references will be incorrect if both (decl and def) files are in the file list because:

• decl location is inside test.h
• def location is inside test.c
• the file list for the main file index contains test.h and test.c
• the main file index does not contain references from test.h
• the background (static) index contains references from test.c, but results from the background index will be skipped, because test.h is in the main file (dynamic) index file list.

[kadircet]

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

297

Ah i see. This all seems really fragile :/ We might as well have something like:

a.h:

struct Bar;

a.cc:

#include "a.h"
struct Bar;

and now as soon as you open a.cc, all the results from a.h will be gone, because canonical declaration location for Bar will be in a.h and there is no definition. (and i believe this kind of forward-decl madness is quite common in at least LLVM).
Even worse, the same will also happen even if you have definition in the header, but a forward decl in the main file, so even accepting the file for definition wouldn't be enough.

It is currently (i.e. without this patch) working as expected, as main file index only owns the information for the "main file" indexing was initiated for. This feels like a big regression to me (that I didn't notice initially, sorry for that), but I am ready to be convinced otherwise :D

As Sam mentioned what you do here and partitioning logic in FileShardedIndex is quite similar (yours undershoot, sharding logic overshoots) but in the sharding process we split indexing result of a full TU/preamble, and later on those shards will always be used in a merged fashion (e.g. when a.cc and b.cc, both including a.h gets indexed, the shard produced for a.h from b.cc won't contain any definition locations, but the shard produced for a.cc will know about those symbols definition locations and in a merged view those symbols will have all the necessary information.), whereas in here the resulting information is used in isolation (main file isn't merged with preamble symbols, but mixes Files view). Hence causing such regressions.

I think the proper thing to do here is to propagate relevant files with slabs on FileSymbols::update. What you do here and sharding isn't very different. The question is should we have a:

• string File
• optional<string> File
• vector<string> Files

Currently we always have exactly one File associated with all of those slabs as we either:

• always do sharding (preamble and background idx)
• even though symbol informations tell otherwise, we've only processed a single file (main file idx)

We would need 3rd option if we were to use filesymbols with a monolithic index, but we don't. And even if we need such a thing in future it shouldn't be a huge change hopefully.

Sorry for the wall of text, I hope I do make sense, but please tell me if I misunderstood/missing something.

[ArcsinX]

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

297

It is currently (i.e. without this patch) working as expected, as main file index only owns the information for the "main file" indexing was initiated for. This feels like a big regression to me (that I didn't notice initially, sorry for that), but I am ready to be convinced otherwise :D

Currently it works mostly as expected. The only thing which worries me is the preamble index update: the first parameter passed to PreambleSymbols.update() is an URI, but we expect a file path there. Thus, the file list of the preamble index contains URIs, which seems incorrect and PreambleIndex::indexedFiles() always returns IndexContents::None.

In other words, we need to make the file list to contains always file paths or always URIs (current situation: the preamble index contains URIs, other indexes contain file paths). I thought that the best solution is to convert URI to file path before PreambleSymbols.update() call, but after D94952#inline-892421 discussion I was no sure about my solution, and seems the solution introduces in this patch also inacceptable.

Currently I am not sure what is the best way to solve this problem =(

[kadircet]

Right, i see the problem you are trying to solve, and all of this is a mess working nicely in unisom, but falls apart if you try to isolate each piece :/ (hence the need for figuring out list of files while indexing instead)

But until that day, I suppose the best we can do is change the contract of FileSymbols to sey keys are always URIs representing the file producing associated slabs. This works:

• For preamble symbols, because even though some shards might contain partial information, when merged they indeed correspond to those set of files, and we always query preamble index in a merged fashion.
• Bg-index is literally the same as preamble-index in that regard
• Main file index will only associate slabs with the "main file" now, which will stop the leakage i mentioned above.

Sorry for going in circles here a bit but it took us some time to figure out the issue here, does that make sense for you too?

[ArcsinX]

In D97535#2596992, @kadircet wrote:

But until that day, I suppose the best we can do is change the contract of FileSymbols to sey keys are always URIs representing the file producing associated slabs.

Agree. I will rework this patch.

[ArcsinX]

• use URIs as keys
• create the file list from the keys

[kadircet]

thanks (both for the patch and bearing with me :D), LGTM!

[ArcsinX]

Call FileIndex::updateMain() with an absolute file path in tests to avoid test failures in debug mode.

[ArcsinX]

Thank you for review!

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

if (auto Error = IndexStorageFactory(Path)->storeShard(Path, *IF))
         continue;
       SV.Digest = Hash;
       SV.HadErrors = HadErrors;
 
       // This can override a newer version that is added in another thread, if
       // this thread sees the older version but finishes later. This should be
       // rare in practice.
       IndexedSymbols.update(
-          Path, std::make_unique<SymbolSlab>(std::move(*IF->Symbols)),
+          Uri, std::make_unique<SymbolSlab>(std::move(*IF->Symbols)),
           std::make_unique<RefSlab>(std::move(*IF->Refs)),
           std::make_unique<RelationSlab>(std::move(*IF->Relations)),
           Path == MainFile);
     }
   }
 }
 
 llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd) {
for (auto &LS : Result) {
           LS.Shard->Relations
               ? std::make_unique<RelationSlab>(std::move(*LS.Shard->Relations))
               : nullptr;
       ShardVersion &SV = ShardVersions[LS.AbsolutePath];
       SV.Digest = LS.Digest;
       SV.HadErrors = LS.HadErrors;
       ++LoadedShards;
 
-      IndexedSymbols.update(LS.AbsolutePath, std::move(SS), std::move(RS),
-                            std::move(RelS), LS.CountReferences);
+      IndexedSymbols.update(URI::create(LS.AbsolutePath).toString(),
+                            std::move(SS), std::move(RS), std::move(RelS),
+                            LS.CountReferences);
     }
   }
   Rebuilder.loadedShard(LoadedShards);
   Rebuilder.doneLoading();
 
   auto FS = TFS.view(/*CWD=*/llvm::None);
   llvm::DenseSet<PathRef> TUsToIndex;
   // We'll accept data from stale shards, but ensure the files get reindexed

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

FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle,
   std::vector<std::shared_ptr<RefSlab>> RefSlabs;
   std::vector<std::shared_ptr<RelationSlab>> RelationSlabs;
   llvm::StringSet<> Files;
   std::vector<RefSlab *> MainFileRefs;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto &FileAndSymbols : SymbolsSnapshot) {
       SymbolSlabs.push_back(FileAndSymbols.second);
       Files.insert(FileAndSymbols.first());
     }
     for (const auto &FileAndRefs : RefsSnapshot) {
       RefSlabs.push_back(FileAndRefs.second.Slab);
       Files.insert(FileAndRefs.first());
       if (FileAndRefs.second.CountReferences)
         MainFileRefs.push_back(RefSlabs.back().get());
     }
     for (const auto &FileAndRelations : RelationsSnapshot) {
       Files.insert(FileAndRelations.first());
       RelationSlabs.push_back(FileAndRelations.second);
     }
 
     if (Version)
       *Version = this->Version;
   }
   std::vector<const Symbol *> AllSymbols;
   std::vector<Symbol> SymsStorage;
   switch (DuplicateHandle) {
   case DuplicateHandling::Merge: {
     llvm::DenseMap<SymbolID, Symbol> Merged;
     for (const auto &Slab : SymbolSlabs) {
       for (const auto &Sym : *Slab) {
         assert(Sym.References == 0 &&
                "Symbol with non-zero references sent to FileSymbols");
         auto I = Merged.try_emplace(Sym.ID, Sym);
         if (!I.second)
vlog(
         "{0} bytes",
         PreambleIndex.estimateMemoryUsage());
   }
 }
 
 void FileIndex::updateMain(PathRef Path, ParsedAST &AST) {
   auto Contents = indexMainDecls(AST);
   MainFileSymbols.update(
-      Path, std::make_unique<SymbolSlab>(std::move(std::get<0>(Contents))),
+      URI::create(Path).toString(),
+      std::make_unique<SymbolSlab>(std::move(std::get<0>(Contents))),
       std::make_unique<RefSlab>(std::move(std::get<1>(Contents))),
       std::make_unique<RelationSlab>(std::move(std::get<2>(Contents))),
       /*CountReferences=*/true);
   size_t IndexVersion = 0;
   auto NewIndex = MainFileSymbols.buildIndex(
       IndexType::Light, DuplicateHandling::Merge, &IndexVersion);
   {
     std::lock_guard<std::mutex> Lock(UpdateIndexMu);

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

for (const SymbolID &Subject : Req.Subjects) {
     }
     lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
   }
 }
 
 llvm::unique_function<IndexContents(llvm::StringRef) const>
 MemIndex::indexedFiles() const {
   return [this](llvm::StringRef FileURI) {
-    if (Files.empty())
-      return IndexContents::None;
-    auto Path = URI::resolve(FileURI, Files.begin()->first());
-    if (!Path) {
-      vlog("Failed to resolve the URI {0} : {1}", FileURI, Path.takeError());
-      return IndexContents::None;
-    }
-    return Files.contains(*Path) ? IdxContents : IndexContents::None;
+    return Files.contains(FileURI) ? IdxContents : IndexContents::None;
   };
 }
 
 size_t MemIndex::estimateMemoryUsage() const {
   return Index.getMemorySize() + Refs.getMemorySize() +
          Relations.getMemorySize() + BackingDataSize;
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/dex/Dex.cpp

for (const SymbolID &Subject : Req.Subjects) {
     }
     lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
   }
 }
 
 llvm::unique_function<IndexContents(llvm::StringRef) const>
 Dex::indexedFiles() const {
   return [this](llvm::StringRef FileURI) {
-    if (Files.empty())
-      return IndexContents::None;
-    auto Path = URI::resolve(FileURI, Files.begin()->first());
-    if (!Path) {
-      vlog("Failed to resolve the URI {0} : {1}", FileURI, Path.takeError());
-      return IndexContents::None;
-    }
-    return Files.contains(*Path) ? IdxContents : IndexContents::None;
+    return Files.contains(FileURI) ? IdxContents : IndexContents::None;
   };
 }
 
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
   Bytes += LookupTable.getMemorySize();
   Bytes += InvertedIndex.getMemorySize();

clang-tools-extra/clangd/test/memory_tree.test

 # CHECK-NEXT:         "main_file": {
 # CHECK-NEXT:           "_self": {{[0-9]+}},
 # CHECK-NEXT:           "_total": {{[0-9]+}},
 # CHECK-NEXT:           "index": {
 # CHECK-NEXT:             "_self": {{[0-9]+}},
 # CHECK-NEXT:             "_total": {{[0-9]+}}
 # CHECK-NEXT:           },
 # CHECK-NEXT:           "slabs": {
-# CHECK-NEXT:             "{{.*}}main.cpp": {
+# CHECK-NEXT:             "_self": {{[0-9]+}},
+# CHECK-NEXT:             "_total": {{[0-9]+}},
+# CHECK-NEXT:             "test:///main.cpp": {
 # CHECK-NEXT:               "_self": {{[0-9]+}},
 # CHECK-NEXT:               "_total": {{[0-9]+}},
 # CHECK-NEXT:               "references": {
 # CHECK-NEXT:                 "_self": {{[0-9]+}},
 # CHECK-NEXT:                 "_total": {{[0-9]+}}
 # CHECK-NEXT:               },
 # CHECK-NEXT:               "relations": {
 # CHECK-NEXT:                 "_self": {{[0-9]+}},
 # CHECK-NEXT:                 "_total": {{[0-9]+}}
 # CHECK-NEXT:               },
 # CHECK-NEXT:               "symbols": {
 # CHECK-NEXT:                 "_self": {{[0-9]+}},
 # CHECK-NEXT:                 "_total": {{[0-9]+}}
 # CHECK-NEXT:               }
-# CHECK-NEXT:             },
-# CHECK-NEXT:             "_self": {{[0-9]+}},
-# CHECK-NEXT:             "_total": {{[0-9]+}}
+# CHECK-NEXT:             }
 # CHECK-NEXT:           }
 # CHECK-NEXT:         },
 # CHECK-NEXT:         "preamble": {
 # CHECK-NEXT:           "_self": {{[0-9]+}},
 # CHECK-NEXT:           "_total": {{[0-9]+}},
 # CHECK-NEXT:           "index": {
 # CHECK-NEXT:             "_self": {{[0-9]+}},
 # CHECK-NEXT:             "_total": {{[0-9]+}}

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

TEST(DexTests, Relations) {
   EXPECT_THAT(Results, UnorderedElementsAre(Child1.ID, Child2.ID));
 }
 
 TEST(DexIndex, IndexedFiles) {
   SymbolSlab Symbols;
   RefSlab Refs;
   auto Size = Symbols.bytes() + Refs.bytes();
   auto Data = std::make_pair(std::move(Symbols), std::move(Refs));
-  llvm::StringSet<> Files = {testPath("foo.cc"), testPath("bar.cc")};
+  llvm::StringSet<> Files = {"unittest:///foo.cc", "unittest:///bar.cc"};
   Dex I(std::move(Data.first), std::move(Data.second), RelationSlab(),
         std::move(Files), IndexContents::All, std::move(Data), Size);
   auto ContainsFile = I.indexedFiles();
   EXPECT_EQ(ContainsFile("unittest:///foo.cc"), IndexContents::All);
   EXPECT_EQ(ContainsFile("unittest:///bar.cc"), IndexContents::All);
   EXPECT_EQ(ContainsFile("unittest:///foobar.cc"), IndexContents::None);
 }
 

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

TEST(FileIndexTest, Refs) {
 
   FileIndex Index;
   // Add test.cc
   TestTU Test;
   Test.HeaderCode = HeaderCode;
   Test.Code = std::string(MainCode.code());
   Test.Filename = "test.cc";
   auto AST = Test.build();
-  Index.updateMain(Test.Filename, AST);
+  Index.updateMain(testPath(Test.Filename), AST);
   // Add test2.cc
   TestTU Test2;
   Test2.HeaderCode = HeaderCode;
   Test2.Code = std::string(MainCode.code());
   Test2.Filename = "test2.cc";
   AST = Test2.build();
-  Index.updateMain(Test2.Filename, AST);
+  Index.updateMain(testPath(Test2.Filename), AST);
 
   EXPECT_THAT(getRefs(Index, Foo.ID),
               RefsAre({AllOf(RefRange(MainCode.range("foo")),
                              FileURI("unittest:///test.cc")),
                        AllOf(RefRange(MainCode.range("foo")),
                              FileURI("unittest:///test2.cc"))}));
 }
 
TEST(FileIndexTest, MacroRefs) {
 
   FileIndex Index;
   // Add test.cc
   TestTU Test;
   Test.HeaderCode = std::string(HeaderCode.code());
   Test.Code = std::string(MainCode.code());
   Test.Filename = "test.cc";
   auto AST = Test.build();
-  Index.updateMain(Test.Filename, AST);
+  Index.updateMain(testPath(Test.Filename), AST);
 
   auto HeaderMacro = findSymbol(Test.headerSymbols(), "HEADER_MACRO");
   EXPECT_THAT(getRefs(Index, HeaderMacro.ID),
               RefsAre({AllOf(RefRange(MainCode.range("ref1")),
                              FileURI("unittest:///test.cc"))}));
 
   auto MainFileMacro = findSymbol(Test.headerSymbols(), "MAINFILE_MACRO");
   EXPECT_THAT(getRefs(Index, MainFileMacro.ID),

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

TEST(MemIndexTest, Lookup) {
   EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre());
 }
 
 TEST(MemIndexTest, IndexedFiles) {
   SymbolSlab Symbols;
   RefSlab Refs;
   auto Size = Symbols.bytes() + Refs.bytes();
   auto Data = std::make_pair(std::move(Symbols), std::move(Refs));
-  llvm::StringSet<> Files = {testPath("foo.cc"), testPath("bar.cc")};
+  llvm::StringSet<> Files = {"unittest:///foo.cc", "unittest:///bar.cc"};
   MemIndex I(std::move(Data.first), std::move(Data.second), RelationSlab(),
              std::move(Files), IndexContents::All, std::move(Data), Size);
   auto ContainsFile = I.indexedFiles();
   EXPECT_EQ(ContainsFile("unittest:///foo.cc"), IndexContents::All);
   EXPECT_EQ(ContainsFile("unittest:///bar.cc"), IndexContents::All);
   EXPECT_EQ(ContainsFile("unittest:///foobar.cc"), IndexContents::None);
 }
 
EXPECT_THAT(std::move(Results3).build(),
                                       FileURI("unittest:///test2.cc"))))));
 }
 
 TEST(MergeIndexTest, IndexedFiles) {
   SymbolSlab DynSymbols;
   RefSlab DynRefs;
   auto DynSize = DynSymbols.bytes() + DynRefs.bytes();
   auto DynData = std::make_pair(std::move(DynSymbols), std::move(DynRefs));
-  llvm::StringSet<> DynFiles = {testPath("foo.cc")};
+  llvm::StringSet<> DynFiles = {"unittest:///foo.cc"};
   MemIndex DynIndex(std::move(DynData.first), std::move(DynData.second),
                     RelationSlab(), std::move(DynFiles), IndexContents::Symbols,
                     std::move(DynData), DynSize);
   SymbolSlab StaticSymbols;
   RefSlab StaticRefs;
   auto StaticData =
       std::make_pair(std::move(StaticSymbols), std::move(StaticRefs));
-  llvm::StringSet<> StaticFiles = {testPath("foo.cc"), testPath("bar.cc")};
+  llvm::StringSet<> StaticFiles = {"unittest:///foo.cc", "unittest:///bar.cc"};
   MemIndex StaticIndex(
       std::move(StaticData.first), std::move(StaticData.second), RelationSlab(),
       std::move(StaticFiles), IndexContents::References, std::move(StaticData),
       StaticSymbols.bytes() + StaticRefs.bytes());
   MergedIndex Merge(&DynIndex, &StaticIndex);
 
   auto ContainsFile = Merge.indexedFiles();
   EXPECT_EQ(ContainsFile("unittest:///foo.cc"),