[clangd] Introduce PostingList interface

[kbobyrev]

Summary

This patch abstracts PostingList interface and reuses existing implementation. It will be used later to test different PostingList representations.

No functionality change is introduced, this patch is mostly refactoring so that the following patches could focus on functionality while not being too hard to review.

[kbobyrev]

There is not enough documentation right now, I should fix that before patch could be reviewed. This is a preview mode.

Also, Index size estimation is incorrect now and will be fixed in the next diff.

[kbobyrev]

Add documentation, don't expose PostingList interface implementations in the public API (similarly to Iterator).

[ioeric]

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

125

nit: InvertedIndex[TokenToPostingList.first] = buildSparsePostingList(...) ?

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

23

I'd probably call this something other than SparsePostingList. It doesn't really do anything fancier than just storing the vector. What if sparse posting lists have their own optimizations one day? So how about something more straightforward? E.g. VectorPostingList or PlainPostingList?

40

As this is just a helper class that is not exposed, I'd suggest making this a standalone class to make it easier to read.

[sammccall]

At a high level: making posting lists an abstract type adds another layer of indirection, which we can use to solve problems. It also has costs, mostly conceptual complexity.
What problems are we solving?

• if we want to dynamically use a different representation for different data/scenarios: this would be a good solution, do we have any evidence that this is the case? I thought the tentative conclusion was vbyte was good enough for all cases. What's the deal with dense/sparse?
• if it's too hard to experiment with different posting list types: how hard is it really? I'm not sure this justifies checking this change in.

I'd suggest as a first step making PostingList a concrete class - this would improve the API and enable experimentation. (Even experimentation with dynamically switching the implementation - it's easier behind a class boundary)

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

35

this talks a lot about how a posting list can be implemented, and what it interacts with - I'd suggest removing/reducing that and talking about what it is, instead :-)

55

why is the caller responsible for choosing the implementation?
It seems like buildPostingList could do this based on inspecting the docs

62

PostingList::create()?

[kbobyrev]

Don't create abstractions for now.

[kbobyrev]

Remove artifacts from assertion messages.

[sammccall]

Great!

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

11

And here

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

39

Why this dep? Seems circular

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

13

And can be traversed in order using an iterator

[kbobyrev]

Wording: traversed *in order*.

[kbobyrev]

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

39

Iterator interface uses DocID, so I guess it should depend on PostingList.h, shouldn't it?

[kbobyrev]

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

39

FWIW I tried to get rid of this dependency in the first place, but it seemed pretty hard, because the options I saw were either forward declaring (which isn't possible since it's practically typedef) it or introducing another using DocID = uint32_t in Iterator.h, which I decided not to do because of the code duplication. Another option would be to make both PostingList.h and Iterator.h depend on some common file, but semantically DocID seems to belong to the Iterator.h, so I didn't think that would be a good solution, too.

Is there something I could do to resolve that?

[kbobyrev]

Pull DocID to Iterator.h.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   index/MemIndex.cpp
   index/Merge.cpp
   index/Serialization.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
   index/dex/Dex.cpp
   index/dex/Iterator.cpp
+  index/dex/PostingList.cpp
   index/dex/Trigram.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangDriver
   clangFormat

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

 // transformations which will be eventually supported by Clangd.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H
 
 #include "Iterator.h"
