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   All = Declaration | Definition | Reference | Spelled,
  67 };
  68
  69 inline RefKind operator|(RefKind L, RefKind R) {
  70   return static_cast<RefKind>(static_cast<uint8_t>(L) |
  71                               static_cast<uint8_t>(R));
  72 }
  73 inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; }
  74 inline RefKind operator&(RefKind A, RefKind B) {
  75   return static_cast<RefKind>(static_cast<uint8_t>(A) &
  76                               static_cast<uint8_t>(B));
  77 }
  78
  79 llvm::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.
  85 struct 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
  95 inline bool operator<(const Ref &L, const Ref &R) {
  96   return std::tie(L.Location, L.Kind, L.Container) <
  97          std::tie(R.Location, R.Kind, R.Container);
  98 }
  99 inline bool operator==(const Ref &L, const Ref &R) {
 100   return std::tie(L.Location, L.Kind, L.Container) ==
 101          std::tie(R.Location, R.Kind, R.Container);
 102 }
 103
 104 llvm::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.
 108 class RefSlab {
 109 public:
 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
 154 private:
 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
 168 namespace llvm {
 169 template <> struct DenseMapInfo<clang::clangd::RefSlab::Builder::Entry> {
 170   using Entry = clang::clangd::RefSlab::Builder::Entry;
 171   static inline Entry getEmptyKey() {
 172     static Entry E{clang::clangd::SymbolID(""), {}};
 173     return E;
 174   }
 175   static inline Entry getTombstoneKey() {
 176     static Entry E{clang::clangd::SymbolID("TOMBSTONE"), {}};
 177     return E;
 178   }
 179   static unsigned getHashValue(const Entry &Val) {
 180     return llvm::hash_combine(
 181         Val.Symbol, reinterpret_cast<uintptr_t>(Val.Reference.Location.FileURI),
 182         Val.Reference.Location.Start.rep(), Val.Reference.Location.End.rep());
 183   }
 184   static bool isEqual(const Entry &LHS, const Entry &RHS) {
 185     return std::tie(LHS.Symbol, LHS.Reference.Location.FileURI,
 186                     LHS.Reference.Kind) ==
 187                std::tie(RHS.Symbol, RHS.Reference.Location.FileURI,
 188                         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