[clangd] FuzzyMatch exposes an API for its word segmentation. NFC

[sammccall]

Summary

This is intended to be used for indexing, e.g. in D49417

[ioeric]

lgtm

clangd/FuzzyMatch.h

 // It indicates both the existence and quality of a match:
 // 'eb' matches both 'emplace_back' and 'embed', the former has a better score.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FUZZYMATCH_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FUZZYMATCH_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace clangd {
 
+// Utilities for word segmentation.
+// FuzzyMatcher already incorporates this logic, so most users don't need this.
+//
+// A name like "fooBar_baz" consists of several parts foo, bar, baz.
+// Aligning segmentation of word and pattern improves the fuzzy-match.
+// For example: [lol] matches "LaughingOutLoud" better than "LionPopulation"
+//
+// First we classify each character into types (uppercase, lowercase, etc).
+// Then we look at the sequence: e.g. [upper, lower] is the start of a segment.
+
+// We distinguish the types of characters that affect segmentation.
+// It's not obvious how to segment digits, we treat them as lowercase letters.
+// As we don't decode UTF-8, we treat bytes over 127 as lowercase too.
+// This means we require exact (case-sensitive) match for those characters.
+enum CharType : unsigned char {
+  Empty = 0,       // Before-the-start and after-the-end (and control chars).
+  Lower = 1,       // Lowercase letters, digits, and non-ASCII bytes.
+  Upper = 2,       // Uppercase letters.
+  Punctuation = 3, // ASCII punctuation (including Space)
+};
+// A CharTypeSet is a bitfield representing all the character types in a word.
+// Its bits are 1<<Empty, 1<<Lower, etc.
+using CharTypeSet = unsigned char;
+
+// Each character's Role is the Head or Tail of a segment, or a Separator.
+// e.g. XMLHttpRequest_Async
+//      +--+---+------ +----
+//      ^Head   ^Tail ^Separator
+enum CharRole : unsigned char {
+  Unknown = 0,   // Stray control characters or impossible states.
+  Tail = 1,      // Part of a word segment, but not the first character.
+  Head = 2,      // The first character of a word segment.
+  Separator = 3, // Punctuation characters that separate word segments.
+};
+
+// Compute segmentation of Text.
+// Character roles are stored in Roles (Roles.size() must equal Text.size()).
+// The set of character types encountered is returned, this may inform
+// heuristics for dealing with poorly-segmented identifiers like "strndup".
+CharTypeSet calculateRoles(llvm::StringRef Text,
+                           llvm::MutableArrayRef<CharRole> Roles);
+
 // A matcher capable of matching and scoring strings against a single pattern.
 // It's optimized for matching against many strings - match() does not allocate.
 class FuzzyMatcher {
 public:
   // Characters beyond MaxPat are ignored.
   FuzzyMatcher(llvm::StringRef Pattern);
 
   // If Word matches the pattern, return a score indicating the quality match.
   // Scores usually fall in a [0,1] range, with 1 being a very good score.
   // "Super" scores in (1,2] are possible if the pattern is the full word.
   // Characters beyond MaxWord are ignored.
   llvm::Optional<float> match(llvm::StringRef Word);
 
   llvm::StringRef pattern() const { return llvm::StringRef(Pat, PatN); }
   bool empty() const { return PatN == 0; }
 
   // Dump internal state from the last match() to the stream, for debugging.
   // Returns the pattern with [] around matched characters, e.g.
   //   [u_p] + "unique_ptr" --> "[u]nique[_p]tr"
   llvm::SmallString<256> dumpLast(llvm::raw_ostream &) const;
 
 private:
   // We truncate the pattern and the word to bound the cost of matching.
   constexpr static int MaxPat = 63, MaxWord = 127;
-  enum CharRole : unsigned char; // For segmentation.
-  enum CharType : unsigned char; // For segmentation.
   // 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; // 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, Action Last) const;
   int skipPenalty(int W, Action Last) const;
   int matchBonus(int P, int W, Action Last) const;
 
   // Pattern data is initialized by the constructor, then constant.
   char Pat[MaxPat];         // Pattern data
   int PatN;                 // Length
   char LowPat[MaxPat];      // Pattern in lowercase
   CharRole PatRole[MaxPat]; // Pattern segmentation info
-  int PatTypeSet;           // Bitmask of 1<<CharType for all Pattern characters
+  CharTypeSet PatTypeSet;   // Bitmask of 1<<CharType for all Pattern characters
   float ScoreScale;         // Normalizes scores for the pattern length.
 
   // Word data is initialized on each call to match(), mostly by init().
   char Word[MaxWord];         // Word data
   int WordN;                  // Length
   char LowWord[MaxWord];      // Word in lowercase
   CharRole WordRole[MaxWord]; // Word segmentation info
-  int WordTypeSet;            // Bitmask of 1<<CharType for all Word characters
+  CharTypeSet WordTypeSet;    // Bitmask of 1<<CharType for all Word characters
   bool WordContainsPattern;   // Simple substring check
 
   // Cumulative best-match score table.
   // Boundary conditions are filled in by the constructor.
   // The rest is repopulated for each match(), by buildGraph().
   struct ScoreInfo {
     signed int Score : 15;
     Action Prev : 1;
   };
   ScoreInfo Scores[MaxPat + 1][MaxWord + 1][/* Last Action */ 2];
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/FuzzyMatch.cpp

FuzzyMatcher::FuzzyMatcher(StringRef Pattern)
   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);
+  PatTypeSet =
+      calculateRoles(StringRef(Pat, PatN), makeMutableArrayRef(PatRole, 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);
   if (isAwful(Best))
     return None;
   float Score =
       ScoreScale * std::min(PerfectBonus * PatN, std::max<int>(0, Best));
   // If the pattern is as long as the word, we have an exact string match,
   // since every pattern character must match something.
   if (WordN == PatN)
     Score *= 2; // May not be perfect 2 if case differs in a significant way.
   return Score;
 }
 
-// Segmentation of words and patterns.
-// A name like "fooBar_baz" consists of several parts foo, bar, baz.
-// Aligning segmentation of word and pattern improves the fuzzy-match.
-// For example: [lol] matches "LaughingOutLoud" better than "LionPopulation"
-//
-// First we classify each character into types (uppercase, lowercase, etc).
-// Then we look at the sequence: e.g. [upper, lower] is the start of a segment.
-
-// We only distinguish the types of characters that affect segmentation.
-// It's not obvious how to segment digits, we treat them as lowercase letters.
-// As we don't decode UTF-8, we treat bytes over 127 as lowercase too.
-// This means we require exact (case-sensitive) match.
-enum FuzzyMatcher::CharType : unsigned char {
-  Empty = 0,       // Before-the-start and after-the-end (and control chars).
-  Lower = 1,       // Lowercase letters, digits, and non-ASCII bytes.
-  Upper = 2,       // Uppercase letters.
-  Punctuation = 3, // ASCII punctuation (including Space)
-};
-
 // We get CharTypes from a lookup table. Each is 2 bits, 4 fit in each byte.
 // The top 6 bits of the char select the byte, the bottom 2 select the offset.
 // e.g. 'q' = 010100 01 = byte 28 (55), bits 3-2 (01) -> Lower.
 constexpr static uint8_t CharTypes[] = {
     0x00, 0x00, 0x00, 0x00, // Control characters
     0x00, 0x00, 0x00, 0x00, // Control characters
     0xff, 0xff, 0xff, 0xff, // Punctuation
     0x55, 0x55, 0xf5, 0xff, // Numbers->Lower, more Punctuation.
     0xab, 0xaa, 0xaa, 0xaa, // @ and A-O
     0xaa, 0xaa, 0xea, 0xff, // P-Z, more Punctuation.
     0x57, 0x55, 0x55, 0x55, // ` and a-o
     0x55, 0x55, 0xd5, 0x3f, // p-z, Punctuation, DEL.
     0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, // Bytes over 127 -> Lower.
     0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, // (probably UTF-8).
     0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55,
     0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55,
 };
 
-// Each character's Role is the Head or Tail of a segment, or a Separator.
-// e.g. XMLHttpRequest_Async
-//      +--+---+------ +----
-//      ^Head   ^Tail ^Separator
-enum FuzzyMatcher::CharRole : unsigned char {
-  Unknown = 0,   // Stray control characters or impossible states.
-  Tail = 1,      // Part of a word segment, but not the first character.
-  Head = 2,      // The first character of a word segment.
-  Separator = 3, // Punctuation characters that separate word segments.
-};
-
 // The Role can be determined from the Type of a character and its neighbors:
 //
 //   Example  | Chars | Type | Role
 //   ---------+--------------+-----
 //   F(o)oBar | Foo   | Ull  | Tail
 //   Foo(B)ar | oBa   | lUl  | Head
 //   (f)oo    | ^fo   | Ell  | Head
 //   H(T)TP   | HTT   | UUU  | Tail
