clang-tools  14.0.0git
Ref.h
Go to the documentation of this file.
1 //===--- Ref.h ---------------------------------------------------*- C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H
10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H
11 
12 #include "SymbolID.h"
13 #include "SymbolLocation.h"
14 #include "clang/Index/IndexSymbol.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/Hashing.h"
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/Support/StringSaver.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include <cstdint>
21 #include <set>
22 #include <utility>
23 
24 namespace clang {
25 namespace clangd {
26 
27 /// Describes the kind of a cross-reference.
28 ///
29 /// This is a bitfield which can be combined from different kinds.
30 enum class RefKind : uint8_t {
31  Unknown = 0,
32  // Points to symbol declaration. Example:
33  //
34  // class Foo;
35  // ^ Foo declaration
36  // Foo foo;
37  // ^ this does not reference Foo declaration
38  Declaration = 1 << 0,
39  // Points to symbol definition. Example:
40  //
41  // int foo();
42  // ^ references foo declaration, but not foo definition
43  // int foo() { return 42; }
44  // ^ references foo definition, but not declaration
45  // bool bar() { return true; }
46  // ^ references both definition and declaration
47  Definition = 1 << 1,
48  // Points to symbol reference. Example:
49  //
50  // int Foo = 42;
51  // int Bar = Foo + 1;
52  // ^ this is a reference to Foo
53  Reference = 1 << 2,
54  // The reference explicitly spells out declaration's name. Such references can
55  // not come from macro expansions or implicit AST nodes.
56  //
57  // class Foo { public: Foo() {} };
58  // ^ references declaration, definition and explicitly spells out name
59  // #define MACRO Foo
60  // v there is an implicit constructor call here which is not a spelled ref
61  // Foo foo;
62  // ^ this reference explicitly spells out Foo's name
63  // struct Bar {
64  // MACRO Internal;
65  // ^ this references Foo, but does not explicitly spell out its name
66  // };
67  Spelled = 1 << 3,
69 };
70 
72  return static_cast<RefKind>(static_cast<uint8_t>(L) |
73  static_cast<uint8_t>(R));
74 }
75 inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; }
77  return static_cast<RefKind>(static_cast<uint8_t>(A) &
78  static_cast<uint8_t>(B));
79 }
80 
81 llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefKind);
82 
83 /// Represents a symbol occurrence in the source file.
84 /// Despite the name, it could be a declaration/definition/reference.
85 ///
86 /// WARNING: Location does not own the underlying data - Copies are shallow.
87 struct Ref {
88  /// The source location where the symbol is named.
91  /// The ID of the symbol whose definition contains this reference.
92  /// For example, for a reference inside a function body, this would
93  /// be that function. For top-level definitions this isNull().
95 };
96 
97 inline bool operator<(const Ref &L, const Ref &R) {
98  return std::tie(L.Location, L.Kind, L.Container) <
99  std::tie(R.Location, R.Kind, R.Container);
100 }
101 inline bool operator==(const Ref &L, const Ref &R) {
102  return std::tie(L.Location, L.Kind, L.Container) ==
103  std::tie(R.Location, R.Kind, R.Container);
104 }
105 
106 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Ref &);
107 
108 /// An efficient structure of storing large set of symbol references in memory.
109 /// Filenames are deduplicated.
110 class RefSlab {
111 public:
112  // Refs are stored in order.
113  using value_type = std::pair<SymbolID, llvm::ArrayRef<Ref>>;
114  using const_iterator = std::vector<value_type>::const_iterator;
116 
117  RefSlab() = default;
118  RefSlab(RefSlab &&Slab) = default;
119  RefSlab &operator=(RefSlab &&RHS) = default;
120 
121  const_iterator begin() const { return Refs.begin(); }
122  const_iterator end() const { return Refs.end(); }
123  /// Gets the number of symbols.
124  size_t size() const { return Refs.size(); }
125  size_t numRefs() const { return NumRefs; }
126  bool empty() const { return Refs.empty(); }
127 
128  size_t bytes() const {
129  return sizeof(*this) + Arena.getTotalMemory() +
130  sizeof(value_type) * Refs.capacity();
131  }
132 
133  /// RefSlab::Builder is a mutable container that can 'freeze' to RefSlab.
134  class Builder {
135  public:
136  Builder() : UniqueStrings(Arena) {}
137  /// Adds a ref to the slab. Deep copy: Strings will be owned by the slab.
138  void insert(const SymbolID &ID, const Ref &S);
139  /// Consumes the builder to finalize the slab.
140  RefSlab build() &&;
141 
142  private:
143  // A ref we're storing with its symbol to consume with build().
144  // All strings are interned, so DenseMapInfo can use pointer comparisons.
145  struct Entry {
147  Ref Reference;
148  };
149  friend struct llvm::DenseMapInfo<Entry>;
150 
151  llvm::BumpPtrAllocator Arena;
152  llvm::UniqueStringSaver UniqueStrings; // Contents on the arena.
153  llvm::DenseSet<Entry> Entries;
154  };
155 
156 private:
157  RefSlab(std::vector<value_type> Refs, llvm::BumpPtrAllocator Arena,
158  size_t NumRefs)
159  : Arena(std::move(Arena)), Refs(std::move(Refs)), NumRefs(NumRefs) {}
160 
161  llvm::BumpPtrAllocator Arena;
162  std::vector<value_type> Refs;
163  /// Number of all references.
164  size_t NumRefs = 0;
165 };
166 
167 } // namespace clangd
168 } // namespace clang
169 
170 namespace llvm {
171 template <> struct DenseMapInfo<clang::clangd::RefSlab::Builder::Entry> {
172  using Entry = clang::clangd::RefSlab::Builder::Entry;
173  static inline Entry getEmptyKey() {
174  static Entry E{clang::clangd::SymbolID(""), {}};
175  return E;
176  }
177  static inline Entry getTombstoneKey() {
178  static Entry E{clang::clangd::SymbolID("TOMBSTONE"), {}};
179  return E;
180  }
181  static unsigned getHashValue(const Entry &Val) {
182  return llvm::hash_combine(
183  Val.Symbol, reinterpret_cast<uintptr_t>(Val.Reference.Location.FileURI),
184  Val.Reference.Location.Start.rep(), Val.Reference.Location.End.rep());
185  }
186  static bool isEqual(const Entry &LHS, const Entry &RHS) {
187  return std::tie(LHS.Symbol, LHS.Reference.Location.FileURI,
188  LHS.Reference.Kind) ==
189  std::tie(RHS.Symbol, RHS.Reference.Location.FileURI,
190  RHS.Reference.Kind) &&
191  LHS.Reference.Location.Start == RHS.Reference.Location.Start &&
192  LHS.Reference.Location.End == RHS.Reference.Location.End;
193  }
194 };
195 } // namespace llvm
196 
197 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H
clang::clangd::Ref::Kind
RefKind Kind
Definition: Ref.h:90
llvm
Some operations such as code completion produce a set of candidates.
Definition: YAMLGenerator.cpp:28
clang::clangd::SymbolLocation
Definition: SymbolLocation.h:19
SymbolID.h
E
const Expr * E
Definition: AvoidBindCheck.cpp:88
clang::clangd::RefKind::All
@ All
clang::clangd::RefKind::Unknown
@ Unknown
Refs
RefSlab Refs
Definition: SymbolCollectorTests.cpp:311
clang::clangd::RefKind::Declaration
@ Declaration
SymbolLocation.h
clang::clangd::RefSlab::Builder::Builder
Builder()
Definition: Ref.h:136
clang::clangd::RefSlab::RefSlab
RefSlab()=default
clang::clangd::RefKind
RefKind
Describes the kind of a cross-reference.
Definition: Ref.h:30
clang::clangd::RefSlab::end
const_iterator end() const
Definition: Ref.h:122
clang::clangd::RefSlab::Builder
RefSlab::Builder is a mutable container that can 'freeze' to RefSlab.
Definition: Ref.h:134
llvm::DenseMapInfo< clang::clangd::RefSlab::Builder::Entry >::getEmptyKey
static Entry getEmptyKey()
Definition: Ref.h:173
clang::clangd::RefSlab
An efficient structure of storing large set of symbol references in memory.
Definition: Ref.h:110
clang::clangd::operator&
DeclRelationSet operator&(DeclRelation L, DeclRelation R)
Definition: FindTarget.h:214
llvm::DenseMapInfo< clang::clangd::RefSlab::Builder::Entry >::isEqual
static bool isEqual(const Entry &LHS, const Entry &RHS)
Definition: Ref.h:186
clang::clangd::RefSlab::value_type
std::pair< SymbolID, llvm::ArrayRef< Ref > > value_type
Definition: Ref.h:113
clang::clangd::RefSlab::numRefs
size_t numRefs() const
Definition: Ref.h:125
ns1::ns2::A
@ A
Definition: CategoricalFeature.h:3
llvm::DenseMapInfo< clang::clangd::RefSlab::Builder::Entry >::Entry
clang::clangd::RefSlab::Builder::Entry Entry
Definition: Ref.h:172
clang::clangd::Ref::Container
SymbolID Container
The ID of the symbol whose definition contains this reference.
Definition: Ref.h:94
clang::clangd::Ref::Location
SymbolLocation Location
The source location where the symbol is named.
Definition: Ref.h:89
clang::clangd::operator|=
IncludeGraphNode::SourceFlag & operator|=(IncludeGraphNode::SourceFlag &A, IncludeGraphNode::SourceFlag B)
Definition: Headers.h:100
clang::clangd::Symbol
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
clang::clangd::RefKind::Reference
@ Reference
clang::clangd::RefSlab::Builder::build
RefSlab build() &&
Consumes the builder to finalize the slab.
Definition: Ref.cpp:42
clang::clangd::RefSlab::Builder::insert
void insert(const SymbolID &ID, const Ref &S)
Adds a ref to the slab. Deep copy: Strings will be owned by the slab.
Definition: Ref.cpp:36
clang::doc::SymbolID
std::array< uint8_t, 20 > SymbolID
Definition: Representation.h:30
clang::clangd::operator<<
llvm::raw_ostream & operator<<(llvm::raw_ostream &OS, const CodeCompletion &C)
Definition: CodeComplete.cpp:2013
llvm::DenseMapInfo< clang::clangd::RefSlab::Builder::Entry >::getHashValue
static unsigned getHashValue(const Entry &Val)
Definition: Ref.h:181
Entry
Definition: Modularize.cpp:428
clang::clangd::RefSlab::const_iterator
std::vector< value_type >::const_iterator const_iterator
Definition: Ref.h:114
clang::clangd::RefSlab::empty
bool empty() const
Definition: Ref.h:126
clang::clangd::RefKind::Spelled
@ Spelled
ID
static char ID
Definition: Logger.cpp:74
clang::clangd::Ref
Represents a symbol occurrence in the source file.
Definition: Ref.h:87
clang::clangd::RefSlab::begin
const_iterator begin() const
Definition: Ref.h:121
clang::clangd::RefSlab::iterator
const_iterator iterator
Definition: Ref.h:115
clang::clangd::operator|
DeclRelationSet operator|(DeclRelation L, DeclRelation R)
Definition: FindTarget.h:211
clang::clangd::RefSlab::operator=
RefSlab & operator=(RefSlab &&RHS)=default
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
Arena
llvm::BumpPtrAllocator Arena
Definition: Serialization.cpp:211
clang::clangd::operator<
bool operator<(const Ref &L, const Ref &R)
Definition: Ref.h:97
clang::clangd::RefSlab::size
size_t size() const
Gets the number of symbols.
Definition: Ref.h:124
clang::clangd::operator==
bool operator==(const Inclusion &LHS, const Inclusion &RHS)
Definition: Headers.cpp:273
ns1::ns2::B
@ B
Definition: CategoricalFeature.h:3
clang::clangd::SymbolID
Definition: SymbolID.h:32
clang::clangd::RefKind::Definition
@ Definition
llvm::DenseMapInfo< clang::clangd::RefSlab::Builder::Entry >::getTombstoneKey
static Entry getTombstoneKey()
Definition: Ref.h:177
clang::clangd::RefSlab::bytes
size_t bytes() const
Definition: Ref.h:128