[clangd] Generate better incomplete bigrams for the Dex index

[kbobyrev]

Summary

Currently, the query trigram generator would simply yield u_p trigram for the u_p query. This is not optimal, since the user is likely to try matching two heads with this query and this patch addresses the issue.

[kbobyrev]

Treat leading underscores as additional signals and don't extract two heads in that case.

[ioeric]

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

324

I'm not sure if this is correct. If users have explicitly typed _, they are likely to want a _ there. You mentioned in the patch summary that users might want to match two heads with this. Could you provide an example?

[kbobyrev]

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

324

The particular example I had on my mind was unique_ptr. Effectively, if the query is SC then StrCat would be matched (because the incomplete trigram would be sc$ and two heads from the symbol identifier would also yield sc$), but for u_p, unique_ptr is currently not matched.

On the other hand, if there's something like m_field and user types mf or m_f it will be matched in both cases, because m_field yields mf$ in the index build stage, so this change doesn't decrease code completion quality for such cases.

[ioeric]

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

324

The problem is that u_p can now match upXXX with up$, which might be a bit surprising for users.

It seems to me that another way way to handle this is to generate u_p trigram for unique_ptr. Have we considered including separators like _ in trigrams?

[kbobyrev]

As Eric suggested, such change might reduce the quality of code completion. A more generic approach is yet to be investigated and requires significantly more time resources, we should try it after we get other parts of the index to work as expected.

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

324

I agree, this might be a better solution. Anyway, this seems that it's probably too early to optimize for such a general case like you suggested. I believe, word bounds might help here, but we should probably try them after we have a fully-functional index upstream.

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

 /// 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.
 ///
 /// For short queries (less than 3 characters with Head or Tail roles in Fuzzy
 /// Matching segmentation) this returns a single trigram with the first
-/// characters (up to 3) to perfrom prefix match.
+/// characters (up to 3) to perfrom prefix match. However, if the query is short
+/// but it contains two HEAD symbols then the returned trigram would be an
+/// incomplete bigram with those two HEADs (unless query starts with '_' which
+/// is treated as an additional information). This would help to match
+/// "unique_ptr" and similar symbols with "u_p" query
 std::vector<Token> generateQueryTrigrams(llvm::StringRef Query);
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang
 
 #endif

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

 
 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()));
 
   // Additional pass is necessary to count valid identifier characters.
   // Depending on that, this function might return incomplete trigram.
+  unsigned Heads = 0;
   unsigned ValidSymbolsCount = 0;
-  for (size_t I = 0; I < Roles.size(); ++I)
-    if (Roles[I] == Head || Roles[I] == Tail)
+  for (size_t I = 0; I < Roles.size(); ++I) {
+    if (Roles[I] == Head) {
+      ++ValidSymbolsCount;
+      ++Heads;
+    } else if (Roles[I] == Tail) {
       ++ValidSymbolsCount;
+    }
+  }
 
   std::string LowercaseQuery = Query.lower();
 
   DenseSet<Token> UniqueTrigrams;
 
   // If the number of symbols which can form fuzzy matching trigram is not
   // sufficient, generate a single incomplete trigram for query.
   if (ValidSymbolsCount < 3) {
-    std::string Chars =
-        LowercaseQuery.substr(0, std::min<size_t>(3UL, Query.size()));
+    std::string Chars;
+    // If the query is not long enough to form a trigram but contains two heads
+    // the returned trigram should be "xy$" where "x" and "y" are the heads.
+    // This might be particulary important for cases like "u_p" to match
+    // "unique_ptr" and similar symbols from the C++ Standard Library.
+    if (Heads == 2 && !Query.startswith("_")) {
+      for (size_t I = 0; I < LowercaseQuery.size(); ++I)
+        if (Roles[I] == Head)
+          Chars += LowercaseQuery[I];
+
+      Chars += END_MARKER;
+    } else {
+      Chars = LowercaseQuery.substr(0, std::min<size_t>(3UL, Query.size()));
       Chars.append(3 - Chars.size(), END_MARKER);
+    }
     UniqueTrigrams.insert(Token(Token::Kind::Trigram, Chars));
   } else {
     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;
 

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

TEST(DexIndexTrigrams, QueryTrigrams) {
   EXPECT_THAT(generateQueryTrigrams("c"), trigramsAre({"c$$"}));
   EXPECT_THAT(generateQueryTrigrams("cl"), trigramsAre({"cl$"}));
   EXPECT_THAT(generateQueryTrigrams("cla"), trigramsAre({"cla"}));
 
   EXPECT_THAT(generateQueryTrigrams("_"), trigramsAre({"_$$"}));
   EXPECT_THAT(generateQueryTrigrams("__"), trigramsAre({"__$"}));
   EXPECT_THAT(generateQueryTrigrams("___"), trigramsAre({"___"}));
 
+  EXPECT_THAT(generateQueryTrigrams("u_p"), trigramsAre({"up$"}));
+  EXPECT_THAT(generateQueryTrigrams("_u_p"), trigramsAre({"_u_"}));
+
   EXPECT_THAT(generateQueryTrigrams("X86"), trigramsAre({"x86"}));
 
   EXPECT_THAT(generateQueryTrigrams("clangd"),
               trigramsAre({"cla", "lan", "ang", "ngd"}));
 
   EXPECT_THAT(generateQueryTrigrams("abc_def"),
               trigramsAre({"abc", "bcd", "cde", "def"}));