[clangd][fuzzyFind] Do not show stale symbols in the result.

[ArcsinX]

Summary

This is follow up to D93393.
Without this patch MergedIndex::fuzzyFind() returns stale symbols from the static index even if these symbols were removed.

[sammccall]

Yup, as mentioned on D93393 this seems like a reasonable tradeoff to me. Thanks!

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

 // The two symbols must have the same ID.
 // Returned symbol may contain data owned by either source.
 Symbol mergeSymbol(const Symbol &L, const Symbol &R);
 
 // MergedIndex is a composite index based on two provided Indexes:
 //  - the Dynamic index covers few files, but is relatively up-to-date.
 //  - the Static index covers a bigger set of files, but is relatively stale.
 // The returned index attempts to combine results, and avoid duplicates.
-//
-// FIXME: We don't have a mechanism in Index to track deleted symbols and
-// refs in dirty files, so the merged index may return stale symbols
-// and refs from Static index.
 class MergedIndex : public SymbolIndex {
   const SymbolIndex *Dynamic, *Static;
 
 public:
   // The constructor does not access the symbols.
   // It's safe to inherit from this class and pass pointers to derived members.
   MergedIndex(const SymbolIndex *Dynamic, const SymbolIndex *Static)
       : Dynamic(Dynamic), Static(Static) {}

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 {
 
-// FIXME: Deleted symbols in dirty files are still returned (from Static).
-//        To identify these eliminate these, we should:
-//          - find the generating file from each Symbol which is Static-only
-//          - ask Dynamic if it has that file (needs new SymbolIndex method)
-//          - if so, drop the Symbol.
 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;
   More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) {
     ++DynamicCount;
     DynB.insert(S);
   });
   SymbolSlab Dyn = std::move(DynB).build();
 
   llvm::DenseSet<SymbolID> SeenDynamicSymbols;
+  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))
+      return;
     auto DynS = Dyn.find(S.ID);
     ++StaticCount;
     if (DynS == Dyn.end())
       return Callback(S);
     ++MergedCount;
     SeenDynamicSymbols.insert(S.ID);
     Callback(mergeSymbol(*DynS, S));
   });

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

 std::vector<SymbolInformation> getSymbols(TestTU &TU, llvm::StringRef Query,
                                           int Limit = 0) {
   auto SymbolInfos = getWorkspaceSymbols(Query, Limit, TU.index().get(),
                                          testPath(TU.Filename));
   EXPECT_TRUE(bool(SymbolInfos)) << "workspaceSymbols returned an error";
   return *SymbolInfos;
 }
 
-TEST(WorkspaceSymbols, Macros) {
+// FIXME: We update two indexes during main file processing:
+//        - preamble index (static)
+//        - main-file index (dynamic)
+//        The macro in this test appears to be in the preamble index and not
+//        in the main-file index. According to our logic of indexes merging, we
+//        do not take this macro from the static (preamble) index, because it
+//        location within the file from the dynamic (main-file) index.
+//
+//        Possible solution is to exclude main-file symbols from the preamble
+//        index, after that we can enable this test again.
+TEST(WorkspaceSymbols, DISABLED_Macros) {
   TestTU TU;
   TU.Code = R"cpp(
        #define MACRO X
        )cpp";
 
   // LSP's SymbolKind doesn't have a "Macro" kind, and
   // indexSymbolKindToSymbolKind() currently maps macros
   // to SymbolKind::String.

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

auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
        J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
                            RelationSlab());
   FuzzyFindRequest Req;
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(MergedIndex(I.get(), J.get()), Req),
               UnorderedElementsAre("ns::A", "ns::B", "ns::C"));
 }
 
+TEST(MergeIndexTest, FuzzyFindRemovedSymbol) {
+  FileIndex DynamicIndex, StaticIndex;
+  MergedIndex Merge(&DynamicIndex, &StaticIndex);
+
+  const char *HeaderCode = "class Foo;";
+  auto HeaderSymbols = TestTU::withHeaderCode(HeaderCode).headerSymbols();
+  auto Foo = findSymbol(HeaderSymbols, "Foo");
+
+  // Build static index for test.cc with Foo symbol
+  TestTU Test;
+  Test.HeaderCode = HeaderCode;
+  Test.Code = "class Foo {};";
+  Test.Filename = "test.cc";
+  auto AST = Test.build();
+  StaticIndex.updateMain(testPath(Test.Filename), AST);
+
+  // Remove Foo symbol, i.e. build dynamic index for test.cc, which is empty.
+  Test.HeaderCode = "";
+  Test.Code = "";
+  AST = Test.build();
+  DynamicIndex.updateMain(testPath(Test.Filename), AST);
+
+  // Merged index should not return removed symbol.
+  FuzzyFindRequest Req;
+  Req.AnyScope = true;
+  Req.Query = "Foo";
+  unsigned SymbolCounter = 0;
+  bool IsIncomplete =
+      Merge.fuzzyFind(Req, [&](const Symbol &) { ++SymbolCounter; });
+  EXPECT_FALSE(IsIncomplete);
+  EXPECT_EQ(SymbolCounter, 0u);
+}
+
 TEST(MergeTest, Merge) {
   Symbol L, R;
   L.ID = R.ID = SymbolID("hello");
   L.Name = R.Name = "Foo";                           // same in both
   L.CanonicalDeclaration.FileURI = "file:///left.h"; // differs
   R.CanonicalDeclaration.FileURI = "file:///right.h";
   L.References = 1;
   R.References = 2;