Index: clang-tools-extra/clangd/CMakeLists.txt
===================================================================
--- clang-tools-extra/clangd/CMakeLists.txt
+++ clang-tools-extra/clangd/CMakeLists.txt
@@ -34,6 +34,7 @@
   TUScheduler.cpp
   URI.cpp
   XRefs.cpp
+
   index/CanonicalIncludes.cpp
   index/FileIndex.cpp
   index/Index.cpp
@@ -42,6 +43,8 @@
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
+  index/dex/QueryIterator.cpp
+
   LINK_LIBS
   clangAST
   clangASTMatchers
Index: clang-tools-extra/clangd/index/dex/QueryIterator.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/dex/QueryIterator.h
@@ -0,0 +1,78 @@
+//===--- 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
Index: clang-tools-extra/clangd/index/dex/QueryIterator.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/dex/QueryIterator.cpp
@@ -0,0 +1,279 @@
+//===--- 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
Index: clang-tools-extra/unittests/clangd/CMakeLists.txt
===================================================================
--- clang-tools-extra/unittests/clangd/CMakeLists.txt
+++ clang-tools-extra/unittests/clangd/CMakeLists.txt
@@ -15,9 +15,10 @@
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
+  DexIndexTests.cpp
   DraftStoreTests.cpp
-  FileIndexTests.cpp
   FileDistanceTests.cpp
+  FileIndexTests.cpp
   FindSymbolsTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
@@ -27,11 +28,11 @@
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SyncAPI.cpp
+  TUSchedulerTests.cpp
   TestFS.cpp
   TestTU.cpp
   ThreadingTests.cpp
   TraceTests.cpp
-  TUSchedulerTests.cpp
   URITests.cpp
   XRefsTests.cpp
   )
Index: clang-tools-extra/unittests/clangd/DexIndexTests.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/unittests/clangd/DexIndexTests.cpp
@@ -0,0 +1,487 @@
+//===--- 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