| 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 }; |
| 42 |
Trigram(Sentinel S) : Data{0, 0, 0, static_cast<char>(S)} {} |
| 43 |
uint32_t id() const { return llvm::bit_cast<uint32_t>(Data); } |
| 44 |
|
| 45 |
public: |
| 46 |
Trigram() : Data{0, 0, 0, 0} {} |
| 47 |
Trigram(char A) : Data{A, 0, 0, 1} {} |
| 48 |
Trigram(char A, char B) : Data{A, B, 0, 2} {} |
| 49 |
Trigram(char A, char B, char C) : Data{A, B, C, 3} {} |
| 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 |