tools/dsymutil/DeclContext.h

   1 //===- tools/dsymutil/DeclContext.h - Dwarf debug info linker ---*- 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_TOOLS_DSYMUTIL_DECLCONTEXT_H
  10 #define LLVM_TOOLS_DSYMUTIL_DECLCONTEXT_H
  11
  12 #include "CompileUnit.h"
  13 #include "NonRelocatableStringpool.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/DenseMapInfo.h"
  16 #include "llvm/ADT/DenseSet.h"
  17 #include "llvm/ADT/StringRef.h"
  18 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
  19 #include "llvm/Support/Path.h"
  20
  21 namespace llvm {
  22 namespace dsymutil {
  23
  24 struct DeclMapInfo;
  25
  26 /// Small helper that resolves and caches file paths. This helps reduce the
  27 /// number of calls to realpath which is expensive. We assume the input are
  28 /// files, and cache the realpath of their parent. This way we can quickly
  29 /// resolve different files under the same path.
  30 class CachedPathResolver {
  31 public:
  32   /// Resolve a path by calling realpath and cache its result. The returned
  33   /// StringRef is interned in the given \p StringPool.
  34   StringRef resolve(std::string Path, NonRelocatableStringpool &StringPool) {
  35     StringRef FileName = sys::path::filename(Path);
  36     SmallString<256> ParentPath = sys::path::parent_path(Path);
  37
  38     // If the ParentPath has not yet been resolved, resolve and cache it for
  39     // future look-ups.
  40     if (!ResolvedPaths.count(ParentPath)) {
  41       SmallString<256> RealPath;
  42       sys::fs::real_path(ParentPath, RealPath);
  43       ResolvedPaths.insert({ParentPath, StringRef(RealPath).str()});
  44     }
  45
  46     // Join the file name again with the resolved path.
  47     SmallString<256> ResolvedPath(ResolvedPaths[ParentPath]);
  48     sys::path::append(ResolvedPath, FileName);
  49     return StringPool.internString(ResolvedPath);
  50   }
  51
  52 private:
  53   StringMap<std::string> ResolvedPaths;
  54 };
  55
  56 /// A DeclContext is a named program scope that is used for ODR uniquing of
  57 /// types.
  58 ///
  59 /// The set of DeclContext for the ODR-subject parts of a Dwarf link is
  60 /// expanded (and uniqued) with each new object file processed. We need to
  61 /// determine the context of each DIE in an linked object file to see if the
  62 /// corresponding type has already been emitted.
  63 ///
  64 /// The contexts are conceptually organized as a tree (eg. a function scope is
  65 /// contained in a namespace scope that contains other scopes), but
  66 /// storing/accessing them in an actual tree is too inefficient: we need to be
  67 /// able to very quickly query a context for a given child context by name.
  68 /// Storing a StringMap in each DeclContext would be too space inefficient.
  69 ///
  70 /// The solution here is to give each DeclContext a link to its parent (this
  71 /// allows to walk up the tree), but to query the existence of a specific
  72 /// DeclContext using a separate DenseMap keyed on the hash of the fully
  73 /// qualified name of the context.
  74 class DeclContext {
  75 public:
  76   using Map = DenseSet<DeclContext *, DeclMapInfo>;
  77
  78   DeclContext() : DefinedInClangModule(0), Parent(*this) {}
  79
  80   DeclContext(unsigned Hash, uint32_t Line, uint32_t ByteSize, uint16_t Tag,
  81               StringRef Name, StringRef File, const DeclContext &Parent,
  82               DWARFDie LastSeenDIE = DWARFDie(), unsigned CUId = 0)
  83       : QualifiedNameHash(Hash), Line(Line), ByteSize(ByteSize), Tag(Tag),
  84         DefinedInClangModule(0), Name(Name), File(File), Parent(Parent),
  85         LastSeenDIE(LastSeenDIE), LastSeenCompileUnitID(CUId) {}
  86
  87   uint32_t getQualifiedNameHash() const { return QualifiedNameHash; }
  88
  89   bool setLastSeenDIE(CompileUnit &U, const DWARFDie &Die);
  90
  91   uint32_t getCanonicalDIEOffset() const { return CanonicalDIEOffset; }
  92   void setCanonicalDIEOffset(uint32_t Offset) { CanonicalDIEOffset = Offset; }
  93
  94   bool isDefinedInClangModule() const { return DefinedInClangModule; }
  95   void setDefinedInClangModule(bool Val) { DefinedInClangModule = Val; }
  96
  97   uint16_t getTag() const { return Tag; }
  98   StringRef getName() const { return Name; }
  99
 100 private:
 101   friend DeclMapInfo;
 102
 103   unsigned QualifiedNameHash = 0;
 104   uint32_t Line = 0;
 105   uint32_t ByteSize = 0;
 106   uint16_t Tag = dwarf::DW_TAG_compile_unit;
 107   unsigned DefinedInClangModule : 1;
 108   StringRef Name;
 109   StringRef File;
 110   const DeclContext &Parent;
 111   DWARFDie LastSeenDIE;
 112   uint32_t LastSeenCompileUnitID = 0;
 113   uint32_t CanonicalDIEOffset = 0;
 114 };
 115
 116 /// This class gives a tree-like API to the DenseMap that stores the
 117 /// DeclContext objects. It holds the BumpPtrAllocator where these objects will
 118 /// be allocated.
 119 class DeclContextTree {
 120 public:
 121   /// Get the child of \a Context described by \a DIE in \a Unit. The
 122   /// required strings will be interned in \a StringPool.
 123   /// \returns The child DeclContext along with one bit that is set if
 124   /// this context is invalid.
 125   ///
 126   /// An invalid context means it shouldn't be considered for uniquing, but its
 127   /// not returning null, because some children of that context might be
 128   /// uniquing candidates.
 129   ///
 130   /// FIXME: The invalid bit along the return value is to emulate some
 131   /// dsymutil-classic functionality.
 132   PointerIntPair<DeclContext *, 1>
 133   getChildDeclContext(DeclContext &Context, const DWARFDie &DIE,
 134                       CompileUnit &Unit, UniquingStringPool &StringPool,
 135                       bool InClangModule);
 136
 137   DeclContext &getRoot() { return Root; }
 138
 139 private:
 140   BumpPtrAllocator Allocator;
 141   DeclContext Root;
 142   DeclContext::Map Contexts;
 143
 144   /// Cache resolved paths from the line table.
 145   CachedPathResolver PathResolver;
 146 };
 147
 148 /// Info type for the DenseMap storing the DeclContext pointers.
 149 struct DeclMapInfo : private DenseMapInfo<DeclContext *> {
 150   using DenseMapInfo<DeclContext *>::getEmptyKey;
 151   using DenseMapInfo<DeclContext *>::getTombstoneKey;
 152
 153   static unsigned getHashValue(const DeclContext *Ctxt) {
 154     return Ctxt->QualifiedNameHash;
 155   }
 156
 157   static bool isEqual(const DeclContext *LHS, const DeclContext *RHS) {
 158     if (RHS == getEmptyKey() || RHS == getTombstoneKey())
 159       return RHS == LHS;
 160     return LHS->QualifiedNameHash == RHS->QualifiedNameHash &&
 161            LHS->Line == RHS->Line && LHS->ByteSize == RHS->ByteSize &&
 162            LHS->Name.data() == RHS->Name.data() &&
 163            LHS->File.data() == RHS->File.data() &&
 164            LHS->Parent.QualifiedNameHash == RHS->Parent.QualifiedNameHash;
 165   }
 166 };
 167
 168 } // end namespace dsymutil
 169 } // end namespace llvm
 170
 171 #endif // LLVM_TOOLS_DSYMUTIL_DECLCONTEXT_H