[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

26 ↗

(On Diff #156270)

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

39 ↗

(On Diff #156270)

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

43 ↗

(On Diff #156270)

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

44 ↗

(On Diff #156270)

could reasonably call this operator*

53 ↗

(On Diff #156270)

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)

59 ↗

(On Diff #156270)

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

63 ↗

(On Diff #156270)

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

76 ↗

(On Diff #156270)

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.

83 ↗

(On Diff #156270)

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

39 ↗

(On Diff #156270)

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.

44 ↗

(On Diff #156270)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

this is done I think.

43 ↗

(On Diff #156725)

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

52 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

please spell these out (local style)

27 ↗

(On Diff #156725)

using namespace llvm

67 ↗

(On Diff #156725)

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

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

75 ↗

(On Diff #156725)

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

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

98 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

nit: & should be enough?

175 ↗

(On Diff #156725)

can this just be a static function?

196 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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 ↗

(On Diff #156725)

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

47 ↗

(On Diff #157206)

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.

48 ↗

(On Diff #157206)

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

66 ↗

(On Diff #157206)

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.

165 ↗

(On Diff #157206)

s/0/1/ for AND lists?

186 ↗

(On Diff #157206)

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.

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   index/CanonicalIncludes.cpp
   index/FileIndex.cpp
   index/Index.cpp
   index/MemIndex.cpp
   index/Merge.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
+  index/dex/Iterator.cpp
   index/dex/Trigram.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangDriver
   clangFormat

clangd/index/dex/Iterator.h

+//===--- Iterator.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.
+//
+//===----------------------------------------------------------------------===//
+//
+// Symbol index queries consist of specific requirements for the requested
+// symbol, such as high fuzzy matching score, scope, type etc. The lists of all
+// symbols matching some criteria (e.g. belonging to "clang::clangd::" scope)
+// are expressed in a form of Search Tokens which are stored in the inverted
+// index.  Inverted index maps these tokens to the posting lists - sorted ( by
+// symbol quality) sequences of symbol IDs matching the token, e.g.  scope token
+// "clangd::clangd::" is mapped to the list of IDs of all symbols which are
+// declared in this namespace. Search queries are build from a set of
+// requirements which can be combined with each other forming the query trees.
+// The leafs of such trees are posting lists, and the nodes are operations on
+// these posting lists, e.g. intersection or union.  Efficient processing of
+// these multi-level queries is handled by Iterators.  Iterators advance through
+// all leaf posting lists producing the result of search query, which preserves
+// the sorted order of IDs. Having the resulting IDs sorted is important,
+// because it allows receiving a certain number of the most valuable items (e.g.
+// symbols with highest quality which was the sorting key in the first place)
+// without processing all items with requested properties (this might not be
+// computationally effective if search request is not very restrictive).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <memory>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+/// Symbol position in the list of all index symbols sorted by a pre-computed
+/// symbol quality.
+using DocID = uint32_t;
+/// Contains sorted sequence of DocIDs all of which belong to symbols matching
+/// certain criteria, i.e. containing a Search Token. PostingLists are values
+/// for the inverted index.
+using PostingList = std::vector<DocID>;
+/// Immutable reference to PostingList object.
+using PostingListRef = llvm::ArrayRef<DocID>;
+
+/// Iterator is the interface for Query Tree node. The simplest type of Iterator
+/// is DocumentIterator which is simply a wrapper around PostingList iterator
+/// and serves as the Query Tree leaf. More sophisticated examples of iterators
+/// can manage intersection, union of the elements produced by other iterators
+/// (their children) to form a multi-level Query Tree. The interface is designed
+/// to be extensible in order to support multiple types of iterators.
+class Iterator {
+  // FIXME(kbobyrev): Provide callback for matched documents.
+  // FIXME(kbobyrev): Implement new types of iterators: Label, Boost (with
+  // scoring), Limit.
+  // FIXME(kbobyrev): Implement iterator cost, an estimate of advance() calls
+  // before iterator exhaustion.
+public:
+  /// Returns true if all valid DocIDs were processed and hence the iterator is
+  /// exhausted.
+  virtual bool reachedEnd() const = 0;
+  /// Moves to next valid DocID. If it doesn't exist, the iterator is exhausted
+  /// and proceeds to the END.
+  ///
+  /// Note: reachedEnd() must be false.
+  virtual void advance() = 0;
+  /// Moves to the first valid DocID which is equal or higher than given ID. If
+  /// it doesn't exist, the iterator is exhausted and proceeds to the END.
+  ///
+  /// Note: reachedEnd() must be false.
+  virtual void advanceTo(DocID ID) = 0;
+  /// Returns the current element this iterator points to.
+  ///
+  /// Note: reachedEnd() must be false.
+  virtual DocID peek() const = 0;
+
+  virtual ~Iterator() {}
+
+  /// 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, ...]" where IDN is N-th PostingList entry.
+  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                                       const Iterator &Iterator) {
+    return Iterator.dump(OS);
+  }
+
+private:
+  virtual llvm::raw_ostream &dump(llvm::raw_ostream &OS) const = 0;
+};
+
+/// Exhausts given iterator and returns all processed DocIDs. The result
+/// contains sorted DocumentIDs.
+std::vector<DocID> consume(Iterator &It);
+
+/// Returns a document iterator over given PostingList.
+std::unique_ptr<Iterator> create(PostingListRef Documents);
+
+/// Returns AND Iterator which performs the intersection of the PostingLists of
+/// its children.
+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);
+
+/// This allows createAnd({create(...), create(...)}) syntax.
+template <size_t Size>
+std::unique_ptr<Iterator>
+createAnd(std::unique_ptr<Iterator>(&&Children)[Size]) {
+  std::vector<std::unique_ptr<Iterator>> Elements;
+  std::move(begin(Children), end(Children), std::back_inserter(Elements));
+  return createAnd(move(Elements));
+}
+
+/// This allows createOr({create(...), create(...)}) syntax.
+template <size_t Size>
+std::unique_ptr<Iterator>
+createOr(std::unique_ptr<Iterator>(&&Children)[Size]) {
+  std::vector<std::unique_ptr<Iterator>> Elements;
+  std::move(begin(Children), end(Children), std::back_inserter(Elements));
+  return createOr(move(Elements));
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+#endif

clangd/index/dex/Iterator.cpp

+//===--- Iterator.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 "Iterator.h"
+#include <algorithm>
+#include <cassert>
+#include <numeric>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+namespace {
+
+/// Implements Iterator over a PostingList. DocumentIterator is the most basic
+/// iterator: it doesn't have any children (hence it is the leaf of iterator
+/// tree) and is simply a wrapper around PostingList::const_iterator.
+class DocumentIterator : public Iterator {
+public:
+  DocumentIterator(PostingListRef Documents)
+      : Documents(Documents), Index(std::begin(Documents)) {}
+
+  bool reachedEnd() const override { return Index == std::end(Documents); }
+
+  /// Advances cursor to the next item.
+  void advance() override {
+    assert(!reachedEnd() && "DocumentIterator can't advance at the end.");
+    ++Index;
+  }
+
+  /// Applies binary search to advance cursor to the next item with DocID equal
+  /// or higher than the given one.
+  void advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "DocumentIterator can't advance at the end.");
+    Index = std::lower_bound(Index, std::end(Documents), ID);
+  }
+
+  DocID peek() const override {
+    assert(!reachedEnd() && "DocumentIterator can't call peek() at the end.");
+    return *Index;
+  }
+
+  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    OS << '[';
+    auto Separator = "";
+    for (const auto &ID : Documents) {
+      OS << Separator << ID;
+      Separator = ", ";
+    }
+    OS << ']';
+    return OS;
+  }
+
+private:
+  PostingListRef Documents;
+  PostingListRef::const_iterator Index;
+};
+
+/// Implements Iterator over the intersection of other iterators.
+///
+/// AndIterator iterates through common items among all children. It becomes
+/// exhausted as soon as any child becomes exhausted. After each mutation, the
+/// iterator restores the invariant: all children must point to the same item.
+class AndIterator : public Iterator {
+public:
+  AndIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)
+      : Children(std::move(AllChildren)) {
+    assert(!Children.empty() && "AndIterator should have at least one child.");
+    // Establish invariants.
+    sync();
+  }
+
+  bool reachedEnd() const override { return ReachedEnd; }
+
+  /// Advances all children to the next common item.
+  void advance() override {
+    assert(!reachedEnd() && "AndIterator can't call advance() at the end.");
+    Children.front()->advance();
+    sync();
+  }
+
+  /// Advances all children to the next common item with DocumentID >= ID.
+  void advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "AndIterator can't call advanceTo() at the end.");
+    Children.front()->advanceTo(ID);
+    sync();
+  }
+
+  DocID peek() const override { return Children.front()->peek(); }
+
+  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    OS << "(& ";
+    auto Separator = "";
+    for (const auto &Child : Children) {
+      OS << Separator << *Child;
+      Separator = " ";
+    }
+    OS << ')';
+    return OS;
+  }
+
+private:
+  /// Restores class invariants: each child will point to the same element after
+  /// sync.
+  void sync() {
+    ReachedEnd |= Children.front()->reachedEnd();
+    if (ReachedEnd)
+      return;
+    auto SyncID = Children.front()->peek();
+    // Indicates whether any child needs to be advanced to new SyncID.
+    bool NeedsAdvance = false;
+    do {
+      NeedsAdvance = false;
+      for (auto &Child : Children) {
+        Child->advanceTo(SyncID);
+        ReachedEnd |= Child->reachedEnd();
+        // If any child reaches end And iterator can not match any other items.
+        // In this case, just terminate the process.
+        if (ReachedEnd)
+          return;
+        // 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.
+        // FIXME(kbobyrev): This is not a very optimized version; after costs
+        // are introduced, cycle should break whenever ID exceeds current one
+        // and cheapest children should be advanced over again.
+        if (Child->peek() > SyncID) {
+          SyncID = Child->peek();
+          NeedsAdvance = true;
+        }
+      }
+    } while (NeedsAdvance);
+  }
+
+  /// AndIterator owns its children and ensures that all of them point to the
+  /// same element. As soon as one child gets exhausted, AndIterator can no
+  /// longer advance and has reached its end.
+  std::vector<std::unique_ptr<Iterator>> Children;
+  /// Indicates whether any child is exhausted. It is cheaper to maintain and
+  /// update the field, rather than traversing the whole subtree in each
+  /// reachedEnd() call.
+  bool ReachedEnd = false;
+};
+
+/// Implements Iterator over the union of other iterators.
+///
+/// OrIterator iterates through all items which can be pointed to by at least
+/// one child. To preserve the sorted order, this iterator always advances the
+/// child with smallest Child->peek() value. OrIterator becomes exhausted as
+/// soon as all of its children are exhausted.
+class OrIterator : public Iterator {
+public:
+  OrIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)
+      : Children(std::move(AllChildren)) {
+    assert(Children.size() > 0 && "Or Iterator must have at least one child.");
+  }
+
+  /// Returns true if all children are exhausted.
+  bool reachedEnd() const override {
+    return std::all_of(begin(Children), end(Children),
+                       [](const std::unique_ptr<Iterator> &Child) {
+                         return Child->reachedEnd();
+                       });
+  }
+
+  /// Moves each child pointing to the smallest DocID to the next item.
+  void advance() override {
+    assert(!reachedEnd() &&
+           "OrIterator must have at least one child to advance().");
+    const auto SmallestID = peek();
+    for (const auto &Child : Children)
+      if (!Child->reachedEnd() && Child->peek() == SmallestID)
+        Child->advance();
+  }
+
+  /// Advances each child to the next existing element with DocumentID >= ID.
+  void advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "Can't advance iterator after it reached the end.");
+    for (const auto &Child : Children)
+      if (!Child->reachedEnd())
+        Child->advanceTo(ID);
+  }
+
+  /// Returns the element under cursor of the child with smallest Child->peek()
+  /// value.
+  DocID peek() const override {
+    assert(!reachedEnd() &&
+           "OrIterator must have at least one child to peek().");
+    DocID Result = std::numeric_limits<DocID>::max();
+
+    for (const auto &Child : Children)
+      if (!Child->reachedEnd())
+        Result = std::min(Result, Child->peek());
+
+    return Result;
+  }
+
+  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+    OS << "(| ";
+    auto Separator = "";
+    for (const auto &Child : Children) {
+      OS << Separator << *Child;
+      Separator = " ";
+    }
+    OS << ')';
+    return OS;
+  }
+
+private:
+  // FIXME(kbobyrev): Would storing Children in min-heap be faster?
+  std::vector<std::unique_ptr<Iterator>> Children;
+};
+
+} // end namespace
+
+std::vector<DocID> consume(Iterator &It) {
+  std::vector<DocID> Result;
+  for (; !It.reachedEnd(); It.advance())
+    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));
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang

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/Iterator.h"
 #include "index/dex/Token.h"
 #include "index/dex/Trigram.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/raw_ostream.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
-
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
+using ::testing::ElementsAre;
+
+TEST(DexIndexIterators, DocumentIterator) {
+  auto DocIterator = create({4, 7, 8, 20, 42, 100});
+
+  EXPECT_EQ(DocIterator->peek(), 4U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  DocIterator->advance();
+  EXPECT_EQ(DocIterator->peek(), 7U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  DocIterator->advanceTo(20);
+  EXPECT_EQ(DocIterator->peek(), 20U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  DocIterator->advanceTo(65);
+  EXPECT_EQ(DocIterator->peek(), 100U);
+  EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+  DocIterator->advanceTo(420);
+  EXPECT_EQ(DocIterator->reachedEnd(), true);
+}
+
+TEST(DexIndexIterators, AndWithEmpty) {
+  const PostingList L0;
+  const PostingList L1 = {0, 5, 7, 10, 42, 320, 9000};
+
+  auto AndEmpty = createAnd({create(L0)});
+  EXPECT_EQ(AndEmpty->reachedEnd(), true);
+
+  auto AndWithEmpty = createAnd({create(L0), create(L1)});
+  EXPECT_EQ(AndWithEmpty->reachedEnd(), true);
+
+  EXPECT_THAT(consume(*AndWithEmpty), ElementsAre());
+}
+
+TEST(DexIndexIterators, AndTwoLists) {
+  const PostingList L0 = {0, 5, 7, 10, 42, 320, 9000};
+  const PostingList L1 = {0, 4, 7, 10, 30, 60, 320, 9000};
+
+  auto And = createAnd({create(L1), create(L0)});
+
+  EXPECT_EQ(And->reachedEnd(), false);
+  EXPECT_THAT(consume(*And), ElementsAre(0U, 7U, 10U, 320U, 9000U));
+
+  And = createAnd({create(L0), create(L1)});
+
+  And->advanceTo(0);
+  EXPECT_EQ(And->peek(), 0U);
+  And->advanceTo(5);
+  EXPECT_EQ(And->peek(), 7U);
+  And->advanceTo(10);
+  EXPECT_EQ(And->peek(), 10U);
+  And->advanceTo(42);
+  EXPECT_EQ(And->peek(), 320U);
+  And->advanceTo(8999);
+  EXPECT_EQ(And->peek(), 9000U);
+  And->advanceTo(9001);
+}
+
+TEST(DexIndexIterators, AndThreeLists) {
+  const PostingList L0 = {0, 5, 7, 10, 42, 320, 9000};
+  const PostingList L1 = {0, 4, 7, 10, 30, 60, 320, 9000};
+  const PostingList L2 = {1, 4, 7, 11, 30, 60, 320, 9000};
+
+  auto And = createAnd({create(L0), create(L1), create(L2)});
+  EXPECT_EQ(And->peek(), 7U);
+  And->advanceTo(300);
+  EXPECT_EQ(And->peek(), 320U);
+  And->advanceTo(100000);
+
+  EXPECT_EQ(And->reachedEnd(), true);
+}
+
+TEST(DexIndexIterators, OrWithEmpty) {
+  const PostingList L0;
+  const PostingList L1 = {0, 5, 7, 10, 42, 320, 9000};
+
+  auto OrEmpty = createOr({create(L0)});
+  EXPECT_EQ(OrEmpty->reachedEnd(), true);
+
+  auto OrWithEmpty = createOr({create(L0), create(L1)});
+  EXPECT_EQ(OrWithEmpty->reachedEnd(), false);
+
+  EXPECT_THAT(consume(*OrWithEmpty),
+              ElementsAre(0U, 5U, 7U, 10U, 42U, 320U, 9000U));
+}
+
+TEST(DexIndexIterators, OrTwoLists) {
+  const PostingList L0 = {0, 5, 7, 10, 42, 320, 9000};
+  const PostingList L1 = {0, 4, 7, 10, 30, 60, 320, 9000};
+
+  auto Or = createOr({create(L0), create(L1)});
+
+  EXPECT_EQ(Or->reachedEnd(), false);
+  EXPECT_EQ(Or->peek(), 0U);
+  Or->advance();
+  EXPECT_EQ(Or->peek(), 4U);
+  Or->advance();
+  EXPECT_EQ(Or->peek(), 5U);
+  Or->advance();
+  EXPECT_EQ(Or->peek(), 7U);
+  Or->advance();
+  EXPECT_EQ(Or->peek(), 10U);
+  Or->advance();
+  EXPECT_EQ(Or->peek(), 30U);
+  Or->advanceTo(42);
+  EXPECT_EQ(Or->peek(), 42U);
+  Or->advanceTo(300);
+  EXPECT_EQ(Or->peek(), 320U);
+  Or->advanceTo(9000);
+  EXPECT_EQ(Or->peek(), 9000U);
+  Or->advanceTo(9001);
+  EXPECT_EQ(Or->reachedEnd(), true);
+
+  Or = createOr({create(L0), create(L1)});
+
+  EXPECT_THAT(consume(*Or),
+              ElementsAre(0U, 4U, 5U, 7U, 10U, 30U, 42U, 60U, 320U, 9000U));
+}
+
+TEST(DexIndexIterators, OrThreeLists) {
+  const PostingList L0 = {0, 5, 7, 10, 42, 320, 9000};
+  const PostingList L1 = {0, 4, 7, 10, 30, 60, 320, 9000};
+  const PostingList L2 = {1, 4, 7, 11, 30, 60, 320, 9000};
+
+  auto Or = createOr({create(L0), create(L1), create(L2)});
+
+  EXPECT_EQ(Or->reachedEnd(), false);
+  EXPECT_EQ(Or->peek(), 0U);
+
+  Or->advance();
+  EXPECT_EQ(Or->peek(), 1U);
+
+  Or->advance();
+  EXPECT_EQ(Or->peek(), 4U);
+
+  Or->advanceTo(7);
+
+  Or->advanceTo(59);
+  EXPECT_EQ(Or->peek(), 60U);
+
+  Or->advanceTo(9001);
+  EXPECT_EQ(Or->reachedEnd(), true);
+}
+
+// FIXME(kbobyrev): The testcase below is similar to what is expected in real
+// queries. It should be updated once new iterators (such as boosting, limiting,
+// etc iterators) appear. However, it is not exhaustive and it would be
+// beneficial to implement automatic generation of query trees for more
+// comprehensive testing.
+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---+
+  //  |1, 3, 5, 8, 9| |1, 5, 7, 9|           |Empty|    |0, 5|    |0, 1, 5|
+  //  +-------------+ +----------+           +-----+    +----+    +-------+
+
+  // Root of the query tree: [1, 5]
+  auto Root = createAnd({
+      // Lower And Iterator: [1, 5, 9]
+      createAnd({create({1, 3, 5, 8, 9}), create({1, 5, 7, 9})}),
+      // Lower Or Iterator: [0, 1, 5]
+      createOr({create({0, 5}), create({0, 1, 5}), create({})}),
+  });
+
+  EXPECT_EQ(Root->reachedEnd(), false);
+  EXPECT_EQ(Root->peek(), 1U);
+  Root->advanceTo(0);
+  // Advance multiple times. Shouldn't do anything.
+  Root->advanceTo(1);
+  Root->advanceTo(0);
+  EXPECT_EQ(Root->peek(), 1U);
+  Root->advance();
+  EXPECT_EQ(Root->peek(), 5U);
+  Root->advanceTo(5);
+  EXPECT_EQ(Root->peek(), 5U);
+  Root->advanceTo(9000);
+  EXPECT_EQ(Root->reachedEnd(), true);
+}
+
+TEST(DexIndexIterators, StringRepresentation) {
+  EXPECT_EQ(llvm::to_string(*(create({4, 7, 8, 20, 42, 100}))),
+            "[4, 7, 8, 20, 42, 100]");
+
+  auto Nested = createAnd({
+      createAnd({create({1, 3, 5, 8, 9}), create({1, 5, 7, 9})}),
+      createOr({create({0, 5}), create({0, 1, 5}), create({})}),
+  });
+
+  EXPECT_EQ(llvm::to_string(*Nested),
+            "(& (& [1, 3, 5, 8, 9] [1, 5, 7, 9]) (| [0, 5] [0, 1, 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);
 }