[clangd] Use more relaxed fuzzy-matching rules for local variables and class members.

[sammccall]

Summary

I think the actual rules implemented here are probably *too* relaxed, and we
should require the first character to match the start of a word segment.
But I'm not sure and this was easier to write, will try it out.

[ilya-biryukov]

With two modes of operation, could inconsistencies between the client-side and the server-side filtering become more/less of an issue?
Is it true that the clients (VSCode, etc) do something closer to Lax mode?

[ilya-biryukov]

Another fair question is: how much should we care about client-side and server-side filtering consistencty in the first place?

clangd/CodeComplete.cpp

case CodeCompletionResult::RK_Macro:
     return CompletionItemKind::Text; // unfortunately, there's no 'Macro'
                                      // completion items in LSP.
   case CodeCompletionResult::RK_Pattern:
     return CompletionItemKind::Snippet;
   }
   llvm_unreachable("Unhandled CodeCompletionResult::ResultKind.");
 }
 
+bool isConstructor(const NamedDecl *ND) {
+  if (const auto *Tmpl = dyn_cast<FunctionTemplateDecl>(ND))
+    ND = Tmpl->getTemplatedDecl();
+  return isa<CXXConstructorDecl>(ND);
+}
+
 /// Get the optional chunk as a string. This function is possibly recursive.
 ///
 /// The parameter info for each parameter is appended to the Parameters.
 std::string getOptionalParameters(const CodeCompletionString &CCS,
                                   std::vector<ParameterInformation> &Parameters,
                                   SignatureQualitySignals &Signal) {
   std::string Result;
   for (const auto &Chunk : CCS) {
if (SemaResult && SemaResult->Declaration) {
       auto &SM = SemaResult->Declaration->getASTContext().getSourceManager();
       for (const Decl *RD : SemaResult->Declaration->redecls())
         if (SM.isInMainFile(SM.getExpansionLoc(RD->getBeginLoc())))
           return None;
     }
     return RankedIncludeHeaders[0];
   }
 
+  // Most results can be spammy, so we apply pretty strict matching rules.
+  // A few are always good though, like local variables.
+  bool couldBeSpam() const {
+    if (SemaResult && SemaResult->Declaration) {
+      if (const NamedDecl *ND = dyn_cast<NamedDecl>(SemaResult->Declaration))
+        if (ND->isCXXClassMember() && !SemaResult->InBaseClass &&
+            !isConstructor(ND))
+          return false;
+      if (const VarDecl* VD = dyn_cast<VarDecl>(SemaResult->Declaration))
+        if (VD->isLocalVarDeclOrParm())
+          return false;
+    }
+    return true;
+  }
+
   using Bundle = llvm::SmallVector<CompletionCandidate, 4>;
 };
 using ScoredBundle =
     std::pair<CompletionCandidate::Bundle, CodeCompletion::Scores>;
 struct ScoredBundleGreater {
   bool operator()(const ScoredBundle &L, const ScoredBundle &R) {
     if (L.second.Total != R.second.Total)
       return L.second.Total > R.second.Total;
class CodeCompleteFlow {
   // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
   CompletionRecorder *Recorder = nullptr;
   CodeCompletionContext::Kind CCContextKind = CodeCompletionContext::CCC_Other;
   // Counters for logging.
   int NSema = 0, NIndex = 0, NSemaAndIndex = 0, NIdent = 0;
   bool Incomplete = false; // Would more be available with a higher limit?
   CompletionPrefix HeuristicPrefix;
   llvm::Optional<FuzzyMatcher> Filter;  // Initialized once Sema runs.
+  llvm::Optional<FuzzyMatcher> FilterLax;
   Range ReplacedRange;
   std::vector<std::string> QueryScopes; // Initialized once Sema runs.
   // Initialized once QueryScopes is initialized, if there are scopes.
   llvm::Optional<ScopeDistance> ScopeProximity;
   llvm::Optional<OpaqueType> PreferredType; // Initialized once Sema runs.
   // Whether to query symbols from any scope. Initialized once Sema runs.
   bool AllScopes = false;
   // Include-insertion and proximity scoring rely on the include structure.
CodeCompleteResult runWithSema() {
     } else {
       const auto &Pos = sourceLocToPosition(
           Recorder->CCSema->getSourceManager(),
           Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
       ReplacedRange.start = ReplacedRange.end = Pos;
     }
     Filter = FuzzyMatcher(
         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
+    FilterLax = FuzzyMatcher(Filter->pattern(), FuzzyMatcher::Lax);
     std::tie(QueryScopes, AllScopes) = getQueryScopes(
         Recorder->CCContext, *Recorder->CCSema, HeuristicPrefix, Opts);
     if (!QueryScopes.empty())
       ScopeProximity.emplace(QueryScopes);
     PreferredType =
         OpaqueType::fromType(Recorder->CCSema->getASTContext(),
                              Recorder->CCContext.getPreferredType());
     // Sema provides the needed context to query the index.
private:
   }
 
   llvm::Optional<float> fuzzyScore(const CompletionCandidate &C) {
     // Macros can be very spammy, so we only support prefix completion.
     // We won't end up with underfull index results, as macros are sema-only.
     if (C.SemaResult && C.SemaResult->Kind == CodeCompletionResult::RK_Macro &&
         !C.Name.startswith_lower(Filter->pattern()))
       return None;
+    if (FilterLax && !C.couldBeSpam())
+      return FilterLax->match(C.Name);
     return Filter->match(C.Name);
   }
 
   // Scores a candidate and adds it to the TopN structure.
   void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
                     CompletionCandidate::Bundle Bundle) {
     SymbolQualitySignals Quality;
     SymbolRelevanceSignals Relevance;

clangd/FuzzyMatch.h

 // heuristics for dealing with poorly-segmented identifiers like "strndup".
 CharTypeSet calculateRoles(llvm::StringRef Text,
                            llvm::MutableArrayRef<CharRole> Roles);
 
 // A matcher capable of matching and scoring strings against a single pattern.
 // It's optimized for matching against many strings - match() does not allocate.
 class FuzzyMatcher {
 public:
+  // Controls which matches are accepted (but not how they're scored).
+  enum MatchStyle {
+    Strict, // Word boundaries matter. [pat] matches PartTwo but not PopTart.
+    Lax,    // Case-insensitive substring match. [sv] matches IsEven.
+  };
   // Characters beyond MaxPat are ignored.
-  FuzzyMatcher(llvm::StringRef Pattern);
+  FuzzyMatcher(llvm::StringRef Pattern, MatchStyle Style = Strict);
 
   // If Word matches the pattern, return a score indicating the quality match.
   // Scores usually fall in a [0,1] range, with 1 being a very good score.
   // "Super" scores in (1,2] are possible if the pattern is the full word.
   // Characters beyond MaxWord are ignored.
   llvm::Optional<float> match(llvm::StringRef Word);
 
   llvm::StringRef pattern() const { return llvm::StringRef(Pat, PatN); }
private:
 
   // Pattern data is initialized by the constructor, then constant.
   char Pat[MaxPat];         // Pattern data
   int PatN;                 // Length
   char LowPat[MaxPat];      // Pattern in lowercase
   CharRole PatRole[MaxPat]; // Pattern segmentation info
   CharTypeSet PatTypeSet;   // Bitmask of 1<<CharType for all Pattern characters
   float ScoreScale;         // Normalizes scores for the pattern length.
+  bool StrictMatch;         // Poor substring matches are reject.
 
   // Word data is initialized on each call to match(), mostly by init().
   char Word[MaxWord];         // Word data
   int WordN;                  // Length
   char LowWord[MaxWord];      // Word in lowercase
   CharRole WordRole[MaxWord]; // Word segmentation info
   CharTypeSet WordTypeSet;    // Bitmask of 1<<CharType for all Word characters
   bool WordContainsPattern;   // Simple substring check

clangd/FuzzyMatch.cpp

 static char lower(char C) { return C >= 'A' && C <= 'Z' ? C + ('a' - 'A') : C; }
 // A "negative infinity" score that won't overflow.
 // We use this to mark unreachable states and forbidden solutions.
 // Score field is 15 bits wide, min value is -2^14, we use half of that.
 static constexpr int AwfulScore = -(1 << 13);
 static bool isAwful(int S) { return S < AwfulScore / 2; }
 static constexpr int PerfectBonus = 4; // Perfect per-pattern-char score.
 
-FuzzyMatcher::FuzzyMatcher(llvm::StringRef Pattern)
+FuzzyMatcher::FuzzyMatcher(llvm::StringRef Pattern, MatchStyle Style)
     : PatN(std::min<int>(MaxPat, Pattern.size())),
-      ScoreScale(PatN ? float{1} / (PerfectBonus * PatN) : 0), WordN(0) {
+      ScoreScale(PatN ? float{1} / (PerfectBonus * PatN) : 0),
+      StrictMatch(Style == Strict), WordN(0) {
   std::copy(Pattern.begin(), Pattern.begin() + PatN, Pat);
   for (int I = 0; I < PatN; ++I)
     LowPat[I] = lower(Pat[I]);
   Scores[0][0][Miss] = {0, Miss};
   Scores[0][0][Match] = {AwfulScore, Miss};
   for (int P = 0; P <= PatN; ++P)
     for (int W = 0; W < P; ++W)
       for (Action A : {Miss, Match})

 }
 
 bool FuzzyMatcher::allowMatch(int P, int W, Action Last) const {
   if (LowPat[P] != LowWord[W])
     return false;
   // We require a "strong" match:
   // - for the first pattern character.  [foo] !~ "barefoot"
   // - after a gap.                      [pat] !~ "patnther"
-  if (Last == Miss) {
+  if (StrictMatch && Last == Miss) {
     // We're banning matches outright, so conservatively accept some other cases
     // where our segmentation might be wrong:
     //  - allow matching B in ABCDef (but not in NDEBUG)
     //  - we'd like to accept print in sprintf, but too many false positives
     if (WordRole[W] == Tail &&
         (Word[W] == LowWord[W] || !(WordTypeSet & 1 << Lower)))
       return false;
   }

clangd/unittests/CodeCompleteTests.cpp

TEST(CompletionTest, Filter) {
   EXPECT_THAT(completions(Body + "int main() { S().Foba^ }").Completions,
               AllOf(Has("FooBar"), Has("FooBaz"), Not(Has("Qux"))));
 
   // Macros require  prefix match.
   EXPECT_THAT(completions(Body + "int main() { C^ }").Completions,
               AllOf(Has("Car"), Not(Has("MotorCar"))));
 }
 
+TEST(CompletionTest, FilterStrictLax) {
+  // qry matches "query" in lax mode, but not in strict mode.
+  std::string Body = R"cpp(
+    #define QUERY_MACRO
+    int queryVariable;
+    void queryFunction();
+    struct QueryClass {
+      void queryBaseMethod();
+    };
+    class QueryEnclosingClass : QueryClass {
+      int QueryField = 42;
+      void queryMethod();
+      void queryEnclosingMethod() {
+        int queryLocalVariable;
+        qry^
+      }
+    };
+  )cpp";
+  auto Results = completions(Body).Completions;
+  EXPECT_THAT(Results, Not(Has("QUERY_MACRO")));
+  EXPECT_THAT(Results, Not(Has("queryVariable")));
+  EXPECT_THAT(Results, Not(Has("queryFunction")));
+  EXPECT_THAT(Results, Not(Has("QueryClass")));
+  EXPECT_THAT(Results, Not(Has("queryBaseMethod")));
+  EXPECT_THAT(Results, Not(Has("QueryEnclosingClass")));
+  EXPECT_THAT(Results, Has("QueryField"));
+  EXPECT_THAT(Results, Has("queryMethod"));
+  EXPECT_THAT(Results, Has("queryEnclosingMethod"));
+  EXPECT_THAT(Results, Has("queryLocalVariable"));
+}
+
 void TestAfterDotCompletion(clangd::CodeCompleteOptions Opts) {
   auto Results = completions(
       R"cpp(
       int global_var;
 
       int global_func();
 
       // Make sure this is not in preamble.

clangd/unittests/FuzzyMatchTests.cpp

struct ExpectedMatch {
   std::string Word;
 
 private:
   llvm::Optional<llvm::StringRef> Annotated;
 };
 
 struct MatchesMatcher : public testing::MatcherInterface<llvm::StringRef> {
   ExpectedMatch Candidate;
+  FuzzyMatcher::MatchStyle Style;
   llvm::Optional<float> Score;
-  MatchesMatcher(ExpectedMatch Candidate, llvm::Optional<float> Score)
-      : Candidate(std::move(Candidate)), Score(Score) {}
+  MatchesMatcher(ExpectedMatch Candidate, FuzzyMatcher::MatchStyle Style,
+                 llvm::Optional<float> Score)
+      : Candidate(std::move(Candidate)), Style(Style), Score(Score) {}
 
   void DescribeTo(::std::ostream *OS) const override {
     llvm::raw_os_ostream(*OS) << "Matches " << Candidate;
     if (Score)
       *OS << " with score " << *Score;
   }
 
   bool MatchAndExplain(llvm::StringRef Pattern,
                        testing::MatchResultListener *L) const override {
     std::unique_ptr<llvm::raw_ostream> OS(
         L->stream()
             ? (llvm::raw_ostream *)(new llvm::raw_os_ostream(*L->stream()))
             : new llvm::raw_null_ostream());
-    FuzzyMatcher Matcher(Pattern);
+    FuzzyMatcher Matcher(Pattern, Style);
     auto Result = Matcher.match(Candidate.Word);
     auto AnnotatedMatch = Matcher.dumpLast(*OS << "\n");
     return Result && Candidate.accepts(AnnotatedMatch) &&
            (!Score || testing::Value(*Result, testing::FloatEq(*Score)));
   }
 };
 
 // Accepts patterns that match a given word, optionally requiring a score.
 // Dumps the debug tables on match failure.
-testing::Matcher<llvm::StringRef> matches(llvm::StringRef M,
-                                          llvm::Optional<float> Score = {}) {
-  return testing::MakeMatcher<llvm::StringRef>(new MatchesMatcher(M, Score));
+testing::Matcher<llvm::StringRef>
+matches(llvm::StringRef M,
+        FuzzyMatcher::MatchStyle Style = FuzzyMatcher::Strict,
+  return testing::MakeMatcher<llvm::StringRef>(
+      new MatchesMatcher(M, Style, Score));
 }
 
 TEST(FuzzyMatch, Matches) {
   EXPECT_THAT("", matches("unique_ptr"));
   EXPECT_THAT("u_p", matches("[u]nique[_p]tr"));
   EXPECT_THAT("up", matches("[u]nique_[p]tr"));
   EXPECT_THAT("uq", Not(matches("unique_ptr")));
   EXPECT_THAT("qp", Not(matches("unique_ptr")));
TEST(FuzzyMatch, Matches) {
   // These would ideally match, but would need special segmentation rules.
   EXPECT_THAT("printf", Not(matches("s[printf]")));
   EXPECT_THAT("str", Not(matches("o[str]eam")));
   EXPECT_THAT("strcpy", Not(matches("strncpy")));
   EXPECT_THAT("std", Not(matches("PTHREAD_MUTEX_STALLED")));
   EXPECT_THAT("std", Not(matches("pthread_condattr_setpshared")));
 }
 
+TEST(FuzzyMatch, MatchesLax) {
+  EXPECT_THAT("", matches("unique_ptr", FuzzyMatcher::Lax));
+  EXPECT_THAT("u_p", matches("[u]nique[_p]tr", FuzzyMatcher::Lax));
+  EXPECT_THAT("up", matches("[u]nique_[p]tr", FuzzyMatcher::Lax));
+  EXPECT_THAT("uq", matches("[u]ni[q]ue_ptr", FuzzyMatcher::Lax));
+  EXPECT_THAT("qp", matches("uni[q]ue_[p]tr", FuzzyMatcher::Lax));
+  EXPECT_THAT("log", matches("SVGFEMorpho[log]yElement", FuzzyMatcher::Lax));
+}
+
 struct RankMatcher : public testing::MatcherInterface<llvm::StringRef> {
   std::vector<ExpectedMatch> RankedStrings;
   RankMatcher(std::initializer_list<ExpectedMatch> RankedStrings)
       : RankedStrings(RankedStrings) {}
 
   void DescribeTo(::std::ostream *OS) const override {
     llvm::raw_os_ostream O(*OS);
     O << "Ranks strings in order: [";
EXPECT_THAT("convertModelPosition",
                     "[convert]ViewTo[ModelPosition]"));
   EXPECT_THAT("is", ranks("[is]ValidViewletId", "[i]mport [s]tatement"));
   EXPECT_THAT("strcpy", ranks("[strcpy]", "[strcpy]_s"));
 }
 
 // Verify some bounds so we know scores fall in the right range.
 // Testing exact scores is fragile, so we prefer Ranking tests.
 TEST(FuzzyMatch, Scoring) {
-  EXPECT_THAT("abs", matches("[a]w[B]xYz[S]", 7.f / 12.f));
-  EXPECT_THAT("abs", matches("[abs]l", 1.f));
-  EXPECT_THAT("abs", matches("[abs]", 2.f));
-  EXPECT_THAT("Abs", matches("[abs]", 2.f));
+  EXPECT_THAT("abs",
+              matches("[a]w[B]xYz[S]", FuzzyMatcher::Strict, 7.f / 12.f));
+  EXPECT_THAT("abs", matches("[abs]l", FuzzyMatcher::Strict, 1.f));
+  EXPECT_THAT("abs", matches("[abs]", FuzzyMatcher::Strict, 2.f));
+  EXPECT_THAT("Abs", matches("[abs]", FuzzyMatcher::Strict, 2.f));
 }
 
 TEST(FuzzyMatch, InitialismAndPrefix) {
   // We want these scores to be roughly the same.
-  EXPECT_THAT("up", matches("[u]nique_[p]tr", 3.f / 4.f));
-  EXPECT_THAT("up", matches("[up]per_bound", 1.f));
+  EXPECT_THAT("up", matches("[u]nique_[p]tr", FuzzyMatcher::Strict, 3.f / 4.f));
+  EXPECT_THAT("up", matches("[up]per_bound", FuzzyMatcher::Strict, 1.f));
 }
 
 // Returns pretty-printed segmentation of Text.
 // e.g. std::basic_string --> +--  +---- +-----
 std::string segment(llvm::StringRef Text) {
   std::vector<CharRole> Roles(Text.size());
   calculateRoles(Text, Roles);
   std::string Printed;