+#include "PostingList.h"
 #include "Token.h"
 #include "Trigram.h"
 #include "index/Index.h"
 #include "index/MemIndex.h"
 #include "index/SymbolCollector.h"
 
 namespace clang {
 namespace clangd {
private:
   std::vector<float> SymbolQuality;
   llvm::DenseMap<SymbolID, const Symbol *> LookupTable;
   /// Inverted index is a mapping from the search token to the posting list,
   /// which contains all items which can be characterized by such search token.
   /// For example, if the search token is scope "std::", the corresponding
   /// posting list would contain all indices of symbols defined in namespace
   /// std. Inverted index is used to retrieve posting lists which are processed
   /// during the fuzzyFind process.
-  llvm::DenseMap<Token, PostingList> InvertedIndex;
+  llvm::DenseMap<Token, std::unique_ptr<PostingList>> InvertedIndex;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
   // Size of memory retained by KeepAlive.
   size_t BackingDataSize = 0;
 
   std::vector<std::string> URISchemes;
 };
 
 /// Returns Search Token for a number of parent directories of given Path.

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

for (const auto &ProximityURI :
       Result.emplace_back(Token::Kind::ProximityURI, ProximityURI);
   return Result;
 }
 
 // Constructs BOOST iterators for Path Proximities.
 std::vector<std::unique_ptr<Iterator>> createFileProximityIterators(
     llvm::ArrayRef<std::string> ProximityPaths,
     llvm::ArrayRef<std::string> URISchemes,
-    const llvm::DenseMap<Token, PostingList> &InvertedIndex) {
+    const llvm::DenseMap<Token, std::unique_ptr<PostingList>> &InvertedIndex) {
   std::vector<std::unique_ptr<Iterator>> BoostingIterators;
   // Deduplicate parent URIs extracted from the ProximityPaths.
   llvm::StringSet<> ParentURIs;
   llvm::StringMap<SourceParams> Sources;
   for (const auto &Path : ProximityPaths) {
     Sources[Path] = SourceParams();
     auto PathURI = URI::create(Path, URISchemes);
     if (!PathURI) {
std::vector<std::unique_ptr<Iterator>> createFileProximityIterators(
   // Proximity Path: the closer processed path is, the higher boosting factor.
   for (const auto &ParentURI : ParentURIs.keys()) {
     const auto It =
         InvertedIndex.find(Token(Token::Kind::ProximityURI, ParentURI));
     if (It != InvertedIndex.end()) {
       // FIXME(kbobyrev): Append LIMIT on top of every BOOST iterator.
       PathProximitySignals.SymbolURI = ParentURI;
       BoostingIterators.push_back(
-          createBoost(create(It->second), PathProximitySignals.evaluate()));
+          createBoost(It->second->iterator(), PathProximitySignals.evaluate()));
     }
   }
   return BoostingIterators;
 }
 
 } // namespace
 
 void Dex::buildIndex() {
void Dex::buildIndex() {
   // SymbolQuality was empty up until now.
   SymbolQuality.resize(Symbols.size());
   // Populate internal storage using Symbol + Score pairs.
   for (size_t I = 0; I < ScoredSymbols.size(); ++I) {
     SymbolQuality[I] = ScoredSymbols[I].first;
     Symbols[I] = ScoredSymbols[I].second;
   }
 
-  // Populate TempInvertedIndex with posting lists for index symbols.
+  // Populate TempInvertedIndex with lists for index symbols.
+  llvm::DenseMap<Token, std::vector<DocID>> TempInvertedIndex;
   for (DocID SymbolRank = 0; SymbolRank < Symbols.size(); ++SymbolRank) {
     const auto *Sym = Symbols[SymbolRank];
     for (const auto &Token : generateSearchTokens(*Sym))
-      InvertedIndex[Token].push_back(SymbolRank);
+      TempInvertedIndex[Token].push_back(SymbolRank);
   }
 
+  // Convert lists of items to posting lists.
+  for (const auto &TokenToPostingList : TempInvertedIndex)
+    InvertedIndex.insert(
+        {TokenToPostingList.first,
+         buildSparsePostingList(move(TokenToPostingList.second))});
+
   vlog("Built Dex with estimated memory usage {0} bytes.",
        estimateMemoryUsage());
 }
 
 /// Constructs iterators over tokens extracted from the query and exhausts it
 /// while applying Callback to each symbol in the order of decreasing quality
 /// of the matched symbols.
 bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
                     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
 
   std::vector<std::unique_ptr<Iterator>> TopLevelChildren;
   const auto TrigramTokens = generateIdentifierTrigrams(Req.Query);
 
   // Generate query trigrams and construct AND iterator over all query
   // trigrams.
   std::vector<std::unique_ptr<Iterator>> TrigramIterators;
   for (const auto &Trigram : TrigramTokens) {
     const auto It = InvertedIndex.find(Trigram);
     if (It != InvertedIndex.end())
-      TrigramIterators.push_back(create(It->second));
+      TrigramIterators.push_back(It->second->iterator());
   }
   if (!TrigramIterators.empty())
     TopLevelChildren.push_back(createAnd(move(TrigramIterators)));
 
   // Generate scope tokens for search query.
   std::vector<std::unique_ptr<Iterator>> ScopeIterators;
   for (const auto &Scope : Req.Scopes) {
     const auto It = InvertedIndex.find(Token(Token::Kind::Scope, Scope));
     if (It != InvertedIndex.end())
-      ScopeIterators.push_back(create(It->second));
+      ScopeIterators.push_back(It->second->iterator());
   }
   // Add OR iterator for scopes if there are any Scope Iterators.
   if (!ScopeIterators.empty())
     TopLevelChildren.push_back(createOr(move(ScopeIterators)));
 
   // Add proximity paths boosting.
   auto BoostingIterators = createFileProximityIterators(
       Req.ProximityPaths, URISchemes, InvertedIndex);

 }
 
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
   Bytes += LookupTable.getMemorySize();
   Bytes += InvertedIndex.getMemorySize();
   for (const auto &P : InvertedIndex)
-    Bytes += P.second.size() * sizeof(DocID);
+    Bytes += P.second->bytes();
   return Bytes + BackingDataSize;
 }
 
 std::vector<std::string> generateProximityURIs(llvm::StringRef URIPath) {
   std::vector<std::string> Result;
   auto ParsedURI = URI::parse(URIPath);
   assert(ParsedURI &&
          "Non-empty argument of generateProximityURIs() should be a valid "

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

 #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>
+#include "PostingList.h"
 
 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.
-// FIXME(kbobyrev): Posting lists for incomplete trigrams (one/two symbols) are
-// likely to be very dense and hence require special attention so that the index
-// doesn't use too much memory. Possible solution would be to construct
-// compressed posting lists which consist of ranges of DocIDs instead of
-// distinct DocIDs. A special case would be the empty query: for that case
-// TrueIterator should be implemented - an iterator which doesn't actually store
-// any PostingList within itself, but "contains" all DocIDs in range
-// [0, IndexSize).
-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): Implement iterator cost, an estimate of advance() calls

 ///
 /// Boosting can be seen as a compromise between retrieving too many items and
 /// calculating finals score for each of them (which might be very expensive)
 /// and not retrieving enough items so that items with very high final score
 /// would not be processed. Boosting score is a computationally efficient way
 /// to acquire preliminary scores of requested items.
 std::vector<std::pair<DocID, float>> consume(Iterator &It);
 
-/// Returns a document iterator over given PostingList.
-///
-/// DocumentIterator returns DEFAULT_BOOST_SCORE for each processed item.
-std::unique_ptr<Iterator> create(PostingListRef Documents);
-
 /// Returns AND Iterator which performs the intersection of the PostingLists of
 /// its children.
 ///
 /// consume(): AND Iterator returns the product of Childrens' boosting scores
 /// when not exhausted and DEFAULT_BOOST_SCORE otherwise.
 std::unique_ptr<Iterator>
 createAnd(std::vector<std::unique_ptr<Iterator>> Children);
 

clang-tools-extra/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 "PostingList.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:
-  explicit 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() && "DOCUMENT iterator 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() && "DOCUMENT iterator can't advance() at the end.");
-    // If current ID is beyond requested one, iterator is already in the right
-    // state.
-    if (peek() < ID)
-      Index = std::lower_bound(Index, std::end(Documents), ID);
-  }
-
-  DocID peek() const override {
-    assert(!reachedEnd() && "DOCUMENT iterator can't peek() at the end.");
-    return *Index;
-  }
-
-  float consume() override {
-    assert(!reachedEnd() && "DOCUMENT iterator can't consume() at the end.");
-    return DEFAULT_BOOST_SCORE;
-  }
-
-  size_t estimateSize() const override { return Documents.size(); }
-
-private:
-  llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
-    OS << '[';
-    auto Separator = "";
-    for (auto It = std::begin(Documents); It != std::end(Documents); ++It) {
-      OS << Separator;
-      if (It == Index)
-        OS << '{' << *It << '}';
-      else
-        OS << *It;
-      Separator = ", ";
-    }
-    OS << Separator;
-    if (Index == std::end(Documents))
-      OS << "{END}";
-    else
-      OS << "END";
-    OS << ']';
-    return OS;
-  }
-
-  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:
   explicit AndIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)

 
 std::vector<std::pair<DocID, float>> consume(Iterator &It) {
   std::vector<std::pair<DocID, float>> Result;
   for (; !It.reachedEnd(); It.advance())
     Result.emplace_back(It.peek(), It.consume());
   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));

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

+//===--- PostingList.h - Symbol identifiers storage interface  --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines posting list interface: a storage for identifiers of symbols
+// which can be characterized by a specific feature (such as fuzzy-find trigram,
+// scope, type or any other Search Token). Posting lists are values for
+// inverted index, which maps search tokens to corresponding posting lists.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include <cstdint>
+#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;
+
+class Iterator;
+
+/// PostingList is an interface for the storage of DocIDs which can be inserted
+/// to the Query Tree as a leaf by constructing Iterator over given PostingList.
+/// Depending on posting list density, users can decide to utilize more
+/// efficient representations to balance the space vs. performance trade-off.
+/// For example, dense posting lists might benefit from various compression
+/// techniques, but require decompression and thus are the cause of performance
+/// overhead.
+// FIXME(kbobyrev): Implement dense posting list implementation using VByte
+// encoding.
+class PostingList {
+public:
+  /// Returns Query Tree leaf iterator over given PostingList.
+  virtual std::unique_ptr<Iterator> iterator() const = 0;
+
+  /// Returns size of underlying storage.
+  virtual size_t bytes() const = 0;
+
+  virtual ~PostingList() {}
+};
+
+/// Returns posting list with sparse in-memory representation. This is useful
+/// for small size posting lists with huge gaps between subsequent DocIDs.
+/// Sparse posting list stores an array of DocIDs and requires
+/// List.size() * sizeof(DocID) memory. It does not induce performance overhead
+/// for data (de)compression, but can consume a lot of memory when given large
+/// dense posting list.
+std::unique_ptr<PostingList>
+buildSparsePostingList(const std::vector<DocID> &&Documents);
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H

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

