[clangd] Simplify Dex query tree logic and fix missing-posting-list bug

[sammccall]

Summary

The bug being fixed: when a posting list doesn't exist in the index, it
was previously just dropped from the query rather than being treated as
empty. Now that we have the FALSE iterator, we can use it instead.

The query tree logic previously had a bunch of special cases to detect whether
subtrees are empty. Now we just naively build the whole tree, and rely
on the query optimizations to drop the trivial parts.

Finally, there was a bug in trigram generation: the empty query would
generate a single trigram "$$$" instead of no trigrams.
This had no effect (there was no posting list, so the other bug
cancelled it out). But we now have to fix this bug too.

[sammccall]

Rebase, and enable test that is now waiting on this patch.

[ilya-biryukov]

Overall LGTM, just a quick question to make sure I get what's going on.

clangd/index/dex/Dex.cpp

184

Why do we still need to push all() with a trivial boost for Scope.empty()? Is this a legacy way to specify "all scopes"?

[ilya-biryukov]

Putting a stamp, assuming is answer is "yes, it's a legacy way to specify all scopes"

[sammccall]

clangd/index/dex/Dex.cpp

184

Yeah. This is specified in FuzzyFindRequest, with a FIXME to remove as we have explicit AnyScope (but we still have code relying on it for now).

clangd/index/dex/Dex.h

public:
 
   void refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
   size_t estimateMemoryUsage() const override;
 
 private:
   void buildIndex();
+  std::unique_ptr<Iterator> iterator(const Token &Tok) const;
 
   /// Stores symbols sorted in the descending order of symbol quality..
   std::vector<const Symbol *> Symbols;
   /// SymbolQuality[I] is the quality of Symbols[I].
   std::vector<float> SymbolQuality;
   llvm::DenseMap<SymbolID, const Symbol *> LookupTable;
   /// Inverted index is a mapping from the search token to the posting list,
   /// which contains all items which can be characterized by such search token.

clangd/index/dex/Dex.cpp

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(
+std::unique_ptr<Iterator> createFileProximityIterator(
     llvm::ArrayRef<std::string> ProximityPaths,
     llvm::ArrayRef<std::string> URISchemes,
     const llvm::DenseMap<Token, PostingList> &InvertedIndex,
     const Corpus &Corpus) {
   std::vector<std::unique_ptr<Iterator>> BoostingIterators;
   // Deduplicate parent URIs extracted from the ProximityPaths.
   llvm::StringSet<> ParentURIs;
   llvm::StringMap<SourceParams> Sources;
for (const auto &ParentURI : ParentURIs.keys()) {
     const auto It = InvertedIndex.find(Tok);
     if (It != InvertedIndex.end()) {
       // FIXME(kbobyrev): Append LIMIT on top of every BOOST iterator.
       PathProximitySignals.SymbolURI = ParentURI;
       BoostingIterators.push_back(Corpus.boost(
           It->second.iterator(&It->first), PathProximitySignals.evaluate()));
     }
   }
-  return BoostingIterators;
+  BoostingIterators.push_back(Corpus.all());
+  return Corpus.unionOf(std::move(BoostingIterators));
 }
 
 } // namespace
 
 void Dex::buildIndex() {
   this->Corpus = dex::Corpus(Symbols.size());
   std::vector<std::pair<float, const Symbol *>> ScoredSymbols(Symbols.size());
 
void Dex::buildIndex() {
   }
 
   // Convert lists of items to posting lists.
   for (const auto &TokenToPostingList : TempInvertedIndex)
     InvertedIndex.insert(
         {TokenToPostingList.first, PostingList(TokenToPostingList.second)});
 }
 
+std::unique_ptr<Iterator> Dex::iterator(const Token &Tok) const {
+  auto It = InvertedIndex.find(Tok);
+  return It == InvertedIndex.end() ? Corpus.none()
+                                   : It->second.iterator(&It->first);
+}
+
 /// Constructs iterators over tokens extracted from the query and exhausts it
 /// while applying Callback to each symbol in the order of decreasing quality
 /// of the matched symbols.
 bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
                     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
   trace::Span Tracer("Dex fuzzyFind");
   FuzzyMatcher Filter(Req.Query);
   // For short queries we use specialized trigrams that don't yield all results.
   // Prevent clients from postfiltering them for longer queries.
   bool More = !Req.Query.empty() && Req.Query.size() < 3;
 