constexpr static uint8_t CharRoles[] = {
     /* Prev=Upper */ 0x00, 0x55, 0x59, 0xff, // Ditto, but U(U)U->Tail
     /* Prev=Separ */ 0x00, 0xaa, 0xaa, 0xff, // After separator, like at start
     // clang-format on
 };
 
 template <typename T> static T packedLookup(const uint8_t *Data, int I) {
   return static_cast<T>((Data[I >> 2] >> ((I & 3) * 2)) & 3);
 }
-void FuzzyMatcher::calculateRoles(const char *Text, CharRole *Out, int &TypeSet,
-                                  int N) {
-  assert(N > 0);
+CharTypeSet calculateRoles(StringRef Text, MutableArrayRef<CharRole> Roles) {
+  assert(Text.size() == Roles.size());
+  if (Text.size() == 0)
+    return 0;
   CharType Type = packedLookup<CharType>(CharTypes, Text[0]);
-  TypeSet = 1 << Type;
+  CharTypeSet TypeSet = 1 << Type;
   // Types holds a sliding window of (Prev, Curr, Next) types.
   // Initial value is (Empty, Empty, type of Text[0]).
   int Types = Type;
   // Rotate slides in the type of the next character.
   auto Rotate = [&](CharType T) { Types = ((Types << 2) | T) & 0x3f; };
-  for (int I = 0; I < N - 1; ++I) {
+  for (unsigned I = 0; I < Text.size() - 1; ++I) {
     // For each character, rotate in the next, and look up the role.
     Type = packedLookup<CharType>(CharTypes, Text[I + 1]);
     TypeSet |= 1 << Type;
     Rotate(Type);
-    *Out++ = packedLookup<CharRole>(CharRoles, Types);
+    Roles[I] = packedLookup<CharRole>(CharRoles, Types);
   }
   // For the last character, the "next character" is Empty.
   Rotate(Empty);
-  *Out++ = packedLookup<CharRole>(CharRoles, Types);
+  Roles[Text.size() - 1] = packedLookup<CharRole>(CharRoles, Types);
+  return TypeSet;
 }
 
 // Sets up the data structures matching Word.
 // Returns false if we can cheaply determine that no match is possible.
 bool FuzzyMatcher::init(StringRef NewWord) {
   WordN = std::min<int>(MaxWord, NewWord.size());
   if (PatN > WordN)
     return false;
if (W == WordN)
       return false;
     if (LowWord[W] == LowPat[P])
       ++P;
   }
 
   // FIXME: some words are hard to tokenize algorithmically.
   // e.g. vsprintf is V S Print F, and should match [pri] but not [int].
   // We could add a tokenization dictionary for common stdlib names.
-  calculateRoles(Word, WordRole, WordTypeSet, WordN);
+  WordTypeSet = calculateRoles(StringRef(Word, WordN),
+                               makeMutableArrayRef(WordRole, WordN));
   return true;
 }
 
 // The forwards pass finds the mappings of Pattern onto Word.
 // Score = best score achieved matching Word[..W] against Pat[..P].
 // Unlike other tables, indices range from 0 to N *inclusive*
 // Matched = whether we chose to match Word[W] with Pat[P] or not.
 //

unittests/clangd/FuzzyMatchTests.cpp

 // Testing exact scores is fragile, so we prefer Ranking tests.
 TEST(FuzzyMatch, Scoring) {
   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));
 }
 
+// Returns pretty-printed segmentation of Text.
+// e.g. std::basic_string --> +--  +---- +-----
+std::string segment(StringRef Text) {
+  std::vector<CharRole> Roles(Text.size());
+  calculateRoles(Text, Roles);
+  std::string Printed;
+  for (unsigned I = 0; I < Text.size(); ++I)
+    Printed.push_back("?-+ "[static_cast<unsigned>(Roles[I])]);
+  return Printed;
+}
+
+// this is a no-op hack so clang-format will vertically align our testcases.
+StringRef returns(StringRef Text) { return Text; }
+
+TEST(FuzzyMatch, Segmentation) {
+  EXPECT_THAT(segment("std::basic_string"), //
+              returns("+--  +---- +-----"));
+  EXPECT_THAT(segment("XMLHttpRequest"), //
+              returns("+--+---+------"));
+  EXPECT_THAT(segment("t3h PeNgU1N oF d00m!!!!!!!!"), //
+              returns("+-- +-+-+-+ ++ +---        "));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang