137 lines · c
1//===--- FuzzyMatch.h - Approximate identifier matching ---------*- 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// This file implements fuzzy-matching of strings against identifiers.10// It indicates both the existence and quality of a match:11// 'eb' matches both 'emplace_back' and 'embed', the former has a better score.12//13//===----------------------------------------------------------------------===//14 15#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FUZZYMATCH_H16#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FUZZYMATCH_H17 18#include "llvm/ADT/ArrayRef.h"19#include "llvm/ADT/SmallString.h"20#include "llvm/ADT/StringRef.h"21#include "llvm/Support/raw_ostream.h"22#include <optional>23 24namespace clang {25namespace clangd {26 27// Utilities for word segmentation.28// FuzzyMatcher already incorporates this logic, so most users don't need this.29//30// A name like "fooBar_baz" consists of several parts foo, bar, baz.31// Aligning segmentation of word and pattern improves the fuzzy-match.32// For example: [lol] matches "LaughingOutLoud" better than "LionPopulation"33//34// First we classify each character into types (uppercase, lowercase, etc).35// Then we look at the sequence: e.g. [upper, lower] is the start of a segment.36 37// We distinguish the types of characters that affect segmentation.38// It's not obvious how to segment digits, we treat them as lowercase letters.39// As we don't decode UTF-8, we treat bytes over 127 as lowercase too.40// This means we require exact (case-sensitive) match for those characters.41enum CharType : unsigned char {42 Empty = 0, // Before-the-start and after-the-end (and control chars).43 Lower = 1, // Lowercase letters, digits, and non-ASCII bytes.44 Upper = 2, // Uppercase letters.45 Punctuation = 3, // ASCII punctuation (including Space)46};47// A CharTypeSet is a bitfield representing all the character types in a word.48// Its bits are 1<<Empty, 1<<Lower, etc.49using CharTypeSet = unsigned char;50 51// Each character's Role is the Head or Tail of a segment, or a Separator.52// e.g. XMLHttpRequest_Async53// +--+---+------ +----54// ^Head ^Tail ^Separator55enum CharRole : unsigned char {56 Unknown = 0, // Stray control characters or impossible states.57 Tail = 1, // Part of a word segment, but not the first character.58 Head = 2, // The first character of a word segment.59 Separator = 3, // Punctuation characters that separate word segments.60};61 62// Compute segmentation of Text.63// Character roles are stored in Roles (Roles.size() must equal Text.size()).64// The set of character types encountered is returned, this may inform65// heuristics for dealing with poorly-segmented identifiers like "strndup".66CharTypeSet calculateRoles(llvm::StringRef Text,67 llvm::MutableArrayRef<CharRole> Roles);68 69// A matcher capable of matching and scoring strings against a single pattern.70// It's optimized for matching against many strings - match() does not allocate.71class FuzzyMatcher {72public:73 // Characters beyond MaxPat are ignored.74 FuzzyMatcher(llvm::StringRef Pattern);75 76 // If Word matches the pattern, return a score indicating the quality match.77 // Scores usually fall in a [0,1] range, with 1 being a very good score.78 // "Super" scores in (1,2] are possible if the pattern is the full word.79 // Characters beyond MaxWord are ignored.80 std::optional<float> match(llvm::StringRef Word);81 82 llvm::StringRef pattern() const { return llvm::StringRef(Pat, PatN); }83 bool empty() const { return PatN == 0; }84 85 // Dump internal state from the last match() to the stream, for debugging.86 // Returns the pattern with [] around matched characters, e.g.87 // [u_p] + "unique_ptr" --> "[u]nique[_p]tr"88 llvm::SmallString<256> dumpLast(llvm::raw_ostream &) const;89 90private:91 // We truncate the pattern and the word to bound the cost of matching.92 constexpr static int MaxPat = 63, MaxWord = 127;93 // Action describes how a word character was matched to the pattern.94 // It should be an enum, but this causes bitfield problems:95 // - for MSVC the enum type must be explicitly unsigned for correctness96 // - GCC 4.8 complains not all values fit if the type is unsigned97 using Action = bool;98 constexpr static Action Miss = false; // Word character was skipped.99 constexpr static Action Match = true; // Matched against a pattern character.100 101 bool init(llvm::StringRef Word);102 void buildGraph();103 bool allowMatch(int P, int W, Action Last) const;104 int skipPenalty(int W, Action Last) const;105 int matchBonus(int P, int W, Action Last) const;106 107 // Pattern data is initialized by the constructor, then constant.108 char Pat[MaxPat]; // Pattern data109 int PatN; // Length110 char LowPat[MaxPat]; // Pattern in lowercase111 CharRole PatRole[MaxPat]; // Pattern segmentation info112 CharTypeSet PatTypeSet; // Bitmask of 1<<CharType for all Pattern characters113 float ScoreScale; // Normalizes scores for the pattern length.114 115 // Word data is initialized on each call to match(), mostly by init().116 char Word[MaxWord]; // Word data117 int WordN; // Length118 char LowWord[MaxWord]; // Word in lowercase119 CharRole WordRole[MaxWord]; // Word segmentation info120 CharTypeSet WordTypeSet; // Bitmask of 1<<CharType for all Word characters121 bool WordContainsPattern; // Simple substring check122 123 // Cumulative best-match score table.124 // Boundary conditions are filled in by the constructor.125 // The rest is repopulated for each match(), by buildGraph().126 struct ScoreInfo {127 signed int Score : 15;128 Action Prev : 1;129 };130 ScoreInfo Scores[MaxPat + 1][MaxWord + 1][/* Last Action */ 2];131};132 133} // namespace clangd134} // namespace clang135 136#endif137