[clangd] Perform merging for stale symbols in MergeIndex

[kadircet]

Summary

Clangd drops symbols from static index whenever the dynamic index is
authoritative for the file. This results in regressions when static and
dynamic index contains different set of information, e.g.
IncludeHeaders.

After this patch, we'll choose to merge symbols from static index with
dynamic one rather than just dropping. This implies correctness problems
when the definition/documentation of the symbol is deleted. But seems
like it is worth having in more cases.

We still drop symbols if dynamic index owns the file and didn't report
the symbol, which means symbol is deleted.

[kadircet]

ping

[sammccall]

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

59

this bool seems complicated enough & duplicated that you could consider pulling out

static bool indexIsAuthoritative(const SymbolIndex::IndexedFiles&, const Symbol &S);

(The IndexedFiles typedef doesn't exist, but it should!)

67

we could SPAN_ATTACH a counter for this too, e.g. static_dropped

(and possibly hoist ++StaticCount to the top, static_dropped can be a subset)

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

318

Bah, this is actually incorrect, for the given example, right? We point to a definition that doesn't exist, in a file where the index is up to date.
Can we at least hint why we do this?
("This seems wrong, but is generic behavior we want for e.g. include headers which are always missing from the dynamic index")

[kadircet]

• Add comments to the unittest to explain why we chose incorrect behaviour.
• Extract authorization logic to a helper.
• Count dropped symbols separately in fuzzyfind tracer stats.

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

bool MergedIndex::fuzzyFind(
   unsigned StaticCount = 0;
   unsigned MergedCount = 0;
   More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) {
     ++DynamicCount;
     DynB.insert(S);
   });
   SymbolSlab Dyn = std::move(DynB).build();
 
-  llvm::DenseSet<SymbolID> SeenDynamicSymbols;
+  llvm::DenseSet<SymbolID> ReportedDynSymbols;
   {
     auto DynamicContainsFile = Dynamic->indexedFiles();
     More |= Static->fuzzyFind(Req, [&](const Symbol &S) {
-      // We expect the definition to see the canonical declaration, so it seems
-      // to be enough to check only the definition if it exists.
-      if ((DynamicContainsFile(S.Definition ? S.Definition.FileURI
+      auto DynS = Dyn.find(S.ID);
+      // If symbol also exist in the dynamic index, just merge and report.
+      if (DynS != Dyn.end()) {
+        ++StaticCount;
+        ++MergedCount;
+        ReportedDynSymbols.insert(S.ID);
+        return Callback(mergeSymbol(*DynS, S));
+      }
+
+      bool DynamicIndexIsAuthoritative =
+          // We expect the definition to see the canonical declaration, so it
+          // seems to be enough to check only the definition if it exists.
+          (DynamicContainsFile(S.Definition ? S.Definition.FileURI
                                             : S.CanonicalDeclaration.FileURI) &
-           IndexContents::Symbols) != IndexContents::None)
+           IndexContents::Symbols) != IndexContents::None;
+      // Otherwise, if the dynamic index owns the symbol's file, it means static
+      // index is stale just drop the symbol.
+      if (DynamicIndexIsAuthoritative)
         return;
-      auto DynS = Dyn.find(S.ID);
+
+      // If not just report the symbol from static index as is.
       ++StaticCount;
-      if (DynS == Dyn.end())
-        return Callback(S);
-      ++MergedCount;
-      SeenDynamicSymbols.insert(S.ID);
-      Callback(mergeSymbol(*DynS, S));
     });
   }
   SPAN_ATTACH(Tracer, "dynamic", DynamicCount);
   SPAN_ATTACH(Tracer, "static", StaticCount);
   SPAN_ATTACH(Tracer, "merged", MergedCount);
   for (const Symbol &S : Dyn)
-    if (!SeenDynamicSymbols.count(S.ID))
+    if (!ReportedDynSymbols.count(S.ID))
       Callback(S);
   return More;
 }
 
 void MergedIndex::lookup(
     const LookupRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   trace::Span Tracer("MergedIndex lookup");
   SymbolSlab::Builder B;
 
   Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); });
 
   auto RemainingIDs = Req.IDs;
   {
     auto DynamicContainsFile = Dynamic->indexedFiles();
     Static->lookup(Req, [&](const Symbol &S) {
-      // We expect the definition to see the canonical declaration, so it seems
-      // to be enough to check only the definition if it exists.
-      if ((DynamicContainsFile(S.Definition ? S.Definition.FileURI
+      // If we've seen the symbol before, just merge.
+      if (const Symbol *Sym = B.find(S.ID)) {
+        RemainingIDs.erase(S.ID);
+        return Callback(mergeSymbol(*Sym, S));
+      }
+
+      // If symbol is missing in dynamic index, and dynamic index owns the
+      // symbol's file. Static index is stale, just drop the symbol.
+      bool DynamicIndexIsAuthoritative =
+          // We expect the definition to see the canonical declaration, so it
+          // seems to be enough to check only the definition if it exists.
+          (DynamicContainsFile(S.Definition ? S.Definition.FileURI
                                             : S.CanonicalDeclaration.FileURI) &
-           IndexContents::Symbols) != IndexContents::None)
+           IndexContents::Symbols) != IndexContents::None;
+      if (DynamicIndexIsAuthoritative)
         return;
-      const Symbol *Sym = B.find(S.ID);
+
+      // Dynamic index doesn't know about this file, just use the symbol from
+      // static index.
       RemainingIDs.erase(S.ID);
-      if (!Sym)
-        Callback(S);
-      else
-        Callback(mergeSymbol(*Sym, S));
     });
   }
   for (const auto &ID : RemainingIDs)
     if (const Symbol *Sym = B.find(ID))
       Callback(*Sym);
 }
 
 bool MergedIndex::refs(const RefsRequest &Req,

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

 //===-- IndexTests.cpp  -------------------------------*- 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 "Annotations.h"
+#include "SyncAPI.h"
 #include "TestIndex.h"
 #include "TestTU.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "index/MemIndex.h"
 #include "index/Merge.h"
 #include "index/Symbol.h"
 #include "clang/Index/IndexSymbol.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <utility>
 
 using ::testing::_;
 using ::testing::AllOf;
 using ::testing::AnyOf;
 using ::testing::ElementsAre;
 using ::testing::IsEmpty;
 using ::testing::Pair;
 using ::testing::Pointee;
TEST(MergeIndexTest, LookupRemovedDefinition) {
   StaticIndex.updateMain(testPath(Test.Filename), AST);
 
   // Remove Foo definition from test.cc, i.e. build dynamic index for test.cc
   // without Foo definition.
   Test.Code = "class Foo;";
   AST = Test.build();
   DynamicIndex.updateMain(testPath(Test.Filename), AST);
 
-  // Merged index should not return the symbol definition if this definition
-  // location is inside a file from the dynamic index.
+  // Even though the definition is actually deleted in the newer version of the
+  // file, we still chose to merge with information coming from static index.
   LookupRequest LookupReq;
   LookupReq.IDs = {Foo.ID};
   unsigned SymbolCounter = 0;
   Merge.lookup(LookupReq, [&](const Symbol &Sym) {
     ++SymbolCounter;
-    EXPECT_FALSE(Sym.Definition);
+    EXPECT_TRUE(Sym.Definition);
   });
   EXPECT_EQ(SymbolCounter, 1u);
+
+  // Drop the symbol completely.
+  Test.Code = "class Bar {};";
+  AST = Test.build();
+  DynamicIndex.updateMain(testPath(Test.Filename), AST);
+
+  // Now we don't expect to see the symbol at all.
+  SymbolCounter = 0;
+  Merge.lookup(LookupReq, [&](const Symbol &Sym) { ++SymbolCounter; });
+  EXPECT_EQ(SymbolCounter, 0u);
 }
 
 TEST(MergeIndexTest, FuzzyFind) {
   auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
                            RelationSlab()),
        J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
                            RelationSlab());
   FuzzyFindRequest Req;
