1//===- DWARFLinkerDeclContext.cpp -----------------------------------------===//
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#include "llvm/DWARFLinker/Classic/DWARFLinkerDeclContext.h"
10#include "llvm/DWARFLinker/Classic/DWARFLinkerCompileUnit.h"
11#include "llvm/DWARFLinker/Utils.h"
12#include "llvm/DebugInfo/DWARF/DWARFContext.h"
13#include "llvm/DebugInfo/DWARF/DWARFDie.h"
14#include "llvm/DebugInfo/DWARF/DWARFTypePrinter.h"
15#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
16#include "llvm/Support/raw_ostream.h"
17
18namespace llvm {
19
20static std::optional<std::string>
21makeSimpleTemplateNameWithParams(StringRef Name, const DWARFDie &DIE) {
22 std::string Result = Name.str();
23 raw_string_ostream OS(Result);
24 DWARFTypePrinter<DWARFDie> Printer(OS);
25 Printer.appendAndTerminateTemplateParameters(D: DIE);
26 if (Result == Name)
27 return std::nullopt;
28 return Result;
29}
30
31/// Bounds walks along DW_AT_type, which malformed input can make cyclic.
32static constexpr unsigned MaxTypeReferenceDepth = 256;
33
34static void appendUnnamedTypeContents(const DWARFDie &DIE, raw_ostream &OS,
35 unsigned Depth);
36
37/// Appends the type \p DIE refers to, through unnamed types up to a named one.
38static void appendUnqualifiedTypeName(DWARFDie DIE, raw_ostream &OS,
39 unsigned Depth) {
40 for (; Depth < MaxTypeReferenceDepth; ++Depth) {
41 DWARFDie Type = DIE.getAttributeValueAsReferencedDie(Attr: dwarf::DW_AT_type);
42 if (!Type)
43 return;
44 OS << '\0' << dwarf::TagString(Tag: Type.getTag());
45 if (const char *Name = Type.getShortName()) {
46 OS << '\0' << Name;
47 return;
48 }
49 appendUnnamedTypeContents(DIE: Type, OS, Depth: Depth + 1);
50 DIE = Type;
51 }
52}
53
54static void appendUnnamedTypeContents(const DWARFDie &DIE, raw_ostream &OS,
55 unsigned Depth) {
56 if (!dwarf_linker::isIdentifiedByChildren(Tag: DIE.getTag()))
57 return;
58
59 OS << '\0' << '(';
60 for (const DWARFDie &Child : DIE.children()) {
61 if (!dwarf_linker::isIdentifyingChild(Die: Child))
62 continue;
63
64 OS << '\0' << dwarf::TagString(Tag: Child.getTag());
65 if (const char *Name = Child.getShortName())
66 OS << '\0' << Name;
67 appendUnqualifiedTypeName(DIE: Child, OS, Depth);
68 }
69 OS << '\0' << ')';
70}
71
72using namespace dwarf_linker;
73using namespace dwarf_linker::classic;
74
75/// Set the last DIE/CU a context was seen in and, possibly invalidate the
76/// context if it is ambiguous.
77///
78/// In the current implementation, we don't handle overloaded functions well,
79/// because the argument types are not taken into account when computing the
80/// DeclContext tree.
81///
82/// Some of this is mitigated byt using mangled names that do contain the
83/// arguments types, but sometimes (e.g. with function templates) we don't have
84/// that. In that case, just do not unique anything that refers to the contexts
85/// we are not able to distinguish.
86///
87/// If a context that is not a namespace appears twice in the same CU, we know
88/// it is ambiguous. Make it invalid.
89bool DeclContext::setLastSeenDIE(CompileUnit &U, const DWARFDie &Die) {
90 if (LastSeenCompileUnitID == U.getUniqueID()) {
91 DWARFUnit &OrigUnit = U.getOrigUnit();
92 uint32_t FirstIdx = OrigUnit.getDIEIndex(D: LastSeenDIE);
93 U.getInfo(Idx: FirstIdx).Ctxt = nullptr;
94 return false;
95 }
96
97 LastSeenCompileUnitID = U.getUniqueID();
98 LastSeenDIE = Die;
99 return true;
100}
101
102PointerIntPair<DeclContext *, 1>
103DeclContextTree::getChildDeclContext(DeclContext &Context, const DWARFDie &DIE,
104 CompileUnit &U, bool InClangModule) {
105 unsigned Tag = DIE.getTag();
106
107 // FIXME: dsymutil-classic compat: We should bail out here if we
108 // have a specification or an abstract_origin. We will get the
109 // parent context wrong here.
110
111 switch (Tag) {
112 default:
113 // By default stop gathering child contexts.
114 return PointerIntPair<DeclContext *, 1>(nullptr);
115 case dwarf::DW_TAG_module:
116 break;
117 case dwarf::DW_TAG_compile_unit:
118 return PointerIntPair<DeclContext *, 1>(&Context);
119 case dwarf::DW_TAG_subprogram:
120 // Do not unique anything inside CU local functions.
121 if ((Context.getTag() == dwarf::DW_TAG_namespace ||
122 Context.getTag() == dwarf::DW_TAG_compile_unit) &&
123 !dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_external), Default: 0))
124 return PointerIntPair<DeclContext *, 1>(nullptr);
125 [[fallthrough]];
126 case dwarf::DW_TAG_member:
127 case dwarf::DW_TAG_namespace:
128 case dwarf::DW_TAG_structure_type:
129 case dwarf::DW_TAG_class_type:
130 case dwarf::DW_TAG_union_type:
131 case dwarf::DW_TAG_enumeration_type:
132 case dwarf::DW_TAG_typedef:
133 // Artificial things might be ambiguous, because they might be created on
134 // demand. For example implicitly defined constructors are ambiguous
135 // because of the way we identify contexts, and they won't be generated
136 // every time everywhere.
137 if (dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_artificial), Default: 0))
138 return PointerIntPair<DeclContext *, 1>(nullptr);
139 break;
140 }
141
142 StringRef Name = DIE.getShortName();
143 StringRef NameForUniquing;
144 StringRef FileRef;
145
146 if (const char *LinkageName = DIE.getLinkageName()) {
147 NameForUniquing = StringPool.internString(S: LinkageName);
148 } else if (!Name.empty()) {
149 // With -gsimple-template-names, DW_AT_name omits template parameters
150 // ("vector" instead of "vector<int>"). Reconstruct them from child
151 // DW_TAG_template_*_parameter DIEs so different specializations get
152 // distinct uniquing names.
153 bool HasTemplateParamsInName =
154 Name.ends_with(Suffix: ">") && !Name.ends_with(Suffix: "<=>") && Name.contains(C: '<');
155 std::optional<std::string> FullName;
156 if (!HasTemplateParamsInName)
157 FullName = makeSimpleTemplateNameWithParams(Name, DIE);
158 NameForUniquing = StringPool.internString(S: FullName ? *FullName : Name);
159 }
160
161 // For typedefs, include the referenced type chain in the uniquing key. Two
162 // typedefs with the same name (e.g. from preferred_name) but different
163 // DW_AT_type targets must get different DeclContexts, otherwise ODR
164 // deduplication can create self-referencing typedef cycles in the output
165 // DWARF. Walk through unnamed wrapper types (pointers, references, const,
166 // etc.) to find a named type for disambiguation. This mirrors the parallel
167 // linker's behavior in SyntheticTypeNameBuilder::addTypeName.
168 if (Tag == dwarf::DW_TAG_typedef && !NameForUniquing.empty()) {
169 SmallString<128> Combined(NameForUniquing);
170 DWARFDie CurDie = DIE;
171 // Guard against malformed input DWARF with cycles in DW_AT_type references;
172 // the parallel linker uses a similar guard in addReferencedODRDies.
173 for (unsigned Depth = 0; Depth < MaxTypeReferenceDepth; ++Depth) {
174 auto TypeAttr = CurDie.find(Attr: dwarf::DW_AT_type);
175 if (!TypeAttr)
176 break;
177 auto RefDie = CurDie.getAttributeValueAsReferencedDie(V: *TypeAttr);
178 if (!RefDie)
179 break;
180 // Use null bytes as separators since they cannot appear in type names
181 // or tag strings, preventing accidental collisions.
182 Combined.push_back(Elt: '\0');
183 Combined.append(RHS: dwarf::TagString(Tag: RefDie.getTag()));
184 StringRef RefName = RefDie.getShortName();
185 if (!RefName.empty()) {
186 Combined.push_back(Elt: '\0');
187 Combined.append(RHS: RefName);
188 break;
189 }
190 CurDie = RefDie;
191 }
192 if (Combined.size() != NameForUniquing.size())
193 NameForUniquing = StringPool.internString(S: Combined);
194 }
195
196 bool IsAnonymousNamespace =
197 NameForUniquing.empty() && Tag == dwarf::DW_TAG_namespace;
198 if (IsAnonymousNamespace) {
199 // FIXME: For dsymutil-classic compatibility. I think uniquing within
200 // anonymous namespaces is wrong. There is no ODR guarantee there.
201 NameForUniquing = "(anonymous namespace)";
202 }
203
204 if (Tag != dwarf::DW_TAG_class_type && Tag != dwarf::DW_TAG_structure_type &&
205 Tag != dwarf::DW_TAG_union_type &&
206 Tag != dwarf::DW_TAG_enumeration_type && NameForUniquing.empty())
207 return PointerIntPair<DeclContext *, 1>(nullptr);
208
209 unsigned Line = 0;
210 unsigned ByteSize = std::numeric_limits<uint32_t>::max();
211
212 if (!InClangModule) {
213 // Gather some discriminating data about the DeclContext we will be
214 // creating: File, line number and byte size. This shouldn't be necessary,
215 // because the ODR is just about names, but given that we do some
216 // approximations with overloaded functions and anonymous namespaces, use
217 // these additional data points to make the process safer.
218 //
219 // This is disabled for clang modules, because forward declarations of
220 // module-defined types do not have a file and line.
221 ByteSize = dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_byte_size),
222 Default: std::numeric_limits<uint64_t>::max());
223 if (Tag != dwarf::DW_TAG_namespace || IsAnonymousNamespace) {
224 if (unsigned FileNum =
225 dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_decl_file), Default: 0)) {
226 if (const auto *LT = U.getOrigUnit().getContext().getLineTableForUnit(
227 U: &U.getOrigUnit())) {
228 // FIXME: dsymutil-classic compatibility. I'd rather not
229 // unique anything in anonymous namespaces, but if we do, then
230 // verify that the file and line correspond.
231 if (IsAnonymousNamespace)
232 FileNum = 1;
233
234 if (LT->hasFileAtIndex(FileIndex: FileNum)) {
235 Line = dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_decl_line), Default: 0);
236 // Cache the resolved paths based on the index in the line table,
237 // because calling realpath is expensive.
238 FileRef = getResolvedPath(CU&: U, FileNum, LineTable: *LT);
239 }
240 }
241 }
242 }
243 }
244
245 // Unnamed types declared on one line differ only in their contents.
246 if (NameForUniquing.empty() && Line) {
247 SmallString<128> Contents;
248 raw_svector_ostream OS(Contents);
249 appendUnnamedTypeContents(DIE, OS, /*Depth=*/0);
250 NameForUniquing = StringPool.internString(S: Contents);
251 }
252
253 if (!Line && NameForUniquing.empty())
254 return PointerIntPair<DeclContext *, 1>(nullptr);
255
256 // We hash NameForUniquing, which is the mangled name, in order to get most
257 // overloaded functions resolve correctly.
258 //
259 // Strictly speaking, hashing the Tag is only necessary for a
260 // DW_TAG_module, to prevent uniquing of a module and a namespace
261 // with the same name.
262 //
263 // FIXME: dsymutil-classic won't unique the same type presented
264 // once as a struct and once as a class. Using the Tag in the fully
265 // qualified name hash to get the same effect.
266 unsigned Hash =
267 hash_combine(args: Context.getQualifiedNameHash(), args: Tag, args: NameForUniquing);
268
269 // FIXME: dsymutil-classic compatibility: when we don't have a name,
270 // use the filename.
271 if (IsAnonymousNamespace)
272 Hash = hash_combine(args: Hash, args: FileRef);
273
274 // Now look if this context already exists.
275 DeclContext Key(Hash, Line, ByteSize, Tag, Name, NameForUniquing, FileRef,
276 Context);
277 auto ContextIter = Contexts.find(V: &Key);
278
279 if (ContextIter == Contexts.end()) {
280 // The context wasn't found.
281 bool Inserted;
282 DeclContext *NewContext = new (Allocator)
283 DeclContext(Hash, Line, ByteSize, Tag, Name, NameForUniquing, FileRef,
284 Context, DIE, U.getUniqueID());
285 std::tie(args&: ContextIter, args&: Inserted) = Contexts.insert(V: NewContext);
286 assert(Inserted && "Failed to insert DeclContext");
287 (void)Inserted;
288 } else if (Tag != dwarf::DW_TAG_namespace &&
289 !(*ContextIter)->setLastSeenDIE(U, Die: DIE)) {
290 // The context was found, but it is ambiguous with another context
291 // in the same file. Mark it invalid.
292 return PointerIntPair<DeclContext *, 1>(*ContextIter, /* IntVal= */ 1);
293 }
294
295 assert(ContextIter != Contexts.end());
296 // FIXME: dsymutil-classic compatibility. Union types aren't
297 // uniques, but their children might be.
298 if ((Tag == dwarf::DW_TAG_subprogram &&
299 Context.getTag() != dwarf::DW_TAG_structure_type &&
300 Context.getTag() != dwarf::DW_TAG_class_type) ||
301 (Tag == dwarf::DW_TAG_union_type))
302 return PointerIntPair<DeclContext *, 1>(*ContextIter, /* IntVal= */ 1);
303
304 return PointerIntPair<DeclContext *, 1>(*ContextIter);
305}
306
307StringRef
308DeclContextTree::getResolvedPath(CompileUnit &CU, unsigned FileNum,
309 const DWARFDebugLine::LineTable &LineTable) {
310 std::pair<unsigned, unsigned> Key = {CU.getUniqueID(), FileNum};
311
312 ResolvedPathsMap::const_iterator It = ResolvedPaths.find(Val: Key);
313 if (It == ResolvedPaths.end()) {
314 std::string FileName;
315 bool FoundFileName = LineTable.getFileNameByIndex(
316 FileIndex: FileNum, CompDir: CU.getOrigUnit().getCompilationDir(),
317 Kind: DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, Result&: FileName);
318 (void)FoundFileName;
319 assert(FoundFileName && "Must get file name from line table");
320
321 // Second level of caching, this time based on the file's parent
322 // path.
323 StringRef ResolvedPath = PathResolver.resolve(Path: FileName, StringPool);
324
325 It = ResolvedPaths.insert(KV: std::make_pair(x&: Key, y&: ResolvedPath)).first;
326 }
327
328 return It->second;
329}
330
331} // namespace llvm
332