nridge updated this revision to Diff 200735.
nridge added a comment.
Herald added a subscriber: mgrang.
Implemented discussed design approach ("Add a RelationSlab storing (subject,
predicate, object) triples, intended for sparse relations")
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D59407/new/
https://reviews.llvm.org/D59407
Files:
clang-tools-extra/clangd/CMakeLists.txt
clang-tools-extra/clangd/index/Index.h
clang-tools-extra/clangd/index/Relation.cpp
clang-tools-extra/clangd/index/Relation.h
clang-tools-extra/clangd/unittests/IndexTests.cpp
Index: clang-tools-extra/clangd/unittests/IndexTests.cpp
===================================================================
--- clang-tools-extra/clangd/unittests/IndexTests.cpp
+++ clang-tools-extra/clangd/unittests/IndexTests.cpp
@@ -76,6 +76,29 @@
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.push_back(Relation{A, index::SymbolRole::RelationBaseOf, B});
+ Builder.push_back(Relation{A, index::SymbolRole::RelationBaseOf, C});
+ Builder.push_back(Relation{B, index::SymbolRole::RelationBaseOf, D});
+ Builder.push_back(Relation{C, index::SymbolRole::RelationBaseOf, D});
+ Builder.push_back(Relation{B, index::SymbolRole::RelationChildOf, A});
+ Builder.push_back(Relation{C, index::SymbolRole::RelationChildOf, A});
+ Builder.push_back(Relation{D, index::SymbolRole::RelationChildOf, B});
+ Builder.push_back(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(SwapIndexTest, OldIndexRecycled) {
auto Token = std::make_shared<int>();
std::weak_ptr<int> WeakToken = Token;
Index: clang-tools-extra/clangd/index/Relation.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/Relation.h
@@ -0,0 +1,98 @@
+//===--- 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 Subject == Other.Subject && Predicate == Other.Predicate &&
+ Object == Other.Object;
+ }
+ // SPO order
+ bool operator<(const Relation &Other) const {
+ if (Subject < Other.Subject) {
+ return true;
+ }
+ if (Subject == Other.Subject) {
+ if (Predicate < Other.Predicate) {
+ return true;
+ }
+
+ if (Predicate == Other.Predicate) {
+ return Object < Other.Object;
+ }
+ }
+ return false;
+ }
+};
+
+class RelationSlab {
+public:
+ using value_type = Relation;
+ using const_iterator = std::vector<value_type>::const_iterator;
+ using iterator = const_iterator;
+
+ // We don't need a separate builder type for this, but reserve
+ // that possibility for the future. Having a build() method is
+ // also useful so when know when to sort the relations.
+ using Builder = RelationSlab;
+
+ 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(); }
+
+ void push_back(const Relation &R) { Relations.push_back(R); }
+
+ size_t bytes() const {
+ return sizeof(*this) + sizeof(value_type) * Relations.capacity();
+ }
+
+ /// Sort relations in SPO order.
+ void sort();
+
+ /// Lookup all relations matching the given subject and predicate.
+ /// Assumes the slab is sorted in SPO order.
+ llvm::iterator_range<iterator> lookup(const SymbolID &Subject,
+ index::SymbolRole Predicate) const;
+
+ RelationSlab build() &&;
+
+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
Index: clang-tools-extra/clangd/index/Relation.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/index/Relation.cpp
@@ -0,0 +1,37 @@
+//===--- 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 {
+
+void RelationSlab::sort() { std::sort(Relations.begin(), Relations.end()); }
+
+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 (A.Subject < B.Subject) ||
+ (A.Subject == B.Subject &&
+ A.Predicate < B.Predicate);
+ });
+ return {IterPair.first, IterPair.second};
+}
+
+RelationSlab RelationSlab::build() && {
+ sort();
+ return std::move(*this);
+}
+
+} // namespace clangd
+} // namespace clang
Index: clang-tools-extra/clangd/index/Index.h
===================================================================
--- clang-tools-extra/clangd/index/Index.h
+++ clang-tools-extra/clangd/index/Index.h
@@ -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"
Index: clang-tools-extra/clangd/CMakeLists.txt
===================================================================
--- clang-tools-extra/clangd/CMakeLists.txt
+++ clang-tools-extra/clangd/CMakeLists.txt
@@ -77,6 +77,7 @@
index/MemIndex.cpp
index/Merge.cpp
index/Ref.cpp
+ index/Relation.cpp
index/Serialization.cpp
index/Symbol.cpp
index/SymbolCollector.cpp
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
