[clangd] Filter completion results by fuzzy-matching identifiers.

[sammccall]

Summary

This allows us to limit the number of results we return and still allow them
to be surfaced by refining a query (D39852).

The initial algorithm is very conservative - it accepts a completion if the
filter is any case-insensitive sub-sequence. It does not attempt to rank items
based on match quality.

[ilya-biryukov]

We definitely need to:

• Rebase this change on top of current head (to account for limits and scoring)
• Set incomplete=true for fuzzy-matched completion results

Maybe also make fuzzy-matching configurable via a flag? Off-by-default for now, so we could start testing it before we finish optimizing single-identifier edits. When we have it, enable fuzzy-matching by default.

clangd/ClangdUnit.cpp

506

Debug output sneaked into the commit.

[sammccall]

Rebase

[sammccall]

In D39882#932858, @ilya-biryukov wrote:

We definitely need to:

• Rebase this change on top of current head (to account for limits and scoring)

Done. There's very little interaction - for now the match doesn't affect scoring, we're just shifting work from the client to the server.

• Set incomplete=true for fuzzy-matched completion results

Why? If you complete "foo.b^" then "qux" isn't a valid result. Clients *must* requery when erasing anyway, regardless of isIncomplete - it's only "further typing" that can reuse the result set.

Maybe also make fuzzy-matching configurable via a flag? Off-by-default for now, so we could start testing it before we finish optimizing single-identifier edits. When we have it, enable fuzzy-matching by default.

Why?
I don't think it makes sense to put this behind a flag, unless we're just worried the code is buggy. I'm already concerned about the proliferation of flags for features users *might* care about, this one either works or it doesn't.
This patch just says "don't return qux() if the user presses ctrl-space after foo.b". It doesn't affect the existing behavior when user types "foo." - we'll still request completion, the filter will be empty. And this patch doesn't affect ranking.

[sammccall]

Rebase and remove debug output.

[sammccall]

@ilya-biryukov Ping... this is the patch we wanted to land this week, so long result sets are correct for user testing next week.

[ilya-biryukov]

LGTM

clangd/ClangdUnit.cpp

CompletionItemsCollector(const clangd::CodeCompleteOptions &CodeCompleteOpts,
                              /*OutputIsBinary=*/false),
         ClangdOpts(CodeCompleteOpts), Items(Items),
         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
         CCTUInfo(Allocator) {}
 
   void ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context,
                                   CodeCompletionResult *Results,
                                   unsigned NumResults) override final {
+    StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
     std::priority_queue<CompletionCandidate> Candidates;
     for (unsigned I = 0; I < NumResults; ++I) {
       auto &Result = Results[I];
       if (!ClangdOpts.IncludeIneligibleResults &&
           (Result.Availability == CXAvailability_NotAvailable ||
            Result.Availability == CXAvailability_NotAccessible))
         continue;
+      if (!Filter.empty() && !fuzzyMatch(S, Context, Filter, Result))
+        continue;
       Candidates.emplace(Result);
       if (ClangdOpts.Limit && Candidates.size() > ClangdOpts.Limit) {
         Candidates.pop();
         Items.isIncomplete = true;
       }
     }
     while (!Candidates.empty()) {
       auto &Candidate = Candidates.top();
       const auto *CCS = Candidate.Result->CreateCodeCompletionString(
           S, Context, *Allocator, CCTUInfo,
           CodeCompleteOpts.IncludeBriefComments);
       assert(CCS && "Expected the CodeCompletionString to be non-null");
       Items.items.push_back(ProcessCodeCompleteResult(Candidate, *CCS));
       Candidates.pop();
     }
     std::reverse(Items.items.begin(), Items.items.end());
   }
 
   GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
 
   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
 
 private:
