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

   1 //===--- SymbolID.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_SYMBOLID_H
  10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOLID_H
  11
  12 #include "llvm/ADT/Hashing.h"
  13 #include "llvm/ADT/StringRef.h"
  14 #include "llvm/Support/Error.h"
  15 #include "llvm/Support/raw_ostream.h"
  16 #include <array>
  17 #include <cstddef>
  18 #include <cstdint>
  19 #include <string>
  20
  21 namespace clang {
  22 namespace clangd {
  23
  24 // The class identifies a particular C++ symbol (class, function, method, etc).
  25 //
  26 // As USRs (Unified Symbol Resolution) could be large, especially for functions
  27 // with long type arguments, SymbolID is using truncated SHA1(USR) values to
  28 // guarantee the uniqueness of symbols while using a relatively small amount of
  29 // memory (vs storing USRs directly).
  30 //
  31 // SymbolID can be used as key in the symbol indexes to lookup the symbol.
  32 class SymbolID {
  33 public:
  34   SymbolID() = default;
  35   explicit SymbolID(llvm::StringRef USR);
  36
  37   bool operator==(const SymbolID &Sym) const {
  38     return HashValue == Sym.HashValue;
  39   }
  40   bool operator!=(const SymbolID &Sym) const { return !(*this == Sym); }
  41   bool operator<(const SymbolID &Sym) const {
  42     // Avoid lexicographic compare which requires swapping bytes or even memcmp!
  43     return llvm::bit_cast<IntTy>(HashValue) <
  44            llvm::bit_cast<IntTy>(Sym.HashValue);
  45   }
  46
  47   // The stored hash is truncated to RawSize bytes.
  48   // This trades off memory against the number of symbols we can handle.
  49   constexpr static size_t RawSize = 8;
  50   llvm::StringRef raw() const;
  51   static SymbolID fromRaw(llvm::StringRef);
  52
  53   // Returns a hex encoded string.
  54   std::string str() const;
  55   static llvm::Expected<SymbolID> fromStr(llvm::StringRef);
  56
  57   bool isNull() const { return *this == SymbolID(); }
  58   explicit operator bool() const { return !isNull(); }
  59
  60 private:
  61   using IntTy = uint64_t;
  62   static_assert(sizeof(IntTy) == RawSize);
  63   std::array<uint8_t, RawSize> HashValue{};
  64 };
  65
  66 inline llvm::hash_code hash_value(const SymbolID &ID) {
  67   // We already have a good hash, just return the first bytes.
  68   static_assert(sizeof(size_t) <= SymbolID::RawSize,
  69                 "size_t longer than SHA1!");
  70   size_t Result;
  71   memcpy(&Result, ID.raw().data(), sizeof(size_t));
  72   return llvm::hash_code(Result);
  73 }
  74
  75 // Write SymbolID into the given stream. SymbolID is encoded as ID.str().
  76 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolID &ID);
  77
  78 } // namespace clangd
  79 } // namespace clang
  80
  81 namespace llvm {
  82 // Support SymbolIDs as DenseMap keys.
  83 template <> struct DenseMapInfo<clang::clangd::SymbolID> {
  84   static inline clang::clangd::SymbolID getEmptyKey() {
  85     static clang::clangd::SymbolID EmptyKey("EMPTYKEY");
  86     return EmptyKey;
  87   }
  88   static inline clang::clangd::SymbolID getTombstoneKey() {
  89     static clang::clangd::SymbolID TombstoneKey("TOMBSTONEKEY");
  90     return TombstoneKey;
  91   }
  92   static unsigned getHashValue(const clang::clangd::SymbolID &Sym) {
  93     return hash_value(Sym);
  94   }
  95   static bool isEqual(const clang::clangd::SymbolID &LHS,
  96                       const clang::clangd::SymbolID &RHS) {
  97     return LHS == RHS;
  98   }
  99 };
 100 } // namespace llvm
 101
 102 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOLID_H