text: //===--- Ref.h ---------------------------------------------------*- C++-*-===//
  //
  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  // See https://llvm.org/LICENSE.txt for license information.
  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  //
  //===----------------------------------------------------------------------===//
  
  #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H
  #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H
  
  #include "SymbolID.h"
  #include "SymbolLocation.h"
  #include "clang/Index/IndexSymbol.h"
  #include "llvm/ADT/DenseMap.h"
  #include "llvm/ADT/Hashing.h"
  #include "llvm/Support/Allocator.h"
  #include "llvm/Support/StringSaver.h"
  #include "llvm/Support/raw_ostream.h"
  #include <cstdint>
  #include <set>
  #include <utility>
  
  namespace clang {
  namespace clangd {
  
  /// Describes the kind of a cross-reference.
  ///
  /// This is a bitfield which can be combined from different kinds.
  enum class RefKind : uint8_t {
    Unknown = 0,
    // Points to symbol declaration. Example:
    //
    // class Foo;
    //       ^ Foo declaration
    // Foo foo;
    // ^ this does not reference Foo declaration
    Declaration = 1 << 0,
    // Points to symbol definition. Example:
    //
    // int foo();
    //     ^ references foo declaration, but not foo definition
    // int foo() { return 42; }
    //     ^ references foo definition, but not declaration
    // bool bar() { return true; }
    //      ^ references both definition and declaration
    Definition = 1 << 1,
    // Points to symbol reference. Example:
    //
    // int Foo = 42;
    // int Bar = Foo + 1;
    //           ^ this is a reference to Foo
    Reference = 1 << 2,
    // The reference explicitly spells out declaration's name. Such references can
    // not come from macro expansions or implicit AST nodes.
    //
    // class Foo { public: Foo() {} };
    //       ^ references declaration, definition and explicitly spells out name
    // #define MACRO Foo
    //     v there is an implicit constructor call here which is not a spelled ref
    // Foo foo;
    // ^ this reference explicitly spells out Foo's name
    // struct Bar {
    //   MACRO Internal;
    //   ^ this references Foo, but does not explicitly spell out its name
    // };
    Spelled = 1 << 3,
    All = Declaration | Definition | Reference | Spelled,
  };
  
  inline RefKind operator|(RefKind L, RefKind R) {
    return static_cast<RefKind>(static_cast<uint8_t>(L) |
                                static_cast<uint8_t>(R));
  }
  inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; }
  inline RefKind operator&(RefKind A, RefKind B) {
    return static_cast<RefKind>(static_cast<uint8_t>(A) &
                                static_cast<uint8_t>(B));
  }
  
  llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefKind);
  
  /// Represents a symbol occurrence in the source file.
  /// Despite the name, it could be a declaration/definition/reference.
  ///
  /// WARNING: Location does not own the underlying data - Copies are shallow.
  struct Ref {
    /// The source location where the symbol is named.
    SymbolLocation Location;
    RefKind Kind = RefKind::Unknown;
    /// The ID of the symbol whose definition contains this reference.
    /// For example, for a reference inside a function body, this would
    /// be that function. For top-level definitions this isNull().
    SymbolID Container;
  };
  
  inline bool operator<(const Ref &L, const Ref &R) {
    return std::tie(L.Location, L.Kind, L.Container) <
           std::tie(R.Location, R.Kind, R.Container);
  }
  inline bool operator==(const Ref &L, const Ref &R) {
    return std::tie(L.Location, L.Kind, L.Container) ==
           std::tie(R.Location, R.Kind, R.Container);
  }
  
  llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Ref &);
  
  /// An efficient structure of storing large set of symbol references in memory.
  /// Filenames are deduplicated.
  class RefSlab {
  public:
    // Refs are stored in order.
    using value_type = std::pair<SymbolID, llvm::ArrayRef<Ref>>;
    using const_iterator = std::vector<value_type>::const_iterator;
    using iterator = const_iterator;
  
    RefSlab() = default;
    RefSlab(RefSlab &&Slab) = default;
    RefSlab &operator=(RefSlab &&RHS) = default;
  
    const_iterator begin() const { return Refs.begin(); }
    const_iterator end() const { return Refs.end(); }
    /// Gets the number of symbols.
    size_t size() const { return Refs.size(); }
    size_t numRefs() const { return NumRefs; }
    bool empty() const { return Refs.empty(); }
  
    size_t bytes() const {
      return sizeof(*this) + Arena.getTotalMemory() +
             sizeof(value_type) * Refs.capacity();
    }
  
    /// RefSlab::Builder is a mutable container that can 'freeze' to RefSlab.
    class Builder {
    public:
      Builder() : UniqueStrings(Arena) {}
      /// Adds a ref to the slab. Deep copy: Strings will be owned by the slab.
      void insert(const SymbolID &ID, const Ref &S);
      /// Consumes the builder to finalize the slab.
      RefSlab build() &&;
  
    private:
      // A ref we're storing with its symbol to consume with build().
      // All strings are interned, so DenseMapInfo can use pointer comparisons.
      struct Entry {
        SymbolID Symbol;
        Ref Reference;
      };
      friend struct llvm::DenseMapInfo<Entry>;
  
      llvm::BumpPtrAllocator Arena;
      llvm::UniqueStringSaver UniqueStrings; // Contents on the arena.
      llvm::DenseSet<Entry> Entries;
    };
  
  private:
    RefSlab(std::vector<value_type> Refs, llvm::BumpPtrAllocator Arena,
            size_t NumRefs)
        : Arena(std::move(Arena)), Refs(std::move(Refs)), NumRefs(NumRefs) {}
  
    llvm::BumpPtrAllocator Arena;
    std::vector<value_type> Refs;
    /// Number of all references.
    size_t NumRefs = 0;
  };
  
  } // namespace clangd
  } // namespace clang
  
  namespace llvm {
  template <> struct DenseMapInfo<clang::clangd::RefSlab::Builder::Entry> {
    using Entry = clang::clangd::RefSlab::Builder::Entry;
    static inline Entry getEmptyKey() {
      static Entry E{clang::clangd::SymbolID(""), {}};
      return E;
    }
    static inline Entry getTombstoneKey() {
      static Entry E{clang::clangd::SymbolID("TOMBSTONE"), {}};
      return E;
    }
    static unsigned getHashValue(const Entry &Val) {
      return llvm::hash_combine(
          Val.Symbol, reinterpret_cast<uintptr_t>(Val.Reference.Location.FileURI),
          Val.Reference.Location.Start.rep(), Val.Reference.Location.End.rep());
    }
    static bool isEqual(const Entry &LHS, const Entry &RHS) {
      return std::tie(LHS.Symbol, LHS.Reference.Location.FileURI,
                      LHS.Reference.Kind) ==
                 std::tie(RHS.Symbol, RHS.Reference.Location.FileURI,
                          RHS.Reference.Kind) &&
             LHS.Reference.Location.Start == RHS.Reference.Location.Start &&
             LHS.Reference.Location.End == RHS.Reference.Location.End;
    }
  };
  } // namespace llvm
  
  #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_REF_H
  