+  bool fuzzyMatch(Sema &S, const CodeCompletionContext &CCCtx, StringRef Filter,
+                  CodeCompletionResult Result) {
+    switch (Result.Kind) {
+    case CodeCompletionResult::RK_Declaration:
+      if (auto *ID = Result.Declaration->getIdentifier())
+        return fuzzyMatch(Filter, ID->getName());
+      break;
+    case CodeCompletionResult::RK_Keyword:
+      return fuzzyMatch(Filter, Result.Keyword);
+    case CodeCompletionResult::RK_Macro:
+      return fuzzyMatch(Filter, Result.Macro->getName());
+    case CodeCompletionResult::RK_Pattern:
+      return fuzzyMatch(Filter, Result.Pattern->getTypedText());
+    }
+    auto *CCS = Result.CreateCodeCompletionString(
+        S, CCCtx, *Allocator, CCTUInfo, /*IncludeBriefComments=*/false);
+    return fuzzyMatch(Filter, CCS->getTypedText());
+  }
+
+  // Checks whether Target matches the Filter.
+  // Currently just requires a case-insensitive subsequence match.
+  // FIXME: make stricter and word-based: 'unique_ptr' should not match 'que'.
+  // FIXME: return a score to be incorporated into ranking.
+  static bool fuzzyMatch(StringRef Filter, StringRef Target) {
+    size_t TPos = 0;
+    for (char C : Filter) {
+      TPos = Target.find_lower(C, TPos);
+      if (TPos == StringRef::npos)
+        return false;
+    }
+    return true;
+  }
+
   CompletionItem
   ProcessCodeCompleteResult(const CompletionCandidate &Candidate,
                             const CodeCompletionString &CCS) const {
 
     // Adjust this to InsertTextFormat::Snippet iff we encounter a
     // CK_Placeholder chunk in SnippetCompletionItemsCollector.
     CompletionItem Item;
     Item.insertTextFormat = InsertTextFormat::PlainText;

unittests/clangd/ClangdTests.cpp

int main() { ClassWithMembers().{complete} }
 
   EXPECT_TRUE(Results.isIncomplete);
   EXPECT_EQ(Opts.Limit, Results.items.size());
   EXPECT_TRUE(ContainsItem(Results, "AAA"));
   EXPECT_TRUE(ContainsItem(Results, "BBB"));
   EXPECT_FALSE(ContainsItem(Results, "CCC"));
 }
 
+TEST_F(ClangdCompletionTest, Filter) {
+  MockFSProvider FS;
+  MockCompilationDatabase CDB(/*AddFreestandingFlag=*/true);
+  CDB.ExtraClangFlags.push_back("-xc++");
+  ErrorCheckingDiagConsumer DiagConsumer;
+  clangd::CodeCompleteOptions Opts;
+  ClangdServer Server(CDB, DiagConsumer, FS, getDefaultAsyncThreadsCount(),
+                      /*StorePreamblesInMemory=*/true, Opts,
+                      EmptyLogger::getInstance());
+
+  auto FooCpp = getVirtualTestFilePath("foo.cpp");
+  FS.Files[FooCpp] = "";
+  FS.ExpectedFile = FooCpp;
+  const char *Body = R"cpp(
+    int Abracadabra;
+    int Alakazam;
+    struct S {
+      int FooBar;
+      int FooBaz;
+      int Qux;
+    };
+  )cpp";
+  auto Complete = [&](StringRef Query) {
+    StringWithPos Completion = parseTextMarker(
+        formatv("{0} int main() { {1}{{complete}} }", Body, Query).str(),
+        "complete");
+    Server.addDocument(FooCpp, Completion.Text);
+    return Server
+        .codeComplete(FooCpp, Completion.MarkerPos, StringRef(Completion.Text))
+        .get()
+        .Value;
+  };
+
+  auto Foba = Complete("S().Foba");
+  EXPECT_TRUE(ContainsItem(Foba, "FooBar"));
+  EXPECT_TRUE(ContainsItem(Foba, "FooBaz"));
+  EXPECT_FALSE(ContainsItem(Foba, "Qux"));
+
+  auto FR = Complete("S().FR");
+  EXPECT_TRUE(ContainsItem(FR, "FooBar"));
+  EXPECT_FALSE(ContainsItem(FR, "FooBaz"));
+  EXPECT_FALSE(ContainsItem(FR, "Qux"));
+
+  auto Op = Complete("S().opr");
+  EXPECT_TRUE(ContainsItem(Op, "operator="));
+
+  auto Aaa = Complete("aaa");
+  EXPECT_TRUE(ContainsItem(Aaa, "Abracadabra"));
+  EXPECT_TRUE(ContainsItem(Aaa, "Alakazam"));
+
+  auto UA = Complete("_a");
+  EXPECT_TRUE(ContainsItem(UA, "static_cast"));
+  EXPECT_FALSE(ContainsItem(UA, "Abracadabra"));
+}
+
 TEST_F(ClangdCompletionTest, CompletionOptions) {
   MockFSProvider FS;
   ErrorCheckingDiagConsumer DiagConsumer;
   MockCompilationDatabase CDB(/*AddFreestandingFlag=*/true);
   CDB.ExtraClangFlags.push_back("-xc++");
 
   auto FooCpp = getVirtualTestFilePath("foo.cpp");
   FS.Files[FooCpp] = "";