313 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "FuzzyMatch.h"10 11#include "gmock/gmock.h"12#include "gtest/gtest.h"13#include <optional>14 15namespace clang {16namespace clangd {17namespace {18using ::testing::Not;19 20struct ExpectedMatch {21 // Annotations are optional, and will not be asserted if absent.22 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 = std::nullopt;27 }28 bool accepts(llvm::StringRef ActualAnnotated) const {29 return !Annotated || ActualAnnotated == *Annotated;30 }31 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 42private:43 std::optional<llvm::StringRef> Annotated;44};45 46struct MatchesMatcher : public ::testing::MatcherInterface<llvm::StringRef> {47 ExpectedMatch Candidate;48 std::optional<float> Score;49 MatchesMatcher(ExpectedMatch Candidate, std::optional<float> Score)50 : Candidate(std::move(Candidate)), Score(Score) {}51 52 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 58 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.74::testing::Matcher<llvm::StringRef> matches(llvm::StringRef M,75 std::optional<float> Score = {}) {76 return ::testing::MakeMatcher<llvm::StringRef>(new MatchesMatcher(M, Score));77}78 79TEST(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 182struct RankMatcher : public ::testing::MatcherInterface<llvm::StringRef> {183 std::vector<ExpectedMatch> RankedStrings;184 RankMatcher(std::initializer_list<ExpectedMatch> RankedStrings)185 : RankedStrings(RankedStrings) {}186 187 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 195 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 std::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.238template <typename... T>239::testing::Matcher<llvm::StringRef> ranks(T... RankedStrings) {240 return ::testing::MakeMatcher<llvm::StringRef>(241 new RankMatcher{ExpectedMatch(RankedStrings)...});242}243 244TEST(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.274TEST(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 281TEST(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 --> +-- +---- +-----289std::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.299std::string returns(llvm::StringRef Text) { return std::string(Text); }300 301TEST(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} // namespace311} // namespace clangd312} // namespace clang313