[clangd] Add bool return type to Index::refs API.

[hokein]

Summary

Similar to fuzzyFind, the bool indicates whether there are more xref
results.

[merge_guards_bot]

Build result: pass - 59972 tests passed, 0 failed and 763 were skipped.
Log files: console-log.txt, CMakeCache.txt

[ilya-biryukov]

NIT: we could probably add LLVM_NODISCARD attribute to ensure the return value is always consumed?
Another NIT: maybe do this for all methods in the index that have the limit in their request (pretty much all of them, I guess)?

[hokein]

In D70139#1743512, @ilya-biryukov wrote:

NIT: we could probably add LLVM_NODISCARD attribute to ensure the return value is always consumed?
Another NIT: maybe do this for all methods in the index that have the limit in their request (pretty much all of them, I guess)?

This restriction seems too strong (every caller has to handle this return value), I'd keep as it-is (consistent with the fuzzyFind API).

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

public:
   lookup(const LookupRequest &Req,
          llvm::function_ref<void(const Symbol &)> Callback) const = 0;
 
   /// Finds all occurrences (e.g. references, declarations, definitions) of a
   /// symbol and applies \p Callback on each result.
   ///
   /// Results should be returned in arbitrary order.
   /// The returned result must be deep-copied if it's used outside Callback.
