[clangd] Improve PostingList iterator string representation

[kbobyrev]

Summary

While dumping the element under PostingList iterator cursor, indicate whether this element is followed by or preceded by any other elements.

[ioeric]

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

96–97

I'd probably print ... [ID] ... to indicate that there can be other elements in the list.

[kbobyrev]

@ioeric does this format look better?

[ioeric]

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

66

nit: should we drop the trailing ... if Index is the last element?

[sammccall]

This change seems fine but...

This representation with the raw DocIDs and position dumped seems mostly useful for debugging buggy iterator implementations, but not really useful for understanding query structure and behavior.

I thought we might be replacing this soon. Of course there's no fundamental reason we can't keep both but I'm curious why this is an area of focus :-)

[kbobyrev]

In D52084#1238537, @sammccall wrote:

This change seems fine but...

This representation with the raw DocIDs and position dumped seems mostly useful for debugging buggy iterator implementations, but not really useful for understanding query structure and behavior.

I agree; There is another issue that I was looking into: I think that it might be useful to understand the structure of fuzzy find query when using dexp tool and I thought that it would be great if we could dump the iterator tree structure along with the results (which is an extension of D52233). For dexp usecase, it would be great to dump the size and the origin of each piece of iterator tree (e.g. labels), but I also think that it might be useful to have "debugging" format so I couldn't figure out what's the best approach here.

I thought we might be replacing this soon. Of course there's no fundamental reason we can't keep both but I'm curious why this is an area of focus :-)

Yes, we are. Initially, this wasn't an area of focus: I just forgot to update the comment in Iterator.h when moving PostingList to a separate file and slightly changing the format, but then Eric had a good proposal and I thought that it's a good improvement. Also, even though the implementation will be different, the dumping format could be the same, so it's not really implementation-specific.

[kbobyrev]

I think this one is addressed in the VByte patch, so I'm closing this revision in order to prevent conflicts between these two.

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

public:
 
   /// Prints a convenient human-readable iterator representation by recursively
   /// dumping iterators in the following format:
   ///
   /// (Type Child1 Child2 ...)
   ///
   /// Where Type is the iterator type representation: "&" for And, "|" for Or,
   /// ChildN is N-th iterator child. Raw iterators over PostingList are
-  /// represented as "[ID1, ID2, ..., {IDN}, ... END]" where IDN is N-th
-  /// PostingList entry and the element which is pointed to by the PostingList
-  /// iterator is enclosed in {} braces.
+  /// represented as "[... ID ...]" where ID is the element under iterator
+  /// cursor.
   friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                        const Iterator &Iterator) {
     return Iterator.dump(OS);
   }
 
   constexpr static float DEFAULT_BOOST_SCORE = 1;
 
 private:

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

float consume() override {
     return DEFAULT_BOOST_SCORE;
   }
 
   size_t estimateSize() const override { return Documents.size(); }
 
 private:
   llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
     OS << '[';
+    if (Index != std::begin(Documents))
+      OS << "... ";
     if (Index != std::end(Documents))
       OS << *Index;
     else
       OS << "END";
+    if (Index != std::end(Documents) && Index != std::end(Documents) - 1)
+      OS << " ...";
     OS << ']';
     return OS;
   }
 
   llvm::ArrayRef<DocID> Documents;
   llvm::ArrayRef<DocID>::const_iterator Index;
 };
 

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

 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});
   const PostingList L5({});
 
-  EXPECT_EQ(llvm::to_string(*(L0.iterator())), "[4]");
+  EXPECT_EQ(llvm::to_string(*(L0.iterator())), "[4 ...]");
 
   auto Nested =
       createAnd(createAnd(L1.iterator(), L2.iterator()),
                 createOr(L3.iterator(), L4.iterator(), L5.iterator()));
 
-  EXPECT_EQ(llvm::to_string(*Nested), "(& (| [5] [1] [END]) (& [1] [1]))");
+  EXPECT_EQ(
+      llvm::to_string(*Nested),
+      "(& (| [... 5] [... 1 ...] [END]) (& [1 ...] [1 ...]))");
 }
 
 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);