116 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// Trigrams are attributes of the symbol unqualified name used to effectively11/// extract symbols which can be fuzzy-matched given user query from the12/// inverted index. To match query with the extracted set of trigrams Q, the set13/// of generated trigrams T for identifier (unqualified symbol name) should14/// 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 three18/// characters (which is only a subset of all trigrams generated for an19/// identifier).20///21//===----------------------------------------------------------------------===//22 23#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_TRIGRAM_H24#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_TRIGRAM_H25 26#include "index/dex/Token.h"27#include "llvm/ADT/bit.h"28 29#include <array>30#include <string>31 32namespace clang {33namespace clangd {34namespace 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.38class 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 45public: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 move61/// 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 265/// - the first character + next head character66///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.72void 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 digits79/// are extracted and returned after deduplication.80///81/// For short queries (less than 3 characters with Head or Tail roles in Fuzzy82/// Matching segmentation) this returns a single trigram with the first83/// characters (up to 3) to perform prefix match.84std::vector<Token> generateQueryTrigrams(llvm::StringRef Query);85 86} // namespace dex87} // namespace clangd88} // namespace clang89 90namespace llvm {91template <> 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 llvm114 115#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_TRIGRAM_H116