[clangd] Force Dex to respect symbol collector flags

[kbobyrev]

Summary

Dex should utilize FuzzyFindRequest.RestrictForCodeCompletion flags and omit symbols not meant for code completion when asked for it.

The measurements below were conducted with setting FuzzyFindRequest.RestrictForCodeCompletion to true (so that it's more realistic). Sadly, the average latency goes down, I suspect that is mostly because of the empty queries where the number of posting lists is critical.

Metrics	Before	After	Relative difference
Cumulative query latency (7000 FuzzyFindRequests over LLVM static index)	6182735043 ns	7202442053 ns	+16%
Whole Index size	81.24 MB	81.79 MB	+0.6%

Out of 292252 symbols collected from LLVM codebase 136926 appear to be restricted for code completion.

[ioeric]

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

27 ↗

(On Diff #166468)

Why do we need NotRestrictedForCodeCompletion token? If RestrictedForCodeCompletion is false, all symbols can match.

[kbobyrev]

RestirctForCodeCompletion and !RestrictForCodeCompletion are not mutually exclusive.

[ioeric]

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

184 ↗

(On Diff #166474)

nit: the comment seems trivial from the if-condition. Maybe remove?

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

594 ↗

(On Diff #166474)

I think the symbol flags should be set before both requests.

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

 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
 namespace {
 
+// Mark symbols which are can be used for code completion.
+static const Token RestrictedForCodeCompletion =
+    Token(Token::Kind::Sentinel, "Restricted For Code Completion");
+
 // Returns the tokens which are given symbol's characteristics. Currently, the
 // generated tokens only contain fuzzy matching trigrams and symbol's scope,
 // but in the future this will also return path proximity tokens and other
 // types of tokens such as symbol type (if applicable).
 // Returns the tokens which are given symbols's characteristics. For example,
 // trigrams and scopes.
 // FIXME(kbobyrev): Support more token types:
 // * Types
 // * Namespace proximity
 std::vector<Token> generateSearchTokens(const Symbol &Sym) {
   std::vector<Token> Result = generateIdentifierTrigrams(Sym.Name);
   Result.emplace_back(Token::Kind::Scope, Sym.Scope);
   // Skip token generation for symbols with unknown declaration location.
   if (!Sym.CanonicalDeclaration.FileURI.empty())
     for (const auto &ProximityURI :
          generateProximityURIs(Sym.CanonicalDeclaration.FileURI))
       Result.emplace_back(Token::Kind::ProximityURI, ProximityURI);
+  if (Sym.Flags & Symbol::IndexedForCodeCompletion)
+    Result.emplace_back(RestrictedForCodeCompletion);
   return Result;
 }
 
 // Constructs BOOST iterators for Path Proximities.
 std::vector<std::unique_ptr<Iterator>> createFileProximityIterators(
     llvm::ArrayRef<std::string> ProximityPaths,
     llvm::ArrayRef<std::string> URISchemes,
     const llvm::DenseMap<Token, PostingList> &InvertedIndex) {
bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
   // Boosting iterators do not actually filter symbols. In order to preserve
   // the validity of resulting query, TRUE iterator should be added along
   // BOOSTs.
   if (!BoostingIterators.empty()) {
     BoostingIterators.push_back(createTrue(Symbols.size()));
     TopLevelChildren.push_back(createOr(move(BoostingIterators)));
   }
 
+  if (Req.RestrictForCodeCompletion)
+    TopLevelChildren.push_back(
+        InvertedIndex.find(RestrictedForCodeCompletion)->second.iterator());
+
   // Use TRUE iterator if both trigrams and scopes from the query are not
   // present in the symbol index.
   auto QueryIterator = TopLevelChildren.empty()
                            ? createTrue(Symbols.size())
                            : createAnd(move(TopLevelChildren));
   // Retrieve more items than it was requested: some of  the items with high
   // final score might not be retrieved otherwise.
   // FIXME(kbobyrev): Pre-scoring retrieval threshold should be adjusted as

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

TEST(DexTest, Lookup) {
   EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc"));
   EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
               UnorderedElementsAre("ns::abc", "ns::xyz"));
   EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}),
               UnorderedElementsAre("ns::xyz"));
   EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre());
 }
 
+TEST(DexTest, SymbolIndexOptionsFilter) {
+  auto CodeCompletionSymbol = symbol("Completion");
+  auto NonCodeCompletionSymbol = symbol("NoCompletion");
+  CodeCompletionSymbol.Flags = Symbol::SymbolFlag::IndexedForCodeCompletion;
+  NonCodeCompletionSymbol.Flags = Symbol::SymbolFlag::None;
+  std::vector<Symbol> Symbols{CodeCompletionSymbol, NonCodeCompletionSymbol};
+  Dex I(Symbols, URISchemes);
+  FuzzyFindRequest Req;
+  Req.RestrictForCodeCompletion = false;
+  EXPECT_THAT(match(I, Req), ElementsAre("Completion", "NoCompletion"));
+  Req.RestrictForCodeCompletion = true;
+  EXPECT_THAT(match(I, Req), ElementsAre("Completion"));
+}
+
 TEST(DexTest, ProximityPathsBoosting) {
   auto RootSymbol = symbol("root::abc");
   RootSymbol.CanonicalDeclaration.FileURI = "unittest:///file.h";
   auto CloseSymbol = symbol("close::abc");
   CloseSymbol.CanonicalDeclaration.FileURI = "unittest:///a/b/c/d/e/f/file.h";
 
   std::vector<Symbol> Symbols{CloseSymbol, RootSymbol};
   Dex I(Symbols, URISchemes);