Index: clangd/FuzzyMatch.h
===================================================================
--- clangd/FuzzyMatch.h
+++ clangd/FuzzyMatch.h
@@ -58,7 +58,7 @@
   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 missPenalty(int W, Action Last) const;
   int matchBonus(int P, int W, Action Last) const;
 
   // Pattern data is initialized by the constructor, then constant.
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,19 @@
       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);
+  // The pattern doesn't have to match the whole word (but the whole pattern
+  // must match). Find the optimal prefix of Word to match Pattern.
+  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 +173,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 +201,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,21 +229,19 @@
 // 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 - missPenalty(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 - missPenalty(W, Match);
+      auto MissMissScore = PreMiss[Miss].Score - missPenalty(W, Miss);
       Score[Miss] = (MatchMissScore > MissMissScore)
                         ? ScoreInfo{MatchMissScore, Match}
                         : ScoreInfo{MissMissScore, Miss};
@@ -284,10 +275,10 @@
          (Word[W] != LowWord[W] && WordTypeSet & 1 << Lower);
 }
 
-int FuzzyMatcher::skipPenalty(int W, Action Last) const {
+int FuzzyMatcher::missPenalty(int W, Action Last) const {
   int S = 0;
   if (WordRole[W] == Head) // Skipping a segment.
-    S += 1;
+    ++S;
   if (Last == Match) // Non-consecutive match.
     S += 2;          // We'd rather skip a segment than split our match.
   return S;
@@ -331,40 +322,46 @@
   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 P = PatN; ++P <= WordN; )
+    if (Scores[PatN][P][Match].Score > Scores[PatN][W][Match].Score)
+      W = P;
+  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;
   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];
-    if (Last == Match)
-      --P;
-    const auto &Prev = Scores[P + 1][W][Cell.Prev];
-    S[W] = Cell.Score - Prev.Score;
-    Last = Cell.Prev;
+  Action A[MaxWord + 1];
+  {
+    int P = PatN;
+    A[WordN] = Miss;
+    for (int I = WordN; I > W; I--) {
+      A[I - 1] = Miss;
+      S[I - 1] = Scores[P][I][Miss].Score - Scores[P][I - 1][Miss].Score;
+    }
+    Action Last = Match;
+    for (int I = W; I > 0; I--) {
+      A[I - 1] = Last;
+      const auto &Cell = Scores[P][I][Last];
+      if (Last == Match)
+        --P;
+      const auto &Prev = Scores[P][I - 1][Cell.Prev];
+      S[I - 1] = Cell.Score - Prev.Score;
+      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 +392,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