TEST(MergeTest, MergeIncludesOnDifferentDefinitions) {
   // Definitions are different.
   R.Definition.FileURI = "file:/right.h";
   M = mergeSymbol(L, R);
   EXPECT_THAT(M.IncludeHeaders,
               UnorderedElementsAre(IncludeHeaderWithRef("common", 2u),
                                    IncludeHeaderWithRef("new", 1u)));
 }
 
+TEST(MergeIndexTest, IncludeHeadersMerged) {
+  auto S = symbol("Z");
+  S.Definition.FileURI = "unittest:///foo.cc";
+
+  SymbolSlab::Builder DynB;
+  S.IncludeHeaders.clear();
+  DynB.insert(S);
+  SymbolSlab DynSymbols = std::move(DynB).build();
+  RefSlab DynRefs;
+  auto DynSize = DynSymbols.bytes() + DynRefs.bytes();
+  auto DynData = std::make_pair(std::move(DynSymbols), std::move(DynRefs));
+  llvm::StringSet<> DynFiles = {S.Definition.FileURI};
+  MemIndex DynIndex(std::move(DynData.first), std::move(DynData.second),
+                    RelationSlab(), std::move(DynFiles), IndexContents::Symbols,
+                    std::move(DynData), DynSize);
+
+  SymbolSlab::Builder StaticB;
+  S.IncludeHeaders.push_back({"<header>", 0});
+  StaticB.insert(S);
+  auto StaticIndex =
+      MemIndex::build(std::move(StaticB).build(), RefSlab(), RelationSlab());
+  MergedIndex Merge(&DynIndex, StaticIndex.get());
+
+  EXPECT_THAT(runFuzzyFind(Merge, S.Name),
+              ElementsAre(testing::Field(
+                  &Symbol::IncludeHeaders,
+                  ElementsAre(IncludeHeaderWithRef("<header>", 0u)))));
+
+  LookupRequest Req;
+  Req.IDs = {S.ID};
+  std::string IncludeHeader;
+  Merge.lookup(Req, [&](const Symbol &S) {
+    EXPECT_TRUE(IncludeHeader.empty());
+    ASSERT_EQ(S.IncludeHeaders.size(), 1u);
+    IncludeHeader = S.IncludeHeaders.front().IncludeHeader.str();
+  });
+  EXPECT_EQ(IncludeHeader, "<header>");
+}
 } // namespace
 } // namespace clangd
 } // namespace clang