[clangd] Dex iterator printer shows query structure, not iterator state.

[sammccall]

Summary

This makes it suitable for logging (which immediately found a bug, to
be fixed in the next patch...)

[ioeric]

unittests/clangd/DexTests.cpp

239

nit: it's not obvious in this test case that [1 3 5] and T=L2 are both posting lists.

clangd/index/dex/Dex.cpp

 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
 #include "Trace.h"
 #include "index/Index.h"
 #include "index/dex/Iterator.h"
 #include "llvm/ADT/StringSet.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include <algorithm>
 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
 namespace {
std::vector<std::unique_ptr<Iterator>> createFileProximityIterators(
   // DistanceCalculator will find the shortest distance from ProximityPaths to
   // any URI extracted from the ProximityPaths.
   URIDistance DistanceCalculator(Sources);
   PathProximitySignals.FileProximityMatch = &DistanceCalculator;
   // Try to build BOOST iterator for each Proximity Path provided by
   // ProximityPaths. Boosting factor should depend on the distance to the
   // Proximity Path: the closer processed path is, the higher boosting factor.
   for (const auto &ParentURI : ParentURIs.keys()) {
-    const auto It =
-        InvertedIndex.find(Token(Token::Kind::ProximityURI, ParentURI));
+    Token Tok(Token::Kind::ProximityURI, ParentURI);
+    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(
-          createBoost(It->second.iterator(), PathProximitySignals.evaluate()));
+      BoostingIterators.push_back(createBoost(It->second.iterator(&It->first),
+                                              PathProximitySignals.evaluate()));
     }
   }
   return BoostingIterators;
 }
 
 } // namespace
 
 void Dex::buildIndex() {

 
 /// 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.");
-  // FIXME: attach the query tree to the trace span.
   trace::Span Tracer("Dex fuzzyFind");
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
 
   std::vector<std::unique_ptr<Iterator>> TopLevelChildren;
   const auto TrigramTokens = generateIdentifierTrigrams(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());
+      TrigramIterators.push_back(It->second.iterator(&It->first));
   }
   if (!TrigramIterators.empty())
     TopLevelChildren.push_back(createAnd(move(TrigramIterators)));
 
   // Generate scope tokens for search query.
   std::vector<std::unique_ptr<Iterator>> ScopeIterators;
   for (const auto &Scope : Req.Scopes) {
-    const auto It = InvertedIndex.find(Token(Token::Kind::Scope, Scope));
+    Token Tok(Token::Kind::Scope, Scope);
+    const auto It = InvertedIndex.find(Tok);
     if (It != InvertedIndex.end())
-      ScopeIterators.push_back(It->second.iterator());
+      ScopeIterators.push_back(It->second.iterator(&It->first));
   }
   if (Req.AnyScope)
     ScopeIterators.push_back(createBoost(createTrue(Symbols.size()),
                                          ScopeIterators.empty() ? 1.0 : 0.2));
 
   // Add OR iterator for scopes if there are any Scope Iterators.
   if (!ScopeIterators.empty())
     TopLevelChildren.push_back(createOr(move(ScopeIterators)));
 
   // Add proximity paths boosting.
   auto BoostingIterators = createFileProximityIterators(
       Req.ProximityPaths, URISchemes, InvertedIndex);
   // 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());
+        InvertedIndex.find(RestrictedForCodeCompletion)
+            ->second.iterator(&RestrictedForCodeCompletion));
 
   // 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
   // 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 ? createLimit(move(QueryIterator), *Req.Limit * 100)
                         : move(QueryIterator);
+  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;
   };
   TopN<IDAndScore, decltype(Compare)> Top(

clangd/index/dex/Iterator.cpp

float consume() override {
     assert(!reachedEnd() && "TRUE iterator can't consume() at the end.");
     return DEFAULT_BOOST_SCORE;
   }
 
   size_t estimateSize() const override { return Size; }
 
 private:
   llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
-    OS << "(TRUE {" << Index << "} out of " << Size << ")";
-    return OS;
+    return OS << "true";
   }
 
   DocID Index = 0;
   /// Size of the underlying virtual PostingList.
   DocID Size;
 };
 
 /// Boost iterator is a wrapper around its child which multiplies scores of