-  virtual void refs(const RefsRequest &Req,
+  ///
+  /// Returns true if there will be more results (limited by Req.Limit);
+  virtual bool refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const = 0;
 
   /// Finds all relations (S, P, O) stored in the index such that S is among
   /// Req.Subjects and P is Req.Predicate, and invokes \p Callback for (S, O) in
   /// each.
   virtual void relations(
       const RelationsRequest &Req,
       llvm::function_ref<void(const SymbolID &Subject, const Symbol &Object)>
public:
   void reset(std::unique_ptr<SymbolIndex>);
 
   // SymbolIndex methods delegate to the current index, which is kept alive
   // until the call returns (even if reset() is called).
   bool fuzzyFind(const FuzzyFindRequest &,
                  llvm::function_ref<void(const Symbol &)>) const override;
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override;
-  void refs(const RefsRequest &,
+  bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
 
   size_t estimateMemoryUsage() const override;
 
 private:

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

 bool SwapIndex::fuzzyFind(const FuzzyFindRequest &R,
                           llvm::function_ref<void(const Symbol &)> CB) const {
   return snapshot()->fuzzyFind(R, CB);
 }
 void SwapIndex::lookup(const LookupRequest &R,
                        llvm::function_ref<void(const Symbol &)> CB) const {
   return snapshot()->lookup(R, CB);
 }
-void SwapIndex::refs(const RefsRequest &R,
+bool SwapIndex::refs(const RefsRequest &R,
                      llvm::function_ref<void(const Ref &)> CB) const {
   return snapshot()->refs(R, CB);
 }
 void SwapIndex::relations(
     const RelationsRequest &R,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> CB) const {
   return snapshot()->relations(R, CB);
 }
 
 size_t SwapIndex::estimateMemoryUsage() const {
   return snapshot()->estimateMemoryUsage();
 }
 
 } // namespace clangd
 } // namespace clang

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

public:
 
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
-  void refs(const RefsRequest &Req,
+  bool refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
   size_t estimateMemoryUsage() const override;
 

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

void MemIndex::lookup(const LookupRequest &Req,
   trace::Span Tracer("MemIndex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = Index.find(ID);
     if (I != Index.end())
       Callback(*I->second);
   }
 }
 
-void MemIndex::refs(const RefsRequest &Req,
+bool MemIndex::refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const {
   trace::Span Tracer("MemIndex refs");
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  bool More = false;
   for (const auto &ReqID : Req.IDs) {
     auto SymRefs = Refs.find(ReqID);
     if (SymRefs == Refs.end())
       continue;
     for (const auto &O : SymRefs->second) {
-      if (Remaining > 0 && static_cast<int>(Req.Filter & O.Kind)) {
+      if (!static_cast<int>(Req.Filter & O.Kind))
+        continue;
+      if (Remaining == 0) {
+        More = true;
+        break;
+      }
+      if (Remaining > 0) {
         --Remaining;
         Callback(O);
       }
     }
   }
+  return More;
 }
 
 void MemIndex::relations(
     const RelationsRequest &Req,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   for (const SymbolID &Subject : Req.Subjects) {

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

public:
   // 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) {}
 
   bool fuzzyFind(const FuzzyFindRequest &,
                  llvm::function_ref<void(const Symbol &)>) const override;
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override;
-  void refs(const RefsRequest &,
+  bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
   size_t estimateMemoryUsage() const override {
     return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
   }
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MERGE_H

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

Static->lookup(Req, [&](const Symbol &S) {
     else
       Callback(mergeSymbol(*Sym, S));
   });
   for (const auto &ID : RemainingIDs)
     if (const Symbol *Sym = B.find(ID))
       Callback(*Sym);
 }
 
-void MergedIndex::refs(const RefsRequest &Req,
+bool MergedIndex::refs(const RefsRequest &Req,
                        llvm::function_ref<void(const Ref &)> Callback) const {
   trace::Span Tracer("MergedIndex refs");
+  bool More = false;
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   // We don't want duplicated refs from the static/dynamic indexes,
   // and we can't reliably deduplicate them because offsets may differ slightly.
   // We consider the dynamic index authoritative and report all its refs,
   // and only report static index refs from other files.
   //
   // FIXME: The heuristic fails if the dynamic index contains a file, but all
   // refs were removed (we will report stale ones from the static index).
   // Ultimately we should explicit check which index has the file instead.
   llvm::StringSet<> DynamicIndexFileURIs;
-  Dynamic->refs(Req, [&](const Ref &O) {
+  More |= Dynamic->refs(Req, [&](const Ref &O) {
     DynamicIndexFileURIs.insert(O.Location.FileURI);
     Callback(O);
     --Remaining;
   });
-  if (Remaining == 0)
-    return;
+  if (Remaining == 0 && More)
+    return More;
   // We return less than Req.Limit if static index returns more refs for dirty
   // files.
-  Static->refs(Req, [&](const Ref &O) {
-    if (Remaining > 0 && !DynamicIndexFileURIs.count(O.Location.FileURI)) {
+  More |= Static->refs(Req, [&](const Ref &O) {
+    if (DynamicIndexFileURIs.count(O.Location.FileURI))
+      return; // ignore refs that have been seen from dynamic index.
+    if (Remaining == 0)
+      More = true;
+    if (Remaining > 0) {
       --Remaining;
       Callback(O);
     }
   });
+  return More;
 }
 
 void MergedIndex::relations(
     const RelationsRequest &Req,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   // Return results from both indexes but avoid duplicates.

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

public:
 
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
-  void refs(const RefsRequest &Req,
+  bool refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
   size_t estimateMemoryUsage() const override;
 

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

void Dex::lookup(const LookupRequest &Req,
   trace::Span Tracer("Dex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = LookupTable.find(ID);
     if (I != LookupTable.end())
       Callback(*I->second);
   }
 }
 
-void Dex::refs(const RefsRequest &Req,
+bool Dex::refs(const RefsRequest &Req,
                llvm::function_ref<void(const Ref &)> Callback) const {
   trace::Span Tracer("Dex refs");
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  bool More = false;
   for (const auto &ID : Req.IDs)
     for (const auto &Ref : Refs.lookup(ID)) {
-      if (Remaining > 0 && static_cast<int>(Req.Filter & Ref.Kind)) {
+      if (!static_cast<int>(Req.Filter & Ref.Kind))
+        continue;
+      if (Remaining == 0) {
+        More = true;
+        break;
+      }
+      if (Remaining > 0) {
         --Remaining;
         Callback(Ref);
       }
     }
+  return More;
 }
 
 void Dex::relations(
     const RelationsRequest &Req,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
   trace::Span Tracer("Dex relations");
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());

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

fuzzyFind(const FuzzyFindRequest &Req,
     Requests.push_back(Req);
     ReceivedRequestCV.notify_one();
     return true;
   }
 
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override {}
 
-  void refs(const RefsRequest &,
-            llvm::function_ref<void(const Ref &)>) const override {}
+  bool refs(const RefsRequest &,
+            llvm::function_ref<void(const Ref &)>) const override {
+    return false;
+  }
 
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override {}
 
   // This is incorrect, but IndexRequestCollector is not an actual index and it
   // isn't used in production code.
   size_t estimateMemoryUsage() const override { return 0; }

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

TEST(DexTests, Refs) {
   AddRef(Foo, "reffoo.h", RefKind::Reference);
   AddRef(Bar, "bar.h", RefKind::Declaration);
 
   RefsRequest Req;
   Req.IDs.insert(Foo.ID);
   Req.Filter = RefKind::Declaration | RefKind::Definition;
 
   std::vector<std::string> Files;
-  Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab())
-      .refs(Req, [&](const Ref &R) { Files.push_back(R.Location.FileURI); });
+  EXPECT_FALSE(Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab())
+                   .refs(Req, [&](const Ref &R) {
+                     Files.push_back(R.Location.FileURI);
+                   }));
   EXPECT_THAT(Files, UnorderedElementsAre("foo.h", "foo.cc"));
 
   Req.Limit = 1;
   Files.clear();
-  Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab())
-      .refs(Req, [&](const Ref &R) { Files.push_back(R.Location.FileURI); });
+  EXPECT_TRUE(Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab())
+                  .refs(Req, [&](const Ref &R) {
+                    Files.push_back(R.Location.FileURI);
+                  }));
   EXPECT_THAT(Files, ElementsAre(AnyOf("foo.h", "foo.cc")));
 }
 
 TEST(DexTests, Relations) {
   auto Parent = symbol("Parent");
   auto Child1 = symbol("Child1");
   auto Child2 = symbol("Child2");
 

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

TEST(MergeIndexTest, Refs) {
   Test2.Code = Test2Code.code();
   Test2.Filename = "test2.cc";
   StaticAST = Test2.build();
   StaticIndex.updateMain(Test2.Filename, StaticAST);
 
   RefsRequest Request;
   Request.IDs = {Foo.ID};
   RefSlab::Builder Results;
-  Merge.refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); });
+  EXPECT_FALSE(
+      Merge.refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); }));
   EXPECT_THAT(
       std::move(Results).build(),
       ElementsAre(Pair(
           _, UnorderedElementsAre(AllOf(RefRange(Test1Code.range("Foo")),
                                         FileURI("unittest:///test.cc")),
                                   AllOf(RefRange(Test2Code.range("Foo")),
                                         FileURI("unittest:///test2.cc"))))));
 
   Request.Limit = 1;
   RefSlab::Builder Results2;
-  Merge.refs(Request, [&](const Ref &O) { Results2.insert(Foo.ID, O); });
+  EXPECT_TRUE(
+      Merge.refs(Request, [&](const Ref &O) { Results2.insert(Foo.ID, O); }));
   EXPECT_THAT(std::move(Results2).build(),
               ElementsAre(Pair(
                   _, ElementsAre(AnyOf(FileURI("unittest:///test.cc"),
                                        FileURI("unittest:///test2.cc"))))));
 }
 
 TEST(MergeIndexTest, NonDocumentation) {
   using index::SymbolKind;

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

TEST(FindReferences, NeedsIndex) {
   TU.Code = ("\n\n" + Main.code()).str();
   EXPECT_THAT(findReferences(AST, Main.point(), 0, TU.index().get()),
               ElementsAre(RangeIs(Main.range())));
 }
 
 TEST(FindReferences, NoQueryForLocalSymbols) {
   struct RecordingIndex : public MemIndex {
     mutable Optional<llvm::DenseSet<SymbolID>> RefIDs;
-    void refs(const RefsRequest &Req,
+    bool refs(const RefsRequest &Req,
               llvm::function_ref<void(const Ref &)>) const override {
       RefIDs = Req.IDs;
+      return false;
     }
   };
 
   struct Test {
     StringRef AnnotatedCode;
     bool WantQuery;
   } Tests[] = {
       {"int ^x;", true},