-  std::vector<std::unique_ptr<Iterator>> TopLevelChildren;
+  std::vector<std::unique_ptr<Iterator>> Criteria;
   const auto TrigramTokens = generateQueryTrigrams(Req.Query);
 
   // Generate query trigrams and construct AND iterator over all query
   // trigrams.
   std::vector<std::unique_ptr<Iterator>> TrigramIterators;
-  for (const auto &Trigram : TrigramTokens) {
-    const auto It = InvertedIndex.find(Trigram);
-    if (It != InvertedIndex.end())
-      TrigramIterators.push_back(It->second.iterator(&It->first));
-  }
-  if (!TrigramIterators.empty())
-    TopLevelChildren.push_back(Corpus.intersect(move(TrigramIterators)));
+  for (const auto &Trigram : TrigramTokens)
+    TrigramIterators.push_back(iterator(Trigram));
+  Criteria.push_back(Corpus.intersect(move(TrigramIterators)));
 
   // Generate scope tokens for search query.
   std::vector<std::unique_ptr<Iterator>> ScopeIterators;
-  for (const auto &Scope : Req.Scopes) {
-    Token Tok(Token::Kind::Scope, Scope);
-    const auto It = InvertedIndex.find(Tok);
-    if (It != InvertedIndex.end())
-      ScopeIterators.push_back(It->second.iterator(&It->first));
-  }
-  if (Req.AnyScope)
+  for (const auto &Scope : Req.Scopes)
+    ScopeIterators.push_back(iterator(Token(Token::Kind::Scope, Scope)));
+  if (Req.AnyScope || /*legacy*/ Req.Scopes.empty())
     ScopeIterators.push_back(
         Corpus.boost(Corpus.all(), ScopeIterators.empty() ? 1.0 : 0.2));
+  Criteria.push_back(Corpus.unionOf(move(ScopeIterators)));
 
-  // Add OR iterator for scopes if there are any Scope Iterators.
-  if (!ScopeIterators.empty())
-    TopLevelChildren.push_back(Corpus.unionOf(move(ScopeIterators)));
-
-  // Add proximity paths boosting.
-  auto BoostingIterators = createFileProximityIterators(
-      Req.ProximityPaths, URISchemes, InvertedIndex, Corpus);
-  // 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(Corpus.all());
-    TopLevelChildren.push_back(Corpus.unionOf(move(BoostingIterators)));
-  }
+  // Add proximity paths boosting (all symbols, some boosted).
+  Criteria.push_back(createFileProximityIterator(Req.ProximityPaths, URISchemes,
+                                                 InvertedIndex, Corpus));
 
   if (Req.RestrictForCodeCompletion)
-    TopLevelChildren.push_back(
-        InvertedIndex.find(RestrictedForCodeCompletion)
-            ->second.iterator(&RestrictedForCodeCompletion));
+    Criteria.push_back(iterator(RestrictedForCodeCompletion));
 
   // Use TRUE iterator if both trigrams and scopes from the query are not
   // present in the symbol index.
-  auto QueryIterator = TopLevelChildren.empty()
-                           ? Corpus.all()
-                           : Corpus.intersect(move(TopLevelChildren));
+  auto Root = Corpus.intersect(move(Criteria));
   // 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
-  // using 100x of the requested number might not be good in practice, e.g.
-  // when the requested number of items is small.
-  auto Root = Req.Limit ? Corpus.limit(move(QueryIterator), *Req.Limit * 100)
-                        : move(QueryIterator);
+  // FIXME(kbobyrev): Tune this ratio.
+  if (Req.Limit)
+    Root = Corpus.limit(move(Root), *Req.Limit * 100);
   SPAN_ATTACH(Tracer, "query", llvm::to_string(*Root));
   vlog("Dex query tree: {0}", *Root);
 
   using IDAndScore = std::pair<DocID, float>;
   std::vector<IDAndScore> IDAndScores = consume(*Root);
 
   auto Compare = [](const IDAndScore &LHS, const IDAndScore &RHS) {
     return LHS.second > RHS.second;

clangd/index/dex/Iterator.h

public:
   /// Inspect iterator type, used internally for optimizing query trees.
   enum class Kind { And, Or, True, False, Other };
   Kind kind() const { return MyKind; }
 
 protected:
   Iterator(Kind MyKind = Kind::Other) : MyKind(MyKind) {}
 
 private:
-  Kind MyKind;
   virtual llvm::raw_ostream &dump(llvm::raw_ostream &OS) const = 0;
   Kind MyKind;
 };
 
 /// Advances the iterator until it is exhausted. Returns pairs of document IDs
 /// with the corresponding boosting score.
 ///
 /// Boosting can be seen as a compromise between retrieving too many items and

clangd/index/dex/Trigram.cpp

if (Roles[I] == Head) {
       Add({LowercaseIdentifier[0], LowercaseIdentifier[I]});
       break;
     }
 
   return {UniqueTrigrams.begin(), UniqueTrigrams.end()};
 }
 
 std::vector<Token> generateQueryTrigrams(llvm::StringRef Query) {
+  if (Query.empty())
+    return {};
   std::string LowercaseQuery = Query.lower();
   if (Query.size() < 3) // short-query trigrams only
     return {Token(Token::Kind::Trigram, LowercaseQuery)};
 
   // Apply fuzzy matching text segmentation.
   std::vector<CharRole> Roles(Query.size());
   calculateRoles(Query, llvm::makeMutableArrayRef(Roles.data(), Query.size()));
 

unittests/clangd/DexTests.cpp

EXPECT_THAT(
                    "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"}));
 
+  EXPECT_THAT(generateQueryTrigrams(""), trigramsAre({}));
   EXPECT_THAT(generateQueryTrigrams("_"), trigramsAre({"_"}));
   EXPECT_THAT(generateQueryTrigrams("__"), trigramsAre({"__"}));
   EXPECT_THAT(generateQueryTrigrams("___"), trigramsAre({}));
 
   EXPECT_THAT(generateQueryTrigrams("X86"), trigramsAre({"x86"}));
 
   EXPECT_THAT(generateQueryTrigrams("clangd"),
               trigramsAre({"cla", "lan", "ang", "ngd"}));
auto I = Dex::build(
       RefSlab(), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.Limit = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
-// TODO(sammccall): enable after D52796 bugfix.
-#if 0
 TEST(DexTest, ShortQuery) {
   auto I =
       Dex::build(generateSymbols({"OneTwoThreeFour"}), RefSlab(), URISchemes);
   FuzzyFindRequest Req;
   bool Incomplete;
 
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour"));
   EXPECT_FALSE(Incomplete) << "Empty string is not a short query";
 
   Req.Query = "t";
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre());
   EXPECT_TRUE(Incomplete) << "Short queries have different semantics";
 
   Req.Query = "tt";
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre());
   EXPECT_TRUE(Incomplete) << "Short queries have different semantics";
 
   Req.Query = "ttf";
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour"));
   EXPECT_FALSE(Incomplete) << "3-char string is not a short query";
 }
-#endif
 
 TEST(DexTest, MatchQualifiedNamesWithoutSpecificScope) {
   auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
                       URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "y";
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
 }

 TEST(DexTest, IgnoreCases) {
   auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 
+TEST(DexTest, UnknownPostingList) {
+  // Regression test: we used to ignore unknown scopes and accept any symbol.
+  auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(),
+                      URISchemes);
+  FuzzyFindRequest Req;
+  Req.Scopes = {"ns2::"};
+  EXPECT_THAT(match(*I, Req), UnorderedElementsAre());
+}
+
 TEST(DexTest, Lookup) {
   auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(), URISchemes);
   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());