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