[clangd] Proof-of-concept query iterators for Dex symbol index

[kbobyrev]

Summary

This patch introduces three essential types of query iterators: DocumentIterator, AndIterator, OrIterator. It provides a convenient API for query tree generation and serves as a building block for the next generation symbol index - Dex. Currently, many optimizations are missed to improve code readability and to serve as the reference implementation. Potential improvements are briefly mentioned in FIXMEs and will be addressed in the following patches.

Dex RFC in the mailing list: http://lists.llvm.org/pipermail/clangd-dev/2018-July/000022.html

Iterators, their applications and potential extensions are explained in detail in the design proposal:
https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit#heading=h.903u1zon9nkj

[sammccall]

Thanks for sending this early!
Rough interface comments - mostly looks good though!

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

27

we should at least use a type alias for a DocID (maybe an opaque one - not sure for now)

40

or have peek return an InvalidID == size_t{-1}?

44

name Rank is confusing. Type should be DocID (param doesn't need a name in the interface)

45

could reasonably call this operator*

54

is shared_ptr really needed here? Seems like a raw pointer would be fine. I can see that when rebuilding the index we'll have some fun lifetime issues that are sometimes solved with shared_ptr, but I think that would be at the full-index level, not the individual-posting-list level.

(if you want one less indirection, you could have using PostingListRef = ArrayRef<size_t>, but it shouldn't matter)

60

what's this for?
I don't think it's worth exposing for testing, should be able to get at the needed cases through the public interface

64

how will you use this? it's not in the interface, and if you know the implementation then creating a new iterator is cheap

77

again, unless you have a strong reason, don't use shared_ptr, as it makes it hard to reason about ownership and lifetimes.

These are a tree, unique_ptr should be fine. That way a top-level owned iterator is self-contained.

84

what's this for?

[kbobyrev]

• Switched from std::shared_ptr to std::unique_ptr for iterator's children: iterators own their subtrees, the lifetime should depend on the root
• Store PostingListRefin DocumentIterator: the lifetime of underlying PostingList should be longer than the DocumentIterator anyway, DocumentIterator can not retrieve results from an incomplete inverted index
• Refined API of different iterators: wipe getIndex(), reset() from DocumentIterator, getChildren from AndIterator and OrIterator
• Not exposing DocumentIterator, AndIterator, OrIterator to the User API anymore: helper functions like std::unique_ptr<QueryIterator> constructDocumentIterator which return a unique pointer and perform type erasure are provided instead
• Improved variable naming, applied refactorings where necessary

[kbobyrev]

Upcoming changes:

• Improve debugging experience by providing llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, std::unique_ptr<QueryIterator> Iterator to recursively pretty print queries in human-readable format: e.g. (& [0, 1, 2, 3] ([3, 4, 6, 8] || [0, 1])). This can be later used for debugging and making sure optimizations were correct.
• Properly document the interface and implementation. The current documentation is just a draft, it should be refined.
• Think about introducing iterator cost and applying cheap optimizations like pre-sorting children of AndIterator before performing advance(): this way the iterator doesn't spend too much time iterating through long posting lists when it has are short/empty children

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

40

Tried to do that, but that creates additional complexity for the AndIterator which stores ReachedEnd anyway. Otherwise I would either have to spend O(Children.size()) to understand that AndIterator reached the end or have inconsistent APIs across the classes, I think it's better to leave it as it is.

45

As discussed offline, *(*Child) would be probably not very clean.

[kbobyrev]

• Implemented convenient dumping via llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, QueryIterator &Iterator), which dumps iterator tree in human-readable format, e.g. (&& [1, 2, 3] (|| [3, 4, 5] []))
• Implemented rather straightforward iterator cost for more efficient AndIterator iterations

The functional part is probably done at this point, the only thing to do at this point is to properly document written code leaving only few FIXMEs for the future.

[sammccall]

A few more comments about the bits I understand, but waiting mostly on the documentation.

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

257

you can just inline this.

If you don't, you have to provide a declaration in the header, outside the class definition. (In addition to the friend declaration). GCC errors on this, clang ignores it (GCC is right).

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

28

uint32_t should be plenty. These will be a large fraction of the index's memory usage. (Especially if we push actual payloads onto disk later)

41

this is done I think.

43

I'm not sure Query actually adds much to this class name. Iterator, AndIterator, etc would read more smoothly.

52

As discussed offline, please leave this out of the initial patch.
It requires quite some explanation and understanding, and seems likely to delay the review.

68

nit: newAndIterator or just andIterator? brevity is the soul of wit and all that

Or even better, what about:

Iterator::createAnd(...)
Iterator::createOr(...)
Iterator::create(PostingList*)

68

nit: pass by value rather than by rvalue-reference unless there's a strong reason.

Here, vector<u_p> isn't copyable, and there are no overloads, and this isn't performance-critical, so it should be fine.

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

19

please spell these out (local style)

27

using namespace llvm

67

nit: just auto And = constructAndIterator({constructDocumentIterator(EmptyList)})

(and below in various places).
This actually seems nicer - the expression hierarchy reflects the iterator hierarchy.

75

just EXPECT_EQ(to_string(*And), "(&& [])")

You may need to #include "llvm/Support/ScopedPrinters.h"

98

add a helper function vector<DocID> consume(Iterator&)
(Maybe even to the main file rather than the tests).

Then this section (and some others) can just be EXPECT_THAT(consume(*And), ElementsAre(0u,7u,10u,...))

140

Hmm, I'm not sure this approach scales - there shouldn't be anything special about composing and/and, compared to and/or, or/not, boost/and, etc.

I'd suggest testing each iterator directly, and then having one test that uses a more complex tree, and dropping this case.

324

This is too complicated. Try to use each iterator once or twice.
(We'll need to extend this when we add new iterator types)

[sammccall]

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

155

nit: & should be enough?

175

can this just be a static function?

196

can we start with the simple/obvious implementation, and add heap later if it actually improves performance?

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

47

nit: this seems non-orthogonal, could we either:

• have advance() and advanceTo() return void
• or remove reachedEnd() and have owners that need to keep the state (and/or iterators) maintain it separately?

54

private?

[kbobyrev]

As discussed offline: I simplified the implementation and cleaned up unit tests. Should look better now.

The next step is to document the implementation.

[kbobyrev]

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

175

Wiped this one. Also, in the future I guess it's better to implement operator<() for iterators, because that's what this essentially is.

196

Done. It doesn't look simpler to me, but I tried to keep it as simple as possible. I also put a FIXME on top of OrIterator with the trade-offs description.

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

324

Done. Dropped this one and two other complicated cases.

[kbobyrev]

Refactored unit tests in few places.

[sammccall]

This looks really nice.
Iterator implementations can be simplified a bit I think.

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

50 ↗

(On Diff #156997)

(uber-nit: slightly clearer to add the separator first, then you only have to compare against zero.
Or this idiom:

const char* Sep = "";
for (DocID D : Documents) {
  OS << Sep << D;
  Sep = ", ";
}

59 ↗

(On Diff #156997)

nit: the code might be slightly more concise (particularly advanceTo) if the current element is represented by a PostingListRef::Iterator rather than an index, up to you.

59 ↗

(On Diff #156997)

(DocID is the wrong type for an index)

65 ↗

(On Diff #156997)

nit: just take children by value without &&

69 ↗

(On Diff #156997)

nit: const auto &

74 ↗

(On Diff #156997)

just return so you don't need the if at the end?

88 ↗

(On Diff #156997)

It would be nice if the functions in this class could share some logic.

what about:

for (auto& C : children)
  C->advance();
sync();

where sync is

// restores class invariants: ReachedEnd set, or all children in sync
void sync() {
DocID Max = 0;
for (auto &C : Children) {
   if (C->reachedEnd()) {
    ReachedEnd = true;
    return;
  }
  Max = std::max(C->peek(), Max);
}
for (auto &C : Children) {
  C->advanceTo(Max);
   if (C->reachedEnd()) {
    ReachedEnd = true;
    return;
  }
}
}

the trick is then the constructor is just sync();, advanceTo is just "advance all children and sync", etc.

155 ↗

(On Diff #156997)

I think this is FIXME: would a min-heap be faster? :-)

181 ↗

(On Diff #156997)

I can't follow this one - why is the outer loop needed?

(It looks like you're using DocID as integer again, but I can't tell why the variable is needed at all)

184 ↗

(On Diff #156997)

nit: you can drop the extra braces here and in advanceTo (at least, you use that style above)

204 ↗

(On Diff #156997)

why not just initialize Result to std::numeric_limits<DocID>::max(), and skip the valid checking?

You know by assertion that you'll find something better.

235 ↗

(On Diff #156997)

for (; !It.reachedEnd(); It.advance())

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

50 ↗

(On Diff #156997)

this doesn't really make sense as static as it operates on an Iterator.
Either a free function or non-static member seems fine

65 ↗

(On Diff #156997)

nit nit: move above the template overload so you can document the readable one.

[kbobyrev]

Address the last round of comments.

Incoming: documentation overhaul.

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

181 ↗

(On Diff #156997)

An artifact from min-heap implementation.

[kbobyrev]

Slightly refactored the code, improved documentation. This patch is ready for review.

[kbobyrev]

Choose better wording in a couple of places.

[ioeric]

Implementation is in a good shape. I only have nits ;)

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

18 ↗

(On Diff #157206)

Please put all local classes and helpers in an anonymous namespace.

20 ↗

(On Diff #157206)

nit: We could elaborate a bit. This is the most basic or "leaf" iterator.

30 ↗

(On Diff #157206)

nit: The complexity is obvious, so I'd probably drop it as this is not public.

39 ↗

(On Diff #157206)

Again, this should also be obvious given the short implementation.

68 ↗

(On Diff #157206)

I'm not exactly sure what this means. Do you mean "AndIterator iterates through common items among all children"?

75 ↗

(On Diff #157206)

nit: ReachedEnd is reset in sync(). Maybe just make it default value for the field?

112 ↗

(On Diff #157206)

nit: documentation for ReachedEnd is already covered below.

114 ↗

(On Diff #157206)

nit: ReachedEnd &= ...; would keep me from worrying about true ReachedEnd getting overridden.

117 ↗

(On Diff #157206)

nit: SyncID or Sync might be clearer.

118 ↗

(On Diff #157206)

Maybe add a comment NeedsAdvance indicates whether advanceTo(ID) should be rerun from the beginning.

145 ↗

(On Diff #157206)

nit: why "local state"? (All instance fields are local states)

166 ↗

(On Diff #157206)

use std::any_of(...)?

176 ↗

(On Diff #157206)

The comment says smallest DocID, but here we call it highest :(

178 ↗

(On Diff #157206)

nit: no braces for one-liners.

218 ↗

(On Diff #157206)

I think this FIXME should live in peek() as it's an optimization for peek().

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

10 ↗

(On Diff #157206)

I think we should give more context here. For example, it's unclear what Query Tree Nodes are. Posting list is not a widely known concept. What is the idea behind iterators? What problem do they solve? Roughly what iterators are provided? An example like ascii graph you have in the test can be useful here as well.

21 ↗

(On Diff #157206)

nit: remove spaces between #includes so that clang-format can sort all #includes properly. same for other files.

34 ↗

(On Diff #157206)

nit:

PostingLists are keys ...

Do you mean values? Isn't inverted index a mapping from search tokens to positing lists?

44 ↗

(On Diff #157206)

Could you also add documentation for Iterator class?

47 ↗

(On Diff #157206)

nit: calls.

52 ↗

(On Diff #157206)

What does invalid mean? Would there be any side effect? Would it trigger a crash?

59 ↗

(On Diff #157206)

micro nit: under cursor might be ambiguous.

Would peek() be valid when reachedEnd() is true?

85 ↗

(On Diff #157206)

nit: a document iterator?

88 ↗

(On Diff #157206)

nit: Returns an AND iterator which ... (same below)

AndIterator is the name for internal implementation and not exposed.

98 ↗

(On Diff #157206)

Documentation for the templated interfaces? e.g. why are they needed?

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

48

This tests multiple things in one test case, and it's unclear what they are testing. Also, the long function body makes the list definitions hard to read from where they are used.

I think this can be split into:

• a test case for iterator dumping.
• a test case for AND of empty list and non-empty list.
• a test case for AND of two lists.
• a test case for AND of three lists.

49

nit: these can be L0, L1, L2, L3. Save you some typing ;)

67

Could you split checks for iterator dumping into a separate test? It's relatively independent. And you wouldn't need to update multiple places in case you update elements in posting lists.

166

s/0/1/ for AND lists?

187

These two operations are not meaningful if we don't check anything after them.

[kbobyrev]

Addressed a round of comments: cleaned up the code, improved documentation and properly introduced such terms like Posting List and Query Tree. Tests are now more modular and each specific piece tests a certain part of implementation.

$ ninja check-clang-tools is green.

[kbobyrev]

Typo: "Returns false if ..., false otherwise" ->"Returns false if ..., true otherwise".

[kbobyrev]

Rebase on top of https://reviews.llvm.org/rL337901

[ioeric]

lg! just a few nits.

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

109 ↗

(On Diff #157439)

This is the post-condition, not a precondition right?

To be clearer, ... each child will point to the same element after sync

162 ↗

(On Diff #157439)

Or Returns true if all children are exhausted. No need for otherwise if it's trivial.

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

12 ↗

(On Diff #157439)

nit: Just to match the actual implementation, use "clang::clangd::" to avoid confusion.

15 ↗

(On Diff #157439)

"number of references" is too specific. Maybe "by symbol quality"?

25 ↗

(On Diff #157439)

Again, replace number of references with quality for generalization.

26 ↗

(On Diff #157439)

with the requested *properties*?

61 ↗

(On Diff #157439)

nit: drop "some of which are not yet introduced" as it's not relevant to the interface itself.

72 ↗

(On Diff #157439)

Just "return true if ...".

There is no need to mention advance() and advanceTo() here as they are already covered in their own documentation.

76 ↗

(On Diff #157439)

Just reachedEnd() must be false. which usually implies assertion. Same elsewhere.

127 ↗

(On Diff #157439)

An example of usage would be simpler and easier to understand here. Same below.

Example:
This allows createAnd({create(...), create(...)})

[kbobyrev]

Address post-lg round of comments.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   ProtocolHandlers.cpp
   Quality.cpp
   SourceCode.cpp
   Threading.cpp
   Trace.cpp
   TUScheduler.cpp
   URI.cpp
   XRefs.cpp
+
   index/CanonicalIncludes.cpp
   index/FileIndex.cpp
   index/Index.cpp
   index/MemIndex.cpp
   index/Merge.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
+  index/dex/QueryIterator.cpp
+
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangDriver
   clangFormat
   clangFrontend
   clangIndex

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

+//===--- QueryIterator.h - Query Symbol Retrieval ---------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// FIXME(kbobyrev): Write a short summary
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H
+
+#include <limits>
+#include <memory>
+#include <vector>
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+using DocID = size_t;
+using PostingList = std::vector<DocID>;
+using PostingListRef = llvm::ArrayRef<DocID>;
+
+// FIXME(kbobyrev): Provide callback for matched documents. Use the callback in
+// RetrievalSession (and limiting matched documents?) later.
+// FIXME(kbobyrev): Count matched documents, so that iterators could limit the
+// number of matched symbols.
+// FIXME(kbobyrev): Introduce scores and boosting.
+// FIXME(kbobyrev): Introduce RetrievalIterator and RetrievalSession.
+// FIXME(kbobyrev): Pretty-print query trees? Any other idea for more pleasant
+// debugging experience? Should iterators have human-readable names?
+// FIXME(kbobyrev): Document this one properly.
+// FIXME(kbobyrev): Don't expose all the classes in the header, move classes to
+// header and only have constructors here.
+class QueryIterator {
+public:
+  // FIXME(kbobyrev): Should advance() and advanceTo() return DocID peek()
+  // instead?
+  virtual bool reachedEnd() const = 0;
+  virtual bool advance() = 0;
+  virtual bool advanceTo(DocID Rank) = 0;
+  /// Returns item under the cursor.
+  virtual DocID peek() const = 0;
+  virtual size_t cost() const = 0;
+
+  virtual llvm::raw_ostream &dump(llvm::raw_ostream &OS) const = 0;
+
+  virtual ~QueryIterator() {}
+
+  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                                       const QueryIterator &Iterator);
+};
+
+// FIXME(kbobyrev): Brief documentation of DocumentIterator here.
+std::unique_ptr<QueryIterator>
+constructDocumentIterator(PostingListRef Documents);
+
+// FIXME(kbobyrev): Brief documentation of AndIterator here.
+std::unique_ptr<QueryIterator>
+constructAndIterator(std::vector<std::unique_ptr<QueryIterator>> &&Children);
+
+// FIXME(kbobyrev): Brief documentation of OrIterator here.
+std::unique_ptr<QueryIterator>
+constructOrIterator(std::vector<std::unique_ptr<QueryIterator>> &&Children);
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+#endif

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

+//===--- QueryIterator.cpp - Query Symbol Retrieval -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "QueryIterator.h"
+
+#include <algorithm>
+#include <cassert>
+#include <numeric>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+/// Implements QueryIterator over a PostingList.
+// FIXME(kbobyrev): Document this one properly.
+class DocumentIterator : public QueryIterator {
+public:
+  DocumentIterator(PostingListRef Documents)
+      : Documents(Documents), Cost(Documents.size()), Index(0) {}
+
+  bool reachedEnd() const override { return Index == Documents.size(); }
+
+  /// Increments Index.
+  bool advance() override {
+    assert(!reachedEnd() && "DocumentIterator can't advance at the end.");
+    ++Index;
+    return reachedEnd();
+  }
+
+  // FIXME(kbobyrev): Properly document this one.
+  bool advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "DocumentIterator can't advance at the end.");
+    Index = std::lower_bound(Documents.begin() + Index, Documents.end(), ID) -
+            Documents.begin();
+    return reachedEnd();
+  }
+
+  DocID peek() const override {
+    assert(!reachedEnd() && "DocumentIterator can't call peek() at the end.");
+    return Documents[Index];
+  }
+
+  size_t cost() const override { return Cost; }
+
+  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    OS << '[';
+    for (size_t Index = 0; Index < Documents.size(); ++Index) {
+      OS << Documents[Index];
+      if (Index + 1 != Documents.size())
+        OS << ", ";
+    }
+    OS << ']';
+    return OS;
+  }
+
+private:
+  PostingListRef Documents;
+  size_t Cost;
+  DocID Index;
+};
+
+// FIXME(kbobyrev): Document this one properly.
+class AndIterator : public QueryIterator {
+public:
+  AndIterator(std::vector<std::unique_ptr<QueryIterator>> &&AllChildren)
+      : Children(std::move(AllChildren)), ReachedEnd(false) {
+    assert(!Children.empty() && "AndIterator should have at least one child.");
+    DocID ID = 0;
+    for (auto &Child : Children) {
+      // Check whether any child iterator points to the end. In this case,
+      // advance() would be invalid.
+      if (Child->reachedEnd()) {
+        ReachedEnd = true;
+        break;
+      }
+      // Choose highest ID among valid children.
+      ID = std::max(ID, Child->peek());
+    }
+    Cost = std::accumulate(
+        begin(Children), end(Children), Children.front()->cost(),
+        [](size_t Current, std::unique_ptr<QueryIterator> &Next) {
+          return std::min(Current, Next->cost());
+        });
+    // Sort all children so that the cheapest are in the beginning.
+    std::sort(begin(Children), end(Children),
+              [](std::unique_ptr<QueryIterator> &LHS,
+                 std::unique_ptr<QueryIterator> &RHS) {
+                return LHS->cost() < RHS->cost();
+              });
+    // Make sure all children point to the same document, otherwise peek() is
+    // invalid.
+    if (!ReachedEnd)
+      advanceTo(ID);
+  }
+
+  bool reachedEnd() const override { return ReachedEnd; }
+
+  // FIXME(kbobyrev): Properly document this one.
+  bool advance() override {
+    assert(!reachedEnd() && "AndIterator can't call advance() at the end.");
+    ReachedEnd = Children.front()->advance();
+    DocID HighestID = 0;
+    if (!ReachedEnd)
+      HighestID = Children.front()->peek();
+    bool ChangedID = true;
+    while (ChangedID && !ReachedEnd) {
+      ChangedID = false;
+      for (auto &Child : Children) {
+        ReachedEnd = Child->advanceTo(HighestID);
+        if (ReachedEnd)
+          break;
+        if (Child->peek() > HighestID) {
+          HighestID = Child->peek();
+          ChangedID = true;
+        }
+      }
+    }
+    return reachedEnd();
+  }
+
+  // FIXME(kbobyrev): Properly document this one.
+  bool advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "AndIterator can't call advanceTo() at the end.");
+    bool NeedsAdvance = false;
+    for (auto &Child : Children) {
+      ReachedEnd = Child->advanceTo(ID);
+      // If any child reaches end And iterator can not match any other items. In
+      // this case, just terminate the process.
+      if (ReachedEnd)
+        break;
+      // If any child goes beyond given ID (i.e. ID is not the common item),
+      // all children should be advanced to the next common item.
+      if (Child->peek() > ID) {
+        ID = Child->peek();
+        NeedsAdvance = true;
+      }
+    }
+    // Advance all children to the next common item.
+    if (!ReachedEnd && NeedsAdvance)
+      advanceTo(ID);
+    return reachedEnd();
+  }
+
+  DocID peek() const override { return Children.front()->peek(); }
+
+  size_t cost() const override { return Cost; }
+
+  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    OS << "(&& ";
+    for (size_t Index = 0; Index < Children.size(); ++Index) {
+      OS << *Children[Index];
+      if (Index + 1 != Children.size())
+        OS << ' ';
+    }
+    OS << ')';
+    return OS;
+  }
+
+private:
+  std::vector<std::unique_ptr<QueryIterator>> Children;
+  size_t Cost;
+  // Store and update local state, otherwise each reachedEnd() call would
+  // require the whole subtree traversal.
+  bool ReachedEnd;
+};
+
+namespace {
+// FIXME(kbobyrev): This compares IDs of two iterators...
+auto CompareIterators = [](std::unique_ptr<QueryIterator> &Left,
+                           std::unique_ptr<QueryIterator> &Right) -> bool {
+  if (Right->reachedEnd())
+    return false;
+  if (Left->reachedEnd())
+    return true;
+  return Left->peek() > Right->peek();
+};
+} // namespace
+
+// FIXME(kbobyrev): Document this one properly.
+class OrIterator : public QueryIterator {
+public:
+  OrIterator(std::vector<std::unique_ptr<QueryIterator>> &&AllChildren)
+      : Children(std::move(AllChildren)) {
+    assert(Children.size() > 0 && "Or Iterator must have at least one child.");
+    Cost = std::accumulate(
+        begin(Children), end(Children), Children.front()->cost(),
+        [](size_t Current, std::unique_ptr<QueryIterator> &Next) {
+          return std::max(Current, Next->cost());
+        });
+    std::make_heap(begin(Children), end(Children), CompareIterators);
+  }
+
+  bool reachedEnd() const override { return Children.front()->reachedEnd(); }
+
+  bool advance() override {
+    assert(!reachedEnd() &&
+           "OrIterator must have at least one child to advance().");
+    const auto HighestID = peek();
+    DocID ChildrenToAdvance = 0;
+    while ((ChildrenToAdvance++ < Children.size()) &&
+           !Children.front()->reachedEnd() &&
+           (Children.front()->peek() == HighestID)) {
+      Children.front()->advance();
+      std::pop_heap(begin(Children), end(Children), CompareIterators);
+      std::push_heap(begin(Children), end(Children), CompareIterators);
+    }
+    return reachedEnd();
+  }
+
+  bool advanceTo(DocID ID) override {
+    assert(!reachedEnd() &&
+           "OrIterator must have at least one child to advanceTo().");
+    for (auto &Child : Children) {
+      if (!Child->reachedEnd()) {
+        Child->advanceTo(ID);
+      }
+    }
+    std::make_heap(begin(Children), end(Children), CompareIterators);
+    return reachedEnd();
+  }
+
+  DocID peek() const override {
+    assert(!reachedEnd() &&
+           "OrIterator must have at least one child to peek().");
+    return Children.front()->peek();
+  }
+
+  size_t cost() const override { return Cost; }
+
+  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    OS << "(|| ";
+    for (size_t Index = 0; Index < Children.size(); ++Index) {
+      OS << *Children[Index];
+      if (Index + 1 != Children.size())
+        OS << ' ';
+    }
+    return OS;
+  }
+
+private:
+  /// Min-heap with child iterators sorted by Child->peek().
+  ///
+  /// Since it is min-heap, whenever any child advances the positions of
+  /// children change as modified child is popped from the heap and back. Do not
+  /// store iterators of Children unless you are sure they are not being
+  /// advanced in the process.
+  std::vector<std::unique_ptr<QueryIterator>> Children;
+  size_t Cost;
+};
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const QueryIterator &Iterator) {
+  return Iterator.dump(OS);
+}
+
+std::unique_ptr<QueryIterator>
+constructDocumentIterator(PostingListRef Documents) {
+  return llvm::make_unique<DocumentIterator>(Documents);
+}
+
+std::unique_ptr<QueryIterator>
+constructAndIterator(std::vector<std::unique_ptr<QueryIterator>> &&Children) {
+  return llvm::make_unique<AndIterator>(move(Children));
+}
+
+std::unique_ptr<QueryIterator>
+constructOrIterator(std::vector<std::unique_ptr<QueryIterator>> &&Children) {
+  return llvm::make_unique<OrIterator>(move(Children));
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang

clang-tools-extra/unittests/clangd/CMakeLists.txt

 
 add_extra_unittest(ClangdTests
   Annotations.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
+  DexIndexTests.cpp
   DraftStoreTests.cpp
-  FileIndexTests.cpp
   FileDistanceTests.cpp
+  FileIndexTests.cpp
   FindSymbolsTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   QualityTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SyncAPI.cpp
+  TUSchedulerTests.cpp
   TestFS.cpp
   TestTU.cpp
   ThreadingTests.cpp
   TraceTests.cpp
-  TUSchedulerTests.cpp
   URITests.cpp
   XRefsTests.cpp
   )
 
 target_link_libraries(ClangdTests
   PRIVATE
   clangAST
   clangBasic

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

+//===--- DexIndexTests.cpp ----------------------------*- C++ -*-----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "index/dex/QueryIterator.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest.h"
+#include <string>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+using std::make_shared;
+using std::max;
+using std::min;
+using std::move;
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+using llvm::raw_string_ostream;
+
+TEST(DexIndexIterators, DocumentIterator) {
+  const PostingList Symbols = {4, 7, 8, 20, 42, 100};
+  auto DocIterator = constructDocumentIterator(Symbols);
+
+  EXPECT_EQ(DocIterator->cost(), Symbols.size());
+
+  EXPECT_EQ(DocIterator->peek(), 4U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  EXPECT_EQ(DocIterator->advance(), false);
+  EXPECT_EQ(DocIterator->peek(), 7U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  EXPECT_EQ(DocIterator->advanceTo(20), false);
+  EXPECT_EQ(DocIterator->peek(), 20U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  EXPECT_EQ(DocIterator->advanceTo(65), false);
+  EXPECT_EQ(DocIterator->peek(), 100U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  EXPECT_EQ(DocIterator->advanceTo(420), true);
+  EXPECT_EQ(DocIterator->reachedEnd(), true);
+
+  string Dump;
+  raw_string_ostream OS(Dump);
+  OS << *DocIterator;
+  EXPECT_EQ(OS.str(), "[4, 7, 8, 20, 42, 100]");
+}
+
+TEST(DexIndexIterators, AndIterator) {
+  const PostingList EmptyList;
+  const PostingList FirstList = {0, 5, 7, 10, 42, 320, 9000};
+  const PostingList SecondList = {0, 4, 7, 10, 30, 60, 320, 9000};
+  const PostingList ThirdList = {1, 4, 7, 11, 30, 60, 320, 9000};
+  const PostingList FourthList = {4, 7, 10, 30, 60, 320, 9000};
+  const PostingList FifthList = {1, 4, 7, 10, 30, 60, 320, 9000, 1000000};
+
+  vector<unique_ptr<QueryIterator>> Children;
+
+  Children.push_back(constructDocumentIterator(EmptyList));
+  auto And = constructAndIterator(move(Children));
+
+  EXPECT_EQ(And->cost(), 0U);
+  EXPECT_EQ(And->reachedEnd(), true);
+
+  string Dump;
+  raw_string_ostream OS(Dump);
+  OS << *And;
+  EXPECT_EQ(OS.str(), "(&& [])");
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(EmptyList));
+  Children.push_back(constructDocumentIterator(FirstList));
+  And = constructAndIterator(move(Children));
+
+  EXPECT_EQ(And->cost(), 0U);
+  EXPECT_EQ(And->reachedEnd(), true);
+
+  Dump.clear();
+  OS << *And;
+  EXPECT_EQ(OS.str(), "(&& [] [0, 5, 7, 10, 42, 320, 9000])");
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(SecondList));
+  Children.push_back(constructDocumentIterator(FirstList));
+  And = constructAndIterator(move(Children));
+  EXPECT_EQ(And->cost(), min(SecondList.size(), FirstList.size()));
+
+  EXPECT_EQ(And->reachedEnd(), false);
+  EXPECT_EQ(And->peek(), 0U);
+  EXPECT_EQ(And->advance(), false);
+  EXPECT_EQ(And->peek(), 7U);
+  EXPECT_EQ(And->advance(), false);
+  EXPECT_EQ(And->peek(), 10U);
+  EXPECT_EQ(And->advance(), false);
+  EXPECT_EQ(And->peek(), 320U);
+  EXPECT_EQ(And->advance(), false);
+  EXPECT_EQ(And->peek(), 9000U);
+  EXPECT_EQ(And->advance(), true);
+
+  Dump.clear();
+  OS << *And;
+  EXPECT_EQ(
+      OS.str(),
+      "(&& [0, 5, 7, 10, 42, 320, 9000] [0, 4, 7, 10, 30, 60, 320, 9000])");
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(SecondList));
+  Children.push_back(constructDocumentIterator(FirstList));
+  And = constructAndIterator(move(Children));
+
+  EXPECT_EQ(And->advanceTo(0), false);
+  EXPECT_EQ(And->peek(), 0U);
+  EXPECT_EQ(And->advanceTo(5), false);
+  EXPECT_EQ(And->peek(), 7U);
+  EXPECT_EQ(And->advanceTo(10), false);
+  EXPECT_EQ(And->peek(), 10U);
+  EXPECT_EQ(And->advanceTo(42), false);
+  EXPECT_EQ(And->peek(), 320U);
+  EXPECT_EQ(And->advanceTo(8999), false);
+  EXPECT_EQ(And->peek(), 9000U);
+  EXPECT_EQ(And->advanceTo(9001), true);
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(SecondList));
+  Children.push_back(constructDocumentIterator(FirstList));
+  And = constructAndIterator(move(Children));
+
+  EXPECT_EQ(And->advanceTo(100000), true);
+
+  // More complicated example: nested And iterators.
+  //
+  //            +------------------+
+  //            |Top Level Iterator|
+  //            +--------+---------+
+  //                     |
+  //       +---------------------------+-----------------+
+  //       |             |             |                 |
+  //  +----v-----+ +-----v-----+ +-----v----+ +----------v----------+
+  //  |First List| |Second List| |Third List| |Bottom Level Iterator|
+  //  +----------+ +-----------+ +----------+ +----------+----------+
+  //                                                     |
+  //                                              +------+------+
+  //                                              |             |
+  //                                        +-----v-----+ +-----v----+
+  //                                        |Fourth List| |Fifth List|
+  //                                        +-----------+ +----------+
+  //
+  // First List:    [0, 5, 7,  10, 42, 320, 9000]
+  // Second List:   [0, 4, 7,  10, 30, 60,  320,  9000]
+  // Third List:    [1, 4, 7,  11, 30, 60,  320,  9000]
+  // Fourth List:   [4, 7, 10, 30, 60, 320, 9000]
+  // Fifth List:    [1, 4, 7,  10, 30, 60,  320,  9000, 1000000]
+  //
+  // Intersection:  [      7,               320,  9000]
+  //
+  // FIXME(kbobyrev): The above example is a subject for optimization.
+  // TopLevelIterator can be flattened.
+  //
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(FourthList));
+  Children.push_back(constructDocumentIterator(FifthList));
+  auto BottomLevelIterator = constructAndIterator(move(Children));
+
+  EXPECT_EQ(BottomLevelIterator->reachedEnd(), false);
+  EXPECT_EQ(BottomLevelIterator->peek(), 4U);
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(FirstList));
+  Children.push_back(constructDocumentIterator(SecondList));
+  Children.push_back(constructDocumentIterator(ThirdList));
+  Children.push_back(move(BottomLevelIterator));
+  auto TopLevelIterator = constructAndIterator(move(Children));
+
+  EXPECT_EQ(TopLevelIterator->reachedEnd(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 7U);
+  EXPECT_EQ(TopLevelIterator->advanceTo(7), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 7U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 320U);
+  EXPECT_EQ(TopLevelIterator->advanceTo(8999), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 9000U);
+  EXPECT_EQ(TopLevelIterator->advance(), true);
+
+  Dump.clear();
+  OS << *TopLevelIterator;
+  EXPECT_EQ(OS.str(),
+            "(&& [0, 5, 7, 10, 42, 320, 9000] (&& [4, 7, 10, 30, 60, 320, "
+            "9000] [1, 4, 7, 10, 30, 60, 320, 9000, 1000000]) [0, 4, 7, 10, "
+            "30, 60, 320, 9000] [1, 4, 7, 11, 30, 60, 320, 9000])");
+}
+
+TEST(DexIndexIterators, OrIterator) {
+  const PostingList EmptyList;
+  const PostingList FirstList = {0, 5, 7, 10, 42, 320, 9000};
+  const PostingList SecondList = {0, 4, 7, 10, 30, 60, 320, 9000};
+  const PostingList ThirdList = {1, 4, 7, 11, 30, 60, 320, 9000};
+  const PostingList FourthList = {4, 7, 10, 30, 60, 320, 9000};
+  const PostingList FifthList = {1, 4, 7, 10, 30, 60, 320, 9000, 1000000};
+
+  vector<unique_ptr<QueryIterator>> Children;
+  Children.push_back(constructDocumentIterator(EmptyList));
+  auto Or = constructOrIterator(move(Children));
+
+  EXPECT_EQ(Or->reachedEnd(), true);
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(FirstList));
+  Children.push_back(constructDocumentIterator(EmptyList));
+  Or = constructOrIterator(move(Children));
+
+  EXPECT_EQ(Or->reachedEnd(), false);
+  EXPECT_EQ(Or->peek(), 0U);
+  EXPECT_EQ(Or->advance(), false);
+  EXPECT_EQ(Or->peek(), 5U);
+  EXPECT_EQ(Or->advance(), false);
+  EXPECT_EQ(Or->peek(), 7U);
+  EXPECT_EQ(Or->advance(), false);
+  EXPECT_EQ(Or->peek(), 10U);
+  EXPECT_EQ(Or->advance(), false);
+  EXPECT_EQ(Or->peek(), 42U);
+  EXPECT_EQ(Or->advanceTo(42), false);
+  EXPECT_EQ(Or->peek(), 42U);
+  EXPECT_EQ(Or->advanceTo(300), false);
+  EXPECT_EQ(Or->peek(), 320U);
+  EXPECT_EQ(Or->advanceTo(9000), false);
+  EXPECT_EQ(Or->peek(), 9000U);
+  EXPECT_EQ(Or->advanceTo(9001), true);
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(FirstList));
+  Children.push_back(constructDocumentIterator(SecondList));
+  Children.push_back(constructDocumentIterator(ThirdList));
+  Or = constructOrIterator(move(Children));
+
+  EXPECT_EQ(Or->reachedEnd(), false);
+  EXPECT_EQ(Or->peek(), 0U);
+
+  EXPECT_EQ(Or->advance(), false);
+  EXPECT_EQ(Or->peek(), 1U);
+
+  EXPECT_EQ(Or->advance(), false);
+  EXPECT_EQ(Or->peek(), 4U);
+
+  EXPECT_EQ(Or->advanceTo(7), false);
+
+  EXPECT_EQ(Or->advanceTo(59), false);
+  EXPECT_EQ(Or->peek(), 60U);
+
+  EXPECT_EQ(Or->advanceTo(9001), true);
+
+  //  The query with 5 posting lists as in AndIterator except that all iterators
+  //  here are OrIterator.
+  //
+  // First List:    [0, 5, 7,  10, 42, 320, 9000]
+  // Second List:   [0, 4, 7,  10, 30, 60,  320,  9000]
+  // Third List:    [1, 4, 7,  11, 30, 60,  320,  9000]
+  // Fourth List:   [4, 7, 10, 30, 60, 320, 9000]
+  // Fifth List:    [1, 4, 7,  10, 30, 60,  320,  9000, 1000000]
+  //
+  // Union: [0, 1, 4, 5, 7, 10, 11, 30, 42, 60, 320, 9000, 1000000]
+  //
+  // FIXME(kbobyrev): Similarly to the initial example with AndIterator, a tree
+  // consisting only of OrIterator nodes can be flattened.
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(FourthList));
+  Children.push_back(constructDocumentIterator(FifthList));
+  auto BottomLevelIterator = constructOrIterator(move(Children));
+
+  EXPECT_EQ(BottomLevelIterator->reachedEnd(), false);
+  EXPECT_EQ(BottomLevelIterator->peek(), 1U);
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(FirstList));
+  Children.push_back(constructDocumentIterator(SecondList));
+  Children.push_back(constructDocumentIterator(ThirdList));
+  Children.push_back(move(BottomLevelIterator));
+  auto TopLevelIterator = constructOrIterator(move(Children));
+
+  EXPECT_EQ(TopLevelIterator->reachedEnd(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 0U);
+
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 1U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 4U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 5U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 7U);
+
+  EXPECT_EQ(TopLevelIterator->advanceTo(8), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 10U);
+  EXPECT_EQ(TopLevelIterator->advanceTo(29), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 30U);
+  EXPECT_EQ(TopLevelIterator->advanceTo(30), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 30U);
+
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 42U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 60U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 320U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 9000U);
+  EXPECT_EQ(TopLevelIterator->advance(), false);
+  EXPECT_EQ(TopLevelIterator->peek(), 1000000U);
+  EXPECT_EQ(TopLevelIterator->advance(), true);
+}
+
+TEST(DexIndexIterators, QueryTree) {
+  // An example of more complicated query
+  //
+  //                      +-----------------+
+  //                      |And Iterator:1, 5|
+  //                      +--------+--------+
+  //                               |
+  //                               |
+  //                 +------------------------------------+
+  //                 |             |                      |
+  //                 |             |                      |
+  //      +----------v----------+  |           +----------v---------+
+  //      |And Iterator: 1, 5, 9|  |           |Or Iterator: 0, 1, 5|
+  //      +----------+----------+  |           +----------+---------+
+  //                 |             |                      |
+  //          +------+-----+       |            +---------+---+-------+-----+
+  //          |            |       |            |             |       |     |
+  //  +-------v-----+ +----v-----+ | +----------v-------+  +--v-+ +---v---+ |
+  //  |0, 3, 5, 8, 9| |0, 5, 7, 9| | |And Iterator: 0, 1|  |0, 5| |0, 1, 5| |
+  //  +-------------+ +----------+ | +----------+-------+  +----+ +-------+ |
+  //                               |            |                           |
+  //                               |       +----+-+---+                     |
+  //                               |       |      |   |                     |
+  //                               | +-----v-+ +--v-+ |               +-----+
+  //                               | |0, 1, 6| |0, 1| |               |
+  //                               | +-------+ +----+ |            +--v--+
+  //                               |                  |            |Empty|
+  //                  +------------v--------+     +---v-------+    +-----+
+  //                  |And Iterator: 1, 5, 8|     |0, 1, 5, 60|
+  //                  +------------+---------     +-----------+
+  //                               |
+  //                  +------------+------------+
+  //                  |                         |
+  //   +--------------v------------+ +----------+-----------------------+
+  //   |And Iterator: 1, 5, 7, 8, 9| |Or Iterator: 0, 1, 4, 5, 8, 10, 42|
+  //   +--------------+------------+ +----------+-----------------------+
+  //                  |                         |
+  //     +-----------------------+     +--------+------+-------+
+  //     |            |          |     |        |      |       |
+  //   +-v-+        +-v-+      +-v-+ +-v-+    +-v-+  +-v-+   +-v-+
+  //   |...|        |...|      |...| |...|    |...|  |...|   |...|
+  //   +---+        +---+      +---+ +---+    +---+  +---+   +---+
+  //
+
+  PostingList FirstList = {1, 3, 5, 8, 9};
+  PostingList SecondList = {1, 5, 7, 9};
+
+  vector<unique_ptr<QueryIterator>> Children;
+  Children.push_back(constructDocumentIterator(FirstList));
+  Children.push_back(constructDocumentIterator(SecondList));
+
+  // First Level And Iterator: [1, 5, 9]
+  auto LeftSubtreeAnd = constructAndIterator(move(Children));
+
+  EXPECT_EQ(LeftSubtreeAnd->cost(), min(FirstList.size(), SecondList.size()));
+
+  PostingList LeftSubtreeFirstList = {0, 1, 2, 5, 6, 7, 8, 9, 10, 42};
+  PostingList LeftSubtreeSecondList = {0, 1, 2, 5, 6, 7, 8, 9};
+  PostingList LeftSubtreeThirdList = {1, 4, 5, 7, 8, 9, 50, 300, 9000};
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(LeftSubtreeFirstList));
+  Children.push_back(constructDocumentIterator(LeftSubtreeSecondList));
+  Children.push_back(constructDocumentIterator(LeftSubtreeThirdList));
+
+  // Bottom Level Left And Iterator: [1, 5, 7, 8, 9]
+  auto BottomLevelLeftAnd = constructAndIterator(move(Children));
+
+  EXPECT_EQ(BottomLevelLeftAnd->cost(),
+            min({LeftSubtreeFirstList.size(), LeftSubtreeSecondList.size(),
+                 LeftSubtreeThirdList.size()}));
+
+  PostingList BottomSubtreeFirstList = {0, 4, 5};
+  PostingList BottomSubtreeSecondList = {0, 1, 10};
+  PostingList BottomSubtreeThirdList = {42};
+  PostingList BottomSubtreeFourthList = {4, 8};
+  PostingList BottomSubtreeEmptyList;
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(BottomSubtreeFirstList));
+  Children.push_back(constructDocumentIterator(BottomSubtreeSecondList));
+  Children.push_back(constructDocumentIterator(BottomSubtreeThirdList));
+  Children.push_back(constructDocumentIterator(BottomSubtreeFourthList));
+  Children.push_back(constructDocumentIterator(BottomSubtreeEmptyList));
+
+  // Bottom Level Right Or Iterator: [0, 1, 4, 5, 8, 10, 42]
+  auto BottomLevelRightOr = constructOrIterator(move(Children));
+
+  EXPECT_EQ(BottomLevelRightOr->cost(),
+            max({BottomSubtreeFirstList.size(), BottomSubtreeSecondList.size(),
+                 BottomSubtreeThirdList.size(), BottomSubtreeFourthList.size(),
+                 BottomSubtreeEmptyList.size()}));
+
+  auto Cost = std::min(BottomLevelLeftAnd->cost(), BottomLevelRightOr->cost());
+
+  Children.clear();
+  Children.push_back(move(BottomLevelLeftAnd));
+  Children.push_back(move(BottomLevelRightOr));
+
+  // First Level Middle And Iterator: [1, 5, 8]
+  auto MiddleSubtreeAnd = constructAndIterator(move(Children));
+
+  EXPECT_EQ(MiddleSubtreeAnd->cost(), Cost);
+
+  const PostingList RightSubtreeAndFirstList = {0, 1, 6};
+  const PostingList RightSubtreeAndSecondList = {0, 1};
+  const PostingList RightSubtreeAndThirdList = {0, 1, 5, 60};
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(RightSubtreeAndFirstList));
+  Children.push_back(constructDocumentIterator(RightSubtreeAndSecondList));
+  Children.push_back(constructDocumentIterator(RightSubtreeAndThirdList));
+  // And Iterator in rightmost subtree, child of first level Or Iterator: [0, 1]
+  auto RightSubtreeAndIterator = constructAndIterator(move(Children));
+
+  EXPECT_EQ(
+      RightSubtreeAndIterator->cost(),
+      min({RightSubtreeAndFirstList.size(), RightSubtreeAndSecondList.size(),
+           RightSubtreeAndThirdList.size()}));
+
+  const PostingList RightSubtreeFirstList = {0, 5};
+  const PostingList RightSubtreeSecondList = {0, 1, 5};
+  const PostingList RightSubtreeEmptyList = {0, 1, 5};
+
+  Cost = max({RightSubtreeAndFirstList.size(), RightSubtreeAndSecondList.size(),
+              RightSubtreeEmptyList.size(), RightSubtreeAndIterator->cost()});
+
+  Children.clear();
+  Children.push_back(constructDocumentIterator(RightSubtreeFirstList));
+  Children.push_back(constructDocumentIterator(RightSubtreeSecondList));
+  Children.push_back(constructDocumentIterator(RightSubtreeEmptyList));
+  Children.push_back(move(RightSubtreeAndIterator));
+  // Rightmost first level Or iterator, child of the root iterator: [0, 1, 5]
+  auto RightSubtreeOr = constructOrIterator(move(Children));
+
+  EXPECT_EQ(RightSubtreeOr->cost(), Cost);
+
+  Cost = std::min({LeftSubtreeAnd->cost(), MiddleSubtreeAnd->cost(),
+                   RightSubtreeOr->cost()});
+
+  Children.clear();
+  Children.push_back(move(LeftSubtreeAnd));
+  Children.push_back(move(MiddleSubtreeAnd));
+  Children.push_back(move(RightSubtreeOr));
+  // Root of the query tree: [1, 5]
+  auto Root = constructAndIterator(move(Children));
+
+  EXPECT_EQ(Root->cost(), Cost);
+
+  EXPECT_EQ(Root->reachedEnd(), false);
+  EXPECT_EQ(Root->peek(), 1U);
+  EXPECT_EQ(Root->advanceTo(0), false);
+  // Advance multiple times. Shouldn't do anything.
+  EXPECT_EQ(Root->advanceTo(1), false);
+  EXPECT_EQ(Root->advanceTo(0), false);
+  EXPECT_EQ(Root->peek(), 1U);
+  EXPECT_EQ(Root->advance(), false);
+  EXPECT_EQ(Root->peek(), 5U);
+  EXPECT_EQ(Root->advanceTo(5), false);
+  EXPECT_EQ(Root->advanceTo(9000), true);
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang