[clangd] Cleanup FuzzyFindRequest filtering limit semantics

[kbobyrev]

Summary

As discussed during D51860 review, it is better to use llvm::Optional here as it has clear semantics which reflect intended behavior.

[sammccall]

Thanks!

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

477 ↗

(On Diff #165261)

nit: 'Req.Limit' would fit on the line

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

182 ↗

(On Diff #165261)

wow, this was overflowing!
I guess harmlessly to... numeric_limits<uint32>::max() - 99 or something? weird.

[kbobyrev]

Change IndexBenchmark accordingly, perform minor cleanup.

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

182 ↗

(On Diff #165261)

Oh, yeah, good catch! I thought I had some workaround at some point, but seems that it was lost at some point.

[kbobyrev]

Don't modify benchmarks since it'd clash with the parent patch in this case.

[kbobyrev]

Update requests.json to comply with the new format.

clangd/CodeComplete.cpp

private:
 
   SymbolSlab queryIndex() {
     trace::Span Tracer("Query index");
     SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit));
 
     // Build the query.
     FuzzyFindRequest Req;
     if (Opts.Limit)
-      Req.MaxCandidateCount = Opts.Limit;
+      Req.Limit = Opts.Limit;
     Req.Query = Filter->pattern();
     Req.RestrictForCodeCompletion = true;
     Req.Scopes = QueryScopes;
     // FIXME: we should send multiple weighted paths here.
     Req.ProximityPaths.push_back(FileName);
     vlog("Code complete: fuzzyFind({0:2})", toJSON(Req));
 
     if (SpecFuzzyFind)

clangd/FindSymbols.cpp

getWorkspaceSymbols(StringRef Query, int Limit, const SymbolIndex *const Index,
 
   // FuzzyFind doesn't want leading :: qualifier
   bool IsGlobalQuery = Names.first.consume_front("::");
   // Restrict results to the scope in the query string if present (global or
   // not).
   if (IsGlobalQuery || !Names.first.empty())
     Req.Scopes = {Names.first};
   if (Limit)
-    Req.MaxCandidateCount = Limit;
-  TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top(Req.MaxCandidateCount);
+    Req.Limit = Limit;
+  TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top(
+      Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
   FuzzyMatcher Filter(Req.Query);
   Index->fuzzyFind(Req, [HintPath, &Top, &Filter](const Symbol &Sym) {
     // Prefer the definition over e.g. a function declaration in a header
     auto &CD = Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration;
     auto Uri = URI::parse(CD.FileURI);
     if (!Uri) {
       log("Workspace symbol: Could not parse URI '{0}' for symbol '{1}'.",
           CD.FileURI, Sym.Name);

clangd/index/Index.h

struct FuzzyFindRequest {
   /// (e.g. namespaces) excluding nested scopes. For example, if a scope "xyz::"
   /// is provided, the matched symbols must be defined in namespace xyz but not
   /// namespace xyz::abc.
   ///
   /// The global scope is "", a top level scope is "foo::", etc.
   std::vector<std::string> Scopes;
   /// \brief The number of top candidates to return. The index may choose to
   /// return more than this, e.g. if it doesn't know which candidates are best.
-  // FIXME: Use llvm::Optional; semantically, the absence of MaxCandidateCount
-  // is equivalent to setting this field to default value as below.
-  uint32_t MaxCandidateCount = std::numeric_limits<uint32_t>::max();
+  llvm::Optional<uint32_t> Limit;
   /// If set to true, only symbols for completion support will be considered.
   bool RestrictForCodeCompletion = false;
   /// Contextually relevant files (e.g. the file we're code-completing in).
   /// Paths should be absolute.
   std::vector<std::string> ProximityPaths;
 
   bool operator==(const FuzzyFindRequest &Req) const {
-    return std::tie(Query, Scopes, MaxCandidateCount, RestrictForCodeCompletion,
+    return std::tie(Query, Scopes, Limit, RestrictForCodeCompletion,
                     ProximityPaths) ==
-           std::tie(Req.Query, Req.Scopes, Req.MaxCandidateCount,
+           std::tie(Req.Query, Req.Scopes, Req.Limit,
                     Req.RestrictForCodeCompletion, Req.ProximityPaths);
   }
   bool operator!=(const FuzzyFindRequest &Req) const { return !(*this == Req); }
 };
 bool fromJSON(const llvm::json::Value &Value, FuzzyFindRequest &Request);
 llvm::json::Value toJSON(const FuzzyFindRequest &Request);
 
 struct LookupRequest {

 class SymbolIndex {
 public:
   virtual ~SymbolIndex() = default;
 
   /// \brief Matches symbols in the index fuzzily and applies \p Callback on
   /// each matched symbol before returning.
   /// If returned Symbols are used outside Callback, they must be deep-copied!
   ///
-  /// Returns true if there may be more results (limited by MaxCandidateCount).
+  /// Returns true if there may be more results (limited by Req.Limit).
   virtual bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const = 0;
 
   /// Looks up symbols with any of the given symbol IDs and applies \p Callback
   /// on each matched symbol.
   /// The returned symbol must be deep-copied if it's used outside Callback.
   virtual void

clangd/index/Index.cpp

 }
 std::shared_ptr<SymbolIndex> SwapIndex::snapshot() const {
   std::lock_guard<std::mutex> Lock(Mutex);
   return Index;
 }
 
 bool fromJSON(const llvm::json::Value &Parameters, FuzzyFindRequest &Request) {
   json::ObjectMapper O(Parameters);
-  int64_t MaxCandidateCount;
+  int64_t Limit;
   bool OK =
       O && O.map("Query", Request.Query) && O.map("Scopes", Request.Scopes) &&
-      O.map("MaxCandidateCount", MaxCandidateCount) &&
+      O.map("Limit", Limit) &&
       O.map("RestrictForCodeCompletion", Request.RestrictForCodeCompletion) &&
       O.map("ProximityPaths", Request.ProximityPaths);
-  if (OK && MaxCandidateCount <= std::numeric_limits<uint32_t>::max())
-    Request.MaxCandidateCount = MaxCandidateCount;
+  if (OK && Limit <= std::numeric_limits<uint32_t>::max())
+    Request.Limit = Limit;
   return OK;
 }
 
 llvm::json::Value toJSON(const FuzzyFindRequest &Request) {
   return json::Object{
       {"Query", Request.Query},
       {"Scopes", json::Array{Request.Scopes}},
-      {"MaxCandidateCount", Request.MaxCandidateCount},
+      {"Limit", Request.Limit},
       {"RestrictForCodeCompletion", Request.RestrictForCodeCompletion},
       {"ProximityPaths", json::Array{Request.ProximityPaths}},
   };
 }
 
 bool SwapIndex::fuzzyFind(const FuzzyFindRequest &R,
                           llvm::function_ref<void(const Symbol &)> CB) const {
   return snapshot()->fuzzyFind(R, CB);

clangd/index/MemIndex.cpp

 }
 
 bool MemIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
 
-  TopN<std::pair<float, const Symbol *>> Top(Req.MaxCandidateCount);
+  TopN<std::pair<float, const Symbol *>> Top(
+      Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
   for (const auto Pair : Index) {
     const Symbol *Sym = Pair.second;
 
     // Exact match against all possible scopes.
     if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope))
       continue;

clangd/index/dex/Dex.cpp

bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
   auto QueryIterator = TopLevelChildren.empty()
                            ? createTrue(Symbols.size())
                            : createAnd(move(TopLevelChildren));
   // Retrieve more items than it was requested: some of  the items with high
   // final score might not be retrieved otherwise.
   // FIXME(kbobyrev): Pre-scoring retrieval threshold should be adjusted as
   // using 100x of the requested number might not be good in practice, e.g.
   // when the requested number of items is small.
-  const size_t ItemsToRetrieve = 100 * Req.MaxCandidateCount;
-  auto Root = createLimit(move(QueryIterator), ItemsToRetrieve);
+  auto Root = Req.Limit ? createLimit(move(QueryIterator), *Req.Limit * 100)
+                        : move(QueryIterator);
 
   using IDAndScore = std::pair<DocID, float>;
   std::vector<IDAndScore> IDAndScores = consume(*Root);
 
   auto Compare = [](const IDAndScore &LHS, const IDAndScore &RHS) {
     return LHS.second > RHS.second;
   };
-  TopN<IDAndScore, decltype(Compare)> Top(Req.MaxCandidateCount, Compare);
+  TopN<IDAndScore, decltype(Compare)> Top(
+      Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max(), Compare);
   for (const auto &IDAndScore : IDAndScores) {
     const DocID SymbolDocID = IDAndScore.first;
     const auto *Sym = Symbols[SymbolDocID];
     const llvm::Optional<float> Score = Filter.match(Sym->Name);
     if (!Score)
       continue;
     // Combine Fuzzy Matching score, precomputed symbol quality and boosting
     // score for a cumulative final symbol score.
     const float FinalScore =
         (*Score) * SymbolQuality[SymbolDocID] * IDAndScore.second;
     // If Top.push(...) returns true, it means that it had to pop an item. In
     // this case, it is possible to retrieve more symbols.
     if (Top.push({SymbolDocID, FinalScore}))
       More = true;
   }
 
-  // Apply callback to the top Req.MaxCandidateCount items in the descending
+  // Apply callback to the top Req.Limit items in the descending
   // order of cumulative score.
   for (const auto &Item : std::move(Top).items())
     Callback(*Symbols[Item.first]);
   return More;
 }
 
 void Dex::lookup(const LookupRequest &Req,
                  llvm::function_ref<void(const Symbol &)> Callback) const {

test/clangd/Inputs/requests.json

-[{"MaxCandidateCount":100,"ProximityPaths":["/usr/home/user/clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp"],"Query":"OMP","RestrictForCodeCompletion":true,"Scopes":["clang::"]},
-{"MaxCandidateCount":100,"ProximityPaths":[],"Query":"s","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
-{"MaxCandidateCount":100,"ProximityPaths":[],"Query":"sy","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
-{"MaxCandidateCount":100,"ProximityPaths":[],"Query":"sys","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
-{"MaxCandidateCount":100,"ProximityPaths":[],"Query":"sys","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
-{"MaxCandidateCount":100,"ProximityPaths":[],"Query":"Dex","RestrictForCodeCompletion":true,"Scopes":["clang::clangd::", "clang::", "clang::clangd::dex::"]},
-{"MaxCandidateCount":100,"ProximityPaths":[],"Query":"Variable","RestrictForCodeCompletion":true,"Scopes":[""]}]
+[{"Limit":100,"ProximityPaths":["/usr/home/user/clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp"],"Query":"OMP","RestrictForCodeCompletion":true,"Scopes":["clang::"]},
+{"Limit":100,"ProximityPaths":[],"Query":"s","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
+{"Limit":100,"ProximityPaths":[],"Query":"sy","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
+{"Limit":100,"ProximityPaths":[],"Query":"sys","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
+{"Limit":100,"ProximityPaths":[],"Query":"sys","RestrictForCodeCompletion":true,"Scopes":["llvm::", ""]},
+{"Limit":100,"ProximityPaths":[],"Query":"Dex","RestrictForCodeCompletion":true,"Scopes":["clang::clangd::", "clang::", "clang::clangd::dex::"]},
+{"Limit":100,"ProximityPaths":[],"Query":"Variable","RestrictForCodeCompletion":true,"Scopes":[""]}]

unittests/clangd/DexTests.cpp

 }
 
 TEST(DexTest, FuzzyMatchQ) {
   auto I = Dex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
       URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "lol";
-  Req.MaxCandidateCount = 2;
+  Req.Limit = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 // FIXME(kbobyrev): This test is different for Dex and MemIndex: while
 // MemIndex manages response deduplication, Dex simply returns all matched
 // symbols which means there might be equivalent symbols in the response.
 // Before drop-in replacement of MemIndex with Dex happens, FileIndex
 // should handle deduplication instead.
 TEST(DexTest, DexDeduplicate) {
   std::vector<Symbol> Symbols = {symbol("1"), symbol("2"), symbol("3"),
                                  symbol("2") /* duplicate */};
   FuzzyFindRequest Req;
   Req.Query = "2";
   Dex I(Symbols, URISchemes);
+  EXPECT_FALSE(Req.Limit);
   EXPECT_THAT(match(I, Req), ElementsAre("2", "2"));
 }
 
 TEST(DexTest, DexLimitedNumMatches) {
   auto I = Dex::build(generateNumSymbols(0, 100), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "5";
-  Req.MaxCandidateCount = 3;
+  Req.Limit = 3;
   bool Incomplete;
   auto Matches = match(*I, Req, &Incomplete);
-  EXPECT_EQ(Matches.size(), Req.MaxCandidateCount);
+  EXPECT_TRUE(Req.Limit);
+  EXPECT_EQ(Matches.size(), *Req.Limit);
   EXPECT_TRUE(Incomplete);
 }
 
 TEST(DexTest, FuzzyMatch) {
   auto I = Dex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
       URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "lol";
-  Req.MaxCandidateCount = 2;
+  Req.Limit = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 TEST(DexTest, MatchQualifiedNamesWithoutSpecificScope) {
   auto I =
       Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), URISchemes);
   FuzzyFindRequest Req;
TEST(DexTest, ProximityPathsBoosting) {
   CloseSymbol.CanonicalDeclaration.FileURI = "unittest:///a/b/c/d/e/f/file.h";
 
   std::vector<Symbol> Symbols{CloseSymbol, RootSymbol};
   Dex I(Symbols, URISchemes);
 
   FuzzyFindRequest Req;
   Req.Query = "abc";
   // The best candidate can change depending on the proximity paths.
-  Req.MaxCandidateCount = 1;
+  Req.Limit = 1;
 
   // FuzzyFind request comes from the file which is far from the root: expect
   // CloseSymbol to come out.
   Req.ProximityPaths = {testPath("a/b/c/d/e/f/file.h")};
   EXPECT_THAT(match(I, Req), ElementsAre("close::abc"));
 
   // FuzzyFind request comes from the file which is close to the root: expect
   // RootSymbol to come out.
   Req.ProximityPaths = {testPath("file.h")};
   EXPECT_THAT(match(I, Req), ElementsAre("root::abc"));
 }
 
 } // namespace
 } // namespace dex
 } // namespace clangd
 } // namespace clang

unittests/clangd/IndexTests.cpp

TEST(MemIndexTest, MemIndexDeduplicate) {
   MemIndex I(Symbols, RefSlab());
   EXPECT_THAT(match(I, Req), ElementsAre("2"));
 }
 
 TEST(MemIndexTest, MemIndexLimitedNumMatches) {
   auto I = MemIndex::build(generateNumSymbols(0, 100), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "5";
-  Req.MaxCandidateCount = 3;
+  Req.Limit = 3;
   bool Incomplete;
   auto Matches = match(*I, Req, &Incomplete);
-  EXPECT_EQ(Matches.size(), Req.MaxCandidateCount);
+  EXPECT_TRUE(Req.Limit);
+  EXPECT_EQ(Matches.size(), *Req.Limit);
   EXPECT_TRUE(Incomplete);
 }
 
 TEST(MemIndexTest, FuzzyMatch) {
   auto I = MemIndex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
       RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "lol";
-  Req.MaxCandidateCount = 2;
+  Req.Limit = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
   auto I =
       MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
   FuzzyFindRequest Req;