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