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, 68 All = Declaration | Definition | Reference | Spelled, 69 }; 70 71 inline RefKind operator|(RefKind L, RefKind R) { 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; } 76 inline RefKind operator&(RefKind A, RefKind B) { 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. 89 SymbolLocation Location; 90 RefKind Kind = RefKind::Unknown; 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(). 94 SymbolID Container; 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; 115 using iterator = const_iterator; 116 117 RefSlab() = default; 118 RefSlab(RefSlab &&Slab) = default; 119 RefSlab &operator=(RefSlab &&RHS) = default; 120 begin()121 const_iterator begin() const { return Refs.begin(); } end()122 const_iterator end() const { return Refs.end(); } 123 /// Gets the number of symbols. size()124 size_t size() const { return Refs.size(); } numRefs()125 size_t numRefs() const { return NumRefs; } empty()126 bool empty() const { return Refs.empty(); } 127 bytes()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: Builder()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 { 146 SymbolID Symbol; 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 198