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 // A reference which is a call. Used as a filter for which references
67 // to store in data structures used for computing outgoing calls.
68 Call = 1 << 4,
69 All = Declaration | Definition | Reference | Spelled,
70};
71
72inline RefKind operator|(RefKind L, RefKind R) {
73 return static_cast<RefKind>(static_cast<uint8_t>(L) |
74 static_cast<uint8_t>(R));
75}
76inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; }
77inline RefKind operator&(RefKind A, RefKind B) {
78 return static_cast<RefKind>(static_cast<uint8_t>(A) &
79 static_cast<uint8_t>(B));
80}
81
82llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefKind);
83
84/// Represents a symbol occurrence in the source file.
85/// Despite the name, it could be a declaration/definition/reference.
86///
87/// WARNING: Location does not own the underlying data - Copies are shallow.
88struct Ref {
89 /// The source location where the symbol is named.
90 SymbolLocation Location;
91 RefKind Kind = RefKind::Unknown;
92 /// The ID of the symbol whose definition contains this reference.
93 /// For example, for a reference inside a function body, this would
94 /// be that function. For top-level definitions this isNull().
95 SymbolID Container;
96};
97
98inline bool operator<(const Ref &L, const Ref &R) {
99 return std::tie(args: L.Location, args: L.Kind, args: L.Container) <
100 std::tie(args: R.Location, args: R.Kind, args: R.Container);
101}
102inline bool operator==(const Ref &L, const Ref &R) {
103 return std::tie(args: L.Location, args: L.Kind, args: L.Container) ==
104 std::tie(args: R.Location, args: R.Kind, args: R.Container);
105}
106
107llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Ref &);
108
109/// An efficient structure of storing large set of symbol references in memory.
110/// Filenames are deduplicated.
111class RefSlab {
112public:
113 // Refs are stored in order.
114 using value_type = std::pair<SymbolID, llvm::ArrayRef<Ref>>;
115 using const_iterator = std::vector<value_type>::const_iterator;
116 using iterator = const_iterator;
117
118 RefSlab() = default;
119 RefSlab(RefSlab &&Slab) = default;
120 RefSlab &operator=(RefSlab &&RHS) = default;
121
122 const_iterator begin() const { return Refs.begin(); }
123 const_iterator end() const { return Refs.end(); }
124 /// Gets the number of symbols.
125 size_t size() const { return Refs.size(); }
126 size_t numRefs() const { return NumRefs; }
127 bool empty() const { return Refs.empty(); }
128
129 size_t bytes() const {
130 return sizeof(*this) + Arena.getTotalMemory() +
131 sizeof(value_type) * Refs.capacity();
132 }
133
134 /// RefSlab::Builder is a mutable container that can 'freeze' to RefSlab.
135 class Builder {
136 public:
137 Builder() : UniqueStrings(Arena) {}
138 /// Adds a ref to the slab. Deep copy: Strings will be owned by the slab.
139 void insert(const SymbolID &ID, const Ref &S);
140 /// Consumes the builder to finalize the slab.
141 RefSlab build() &&;
142
143 private:
144 // A ref we're storing with its symbol to consume with build().
145 // All strings are interned, so DenseMapInfo can use pointer comparisons.
146 struct Entry {
147 SymbolID Symbol;
148 Ref Reference;
149 };
150 friend struct llvm::DenseMapInfo<Entry>;
151
152 llvm::BumpPtrAllocator Arena;
153 llvm::UniqueStringSaver UniqueStrings; // Contents on the arena.
154 llvm::DenseSet<Entry> Entries;
155 };
156
157private:
158 RefSlab(std::vector<value_type> Refs, llvm::BumpPtrAllocator Arena,
159 size_t NumRefs)
160 : Arena(std::move(Arena)), Refs(std::move(Refs)), NumRefs(NumRefs) {}
161
162 llvm::BumpPtrAllocator Arena;
163 std::vector<value_type> Refs;
164 /// Number of all references.
165 size_t NumRefs = 0;
166};
167
168} // namespace clangd
169} // namespace clang
170
171namespace llvm {
172template <> struct DenseMapInfo<clang::clangd::RefSlab::Builder::Entry> {
173 using Entry = clang::clangd::RefSlab::Builder::Entry;
174 static inline Entry getEmptyKey() {
175 static Entry E{.Symbol: clang::clangd::SymbolID(""), .Reference: {}};
176 return E;
177 }
178 static inline Entry getTombstoneKey() {
179 static Entry E{.Symbol: clang::clangd::SymbolID("TOMBSTONE"), .Reference: {}};
180 return E;
181 }
182 static unsigned getHashValue(const Entry &Val) {
183 return llvm::hash_combine(
184 args: Val.Symbol, args: reinterpret_cast<uintptr_t>(Val.Reference.Location.FileURI),
185 args: Val.Reference.Location.Start.rep(), args: Val.Reference.Location.End.rep());
186 }
187 static bool isEqual(const Entry &LHS, const Entry &RHS) {
188 return std::tie(args: LHS.Symbol, args: LHS.Reference.Location.FileURI,
189 args: LHS.Reference.Kind) ==
190 std::tie(args: RHS.Symbol, args: RHS.Reference.Location.FileURI,
191 args: RHS.Reference.Kind) &&
192 LHS.Reference.Location.Start == RHS.Reference.Location.Start &&
193 LHS.Reference.Location.End == RHS.Reference.Location.End;
194 }
195};
196} // namespace llvm
197
198#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H
199

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