Index: clang-tools-extra/trunk/clangd/FuzzyMatch.h =================================================================== --- clang-tools-extra/trunk/clangd/FuzzyMatch.h +++ clang-tools-extra/trunk/clangd/FuzzyMatch.h @@ -50,16 +50,18 @@ constexpr static int MaxPat = 63, MaxWord = 127; enum CharRole : unsigned char; // For segmentation. enum CharType : unsigned char; // For segmentation. - // Action should be an enum, but this causes bitfield problems: + // Action describes how a word character was matched to the pattern. + // It should be an enum, but this causes bitfield problems: // - for MSVC the enum type must be explicitly unsigned for correctness // - GCC 4.8 complains not all values fit if the type is unsigned using Action = bool; - constexpr static Action Miss = false, Match = true; + constexpr static Action Miss = false; // Word character was skipped. + constexpr static Action Match = true; // Matched against a pattern character. bool init(llvm::StringRef Word); void buildGraph(); void calculateRoles(const char *Text, CharRole *Out, int &Types, int N); - bool allowMatch(int P, int W) const; + bool allowMatch(int P, int W, Action Last) const; int skipPenalty(int W, Action Last) const; int matchBonus(int P, int W, Action Last) const; @@ -68,7 +70,7 @@ int PatN; // Length char LowPat[MaxPat]; // Pattern in lowercase CharRole PatRole[MaxPat]; // Pattern segmentation info - int PatTypeSet; // Bitmask of 1< MissMatchScore) - ? ScoreInfo{MatchMatchScore, Match} - : ScoreInfo{MissMatchScore, Miss}; - } + auto &PreMatch = Scores[P][W]; + auto MatchMatchScore = + allowMatch(P, W, Match) + ? PreMatch[Match].Score + matchBonus(P, W, Match) + : AwfulScore; + auto MissMatchScore = allowMatch(P, W, Miss) + ? PreMatch[Miss].Score + matchBonus(P, W, Miss) + : AwfulScore; + Score[Match] = (MatchMatchScore > MissMatchScore) + ? ScoreInfo{MatchMatchScore, Match} + : ScoreInfo{MissMatchScore, Miss}; } } } -bool FuzzyMatcher::allowMatch(int P, int W) const { +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 only. - if (P > 0) - return true; - // Obvious "strong match" for first char: match against a word head. - // 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 - return WordRole[W] != Tail || - (Word[W] != LowWord[W] && WordTypeSet & 1 << Lower); + // We require a "strong" match: + // - for the first pattern character. [foo] !~ "barefoot" + // - after a gap. [pat] !~ "patnther" + if (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; + } + return true; } int FuzzyMatcher::skipPenalty(int W, Action Last) const { Index: clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp @@ -193,27 +193,22 @@ TEST(CompletionTest, Filter) { std::string Body = R"cpp( - #define FooBarMacro - int Abracadabra; - int Alakazam; + #define MotorCar + int Car; struct S { int FooBar; int FooBaz; int Qux; }; )cpp"; - EXPECT_THAT(completions(Body + "int main() { S().Foba^ }").items, - AllOf(Has("FooBar"), Has("FooBaz"), Not(Has("FooBarMacro")), - Not(Has("Qux")))); - - EXPECT_THAT(completions(Body + "int main() { S().FR^ }").items, - AllOf(Has("FooBar"), Not(Has("FooBaz")), Not(Has("Qux")))); - EXPECT_THAT(completions(Body + "int main() { aaa^ }").items, - AllOf(Has("Abracadabra"), Has("Alakazam"))); + // Only items matching the fuzzy query are returned. + EXPECT_THAT(completions(Body + "int main() { S().Foba^ }").items, + AllOf(Has("FooBar"), Has("FooBaz"), Not(Has("Qux")))); - EXPECT_THAT(completions(Body + "int main() { _a^ }").items, - AllOf(Has("static_cast"), Not(Has("Abracadabra")))); + // Macros require prefix match. + EXPECT_THAT(completions(Body + "int main() { C^ }").items, + AllOf(Has("Car"), Not(Has("MotorCar")))); } void TestAfterDotCompletion(clangd::CodeCompleteOptions Opts) { @@ -461,21 +456,21 @@ TEST(CompletionTest, ScopedNoIndex) { auto Results = completions( R"cpp( - namespace fake { int BigBang, Babble, Ball; }; - int main() { fake::bb^ } + namespace fake { int BigBang, Babble, Box; }; + int main() { fake::ba^ } ")cpp"); - // BigBang is a better match than Babble. Ball doesn't match at all. - EXPECT_THAT(Results.items, ElementsAre(Named("BigBang"), Named("Babble"))); + // Babble is a better match than BigBang. Box doesn't match at all. + EXPECT_THAT(Results.items, ElementsAre(Named("Babble"), Named("BigBang"))); } TEST(CompletionTest, Scoped) { auto Results = completions( R"cpp( - namespace fake { int Babble, Ball; }; - int main() { fake::bb^ } + namespace fake { int Babble, Box; }; + int main() { fake::ba^ } ")cpp", {var("fake::BigBang")}); - EXPECT_THAT(Results.items, ElementsAre(Named("BigBang"), Named("Babble"))); + EXPECT_THAT(Results.items, ElementsAre(Named("Babble"), Named("BigBang"))); } TEST(CompletionTest, ScopedWithFilter) { Index: clang-tools-extra/trunk/unittests/clangd/FuzzyMatchTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/FuzzyMatchTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/FuzzyMatchTests.cpp @@ -79,7 +79,7 @@ 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", matches("[u]ni[q]ue_ptr")); + EXPECT_THAT("uq", Not(matches("unique_ptr"))); EXPECT_THAT("qp", Not(matches("unique_ptr"))); EXPECT_THAT("log", Not(matches("SVGFEMorphologyElement"))); @@ -99,7 +99,7 @@ EXPECT_THAT("moza", matches("-[moz]-[a]nimation")); EXPECT_THAT("ab", matches("[ab]A")); - EXPECT_THAT("ccm", matches("[c]a[cm]elCase")); + EXPECT_THAT("ccm", Not(matches("cacmelCase"))); EXPECT_THAT("bti", Not(matches("the_black_knight"))); EXPECT_THAT("ccm", Not(matches("camelCase"))); EXPECT_THAT("cmcm", Not(matches("camelCase"))); @@ -110,17 +110,17 @@ EXPECT_THAT("LLLL", Not(matches("SVisualLoggerLogsList"))); EXPECT_THAT("TEdit", matches("[T]ext[Edit]")); EXPECT_THAT("TEdit", matches("[T]ext[Edit]or")); - EXPECT_THAT("TEdit", matches("[Te]xte[dit]")); + EXPECT_THAT("TEdit", Not(matches("[T]ext[edit]"))); EXPECT_THAT("TEdit", matches("[t]ext_[edit]")); - EXPECT_THAT("TEditDit", matches("[T]ext[Edit]or[D]ecorat[i]on[T]ype")); + EXPECT_THAT("TEditDt", matches("[T]ext[Edit]or[D]ecoration[T]ype")); EXPECT_THAT("TEdit", matches("[T]ext[Edit]orDecorationType")); EXPECT_THAT("Tedit", matches("[T]ext[Edit]")); EXPECT_THAT("ba", Not(matches("?AB?"))); EXPECT_THAT("bkn", matches("the_[b]lack_[kn]ight")); - EXPECT_THAT("bt", matches("the_[b]lack_knigh[t]")); - EXPECT_THAT("ccm", matches("[c]amelCase[cm]")); - EXPECT_THAT("fdm", matches("[f]in[dM]odel")); - EXPECT_THAT("fob", matches("[fo]o[b]ar")); + EXPECT_THAT("bt", Not(matches("the_[b]lack_knigh[t]"))); + EXPECT_THAT("ccm", Not(matches("[c]amelCase[cm]"))); + EXPECT_THAT("fdm", Not(matches("[f]in[dM]odel"))); + EXPECT_THAT("fob", Not(matches("[fo]o[b]ar"))); EXPECT_THAT("fobz", Not(matches("foobar"))); EXPECT_THAT("foobar", matches("[foobar]")); EXPECT_THAT("form", matches("editor.[form]atOnSave")); @@ -132,14 +132,14 @@ EXPECT_THAT("gp", matches("[G]it_Git_[P]ull")); EXPECT_THAT("is", matches("[I]mport[S]tatement")); EXPECT_THAT("is", matches("[is]Valid")); - EXPECT_THAT("lowrd", matches("[low]Wo[rd]")); - EXPECT_THAT("myvable", matches("[myva]ria[ble]")); + EXPECT_THAT("lowrd", Not(matches("[low]Wo[rd]"))); + EXPECT_THAT("myvable", Not(matches("[myva]ria[ble]"))); EXPECT_THAT("no", Not(matches(""))); EXPECT_THAT("no", Not(matches("match"))); EXPECT_THAT("ob", Not(matches("foobar"))); EXPECT_THAT("sl", matches("[S]Visual[L]oggerLogsList")); - EXPECT_THAT("sllll", matches("[S]Visua[lL]ogger[L]ogs[L]ist")); - EXPECT_THAT("Three", matches("H[T]ML[HRE]l[e]ment")); + EXPECT_THAT("sllll", matches("[S]Visua[L]ogger[Ll]ama[L]ist")); + EXPECT_THAT("THRE", matches("H[T]ML[HRE]lement")); EXPECT_THAT("b", Not(matches("NDEBUG"))); EXPECT_THAT("Three", matches("[Three]")); EXPECT_THAT("fo", Not(matches("barfoo"))); @@ -173,6 +173,9 @@ // 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"))); } struct RankMatcher : public testing::MatcherInterface { @@ -236,12 +239,11 @@ } TEST(FuzzyMatch, Ranking) { - EXPECT_THAT("eb", ranks("[e]mplace_[b]ack", "[e]m[b]ed")); EXPECT_THAT("cons", ranks("[cons]ole", "[Cons]ole", "ArrayBuffer[Cons]tructor")); EXPECT_THAT("foo", ranks("[foo]", "[Foo]")); - EXPECT_THAT("onMess", - ranks("[onMess]age", "[onmess]age", "[on]This[M]ega[Es]cape[s]")); + EXPECT_THAT("onMes", + ranks("[onMes]sage", "[onmes]sage", "[on]This[M]ega[Es]capes")); EXPECT_THAT("CC", ranks("[C]amel[C]ase", "[c]amel[C]ase")); EXPECT_THAT("cC", ranks("[c]amel[C]ase", "[C]amel[C]ase")); EXPECT_THAT("p", ranks("[p]", "[p]arse", "[p]osix", "[p]afdsa", "[p]ath")); @@ -259,18 +261,13 @@ ranks("[convertModelPosition]ToViewPosition", "[convert]ViewTo[ModelPosition]")); EXPECT_THAT("is", ranks("[is]ValidViewletId", "[i]mport [s]tatement")); - EXPECT_THAT("title", ranks("window.[title]", - "files.[t]r[i]m[T]rai[l]ingWhit[e]space")); - EXPECT_THAT("strcpy", ranks("[strcpy]", "[strcpy]_s", "[str]n[cpy]")); - EXPECT_THAT("close", ranks("workbench.quickOpen.[close]OnFocusOut", - "[c]ss.[l]int.imp[o]rt[S]tat[e]ment", - "[c]ss.co[lo]rDecorator[s].[e]nable")); + 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]x[b]y[s]z", 0.f)); + EXPECT_THAT("abs", matches("[a]w[B]xYz[S]", 0.f)); EXPECT_THAT("abs", matches("[abs]l", 1.f)); EXPECT_THAT("abs", matches("[abs]", 2.f)); EXPECT_THAT("Abs", matches("[abs]", 2.f));