+//===--- PostingList.cpp - Symbol identifiers storage interface -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "PostingList.h"
+#include "Iterator.h"
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+namespace {
+
+/// SparsePostingList owns underlying data represented as std::vector<DocID>.
+/// It is effective where gaps between subsequent DocIDs are expected to take
+/// the whole sizeof(DocID) filled with significant bits, because it doesn't
+/// compress underlying data.
+class SparsePostingList : public PostingList {
+public:
+  explicit SparsePostingList(const std::vector<DocID> &&Documents)
+      : Documents(std::move(Documents)) {}
+
+  virtual std::unique_ptr<Iterator> iterator() const override {
+    return llvm::make_unique<SparseIterator>(move(Documents));
+  }
+
+  virtual size_t bytes() const override {
+    return Documents.size() * sizeof(DocID);
+  }
+
+private:
+  /// Implements Iterator over SparsePostingList. This is the most basic
+  /// iterator and is simply a wrapper around
+  /// std::vector<DocID>::const_iterator.
+  class SparseIterator : public Iterator {
+  public:
+    explicit SparseIterator(llvm::ArrayRef<DocID> 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() &&
+             "Sparse Posting List iterator 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() &&
+             "Sparse Posting List iterator can't advance() at the end.");
+      // If current ID is beyond requested one, iterator is already in the right
+      // state.
+      if (peek() < ID)
+        Index = std::lower_bound(Index, std::end(Documents), ID);
+    }
+
+    DocID peek() const override {
+      assert(!reachedEnd() &&
+             "Sparse Posting List iterator can't peek() at the end.");
+      return *Index;
+    }
+
+    float consume() override {
+      assert(!reachedEnd() &&
+             "Sparse Posting List iterator can't consume() at the end.");
+      return DEFAULT_BOOST_SCORE;
+    }
+
+    size_t estimateSize() const override { return Documents.size(); }
+
+  private:
+    llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+      OS << '[';
+      if (Index != std::end(Documents))
+        OS << *Index;
+      else
+        OS << "END";
+      OS << ']';
+      return OS;
+    }
+
+    llvm::ArrayRef<DocID> Documents;
+    llvm::ArrayRef<DocID>::const_iterator Index;
+  };
+
+  const std::vector<DocID> Documents;
+};
+
+} // namespace
+
+std::unique_ptr<PostingList>
+buildSparsePostingList(const std::vector<DocID> &&Documents) {
+  return llvm::make_unique<SparsePostingList>(move(Documents));
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang

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

std::vector<DocID> consumeIDs(Iterator &It) {
   auto IDAndScore = consume(It);
   std::vector<DocID> IDs(IDAndScore.size());
   for (size_t I = 0; I < IDAndScore.size(); ++I)
     IDs[I] = IDAndScore[I].first;
   return IDs;
 }
 
 TEST(DexIterators, DocumentIterator) {
-  const PostingList L = {4, 7, 8, 20, 42, 100};
-  auto DocIterator = create(L);
+  const auto L = buildSparsePostingList({4, 7, 8, 20, 42, 100});
+  auto DocIterator = L->iterator();
 
   EXPECT_EQ(DocIterator->peek(), 4U);
   EXPECT_FALSE(DocIterator->reachedEnd());
 
   DocIterator->advance();
   EXPECT_EQ(DocIterator->peek(), 7U);
   EXPECT_FALSE(DocIterator->reachedEnd());
 
   DocIterator->advanceTo(20);
   EXPECT_EQ(DocIterator->peek(), 20U);
   EXPECT_FALSE(DocIterator->reachedEnd());
 
   DocIterator->advanceTo(65);
   EXPECT_EQ(DocIterator->peek(), 100U);
   EXPECT_FALSE(DocIterator->reachedEnd());
 
   DocIterator->advanceTo(420);
   EXPECT_TRUE(DocIterator->reachedEnd());
 }
 
 TEST(DexIterators, AndWithEmpty) {
-  const PostingList L0;
-  const PostingList L1 = {0, 5, 7, 10, 42, 320, 9000};
+  const auto L0 = buildSparsePostingList({});
+  const auto L1 = buildSparsePostingList({0, 5, 7, 10, 42, 320, 9000});
 
-  auto AndEmpty = createAnd(create(L0));
+  auto AndEmpty = createAnd(L0->iterator());
   EXPECT_TRUE(AndEmpty->reachedEnd());
 
-  auto AndWithEmpty = createAnd(create(L0), create(L1));
+  auto AndWithEmpty = createAnd(L0->iterator(), L1->iterator());
   EXPECT_TRUE(AndWithEmpty->reachedEnd());
 
   EXPECT_THAT(consumeIDs(*AndWithEmpty), ElementsAre());
 }
 
 TEST(DexIterators, AndTwoLists) {
-  const PostingList L0 = {0, 5, 7, 10, 42, 320, 9000};
-  const PostingList L1 = {0, 4, 7, 10, 30, 60, 320, 9000};
+  const auto L0 = buildSparsePostingList({0, 5, 7, 10, 42, 320, 9000});
+  const auto L1 = buildSparsePostingList({0, 4, 7, 10, 30, 60, 320, 9000});
 
-  auto And = createAnd(create(L1), create(L0));
+  auto And = createAnd(L1->iterator(), L0->iterator());
 
   EXPECT_FALSE(And->reachedEnd());
   EXPECT_THAT(consumeIDs(*And), ElementsAre(0U, 7U, 10U, 320U, 9000U));
 
-  And = createAnd(create(L0), create(L1));
+  And = createAnd(L0->iterator(), L1->iterator());
 
   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(DexIterators, 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};
+  const auto L0 = buildSparsePostingList({0, 5, 7, 10, 42, 320, 9000});
+  const auto L1 = buildSparsePostingList({0, 4, 7, 10, 30, 60, 320, 9000});
+  const auto L2 = buildSparsePostingList({1, 4, 7, 11, 30, 60, 320, 9000});
 
-  auto And = createAnd(create(L0), create(L1), create(L2));
+  auto And = createAnd(L0->iterator(), L1->iterator(), L2->iterator());
   EXPECT_EQ(And->peek(), 7U);
   And->advanceTo(300);
   EXPECT_EQ(And->peek(), 320U);
   And->advanceTo(100000);
 
   EXPECT_TRUE(And->reachedEnd());
 }
 
 TEST(DexIterators, OrWithEmpty) {
-  const PostingList L0;
-  const PostingList L1 = {0, 5, 7, 10, 42, 320, 9000};
+  const auto L0 = buildSparsePostingList({});
+  const auto L1 = buildSparsePostingList({0, 5, 7, 10, 42, 320, 9000});
 
-  auto OrEmpty = createOr(create(L0));
+  auto OrEmpty = createOr(L0->iterator());
   EXPECT_TRUE(OrEmpty->reachedEnd());
 
-  auto OrWithEmpty = createOr(create(L0), create(L1));
+  auto OrWithEmpty = createOr(L0->iterator(), L1->iterator());
   EXPECT_FALSE(OrWithEmpty->reachedEnd());
 
   EXPECT_THAT(consumeIDs(*OrWithEmpty),
               ElementsAre(0U, 5U, 7U, 10U, 42U, 320U, 9000U));
 }
 
 TEST(DexIterators, OrTwoLists) {
-  const PostingList L0 = {0, 5, 7, 10, 42, 320, 9000};
-  const PostingList L1 = {0, 4, 7, 10, 30, 60, 320, 9000};
+  const auto L0 = buildSparsePostingList({0, 5, 7, 10, 42, 320, 9000});
+  const auto L1 = buildSparsePostingList({0, 4, 7, 10, 30, 60, 320, 9000});
 
-  auto Or = createOr(create(L0), create(L1));
+  auto Or = createOr(L0->iterator(), L1->iterator());
 
   EXPECT_FALSE(Or->reachedEnd());
   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_TRUE(Or->reachedEnd());
 
-  Or = createOr(create(L0), create(L1));
+  Or = createOr(L0->iterator(), L1->iterator());
 
   EXPECT_THAT(consumeIDs(*Or),
               ElementsAre(0U, 4U, 5U, 7U, 10U, 30U, 42U, 60U, 320U, 9000U));
 }
 
 TEST(DexIterators, 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};
+  const auto L0 = buildSparsePostingList({0, 5, 7, 10, 42, 320, 9000});
+  const auto L1 = buildSparsePostingList({0, 4, 7, 10, 30, 60, 320, 9000});
+  const auto L2 = buildSparsePostingList({1, 4, 7, 11, 30, 60, 320, 9000});
 
-  auto Or = createOr(create(L0), create(L1), create(L2));
+  auto Or = createOr(L0->iterator(), L1->iterator(), L2->iterator());
 
   EXPECT_FALSE(Or->reachedEnd());
   EXPECT_EQ(Or->peek(), 0U);
 
   Or->advance();
   EXPECT_EQ(Or->peek(), 1U);
 
   Or->advance();
TEST(DexIterators, QueryTree) {
   //  +-------v-----+ +----+---+             +--v--+  +---v----+ +----v---+
   //  |1, 3, 5, 8, 9| |Boost: 2|             |Empty|  |Boost: 3| |Boost: 4|
   //  +-------------+ +----+---+             +-----+  +---+----+ +----+---+
   //                       |                              |           |
   //                  +----v-----+                      +-v--+    +---v---+
   //                  |1, 5, 7, 9|                      |1, 5|    |0, 3, 5|
   //                  +----------+                      +----+    +-------+
   //
-  const PostingList L0 = {1, 3, 5, 8, 9};
-  const PostingList L1 = {1, 5, 7, 9};
-  const PostingList L3;
-  const PostingList L4 = {1, 5};
-  const PostingList L5 = {0, 3, 5};
+  const auto L0 = buildSparsePostingList({1, 3, 5, 8, 9});
+  const auto L1 = buildSparsePostingList({1, 5, 7, 9});
+  const auto L3 = buildSparsePostingList({});
+  const auto L4 = buildSparsePostingList({1, 5});
+  const auto L5 = buildSparsePostingList({0, 3, 5});
 
   // Root of the query tree: [1, 5]
   auto Root = createAnd(
       // Lower And Iterator: [1, 5, 9]
-      createAnd(create(L0), createBoost(create(L1), 2U)),
+      createAnd(L0->iterator(), createBoost(L1->iterator(), 2U)),
       // Lower Or Iterator: [0, 1, 5]
-      createOr(create(L3), createBoost(create(L4), 3U),
-               createBoost(create(L5), 4U)));
+      createOr(L3->iterator(), createBoost(L4->iterator(), 3U),
+               createBoost(L5->iterator(), 4U)));
 
   EXPECT_FALSE(Root->reachedEnd());
   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);
   auto ElementBoost = Root->consume();
   EXPECT_THAT(ElementBoost, 6);
   Root->advance();
   EXPECT_EQ(Root->peek(), 5U);
   Root->advanceTo(5);
   EXPECT_EQ(Root->peek(), 5U);
   ElementBoost = Root->consume();
   EXPECT_THAT(ElementBoost, 8);
   Root->advanceTo(9000);
   EXPECT_TRUE(Root->reachedEnd());
 }
 
 TEST(DexIterators, StringRepresentation) {
-  const PostingList L0 = {4, 7, 8, 20, 42, 100};
-  const PostingList L1 = {1, 3, 5, 8, 9};
-  const PostingList L2 = {1, 5, 7, 9};
-  const PostingList L3 = {0, 5};
-  const PostingList L4 = {0, 1, 5};
-  const PostingList L5;
-
-  EXPECT_EQ(llvm::to_string(*(create(L0))), "[{4}, 7, 8, 20, 42, 100, END]");
-
-  auto Nested = createAnd(createAnd(create(L1), create(L2)),
-                          createOr(create(L3), create(L4), create(L5)));
-
-  EXPECT_EQ(llvm::to_string(*Nested),
-            "(& (| [0, {5}, END] [0, {1}, 5, END] [{END}]) (& [{1}, 5, 7, 9, "
-            "END] [{1}, 3, 5, 8, 9, END]))");
+  const auto L0 = buildSparsePostingList({4, 7, 8, 20, 42, 100});
+  const auto L1 = buildSparsePostingList({1, 3, 5, 8, 9});
+  const auto L2 = buildSparsePostingList({1, 5, 7, 9});
+  const auto L3 = buildSparsePostingList({0, 5});
+  const auto L4 = buildSparsePostingList({0, 1, 5});
+  const auto L5 = buildSparsePostingList({});
+
+  EXPECT_EQ(llvm::to_string(*(L0->iterator())), "[4]");
+
+  auto Nested =
+      createAnd(createAnd(L1->iterator(), L2->iterator()),
+                createOr(L3->iterator(), L4->iterator(), L5->iterator()));
+
+  EXPECT_EQ(llvm::to_string(*Nested), "(& (| [5] [1] [END]) (& [1] [1]))");
 }
 
 TEST(DexIterators, Limit) {
-  const PostingList L0 = {3, 6, 7, 20, 42, 100};
-  const PostingList L1 = {1, 3, 5, 6, 7, 30, 100};
-  const PostingList L2 = {0, 3, 5, 7, 8, 100};
+  const auto L0 = buildSparsePostingList({3, 6, 7, 20, 42, 100});
+  const auto L1 = buildSparsePostingList({1, 3, 5, 6, 7, 30, 100});
+  const auto L2 = buildSparsePostingList({0, 3, 5, 7, 8, 100});
 
-  auto DocIterator = createLimit(create(L0), 42);
+  auto DocIterator = createLimit(L0->iterator(), 42);
   EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre(3, 6, 7, 20, 42, 100));
 
