kbobyrev updated this revision to Diff 156725.
kbobyrev added a comment.
Herald added a subscriber: mgrang.
- Implemented convenient dumping via `llvm::raw_ostream
&operator<<(llvm::raw_ostream &OS, QueryIterator &Iterator)`, which dumps
iterator tree in human-readable format, e.g. `(&& [1, 2, 3] (|| [3, 4, 5] []))`
- Implemented rather straightforward iterator `cost` for more efficient
`AndIterator` iterations
The functional part is probably done at this point, the only thing to do at
this point is to properly document written code leaving only few `FIXME`s for
the future.
https://reviews.llvm.org/D49546
Files:
clang-tools-extra/clangd/CMakeLists.txt
clang-tools-extra/clangd/index/dex/QueryIterator.cpp
clang-tools-extra/clangd/index/dex/QueryIterator.h
clang-tools-extra/unittests/clangd/CMakeLists.txt
clang-tools-extra/unittests/clangd/DexIndexTests.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
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/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/clangd/CMakeLists.txt
===================================================================
--- clang-tools-extra/clangd/CMakeLists.txt
+++ clang-tools-extra/clangd/CMakeLists.txt
@@ -34,14 +34,17 @@
TUScheduler.cpp
URI.cpp
XRefs.cpp
+
index/CanonicalIncludes.cpp
index/FileIndex.cpp
index/Index.cpp
index/MemIndex.cpp
index/Merge.cpp
index/SymbolCollector.cpp
index/SymbolYAML.cpp
+ index/dex/QueryIterator.cpp
+
LINK_LIBS
clangAST
clangASTMatchers
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
