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