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