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

   1 //===-- FuzzyMatchTests.cpp - String fuzzy matcher tests --------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "FuzzyMatch.h"
  10
  11 #include "gmock/gmock.h"
  12 #include "gtest/gtest.h"
  13
  14 namespace clang {
  15 namespace clangd {
  16 namespace {
  17 using ::testing::Not;
  18
  19 struct ExpectedMatch {
  20   // Annotations are optional, and will not be asserted if absent.
  21   ExpectedMatch(llvm::StringRef Match) : Word(Match), Annotated(Match) {
  22     for (char C : "[]")
  23       Word.erase(std::remove(Word.begin(), Word.end(), C), Word.end());
  24     if (Word.size() == Annotated->size())
  25       Annotated = llvm::None;
  26   }
  27   bool accepts(llvm::StringRef ActualAnnotated) const {
  28     return !Annotated || ActualAnnotated == *Annotated;
  29   }
  30
  31   friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
  32                                        const ExpectedMatch &M) {
  33     OS << "'" << M.Word;
  34     if (M.Annotated)
  35       OS << "' as " << *M.Annotated;
  36     return OS;
  37   }
  38
  39   std::string Word;
  40
  41 private:
  42   llvm::Optional<llvm::StringRef> Annotated;
  43 };
  44
  45 struct MatchesMatcher : public ::testing::MatcherInterface<llvm::StringRef> {
  46   ExpectedMatch Candidate;
  47   llvm::Optional<float> Score;
  48   MatchesMatcher(ExpectedMatch Candidate, llvm::Optional<float> Score)
  49       : Candidate(std::move(Candidate)), Score(Score) {}
  50
  51   void DescribeTo(::std::ostream *OS) const override {
  52     llvm::raw_os_ostream(*OS) << "Matches " << Candidate;
  53     if (Score)
  54       *OS << " with score " << *Score;
  55   }
  56
  57   bool MatchAndExplain(llvm::StringRef Pattern,
  58                        ::testing::MatchResultListener *L) const override {
  59     std::unique_ptr<llvm::raw_ostream> OS(
  60         L->stream()
  61             ? (llvm::raw_ostream *)(new llvm::raw_os_ostream(*L->stream()))
  62             : new llvm::raw_null_ostream());
  63     FuzzyMatcher Matcher(Pattern);
  64     auto Result = Matcher.match(Candidate.Word);
  65     auto AnnotatedMatch = Matcher.dumpLast(*OS << "\n");
  66     return Result && Candidate.accepts(AnnotatedMatch) &&
  67            (!Score || ::testing::Value(*Result, ::testing::FloatEq(*Score)));
  68   }
  69 };
  70
  71 // Accepts patterns that match a given word, optionally requiring a score.
  72 // Dumps the debug tables on match failure.
  73 ::testing::Matcher<llvm::StringRef> matches(llvm::StringRef M,
  74                                             llvm::Optional<float> Score = {}) {
  75   return ::testing::MakeMatcher<llvm::StringRef>(new MatchesMatcher(M, Score));
  76 }
  77
  78 TEST(FuzzyMatch, Matches) {
  79   EXPECT_THAT("", matches("unique_ptr"));
  80   EXPECT_THAT("u_p", matches("[u]nique[_p]tr"));
  81   EXPECT_THAT("up", matches("[u]nique_[p]tr"));
  82   EXPECT_THAT("uq", Not(matches("unique_ptr")));
  83   EXPECT_THAT("qp", Not(matches("unique_ptr")));
  84   EXPECT_THAT("log", Not(matches("SVGFEMorphologyElement")));
  85
  86   EXPECT_THAT("tit", matches("win.[tit]"));
  87   EXPECT_THAT("title", matches("win.[title]"));
  88   EXPECT_THAT("WordCla", matches("[Word]Character[Cla]ssifier"));
  89   EXPECT_THAT("WordCCla", matches("[WordC]haracter[Cla]ssifier"));
  90
  91   EXPECT_THAT("dete", Not(matches("editor.quickSuggestionsDelay")));
  92
  93   EXPECT_THAT("highlight", matches("editorHover[Highlight]"));
  94   EXPECT_THAT("hhighlight", matches("editor[H]over[Highlight]"));
  95   EXPECT_THAT("dhhighlight", Not(matches("editorHoverHighlight")));
  96
  97   EXPECT_THAT("-moz", matches("[-moz]-foo"));
  98   EXPECT_THAT("moz", matches("-[moz]-foo"));
  99   EXPECT_THAT("moza", matches("-[moz]-[a]nimation"));
 100
 101   EXPECT_THAT("ab", matches("[ab]A"));
 102   EXPECT_THAT("ccm", Not(matches("cacmelCase")));
 103   EXPECT_THAT("bti", Not(matches("the_black_knight")));
 104   EXPECT_THAT("ccm", Not(matches("camelCase")));
 105   EXPECT_THAT("cmcm", Not(matches("camelCase")));
 106   EXPECT_THAT("BK", matches("the_[b]lack_[k]night"));
 107   EXPECT_THAT("KeyboardLayout=", Not(matches("KeyboardLayout")));
 108   EXPECT_THAT("LLL", matches("SVisual[L]ogger[L]ogs[L]ist"));
 109   EXPECT_THAT("LLLL", Not(matches("SVilLoLosLi")));
 110   EXPECT_THAT("LLLL", Not(matches("SVisualLoggerLogsList")));
 111   EXPECT_THAT("TEdit", matches("[T]ext[Edit]"));
 112   EXPECT_THAT("TEdit", matches("[T]ext[Edit]or"));
 113   EXPECT_THAT("TEdit", Not(matches("[T]ext[edit]")));
 114   EXPECT_THAT("TEdit", matches("[t]ext_[edit]"));
 115   EXPECT_THAT("TEditDt", matches("[T]ext[Edit]or[D]ecoration[T]ype"));
 116   EXPECT_THAT("TEdit", matches("[T]ext[Edit]orDecorationType"));
 117   EXPECT_THAT("Tedit", matches("[T]ext[Edit]"));
 118   EXPECT_THAT("ba", Not(matches("?AB?")));
 119   EXPECT_THAT("bkn", matches("the_[b]lack_[kn]ight"));
 120   EXPECT_THAT("bt", Not(matches("the_[b]lack_knigh[t]")));
 121   EXPECT_THAT("ccm", Not(matches("[c]amelCase[cm]")));
 122   EXPECT_THAT("fdm", Not(matches("[f]in[dM]odel")));
 123   EXPECT_THAT("fob", Not(matches("[fo]o[b]ar")));
 124   EXPECT_THAT("fobz", Not(matches("foobar")));
 125   EXPECT_THAT("foobar", matches("[foobar]"));
 126   EXPECT_THAT("form", matches("editor.[form]atOnSave"));
 127   EXPECT_THAT("g p", matches("[G]it:[ P]ull"));
 128   EXPECT_THAT("g p", matches("[G]it:[ P]ull"));
 129   EXPECT_THAT("gip", matches("[Gi]t: [P]ull"));
 130   EXPECT_THAT("gip", matches("[Gi]t: [P]ull"));
 131   EXPECT_THAT("gp", matches("[G]it: [P]ull"));
 132   EXPECT_THAT("gp", matches("[G]it_Git_[P]ull"));
 133   EXPECT_THAT("is", matches("[I]mport[S]tatement"));
 134   EXPECT_THAT("is", matches("[is]Valid"));
 135   EXPECT_THAT("lowrd", Not(matches("[low]Wo[rd]")));
 136   EXPECT_THAT("myvable", Not(matches("[myva]ria[ble]")));
 137   EXPECT_THAT("no", Not(matches("")));
 138   EXPECT_THAT("no", Not(matches("match")));
 139   EXPECT_THAT("ob", Not(matches("foobar")));
 140   EXPECT_THAT("sl", matches("[S]Visual[L]oggerLogsList"));
 141   EXPECT_THAT("sllll", matches("[S]Visua[L]ogger[Ll]ama[L]ist"));
 142   EXPECT_THAT("THRE", matches("H[T]ML[HRE]lement"));
 143   EXPECT_THAT("b", Not(matches("NDEBUG")));
 144   EXPECT_THAT("Three", matches("[Three]"));
 145   EXPECT_THAT("fo", Not(matches("barfoo")));
 146   EXPECT_THAT("fo", matches("bar_[fo]o"));
 147   EXPECT_THAT("fo", matches("bar_[Fo]o"));
 148   EXPECT_THAT("fo", matches("bar [fo]o"));
 149   EXPECT_THAT("fo", matches("bar.[fo]o"));
 150   EXPECT_THAT("fo", matches("bar/[fo]o"));
 151   EXPECT_THAT("fo", matches("bar\\[fo]o"));
 152
 153   EXPECT_THAT(
 154       "aaaaaa",
 155       matches("[aaaaaa]aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
 156               "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
 157   EXPECT_THAT("baba", Not(matches("ababababab")));
 158   EXPECT_THAT("fsfsfs", Not(matches("dsafdsafdsafdsafdsafdsafdsafasdfdsa")));
 159   EXPECT_THAT("fsfsfsfsfsfsfsf",
 160               Not(matches("dsafdsafdsafdsafdsafdsafdsafasdfdsafdsafdsafdsafdsfd"
 161                           "safdsfdfdfasdnfdsajfndsjnafjndsajlknfdsa")));
 162
 163   EXPECT_THAT("  g", matches("[  g]roup"));
 164   EXPECT_THAT("g", matches("  [g]roup"));
 165   EXPECT_THAT("g g", Not(matches("  groupGroup")));
 166   EXPECT_THAT("g g", matches("  [g]roup[ G]roup"));
 167   EXPECT_THAT(" g g", matches("[ ] [g]roup[ G]roup"));
 168   EXPECT_THAT("zz", matches("[zz]Group"));
 169   EXPECT_THAT("zzg", matches("[zzG]roup"));
 170   EXPECT_THAT("g", matches("zz[G]roup"));
 171
 172   EXPECT_THAT("aaaa", matches("_a_[aaaa]")); // Prefer consecutive.
 173   // These would ideally match, but would need special segmentation rules.
 174   EXPECT_THAT("printf", Not(matches("s[printf]")));
 175   EXPECT_THAT("str", Not(matches("o[str]eam")));
 176   EXPECT_THAT("strcpy", Not(matches("strncpy")));
 177   EXPECT_THAT("std", Not(matches("PTHREAD_MUTEX_STALLED")));
 178   EXPECT_THAT("std", Not(matches("pthread_condattr_setpshared")));
 179 }
 180
 181 struct RankMatcher : public ::testing::MatcherInterface<llvm::StringRef> {
 182   std::vector<ExpectedMatch> RankedStrings;
 183   RankMatcher(std::initializer_list<ExpectedMatch> RankedStrings)
 184       : RankedStrings(RankedStrings) {}
 185
 186   void DescribeTo(::std::ostream *OS) const override {
 187     llvm::raw_os_ostream O(*OS);
 188     O << "Ranks strings in order: [";
 189     for (const auto &Str : RankedStrings)
 190       O << "\n\t" << Str;
 191     O << "\n]";
 192   }
 193
 194   bool MatchAndExplain(llvm::StringRef Pattern,
 195                        ::testing::MatchResultListener *L) const override {
 196     std::unique_ptr<llvm::raw_ostream> OS(
 197         L->stream()
 198             ? (llvm::raw_ostream *)(new llvm::raw_os_ostream(*L->stream()))
 199             : new llvm::raw_null_ostream());
 200     FuzzyMatcher Matcher(Pattern);
 201     const ExpectedMatch *LastMatch;
 202     llvm::Optional<float> LastScore;
 203     bool Ok = true;
 204     for (const auto &Str : RankedStrings) {
 205       auto Score = Matcher.match(Str.Word);
 206       if (!Score) {
 207         *OS << "\nDoesn't match '" << Str.Word << "'";
 208         Matcher.dumpLast(*OS << "\n");
 209         Ok = false;
 210       } else {
 211         std::string Buf;
 212         llvm::raw_string_ostream Info(Buf);
 213         auto AnnotatedMatch = Matcher.dumpLast(Info);
 214
 215         if (!Str.accepts(AnnotatedMatch)) {
 216           *OS << "\nDoesn't match " << Str << ", but " << AnnotatedMatch << "\n"
 217               << Info.str();
 218           Ok = false;
 219         } else if (LastScore && *LastScore < *Score) {
 220           *OS << "\nRanks '" << Str.Word << "'=" << *Score << " above '"
 221               << LastMatch->Word << "'=" << *LastScore << "\n"
 222               << Info.str();
 223           Matcher.match(LastMatch->Word);
 224           Matcher.dumpLast(*OS << "\n");
 225           Ok = false;
 226         }
 227       }
 228       LastMatch = &Str;
 229       LastScore = Score;
 230     }
 231     return Ok;
 232   }
 233 };
 234
 235 // Accepts patterns that match all the strings and rank them in the given order.
 236 // Dumps the debug tables on match failure.
 237 template <typename... T>
 238 ::testing::Matcher<llvm::StringRef> ranks(T... RankedStrings) {
 239   return ::testing::MakeMatcher<llvm::StringRef>(
 240       new RankMatcher{ExpectedMatch(RankedStrings)...});
 241 }
 242
 243 TEST(FuzzyMatch, Ranking) {
 244   EXPECT_THAT("cons",
 245               ranks("[cons]ole", "[Cons]ole", "ArrayBuffer[Cons]tructor"));
 246   EXPECT_THAT("foo", ranks("[foo]", "[Foo]"));
 247   EXPECT_THAT("onMes",
 248               ranks("[onMes]sage", "[onmes]sage", "[on]This[M]ega[Es]capes"));
 249   EXPECT_THAT("onmes",
 250               ranks("[onmes]sage", "[onMes]sage", "[on]This[M]ega[Es]capes"));
 251   EXPECT_THAT("CC", ranks("[C]amel[C]ase", "[c]amel[C]ase"));
 252   EXPECT_THAT("cC", ranks("[c]amel[C]ase", "[C]amel[C]ase"));
 253   EXPECT_THAT("p", ranks("[p]", "[p]arse", "[p]osix", "[p]afdsa", "[p]ath"));
 254   EXPECT_THAT("pa", ranks("[pa]rse", "[pa]th", "[pa]fdsa"));
 255   EXPECT_THAT("log", ranks("[log]", "Scroll[Log]icalPosition"));
 256   EXPECT_THAT("e", ranks("[e]lse", "Abstract[E]lement"));
 257   EXPECT_THAT("workbench.sideb",
 258               ranks("[workbench.sideB]ar.location",
 259                     "[workbench.]editor.default[SideB]ySideLayout"));
 260   EXPECT_THAT("editor.r", ranks("[editor.r]enderControlCharacter",
 261                                 "[editor.]overview[R]ulerlanes",
 262                                 "diff[Editor.r]enderSideBySide"));
 263   EXPECT_THAT("-mo", ranks("[-mo]z-columns", "[-]ms-ime-[mo]de"));
 264   EXPECT_THAT("convertModelPosition",
 265               ranks("[convertModelPosition]ToViewPosition",
 266                     "[convert]ViewTo[ModelPosition]"));
 267   EXPECT_THAT("is", ranks("[is]ValidViewletId", "[i]mport [s]tatement"));
 268   EXPECT_THAT("strcpy", ranks("[strcpy]", "[strcpy]_s"));
 269 }
 270
 271 // Verify some bounds so we know scores fall in the right range.
 272 // Testing exact scores is fragile, so we prefer Ranking tests.
 273 TEST(FuzzyMatch, Scoring) {
 274   EXPECT_THAT("abs", matches("[a]w[B]xYz[S]", 7.f / 12.f));
 275   EXPECT_THAT("abs", matches("[abs]l", 1.f));
 276   EXPECT_THAT("abs", matches("[abs]", 2.f));
 277   EXPECT_THAT("Abs", matches("[abs]", 2.f));
 278 }
 279
 280 TEST(FuzzyMatch, InitialismAndPrefix) {
 281   // We want these scores to be roughly the same.
 282   EXPECT_THAT("up", matches("[u]nique_[p]tr", 3.f / 4.f));
 283   EXPECT_THAT("up", matches("[up]per_bound", 1.f));
 284 }
 285
 286 // Returns pretty-printed segmentation of Text.
 287 // e.g. std::basic_string --> +--  +---- +-----
 288 std::string segment(llvm::StringRef Text) {
 289   std::vector<CharRole> Roles(Text.size());
 290   calculateRoles(Text, Roles);
 291   std::string Printed;
 292   for (unsigned I = 0; I < Text.size(); ++I)
 293     Printed.push_back("?-+ "[static_cast<unsigned>(Roles[I])]);
 294   return Printed;
 295 }
 296
 297 // this is a no-op hack so clang-format will vertically align our testcases.
 298 std::string returns(llvm::StringRef Text) { return std::string(Text); }
 299
 300 TEST(FuzzyMatch, Segmentation) {
 301   EXPECT_THAT(segment("std::basic_string"), //
 302               returns("+--  +---- +-----"));
 303   EXPECT_THAT(segment("XMLHttpRequest"), //
 304               returns("+--+---+------"));
 305   EXPECT_THAT(segment("t3h PeNgU1N oF d00m!!!!!!!!"), //
 306               returns("+-- +-+-+-+ ++ +---        "));
 307 }
 308
 309 } // namespace
 310 } // namespace clangd
 311 } // namespace clang