[clangd] Remove one-segment-skipping from Dex trigrams.

[sammccall]

Summary

Currently queries like "ab" can match identifiers like a_yellow_bee.
The value of allowing this for exactly one segment but no more seems dubious.
It costs ~3% of overall ram (~9% of posting list ram) and some quality.

[ioeric]

lgtm

clangd/index/dex/Trigram.cpp

38–39

This can be removed now?

clangd/index/dex/Trigram.h

 namespace clangd {
 namespace dex {
 
 /// Returns list of unique fuzzy-search trigrams from unqualified symbol.
 /// The trigrams give the 3-character query substrings this symbol can match.
 ///
 /// The symbol's name is broken into segments, e.g. "FooBar" has two segments.
 /// 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 stop.
+/// to the next character or to the start of the next segment.
 ///
 /// Short trigrams (length 1-2) are used for short queries. These are:
 ///  - prefixes of the identifier, of length 1 and 2
 ///  - the first character + next head character
 ///
 /// For "FooBar" we get the following trigrams:
 ///  {f, fo, fb, foo, fob, fba, oob, oba, bar}.
 ///

clangd/index/dex/Trigram.cpp

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;
+  unsigned NextTail = 0, NextHead = 0;
   for (int I = LowercaseIdentifier.size() - 1; I >= 0; --I) {
-    Next[I] = {{NextTail, NextHead, NextNextHead}};
+    Next[I] = {{NextTail, NextHead}};
     NextTail = Roles[I] == Tail ? I : 0;
     if (Roles[I] == Head) {
-      NextNextHead = NextHead;
       NextHead = I;
     }
   }
 
   DenseSet<Token> UniqueTrigrams;
 
   auto Add = [&](std::string Chars) {
     UniqueTrigrams.insert(Token(Token::Kind::Trigram, Chars));

unittests/clangd/DexTests.cpp

TEST(DexTrigrams, IdentifierTrigrams) {
   EXPECT_THAT(generateIdentifierTrigrams("clangd"),
               trigramsAre({"c", "cl", "cla", "lan", "ang", "ngd"}));
 
   EXPECT_THAT(generateIdentifierTrigrams("abc_def"),
               trigramsAre({"a", "ab", "ad", "abc", "abd", "ade", "bcd", "bde",
                            "cde", "def"}));
 
   EXPECT_THAT(generateIdentifierTrigrams("a_b_c_d_e_"),
-              trigramsAre({"a", "a_", "ab", "abc", "abd", "acd", "ace", "bcd",
-                           "bce", "bde", "cde"}));
+              trigramsAre({"a", "a_", "ab", "abc", "bcd", "cde"}));
 
   EXPECT_THAT(generateIdentifierTrigrams("unique_ptr"),
               trigramsAre({"u", "un", "up", "uni", "unp", "upt", "niq", "nip",
                            "npt", "iqu", "iqp", "ipt", "que", "qup", "qpt",
                            "uep", "ept", "ptr"}));
 
   EXPECT_THAT(
       generateIdentifierTrigrams("TUDecl"),
       trigramsAre({"t", "tu", "td", "tud", "tde", "ude", "dec", "ecl"}));
 
   EXPECT_THAT(generateIdentifierTrigrams("IsOK"),
               trigramsAre({"i", "is", "io", "iso", "iok", "sok"}));
 
-  auto X = generateIdentifierTrigrams("abc_defGhij__klm");
   EXPECT_THAT(
       generateIdentifierTrigrams("abc_defGhij__klm"),
-      trigramsAre({"a",   "ab",  "ad",  "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",
+      trigramsAre({"a",   "ab",  "ad",  "abc", "abd", "ade", "adg", "bcd",
+                   "bde", "bdg", "cde", "cdg", "def", "deg", "dgh", "dgk",
+                   "efg", "egh", "egk", "fgh", "fgk", "ghi", "ghk", "gkl",
                    "hij", "hik", "hkl", "ijk", "ikl", "jkl", "klm"}));
 }
 
 TEST(DexTrigrams, QueryTrigrams) {
   EXPECT_THAT(generateQueryTrigrams("c"), trigramsAre({"c"}));
   EXPECT_THAT(generateQueryTrigrams("cl"), trigramsAre({"cl"}));
   EXPECT_THAT(generateQueryTrigrams("cla"), trigramsAre({"cla"}));