kbobyrev updated this revision to Diff 157004.
kbobyrev added a comment.
Refactored unit tests in few places.
https://reviews.llvm.org/D49546
Files:
clang-tools-extra/clangd/CMakeLists.txt
clang-tools-extra/clangd/index/dex/Iterator.cpp
clang-tools-extra/clangd/index/dex/Iterator.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,201 @@
+//===--- DexIndexTests.cpp ----------------------------*- C++ -*-----------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "index/dex/Iterator.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <string>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+using ::testing::ElementsAre;
+
+TEST(DexIndexIterators, DocumentIterator) {
+ auto DocIterator = Iterator::create({4, 7, 8, 20, 42, 100});
+
+ EXPECT_EQ(DocIterator->peek(), 4U);
+ EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+ DocIterator->advance();
+ EXPECT_EQ(DocIterator->peek(), 7U);
+ EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+ DocIterator->advanceTo(20);
+ EXPECT_EQ(DocIterator->peek(), 20U);
+ EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+ DocIterator->advanceTo(65);
+ EXPECT_EQ(DocIterator->peek(), 100U);
+ EXPECT_EQ(DocIterator->reachedEnd(), false);
+
+ DocIterator->advanceTo(420);
+ EXPECT_EQ(DocIterator->reachedEnd(), true);
+
+ EXPECT_EQ(llvm::to_string(*DocIterator), "[4, 7, 8, 20, 42, 100]");
+}
+
+TEST(DexIndexIterators, AndIterator) {
+ const PostingList EmptyList;
+ const PostingList FirstList = {0, 5, 7, 10, 42, 320, 9000};
+ const PostingList SecondList = {0, 4, 7, 10, 30, 60, 320, 9000};
+ const PostingList ThirdList = {1, 4, 7, 11, 30, 60, 320, 9000};
+
+ auto And = Iterator::createAnd({Iterator::create(EmptyList)});
+
+ EXPECT_EQ(llvm::to_string(*And), "(& [])");
+
+ And = Iterator::createAnd(
+ {Iterator::create(EmptyList), Iterator::create(FirstList)});
+
+ EXPECT_EQ(llvm::to_string(*And), "(& [] [0, 5, 7, 10, 42, 320, 9000])");
+
+ And = Iterator::createAnd(
+ {Iterator::create(FirstList), Iterator::create(SecondList)});
+
+ EXPECT_EQ(And->reachedEnd(), false);
+ EXPECT_THAT(Iterator::consume(*And), ElementsAre(0U, 7U, 10U, 320U, 9000U));
+
+ EXPECT_EQ(
+ llvm::to_string(*And),
+ "(& [0, 5, 7, 10, 42, 320, 9000] [0, 4, 7, 10, 30, 60, 320, 9000])");
+
+ And = Iterator::createAnd(
+ {Iterator::create(SecondList), Iterator::create(FirstList)});
+
+ And->advanceTo(0);
+ EXPECT_EQ(And->peek(), 0U);
+ And->advanceTo(5);
+ EXPECT_EQ(And->peek(), 7U);
+ And->advanceTo(10);
+ EXPECT_EQ(And->peek(), 10U);
+ And->advanceTo(42);
+ EXPECT_EQ(And->peek(), 320U);
+ And->advanceTo(8999);
+ EXPECT_EQ(And->peek(), 9000U);
+ And->advanceTo(9001);
+
+ And = Iterator::createAnd({Iterator::create(FirstList),
+ Iterator::create(SecondList),
+ Iterator::create(ThirdList)});
+ EXPECT_EQ(And->peek(), 7U);
+ And->advanceTo(300);
+ EXPECT_EQ(And->peek(), 320U);
+ And->advanceTo(100000);
+
+ EXPECT_EQ(And->reachedEnd(), true);
+}
+
+TEST(DexIndexIterators, OrIterator) {
+ const PostingList EmptyList;
+ const PostingList FirstList = {0, 5, 7, 10, 42, 320, 9000};
+ const PostingList SecondList = {0, 4, 7, 10, 30, 60, 320, 9000};
+ const PostingList ThirdList = {1, 4, 7, 11, 30, 60, 320, 9000};
+
+ auto Or = Iterator::createOr({Iterator::create(EmptyList)});
+
+ EXPECT_EQ(Or->reachedEnd(), true);
+
+ Or = Iterator::createOr(
+ {Iterator::create(FirstList), Iterator::create(EmptyList)});
+
+ EXPECT_EQ(Or->reachedEnd(), false);
+ EXPECT_EQ(Or->peek(), 0U);
+ Or->advance();
+ EXPECT_EQ(Or->peek(), 5U);
+ Or->advance();
+ EXPECT_EQ(Or->peek(), 7U);
+ Or->advance();
+ EXPECT_EQ(Or->peek(), 10U);
+ Or->advance();
+ EXPECT_EQ(Or->peek(), 42U);
+ Or->advanceTo(42);
+ EXPECT_EQ(Or->peek(), 42U);
+ Or->advanceTo(300);
+ EXPECT_EQ(Or->peek(), 320U);
+ Or->advanceTo(9000);
+ EXPECT_EQ(Or->peek(), 9000U);
+ Or->advanceTo(9001);
+
+ Or = Iterator::createOr({Iterator::create(FirstList),
+ Iterator::create(SecondList),
+ Iterator::create(ThirdList)});
+
+ EXPECT_EQ(Or->reachedEnd(), false);
+ EXPECT_EQ(Or->peek(), 0U);
+
+ Or->advance();
+ EXPECT_EQ(Or->peek(), 1U);
+
+ Or->advance();
+ EXPECT_EQ(Or->peek(), 4U);
+
+ Or->advanceTo(7);
+
+ Or->advanceTo(59);
+ EXPECT_EQ(Or->peek(), 60U);
+
+ Or->advanceTo(9001);
+}
+
+// FIXME(kbobyrev): The testcase below is similar to what is expected in real
+// queries. It should be updated once new iterators (such as boosting, limiting,
+// etc iterators) appear. However, it is not exhaustive and it would be
+// beneficial to implement automatic generation of query trees for more
+// comprehensive testing.
+TEST(DexIndexIterators, QueryTree) {
+ // An example of more complicated query
+ //
+ // +-----------------+
+ // |And Iterator:1, 5|
+ // +--------+--------+
+ // |
+ // |
+ // +------------------------------------+
+ // | |
+ // | |
+ // +----------v----------+ +----------v---------+
+ // |And Iterator: 1, 5, 9| |Or Iterator: 0, 1, 5|
+ // +----------+----------+ +----------+---------+
+ // | |
+ // +------+-----+ +---------+-----------+
+ // | | | | |
+ // +-------v-----+ +----v-----+ +--v--+ +-V--+ +---v---+
+ // |0, 3, 5, 8, 9| |0, 5, 7, 9| |Empty| |0, 5| |0, 1, 5|
+ // +-------------+ +----------+ +-----+ +----+ +-------+
+
+ // Root of the query tree: [1, 5]
+ auto Root = Iterator::createAnd({
+ // Lower And Iterator: [1, 5, 9]
+ Iterator::createAnd(
+ {Iterator::create({1, 3, 5, 8, 9}), Iterator::create({1, 5, 7, 9})}),
+ // Lower Or Iterator: [0, 1, 5]
+ Iterator::createOr({Iterator::create({0, 5}), Iterator::create({0, 1, 5}),
+ Iterator::create({})}),
+ });
+
+ EXPECT_EQ(Root->reachedEnd(), false);
+ EXPECT_EQ(Root->peek(), 1U);
+ Root->advanceTo(0);
+ // Advance multiple times. Shouldn't do anything.
+ Root->advanceTo(1);
+ Root->advanceTo(0);
+ EXPECT_EQ(Root->peek(), 1U);
+ Root->advance();
+ EXPECT_EQ(Root->peek(), 5U);
+ Root->advanceTo(5);
+ Root->advanceTo(9000);
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
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/Iterator.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/dex/Iterator.h
@@ -0,0 +1,87 @@
+//===--- Iterator.h - Query Symbol Retrieval --------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// FIXME(kbobyrev): Write a short summary
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H
+
+#include <algorithm>
+#include <memory>
+#include <vector>
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+using DocID = uint32_t;
+using PostingList = std::vector<DocID>;
+using PostingListRef = llvm::ArrayRef<DocID>;
+
+// FIXME(kbobyrev): Provide callback for matched documents.
+// FIXME(kbobyrev): Implement new types of iterators: Label, Boost, Limit.
+// FIXME(kbobyrev): Document this one properly.
+class Iterator {
+public:
+ virtual bool reachedEnd() const = 0;
+ virtual void advance() = 0;
+ virtual void advanceTo(DocID Rank) = 0;
+ /// Returns item under the cursor.
+ virtual DocID peek() const = 0;
+
+ virtual ~Iterator() {}
+
+ friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const Iterator &Iterator) {
+ return Iterator.dump(OS);
+ }
+
+ static std::vector<DocID> consume(Iterator &It);
+
+ // FIXME(kbobyrev): Brief documentation of DocumentIterator here.
+ static std::unique_ptr<Iterator> create(PostingListRef Documents);
+
+ // FIXME(kbobyrev): Brief documentation of AndIterator here.
+ template <size_t Size>
+ static std::unique_ptr<Iterator>
+ createAnd(std::unique_ptr<Iterator>(&&Children)[Size]) {
+ std::vector<std::unique_ptr<Iterator>> Elements;
+ std::move(begin(Children), end(Children), std::back_inserter(Elements));
+ return createAnd(move(Elements));
+ }
+
+ static std::unique_ptr<Iterator>
+ createAnd(std::vector<std::unique_ptr<Iterator>> Children);
+
+ // FIXME(kbobyrev): Brief documentation of OrIterator here.
+ template <size_t Size>
+ static std::unique_ptr<Iterator>
+ createOr(std::unique_ptr<Iterator>(&&Children)[Size]) {
+ std::vector<std::unique_ptr<Iterator>> Elements;
+ std::move(begin(Children), end(Children), std::back_inserter(Elements));
+ return createOr(move(Elements));
+ }
+
+ static std::unique_ptr<Iterator>
+ createOr(std::vector<std::unique_ptr<Iterator>> Children);
+
+private:
+ virtual llvm::raw_ostream &dump(llvm::raw_ostream &OS) const = 0;
+};
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+#endif
Index: clang-tools-extra/clangd/index/dex/Iterator.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/dex/Iterator.cpp
@@ -0,0 +1,258 @@
+//===--- Iterator.cpp - Query Symbol Retrieval ------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Iterator.h"
+
+#include <algorithm>
+#include <cassert>
+#include <numeric>
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+/// Implements Iterator over a PostingList.
+// FIXME(kbobyrev): Document this one properly.
+class DocumentIterator : public Iterator {
+public:
+ DocumentIterator(PostingListRef Documents) : Documents(Documents), Index(0) {}
+
+ bool reachedEnd() const override { return Index == Documents.size(); }
+
+ /// Increments Index.
+ void advance() override {
+ assert(!reachedEnd() && "DocumentIterator can't advance at the end.");
+ ++Index;
+ }
+
+ // FIXME(kbobyrev): Properly document this one.
+ void advanceTo(DocID ID) override {
+ assert(!reachedEnd() && "DocumentIterator can't advance at the end.");
+ Index = std::lower_bound(Documents.begin() + Index, Documents.end(), ID) -
+ Documents.begin();
+ }
+
+ DocID peek() const override {
+ assert(!reachedEnd() && "DocumentIterator can't call peek() at the end.");
+ return Documents[Index];
+ }
+
+ llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+ OS << '[';
+ for (size_t Index = 0; Index < Documents.size(); ++Index) {
+ OS << Documents[Index];
+ if (Index + 1 != Documents.size())
+ OS << ", ";
+ }
+ OS << ']';
+ return OS;
+ }
+
+private:
+ PostingListRef Documents;
+ DocID Index;
+};
+
+// FIXME(kbobyrev): Document this one properly.
+class AndIterator : public Iterator {
+public:
+ AndIterator(std::vector<std::unique_ptr<Iterator>> &&AllChildren)
+ : Children(std::move(AllChildren)), ReachedEnd(false) {
+ assert(!Children.empty() && "AndIterator should have at least one child.");
+ DocID ID = 0;
+ for (auto &Child : Children) {
+ // Check whether any child iterator points to the end. In this case,
+ // advance() would be invalid.
+ if (Child->reachedEnd()) {
+ ReachedEnd = true;
+ break;
+ }
+ // Choose highest ID among valid children.
+ ID = std::max(ID, Child->peek());
+ }
+ // Make sure all children point to the same document, otherwise peek() is
+ // invalid.
+ if (!ReachedEnd)
+ advanceTo(ID);
+ }
+
+ bool reachedEnd() const override { return ReachedEnd; }
+
+ // FIXME(kbobyrev): Properly document this one.
+ void advance() override {
+ assert(!reachedEnd() && "AndIterator can't call advance() at the end.");
+ Children.front()->advance();
+ ReachedEnd = Children.front()->reachedEnd();
+ DocID HighestID = 0;
+ if (!ReachedEnd)
+ HighestID = Children.front()->peek();
+ bool ChangedID = true;
+ while (ChangedID && !ReachedEnd) {
+ ChangedID = false;
+ for (auto &Child : Children) {
+ Child->advanceTo(HighestID);
+ ReachedEnd = Child->reachedEnd();
+ if (ReachedEnd)
+ break;
+ if (Child->peek() > HighestID) {
+ HighestID = Child->peek();
+ ChangedID = true;
+ }
+ }
+ }
+ }
+
+ // FIXME(kbobyrev): Properly document this one.
+ void advanceTo(DocID ID) override {
+ assert(!reachedEnd() && "AndIterator can't call advanceTo() at the end.");
+ bool NeedsAdvance = false;
+ for (auto &Child : Children) {
+ Child->advanceTo(ID);
+ ReachedEnd = Child->reachedEnd();
+ // If any child reaches end And iterator can not match any other items. In
+ // this case, just terminate the process.
+ if (ReachedEnd)
+ break;
+ // If any child goes beyond given ID (i.e. ID is not the common item),
+ // all children should be advanced to the next common item.
+ if (Child->peek() > ID) {
+ ID = Child->peek();
+ NeedsAdvance = true;
+ }
+ }
+ // Advance all children to the next common item.
+ if (!ReachedEnd && NeedsAdvance)
+ advanceTo(ID);
+ }
+
+ DocID peek() const override { return Children.front()->peek(); }
+
+ llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+ OS << "(& ";
+ for (size_t Index = 0; Index < Children.size(); ++Index) {
+ OS << *Children[Index];
+ if (Index + 1 != Children.size())
+ OS << ' ';
+ }
+ OS << ')';
+ return OS;
+ }
+
+private:
+ std::vector<std::unique_ptr<Iterator>> Children;
+ // Store and update local state, otherwise each reachedEnd() call would
+ // require the whole subtree traversal.
+ bool ReachedEnd;
+};
+
+// FIXME(kbobyrev): Document this one properly.
+// FIXME(kbobyrev): Currently, the implementation is inefficient because peek()
+// and reachedEnd() are computed in O(Children.size()). This can be fixed by
+// maintaining heap in Children - both peek() and reachedEnd() will become O(1),
+// the only overhead will be that advance() will have to pop each child after
+// calling Child->advance() and push it back to the heap to maintain the
+// structure. The additional complexity of advance() will be at most
+// 2 * N * log(N), where N = Children.size(). Also, the heap will be initialized
+// in constructor, which will yield at most 3 * N additional atomic operations.
+class OrIterator : public Iterator {
+public:
+ OrIterator(std::vector<std::unique_ptr<Iterator>> &&AllChildren)
+ : Children(std::move(AllChildren)) {
+ assert(Children.size() > 0 && "Or Iterator must have at least one child.");
+ }
+
+ bool reachedEnd() const override {
+ for (auto &Child : Children)
+ if (!Child->reachedEnd())
+ return false;
+ return true;
+ }
+
+ void advance() override {
+ assert(!reachedEnd() &&
+ "OrIterator must have at least one child to advance().");
+ const auto HighestID = peek();
+ DocID ChildrenToAdvance = 0;
+ while ((ChildrenToAdvance++ < Children.size()) && !reachedEnd() &&
+ (peek() == HighestID)) {
+ for (auto &Child : Children) {
+ if (!Child->reachedEnd() && Child->peek() == HighestID) {
+ Child->advance();
+ }
+ }
+ }
+ }
+
+ void advanceTo(DocID ID) override {
+ assert(!reachedEnd() && "Can't advance iterator after it reached the end.");
+ for (auto &Child : Children) {
+ if (!Child->reachedEnd()) {
+ Child->advanceTo(ID);
+ }
+ }
+ }
+
+ DocID peek() const override {
+ assert(!reachedEnd() &&
+ "OrIterator must have at least one child to peek().");
+ bool FoundFirstValid = false;
+ DocID Result = 0;
+ for (auto &Child : Children) {
+ if (!Child->reachedEnd()) {
+ if (!FoundFirstValid) {
+ Result = Child->peek();
+ FoundFirstValid = true;
+ continue;
+ }
+ Result = std::min(Result, Child->peek());
+ }
+ }
+ return Result;
+ }
+
+ llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
+ OS << "(| ";
+ for (size_t Index = 0; Index < Children.size(); ++Index) {
+ OS << *Children[Index];
+ if (Index + 1 != Children.size())
+ OS << ' ';
+ }
+ return OS;
+ }
+
+private:
+ std::vector<std::unique_ptr<Iterator>> Children;
+};
+
+std::vector<DocID> Iterator::consume(Iterator &It) {
+ std::vector<DocID> Result;
+ while (!It.reachedEnd()) {
+ Result.push_back(It.peek());
+ It.advance();
+ }
+ return Result;
+}
+
+std::unique_ptr<Iterator> Iterator::create(PostingListRef Documents) {
+ return llvm::make_unique<DocumentIterator>(Documents);
+}
+
+std::unique_ptr<Iterator>
+Iterator::createAnd(std::vector<std::unique_ptr<Iterator>> Children) {
+ return llvm::make_unique<AndIterator>(move(Children));
+}
+
+std::unique_ptr<Iterator>
+Iterator::createOr(std::vector<std::unique_ptr<Iterator>> Children) {
+ return llvm::make_unique<OrIterator>(move(Children));
+}
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
Index: clang-tools-extra/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/Iterator.cpp
+
LINK_LIBS
clangAST
clangASTMatchers
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
