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,120 @@ +//===--- QueryIterator.h- FIXME(kbobyrev): summary --------------*- 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 +#include +#include +#include + +namespace clang { +namespace clangd { +namespace dex { + +using PostingList = std::vector; + +// 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. +class QueryIterator { +public: + virtual bool reachedEnd() const = 0; + // FIXME(kbobyrev): Should advance() and advanceTo() return size_t peek() + // instead? + virtual bool advance() = 0; + virtual bool advanceTo(size_t Rank) = 0; + virtual size_t peek() const = 0; + + virtual ~QueryIterator() {} +}; + +/// Implements QueryIterator over a PostingList. +// FIXME(kbobyrev): Document this one properly. +class DocumentIterator : public QueryIterator { +public: + DocumentIterator(std::shared_ptr Documents); + + bool reachedEnd() const override; + /// Increments Index. + bool advance() override; + bool advanceTo(size_t Rank) override; + size_t getIndex() const; + size_t peek() const override; + + /// + void reset(); + +private: + // FIXME(kbobyrev): Document iterator doesn't really "own" the underlying + // posting list, it "borrows" it from the inverted index. Is std::shared_ptr + // fine here? + std::shared_ptr Documents; + size_t Index; +}; + +// FIXME(kbobyrev): Document this one properly. +class AndIterator : public QueryIterator { +public: + AndIterator(const std::vector> &Children); + + bool reachedEnd() const override; + bool advance() override; + bool advanceTo(size_t Rank) override; + size_t peek() const override; + + const std::vector> getChildren() const; + +private: + // FIXME(kbobyrev): Should I use std::unique_ptr here since higher level + // iterators "own" their children in some sense? + std::vector> Children; + // Store and update local variable, otherwise each reachedEnd() call would + // require the whole subtree traversal. + bool ReachedEnd; +}; + +// FIXME(kbobyrev): Document this one properly. +class OrIterator : public QueryIterator { +public: + OrIterator(const std::vector> &AllChildren); + + bool reachedEnd() const override; + bool advance() override; + bool advanceTo(size_t Rank) override; + size_t peek() const override; + + const std::vector> getChildren() const; + +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> 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,189 @@ +//===--- QueryIterator.cpp- FIXME(kbobyrev): summary ------------*- 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 +#include + +namespace clang { +namespace clangd { +namespace dex { + +DocumentIterator::DocumentIterator(std::shared_ptr Documents) + : Documents(Documents), Index(0) {} + +bool DocumentIterator::reachedEnd() const { + return Documents == nullptr || Index == Documents->size(); +} + +bool DocumentIterator::advance() { + assert(!reachedEnd() && "DocumentIterator can't advance at the end."); + ++Index; + return reachedEnd(); +} + +// FIXME(kbobyrev): Properly document this one. +bool DocumentIterator::advanceTo(size_t Rank) { + assert(!reachedEnd() && "DocumentIterator can't advance at the end."); + Index = std::lower_bound(Documents->begin() + Index, Documents->end(), Rank) - + Documents->begin(); + return reachedEnd(); +} + +size_t DocumentIterator::getIndex() const { return Index; } + +size_t DocumentIterator::peek() const { + assert(!reachedEnd() && "DocumentIterator can't call peek() at the end."); + return (*Documents)[Index]; +} + +void DocumentIterator::reset() { Index = 0; } + +// FIXME(kbobyrev): Properly document this one. +AndIterator::AndIterator( + const std::vector> &Children) + : Children(Children), ReachedEnd(false) { + assert(!Children.empty() && "AndIterator should have at least one child."); + size_t Rank = 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 Lowest Rank among valid children. + Rank = std::max(Rank, Child->peek()); + } + // Make sure all children point to the same document, otherwise peek() is + // invalid. + if (!ReachedEnd) + advanceTo(Rank); +} + +bool AndIterator::reachedEnd() const { return ReachedEnd; } + +// FIXME(kbobyrev): Properly document this one. +bool AndIterator::advance() { + assert(!reachedEnd() && "AndIterator can't call advance() at the end."); + // FIXME(kbobyrev): Should the Children be sorted by increasing Rank + // beforehand? + ReachedEnd = Children.front()->advance(); + size_t LowestRank = 0; + if (!ReachedEnd) + LowestRank = Children.front()->peek(); + bool ChangedRank = true; + while (ChangedRank && !ReachedEnd) { + ChangedRank = false; + for (auto Child : Children) { + ReachedEnd = Child->advanceTo(LowestRank); + if (ReachedEnd) + break; + if (Child->peek() > LowestRank) { + LowestRank = Child->peek(); + ChangedRank = true; + } + } + } + return reachedEnd(); +} + +// FIXME(kbobyrev): Properly document this one. +bool AndIterator::advanceTo(size_t Rank) { + assert(!reachedEnd() && "AndIterator can't call advanceTo() at the end."); + bool NeedsAdvance = false; + for (auto Child : Children) { + ReachedEnd = Child->advanceTo(Rank); + // 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 Rank (i.e. Rank is not the common item), + // all children should be advanced to the next common item. + if (Child->peek() > Rank) { + Rank = Child->peek(); + NeedsAdvance = true; + } + } + // Advance all children to the next common item. + if (!ReachedEnd && NeedsAdvance) + advanceTo(Rank); + return reachedEnd(); +} + +size_t AndIterator::peek() const { return Children.front()->peek(); } + +const std::vector> +AndIterator::getChildren() const { + return Children; +} + +namespace { +auto CompareIterators = [](std::shared_ptr Left, + std::shared_ptr Right) -> bool { + if (Right->reachedEnd()) + return false; + if (Left->reachedEnd()) + return true; + return Left->peek() > Right->peek(); +}; +} // namespace + +OrIterator::OrIterator( + const std::vector> &AllChildren) + : Children(AllChildren) { + assert(AllChildren.size() > 0 && "Or Iterator must have at least one child."); + std::make_heap(begin(Children), end(Children), CompareIterators); +} + +bool OrIterator::reachedEnd() const { return Children.front()->reachedEnd(); } + +bool OrIterator::advance() { + assert(!reachedEnd() && + "OrIterator must have at least one child to advance()."); + const auto HighestRank = peek(); + size_t ChildrenToAdvance = 0; + while ((ChildrenToAdvance++ < Children.size()) && + !Children.front()->reachedEnd() && + (Children.front()->peek() == HighestRank)) { + Children.front()->advance(); + std::pop_heap(begin(Children), end(Children), CompareIterators); + std::push_heap(begin(Children), end(Children), CompareIterators); + } + // FIXME(kbobyrev): This is suboptimal. + std::make_heap(begin(Children), end(Children), CompareIterators); + return reachedEnd(); +} + +bool OrIterator::advanceTo(size_t Rank) { + assert(!reachedEnd() && + "OrIterator must have at least one child to advanceTo()."); + for (auto Child : Children) { + if (!Child->reachedEnd()) { + Child->advanceTo(Rank); + } + } + std::make_heap(begin(Children), end(Children), CompareIterators); + return reachedEnd(); +} + +size_t OrIterator::peek() const { + assert(!reachedEnd() && "OrIterator must have at least one child to peek()."); + return Children.front()->peek(); +} + +const std::vector> +OrIterator::getChildren() const { + return 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,440 @@ +//===-- 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 "gtest/gtest.h" + +namespace clang { +namespace clangd { +namespace dex { + +using std::make_shared; +using std::shared_ptr; +using std::vector; + +TEST(DexIndexIterators, DocumentIterator) { + const auto Symbols = + make_shared(PostingList({4, 7, 8, 20, 42, 100})); + DocumentIterator Iterator(Symbols); + + EXPECT_EQ(Iterator.getIndex(), 0U); + EXPECT_EQ(Iterator.peek(), 4U); + EXPECT_EQ(Iterator.reachedEnd(), false); + + EXPECT_EQ(Iterator.advance(), false); + EXPECT_EQ(Iterator.getIndex(), 1U); + EXPECT_EQ(Iterator.peek(), 7U); + EXPECT_EQ(Iterator.reachedEnd(), false); + + EXPECT_EQ(Iterator.advanceTo(20), false); + EXPECT_EQ(Iterator.peek(), 20U); + EXPECT_EQ(Iterator.getIndex(), 3U); + EXPECT_EQ(Iterator.reachedEnd(), false); + + EXPECT_EQ(Iterator.advanceTo(65), false); + EXPECT_EQ(Iterator.peek(), 100U); + EXPECT_EQ(Iterator.getIndex(), 5U); + EXPECT_EQ(Iterator.reachedEnd(), false); + + EXPECT_EQ(Iterator.advanceTo(420), true); + EXPECT_EQ(Iterator.getIndex(), 6U); + EXPECT_EQ(Iterator.reachedEnd(), true); +} + +TEST(DexIndexIterators, AndIterator) { + const auto EmptyList = make_shared(PostingList()); + const auto FirstList = + make_shared(PostingList({0, 5, 7, 10, 42, 320, 9000})); + const auto SecondList = + make_shared(PostingList({0, 4, 7, 10, 30, 60, 320, 9000})); + const auto ThirdList = + make_shared(PostingList({1, 4, 7, 11, 30, 60, 320, 9000})); + const auto FourthList = + make_shared(PostingList({4, 7, 10, 30, 60, 320, 9000})); + const auto FifthList = make_shared( + PostingList({1, 4, 7, 10, 30, 60, 320, 9000, 1000000})); + + vector> Children = { + make_shared(EmptyList)}; + AndIterator And(Children); + + EXPECT_EQ(And.reachedEnd(), true); + + Children = {make_shared(EmptyList), + make_shared(FirstList)}; + And = AndIterator(Children); + + EXPECT_EQ(And.reachedEnd(), true); + + Children = {make_shared(FirstList), + make_shared(SecondList)}; + And = AndIterator(Children); + + EXPECT_EQ(And.reachedEnd(), false); + EXPECT_EQ(And.peek(), 0U); + + for (auto Child : And.getChildren()) + EXPECT_EQ(Child->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); + + Children = {make_shared(FirstList), + make_shared(SecondList)}; + And = AndIterator(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 = {make_shared(FirstList), + make_shared(SecondList)}; + And = AndIterator(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. + // + vector> BottomLevelChildren = { + make_shared(FourthList), + make_shared(FifthList)}; + auto BottomLevelIterator = make_shared(BottomLevelChildren); + + EXPECT_EQ(BottomLevelIterator->reachedEnd(), false); + EXPECT_EQ(BottomLevelIterator->peek(), 4U); + + vector> TopLevelChildren = { + make_shared(FirstList), + make_shared(SecondList), + make_shared(ThirdList), BottomLevelIterator}; + AndIterator TopLevelIterator(TopLevelChildren); + + 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); +} + +TEST(DexIndexIterators, OrIterator) { + const auto EmptyList = make_shared(PostingList()); + const auto FirstList = + make_shared(PostingList({0, 5, 7, 10, 42, 320, 9000})); + const auto SecondList = + make_shared(PostingList({0, 4, 7, 10, 30, 60, 320, 9000})); + const auto ThirdList = + make_shared(PostingList({1, 4, 7, 11, 30, 60, 320, 9000})); + const auto FourthList = + make_shared(PostingList({4, 7, 10, 30, 60, 320, 9000})); + const auto FifthList = make_shared( + PostingList({1, 4, 7, 10, 30, 60, 320, 9000, 1000000})); + + vector> Children = { + make_shared(EmptyList)}; + OrIterator Or(Children); + + EXPECT_EQ(Or.reachedEnd(), true); + + Children = {make_shared(EmptyList), + make_shared(FirstList)}; + Or = OrIterator(Children); + + EXPECT_EQ(Or.reachedEnd(), false); + EXPECT_EQ(Or.peek(), 0U); + + EXPECT_EQ(Or.getChildren().front()->reachedEnd(), false); + EXPECT_EQ(Or.getChildren().back()->reachedEnd(), true); + EXPECT_EQ(Or.getChildren().front()->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 = {make_shared(FirstList), + make_shared(SecondList), + make_shared(ThirdList)}; + Or = OrIterator(Children); + + EXPECT_EQ(Or.reachedEnd(), false); + EXPECT_EQ(Or.peek(), 0U); + + EXPECT_EQ(Or.advance(), false); + EXPECT_EQ(Or.peek(), 1U); + EXPECT_EQ(Or.getChildren().front()->peek(), 1U); + + EXPECT_EQ(Or.advance(), false); + EXPECT_EQ(Or.peek(), 4U); + + EXPECT_EQ(Or.advanceTo(7), false); + for (auto Child : Or.getChildren()) + EXPECT_EQ(Child->peek(), 7U); + + 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. + vector> BottomLevelChildren = { + make_shared(FourthList), + make_shared(FifthList)}; + auto BottomLevelIterator = make_shared(BottomLevelChildren); + + EXPECT_EQ(BottomLevelIterator->reachedEnd(), false); + EXPECT_EQ(BottomLevelIterator->peek(), 1U); + + vector> TopLevelChildren = { + make_shared(FirstList), + make_shared(SecondList), + make_shared(ThirdList), BottomLevelIterator}; + OrIterator TopLevelIterator(TopLevelChildren); + + 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-+ + // |...| |...| |...| |...| |...| |...| |...| + // +---+ +---+ +---+ +---+ +---+ +---+ +---+ + // + + auto FirstList = make_shared(PostingList({1, 3, 5, 8, 9})); + auto SecondList = make_shared(PostingList({1, 5, 7, 9})); + vector> Children = { + make_shared(FirstList), + make_shared(SecondList), + }; + + // First Level And Iterator: [1, 5, 9] + auto LeftSubtreeAnd = make_shared(Children); + + FirstList = + make_shared(PostingList({0, 1, 2, 5, 6, 7, 8, 9, 10, 42})); + SecondList = make_shared(PostingList({0, 1, 2, 5, 6, 7, 8, 9})); + auto ThirdList = + make_shared(PostingList({1, 4, 5, 7, 8, 9, 50, 300, 9000})); + + Children = { + make_shared(FirstList), + make_shared(SecondList), + make_shared(ThirdList), + }; + + // Bottom Level Left And Iterator: [1, 5, 7, 8, 9] + auto BottomLevelLeftAnd = make_shared(Children); + + FirstList = make_shared(PostingList({0, 4, 5})); + SecondList = make_shared(PostingList({0, 1, 10})); + ThirdList = make_shared(PostingList({42})); + auto FourthList = make_shared(PostingList({4, 8})); + auto EmptyList = make_shared(PostingList({})); + + Children = { + make_shared(EmptyList), + make_shared(FirstList), + make_shared(SecondList), + make_shared(ThirdList), + make_shared(FourthList), + }; + + // Bottom Level Right Or Iterator: [0, 1, 4, 5, 8, 10, 42] + auto BottomLevelRightOr = make_shared(Children); + + Children = { + BottomLevelLeftAnd, + BottomLevelRightOr, + }; + // First Level Middle And Iterator: [1, 5, 8] + auto MiddleSubtreeAnd = make_shared(Children); + + FirstList = make_shared(PostingList({0, 1, 6})); + SecondList = make_shared(PostingList({0, 1})); + ThirdList = make_shared(PostingList({0, 1, 5, 60})); + + Children = { + make_shared(FirstList), + make_shared(SecondList), + make_shared(ThirdList), + }; + // And Iterator in rightmost subtree, child of first level Or Iterator: [0, 1] + auto RightSubtreeAndIterator = make_shared(Children); + + FirstList = make_shared(PostingList({0, 5})); + SecondList = make_shared(PostingList({0, 1, 5})); + + Children = { + RightSubtreeAndIterator, + make_shared(FirstList), + make_shared(SecondList), + make_shared(EmptyList), + }; + // Rightmost first level Or iterator, child of the root iterator: [0, 1, 5] + auto RightSubtreeOrIterator = make_shared(Children); + + Children = { + LeftSubtreeAnd, + MiddleSubtreeAnd, + RightSubtreeOrIterator, + }; + // Root of the query tree: [1, 5] + AndIterator Root(Children); + + 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