1 //===--- Trigram.h - Trigram generation for Fuzzy 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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// Trigrams are attributes of the symbol unqualified name used to effectively 11 /// extract symbols which can be fuzzy-matched given user query from the 12 /// inverted index. To match query with the extracted set of trigrams Q, the set 13 /// of generated trigrams T for identifier (unqualified symbol name) should 14 /// contain all items of Q, i.e. Q ⊆ T. 15 /// 16 /// Trigram sets extracted from unqualified name and from query are different: 17 /// the set of query trigrams only contains consecutive sequences of three 18 /// characters (which is only a subset of all trigrams generated for an 19 /// identifier). 20 /// 21 //===----------------------------------------------------------------------===// 22 23 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_TRIGRAM_H 24 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_TRIGRAM_H 25 26 #include "index/dex/Token.h" 27 #include "llvm/ADT/bit.h" 28 29 #include <array> 30 #include <string> 31 32 namespace clang { 33 namespace clangd { 34 namespace dex { 35 36 // Compact representation of a trigram (string with up to 3 characters). 37 // Trigram generation is the hot path of indexing, so Token is too wasteful. 38 class Trigram { 39 std::array<char, 4> Data; // Last element is length. 40 // Steal some invalid bit patterns for DenseMap sentinels. 41 enum class Sentinel { Tombstone = 4, Empty = 5 }; Trigram(Sentinel S)42 Trigram(Sentinel S) : Data{0, 0, 0, static_cast<char>(S)} {} id()43 uint32_t id() const { return llvm::bit_cast<uint32_t>(Data); } 44 45 public: Trigram()46 Trigram() : Data{0, 0, 0, 0} {} Trigram(char A)47 Trigram(char A) : Data{A, 0, 0, 1} {} Trigram(char A,char B)48 Trigram(char A, char B) : Data{A, B, 0, 2} {} Trigram(char A,char B,char C)49 Trigram(char A, char B, char C) : Data{A, B, C, 3} {} str()50 std::string str() const { return std::string(Data.data(), Data[3]); } 51 friend struct ::llvm::DenseMapInfo<Trigram>; 52 friend bool operator==(Trigram L, Trigram R) { return L.id() == R.id(); } 53 friend bool operator<(Trigram L, Trigram R) { return L.id() < R.id(); } 54 }; 55 56 /// Produces list of unique fuzzy-search trigrams from unqualified symbol. 57 /// The trigrams give the 3-character query substrings this symbol can match. 58 /// 59 /// The symbol's name is broken into segments, e.g. "FooBar" has two segments. 60 /// Trigrams can start at any character in the input. Then we can choose to move 61 /// to the next character or to the start of the next segment. 62 /// 63 /// Short trigrams (length 1-2) are used for short queries. These are: 64 /// - prefixes of the identifier, of length 1 and 2 65 /// - the first character + next head character 66 /// 67 /// For "FooBar" we get the following trigrams: 68 /// {f, fo, fb, foo, fob, fba, oob, oba, bar}. 69 /// 70 /// Trigrams are lowercase, as trigram matching is case-insensitive. 71 /// Trigrams in the list are deduplicated. 72 void generateIdentifierTrigrams(llvm::StringRef Identifier, 73 std::vector<Trigram> &Out); 74 75 /// Returns list of unique fuzzy-search trigrams given a query. 76 /// 77 /// Query is segmented using FuzzyMatch API and downcasted to lowercase. Then, 78 /// the simplest trigrams - sequences of three consecutive letters and digits 79 /// are extracted and returned after deduplication. 80 /// 81 /// For short queries (less than 3 characters with Head or Tail roles in Fuzzy 82 /// Matching segmentation) this returns a single trigram with the first 83 /// characters (up to 3) to perform prefix match. 84 std::vector<Token> generateQueryTrigrams(llvm::StringRef Query); 85 86 } // namespace dex 87 } // namespace clangd 88 } // namespace clang 89 90 namespace llvm { 91 template <> struct DenseMapInfo<clang::clangd::dex::Trigram> { 92 using Trigram = clang::clangd::dex::Trigram; 93 static inline Trigram getEmptyKey() { 94 return Trigram(Trigram::Sentinel::Empty); 95 } 96 static inline Trigram getTombstoneKey() { 97 return Trigram(Trigram::Sentinel::Tombstone); 98 } 99 static unsigned getHashValue(Trigram V) { 100 // Finalize step from MurmurHash3. 101 uint32_t X = V.id(); 102 X ^= X >> 16; 103 X *= uint32_t{0x85ebca6b}; 104 X ^= X >> 13; 105 X *= uint32_t{0xc2b2ae35}; 106 X ^= X >> 16; 107 return X; 108 } 109 static bool isEqual(const Trigram &LHS, const Trigram &RHS) { 110 return LHS == RHS; 111 } 112 }; 113 } // namespace llvm 114 115 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_TRIGRAM_H 116