clang-tools-extra/clangd/index/Ref.h

   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
  22 namespace clang {
  23 namespace clangd {
  24
  25 /// Describes the kind of a cross-reference.
  26 ///
  27 /// This is a bitfield which can be combined from different kinds.
  28 enum 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
  72 inline RefKind operator|(RefKind L, RefKind R) {
  73   return static_cast<RefKind>(static_cast<uint8_t>(L) |
  74                               static_cast<uint8_t>(R));
  75 }
  76 inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; }
  77 inline RefKind operator&(RefKind A, RefKind B) {
  78   return static_cast<RefKind>(static_cast<uint8_t>(A) &
  79                               static_cast<uint8_t>(B));
  80 }
  81
  82 llvm::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.
  88 struct 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
  98 inline 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 }
 102 inline 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
 107 llvm::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.
 111 class RefSlab {
 112 public:
 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
 157 private:
 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
 171 namespace llvm {
 172 template <> 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 llvm
 197
 198 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H