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/Iterator.cpp
+
   LINK_LIBS
   clangAST
   clangASTMatchers
Index: clang-tools-extra/clangd/index/dex/Iterator.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/dex/Iterator.h
@@ -0,0 +1,87 @@
+//===--- 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.
+//
+//===----------------------------------------------------------------------===//
+//
+// 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 <algorithm>
+#include <memory>
+#include <vector>
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+using DocID = uint32_t;
+using PostingList = std::vector<DocID>;
+using PostingListRef = llvm::ArrayRef<DocID>;
+
+// FIXME(kbobyrev): Provide callback for matched documents.
+// FIXME(kbobyrev): Implement new types of iterators: Label, Boost, Limit.
+// FIXME(kbobyrev): Document this one properly.
+class Iterator {
+public:
+  virtual bool reachedEnd() const = 0;
+  virtual void advance() = 0;
+  virtual void advanceTo(DocID Rank) = 0;
+  /// Returns item under the cursor.
+  virtual DocID peek() const = 0;
+
+  virtual ~Iterator() {}
+
+  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                                       const Iterator &Iterator) {
+    return Iterator.dump(OS);
+  }
+
+  static std::vector<DocID> consume(Iterator &It);
+
+  // FIXME(kbobyrev): Brief documentation of DocumentIterator here.
+  static std::unique_ptr<Iterator> create(PostingListRef Documents);
+
+  // FIXME(kbobyrev): Brief documentation of AndIterator here.
+  template <size_t Size>
+  static 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));
+  }
+
+  static std::unique_ptr<Iterator>
+  createAnd(std::vector<std::unique_ptr<Iterator>> Children);
+
+  // FIXME(kbobyrev): Brief documentation of OrIterator here.
+  template <size_t Size>
+  static 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));
+  }
+
+  static std::unique_ptr<Iterator>
+  createOr(std::vector<std::unique_ptr<Iterator>> Children);
+
+private:
+  virtual llvm::raw_ostream &dump(llvm::raw_ostream &OS) const = 0;
+};
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+#endif
Index: clang-tools-extra/clangd/index/dex/Iterator.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/dex/Iterator.cpp
@@ -0,0 +1,258 @@
+//===--- 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 {
+
+/// Implements Iterator over a PostingList.
+// FIXME(kbobyrev): Document this one properly.
+class DocumentIterator : public Iterator {
+public:
+  DocumentIterator(PostingListRef Documents) : Documents(Documents), Index(0) {}
+
+  bool reachedEnd() const override { return Index == Documents.size(); }
+
+  /// Increments Index.
+  void advance() override {
+    assert(!reachedEnd() && "DocumentIterator can't advance at the end.");
+    ++Index;
+  }
+
+  // FIXME(kbobyrev): Properly document this one.
+  void 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();
+  }
+
+  DocID peek() const override {
+    assert(!reachedEnd() && "DocumentIterator can't call peek() at the end.");
+    return Documents[Index];
+  }
+
+  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;
+  DocID Index;
+};
+
+// FIXME(kbobyrev): Document this one properly.
+class AndIterator : public Iterator {
+public:
+  AndIterator(std::vector<std::unique_ptr<Iterator>> &&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());
+    }
+    // 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.
+  void advance() override {
+    assert(!reachedEnd() && "AndIterator can't call advance() at the end.");
+    Children.front()->advance();
+    ReachedEnd = Children.front()->reachedEnd();
+    DocID HighestID = 0;
+    if (!ReachedEnd)
+      HighestID = Children.front()->peek();
+    bool ChangedID = true;
+    while (ChangedID && !ReachedEnd) {
+      ChangedID = false;
+      for (auto &Child : Children) {
+        Child->advanceTo(HighestID);
+        ReachedEnd = Child->reachedEnd();
+        if (ReachedEnd)
+          break;
+        if (Child->peek() > HighestID) {
+          HighestID = Child->peek();
+          ChangedID = true;
+        }
+      }
+    }
+  }
+
+  // FIXME(kbobyrev): Properly document this one.
+  void advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "AndIterator can't call advanceTo() at the end.");
+    bool NeedsAdvance = false;
+    for (auto &Child : Children) {
+      Child->advanceTo(ID);
+      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)
+        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);
+  }
+
+  DocID peek() const override { return Children.front()->peek(); }
+
+  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<Iterator>> Children;
+  // Store and update local state, otherwise each reachedEnd() call would
+  // require the whole subtree traversal.
+  bool ReachedEnd;
+};
+
+// FIXME(kbobyrev): Document this one properly.
+// FIXME(kbobyrev): Currently, the implementation is inefficient because peek()
+// and reachedEnd() are computed in O(Children.size()). This can be fixed by
+// maintaining heap in Children - both peek() and reachedEnd() will become O(1),
+// the only overhead will be that advance() will have to pop each child after
+// calling Child->advance() and push it back to the heap to maintain the
+// structure. The additional complexity of advance() will be at most
+// 2 * N * log(N), where N = Children.size(). Also, the heap will be initialized
+// in constructor, which will yield at most 3 * N additional atomic operations.
+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.");
+  }
+
+  bool reachedEnd() const override {
+    for (auto &Child : Children)
+      if (!Child->reachedEnd())
+        return false;
+    return true;
+  }
+
+  void advance() override {
+    assert(!reachedEnd() &&
+           "OrIterator must have at least one child to advance().");
+    const auto HighestID = peek();
+    DocID ChildrenToAdvance = 0;
+    while ((ChildrenToAdvance++ < Children.size()) && !reachedEnd() &&
+           (peek() == HighestID)) {
+      for (auto &Child : Children) {
+        if (!Child->reachedEnd() && Child->peek() == HighestID) {
+          Child->advance();
+        }
+      }
+    }
+  }
+
+  void advanceTo(DocID ID) override {
+    assert(!reachedEnd() && "Can't advance iterator after it reached the end.");
+    for (auto &Child : Children) {
+      if (!Child->reachedEnd()) {
+        Child->advanceTo(ID);
+      }
+    }
+  }
+
+  DocID peek() const override {
+    assert(!reachedEnd() &&
+           "OrIterator must have at least one child to peek().");
+    bool FoundFirstValid = false;
+    DocID Result = 0;
+    for (auto &Child : Children) {
+      if (!Child->reachedEnd()) {
+        if (!FoundFirstValid) {
+          Result = Child->peek();
+          FoundFirstValid = true;
+          continue;
+        }
+        Result = std::min(Result, Child->peek());
+      }
+    }
+    return Result;
+  }
+
+  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:
+  std::vector<std::unique_ptr<Iterator>> Children;
+};
+
+std::vector<DocID> Iterator::consume(Iterator &It) {
+  std::vector<DocID> Result;
+  while (!It.reachedEnd()) {
+    Result.push_back(It.peek());
+    It.advance();
+  }
+  return Result;
+}
+
+std::unique_ptr<Iterator> Iterator::create(PostingListRef Documents) {
+  return llvm::make_unique<DocumentIterator>(Documents);
+}
+
+std::unique_ptr<Iterator>
+Iterator::createAnd(std::vector<std::unique_ptr<Iterator>> Children) {
+  return llvm::make_unique<AndIterator>(move(Children));
+}
+
+std::unique_ptr<Iterator>
+Iterator::createOr(std::vector<std::unique_ptr<Iterator>> 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,201 @@
+//===--- 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 "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <string>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+using ::testing::ElementsAre;
+
+TEST(DexIndexIterators, DocumentIterator) {
+  auto DocIterator = Iterator::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);
+
+  EXPECT_EQ(llvm::to_string(*DocIterator), "[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};
+
+  auto And = Iterator::createAnd({Iterator::create(EmptyList)});
+
+  EXPECT_EQ(llvm::to_string(*And), "(& [])");
+
+  And = Iterator::createAnd(
+      {Iterator::create(EmptyList), Iterator::create(FirstList)});
+
+  EXPECT_EQ(llvm::to_string(*And), "(& [] [0, 5, 7, 10, 42, 320, 9000])");
+
+  And = Iterator::createAnd(
+      {Iterator::create(FirstList), Iterator::create(SecondList)});
+
+  EXPECT_EQ(And->reachedEnd(), false);
+  EXPECT_THAT(Iterator::consume(*And), ElementsAre(0U, 7U, 10U, 320U, 9000U));
+
+  EXPECT_EQ(
+      llvm::to_string(*And),
+      "(& [0, 5, 7, 10, 42, 320, 9000] [0, 4, 7, 10, 30, 60, 320, 9000])");
+
+  And = Iterator::createAnd(
+      {Iterator::create(SecondList), Iterator::create(FirstList)});
+
+  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);
+
+  And = Iterator::createAnd({Iterator::create(FirstList),
+                             Iterator::create(SecondList),
+                             Iterator::create(ThirdList)});
+  EXPECT_EQ(And->peek(), 7U);
+  And->advanceTo(300);
+  EXPECT_EQ(And->peek(), 320U);
+  And->advanceTo(100000);
+
+  EXPECT_EQ(And->reachedEnd(), true);
+}
+
+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};
+
+  auto Or = Iterator::createOr({Iterator::create(EmptyList)});
+
+  EXPECT_EQ(Or->reachedEnd(), true);
+
+  Or = Iterator::createOr(
+      {Iterator::create(FirstList), Iterator::create(EmptyList)});
+
+  EXPECT_EQ(Or->reachedEnd(), false);
+  EXPECT_EQ(Or->peek(), 0U);
+  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(), 42U);
+  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);
+
+  Or = Iterator::createOr({Iterator::create(FirstList),
+                           Iterator::create(SecondList),
+                           Iterator::create(ThirdList)});
+
+  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);
+}
+
+// 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---+
+  //  |0, 3, 5, 8, 9| |0, 5, 7, 9|           |Empty|    |0, 5|    |0, 1, 5|
+  //  +-------------+ +----------+           +-----+    +----+    +-------+
+
+  // Root of the query tree: [1, 5]
+  auto Root = Iterator::createAnd({
+      // Lower And Iterator: [1, 5, 9]
+      Iterator::createAnd(
+          {Iterator::create({1, 3, 5, 8, 9}), Iterator::create({1, 5, 7, 9})}),
+      // Lower Or Iterator: [0, 1, 5]
+      Iterator::createOr({Iterator::create({0, 5}), Iterator::create({0, 1, 5}),
+                          Iterator::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);
+  Root->advanceTo(9000);
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang