[clangd] Introduce Dex symbol index search tokens

[kbobyrev]

Summary

This patch introduces the core building block of the next-generation Clangd symbol index - Dex. Search tokens are the keys in the inverted index and represent a characteristic of a specific symbol: examples of search token types (Token Namespaces) are

• Trigrams - these are essential for unqualified symbol name fuzzy search
• Scopes for filtering the symbols by the namespace
• Paths, e.g. these can be used to uprank symbols defined close to the edited file

This patch outlines the generic for such token namespaces, but only implements trigram generation.

The intuition behind trigram generation algorithm is that each extracted trigram is a valid sequence for Fuzzy Matcher jumps, proposed implementation utilize existing FuzzyMatcher API for segmentation and trigram extraction.

However, trigrams generation algorithm for the query string is different from the previous one: it simply yields sequences of 3 consecutive lowercased valid characters (letters, digits).

Dex RFC in the mailing list: http://lists.llvm.org/pipermail/clangd-dev/2018-July/000022.html

The trigram generation techniques are described in detail in the proposal:
https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit#heading=h.903u1zon9nkj

[kbobyrev]

The upcoming changes:

• Use segmentation API exposed in https://reviews.llvm.org/rL337527
• Get rid of the pre-computed hash for now as discussed internally
• Fix the bug with whole segments concatenation

[sammccall]

clang-tools-extra/clangd/index/dex/Token.cpp

25 ↗