public:
   DocID peek() const override { return Child->peek(); }
 
   float consume() override { return Child->consume() * Factor; }
 
   size_t estimateSize() const override { return Child->estimateSize(); }
 
 private:
   llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
-    OS << "(BOOST " << Factor << ' ' << *Child << ')';
-    return OS;
+    return OS << "(* " << Factor << ' ' << *Child << ')';
   }
 
   std::unique_ptr<Iterator> Child;
   float Factor;
 };
 
 /// This iterator limits the number of items retrieved from the child iterator
 /// on top of the query tree. To ensure that query tree with LIMIT iterators
public:
   }
 
   size_t estimateSize() const override {
     return std::min(Child->estimateSize(), Limit);
   }
 
 private:
   llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
-    OS << "(LIMIT " << Limit << '(' << ItemsLeft << ") " << *Child << ')';
-    return OS;
+    return OS << "(LIMIT " << Limit << " " << *Child << ')';
   }
 
   std::unique_ptr<Iterator> Child;
   size_t Limit;
   size_t ItemsLeft;
 };
 
 } // end namespace

clangd/index/dex/PostingList.h

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace dex {
-
-class Iterator;
+struct Token;
 
 /// NOTE: This is an implementation detail.
 ///
 /// Chunk is a fixed-width piece of PostingList which contains the first DocID
 /// in uncompressed format (Head) and delta-encoded Payload. It can be
 /// decompressed upon request.
 struct Chunk {
   /// Keep sizeof(Chunk) == 32.

 /// are stored in underlying chunks. Compression saves memory at a small cost
 /// in access time, which is still fast enough in practice.
 class PostingList {
 public:
   explicit PostingList(llvm::ArrayRef<DocID> Documents);
 
   /// Constructs DocumentIterator over given posting list. DocumentIterator will
   /// go through the chunks and decompress them on-the-fly when necessary.
-  std::unique_ptr<Iterator> iterator() const;
+  /// If given, Tok is only used for the string representation.
+  std::unique_ptr<Iterator> iterator(const Token *Tok = nullptr) const;
 
   /// Returns in-memory size of external storage.
   size_t bytes() const { return Chunks.capacity() * sizeof(Chunk); }
 
 private:
   const std::vector<Chunk> Chunks;
 };
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H

clangd/index/dex/PostingList.cpp

 //===--- PostingList.cpp - Symbol identifiers storage interface -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PostingList.h"
 #include "Iterator.h"
+#include "Token.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MathExtras.h"
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
 namespace {
 
 /// Implements iterator of PostingList chunks. This requires iterating over two
 /// levels: the first level iterator iterates over the chunks and decompresses
 /// them on-the-fly when the contents of chunk are to be seen.
 class ChunkIterator : public Iterator {
 public:
-  explicit ChunkIterator(llvm::ArrayRef<Chunk> Chunks)
-      : Chunks(Chunks), CurrentChunk(Chunks.begin()) {
+  explicit ChunkIterator(const Token *Tok, llvm::ArrayRef<Chunk> Chunks)
+      : Tok(Tok), Chunks(Chunks), CurrentChunk(Chunks.begin()) {
     if (!Chunks.empty()) {
       DecompressedChunk = CurrentChunk->decompress();
       CurrentID = DecompressedChunk.begin();
     }
   }
 
   bool reachedEnd() const override { return CurrentChunk == Chunks.end(); }
 
public:
   }
 
   size_t estimateSize() const override {
     return Chunks.size() * ApproxEntriesPerChunk;
   }
 
 private:
   llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    if (Tok != nullptr)
+      return OS << *Tok;
     OS << '[';
-    if (CurrentChunk != Chunks.begin() ||
-        (CurrentID != DecompressedChunk.begin() && !DecompressedChunk.empty()))
-      OS << "... ";
-    OS << (reachedEnd() ? "END" : std::to_string(*CurrentID));
-    if (!reachedEnd() && CurrentID < DecompressedChunk.end() - 1)
-      OS << " ...";
-    OS << ']';
-    return OS;
+    const char *Sep = "";
+    for (const Chunk &C : Chunks)
+      for (const DocID Doc : C.decompress()) {
+        OS << Sep << Doc;
+        Sep = " ";
+      }
+    return OS << ']';
   }
 
   /// If the cursor is at the end of a chunk, place it at the start of the next
   /// chunk.
   void normalizeCursor() {
     // Invariant is already established if examined chunk is not exhausted.
     if (CurrentID != std::end(DecompressedChunk))
       return;
if ((CurrentChunk != Chunks.end() - 1) &&
           CurrentChunk + 1, Chunks.end(), ID,
           [](const Chunk &C, const DocID ID) { return C.Head <= ID; });
       --CurrentChunk;
       DecompressedChunk = CurrentChunk->decompress();
       CurrentID = DecompressedChunk.begin();
     }
   }
 
+  const Token *Tok;
   llvm::ArrayRef<Chunk> Chunks;
   /// Iterator over chunks.
   /// If CurrentChunk is valid, then DecompressedChunk is
   /// CurrentChunk->decompress() and CurrentID is a valid (non-end) iterator
   /// into it.
   decltype(Chunks)::const_iterator CurrentChunk;
   llvm::SmallVector<DocID, Chunk::PayloadSize + 1> DecompressedChunk;
   /// Iterator over DecompressedChunk.
for (DocID Current = Head; !Bytes.empty(); Current += Delta) {
     Result.push_back(Current + Delta);
   }
   return llvm::SmallVector<DocID, Chunk::PayloadSize + 1>{Result};
 }
 
 PostingList::PostingList(llvm::ArrayRef<DocID> Documents)
     : Chunks(encodeStream(Documents)) {}
 
-std::unique_ptr<Iterator> PostingList::iterator() const {
-  return llvm::make_unique<ChunkIterator>(Chunks);
+std::unique_ptr<Iterator> PostingList::iterator(const Token *Tok) const {
+  return llvm::make_unique<ChunkIterator>(Tok, Chunks);
 }
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang

clangd/index/dex/Token.h

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) {
+    switch (T.TokenKind) {
+    case Kind::Trigram:
+      OS << "T=";
+      break;
+    case Kind::Scope:
+      OS << "S=";
+      break;
+    case Kind::ProximityURI:
+      OS << "U=";
+      break;
+    case Kind::Sentinel:
+      OS << "?=";
+      break;
+    }
     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);
   }
 };

