clang-tools  16.0.0git
FuzzyMatchTests.cpp
Go to the documentation of this file.
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)
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
RankedStrings
std::vector< ExpectedMatch > RankedStrings
Definition: FuzzyMatchTests.cpp:182
clang::clangd::TEST
TEST(BackgroundQueueTest, Priority)
Definition: BackgroundIndexTests.cpp:750
clang::clangd::calculateRoles
CharTypeSet calculateRoles(llvm::StringRef Text, llvm::MutableArrayRef< CharRole > Roles)
Definition: FuzzyMatch.cpp:154
Text
std::string Text
Definition: HTMLGenerator.cpp:80
M
const google::protobuf::Message & M
Definition: Server.cpp:309
FuzzyMatch.h
clang::clangd::operator<<
llvm::raw_ostream & operator<<(llvm::raw_ostream &OS, const CodeCompletion &C)
Definition: CodeComplete.cpp:2200
Word
std::string Word
Definition: FuzzyMatchTests.cpp:39
Info
FunctionInfo Info
Definition: FunctionSizeCheck.cpp:121
Score
llvm::Optional< float > Score
Definition: FuzzyMatchTests.cpp:47
Candidate
ExpectedMatch Candidate
Definition: FuzzyMatchTests.cpp:46
C
const Criteria C
Definition: FunctionCognitiveComplexityCheck.cpp:93
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
OS
llvm::raw_string_ostream OS
Definition: TraceTests.cpp:160
Value
static constexpr bool Value
Definition: SuspiciousCallArgumentCheck.cpp:72