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. This mirrors the parallel linker's behavior in
166 // SyntheticTypeNameBuilder::addTypeName.
167 if (Tag == dwarf::DW_TAG_typedef && !NameForUniquing.empty()) {
168 SmallString<128> Combined(NameForUniquing);
169 raw_svector_ostream OS(Combined);
170 appendUnqualifiedTypeName(DIE, OS, /*Depth=*/0);
171 if (Combined.size() != NameForUniquing.size())
172 NameForUniquing = StringPool.internString(S: Combined);
173 }
174
175 bool IsAnonymousNamespace =
176 NameForUniquing.empty() && Tag == dwarf::DW_TAG_namespace;
177 if (IsAnonymousNamespace) {
178 // FIXME: For dsymutil-classic compatibility. I think uniquing within
179 // anonymous namespaces is wrong. There is no ODR guarantee there.
180 NameForUniquing = "(anonymous namespace)";
181 }
182
183 if (Tag != dwarf::DW_TAG_class_type && Tag != dwarf::DW_TAG_structure_type &&
184 Tag != dwarf::DW_TAG_union_type &&
185 Tag != dwarf::DW_TAG_enumeration_type && NameForUniquing.empty())
186 return PointerIntPair<DeclContext *, 1>(nullptr);
187
188 unsigned Line = 0;
189 unsigned ByteSize = std::numeric_limits<uint32_t>::max();
190
191 if (!InClangModule) {
192 // Gather some discriminating data about the DeclContext we will be
193 // creating: File, line number and byte size. This shouldn't be necessary,
194 // because the ODR is just about names, but given that we do some
195 // approximations with overloaded functions and anonymous namespaces, use
196 // these additional data points to make the process safer.
197 //
198 // This is disabled for clang modules, because forward declarations of
199 // module-defined types do not have a file and line.
200 ByteSize = dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_byte_size),
201 Default: std::numeric_limits<uint64_t>::max());
202 if (Tag != dwarf::DW_TAG_namespace || IsAnonymousNamespace) {
203 if (unsigned FileNum =
204 dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_decl_file), Default: 0)) {
205 if (const auto *LT = U.getOrigUnit().getContext().getLineTableForUnit(
206 U: &U.getOrigUnit())) {
207 // FIXME: dsymutil-classic compatibility. I'd rather not
208 // unique anything in anonymous namespaces, but if we do, then
209 // verify that the file and line correspond.
210 if (IsAnonymousNamespace)
211 FileNum = 1;
212
213 if (LT->hasFileAtIndex(FileIndex: FileNum)) {
214 Line = dwarf::toUnsigned(V: DIE.find(Attr: dwarf::DW_AT_decl_line), Default: 0);
215 // Cache the resolved paths based on the index in the line table,
216 // because calling realpath is expensive.
217 FileRef = getResolvedPath(CU&: U, FileNum, LineTable: *LT);
218 }
219 }
220 }
221 }
222 }
223
224 // Unnamed types declared on one line differ only in their contents.
225 if (NameForUniquing.empty() && Line) {
226 SmallString<128> Contents;
227 raw_svector_ostream OS(Contents);
228 appendUnnamedTypeContents(DIE, OS, /*Depth=*/0);
229 NameForUniquing = StringPool.internString(S: Contents);
230 }
231
232 if (!Line && NameForUniquing.empty())
233 return PointerIntPair<DeclContext *, 1>(nullptr);
234
235 // We hash NameForUniquing, which is the mangled name, in order to get most
236 // overloaded functions resolve correctly.
237 //
238 // Strictly speaking, hashing the Tag is only necessary for a
239 // DW_TAG_module, to prevent uniquing of a module and a namespace
240 // with the same name.
241 //
242 // FIXME: dsymutil-classic won't unique the same type presented
243 // once as a struct and once as a class. Using the Tag in the fully
244 // qualified name hash to get the same effect.
245 unsigned Hash =
246 hash_combine(args: Context.getQualifiedNameHash(), args: Tag, args: NameForUniquing);
247
248 // FIXME: dsymutil-classic compatibility: when we don't have a name,
249 // use the filename.
250 if (IsAnonymousNamespace)
251 Hash = hash_combine(args: Hash, args: FileRef);
252
253 // Now look if this context already exists.
254 DeclContext Key(Hash, Line, ByteSize, Tag, Name, NameForUniquing, FileRef,
255 Context);
256 auto ContextIter = Contexts.find(V: &Key);
257
258 if (ContextIter == Contexts.end()) {
259 // The context wasn't found.
260 bool Inserted;
261 DeclContext *NewContext = new (Allocator)
262 DeclContext(Hash, Line, ByteSize, Tag, Name, NameForUniquing, FileRef,
263 Context, DIE, U.getUniqueID());
264 std::tie(args&: ContextIter, args&: Inserted) = Contexts.insert(V: NewContext);
265 assert(Inserted && "Failed to insert DeclContext");
266 (void)Inserted;
267 } else if (Tag != dwarf::DW_TAG_namespace &&
268 !(*ContextIter)->setLastSeenDIE(U, Die: DIE)) {
269 // The context was found, but it is ambiguous with another context
270 // in the same file. Mark it invalid.
271 return PointerIntPair<DeclContext *, 1>(*ContextIter, /* IntVal= */ 1);
272 }
273
274 assert(ContextIter != Contexts.end());
275 // FIXME: dsymutil-classic compatibility. Union types aren't
276 // uniques, but their children might be.
277 if ((Tag == dwarf::DW_TAG_subprogram &&
278 Context.getTag() != dwarf::DW_TAG_structure_type &&
279 Context.getTag() != dwarf::DW_TAG_class_type) ||
280 (Tag == dwarf::DW_TAG_union_type))
281 return PointerIntPair<DeclContext *, 1>(*ContextIter, /* IntVal= */ 1);
282
283 return PointerIntPair<DeclContext *, 1>(*ContextIter);
284}
285
286StringRef
287DeclContextTree::getResolvedPath(CompileUnit &CU, unsigned FileNum,
288 const DWARFDebugLine::LineTable &LineTable) {
289 std::pair<unsigned, unsigned> Key = {CU.getUniqueID(), FileNum};
290
291 ResolvedPathsMap::const_iterator It = ResolvedPaths.find(Val: Key);
292 if (It == ResolvedPaths.end()) {
293 std::string FileName;
294 bool FoundFileName = LineTable.getFileNameByIndex(
295 FileIndex: FileNum, CompDir: CU.getOrigUnit().getCompilationDir(),
296 Kind: DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, Result&: FileName);
297 (void)FoundFileName;
298 assert(FoundFileName && "Must get file name from line table");
299
300 // Undo prefix mapping, so that the path can be resolved on disk.
301 FileName = CU.getContainingFile().remapPath(Path: FileName);
302
303 // Second level of caching, this time based on the file's parent
304 // path.
305 StringRef ResolvedPath = PathResolver.resolve(Path: FileName, StringPool);
306
307 It = ResolvedPaths.insert(KV: std::make_pair(x&: Key, y&: ResolvedPath)).first;
308 }
309
310 return It->second;
311}
312
313} // namespace llvm
314