unittests/clangd/DexTests.cpp

TEST(DexIterators, QueryTree) {
   EXPECT_EQ(Root->peek(), 5U);
   ElementBoost = Root->consume();
   EXPECT_THAT(ElementBoost, 8);
   Root->advanceTo(9000);
   EXPECT_TRUE(Root->reachedEnd());
 }
 
 TEST(DexIterators, StringRepresentation) {
-  const PostingList L0({4, 7, 8, 20, 42, 100});
-  const PostingList L1({1, 3, 5, 8, 9});
-  const PostingList L2({1, 5, 7, 9});
-  const PostingList L3({0, 5});
-  const PostingList L4({0, 1, 5});
-
-  EXPECT_EQ(llvm::to_string(*(L0.iterator())), "[4 ...]");
-  auto It = L0.iterator();
-  It->advanceTo(19);
-  EXPECT_EQ(llvm::to_string(*It), "[... 20 ...]");
-  It->advanceTo(9000);
-  EXPECT_EQ(llvm::to_string(*It), "[... END]");
+  const PostingList L1({1, 3, 5});
+  const PostingList L2({1, 7, 9});
+  auto I1 = L1.iterator();
+  Token Tok(Token::Kind::Trigram, "L2");
+  auto I2 = L1.iterator(&Tok);
+
+  EXPECT_EQ(llvm::to_string(*I1), "[1 3 5]");
+  EXPECT_EQ(llvm::to_string(*I2), "T=L2");
+
+  auto Tree = createLimit(createAnd(move(I1), move(I2)), 10);
+  EXPECT_EQ(llvm::to_string(*Tree), "(LIMIT 10 (& [1 3 5] T=L2))");
 }
 
 TEST(DexIterators, Limit) {
   const PostingList L0({3, 6, 7, 20, 42, 100});
   const PostingList L1({1, 3, 5, 6, 7, 30, 100});
   const PostingList L2({0, 3, 5, 7, 8, 100});
 
   auto DocIterator = createLimit(L0.iterator(), 42);