Author: nridge Date: Sun Jun 2 21:55:46 2019 New Revision: 362352 URL: http://llvm.org/viewvc/llvm-project?rev=362352&view=rev Log: [clangd] Add RelationSlab
Summary: RelationSlab is a new index data structure that stores relations between symbols. Reviewers: kadircet Subscribers: ilya-biryukov, ioeric, MaskRay, jkorous, arphaman, cfe-commits Tags: #clang Differential Revision: https://reviews.llvm.org/D59407 Added: clang-tools-extra/trunk/clangd/index/Relation.cpp clang-tools-extra/trunk/clangd/index/Relation.h Modified: clang-tools-extra/trunk/clangd/CMakeLists.txt clang-tools-extra/trunk/clangd/index/Index.h clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp Modified: clang-tools-extra/trunk/clangd/CMakeLists.txt URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/CMakeLists.txt?rev=362352&r1=362351&r2=362352&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/CMakeLists.txt (original) +++ clang-tools-extra/trunk/clangd/CMakeLists.txt Sun Jun 2 21:55:46 2019 @@ -77,6 +77,7 @@ add_clang_library(clangDaemon index/MemIndex.cpp index/Merge.cpp index/Ref.cpp + index/Relation.cpp index/Serialization.cpp index/Symbol.cpp index/SymbolCollector.cpp Modified: clang-tools-extra/trunk/clangd/index/Index.h URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/index/Index.h?rev=362352&r1=362351&r2=362352&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/index/Index.h (original) +++ clang-tools-extra/trunk/clangd/index/Index.h Sun Jun 2 21:55:46 2019 @@ -10,6 +10,7 @@ #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H #include "Ref.h" +#include "Relation.h" #include "Symbol.h" #include "SymbolID.h" #include "llvm/ADT/DenseSet.h" Added: clang-tools-extra/trunk/clangd/index/Relation.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/index/Relation.cpp?rev=362352&view=auto ============================================================================== --- clang-tools-extra/trunk/clangd/index/Relation.cpp (added) +++ clang-tools-extra/trunk/clangd/index/Relation.cpp Sun Jun 2 21:55:46 2019 @@ -0,0 +1,40 @@ +//===--- Relation.cpp --------------------------------------------*- C++-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Relation.h" + +#include <algorithm> + +namespace clang { +namespace clangd { + +llvm::iterator_range<RelationSlab::iterator> +RelationSlab::lookup(const SymbolID &Subject, + index::SymbolRole Predicate) const { + auto IterPair = std::equal_range(Relations.begin(), Relations.end(), + Relation{Subject, Predicate, SymbolID{}}, + [](const Relation &A, const Relation &B) { + return std::tie(A.Subject, A.Predicate) < + std::tie(B.Subject, B.Predicate); + }); + return {IterPair.first, IterPair.second}; +} + +RelationSlab RelationSlab::Builder::build() && { + // Sort in SPO order. + std::sort(Relations.begin(), Relations.end()); + + // Remove duplicates. + Relations.erase(std::unique(Relations.begin(), Relations.end()), + Relations.end()); + + return RelationSlab{std::move(Relations)}; +} + +} // namespace clangd +} // namespace clang Added: clang-tools-extra/trunk/clangd/index/Relation.h URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/index/Relation.h?rev=362352&view=auto ============================================================================== --- clang-tools-extra/trunk/clangd/index/Relation.h (added) +++ clang-tools-extra/trunk/clangd/index/Relation.h Sun Jun 2 21:55:46 2019 @@ -0,0 +1,88 @@ +//===--- Relation.h ----------------------------------------------*- C++-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H + +#include "SymbolID.h" +#include "SymbolLocation.h" +#include "clang/Index/IndexSymbol.h" +#include "llvm/ADT/iterator_range.h" +#include <cstdint> +#include <utility> + +namespace clang { +namespace clangd { + +/// Represents a relation between two symbols. +/// For an example "A is a base class of B" may be represented +/// as { Subject = A, Predicate = RelationBaseOf, Object = B }. +struct Relation { + SymbolID Subject; + index::SymbolRole Predicate; + SymbolID Object; + + bool operator==(const Relation &Other) const { + return std::tie(Subject, Predicate, Object) == + std::tie(Other.Subject, Other.Predicate, Other.Object); + } + // SPO order + bool operator<(const Relation &Other) const { + return std::tie(Subject, Predicate, Object) < + std::tie(Other.Subject, Other.Predicate, Other.Object); + } +}; + +class RelationSlab { +public: + using value_type = Relation; + using const_iterator = std::vector<value_type>::const_iterator; + using iterator = const_iterator; + + RelationSlab() = default; + RelationSlab(RelationSlab &&Slab) = default; + RelationSlab &operator=(RelationSlab &&RHS) = default; + + const_iterator begin() const { return Relations.begin(); } + const_iterator end() const { return Relations.end(); } + size_t size() const { return Relations.size(); } + bool empty() const { return Relations.empty(); } + + size_t bytes() const { + return sizeof(*this) + sizeof(value_type) * Relations.capacity(); + } + + /// Lookup all relations matching the given subject and predicate. + llvm::iterator_range<iterator> lookup(const SymbolID &Subject, + index::SymbolRole Predicate) const; + + /// RelationSlab::Builder is a mutable container that can 'freeze' to + /// RelationSlab. + class Builder { + public: + /// Adds a relation to the slab. + void insert(const Relation &R) { Relations.push_back(R); } + + /// Consumes the builder to finalize the slab. + RelationSlab build() &&; + + private: + std::vector<Relation> Relations; + }; + +private: + RelationSlab(std::vector<Relation> Relations) + : Relations(std::move(Relations)) {} + + std::vector<Relation> Relations; +}; + +} // namespace clangd +} // namespace clang + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H Modified: clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp?rev=362352&r1=362351&r2=362352&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp (original) +++ clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp Sun Jun 2 21:55:46 2019 @@ -76,6 +76,45 @@ TEST(SymbolSlab, FindAndIterate) { EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym)); } +TEST(RelationSlab, Lookup) { + SymbolID A{"A"}; + SymbolID B{"B"}; + SymbolID C{"C"}; + SymbolID D{"D"}; + + RelationSlab::Builder Builder; + Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, B}); + Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, C}); + Builder.insert(Relation{B, index::SymbolRole::RelationBaseOf, D}); + Builder.insert(Relation{C, index::SymbolRole::RelationBaseOf, D}); + Builder.insert(Relation{B, index::SymbolRole::RelationChildOf, A}); + Builder.insert(Relation{C, index::SymbolRole::RelationChildOf, A}); + Builder.insert(Relation{D, index::SymbolRole::RelationChildOf, B}); + Builder.insert(Relation{D, index::SymbolRole::RelationChildOf, C}); + + RelationSlab Slab = std::move(Builder).build(); + EXPECT_THAT( + Slab.lookup(A, index::SymbolRole::RelationBaseOf), + UnorderedElementsAre(Relation{A, index::SymbolRole::RelationBaseOf, B}, + Relation{A, index::SymbolRole::RelationBaseOf, C})); +} + +TEST(RelationSlab, Duplicates) { + SymbolID A{"A"}; + SymbolID B{"B"}; + SymbolID C{"C"}; + + RelationSlab::Builder Builder; + Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, B}); + Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, C}); + Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, B}); + + RelationSlab Slab = std::move(Builder).build(); + EXPECT_THAT(Slab, UnorderedElementsAre( + Relation{A, index::SymbolRole::RelationBaseOf, B}, + Relation{A, index::SymbolRole::RelationBaseOf, C})); +} + TEST(SwapIndexTest, OldIndexRecycled) { auto Token = std::make_shared<int>(); std::weak_ptr<int> WeakToken = Token; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