(On Diff #156444)

specializing the hash function looks like premature optimization (or possibly pessimisation)
One the one hand, it's a perfect hash!

On the other hand, when used with a power-of-two sized hashtable (particularly 256 is a fun example), all the trigrams are going to hash into the alphanumeric buckets, and other buckets will be empty!

DenseMap is a power-of-two hashtable!

30 ↗

(On Diff #156444)

llvm::hash_combine(static_cast<int>(TokenKind),Data)

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

10 ↗

(On Diff #156444)

nit: swap these sentences around? conceptual explanation first, how they're used later?

could even give an example:

// The symbol std::cout might have the tokens:
// * Scope "std::"
// * Trigram "cou"
// * Trigram "out"
// * Type "std::ostream"

28 ↗

(On Diff #156444)

nit: "Hashable" isn't really important here.
nit: it doesn't *represent* a search primitive, it *is* a search primitive.

Maybe

/// A Token represents an attribute of a symbol, such as a particular
/// trigram present in the name (used for fuzzy search).

33 ↗

(On Diff #156444)

As discussed offline: think we misunderstood each other about the separate struct.
I rather meant *this* class could just be a struct.

36 ↗

(On Diff #156444)

don't give examples of the enum values immediately before defining the enum values :-)
Just put the comments on the values themselves, and omit the ones that aren't here yet (or leave a TODO)

47 ↗

(On Diff #156444)

move these to enum values

58 ↗

(On Diff #156444)

nit: probably reverse the order here since Token(TRIGRAM, "str") reads more naturally than Token("str", TRIGRAM) - context is present to understand the data

60 ↗

(On Diff #156444)

can we just use the standard hash_value() function? Why this accessor?

79 ↗

(On Diff #156444)

as discussed offline: this precomputed hash looks like premature optimization to me.

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

35 ↗

(On Diff #156444)

just iterate at the end and collect them? order shouldn't matter here.

37 ↗

(On Diff #156444)

ah, you're also handling this by cases here.

This doesn't seem necessary.
In fact I think there's a fairly simple way to express this that works naturally with the segmentation structure produced by fuzzymatch (so doesn't need a version of segmentIdentifier to wrap it).
But it's taking me too long to work out the details, will write a followup comment or discuss offline.

46 ↗

(On Diff #156444)

please use short names like I, S1, etc for iterators and loop counters.

90 ↗

(On Diff #156444)

There seems to be a lot of overlap between this one and the third loop.

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

10 ↗

(On Diff #156444)

This would be a great place to describe *how* trigrams are used by fuzzy matching (the idea that you generate trigrams T for the identifier, trigrams Q for the query, and require Q ⊆ T)

56 ↗

(On Diff #156444)

Per the examples above, segmentIdentifier doesn't case-fold its output, but all the inputs shown here are lowercase.
Is the caller expected to do that in between calling here, or does generateTrigrams case-fold as part of generation?

(please doc)

58 ↗

(On Diff #156444)

seem to have two summaries here, drop or merge with previous?

64 ↗

(On Diff #156444)

This is true, but I think treating these as four cases doesn't give a clear understanding of how they're related.

What about:

Trigrams can start at any character in the input. Then we can choose to move to the next character, move to the start of the next segment, or skip over a segment.

For input [abstract factory producer impl]:
* the simplest trigrams are consecutive letters from one segment (abs, bst, ..., mpl)
* but may cross two segments (abf, bpr)
* or even three (api, ypi)

[sammccall]

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

37 ↗

(On Diff #156444)

The idea is to precompute the list of "legal next chars" after each char.
This can in fact be done in one backwards pass. Then actually computing the trigram set is very easy.

generateTrigrams(StringRef Text) {
// Segment the text.
vector<CharRole> Roles(Text.size());
calculateRoles(Text, makeMutableArrayRef(Roles));

// Calculate legal next characters after each character.
vector<unsigned[3]> Next(Text.size()); // 0 entries mean "nothing"
unsigned NextTail = 0, NextSeg = 0, NextNextSeg = 0;
for (int I = Text.size() - 1; i >= 0; --I) {
  Next[I] = {NextTail, NextSeg, NextNextSeg};
  NextTail = Roles[I] == Tail ? I : 0;
  if (Roles[I] == Head) {
    NextNextHead = NextHead;
    NextHead = I;
  }
}

// Compute trigrams. They can start at head or tail chars.
DenseSet<Token> Tokens.
for (int I = 0; I < Text.size(); ++I) {
  if (Roles[I] != Head && Roles[I] != Tail) continue;
  for (unsigned J : Next[I]) {
    if (!J) continue;
    for (unsigned K : Next[K]) {
      if (!K) continue;
      char Trigram[] = {Text[I], Text[J], Text[K]};
      Tokens.emplate(TRIGRAM, Trigram);
    }
  }
}

// Return deduplicated trigrams.
std::vector<Token> TokensV;
for (const auto& E : Tokens) TokensV.push_back(E.second);
return TokensV;

[kbobyrev]

Address all comments from the last iteration.

Latest changes:

• Trigram generation algorithm now uses clangd FuzzyMatching API using the technique proposed by @sammccall
• Another piece of trigram generation algorithm on query-side was introduced
• Hash is no longer stored for each token and is computed more effectively
• Documentation is refined and should be more consistent now

[kbobyrev]

Wrong diff, should be correct now.

[sammccall]

Looks really nice! Only major issue is the query trigrams don't look right.
Otherwise, some style nits and fixes that seem to have gotten lost.

clang-tools-extra/clangd/index/dex/Token.cpp

28 ↗

(On Diff #156774)

nit: inline these trivial accessors, so they can be inlined at the callsite

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

33 ↗

(On Diff #156444)

This one doesn't seem to be done - any reason to keep the class with accessors rather than just a struct for now?

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

32 ↗

(On Diff #156774)

nit: total segment length <3 characters?
(e.g. u_p is also ignored)

38 ↗

(On Diff #156774)

nit: seems clearer to call tolower inline rather than mutating the input param - "identifier" doesn't really describe its new value

39 ↗

(On Diff #156774)

nit: prefer llvm::toLower, which returns char

94 ↗

(On Diff #156774)

(again, toLower and consider moving to Chars.push_back() call)

105 ↗

(On Diff #156774)

i.e. you don't want this

35 ↗

(On Diff #156444)

this was not done
(now also in generateQueryTrigrams)

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

37 ↗

(On Diff #156774)

nit: using the same logic as FuzzyMatch
(callers don't know the name calculateRoles, probably)

nit: lowercased
(downcast seems a bit confusing)

49 ↗

(On Diff #156774)

nit: StringRef here and below?

56 ↗

(On Diff #156774)

this appears to be too restrictive?

e.g. for TUDecl you require [tud, ude, dec, ecl]

I think you just want a sliding window of three successive head/tail characters.

clang-tools-extra/unittests/clangd/DexIndexTests.cpp

75 ↗

(On Diff #156774)

seems like it should be [abc, bcd, cde, def]

[kbobyrev]

Address all comments, refine tests.

[kbobyrev]

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

38 ↗

(On Diff #156774)

As discussed offline, I think it might be more efficient to copy apply toLower once instead of doing that up to 8 times more.

[sammccall]

Thanks for the polish!
Last few nits, but feel free to land once you're happy.

clang-tools-extra/clangd/index/dex/Token.cpp

21 ↗

(On Diff #157020)

nit: I'd suggest inlining these trivial functions and deleting the cpp file - one less file is always nice!

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

51 ↗

(On Diff #157020)

This sentence got a bit mangled.

90 ↗

(On Diff #157020)

nit: just return {clang::clangd::dex::Token::Kind::Sentinel, "EmptyKey"};
you're making a copy here anyway.

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

56 ↗

(On Diff #157020)

(just for my curiosity - why are the double braces needed rather than single?)

101 ↗

(On Diff #157020)

nit: LowercaseQuery = Query.lower();
(and above)

clang-tools-extra/unittests/clangd/DexIndexTests.cpp

22 ↗

(On Diff #157020)

you never call this function from tests, fold it together into Trigrams?

31 ↗

(On Diff #157020)

nit: function needs to start with a lowercase letter

if you like: trigramsAre would fit with typical matcher factory style

[kbobyrev]

Address last round of comments.

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

56 ↗

(On Diff #157020)

Discussed offline: that's probably a bug, probably worth looking into.

clang-tools-extra/trunk/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   ProtocolHandlers.cpp
   Quality.cpp
   SourceCode.cpp
   Threading.cpp
   Trace.cpp
   TUScheduler.cpp
   URI.cpp
   XRefs.cpp
+
   index/CanonicalIncludes.cpp
   index/FileIndex.cpp
   index/Index.cpp
   index/MemIndex.cpp
   index/Merge.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
+  index/dex/Trigram.cpp
+
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangDriver
   clangFormat
   clangFrontend
   clangIndex

clang-tools-extra/trunk/clangd/index/dex/Token.h

+//===--- Token.h - Symbol Search primitive ----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Token objects represent a characteristic of a symbol, which can be used to
+// perform efficient search. Tokens are keys for inverted index which are mapped
+// to the corresponding posting lists.
+//
+// The symbol std::cout might have the tokens:
+// * Scope "std::"
+// * Trigram "cou"
+// * Trigram "out"
+// * Type "std::ostream"
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TOKEN_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TOKEN_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+/// A Token represents an attribute of a symbol, such as a particular trigram
+/// present in the name (used for fuzzy search).
+///
+/// Tokens can be used to perform more sophisticated search queries by
+/// constructing complex iterator trees.
+struct Token {
+  /// Kind specifies Token type which defines semantics for the internal
+  /// representation. Each Kind has different representation stored in Data
+  /// field.
+  enum class Kind {
+    /// Represents trigram used for fuzzy search of unqualified symbol names.
+    ///
+    /// Data contains 3 bytes with trigram contents.
+    Trigram,
+    /// Scope primitives, e.g. "symbol belongs to namespace foo::bar".
+    ///
+    /// Data stroes full scope name , e.g. "foo::bar::baz::" or "" (for global
+    /// scope).
+    Scope,
+    /// Internal Token type for invalid/special tokens, e.g. empty tokens for
+    /// llvm::DenseMap.
+    Sentinel,
+    /// FIXME(kbobyrev): Add other Token Kinds
+    /// * Path with full or relative path to the directory in which symbol is
+    ///   defined
+    /// * Type with qualified type name or its USR
+  };
+
+  Token(Kind TokenKind, llvm::StringRef Data)
+      : Data(Data), TokenKind(TokenKind) {}
+
+  bool operator==(const Token &Other) const {
+    return TokenKind == Other.TokenKind && Data == Other.Data;
+  }
+
+  /// Representation which is unique among Token with the same Kind.
+  std::string Data;
+  Kind TokenKind;
+
+  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Token &T) {
+    return OS << T.Data;
+  }
+
+private:
+  friend llvm::hash_code hash_value(const Token &Token) {
+    return llvm::hash_combine(static_cast<int>(Token.TokenKind), Token.Data);
+  }
+};
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+namespace llvm {
+
+// Support Tokens as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::dex::Token> {
+  static inline clang::clangd::dex::Token getEmptyKey() {
+    return {clang::clangd::dex::Token::Kind::Sentinel, "EmptyKey"};
+  }
+
+  static inline clang::clangd::dex::Token getTombstoneKey() {
+    return {clang::clangd::dex::Token::Kind::Sentinel, "TombstoneKey"};
+  }
+
+  static unsigned getHashValue(const clang::clangd::dex::Token &Tag) {
+    return hash_value(Tag);
+  }
+
+  static bool isEqual(const clang::clangd::dex::Token &LHS,
+                      const clang::clangd::dex::Token &RHS) {
+    return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
+#endif

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

+//===--- Trigram.h - Trigram generation for Fuzzy Matching ------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Trigrams are attributes of the symbol unqualified name used to effectively
+// extract symbols which can be fuzzy-matched given user query from the inverted
+// index. To match query with the extracted set of trigrams Q, the set of
+// generated trigrams T for identifier (unqualified symbol name) should contain
+// all items of Q, i.e. Q ⊆ T.
+//
+// Trigram sets extracted from unqualified name and from query are different:
+// the set of query trigrams only contains consecutive sequences of three
+// characters (which is only a subset of all trigrams generated for an
+// identifier).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H
+
+#include "Token.h"
+
+#include <string>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+/// Returns list of unique fuzzy-search trigrams from unqualified symbol.
+///
+/// First, given Identifier (unqualified symbol name) is segmented using
+/// FuzzyMatch API and lowercased. After segmentation, the following technique
+/// is applied for generating trigrams: for each letter or digit in the input
+/// string the algorithms looks for the possible next and skip-1-next symbols
+/// which can be jumped to during fuzzy matching. Each combination of such three
+/// symbols is inserted into the result.
+///
+/// Trigrams can start at any character in the input. Then we can choose to move
+/// to the next character, move to the start of the next segment, or skip over a
+/// segment.
+///
+/// Note: the returned list of trigrams does not have duplicates, if any trigram
+/// belongs to more than one class it is only inserted once.
+std::vector<Token> generateIdentifierTrigrams(llvm::StringRef Identifier);
+
+/// Returns list of unique fuzzy-search trigrams given a query.
+///
+/// Query is segmented using FuzzyMatch API and downcasted to lowercase. Then,
+/// the simplest trigrams - sequences of three consecutive letters and digits
+/// are extracted and returned after deduplication.
+std::vector<Token> generateQueryTrigrams(llvm::StringRef Query);
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+#endif

clang-tools-extra/trunk/clangd/index/dex/Trigram.cpp

+//===--- Trigram.cpp - Trigram generation for Fuzzy Matching ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Trigram.h"
+#include "../../FuzzyMatch.h"
+#include "Token.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/StringExtras.h"
+
+#include <cctype>
+#include <queue>
+#include <string>
+
+using namespace llvm;
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+// FIXME(kbobyrev): Deal with short symbol symbol names. A viable approach would
+// be generating unigrams and bigrams here, too. This would prevent symbol index
+// from applying fuzzy matching on a tremendous number of symbols and allow
+// supplementary retrieval for short queries.
+//
+// Short names (total segment length <3 characters) are currently ignored.
+std::vector<Token> generateIdentifierTrigrams(llvm::StringRef Identifier) {
+  // Apply fuzzy matching text segmentation.
+  std::vector<CharRole> Roles(Identifier.size());
+  calculateRoles(Identifier,
+                 llvm::makeMutableArrayRef(Roles.data(), Identifier.size()));
+
+  std::string LowercaseIdentifier = Identifier.lower();
+
+  // For each character, store indices of the characters to which fuzzy matching
+  // algorithm can jump. There are 3 possible variants:
+  //
+  // * Next Tail - next character from the same segment
+  // * Next Head - front character of the next segment
+  // * Skip-1-Next Head - front character of the skip-1-next segment
+  //
+  // Next stores tuples of three indices in the presented order, if a variant is
+  // not available then 0 is stored.
+  std::vector<std::array<unsigned, 3>> Next(LowercaseIdentifier.size());
+  unsigned NextTail = 0, NextHead = 0, NextNextHead = 0;
+  for (int I = LowercaseIdentifier.size() - 1; I >= 0; --I) {
+    Next[I] = {{NextTail, NextHead, NextNextHead}};
+    NextTail = Roles[I] == Tail ? I : 0;
+    if (Roles[I] == Head) {
+      NextNextHead = NextHead;
+      NextHead = I;
+    }
+  }
+
+  DenseSet<Token> UniqueTrigrams;
+  std::array<char, 4> Chars;
+  for (size_t I = 0; I < LowercaseIdentifier.size(); ++I) {
+    // Skip delimiters.
+    if (Roles[I] != Head && Roles[I] != Tail)
+      continue;
+    for (const unsigned J : Next[I]) {
+      if (!J)
+        continue;
+      for (const unsigned K : Next[J]) {
+        if (!K)
+          continue;
+        Chars = {{LowercaseIdentifier[I], LowercaseIdentifier[J],
+                  LowercaseIdentifier[K], 0}};
+        auto Trigram = Token(Token::Kind::Trigram, Chars.data());
+        // Push unique trigrams to the result.
+        if (!UniqueTrigrams.count(Trigram)) {
+          UniqueTrigrams.insert(Trigram);
+        }
+      }
+    }
+  }
+
+  std::vector<Token> Result;
+  for (const auto &Trigram : UniqueTrigrams)
+    Result.push_back(Trigram);
+
+  return Result;
+}
+
+// FIXME(kbobyrev): Similarly, to generateIdentifierTrigrams, this ignores short
+// inputs (total segment length <3 characters).
+std::vector<Token> generateQueryTrigrams(llvm::StringRef Query) {
+  // Apply fuzzy matching text segmentation.
+  std::vector<CharRole> Roles(Query.size());
+  calculateRoles(Query, llvm::makeMutableArrayRef(Roles.data(), Query.size()));
+
+  std::string LowercaseQuery = Query.lower();
+
+  DenseSet<Token> UniqueTrigrams;
+  std::deque<char> Chars;
+
+  for (size_t I = 0; I < LowercaseQuery.size(); ++I) {
+    // If current symbol is delimiter, just skip it.
+    if (Roles[I] != Head && Roles[I] != Tail)
+      continue;
+
+    Chars.push_back(LowercaseQuery[I]);
+
+    if (Chars.size() > 3)
+      Chars.pop_front();
+    if (Chars.size() == 3) {
+      auto Trigram =
+          Token(Token::Kind::Trigram, std::string(begin(Chars), end(Chars)));
+      // Push unique trigrams to the result.
+      if (!UniqueTrigrams.count(Trigram)) {
+        UniqueTrigrams.insert(Trigram);
+      }
+    }
+  }
+
+  std::vector<Token> Result;
+  for (const auto &Trigram : UniqueTrigrams)
+    Result.push_back(Trigram);
+
+  return Result;
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang

clang-tools-extra/trunk/unittests/clangd/CMakeLists.txt

 
 add_extra_unittest(ClangdTests
   Annotations.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
+  DexIndexTests.cpp
   DraftStoreTests.cpp
-  FileIndexTests.cpp
   FileDistanceTests.cpp
+  FileIndexTests.cpp
   FindSymbolsTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   QualityTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SyncAPI.cpp
+  TUSchedulerTests.cpp
   TestFS.cpp
   TestTU.cpp
   ThreadingTests.cpp
   TraceTests.cpp
-  TUSchedulerTests.cpp
   URITests.cpp
   XRefsTests.cpp
   )
 
 target_link_libraries(ClangdTests
   PRIVATE
   clangAST
   clangBasic

clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp

+//===-- DexIndexTests.cpp  ----------------------------*- C++ -*-----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "index/dex/Token.h"
+#include "index/dex/Trigram.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+testing::Matcher<std::vector<Token>>
+trigramsAre(std::initializer_list<std::string> Trigrams) {
+  std::vector<Token> Tokens;
+  for (const auto &Symbols : Trigrams) {
+    Tokens.push_back(Token(Token::Kind::Trigram, Symbols));
+  }
+  return testing::UnorderedElementsAreArray(Tokens);
+}
+
+TEST(DexIndexTrigrams, IdentifierTrigrams) {
+  EXPECT_THAT(generateIdentifierTrigrams("X86"), trigramsAre({"x86"}));
+
+  EXPECT_THAT(generateIdentifierTrigrams("nl"), trigramsAre({}));
+
+  EXPECT_THAT(generateIdentifierTrigrams("clangd"),
+              trigramsAre({"cla", "lan", "ang", "ngd"}));
+
+  EXPECT_THAT(generateIdentifierTrigrams("abc_def"),
+              trigramsAre({"abc", "abd", "ade", "bcd", "bde", "cde", "def"}));
+
+  EXPECT_THAT(
+      generateIdentifierTrigrams("a_b_c_d_e_"),
+      trigramsAre({"abc", "abd", "acd", "ace", "bcd", "bce", "bde", "cde"}));
+
+  EXPECT_THAT(
+      generateIdentifierTrigrams("unique_ptr"),
+      trigramsAre({"uni", "unp", "upt", "niq", "nip", "npt", "iqu", "iqp",
+                   "ipt", "que", "qup", "qpt", "uep", "ept", "ptr"}));
+
+  EXPECT_THAT(generateIdentifierTrigrams("TUDecl"),
+              trigramsAre({"tud", "tde", "ude", "dec", "ecl"}));
+
+  EXPECT_THAT(generateIdentifierTrigrams("IsOK"),
+              trigramsAre({"iso", "iok", "sok"}));
+
+  EXPECT_THAT(generateIdentifierTrigrams("abc_defGhij__klm"),
+              trigramsAre({
+                  "abc", "abd", "abg", "ade", "adg", "adk", "agh", "agk", "bcd",
+                  "bcg", "bde", "bdg", "bdk", "bgh", "bgk", "cde", "cdg", "cdk",
+                  "cgh", "cgk", "def", "deg", "dek", "dgh", "dgk", "dkl", "efg",
+                  "efk", "egh", "egk", "ekl", "fgh", "fgk", "fkl", "ghi", "ghk",
+                  "gkl", "hij", "hik", "hkl", "ijk", "ikl", "jkl", "klm",
+              }));
+}
+
+TEST(DexIndexTrigrams, QueryTrigrams) {
+  EXPECT_THAT(generateQueryTrigrams("X86"), trigramsAre({"x86"}));
+
+  EXPECT_THAT(generateQueryTrigrams("nl"), trigramsAre({}));
+
+  EXPECT_THAT(generateQueryTrigrams("clangd"),
+              trigramsAre({"cla", "lan", "ang", "ngd"}));
+
+  EXPECT_THAT(generateQueryTrigrams("abc_def"),
+              trigramsAre({"abc", "bcd", "cde", "def"}));
+
+  EXPECT_THAT(generateQueryTrigrams("a_b_c_d_e_"),
+              trigramsAre({"abc", "bcd", "cde"}));
+
+  EXPECT_THAT(generateQueryTrigrams("unique_ptr"),
+              trigramsAre({"uni", "niq", "iqu", "que", "uep", "ept", "ptr"}));
+
+  EXPECT_THAT(generateQueryTrigrams("TUDecl"),
+              trigramsAre({"tud", "ude", "dec", "ecl"}));
+
+  EXPECT_THAT(generateQueryTrigrams("IsOK"), trigramsAre({"iso", "sok"}));
+
+  EXPECT_THAT(generateQueryTrigrams("abc_defGhij__klm"),
+              trigramsAre({"abc", "bcd", "cde", "def", "efg", "fgh", "ghi",
+                           "hij", "ijk", "jkl", "klm"}));
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang