[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

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)

73

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

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/Index.h

public:
   /// each.
   virtual void relations(
       const RelationsRequest &Req,
       llvm::function_ref<void(const SymbolID &Subject, const Symbol &Object)>
           Callback) const = 0;
 
   /// Returns function which checks if the specified file was used to build this
   /// index or not. The function must only be called while the index is alive.
-  virtual llvm::unique_function<IndexContents(llvm::StringRef) const>
-  indexedFiles() const = 0;
+  using IndexedFiles =
+      llvm::unique_function<IndexContents(llvm::StringRef) const>;
+  virtual IndexedFiles indexedFiles() const = 0;
 
   /// Returns estimated size of index (in bytes).
   virtual size_t estimateMemoryUsage() const = 0;
 };
 
 // Delegating implementation of SymbolIndex whose delegate can be swapped out.
 class SwapIndex : public SymbolIndex {
 public:

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

 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <iterator>
 
 namespace clang {
 namespace clangd {
 
+namespace {
+
+// Returns true if file defining/declaring \p S is covered by \p Index.
+bool isIndexAuthoritative(const SymbolIndex::IndexedFiles &Index,
+                          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.
+  const char *OwningFile =
+      S.Definition ? S.Definition.FileURI : S.CanonicalDeclaration.FileURI;
+  return (Index(OwningFile) & IndexContents::Symbols) != IndexContents::None;
+}
+} // namespace
+
 bool MergedIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   // We can't step through both sources in parallel. So:
   //  1) query all dynamic symbols, slurping results into a slab
   //  2) query the static symbols, for each one:
   //    a) if it's not in the dynamic slab, yield it directly
   //    b) if it's in the dynamic slab, merge it and yield the result
   //  3) now yield all the dynamic symbols we haven't processed.
   trace::Span Tracer("MergedIndex fuzzyFind");
   bool More = false; // We'll be incomplete if either source was.
   SymbolSlab::Builder DynB;
   unsigned DynamicCount = 0;
   unsigned StaticCount = 0;
   unsigned MergedCount = 0;
+  // Number of results ignored due to staleness.
+  unsigned StaticDropped = 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
-                                            : S.CanonicalDeclaration.FileURI) &
-           IndexContents::Symbols) != IndexContents::None)
-        return;
-      auto DynS = Dyn.find(S.ID);
       ++StaticCount;
-      if (DynS == Dyn.end())
-        return Callback(S);
+      auto DynS = Dyn.find(S.ID);
+      // If symbol also exist in the dynamic index, just merge and report.
+      if (DynS != Dyn.end()) {
         ++MergedCount;
-      SeenDynamicSymbols.insert(S.ID);
-      Callback(mergeSymbol(*DynS, S));
+        ReportedDynSymbols.insert(S.ID);
+        return Callback(mergeSymbol(*DynS, S));
+      }
+
+      // Otherwise, if the dynamic index owns the symbol's file, it means static
+      // index is stale just drop the symbol.
+      if (isIndexAuthoritative(DynamicContainsFile, S)) {
+        ++StaticDropped;
+        return;
+      }
+
+      // If not just report the symbol from static index as is.
+      return Callback(S);
     });
   }
   SPAN_ATTACH(Tracer, "dynamic", DynamicCount);
   SPAN_ATTACH(Tracer, "static", StaticCount);
+  SPAN_ATTACH(Tracer, "static_dropped", StaticDropped);
   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
-                                            : S.CanonicalDeclaration.FileURI) &
-           IndexContents::Symbols) != IndexContents::None)
+      // 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.
+      if (isIndexAuthoritative(DynamicContainsFile, S))
         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.
+  // This seems wrong, but is generic behavior we want for e.g. include headers
+  // which are always missing from the dynamic 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