199 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H10#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H11 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 declaration34 // Foo foo;35 // ^ this does not reference Foo declaration36 Declaration = 1 << 0,37 // Points to symbol definition. Example:38 //39 // int foo();40 // ^ references foo declaration, but not foo definition41 // int foo() { return 42; }42 // ^ references foo definition, but not declaration43 // bool bar() { return true; }44 // ^ references both definition and declaration45 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 Foo51 Reference = 1 << 2,52 // The reference explicitly spells out declaration's name. Such references can53 // not come from macro expansions or implicit AST nodes.54 //55 // class Foo { public: Foo() {} };56 // ^ references declaration, definition and explicitly spells out name57 // #define MACRO Foo58 // v there is an implicit constructor call here which is not a spelled ref59 // Foo foo;60 // ^ this reference explicitly spells out Foo's name61 // struct Bar {62 // MACRO Internal;63 // ^ this references Foo, but does not explicitly spell out its name64 // };65 Spelled = 1 << 3,66 // A reference which is a call. Used as a filter for which references67 // 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 would94 /// 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(L.Location, L.Kind, L.Container) <100 std::tie(R.Location, R.Kind, R.Container);101}102inline bool operator==(const Ref &L, const Ref &R) {103 return std::tie(L.Location, L.Kind, L.Container) ==104 std::tie(R.Location, R.Kind, 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 clangd169} // namespace clang170 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{clang::clangd::SymbolID(""), {}};176 return E;177 }178 static inline Entry getTombstoneKey() {179 static Entry E{clang::clangd::SymbolID("TOMBSTONE"), {}};180 return E;181 }182 static unsigned getHashValue(const Entry &Val) {183 return llvm::hash_combine(184 Val.Symbol, reinterpret_cast<uintptr_t>(Val.Reference.Location.FileURI),185 Val.Reference.Location.Start.rep(), Val.Reference.Location.End.rep());186 }187 static bool isEqual(const Entry &LHS, const Entry &RHS) {188 return std::tie(LHS.Symbol, LHS.Reference.Location.FileURI,189 LHS.Reference.Kind) ==190 std::tie(RHS.Symbol, RHS.Reference.Location.FileURI,191 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 llvm197 198#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H199