clang-tools  15.0.0git
Trigram.h
Go to the documentation of this file.
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> {
93  static inline Trigram getEmptyKey() {
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
llvm
Some operations such as code completion produce a set of candidates.
Definition: YAMLGenerator.cpp:28
clang::clangd::dex::Trigram::str
std::string str() const
Definition: Trigram.h:50
clang::clangd::dex::Trigram::operator==
friend bool operator==(Trigram L, Trigram R)
Definition: Trigram.h:52
clang::clangd::dex::Trigram::Trigram
Trigram(char A)
Definition: Trigram.h:47
clang::clangd::dex::Trigram
Definition: Trigram.h:38
clang::clangd::dex::Trigram::Trigram
Trigram(char A, char B, char C)
Definition: Trigram.h:49
clang::clangd::dex::generateQueryTrigrams
std::vector< Token > generateQueryTrigrams(llvm::StringRef Query)
Returns list of unique fuzzy-search trigrams given a query.
Definition: Trigram.cpp:123
llvm::DenseMapInfo< clang::clangd::dex::Trigram >::getHashValue
static unsigned getHashValue(Trigram V)
Definition: Trigram.h:99
ns1::ns2::A
@ A
Definition: CategoricalFeature.h:3
X
int X
Definition: LSPBinderTests.cpp:25
llvm::DenseMapInfo< clang::clangd::dex::Trigram >::isEqual
static bool isEqual(const Trigram &LHS, const Trigram &RHS)
Definition: Trigram.h:109
llvm::DenseMapInfo< clang::clangd::dex::Trigram >::getEmptyKey
static Trigram getEmptyKey()
Definition: Trigram.h:93
clang::clangd::dex::Trigram::Trigram
Trigram()
Definition: Trigram.h:46
clang::clangd::dex::generateIdentifierTrigrams
void generateIdentifierTrigrams(llvm::StringRef Identifier, std::vector< Trigram > &Result)
Produces list of unique fuzzy-search trigrams from unqualified symbol.
Definition: Trigram.cpp:100
llvm::DenseMapInfo< clang::clangd::dex::Trigram >::getTombstoneKey
static Trigram getTombstoneKey()
Definition: Trigram.h:96
clang::clangd::Empty
@ Empty
Definition: FuzzyMatch.h:42
clang::clangd::dex::Trigram::operator<
friend bool operator<(Trigram L, Trigram R)
Definition: Trigram.h:53
clang::clangd::dex::Trigram::Trigram
Trigram(char A, char B)
Definition: Trigram.h:48
C
const Criteria C
Definition: FunctionCognitiveComplexityCheck.cpp:93
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
ns1::ns2::B
@ B
Definition: CategoricalFeature.h:3
Out
CompiledFragmentImpl & Out
Definition: ConfigCompile.cpp:99
Token.h