-  DocIterator = createLimit(create(L0), 3);
+  DocIterator = createLimit(L0->iterator(), 3);
   EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre(3, 6, 7));
 
-  DocIterator = createLimit(create(L0), 0);
+  DocIterator = createLimit(L0->iterator(), 0);
   EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre());
 
-  auto AndIterator =
-      createAnd(createLimit(createTrue(9000), 343), createLimit(create(L0), 2),
-                createLimit(create(L1), 3), createLimit(create(L2), 42));
+  auto AndIterator = createAnd(
+      createLimit(createTrue(9000), 343), createLimit(L0->iterator(), 2),
+      createLimit(L1->iterator(), 3), createLimit(L2->iterator(), 42));
   EXPECT_THAT(consumeIDs(*AndIterator), ElementsAre(3, 7));
 }
 
 TEST(DexIterators, True) {
   auto TrueIterator = createTrue(0U);
   EXPECT_TRUE(TrueIterator->reachedEnd());
   EXPECT_THAT(consumeIDs(*TrueIterator), ElementsAre());
 
-  PostingList L0 = {1, 2, 5, 7};
+  const auto L0 = buildSparsePostingList({1, 2, 5, 7});
   TrueIterator = createTrue(7U);
   EXPECT_THAT(TrueIterator->peek(), 0);
-  auto AndIterator = createAnd(create(L0), move(TrueIterator));
+  auto AndIterator = createAnd(L0->iterator(), move(TrueIterator));
   EXPECT_FALSE(AndIterator->reachedEnd());
   EXPECT_THAT(consumeIDs(*AndIterator), ElementsAre(1, 2, 5));
 }
 
 TEST(DexIterators, Boost) {
   auto BoostIterator = createBoost(createTrue(5U), 42U);
   EXPECT_FALSE(BoostIterator->reachedEnd());
   auto ElementBoost = BoostIterator->consume();
   EXPECT_THAT(ElementBoost, 42U);
 
-  const PostingList L0 = {2, 4};
-  const PostingList L1 = {1, 4};
-  auto Root = createOr(createTrue(5U), createBoost(create(L0), 2U),
-                       createBoost(create(L1), 3U));
+  const auto L0 = buildSparsePostingList({2, 4});
+  const auto L1 = buildSparsePostingList({1, 4});
+  auto Root = createOr(createTrue(5U), createBoost(L0->iterator(), 2U),
+                       createBoost(L1->iterator(), 3U));
 
   ElementBoost = Root->consume();
   EXPECT_THAT(ElementBoost, Iterator::DEFAULT_BOOST_SCORE);
   Root->advance();
   EXPECT_THAT(Root->peek(), 1U);
   ElementBoost = Root->consume();
   EXPECT_THAT(ElementBoost, 3);
 
TEST(Dex, Lookup) {
   EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
               UnorderedElementsAre("ns::abc", "ns::xyz"));
   EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}),
               UnorderedElementsAre("ns::xyz"));
   EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre());
 }
 
 TEST(Dex, FuzzyFind) {
-  auto Index = Dex::build(
-      generateSymbols({"ns::ABC", "ns::BCD", "::ABC", "ns::nested::ABC",
-                       "other::ABC", "other::A"}),
+  auto Index =
+      Dex::build(generateSymbols({"ns::ABC", "ns::BCD", "::ABC",
+                                  "ns::nested::ABC", "other::ABC", "other::A"}),
                  URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "ABC";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("ns::ABC"));
   Req.Scopes = {"ns::", "ns::nested::"};
   EXPECT_THAT(match(*Index, Req),
               UnorderedElementsAre("ns::ABC", "ns::nested::ABC"));
   Req.Query = "A";
TEST(DexTest, FuzzyMatch) {
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.MaxCandidateCount = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 TEST(DexTest, MatchQualifiedNamesWithoutSpecificScope) {
-  auto I =
-      Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), URISchemes);
+  auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "y";
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
 }
 
 TEST(DexTest, MatchQualifiedNamesWithGlobalScope) {
-  auto I =
-      Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), URISchemes);
+  auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3"));
 }
 
 TEST(DexTest, MatchQualifiedNamesWithOneScope) {
   auto I = Dex::build(