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

[Sam McCall via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rL319552: [clangd] Filter completion results by fuzzy-matching 
identifiers. (authored by sammccall).

Changed prior to commit:
  https://reviews.llvm.org/D39882?vs=125009=125155#toc

Repository:
  rL LLVM

https://reviews.llvm.org/D39882

Files:
  clang-tools-extra/trunk/clangd/ClangdUnit.cpp
  clang-tools-extra/trunk/test/clangd/completion-items-kinds.test
  clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp

Index: clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp
===
--- clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp
+++ clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp
@@ -742,6 +742,61 @@
   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;
Index: clang-tools-extra/trunk/clangd/ClangdUnit.cpp
===
--- clang-tools-extra/trunk/clangd/ClangdUnit.cpp
+++ clang-tools-extra/trunk/clangd/ClangdUnit.cpp
@@ -446,13 +446,16 @@
   void ProcessCodeCompleteResults(Sema , CodeCompletionContext Context,
   CodeCompletionResult *Results,
   unsigned NumResults) override final {
+StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
 std::priority_queue Candidates;
 for (unsigned I = 0; I < NumResults; ++I) {
   auto  = 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();
@@ -476,6 +479,39 @@
   CodeCompletionTUInfo () override { return CCTUInfo; }
 
 private:
+  bool fuzzyMatch(Sema , const CodeCompletionContext , 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 

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

[Sam McCall via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rCTE319552: [clangd] Filter completion results by 
fuzzy-matching identifiers. (authored by sammccall).

Changed prior to commit:
  https://reviews.llvm.org/D39882?vs=125009=125154#toc

Repository:
  rL LLVM

https://reviews.llvm.org/D39882

Files:
  clangd/ClangdUnit.cpp
  test/clangd/completion-items-kinds.test
  unittests/clangd/ClangdTests.cpp

Index: unittests/clangd/ClangdTests.cpp
===
--- unittests/clangd/ClangdTests.cpp
+++ unittests/clangd/ClangdTests.cpp
@@ -742,6 +742,61 @@
   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;
Index: clangd/ClangdUnit.cpp
===
--- clangd/ClangdUnit.cpp
+++ clangd/ClangdUnit.cpp
@@ -446,13 +446,16 @@
   void ProcessCodeCompleteResults(Sema , CodeCompletionContext Context,
   CodeCompletionResult *Results,
   unsigned NumResults) override final {
+StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
 std::priority_queue Candidates;
 for (unsigned I = 0; I < NumResults; ++I) {
   auto  = 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();
@@ -476,6 +479,39 @@
   CodeCompletionTUInfo () override { return CCTUInfo; }
 
 private:
+  bool fuzzyMatch(Sema , const CodeCompletionContext , 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;
+  }
+
   

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

[Ilya Biryukov via Phabricator via cfe-commits]

ilya-biryukov accepted this revision.
ilya-biryukov added a comment.
This revision is now accepted and ready to land.

LGTM


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D39882



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall added a comment.

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


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D39882



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall updated this revision to Diff 125009.
sammccall added a comment.
Herald added a subscriber: klimek.

Rebase and remove debug output.


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D39882

Files:
  clangd/ClangdUnit.cpp
  unittests/clangd/ClangdTests.cpp

Index: unittests/clangd/ClangdTests.cpp
===
--- unittests/clangd/ClangdTests.cpp
+++ unittests/clangd/ClangdTests.cpp
@@ -742,6 +742,61 @@
   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;
Index: clangd/ClangdUnit.cpp
===
--- clangd/ClangdUnit.cpp
+++ clangd/ClangdUnit.cpp
@@ -446,13 +446,16 @@
   void ProcessCodeCompleteResults(Sema , CodeCompletionContext Context,
   CodeCompletionResult *Results,
   unsigned NumResults) override final {
+StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
 std::priority_queue Candidates;
 for (unsigned I = 0; I < NumResults; ++I) {
   auto  = 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();
@@ -476,6 +479,39 @@
   CodeCompletionTUInfo () override { return CCTUInfo; }
 
 private:
+  bool fuzzyMatch(Sema , const CodeCompletionContext , 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 ,
 const CodeCompletionString ) const {

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

[Sam McCall via Phabricator via cfe-commits]

sammccall added a comment.

In https://reviews.llvm.org/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.


https://reviews.llvm.org/D39882



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall updated this revision to Diff 124043.
sammccall added a comment.

Rebase


https://reviews.llvm.org/D39882

Files:
  clangd/ClangdUnit.cpp
  unittests/clangd/ClangdTests.cpp

Index: unittests/clangd/ClangdTests.cpp
===
--- unittests/clangd/ClangdTests.cpp
+++ unittests/clangd/ClangdTests.cpp
@@ -742,6 +742,61 @@
   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;
Index: clangd/ClangdUnit.cpp
===
--- clangd/ClangdUnit.cpp
+++ clangd/ClangdUnit.cpp
@@ -434,9 +434,13 @@
   void ProcessCodeCompleteResults(Sema , CodeCompletionContext Context,
   CodeCompletionResult *Results,
   unsigned NumResults) override final {
+StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
 std::priority_queue Candidates;
 for (unsigned I = 0; I < NumResults; ++I) {
-  Candidates.emplace(Results[I]);
+  auto  = Results[I];
+  if (!Filter.empty() && !fuzzyMatch(S, Context, Filter, Result))
+continue;
+  Candidates.emplace(Result);
   if (ClangdOpts.Limit && Candidates.size() > ClangdOpts.Limit) {
 Candidates.pop();
 Items.isIncomplete = true;
@@ -459,6 +463,41 @@
   CodeCompletionTUInfo () override { return CCTUInfo; }
 
 private:
+  bool fuzzyMatch(Sema , const CodeCompletionContext , 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) {
+llvm::errs() << "match " << Target << " against " << Filter << "\n";
+size_t TPos = 0;
+for (char C : Filter) {
+  TPos = Target.find_lower(C, TPos);
+  if (TPos == StringRef::npos)
+return false;
+}
+llvm::errs() << "yeah\n";
+return true;
+  }
+
   CompletionItem
   ProcessCodeCompleteResult(const CompletionCandidate ,
 const CodeCompletionString ) const {
___
cfe-commits mailing list
cfe-commits@lists.llvm.org

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

[Ilya Biryukov via Phabricator via cfe-commits]

ilya-biryukov added a comment.

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.




Comment at: clangd/ClangdUnit.cpp:427
+  static bool fuzzyMatch(StringRef Filter, StringRef Target) {
+llvm::errs() << "match " << Target << " against " << Filter << "\n";
+size_t TPos = 0;

Debug output sneaked into the commit.


https://reviews.llvm.org/D39882



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall created this revision.

This allows us to limit the number of results we return and still allow them
to be surfaced by refining a query (https://reviews.llvm.org/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.


https://reviews.llvm.org/D39882

Files:
  clangd/ClangdUnit.cpp
  unittests/clangd/ClangdTests.cpp

Index: unittests/clangd/ClangdTests.cpp
===
--- unittests/clangd/ClangdTests.cpp
+++ unittests/clangd/ClangdTests.cpp
@@ -694,6 +694,61 @@
   }
 }
 
+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(),
+  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;
Index: clangd/ClangdUnit.cpp
===
--- clangd/ClangdUnit.cpp
+++ clangd/ClangdUnit.cpp
@@ -380,9 +380,12 @@
   void ProcessCodeCompleteResults(Sema , CodeCompletionContext Context,
   CodeCompletionResult *Results,
   unsigned NumResults) override final {
+StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
 Items.reserve(NumResults);
 for (unsigned I = 0; I < NumResults; ++I) {
   auto  = Results[I];
+  if (!Filter.empty() && !fuzzyMatch(S, Context, Filter, Result))
+continue;
   const auto *CCS = Result.CreateCodeCompletionString(
   S, Context, *Allocator, CCTUInfo,
   CodeCompleteOpts.IncludeBriefComments);
@@ -397,6 +400,41 @@
   CodeCompletionTUInfo () override { return CCTUInfo; }
 
 private:
+  bool fuzzyMatch(Sema , const CodeCompletionContext , 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) {
+llvm::errs() << "match " << Target << " against " << Filter << "\n";
+size_t TPos = 0;
+for (char C : Filter) {
+  TPos = Target.find_lower(C, TPos);
+  if (TPos == StringRef::npos)
+return false;
+}
+llvm::errs() << "yeah\n";
+return true;
+  }
+
   CompletionItem
   ProcessCodeCompleteResult(const CodeCompletionResult ,
 const CodeCompletionString ) const {