MaskRay updated this revision to Diff 139314.
MaskRay edited the summary of this revision.
MaskRay added a comment.
Update summary
Repository:
rCTE Clang Tools Extra
https://reviews.llvm.org/D44720
Files:
clangd/FuzzyMatch.cpp
clangd/FuzzyMatch.h
Index: clangd/FuzzyMatch.h
===================================================================
--- clangd/FuzzyMatch.h
+++ clangd/FuzzyMatch.h
@@ -58,8 +58,8 @@
void buildGraph();
void calculateRoles(const char *Text, CharRole *Out, int &Types, int N);
bool allowMatch(int P, int W) const;
- int skipPenalty(int W, Action Last) const;
- int matchBonus(int P, int W, Action Last) const;
+ int missScore(int W, Action Last) const;
+ int matchScore(int P, int W, Action Last) const;
// Pattern data is initialized by the constructor, then constant.
char Pat[MaxPat]; // Pattern data
Index: clangd/FuzzyMatch.cpp
===================================================================
--- clangd/FuzzyMatch.cpp
+++ clangd/FuzzyMatch.cpp
@@ -58,6 +58,7 @@
#include "FuzzyMatch.h"
#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Format.h"
namespace clang {
@@ -67,7 +68,6 @@
constexpr int FuzzyMatcher::MaxPat;
constexpr int FuzzyMatcher::MaxWord;
-static char lower(char C) { return C >= 'A' && C <= 'Z' ? C + ('a' - 'A') : C; }
// A "negative infinity" score that won't overflow.
// We use this to mark unreachable states and forbidden solutions.
// Score field is 15 bits wide, min value is -2^14, we use half of that.
@@ -80,25 +80,17 @@
ScoreScale(PatN ? float{1} / (PerfectBonus * PatN) : 0), WordN(0) {
std::copy(Pattern.begin(), Pattern.begin() + PatN, Pat);
for (int I = 0; I < PatN; ++I)
- LowPat[I] = lower(Pat[I]);
- Scores[0][0][Miss] = {0, Miss};
- Scores[0][0][Match] = {AwfulScore, Miss};
- for (int P = 0; P <= PatN; ++P)
- for (int W = 0; W < P; ++W)
- for (Action A : {Miss, Match})
- Scores[P][W][A] = {AwfulScore, Miss};
- if (PatN > 0)
- calculateRoles(Pat, PatRole, PatTypeSet, PatN);
+ LowPat[I] = toLower(Pat[I]);
+ calculateRoles(Pat, PatRole, PatTypeSet, PatN);
}
Optional<float> FuzzyMatcher::match(StringRef Word) {
if (!(WordContainsPattern = init(Word)))
return None;
- if (!PatN)
- return 1;
buildGraph();
- auto Best = std::max(Scores[PatN][WordN][Miss].Score,
- Scores[PatN][WordN][Match].Score);
+ int Best = AwfulScore;
+ for (int I = PatN; I <= WordN; I++)
+ Best = std::max(Best, Scores[PatN][I][Match].Score);
if (isAwful(Best))
return None;
return ScoreScale * std::min(PerfectBonus * PatN, std::max<int>(0, Best));
@@ -179,7 +171,8 @@
}
void FuzzyMatcher::calculateRoles(const char *Text, CharRole *Out, int &TypeSet,
int N) {
- assert(N > 0);
+ if (!N)
+ return;
CharType Type = packedLookup<CharType>(CharTypes, Text[0]);
TypeSet = 1 << Type;
// Types holds a sliding window of (Prev, Curr, Next) types.
@@ -206,10 +199,8 @@
if (PatN > WordN)
return false;
std::copy(NewWord.begin(), NewWord.begin() + WordN, Word);
- if (PatN == 0)
- return true;
for (int I = 0; I < WordN; ++I)
- LowWord[I] = lower(Word[I]);
+ LowWord[I] = toLower(Word[I]);
// Cheap subsequence check.
for (int W = 0, P = 0; P != PatN; ++W) {
@@ -236,31 +227,29 @@
// This range is not strict: we can apply larger bonuses/penalties, or penalize
// non-matched characters.
void FuzzyMatcher::buildGraph() {
+ Scores[0][0][Miss] = Scores[0][0][Match] = {0, Miss};
for (int W = 0; W < WordN; ++W) {
- Scores[0][W + 1][Miss] = {Scores[0][W][Miss].Score - skipPenalty(W, Miss),
+ Scores[0][W + 1][Miss] = {Scores[0][W][Miss].Score + missScore(W, Miss),
Miss};
Scores[0][W + 1][Match] = {AwfulScore, Miss};
}
for (int P = 0; P < PatN; ++P) {
+ Scores[P + 1][P][Miss] = Scores[P + 1][P][Match] = {AwfulScore, Miss};
for (int W = P; W < WordN; ++W) {
auto &Score = Scores[P + 1][W + 1], &PreMiss = Scores[P + 1][W];
- auto MatchMissScore = PreMiss[Match].Score;
- auto MissMissScore = PreMiss[Miss].Score;
- if (P < PatN - 1) { // Skipping trailing characters is always free.
- MatchMissScore -= skipPenalty(W, Match);
- MissMissScore -= skipPenalty(W, Miss);
- }
+ auto MatchMissScore = PreMiss[Match].Score + missScore(W, Match);
+ auto MissMissScore = PreMiss[Miss].Score + missScore(W, Miss);
Score[Miss] = (MatchMissScore > MissMissScore)
? ScoreInfo{MatchMissScore, Match}
: ScoreInfo{MissMissScore, Miss};
if (!allowMatch(P, W)) {
Score[Match] = {AwfulScore, Miss};
} else {
auto &PreMatch = Scores[P][W];
- auto MatchMatchScore = PreMatch[Match].Score + matchBonus(P, W, Match);
- auto MissMatchScore = PreMatch[Miss].Score + matchBonus(P, W, Miss);
+ auto MatchMatchScore = PreMatch[Match].Score + matchScore(P, W, Match);
+ auto MissMatchScore = PreMatch[Miss].Score + matchScore(P, W, Miss);
Score[Match] = (MatchMatchScore > MissMatchScore)
? ScoreInfo{MatchMatchScore, Match}
: ScoreInfo{MissMatchScore, Miss};
@@ -284,16 +273,16 @@
(Word[W] != LowWord[W] && WordTypeSet & 1 << Lower);
}
-int FuzzyMatcher::skipPenalty(int W, Action Last) const {
+int FuzzyMatcher::missScore(int W, Action Last) const {
int S = 0;
if (WordRole[W] == Head) // Skipping a segment.
- S += 1;
+ S -= 1;
if (Last == Match) // Non-consecutive match.
- S += 2; // We'd rather skip a segment than split our match.
+ S -= 2; // We'd rather skip a segment than split our match.
return S;
}
-int FuzzyMatcher::matchBonus(int P, int W, Action Last) const {
+int FuzzyMatcher::matchScore(int P, int W, Action Last) const {
assert(LowPat[P] == LowWord[W]);
int S = 1;
// Bonus: pattern so far is a (case-insensitive) prefix of the word.
@@ -331,40 +320,42 @@
if (!WordContainsPattern) {
OS << "Substring check failed.\n";
return Result;
- } else if (isAwful(std::max(Scores[PatN][WordN][Match].Score,
- Scores[PatN][WordN][Miss].Score))) {
+ }
+ int W = PatN;
+ for (int I = PatN; ++I <= WordN; )
+ if (Scores[PatN][I][Match].Score > Scores[PatN][W][Match].Score)
+ W = I;
+ if (isAwful(Scores[PatN][W][Match].Score))
OS << "Substring check passed, but all matches are forbidden\n";
- }
if (!(PatTypeSet & 1 << Upper))
OS << "Lowercase query, so scoring ignores case\n";
// Traverse Matched table backwards to reconstruct the Pattern/Word mapping.
// The Score table has cumulative scores, subtracting along this path gives
// us the per-letter scores.
- Action Last =
- (Scores[PatN][WordN][Match].Score > Scores[PatN][WordN][Miss].Score)
- ? Match
- : Miss;
+ Action Last = Miss;
int S[MaxWord];
- Action A[MaxWord];
- for (int W = WordN - 1, P = PatN - 1; W >= 0; --W) {
- A[W] = Last;
- const auto &Cell = Scores[P + 1][W + 1][Last];
+ Action A[MaxWord + 1];
+ A[WordN] = Miss;
+ for (int I = WordN, P = PatN; I > 0; I--) {
+ if (I == W)
+ Last = Match;
+ A[I - 1] = Last;
+ const auto &Cell = Scores[P][I][Last];
if (Last == Match)
--P;
- const auto &Prev = Scores[P + 1][W][Cell.Prev];
- S[W] = Cell.Score - Prev.Score;
- Last = Cell.Prev;
+ const auto &Prev = Scores[P][I - 1][Cell.Prev];
+ S[I - 1] = Cell.Score - Prev.Score;
+ if (I <= W)
+ Last = Cell.Prev;
}
for (int I = 0; I < WordN; ++I) {
if (A[I] == Match && (I == 0 || A[I - 1] == Miss))
Result.push_back('[');
- if (A[I] == Miss && I > 0 && A[I - 1] == Match)
- Result.push_back(']');
Result.push_back(Word[I]);
+ if (A[I] == Match && A[I + 1] == Miss)
+ Result.push_back(']');
}
- if (A[WordN - 1] == Match)
- Result.push_back(']');
for (char C : StringRef(Word, WordN))
OS << " " << C << " ";
@@ -395,7 +386,7 @@
for (Action A : {Miss, Match}) {
OS << ((I && A == Miss) ? Pat[I - 1] : ' ') << "|";
for (int J = 0; J <= WordN; ++J) {
- if (!isAwful(Scores[I][J][A].Score))
+ if (I <= J && !isAwful(Scores[I][J][A].Score))
OS << format("%3d%c", Scores[I][J][A].Score,
Scores[I][J][A].Prev == Match ? '*' : ' ');
else
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
