[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rL362352: [clangd] Add RelationSlab (authored by nridge, 
committed by ).
Herald added a project: LLVM.
Herald added a subscriber: llvm-commits.

Changed prior to commit:
  https://reviews.llvm.org/D59407?vs=202369=202643#toc

Repository:
  rL LLVM

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407

Files:
  clang-tools-extra/trunk/clangd/CMakeLists.txt
  clang-tools-extra/trunk/clangd/index/Index.h
  clang-tools-extra/trunk/clangd/index/Relation.cpp
  clang-tools-extra/trunk/clangd/index/Relation.h
  clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp

Index: clang-tools-extra/trunk/clangd/index/Relation.cpp
===
--- clang-tools-extra/trunk/clangd/index/Relation.cpp
+++ clang-tools-extra/trunk/clangd/index/Relation.cpp
@@ -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 
+
+namespace clang {
+namespace clangd {
+
+llvm::iterator_range
+RelationSlab::lookup(const SymbolID ,
+ index::SymbolRole Predicate) const {
+  auto IterPair = std::equal_range(Relations.begin(), Relations.end(),
+   Relation{Subject, Predicate, SymbolID{}},
+   [](const Relation , const Relation ) {
+ 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
Index: clang-tools-extra/trunk/clangd/index/Relation.h
===
--- clang-tools-extra/trunk/clangd/index/Relation.h
+++ clang-tools-extra/trunk/clangd/index/Relation.h
@@ -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 
+#include 
+
+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 ) const {
+return std::tie(Subject, Predicate, Object) ==
+   std::tie(Other.Subject, Other.Predicate, Other.Object);
+  }
+  // SPO order
+  bool operator<(const Relation ) 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::const_iterator;
+  using iterator = const_iterator;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &) = default;
+  RelationSlab =(RelationSlab &) = 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 lookup(const SymbolID ,
+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 ) { Relations.push_back(R); }
+
+/// Consumes the builder to finalize the slab.
+ 

[PATCH] D59407: [clangd] Add RelationSlab

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet accepted this revision.
kadircet added a comment.

Still LG, thanks for the patch!


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge updated this revision to Diff 202369.
nridge added a comment.

Address latest review comments


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,45 @@
 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();
   std::weak_ptr WeakToken = Token;
Index: clang-tools-extra/clangd/index/Relation.h
===
--- /dev/null
+++ clang-tools-extra/clangd/index/Relation.h
@@ -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 
+#include 
+
+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 ) const {
+return std::tie(Subject, Predicate, Object) ==
+   std::tie(Other.Subject, Other.Predicate, Other.Object);
+  }
+  // SPO order
+  bool operator<(const Relation ) 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::const_iterator;
+  using iterator = const_iterator;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &) = default;
+  RelationSlab =(RelationSlab &) = 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 lookup(const SymbolID ,
+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 

[PATCH] D59407: [clangd] Add RelationSlab

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet added a comment.

btw, I believe you have enough good quality patches to apply for commit access.

Are there any obstacles that is keeping you from applying?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Sam McCall via Phabricator via cfe-commits]

sammccall accepted this revision.
sammccall added a comment.

Awesome, thank you!




Comment at: clang-tools-extra/clangd/index/Relation.h:75
+  private:
+std::vector Relations;
+  };

kadircet wrote:
> maybe use a set so that we can be sure that there won't be any duplicates. 
> sorry for missing that in the previous iteration.
(you're sorting the array at the end anyway, so sort + unique + erase seems 
neater)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet accepted this revision.
kadircet added a comment.
This revision is now accepted and ready to land.

LGTM, except the duplication issue. Thanks!




Comment at: clang-tools-extra/clangd/index/Relation.h:75
+  private:
+std::vector Relations;
+  };

maybe use a set so that we can be sure that there won't be any duplicates. 
sorry for missing that in the previous iteration.



Comment at: clang-tools-extra/clangd/unittests/IndexTests.cpp:79
 
