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"
13#include "index/SymbolLocation.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,
66 All = Declaration | Definition | Reference | Spelled,
67};
68
69inline RefKind operator|(RefKind L, RefKind R) {
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; }
74inline RefKind operator&(RefKind A, RefKind B) {
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.
87 SymbolLocation Location;
88 RefKind Kind = RefKind::Unknown;
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().
92 SymbolID Container;
93};
94
95inline bool operator<(const Ref &L, const Ref &R) {
96 return std::tie(args: L.Location, args: L.Kind, args: L.Container) <
97 std::tie(args: R.Location, args: R.Kind, args: R.Container);
98}
99inline bool operator==(const Ref &L, const Ref &R) {
100 return std::tie(args: L.Location, args: L.Kind, args: L.Container) ==
101 std::tie(args: R.Location, args: R.Kind, args: 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;
113 using iterator = 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.
138 RefSlab build() &&;
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 {
144 SymbolID Symbol;
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{.Symbol: clang::clangd::SymbolID(""), .Reference: {}};
173 return E;
174 }
175 static inline Entry getTombstoneKey() {
176 static Entry E{.Symbol: clang::clangd::SymbolID("TOMBSTONE"), .Reference: {}};
177 return E;
178 }
179 static unsigned getHashValue(const Entry &Val) {
180 return llvm::hash_combine(
181 args: Val.Symbol, args: reinterpret_cast<uintptr_t>(Val.Reference.Location.FileURI),
182 args: Val.Reference.Location.Start.rep(), args: Val.Reference.Location.End.rep());
183 }
184 static bool isEqual(const Entry &LHS, const Entry &RHS) {
185 return std::tie(args: LHS.Symbol, args: LHS.Reference.Location.FileURI,
186 args: LHS.Reference.Kind) ==
187 std::tie(args: RHS.Symbol, args: RHS.Reference.Location.FileURI,
188 args: 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
196

source code of clang-tools-extra/clangd/index/Ref.h