[clangd] Implement TRUE Iterator

[kbobyrev]

Summary

This patch introduces TRUE Iterator which efficiently handles posting lists containing all items within [0, Size) range.

[ioeric]

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

230 ↗

(On Diff #161430)

nit: The documentation here is a bit verbose as. How about ... It stores size of the virtual posting list, and all operations are performed in O(1).? Other statements can be easily derived from this IMO.

248 ↗

(On Diff #161430)

Should we check ID < Size here?

258 ↗

(On Diff #161430)

nit: maybe s/TrueIterator/TRUE/?

[kbobyrev]

Address a couple of comments.

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

248 ↗

(On Diff #161430)

Not really, here's an example: (& ({0}, 42) (TRUE {0} out of 10).

When called advance(), underlying AND iterator would point to 42 and advanceTo() would be called on TRUE iterator, it will move it to the END but it would be completely valid (same behavior for every iterator, actually, since none of them check for ID < LastDocID equivalent).

I should, however, do Index = std::min(ID, Size) since calling dump() and getting something like (TRUE {9000} out of 42) would be implicit.

[ioeric]

lg

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

 std::unique_ptr<Iterator>
 createAnd(std::vector<std::unique_ptr<Iterator>> Children);
 
 /// Returns OR Iterator which performs the union of the PostingLists of its
 /// children.
 std::unique_ptr<Iterator>
 createOr(std::vector<std::unique_ptr<Iterator>> Children);
 
+/// Returns TRUE Iterator which iterates over "virtual" PostingList containing
+/// all items in range [0, Size) in an efficient manner.
+std::unique_ptr<Iterator> createTrue(DocID Size);
+
 /// This allows createAnd(create(...), create(...)) syntax.
 template <typename... Args> std::unique_ptr<Iterator> createAnd(Args... args) {
   std::vector<std::unique_ptr<Iterator>> Children;
   populateChildren(Children, args...);
   return createAnd(move(Children));
 }
 
 /// This allows createOr(create(...), create(...)) syntax.

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

llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
     return OS;
   }
 
 private:
   // FIXME(kbobyrev): Would storing Children in min-heap be faster?
   std::vector<std::unique_ptr<Iterator>> Children;
 };
 
+/// TrueIterator handles PostingLists which contain all items of the index. It
+/// stores size of the virtual posting list, and all operations are performed
+/// in O(1).
+class TrueIterator : public Iterator {
+public:
+  TrueIterator(DocID Size) : Size(Size) {}
+
+  bool reachedEnd() const override { return Index >= Size; }
+
+  void advance() override {
+    assert(!reachedEnd() && "Can't advance iterator after it reached the end.");
+    ++Index;
+  }
+
+  void advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "Can't advance iterator after it reached the end.");
+    Index = std::min(ID, Size);
+  }
+
+  DocID peek() const override {
+    assert(!reachedEnd() && "TrueIterator can't call peek() at the end.");
+    return Index;
+  }
+
+private:
+  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    OS << "(TRUE {" << Index << "} out of " << Size << ")";
+    return OS;
+  }
+
+  DocID Index = 0;
+  /// Size of the underlying virtual PostingList.
+  DocID Size;
+};
+
 } // end namespace
 
 std::vector<DocID> consume(Iterator &It, size_t Limit) {
   std::vector<DocID> Result;
   for (size_t Retrieved = 0; !It.reachedEnd() && Retrieved < Limit;
        It.advance(), ++Retrieved)
     Result.push_back(It.peek());
   return Result;
 }
 
 std::unique_ptr<Iterator> create(PostingListRef Documents) {
   return llvm::make_unique<DocumentIterator>(Documents);
 }
 
 std::unique_ptr<Iterator>
 createAnd(std::vector<std::unique_ptr<Iterator>> Children) {
   return llvm::make_unique<AndIterator>(move(Children));
 }
 
 std::unique_ptr<Iterator>
 createOr(std::vector<std::unique_ptr<Iterator>> Children) {
   return llvm::make_unique<OrIterator>(move(Children));
 }
 
+std::unique_ptr<Iterator> createTrue(DocID Size) {
+  return llvm::make_unique<TrueIterator>(Size);
+}
+
 } // namespace dex
 } // namespace clangd
 } // namespace clang

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

TEST(DexIndexIterators, Limit) {
 
   DocIterator = create(L0);
   EXPECT_THAT(consume(*DocIterator, 3), ElementsAre(4, 7, 8));
 
   DocIterator = create(L0);
   EXPECT_THAT(consume(*DocIterator, 0), ElementsAre());
 }
 
+TEST(DexIndexIterators, True) {
+  auto TrueIterator = createTrue(0U);
+  EXPECT_THAT(TrueIterator->reachedEnd(), true);
+  EXPECT_THAT(consume(*TrueIterator), ElementsAre());
+
+  PostingList L0 = {1, 2, 5, 7};
+  TrueIterator = createTrue(7U);
+  EXPECT_THAT(TrueIterator->peek(), 0);
+  auto AndIterator = createAnd(create(L0), move(TrueIterator));
+  EXPECT_THAT(AndIterator->reachedEnd(), false);
+  EXPECT_THAT(consume(*AndIterator), ElementsAre(1, 2, 5));
+}
+
 testing::Matcher<std::vector<Token>>
 trigramsAre(std::initializer_list<std::string> Trigrams) {
   std::vector<Token> Tokens;
   for (const auto &Symbols : Trigrams) {
     Tokens.push_back(Token(Token::Kind::Trigram, Symbols));
   }
   return testing::UnorderedElementsAreArray(Tokens);
 }