+TEST(RelationSlab, Lookup) {
+  SymbolID A{"A"};

could you also add a test case that's inserting duplicate relations?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge added inline comments.



Comment at: clang-tools-extra/clangd/index/Relation.cpp:19
+llvm::iterator_range
+RelationSlab::lookup(const SymbolID ,
+ index::SymbolRole Predicate) const {

kadircet wrote:
> I would suggest adding another version which returns all the relations a 
> given `Subject` participates, but I suppose currently we don't have any use 
> cases.
> 
> Feel free to add or skip, that can be added when necessary.
I'd rather add this when a use case arises.



Comment at: clang-tools-extra/clangd/index/Relation.h:52
+
+class RelationSlab {
+public:

kadircet wrote:
> I believe `RelationSlab` should still be immutable, even after the `build` 
> operation below `RelationSlab` is mutable.
> Let's introduce the builder class and move mutating operations and build into 
> it. So that it would be more symmetric to other slabs we have.
> 
> Also are there any use-cases requiring RelationSlab to be mutable?
I'm not aware of any use-cases requiring it to be mutable. I'm making it 
immutable as suggested.



Comment at: clang-tools-extra/clangd/index/Relation.h:89
+private:
+  RelationSlab(std::vector Relations)
+  : Relations(std::move(Relations)) {}

kadircet wrote:
> Do we really need this?
I think so. The builder needs a way to construct the slab. Aggregate 
initialization doesn't work because the class already has declared default and 
copy constructors.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge updated this revision to Diff 201427.
nridge marked 19 inline comments as done.
nridge added a comment.

Address review comments


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.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(SwapIndexTest, OldIndexRecycled) {
   auto Token = std::make_shared();
   std::weak_ptr WeakToken = Token;
Index: clang-tools-extra/clangd/index/Relation.h
===
--- /dev/null
+++ clang-tools-extra/clangd/index/Relation.h
@@ -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 
+#include 
+
+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 ) const {
+return std::tie(Subject, Predicate, Object) ==
+   std::tie(Other.Subject, Other.Predicate, Other.Object);
+  }
+  // SPO order
+  bool operator<(const Relation ) 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::const_iterator;
+  using iterator = const_iterator;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &) = default;
+  RelationSlab =(RelationSlab &) = 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 lookup(const SymbolID ,
+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 ) { Relations.push_back(R); }
+
+/// Consumes the builder to finalize the slab.
+RelationSlab build() &&;
+
+  private:
+std::vector Relations;
+  };
+
+private:
+  RelationSlab(std::vector Relations)
+  : Relations(std::move(Relations)) {}
+
+  std::vector Relations;
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H
Index: clang-tools-extra/clangd/index/Relation.cpp
===
--- /dev/null
+++ 

[PATCH] D59407: [clangd] Add RelationSlab

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet added a comment.

Mostly LG from my side, thanks!




Comment at: clang-tools-extra/clangd/index/Relation.cpp:19
+llvm::iterator_range
+RelationSlab::lookup(const SymbolID ,
+ index::SymbolRole Predicate) const {

I would suggest adding another version which returns all the relations a given 
`Subject` participates, but I suppose currently we don't have any use cases.

Feel free to add or skip, that can be added when necessary.



Comment at: clang-tools-extra/clangd/index/Relation.cpp:24
+   [](const Relation , const Relation ) {
+ return (A.Subject < B.Subject) ||
+(A.Subject == B.Subject &&

`std::tie`



Comment at: clang-tools-extra/clangd/index/Relation.h:31
+  bool operator==(const Relation ) const {
+return Subject == Other.Subject && Predicate == Other.Predicate &&
+   Object == Other.Object;

nit: could you use `std::tie`



Comment at: clang-tools-extra/clangd/index/Relation.h:35
+  // SPO order
+  bool operator<(const Relation ) const {
+if (Subject < Other.Subject) {

again `std::tie`



Comment at: clang-tools-extra/clangd/index/Relation.h:52
+
+class RelationSlab {
+public:

I believe `RelationSlab` should still be immutable, even after the `build` 
operation below `RelationSlab` is mutable.
Let's introduce the builder class and move mutating operations and build into 
it. So that it would be more symmetric to other slabs we have.

Also are there any use-cases requiring RelationSlab to be mutable?



Comment at: clang-tools-extra/clangd/index/Relation.h:60
+  // that possibility for the future. Having a build() method is
+  // also useful so when know when to sort the relations.
+  using Builder = RelationSlab;

there seems to be some typos in the comment



Comment at: clang-tools-extra/clangd/index/Relation.h:72
+
+  void push_back(const Relation ) { Relations.push_back(R); }
+

maybe rename to `insert` to keep symmetry with other slabs?
also it suggests a semantics on the operation that we don't care about.



Comment at: clang-tools-extra/clangd/index/Relation.h:79
+  /// Sort relations in SPO order.
+  void sort();
+

maybe even get rid of sort by inlining it into build?



Comment at: clang-tools-extra/clangd/index/Relation.h:82
+  /// Lookup all relations matching the given subject and predicate.
+  /// Assumes the slab is sorted in SPO order.
+  llvm::iterator_range lookup(const SymbolID ,

again, we could get rid of this comment if slab was immutable



Comment at: clang-tools-extra/clangd/index/Relation.h:89
+private:
+  RelationSlab(std::vector Relations)
+  : Relations(std::move(Relations)) {}

Do we really need this?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

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();
   std::weak_ptr 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 
+#include 
+
+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 ) const {
+return Subject == Other.Subject && Predicate == Other.Predicate &&
+   Object == Other.Object;
+  }
+  // SPO order
+  bool operator<(const Relation ) 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::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 &) = default;
+  RelationSlab =(RelationSlab &) = 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 ) { 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 lookup(const SymbolID ,
+index::SymbolRole Predicate) const;
+
+  RelationSlab build() &&;
+
+private:
+  RelationSlab(std::vector 

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge planned changes to this revision.
nridge added a comment.

In D59407#1478794 , @sammccall wrote:

> So if you can stomach it, I think
>
> > **Approach 2: Add a RelationSlab storing (subject, predicate, object) 
> > triples, intended for sparse relations***
>
> is certainly fine with us (having spoken with @kadircet @ilya-biryukov 
> @sammccall @gribozavr - @hokein is on vacation but not nearly as stubborn as 
> I am!)


Yep, I'm happy to move forward with that approach. Thanks for the guidance!


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Sam McCall via Phabricator via cfe-commits]

sammccall added a subscriber: hokein.
sammccall added a comment.

Hi Nathan, sorry for the stall here, and for repeatedly going over the same 
issues.
The design space here is pretty complicated.

I think the conclusion of recent offline discussions is:

- refs and relations can be the same thing-ish when seen through a certain lens.
- Unifying them probably isn't space-prohibitive *if* we implement callgraph: 
it's something like +15% to overall memory usage, and storing callgraph in 
another way is likely to be similar.
- however unifying the concepts seems likely to be awkward in practice. LSP 
features seem to want one or the other but not both - symbolID is generally 
better than location if it's precise enough, and useless if not. We're storing 
redundant information (the location for the method override ref is the same as 
the declaration of the related symbol). We risk tying ourselves in knots 
maintaining a model that doesn't map well onto our problems.
- In terms of storage size, relation-major (`map>>` or so) seems like a quick win. But it's a 
small enough one that we should try to live without it first.

So if you can stomach it, I think

> **Approach 2: Add a RelationSlab storing (subject, predicate, object) 
> triples, intended for sparse relations***

is certainly fine with us (having spoken with @kadircet @ilya-biryukov 
@sammccall @gribozavr - @hokein is on vacation but not nearly as stubborn as I 
am!)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge added a comment.

Hi, any update here? I would appreciate some guidance so I can move forward 
with this.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge added a comment.

In D59407#1456394 , @sammccall wrote:

> One thing that strikes me here is that this case is very similar to our 
> existing Ref data - it's basically a subset, but with a symbolid payload 
> instead of location. We could consider just adding the SymbolID to Refs - 
> it'd blow up the size of that by 50%, but we may not do much better with some 
> other representation, and it would avoid adding any new complexity.


Note that this was considered and rejected earlier (see here 
 and here 
), though that discussion did not 
consider denser relations like callgraph.

Given the additional information and perspectives from the conversation here, I 
have two suggestions for potential ways forward:

**Approach 1: Add SymbolID to Refs**

- This would be initially wasteful when only subtypes use it, but if we then 
build callgraph on top of it as well it will become significantly less wasteful.
- This has the benefit that we don't have duplicate information for 
find-references and callgraph (they both use Refs).
- This approach probably adds the least amount of complexity overall.

**Approach 2: Add a RelationSlab storing (subject, predicate, object) triples, 
intended for sparse relations**

- This would allow us to implement features that require sparse relations, such 
as subtypes and overrides, without any significant increase to index size.
- If we later want to add dense relations like callgraph, we'd use a different 
mechanism for them (possibly by adding SymbolID to Refs as in approach 1).
- If we do end up adding SymbolID to Refs for callgraph, and want to start 
using that for sparse relations too, we can rip out RelationSlab.
- This also adds relatively little complexity, though slightly more than 
approach 1, and we are throwing away some code if we end up adding SymbolID to 
Refs eventually.

Any thoughts on which of the approaches to take, or something else altogether? 
It would be good to have confidence that the chosen approach will pass code 
review before I spend time implementing it :)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Sam McCall via Phabricator via cfe-commits]

sammccall added a comment.

In D59407#1447070 , @nridge wrote:

> @sammccall, thank you for having a look at this.
>
> I have no objection to revising the data model if there's agreement on a 
> better one.
>
> In D59407#1446464 , @sammccall wrote:
>
> > - I don't think we yet know what the more resource-critical (denser) 
> > relations and queries are, so it's unclear what to optimize for
>
>
> Based on a brief mental survey of C++ IDE features I'm familiar with, I can 
> think of the following additional uses of the relations capability:
>
> - A call hierarchy feature (which is also proposed for LSP 
> , with 
> client  and server 
>  
> implementation efforts) would need every caller-callee relationship to be 
> recorded in the index (`RelationCalledBy`).
> - Given a virtual method declaration, a user may want to see a list of 
> implementations (overriders) and navigate to one or more of them. This would 
> need every overrider relationship to be recorded in the index 
> (`RelationOverrideOf`).
>
>   Intuitively, it seems like `RelationOverrideOf` would be slightly denser 
> than `RelationChildOf` (though not by much), while `RelationCalledBy` would 
> be significantly denser. In terms of queries, I believe the key for lookups 
> for both of the above would be a (subject, predicate) pair, just like for 
> subtypes.
>
>   Does that change your analysis at all?


Sorry for the slow response here. Override and callgraph are great examples!
As you say, override is probably pretty sparse and it's probably not worth 
worrying about the storage too much.

If we stored a callgraph we'd definitely need to worry about the representation 
though. The space-saving hierarchy in this case would be map>I guess. Maybe storing one `vector>` for each relationship type would work here - querying for a bunch 
of relationship types is rare.
One thing that strikes me here is that this case is very similar to our 
existing Ref data - it's basically a subset, but with a symbolid payload 
instead of location. We could consider just adding the SymbolID to Refs - it'd 
blow up the size of that by 50%, but we may not do much better with some other 
representation, and it would avoid adding any new complexity.
Ultimately it may also be that supporting both find references and callgraph 
(which provide closely overlapping functionality) isn't a good use of index 
memory.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge requested review of this revision.
nridge added a reviewer: sammccall.
nridge added a comment.

I guess I should clear the "Accepted" status until we settle the question of 
the data model.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge added a comment.

@sammccall, thank you for having a look at this.

I have no objection to revising the data model if there's agreement on a better 
one.

In D59407#1446464 , @sammccall wrote:

> - I don't think we yet know what the more resource-critical (denser) 
> relations and queries are, so it's unclear what to optimize for


Based on a brief mental survey of C++ IDE features I'm familiar with, I can 
think of the following additional uses of the relations capability:

- A call hierarchy feature (which is also proposed for LSP 
, with client 
 and server 
 
implementation efforts) would need every caller-callee relationship to be 
recorded in the index (`RelationCalledBy`).
- Given a virtual method declaration, a user may want to see a list of 
implementations (overriders) and navigate to one or more of them. This would 
need every overrider relationship to be recorded in the index 
(`RelationOverrideOf`).

Intuitively, it seems like `RelationOverrideOf` would be slightly denser than 
`RelationChildOf` (though not by much), while `RelationCalledBy` would be 
significantly denser. In terms of queries, I believe the key for lookups for 
both of the above would be a (subject, predicate) pair, just like for subtypes.

Does that change your analysis at all?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Sam McCall via Phabricator via cfe-commits]

sammccall added a comment.

(Sorry to arrive late at this discussion, I'm just back from leave.
I have some suggestions and would appreciate your thoughts, but if simply this 
feels too much like going around in circles I'm happy to work out how we can 
address this after this patch lands instead.
Have discussed offline with @gribozavr and I think we're roughly on the same 
page. @kadircet is now out on leave)

I think the data model might be overly complicated here.
I can see how the discussion got here: it mirrors the other `*Slab` types quite 
closely. But:

- those types were designed to solve specific problems that we don't have here 
(string deduplication and symbol merging)
- I think the class-parent relation is pretty sparse (maybe 1 edge per 10 
symbols?) so lots of options will work fine
- I don't think we yet know what the more resource-critical (denser) relations 
and queries are, so it's unclear what to optimize for

I think the simplest model that can work here is something like:

- `Relation` is `struct { SymbolID Subject; SymbolRole Relation; SymbolID 
Object }`
- this is a value type, so could be passed around simply as 
`std::vector`. If `RelationSlab` is desired for symmetry, it could be 
an alias or simple wrapper around `std::vector`.

This has a few advantages:

- the `Relation` value_type is self-contained, has clearer semantics, and works 
as the result of any type of query: based on subject and/or predicate and/or 
object. (Similar to how it's convenient that Symbol contains SymbolID).
- if lookup is desired, lookup by subject, subject+predicate, or full-triple is 
possible by sorting in SPO order with binary search. Return type is simple 
`ArrayRef`. (Though fancy lookup maybe better belongs in MemIndex/Dex 
rather than in the slab). For more query types, storing a copies in OSP and/or 
POS order is pretty cheap too.
- memory efficiency: it costs `20*distinct(subject, predicate, object)` bytes, 
vs `28*distinct(subject, predicate) + 8 * distinct(subject, predicate, 
object)`. Unless the average number of objects for a `(subject, predicate)` 
pair (that has at least one object) is >2.3, the former is smaller. For the 
current use case, this average is certainly <1.1.
- simplicity: no arenas, easy mental model.

I see discussion of (something like) this option stalled around the index 
constructors, but I don't see a fundamental block there. The concept that the 
index constructor should be templated over would be `Iterable`. LMK 
if I'm missing something.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge added a comment.

Ok, cool. In that case, I think this patch is ready to be committed, and would 
appreciate it if someone could commit it. Thanks!


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Dmitri Gribenko via Phabricator via cfe-commits]

gribozavr added a comment.

Submitting code as it becomes ready is the usual practice here.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge added a comment.

As this is the first of a series of patches adding support for relations, and 
then building type hierarchy subtypes on top (as discussed here 
), how should we go about landing this 
-- should we land each patch in the series as soon as it's ready, or should we 
wait to land them all together?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge updated this revision to Diff 191886.
nridge added a comment.

Scrapped 'struct Relation' and addressed other comments


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

Index: clang-tools-extra/clangd/index/Relation.h
===
--- /dev/null
+++ clang-tools-extra/clangd/index/Relation.h
@@ -0,0 +1,120 @@
+//===--- 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/DenseMap.h"
+#include "llvm/Support/StringSaver.h"
+#include "llvm/Support/raw_ostream.h"
+#include 
+#include 
+#include 
+
+namespace clang {
+namespace clangd {
+
+struct RelationKey {
+  SymbolID Symbol;
+  index::SymbolRole Kind;
+
+  bool operator==(const RelationKey ) const {
+return Symbol == Other.Symbol && Kind == Other.Kind;
+  }
+
+private:
+  friend llvm::hash_code hash_value(const RelationKey ) {
+return llvm::hash_combine(Key.Symbol, static_cast(Key.Kind));
+  }
+};
+
+class RelationSlab {
+public:
+  /// The interpretation of a pair (Key, Value) is:
+  /// " is  of every symbol in ".
+  /// For example, if Key.Kind == SymbolRole::RelationChildOf,
+  /// then Key.Symbol is the child of every symbol in Value (i.e. the symbols
+  /// in Value are the base classes of Key.Symbol).
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;
+  using iterator = const_iterator;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &) = default;
+  RelationSlab =(RelationSlab &) = default;
+
+  const_iterator begin() const { return Relations.begin(); }
+  const_iterator end() const { return Relations.end(); }
+  size_t size() const { return Relations.size(); }
+  size_t numRelations() const { return NumRelations; }
+  bool empty() const { return Relations.empty(); }
+
+  size_t bytes() const {
+return sizeof(*this) + Arena.getTotalMemory() +
+   sizeof(value_type) * Relations.capacity();
+  }
+
+  /// A mutable container that can 'freeze' to RelationSlab.
+  class Builder {
+  public:
+Builder() {}
+/// Adds a relation to the slab.
+void insert(const RelationKey , const SymbolID );
+/// Consumes the builder to finalize the slab.
+RelationSlab build() &&;
+
+  private:
+llvm::BumpPtrAllocator Arena;
+llvm::DenseMap> Relations;
+  };
+
+private:
+  RelationSlab(std::vector Relations, llvm::BumpPtrAllocator Arena,
+   size_t NumRelations)
+  : Arena(std::move(Arena)), Relations(std::move(Relations)),
+NumRelations(NumRelations) {}
+
+  llvm::BumpPtrAllocator Arena;
+  std::vector Relations;
+  // Number of all relations.
+  size_t NumRelations = 0;
+};
+
+} // namespace clangd
+} // namespace clang
+
+namespace llvm {
+
+// Support RelationKeys as DenseMap keys.
+template <> struct DenseMapInfo {
+  static inline clang::clangd::RelationKey getEmptyKey() {
+return {DenseMapInfo::getEmptyKey(),
+clang::index::SymbolRole::RelationChildOf};
+  }
+
+  static inline clang::clangd::RelationKey getTombstoneKey() {
+return {DenseMapInfo::getTombstoneKey(),
+clang::index::SymbolRole::RelationChildOf};
+  }
+
+  static unsigned getHashValue(const clang::clangd::RelationKey ) {
+return hash_value(Key);
+  }
+
+  static bool isEqual(const clang::clangd::RelationKey ,
+  const clang::clangd::RelationKey ) {
+return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
+#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,35 @@
+//===--- 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"
+
+namespace clang {
+namespace clangd {
+
+void RelationSlab::Builder::insert(const RelationKey , const SymbolID ) {
+  

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge marked 2 inline comments as done.
nridge added inline comments.



Comment at: clang-tools-extra/clangd/index/Relation.h:1
+//===--- Ref.h ---*- 
C++-*-===//
+//

gribozavr wrote:
> gribozavr wrote:
> > "--- Relation.h "
> Not done?
(Sorry, I have these comments addressed locally, was just waiting for the 
resolution of the remaining issue before uploading.)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Dmitri Gribenko via Phabricator via cfe-commits]

gribozavr added inline comments.



Comment at: clang-tools-extra/clangd/index/Relation.h:1
+//===--- Ref.h ---*- 
C++-*-===//
+//

gribozavr wrote:
> "--- Relation.h "
Not done?



Comment at: clang-tools-extra/clangd/index/Relation.h:41
+public:
+  // Key.Symbol is Key.Kind of every symbol in Value.
+  // For example, if Key.Kind == SymbolRole::RelationChildOf,

gribozavr wrote:
> Three slashes for doc comments, please.
Not done?



Comment at: clang-tools-extra/clangd/index/Relation.h:45
+  // in Value are the base classes of Key.Symbol).
+  struct Relation {
+RelationKey Key;

nridge wrote:
> gribozavr wrote:
> > Lift it up into the `clang::clangd` namespace?  (like `Symbol` and `Ref`)
> This comment made me realize that I haven't addressed your previous comment 
> properly: I haven't changed `RelationSlab::value_type` from 
> `std::pair>` to `Relation`.
> 
> I tried to make that change this time, and ran into a problem:
> 
> In the rest of the subtypes patch (D58880), one of the things I do is extend 
> the `MemIndex` constructor so that, in addition to taking a symbol range and 
> a ref range, it takes a relation range.
> 
> That constructor assumes that the elements of that range have members of some 
> name - either `first` and `second` (as currently in D58880), or `Key` and 
> `Value`.
> 
> However, that constructor has two call sites. In `MemIndex::build()`, we pass 
> in the slabs themselves as the ranges. So, if we make this change, the field 
> names for that call site will be `Key` and `Value`. However, for the second 
> call site in `FileSymbols::buildIndex()`, the ranges that are passed in are 
> `DenseMap`s, and therefore their elements' field names are necessarily 
> `first` and `second`. The same constructor cannot therefore accept both 
> ranges.
> 
> How do you propose we address this?
> 
>  * Scrap `struct Relation`, and keep `value_type` as `std::pair llvm::ArrayRef>`?
>  * Keep `struct Relation`, but make its fields named `first` and `second`?
>  * Split the constructor of `MemIndex` into two constructors, to accomodate 
> both sets of field names?
>  * Something else?
I guess we should scrap it then.  Kadir, WDYT?



Comment at: clang-tools-extra/clangd/index/Relation.h:68
+
+  // RelationSlab::Builder is a mutable container that can 'freeze' to
+  // RelationSlab.

gribozavr wrote:
> No need to repeat the type name being documented.  "A mutable container that 
> can ..."
Not done?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge marked 8 inline comments as done.
nridge added inline comments.



Comment at: clang-tools-extra/clangd/index/Index.h:43
+public:
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;

kadircet wrote:
> nridge wrote:
> > kadircet wrote:
> > > gribozavr wrote:
> > > > `struct Relation`?  And in the comments for it, please explain which 
> > > > way the relationship is directed (is the SymbolID in the key the 
> > > > subtype?  or is the SymbolID in the ArrayRef the subtype?).
> > > Ah exactly my thoughts, forget to mention this.
> > > 
> > > I believe current usage is the counter-intuitive one. For example, we 
> > > will most likely query with something like:
> > > `getRelations(SymbolID, baseOf)` to get all relations where `SymbolID` is 
> > > `baseOf` something else(which says get children of `SymbolID`)
> > > 
> > > So that this valueType can be read like, 
> > > ```
> > > `SymbolID` is `RelationKind` every `SymbolID inside array`
> > > ```
> > > WDYT?
> > The way I was thinking of it is that `getRelations(SymbolID, baseOf)` would 
> > return all the bases of `SymbolID`. However, the opposite interpretation is 
> > also reasonable, we just need to pick one and document it. I'm happy to go 
> > with your suggested one.
> It looks like IndexingAPI is also using the interpretation I suggested, so 
> let's move with that one if you don't have any other concerns.
Already updated to this interpretation :)



Comment at: clang-tools-extra/clangd/index/Relation.h:45
+  // in Value are the base classes of Key.Symbol).
+  struct Relation {
+RelationKey Key;

gribozavr wrote:
> Lift it up into the `clang::clangd` namespace?  (like `Symbol` and `Ref`)
This comment made me realize that I haven't addressed your previous comment 
properly: I haven't changed `RelationSlab::value_type` from 
`std::pair>` to `Relation`.

I tried to make that change this time, and ran into a problem:

In the rest of the subtypes patch (D58880), one of the things I do is extend 
the `MemIndex` constructor so that, in addition to taking a symbol range and a 
ref range, it takes a relation range.

That constructor assumes that the elements of that range have members of some 
name - either `first` and `second` (as currently in D58880), or `Key` and 
`Value`.

However, that constructor has two call sites. In `MemIndex::build()`, we pass 
in the slabs themselves as the ranges. So, if we make this change, the field 
names for that call site will be `Key` and `Value`. However, for the second 
call site in `FileSymbols::buildIndex()`, the ranges that are passed in are 
`DenseMap`s, and therefore their elements' field names are necessarily `first` 
and `second`. The same constructor cannot therefore accept both ranges.

How do you propose we address this?

 * Scrap `struct Relation`, and keep `value_type` as `std::pair>`?
 * Keep `struct Relation`, but make its fields named `first` and `second`?
 * Split the constructor of `MemIndex` into two constructors, to accomodate 
both sets of field names?
 * Something else?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet added a comment.

In D59407#1432543 , @nridge wrote:

> If it's (B), how many bytes should the index be? Are the space gains worth 
> the complexity, given that `SymbolID` is only 8 bytes to begin with? (As 
> compared to say, the filenames in `Ref`, which can be much longer, making 
> this sort of optimization more clearly worth it.)


That was the case, I agree with you we should rather do that while serializing 
where we have variable length integers and duplication is more severe(all three 
slabs make use of same SymbolID pool).




Comment at: clang-tools-extra/clangd/index/Index.h:43
+public:
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;

nridge wrote:
> kadircet wrote:
> > gribozavr wrote:
> > > `struct Relation`?  And in the comments for it, please explain which way 
> > > the relationship is directed (is the SymbolID in the key the subtype?  or 
> > > is the SymbolID in the ArrayRef the subtype?).
> > Ah exactly my thoughts, forget to mention this.
> > 
> > I believe current usage is the counter-intuitive one. For example, we will 
> > most likely query with something like:
> > `getRelations(SymbolID, baseOf)` to get all relations where `SymbolID` is 
> > `baseOf` something else(which says get children of `SymbolID`)
> > 
> > So that this valueType can be read like, 
> > ```
> > `SymbolID` is `RelationKind` every `SymbolID inside array`
> > ```
> > WDYT?
> The way I was thinking of it is that `getRelations(SymbolID, baseOf)` would 
> return all the bases of `SymbolID`. However, the opposite interpretation is 
> also reasonable, we just need to pick one and document it. I'm happy to go 
> with your suggested one.
It looks like IndexingAPI is also using the interpretation I suggested, so 
let's move with that one if you don't have any other concerns.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Dmitri Gribenko via Phabricator via cfe-commits]

gribozavr accepted this revision.
gribozavr added inline comments.
This revision is now accepted and ready to land.



Comment at: clang-tools-extra/clangd/index/Index.h:59
+return sizeof(*this) + Arena.getTotalMemory() +
+   sizeof(value_type) * Relations.size();
+  }

nridge wrote:
> kadircet wrote:
> > use capacity instead of size
> Note, `RefSlab::bytes()` (which I where I copied this from) uses `size()` as 
> well. Should I change that too?
I'd say yes -- in a separate patch though.  Thanks for catching it!



Comment at: clang-tools-extra/clangd/index/Relation.h:1
+//===--- Ref.h ---*- 
C++-*-===//
+//

"--- Relation.h "



Comment at: clang-tools-extra/clangd/index/Relation.h:41
+public:
+  // Key.Symbol is Key.Kind of every symbol in Value.
+  // For example, if Key.Kind == SymbolRole::RelationChildOf,

Three slashes for doc comments, please.



Comment at: clang-tools-extra/clangd/index/Relation.h:45
+  // in Value are the base classes of Key.Symbol).
+  struct Relation {
+RelationKey Key;

Lift it up into the `clang::clangd` namespace?  (like `Symbol` and `Ref`)



Comment at: clang-tools-extra/clangd/index/Relation.h:68
+
+  // RelationSlab::Builder is a mutable container that can 'freeze' to
+  // RelationSlab.

No need to repeat the type name being documented.  "A mutable container that 
can ..."


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge updated this revision to Diff 191036.
nridge marked an inline comment as done.
nridge added a comment.
Herald added a subscriber: mgorny.

Address review comments, except for the deduplication which is still under 
discussion


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

Index: clang-tools-extra/clangd/index/Relation.h
===
--- /dev/null
+++ clang-tools-extra/clangd/index/Relation.h
@@ -0,0 +1,124 @@
+//===--- Ref.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/DenseMap.h"
+#include "llvm/Support/StringSaver.h"
+#include "llvm/Support/raw_ostream.h"
+#include 
+#include 
+#include 
+
+namespace clang {
+namespace clangd {
+
+struct RelationKey {
+  SymbolID Symbol;
+  index::SymbolRole Kind;
+
+  bool operator==(const RelationKey ) const {
+return Symbol == Other.Symbol && Kind == Other.Kind;
+  }
+
+private:
+  friend llvm::hash_code hash_value(const RelationKey ) {
+return llvm::hash_combine(Key.Symbol, static_cast(Key.Kind));
+  }
+};
+
+class RelationSlab {
+public:
+  // Key.Symbol is Key.Kind of every symbol in Value.
+  // For example, if Key.Kind == SymbolRole::RelationChildOf,
+  // then Key.Symbol is the child of every symbol in Value (i.e. the symbols
+  // in Value are the base classes of Key.Symbol).
+  struct Relation {
+RelationKey Key;
+llvm::ArrayRef Value;
+  };
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;
+  using iterator = const_iterator;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &) = default;
+  RelationSlab =(RelationSlab &) = default;
+
+  const_iterator begin() const { return Relations.begin(); }
+  const_iterator end() const { return Relations.end(); }
+  size_t size() const { return Relations.size(); }
+  size_t numRelations() const { return NumRelations; }
+  bool empty() const { return Relations.empty(); }
+
+  size_t bytes() const {
+return sizeof(*this) + Arena.getTotalMemory() +
+   sizeof(value_type) * Relations.capacity();
+  }
+
+  // RelationSlab::Builder is a mutable container that can 'freeze' to
+  // RelationSlab.
+  class Builder {
+  public:
+Builder() {}
+// Adds a relation to the slab.
+void insert(const RelationKey , const SymbolID );
+// Consumes the builder to finalize the slab.
+RelationSlab build() &&;
+
+  private:
+llvm::BumpPtrAllocator Arena;
+llvm::DenseMap> Relations;
+  };
+
+private:
+  RelationSlab(std::vector Relations, llvm::BumpPtrAllocator Arena,
+   size_t NumRelations)
+  : Arena(std::move(Arena)), Relations(std::move(Relations)),
+NumRelations(NumRelations) {}
+
+  llvm::BumpPtrAllocator Arena;
+  std::vector Relations;
+  // Number of all relations.
+  size_t NumRelations = 0;
+};
+
+} // namespace clangd
+} // namespace clang
+
+namespace llvm {
+
+// Support RelationKeys as DenseMap keys.
+template <> struct DenseMapInfo {
+  static inline clang::clangd::RelationKey getEmptyKey() {
+return {DenseMapInfo::getEmptyKey(),
+clang::index::SymbolRole::RelationChildOf};
+  }
+
+  static inline clang::clangd::RelationKey getTombstoneKey() {
+return {DenseMapInfo::getTombstoneKey(),
+clang::index::SymbolRole::RelationChildOf};
+  }
+
+  static unsigned getHashValue(const clang::clangd::RelationKey ) {
+return hash_value(Key);
+  }
+
+  static bool isEqual(const clang::clangd::RelationKey ,
+  const clang::clangd::RelationKey ) {
+return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
+#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,35 @@
+//===--- Ref.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
+//

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge marked 7 inline comments as done.
nridge added inline comments.



Comment at: clang-tools-extra/clangd/index/Index.h:43
+public:
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;

kadircet wrote:
> gribozavr wrote:
> > `struct Relation`?  And in the comments for it, please explain which way 
> > the relationship is directed (is the SymbolID in the key the subtype?  or 
> > is the SymbolID in the ArrayRef the subtype?).
> Ah exactly my thoughts, forget to mention this.
> 
> I believe current usage is the counter-intuitive one. For example, we will 
> most likely query with something like:
> `getRelations(SymbolID, baseOf)` to get all relations where `SymbolID` is 
> `baseOf` something else(which says get children of `SymbolID`)
> 
> So that this valueType can be read like, 
> ```
> `SymbolID` is `RelationKind` every `SymbolID inside array`
> ```
> WDYT?
The way I was thinking of it is that `getRelations(SymbolID, baseOf)` would 
return all the bases of `SymbolID`. However, the opposite interpretation is 
also reasonable, we just need to pick one and document it. I'm happy to go with 
your suggested one.



Comment at: clang-tools-extra/clangd/index/Index.h:59
+return sizeof(*this) + Arena.getTotalMemory() +
+   sizeof(value_type) * Relations.size();
+  }

kadircet wrote:
> use capacity instead of size
Note, `RefSlab::bytes()` (which I where I copied this from) uses `size()` as 
well. Should I change that too?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge added a comment.

In D59407#1430656 , @kadircet wrote:

> I believe it makes sense to deduplicate SymbolIDs for RelationSlab.
>  Up until now, we mostly had only one occurence of a SymbolID in a Slab, but 
> RelationSlab does not follow that assumption.


Just to make sure I understand, do you mean:

(A) When adding a `SymbolID` to an entry's value, check that it's not already 
there; or
(B) Try to conserve space by not storing `SymbolID`s directly in the entries, 
but storing an index into a separate list of unique `SymbolID`s.

If it's (B), how many bytes should the index be? Are the space gains worth the 
complexity, given that `SymbolID` is only 8 bytes to begin with? (As compared 
to say, the filenames in `Ref`, which can be much longer, making this sort of 
optimization more clearly worth it.)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet added inline comments.



Comment at: clang-tools-extra/clangd/index/Index.h:43
+public:
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;

gribozavr wrote:
> `struct Relation`?  And in the comments for it, please explain which way the 
> relationship is directed (is the SymbolID in the key the subtype?  or is the 
> SymbolID in the ArrayRef the subtype?).
Ah exactly my thoughts, forget to mention this.

I believe current usage is the counter-intuitive one. For example, we will most 
likely query with something like:
`getRelations(SymbolID, baseOf)` to get all relations where `SymbolID` is 
`baseOf` something else(which says get children of `SymbolID`)

So that this valueType can be read like, 
```
`SymbolID` is `RelationKind` every `SymbolID inside array`
```
WDYT?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Dmitri Gribenko via Phabricator via cfe-commits]

gribozavr added inline comments.



Comment at: clang-tools-extra/clangd/index/Index.cpp:35
+auto *Array = Arena.Allocate(Rels.size());
+std::uninitialized_copy(Rels.begin(), Rels.end(), Array);
+Result.emplace_back(Entry.first,

Use `ArrayRef::copy()`, for example: https://reviews.llvm.org/D58782




Comment at: clang-tools-extra/clangd/index/Index.h:43
+public:
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;

`struct Relation`?  And in the comments for it, please explain which way the 
relationship is directed (is the SymbolID in the key the subtype?  or is the 
SymbolID in the ArrayRef the subtype?).



Comment at: clang-tools-extra/clangd/index/Index.h:88
+  size_t NumRelations = 0;
+};
+

Please move all new declarations into `Relation.h`.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet added a comment.

This mostly looks good, one high level comment:
I believe it makes sense to deduplicate SymbolIDs for RelationSlab.
Up until now, we mostly had only one occurence of a SymbolID in a Slab, but 
RelationSlab does not follow that assumption.

Also can you add a few tests after the above mentioned check to make sure 
interning SymbolIDs works as expected?




Comment at: clang-tools-extra/clangd/index/Index.h:25
 
+enum class RelationKind { Subtype };
+

nridge wrote:
> One thing I'm wondering about is: would it be better to just use 
> `clang::index::SymbolRole` here (which has `Relation___Of` entries that cover 
> what we're interested in) instead of having our own enum?
I totally agree, but that struct is 4 bytes. I am not sure it is worth the 
trade off when storing the relationslab, but since this patch is not related to 
serialization let's get rid of RelationKind and make use of 
clang::index::SymbolRole.

When landing serialization part we can either split clang::index::SymbolRole 
into two parts or add some custom mapping to serialize only relevant bits etc.



Comment at: clang-tools-extra/clangd/index/Index.h:59
+return sizeof(*this) + Arena.getTotalMemory() +
+   sizeof(value_type) * Relations.size();
+  }

use capacity instead of size



Comment at: clang-tools-extra/clangd/index/Index.h:67
+Builder() {}
+// Adds a relation to the slab. Deep copy: Strings will be owned by the
+// slab.

I am not sure comment currently applies to RelationSlab internals, since 
everything is of value type anyways, there are no references.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge marked an inline comment as done.
nridge added inline comments.



Comment at: clang-tools-extra/clangd/index/Index.h:25
 
+enum class RelationKind { Subtype };
+

One thing I'm wondering about is: would it be better to just use 
`clang::index::SymbolRole` here (which has `Relation___Of` entries that cover 
what we're interested in) instead of having our own enum?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D59407/new/

https://reviews.llvm.org/D59407



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D59407: [clangd] Add RelationSlab

[Nathan Ridge via Phabricator via cfe-commits]

nridge created this revision.
nridge added a reviewer: kadircet.
Herald added subscribers: cfe-commits, arphaman, jkorous, MaskRay, ioeric, 
ilya-biryukov.
Herald added a project: clang.

RelationSlab is a new index data structure, similar to SymbolSlab and
RefSlab. RelationSlab stores relations between Symbols.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D59407

Files:
  clang-tools-extra/clangd/index/Index.cpp
  clang-tools-extra/clangd/index/Index.h

Index: clang-tools-extra/clangd/index/Index.h
===
--- clang-tools-extra/clangd/index/Index.h
+++ clang-tools-extra/clangd/index/Index.h
@@ -22,6 +22,71 @@
 namespace clang {
 namespace clangd {
 
+enum class RelationKind { Subtype };
+
+struct RelationKey {
+  SymbolID Symbol;
+  RelationKind Kind;
+
+  bool operator==(const RelationKey ) const {
+return Symbol == Other.Symbol && Kind == Other.Kind;
+  }
+
+private:
+  friend llvm::hash_code hash_value(const RelationKey ) {
+return llvm::hash_combine(Key.Symbol, static_cast(Key.Kind));
+  }
+};
+
+class RelationSlab {
+public:
+  using value_type = std::pair>;
+  using const_iterator = std::vector::const_iterator;
+  using iterator = const_iterator;
+
+  RelationSlab() = default;
+  RelationSlab(RelationSlab &) = default;
+  RelationSlab =(RelationSlab &) = default;
+
+  const_iterator begin() const { return Relations.begin(); }
+  const_iterator end() const { return Relations.end(); }
+  size_t size() const { return Relations.size(); }
+  size_t numRelations() const { return NumRelations; }
+  bool empty() const { return Relations.empty(); }
+
+  size_t bytes() const {
+return sizeof(*this) + Arena.getTotalMemory() +
+   sizeof(value_type) * Relations.size();
+  }
+
+  // RelationSlab::Builder is a mutable container that can 'freeze' to
+  // RelationSlab.
+  class Builder {
+  public:
+Builder() {}
+// Adds a relation to the slab. Deep copy: Strings will be owned by the
+// slab.
+void insert(const RelationKey , const SymbolID );
+// Consumes the builder to finalize the slab.
+RelationSlab build() &&;
+
+  private:
+llvm::BumpPtrAllocator Arena;
+llvm::DenseMap> Relations;
+  };
+
+private:
+  RelationSlab(std::vector Relations, llvm::BumpPtrAllocator Arena,
+   size_t NumRelations)
+  : Arena(std::move(Arena)), Relations(std::move(Relations)),
+NumRelations(NumRelations) {}
+
+  llvm::BumpPtrAllocator Arena;
+  std::vector Relations;
+  // Number of all relations.
+  size_t NumRelations = 0;
+};
+
 struct FuzzyFindRequest {
   /// \brief A query string for the fuzzy find. This is matched against symbols'
   /// un-qualified identifiers and should not contain qualifiers like "::".
@@ -136,4 +201,30 @@
 } // namespace clangd
 } // namespace clang
 
+namespace llvm {
+
+// Support RelationKeys as DenseMap keys.
+template <> struct DenseMapInfo {
+  static inline clang::clangd::RelationKey getEmptyKey() {
+return {DenseMapInfo::getEmptyKey(),
+clang::clangd::RelationKind::Subtype};
+  }
+
+  static inline clang::clangd::RelationKey getTombstoneKey() {
+return {DenseMapInfo::getTombstoneKey(),
+clang::clangd::RelationKind::Subtype};
+  }
+
+  static unsigned getHashValue(const clang::clangd::RelationKey ) {
+return hash_value(Key);
+  }
+
+  static bool isEqual(const clang::clangd::RelationKey ,
+  const clang::clangd::RelationKey ) {
+return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
Index: clang-tools-extra/clangd/index/Index.cpp
===
--- clang-tools-extra/clangd/index/Index.cpp
+++ clang-tools-extra/clangd/index/Index.cpp
@@ -17,6 +17,28 @@
 namespace clang {
 namespace clangd {
 
+void RelationSlab::Builder::insert(const RelationKey , const SymbolID ) {
+  Relations[Key].push_back(S);
+}
+
+RelationSlab RelationSlab::Builder::build() && {
+  // Reallocate relations on the arena to reduce waste and indirections when
+  // reading.
+  std::vector>> Result;
+  Result.reserve(Relations.size());
+  size_t NumRelations = 0;
+  for (auto  : Relations) {
+auto  = Entry.second;
+
+NumRelations += Rels.size();
+auto *Array = Arena.Allocate(Rels.size());
+std::uninitialized_copy(Rels.begin(), Rels.end(), Array);
+Result.emplace_back(Entry.first,
+llvm::ArrayRef(Array, Rels.size()));
+  }
+  return RelationSlab(std::move(Result), std::move(Arena), NumRelations);
+}
+
 void SwapIndex::reset(std::unique_ptr Index) {
   // Keep the old index alive, so we don't destroy it under lock (may be slow).
   std::shared_ptr Pin;
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits