1 //===-- AppleDWARFIndex.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/AppleDWARFIndex.h"
10 #include "Plugins/SymbolFile/DWARF/DWARFDeclContext.h"
11 #include "Plugins/SymbolFile/DWARF/DWARFUnit.h"
12 #include "Plugins/SymbolFile/DWARF/LogChannelDWARF.h"
13 
14 #include "lldb/Core/Module.h"
15 #include "lldb/Symbol/Function.h"
16 #include "llvm/Support/DJB.h"
17 
18 using namespace lldb_private;
19 using namespace lldb;
20 using namespace lldb_private::dwarf;
21 using namespace lldb_private::plugin::dwarf;
22 
23 std::unique_ptr<AppleDWARFIndex> AppleDWARFIndex::Create(
24     Module &module, DWARFDataExtractor apple_names,
25     DWARFDataExtractor apple_namespaces, DWARFDataExtractor apple_types,
26     DWARFDataExtractor apple_objc, DWARFDataExtractor debug_str) {
27 
28   llvm::DataExtractor llvm_debug_str = debug_str.GetAsLLVM();
29 
30   auto apple_names_table_up = std::make_unique<llvm::AppleAcceleratorTable>(
31       apple_names.GetAsLLVMDWARF(), llvm_debug_str);
32 
33   auto apple_namespaces_table_up =
34       std::make_unique<llvm::AppleAcceleratorTable>(
35           apple_namespaces.GetAsLLVMDWARF(), llvm_debug_str);
36 
37   auto apple_types_table_up = std::make_unique<llvm::AppleAcceleratorTable>(
38       apple_types.GetAsLLVMDWARF(), llvm_debug_str);
39 
40   auto apple_objc_table_up = std::make_unique<llvm::AppleAcceleratorTable>(
41       apple_objc.GetAsLLVMDWARF(), llvm_debug_str);
42 
43   auto extract_and_check = [](auto &TablePtr) {
44     if (auto E = TablePtr->extract()) {
45       llvm::consumeError(std::move(E));
46       TablePtr.reset();
47     }
48   };
49 
50   extract_and_check(apple_names_table_up);
51   extract_and_check(apple_namespaces_table_up);
52   extract_and_check(apple_types_table_up);
53   extract_and_check(apple_objc_table_up);
54   assert(apple_names.GetByteSize() == 0 || apple_names.GetSharedDataBuffer());
55   assert(apple_namespaces.GetByteSize() == 0 ||
56          apple_namespaces.GetSharedDataBuffer());
57   assert(apple_types.GetByteSize() == 0 || apple_types.GetSharedDataBuffer());
58   assert(apple_objc.GetByteSize() == 0 || apple_objc.GetSharedDataBuffer());
59 
60   if (apple_names_table_up || apple_namespaces_table_up ||
61       apple_types_table_up || apple_objc_table_up)
62     return std::make_unique<AppleDWARFIndex>(
63         module, std::move(apple_names_table_up),
64         std::move(apple_namespaces_table_up), std::move(apple_types_table_up),
65         std::move(apple_objc_table_up), apple_names.GetSharedDataBuffer(),
66         apple_namespaces.GetSharedDataBuffer(),
67         apple_types.GetSharedDataBuffer(), apple_objc.GetSharedDataBuffer());
68 
69   return nullptr;
70 }
71 
72 /// Returns true if `tag` is a class_type of structure_type tag.
73 static bool IsClassOrStruct(dw_tag_t tag) {
74   return tag == DW_TAG_class_type || tag == DW_TAG_structure_type;
75 }
76 
77 /// Returns true if `entry` has an extractable DW_ATOM_qual_name_hash and it
78 /// matches `expected_hash`.
79 static bool
80 EntryHasMatchingQualhash(const llvm::AppleAcceleratorTable::Entry &entry,
81                          uint32_t expected_hash) {
82   std::optional<llvm::DWARFFormValue> form_value =
83       entry.lookup(dwarf::DW_ATOM_qual_name_hash);
84   if (!form_value)
85     return false;
86   std::optional<uint64_t> hash = form_value->getAsUnsignedConstant();
87   return hash && (*hash == expected_hash);
88 }
89 
90 /// Returns true if `entry` has an extractable DW_ATOM_die_tag and it matches
91 /// `expected_tag`. We also consider it a match if the tags are different but
92 /// in the set of {TAG_class_type, TAG_struct_type}.
93 static bool EntryHasMatchingTag(const llvm::AppleAcceleratorTable::Entry &entry,
94                                 dw_tag_t expected_tag) {
95   std::optional<llvm::DWARFFormValue> form_value =
96       entry.lookup(dwarf::DW_ATOM_die_tag);
97   if (!form_value)
98     return false;
99   std::optional<uint64_t> maybe_tag = form_value->getAsUnsignedConstant();
100   if (!maybe_tag)
101     return false;
102   auto tag = static_cast<dw_tag_t>(*maybe_tag);
103   return tag == expected_tag ||
104          (IsClassOrStruct(tag) && IsClassOrStruct(expected_tag));
105 }
106 
107 /// Returns true if `entry` has an extractable DW_ATOM_type_flags and the flag
108 /// "DW_FLAG_type_implementation" is set.
109 static bool
110 HasImplementationFlag(const llvm::AppleAcceleratorTable::Entry &entry) {
111   std::optional<llvm::DWARFFormValue> form_value =
112       entry.lookup(dwarf::DW_ATOM_type_flags);
113   if (!form_value)
114     return false;
115   std::optional<uint64_t> Flags = form_value->getAsUnsignedConstant();
116   return Flags &&
117          (*Flags & llvm::dwarf::AcceleratorTable::DW_FLAG_type_implementation);
118 }
119 
120 void AppleDWARFIndex::SearchFor(const llvm::AppleAcceleratorTable &table,
121                                 llvm::StringRef name,
122                                 llvm::function_ref<bool(DWARFDIE die)> callback,
123                                 std::optional<dw_tag_t> search_for_tag,
124                                 std::optional<uint32_t> search_for_qualhash) {
125   auto converted_cb = DIERefCallback(callback, name);
126   for (const auto &entry : table.equal_range(name)) {
127     if (search_for_qualhash &&
128         !EntryHasMatchingQualhash(entry, *search_for_qualhash))
129       continue;
130     if (search_for_tag && !EntryHasMatchingTag(entry, *search_for_tag))
131       continue;
132     if (!converted_cb(entry))
133       break;
134   }
135 }
136 
137 void AppleDWARFIndex::GetGlobalVariables(
138     ConstString basename, llvm::function_ref<bool(DWARFDIE die)> callback) {
139   if (!m_apple_names_up)
140     return;
141   SearchFor(*m_apple_names_up, basename, callback);
142 }
143 
144 void AppleDWARFIndex::GetGlobalVariables(
145     const RegularExpression &regex,
146     llvm::function_ref<bool(DWARFDIE die)> callback) {
147   if (!m_apple_names_up)
148     return;
149 
150   DIERefCallbackImpl converted_cb = DIERefCallback(callback, regex.GetText());
151 
152   for (const auto &entry : m_apple_names_up->entries())
153     if (std::optional<llvm::StringRef> name = entry.readName();
154         name && Mangled(*name).NameMatches(regex))
155       if (!converted_cb(entry.BaseEntry))
156         return;
157 }
158 
159 void AppleDWARFIndex::GetGlobalVariables(
160     DWARFUnit &cu, llvm::function_ref<bool(DWARFDIE die)> callback) {
161   if (!m_apple_names_up)
162     return;
163 
164   const DWARFUnit &non_skeleton_cu = cu.GetNonSkeletonUnit();
165   dw_offset_t lower_bound = non_skeleton_cu.GetOffset();
166   dw_offset_t upper_bound = non_skeleton_cu.GetNextUnitOffset();
167   auto is_in_range = [lower_bound, upper_bound](std::optional<uint32_t> val) {
168     return val.has_value() && *val >= lower_bound && *val < upper_bound;
169   };
170 
171   DIERefCallbackImpl converted_cb = DIERefCallback(callback);
172   for (auto entry : m_apple_names_up->entries()) {
173     if (is_in_range(entry.BaseEntry.getDIESectionOffset()))
174       if (!converted_cb(entry.BaseEntry))
175         return;
176   }
177 }
178 
179 void AppleDWARFIndex::GetObjCMethods(
180     ConstString class_name, llvm::function_ref<bool(DWARFDIE die)> callback) {
181   if (!m_apple_objc_up)
182     return;
183   SearchFor(*m_apple_objc_up, class_name, callback);
184 }
185 
186 void AppleDWARFIndex::GetCompleteObjCClass(
187     ConstString class_name, bool must_be_implementation,
188     llvm::function_ref<bool(DWARFDIE die)> callback) {
189   if (!m_apple_types_up)
190     return;
191 
192   llvm::SmallVector<DIERef> decl_dies;
193   auto converted_cb = DIERefCallback(callback, class_name);
194 
195   for (const auto &entry : m_apple_types_up->equal_range(class_name)) {
196     if (HasImplementationFlag(entry)) {
197       converted_cb(entry);
198       return;
199     }
200 
201     decl_dies.emplace_back(std::nullopt, DIERef::Section::DebugInfo,
202                            *entry.getDIESectionOffset());
203   }
204 
205   if (must_be_implementation)
206     return;
207   for (DIERef ref : decl_dies)
208     if (!converted_cb(ref))
209       return;
210 }
211 
212 void AppleDWARFIndex::GetTypes(
213     ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) {
214   if (!m_apple_types_up)
215     return;
216   SearchFor(*m_apple_types_up, name, callback);
217 }
218 
219 void AppleDWARFIndex::GetTypes(
220     const DWARFDeclContext &context,
221     llvm::function_ref<bool(DWARFDIE die)> callback) {
222   if (!m_apple_types_up)
223     return;
224 
225   Log *log = GetLog(DWARFLog::TypeCompletion | DWARFLog::Lookups);
226   const bool entries_have_tag =
227       m_apple_types_up->containsAtomType(DW_ATOM_die_tag);
228   const bool entries_have_qual_hash =
229       m_apple_types_up->containsAtomType(DW_ATOM_qual_name_hash);
230 
231   llvm::StringRef expected_name = context[0].name;
232 
233   if (entries_have_tag && entries_have_qual_hash) {
234     const dw_tag_t expected_tag = context[0].tag;
235     const uint32_t expected_qualname_hash =
236         llvm::djbHash(context.GetQualifiedName());
237     if (log)
238       m_module.LogMessage(log, "FindByNameAndTagAndQualifiedNameHash()");
239     SearchFor(*m_apple_types_up, expected_name, callback, expected_tag,
240                expected_qualname_hash);
241     return;
242   }
243 
244   // Historically, if there are no tags, we also ignore qual_hash (why?)
245   if (!entries_have_tag) {
246     SearchFor(*m_apple_names_up, expected_name, callback);
247     return;
248   }
249 
250   // We have a tag but no qual hash.
251 
252   // When searching for a scoped type (for example,
253   // "std::vector<int>::const_iterator") searching for the innermost
254   // name alone ("const_iterator") could yield many false
255   // positives. By searching for the parent type ("vector<int>")
256   // first we can avoid extracting type DIEs from object files that
257   // would fail the filter anyway.
258   if ((context.GetSize() > 1) && IsClassOrStruct(context[1].tag))
259     if (m_apple_types_up->equal_range(context[1].name).empty())
260       return;
261 
262   if (log)
263     m_module.LogMessage(log, "FindByNameAndTag()");
264   const dw_tag_t expected_tag = context[0].tag;
265   SearchFor(*m_apple_types_up, expected_name, callback, expected_tag);
266   return;
267 }
268 
269 void AppleDWARFIndex::GetNamespaces(
270     ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) {
271   if (!m_apple_namespaces_up)
272     return;
273   SearchFor(*m_apple_namespaces_up, name, callback);
274 }
275 
276 void AppleDWARFIndex::GetFunctions(
277     const Module::LookupInfo &lookup_info, SymbolFileDWARF &dwarf,
278     const CompilerDeclContext &parent_decl_ctx,
279     llvm::function_ref<bool(DWARFDIE die)> callback) {
280   if (!m_apple_names_up)
281     return;
282 
283   ConstString name = lookup_info.GetLookupName();
284   for (const auto &entry : m_apple_names_up->equal_range(name)) {
285     DIERef die_ref(std::nullopt, DIERef::Section::DebugInfo,
286                    *entry.getDIESectionOffset());
287     if (!ProcessFunctionDIE(lookup_info, die_ref, dwarf, parent_decl_ctx,
288                             callback))
289       return;
290   }
291 }
292 
293 void AppleDWARFIndex::GetFunctions(
294     const RegularExpression &regex,
295     llvm::function_ref<bool(DWARFDIE die)> callback) {
296   return GetGlobalVariables(regex, callback);
297 }
298 
299 void AppleDWARFIndex::Dump(Stream &s) {
300   if (m_apple_names_up)
301     s.PutCString(".apple_names index present\n");
302   if (m_apple_namespaces_up)
303     s.PutCString(".apple_namespaces index present\n");
304   if (m_apple_types_up)
305     s.PutCString(".apple_types index present\n");
306   if (m_apple_objc_up)
307     s.PutCString(".apple_objc index present\n");
308   // TODO: Dump index contents
309 }
310