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