clang-tools-extra/clangd/index/dex/Trigram.h

   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