1//===-- DebugNamesDWARFIndex.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 "Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h"
10#include "Plugins/SymbolFile/DWARF/DWARFDebugInfo.h"
11#include "Plugins/SymbolFile/DWARF/DWARFDeclContext.h"
12#include "Plugins/SymbolFile/DWARF/SymbolFileDWARFDwo.h"
13#include "lldb/Core/Module.h"
14#include "lldb/Utility/RegularExpression.h"
15#include "lldb/Utility/Stream.h"
16#include "llvm/ADT/Sequence.h"
17#include <optional>
18
19using namespace lldb_private;
20using namespace lldb;
21using namespace lldb_private::dwarf;
22using namespace lldb_private::plugin::dwarf;
23
24llvm::Expected<std::unique_ptr<DebugNamesDWARFIndex>>
25DebugNamesDWARFIndex::Create(Module &module, DWARFDataExtractor debug_names,
26 DWARFDataExtractor debug_str,
27 SymbolFileDWARF &dwarf) {
28 auto index_up = std::make_unique<DebugNames>(args: debug_names.GetAsLLVMDWARF(),
29 args: debug_str.GetAsLLVM());
30 if (llvm::Error E = index_up->extract())
31 return std::move(E);
32
33 return std::unique_ptr<DebugNamesDWARFIndex>(new DebugNamesDWARFIndex(
34 module, std::move(index_up), debug_names, debug_str, dwarf));
35}
36
37llvm::DenseSet<dw_offset_t>
38DebugNamesDWARFIndex::GetUnits(const DebugNames &debug_names) {
39 llvm::DenseSet<dw_offset_t> result;
40 for (const DebugNames::NameIndex &ni : debug_names) {
41 const uint32_t num_cus = ni.getCUCount();
42 for (uint32_t cu = 0; cu < num_cus; ++cu)
43 result.insert(V: ni.getCUOffset(CU: cu));
44 const uint32_t num_tus = ni.getLocalTUCount();
45 for (uint32_t tu = 0; tu < num_tus; ++tu)
46 result.insert(V: ni.getLocalTUOffset(TU: tu));
47 }
48 return result;
49}
50
51std::optional<DIERef>
52DebugNamesDWARFIndex::ToDIERef(const DebugNames::Entry &entry) const {
53 // Look for a DWARF unit offset (CU offset or local TU offset) as they are
54 // both offsets into the .debug_info section.
55 std::optional<uint64_t> unit_offset = entry.getCUOffset();
56 if (!unit_offset) {
57 unit_offset = entry.getLocalTUOffset();
58 if (!unit_offset)
59 return std::nullopt;
60 }
61
62 DWARFUnit *cu =
63 m_debug_info.GetUnitAtOffset(section: DIERef::Section::DebugInfo, cu_offset: *unit_offset);
64 if (!cu)
65 return std::nullopt;
66
67 cu = &cu->GetNonSkeletonUnit();
68 if (std::optional<uint64_t> die_offset = entry.getDIEUnitOffset())
69 return DIERef(cu->GetSymbolFileDWARF().GetFileIndex(),
70 DIERef::Section::DebugInfo, cu->GetOffset() + *die_offset);
71
72 return std::nullopt;
73}
74
75bool DebugNamesDWARFIndex::ProcessEntry(
76 const DebugNames::Entry &entry,
77 llvm::function_ref<bool(DWARFDIE die)> callback) {
78 std::optional<DIERef> ref = ToDIERef(entry);
79 if (!ref)
80 return true;
81 SymbolFileDWARF &dwarf = *llvm::cast<SymbolFileDWARF>(
82 Val: m_module.GetSymbolFile()->GetBackingSymbolFile());
83 DWARFDIE die = dwarf.GetDIE(die_ref: *ref);
84 if (!die)
85 return true;
86 return callback(die);
87}
88
89void DebugNamesDWARFIndex::MaybeLogLookupError(llvm::Error error,
90 const DebugNames::NameIndex &ni,
91 llvm::StringRef name) {
92 // Ignore SentinelErrors, log everything else.
93 LLDB_LOG_ERROR(
94 GetLog(DWARFLog::Lookups),
95 handleErrors(std::move(error), [](const DebugNames::SentinelError &) {}),
96 "Failed to parse index entries for index at {1:x}, name {2}: {0}",
97 ni.getUnitOffset(), name);
98}
99
100void DebugNamesDWARFIndex::GetGlobalVariables(
101 ConstString basename, llvm::function_ref<bool(DWARFDIE die)> callback) {
102 for (const DebugNames::Entry &entry :
103 m_debug_names_up->equal_range(Key: basename.GetStringRef())) {
104 if (entry.tag() != DW_TAG_variable)
105 continue;
106
107 if (!ProcessEntry(entry, callback))
108 return;
109 }
110
111 m_fallback.GetGlobalVariables(basename, callback);
112}
113
114void DebugNamesDWARFIndex::GetGlobalVariables(
115 const RegularExpression &regex,
116 llvm::function_ref<bool(DWARFDIE die)> callback) {
117 for (const DebugNames::NameIndex &ni: *m_debug_names_up) {
118 for (DebugNames::NameTableEntry nte: ni) {
119 Mangled mangled_name(nte.getString());
120 if (!mangled_name.NameMatches(regex))
121 continue;
122
123 uint64_t entry_offset = nte.getEntryOffset();
124 llvm::Expected<DebugNames::Entry> entry_or = ni.getEntry(Offset: &entry_offset);
125 for (; entry_or; entry_or = ni.getEntry(Offset: &entry_offset)) {
126 if (entry_or->tag() != DW_TAG_variable)
127 continue;
128
129 if (!ProcessEntry(entry: *entry_or, callback))
130 return;
131 }
132 MaybeLogLookupError(error: entry_or.takeError(), ni, name: nte.getString());
133 }
134 }
135
136 m_fallback.GetGlobalVariables(regex, callback);
137}
138
139void DebugNamesDWARFIndex::GetGlobalVariables(
140 DWARFUnit &cu, llvm::function_ref<bool(DWARFDIE die)> callback) {
141 uint64_t cu_offset = cu.GetOffset();
142 bool found_entry_for_cu = false;
143 for (const DebugNames::NameIndex &ni : *m_debug_names_up) {
144 // Check if this name index contains an entry for the given CU.
145 bool cu_matches = false;
146 for (uint32_t i = 0; i < ni.getCUCount(); ++i) {
147 if (ni.getCUOffset(CU: i) == cu_offset) {
148 cu_matches = true;
149 break;
150 }
151 }
152 if (!cu_matches)
153 continue;
154
155 for (DebugNames::NameTableEntry nte : ni) {
156 uint64_t entry_offset = nte.getEntryOffset();
157 llvm::Expected<DebugNames::Entry> entry_or = ni.getEntry(Offset: &entry_offset);
158 for (; entry_or; entry_or = ni.getEntry(Offset: &entry_offset)) {
159 if (entry_or->tag() != DW_TAG_variable)
160 continue;
161 if (entry_or->getCUOffset() != cu_offset)
162 continue;
163
164 found_entry_for_cu = true;
165 if (!ProcessEntry(entry: *entry_or, callback))
166 return;
167 }
168 MaybeLogLookupError(error: entry_or.takeError(), ni, name: nte.getString());
169 }
170 }
171 // If no name index for that particular CU was found, fallback to
172 // creating the manual index.
173 if (!found_entry_for_cu)
174 m_fallback.GetGlobalVariables(unit&: cu, callback);
175}
176
177void DebugNamesDWARFIndex::GetCompleteObjCClass(
178 ConstString class_name, bool must_be_implementation,
179 llvm::function_ref<bool(DWARFDIE die)> callback) {
180 // Keep a list of incomplete types as fallback for when we don't find the
181 // complete type.
182 DIEArray incomplete_types;
183
184 for (const DebugNames::Entry &entry :
185 m_debug_names_up->equal_range(Key: class_name.GetStringRef())) {
186 if (entry.tag() != DW_TAG_structure_type &&
187 entry.tag() != DW_TAG_class_type)
188 continue;
189
190 std::optional<DIERef> ref = ToDIERef(entry);
191 if (!ref)
192 continue;
193
194 DWARFUnit *cu = m_debug_info.GetUnit(die_ref: *ref);
195 if (!cu || !cu->Supports_DW_AT_APPLE_objc_complete_type()) {
196 incomplete_types.push_back(x: *ref);
197 continue;
198 }
199
200 DWARFDIE die = m_debug_info.GetDIE(die_ref: *ref);
201 if (!die) {
202 ReportInvalidDIERef(ref: *ref, name: class_name.GetStringRef());
203 continue;
204 }
205
206 if (die.GetAttributeValueAsUnsigned(attr: DW_AT_APPLE_objc_complete_type, fail_value: 0)) {
207 // If we find the complete version we're done.
208 callback(die);
209 return;
210 }
211 incomplete_types.push_back(x: *ref);
212 }
213
214 auto dierefcallback = DIERefCallback(callback, name: class_name.GetStringRef());
215 for (DIERef ref : incomplete_types)
216 if (!dierefcallback(ref))
217 return;
218
219 m_fallback.GetCompleteObjCClass(class_name, must_be_implementation, callback);
220}
221
222namespace {
223using Entry = llvm::DWARFDebugNames::Entry;
224
225/// If `entry` and all of its parents have an `IDX_parent`, use that information
226/// to build and return a list of at most `max_parents` parent Entries.
227/// `entry` itself is not included in the list.
228/// If any parent does not have an `IDX_parent`, or the Entry data is corrupted,
229/// nullopt is returned.
230std::optional<llvm::SmallVector<Entry, 4>>
231getParentChain(Entry entry, uint32_t max_parents) {
232 llvm::SmallVector<Entry, 4> parent_entries;
233
234 do {
235 if (!entry.hasParentInformation())
236 return std::nullopt;
237
238 llvm::Expected<std::optional<Entry>> parent = entry.getParentDIEEntry();
239 if (!parent) {
240 // Bad data.
241 LLDB_LOG_ERROR(
242 GetLog(DWARFLog::Lookups), parent.takeError(),
243 "Failed to extract parent entry from a non-empty IDX_parent");
244 return std::nullopt;
245 }
246
247 // Last parent in the chain.
248 if (!parent->has_value())
249 break;
250
251 parent_entries.push_back(Elt: **parent);
252 entry = **parent;
253 } while (parent_entries.size() < max_parents);
254
255 return parent_entries;
256}
257} // namespace
258
259void DebugNamesDWARFIndex::GetFullyQualifiedType(
260 const DWARFDeclContext &context,
261 llvm::function_ref<bool(DWARFDIE die)> callback) {
262 if (context.GetSize() == 0)
263 return;
264
265 llvm::StringRef leaf_name = context[0].name;
266 llvm::SmallVector<llvm::StringRef> parent_names;
267 for (auto idx : llvm::seq<int>(Begin: 1, End: context.GetSize()))
268 parent_names.emplace_back(Args: context[idx].name);
269
270 // For each entry, grab its parent chain and check if we have a match.
271 for (const DebugNames::Entry &entry :
272 m_debug_names_up->equal_range(Key: leaf_name)) {
273 if (!isType(T: entry.tag()))
274 continue;
275
276 // Grab at most one extra parent, subsequent parents are not necessary to
277 // test equality.
278 std::optional<llvm::SmallVector<Entry, 4>> parent_chain =
279 getParentChain(entry, max_parents: parent_names.size() + 1);
280
281 if (!parent_chain) {
282 // Fallback: use the base class implementation.
283 if (!ProcessEntry(entry, callback: [&](DWARFDIE die) {
284 return GetFullyQualifiedTypeImpl(context, die, callback);
285 }))
286 return;
287 continue;
288 }
289
290 if (SameParentChain(parent_names, parent_entries: *parent_chain) &&
291 !ProcessEntry(entry, callback))
292 return;
293 }
294}
295
296bool DebugNamesDWARFIndex::SameParentChain(
297 llvm::ArrayRef<llvm::StringRef> parent_names,
298 llvm::ArrayRef<DebugNames::Entry> parent_entries) const {
299
300 if (parent_entries.size() != parent_names.size())
301 return false;
302
303 auto SameAsEntryATName = [this](llvm::StringRef name,
304 const DebugNames::Entry &entry) {
305 // Peek at the AT_name of `entry` and test equality to `name`.
306 auto maybe_dieoffset = entry.getDIEUnitOffset();
307 if (!maybe_dieoffset)
308 return false;
309 auto die_ref = ToDIERef(entry);
310 if (!die_ref)
311 return false;
312 return name == m_debug_info.PeekDIEName(die_ref: *die_ref);
313 };
314
315 // If the AT_name of any parent fails to match the expected name, we don't
316 // have a match.
317 for (auto [parent_name, parent_entry] :
318 llvm::zip_equal(t&: parent_names, u&: parent_entries))
319 if (!SameAsEntryATName(parent_name, parent_entry))
320 return false;
321 return true;
322}
323
324void DebugNamesDWARFIndex::GetTypes(
325 ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) {
326 for (const DebugNames::Entry &entry :
327 m_debug_names_up->equal_range(Key: name.GetStringRef())) {
328 if (isType(T: entry.tag())) {
329 if (!ProcessEntry(entry, callback))
330 return;
331 }
332 }
333
334 m_fallback.GetTypes(name, callback);
335}
336
337void DebugNamesDWARFIndex::GetTypes(
338 const DWARFDeclContext &context,
339 llvm::function_ref<bool(DWARFDIE die)> callback) {
340 auto name = context[0].name;
341 for (const DebugNames::Entry &entry : m_debug_names_up->equal_range(Key: name)) {
342 if (entry.tag() == context[0].tag) {
343 if (!ProcessEntry(entry, callback))
344 return;
345 }
346 }
347
348 m_fallback.GetTypes(context, callback);
349}
350
351void DebugNamesDWARFIndex::GetNamespaces(
352 ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) {
353 for (const DebugNames::Entry &entry :
354 m_debug_names_up->equal_range(Key: name.GetStringRef())) {
355 lldb_private::dwarf::Tag entry_tag = entry.tag();
356 if (entry_tag == DW_TAG_namespace ||
357 entry_tag == DW_TAG_imported_declaration) {
358 if (!ProcessEntry(entry, callback))
359 return;
360 }
361 }
362
363 m_fallback.GetNamespaces(name, callback);
364}
365
366void DebugNamesDWARFIndex::GetFunctions(
367 const Module::LookupInfo &lookup_info, SymbolFileDWARF &dwarf,
368 const CompilerDeclContext &parent_decl_ctx,
369 llvm::function_ref<bool(DWARFDIE die)> callback) {
370 ConstString name = lookup_info.GetLookupName();
371 std::set<DWARFDebugInfoEntry *> seen;
372 for (const DebugNames::Entry &entry :
373 m_debug_names_up->equal_range(Key: name.GetStringRef())) {
374 Tag tag = entry.tag();
375 if (tag != DW_TAG_subprogram && tag != DW_TAG_inlined_subroutine)
376 continue;
377
378 if (std::optional<DIERef> ref = ToDIERef(entry)) {
379 if (!ProcessFunctionDIE(lookup_info, ref: *ref, dwarf, parent_decl_ctx,
380 callback: [&](DWARFDIE die) {
381 if (!seen.insert(x: die.GetDIE()).second)
382 return true;
383 return callback(die);
384 }))
385 return;
386 }
387 }
388
389 m_fallback.GetFunctions(lookup_info, dwarf, parent_decl_ctx, callback);
390}
391
392void DebugNamesDWARFIndex::GetFunctions(
393 const RegularExpression &regex,
394 llvm::function_ref<bool(DWARFDIE die)> callback) {
395 for (const DebugNames::NameIndex &ni: *m_debug_names_up) {
396 for (DebugNames::NameTableEntry nte: ni) {
397 if (!regex.Execute(string: nte.getString()))
398 continue;
399
400 uint64_t entry_offset = nte.getEntryOffset();
401 llvm::Expected<DebugNames::Entry> entry_or = ni.getEntry(Offset: &entry_offset);
402 for (; entry_or; entry_or = ni.getEntry(Offset: &entry_offset)) {
403 Tag tag = entry_or->tag();
404 if (tag != DW_TAG_subprogram && tag != DW_TAG_inlined_subroutine)
405 continue;
406
407 if (!ProcessEntry(entry: *entry_or, callback))
408 return;
409 }
410 MaybeLogLookupError(error: entry_or.takeError(), ni, name: nte.getString());
411 }
412 }
413
414 m_fallback.GetFunctions(regex, callback);
415}
416
417void DebugNamesDWARFIndex::Dump(Stream &s) {
418 m_fallback.Dump(s);
419
420 std::string data;
421 llvm::raw_string_ostream os(data);
422 m_debug_names_up->dump(OS&: os);
423 s.PutCString(cstr: os.str());
424}
425

source code of lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp