1 | //===-- LibCxxMap.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 "LibCxx.h" |
10 | |
11 | #include "Plugins/TypeSystem/Clang/TypeSystemClang.h" |
12 | #include "lldb/Core/ValueObject.h" |
13 | #include "lldb/Core/ValueObjectConstResult.h" |
14 | #include "lldb/DataFormatters/FormattersHelpers.h" |
15 | #include "lldb/Target/Target.h" |
16 | #include "lldb/Utility/DataBufferHeap.h" |
17 | #include "lldb/Utility/Endian.h" |
18 | #include "lldb/Utility/Status.h" |
19 | #include "lldb/Utility/Stream.h" |
20 | |
21 | using namespace lldb; |
22 | using namespace lldb_private; |
23 | using namespace lldb_private::formatters; |
24 | |
25 | class MapEntry { |
26 | public: |
27 | MapEntry() = default; |
28 | explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} |
29 | explicit MapEntry(ValueObject *entry) |
30 | : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} |
31 | |
32 | ValueObjectSP left() const { |
33 | static ConstString g_left("__left_" ); |
34 | if (!m_entry_sp) |
35 | return m_entry_sp; |
36 | return m_entry_sp->GetSyntheticChildAtOffset( |
37 | offset: 0, type: m_entry_sp->GetCompilerType(), can_create: true); |
38 | } |
39 | |
40 | ValueObjectSP right() const { |
41 | static ConstString g_right("__right_" ); |
42 | if (!m_entry_sp) |
43 | return m_entry_sp; |
44 | return m_entry_sp->GetSyntheticChildAtOffset( |
45 | offset: m_entry_sp->GetProcessSP()->GetAddressByteSize(), |
46 | type: m_entry_sp->GetCompilerType(), can_create: true); |
47 | } |
48 | |
49 | ValueObjectSP parent() const { |
50 | static ConstString g_parent("__parent_" ); |
51 | if (!m_entry_sp) |
52 | return m_entry_sp; |
53 | return m_entry_sp->GetSyntheticChildAtOffset( |
54 | offset: 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(), |
55 | type: m_entry_sp->GetCompilerType(), can_create: true); |
56 | } |
57 | |
58 | uint64_t value() const { |
59 | if (!m_entry_sp) |
60 | return 0; |
61 | return m_entry_sp->GetValueAsUnsigned(fail_value: 0); |
62 | } |
63 | |
64 | bool error() const { |
65 | if (!m_entry_sp) |
66 | return true; |
67 | return m_entry_sp->GetError().Fail(); |
68 | } |
69 | |
70 | bool null() const { return (value() == 0); } |
71 | |
72 | ValueObjectSP GetEntry() const { return m_entry_sp; } |
73 | |
74 | void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } |
75 | |
76 | bool operator==(const MapEntry &rhs) const { |
77 | return (rhs.m_entry_sp.get() == m_entry_sp.get()); |
78 | } |
79 | |
80 | private: |
81 | ValueObjectSP m_entry_sp; |
82 | }; |
83 | |
84 | class MapIterator { |
85 | public: |
86 | MapIterator() = default; |
87 | MapIterator(MapEntry entry, size_t depth = 0) |
88 | : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {} |
89 | MapIterator(ValueObjectSP entry, size_t depth = 0) |
90 | : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {} |
91 | MapIterator(const MapIterator &rhs) |
92 | : m_entry(rhs.m_entry), m_max_depth(rhs.m_max_depth), m_error(false) {} |
93 | MapIterator(ValueObject *entry, size_t depth = 0) |
94 | : m_entry(entry), m_max_depth(depth), m_error(false) {} |
95 | |
96 | MapIterator &operator=(const MapIterator &) = default; |
97 | |
98 | ValueObjectSP value() { return m_entry.GetEntry(); } |
99 | |
100 | ValueObjectSP advance(size_t count) { |
101 | ValueObjectSP fail; |
102 | if (m_error) |
103 | return fail; |
104 | size_t steps = 0; |
105 | while (count > 0) { |
106 | next(); |
107 | count--, steps++; |
108 | if (m_error || m_entry.null() || (steps > m_max_depth)) |
109 | return fail; |
110 | } |
111 | return m_entry.GetEntry(); |
112 | } |
113 | |
114 | protected: |
115 | void next() { |
116 | if (m_entry.null()) |
117 | return; |
118 | MapEntry right(m_entry.right()); |
119 | if (!right.null()) { |
120 | m_entry = tree_min(x: std::move(right)); |
121 | return; |
122 | } |
123 | size_t steps = 0; |
124 | while (!is_left_child(x: m_entry)) { |
125 | if (m_entry.error()) { |
126 | m_error = true; |
127 | return; |
128 | } |
129 | m_entry.SetEntry(m_entry.parent()); |
130 | steps++; |
131 | if (steps > m_max_depth) { |
132 | m_entry = MapEntry(); |
133 | return; |
134 | } |
135 | } |
136 | m_entry = MapEntry(m_entry.parent()); |
137 | } |
138 | |
139 | private: |
140 | MapEntry tree_min(MapEntry x) { |
141 | if (x.null()) |
142 | return MapEntry(); |
143 | MapEntry left(x.left()); |
144 | size_t steps = 0; |
145 | while (!left.null()) { |
146 | if (left.error()) { |
147 | m_error = true; |
148 | return MapEntry(); |
149 | } |
150 | x = left; |
151 | left.SetEntry(x.left()); |
152 | steps++; |
153 | if (steps > m_max_depth) |
154 | return MapEntry(); |
155 | } |
156 | return x; |
157 | } |
158 | |
159 | bool is_left_child(const MapEntry &x) { |
160 | if (x.null()) |
161 | return false; |
162 | MapEntry rhs(x.parent()); |
163 | rhs.SetEntry(rhs.left()); |
164 | return x.value() == rhs.value(); |
165 | } |
166 | |
167 | MapEntry m_entry; |
168 | size_t m_max_depth = 0; |
169 | bool m_error = false; |
170 | }; |
171 | |
172 | namespace lldb_private { |
173 | namespace formatters { |
174 | class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd { |
175 | public: |
176 | LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); |
177 | |
178 | ~LibcxxStdMapSyntheticFrontEnd() override = default; |
179 | |
180 | llvm::Expected<uint32_t> CalculateNumChildren() override; |
181 | |
182 | lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override; |
183 | |
184 | lldb::ChildCacheState Update() override; |
185 | |
186 | bool MightHaveChildren() override; |
187 | |
188 | size_t GetIndexOfChildWithName(ConstString name) override; |
189 | |
190 | private: |
191 | bool GetDataType(); |
192 | |
193 | void GetValueOffset(const lldb::ValueObjectSP &node); |
194 | |
195 | ValueObject *m_tree = nullptr; |
196 | ValueObject *m_root_node = nullptr; |
197 | CompilerType m_element_type; |
198 | uint32_t m_skip_size = UINT32_MAX; |
199 | size_t m_count = UINT32_MAX; |
200 | std::map<size_t, MapIterator> m_iterators; |
201 | }; |
202 | } // namespace formatters |
203 | } // namespace lldb_private |
204 | |
205 | lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: |
206 | LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) |
207 | : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(), m_iterators() { |
208 | if (valobj_sp) |
209 | Update(); |
210 | } |
211 | |
212 | llvm::Expected<uint32_t> lldb_private::formatters:: |
213 | LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren() { |
214 | if (m_count != UINT32_MAX) |
215 | return m_count; |
216 | |
217 | if (m_tree == nullptr) |
218 | return 0; |
219 | |
220 | ValueObjectSP size_node(m_tree->GetChildMemberWithName(name: "__pair3_" )); |
221 | if (!size_node) |
222 | return 0; |
223 | |
224 | size_node = GetFirstValueOfLibCXXCompressedPair(pair&: *size_node); |
225 | |
226 | if (!size_node) |
227 | return 0; |
228 | |
229 | m_count = size_node->GetValueAsUnsigned(fail_value: 0); |
230 | return m_count; |
231 | } |
232 | |
233 | bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() { |
234 | if (m_element_type.IsValid()) |
235 | return true; |
236 | m_element_type.Clear(); |
237 | ValueObjectSP deref; |
238 | Status error; |
239 | deref = m_root_node->Dereference(error); |
240 | if (!deref || error.Fail()) |
241 | return false; |
242 | deref = deref->GetChildMemberWithName(name: "__value_" ); |
243 | if (deref) { |
244 | m_element_type = deref->GetCompilerType(); |
245 | return true; |
246 | } |
247 | deref = m_backend.GetChildAtNamePath(names: {"__tree_" , "__pair3_" }); |
248 | if (!deref) |
249 | return false; |
250 | m_element_type = deref->GetCompilerType() |
251 | .GetTypeTemplateArgument(idx: 1) |
252 | .GetTypeTemplateArgument(idx: 1); |
253 | if (m_element_type) { |
254 | std::string name; |
255 | uint64_t bit_offset_ptr; |
256 | uint32_t bitfield_bit_size_ptr; |
257 | bool is_bitfield_ptr; |
258 | m_element_type = m_element_type.GetFieldAtIndex( |
259 | idx: 0, name, bit_offset_ptr: &bit_offset_ptr, bitfield_bit_size_ptr: &bitfield_bit_size_ptr, is_bitfield_ptr: &is_bitfield_ptr); |
260 | m_element_type = m_element_type.GetTypedefedType(); |
261 | return m_element_type.IsValid(); |
262 | } else { |
263 | m_element_type = m_backend.GetCompilerType().GetTypeTemplateArgument(idx: 0); |
264 | return m_element_type.IsValid(); |
265 | } |
266 | } |
267 | |
268 | void lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset( |
269 | const lldb::ValueObjectSP &node) { |
270 | if (m_skip_size != UINT32_MAX) |
271 | return; |
272 | if (!node) |
273 | return; |
274 | CompilerType node_type(node->GetCompilerType()); |
275 | uint64_t bit_offset; |
276 | if (node_type.GetIndexOfFieldWithName(name: "__value_" , field_compiler_type: nullptr, bit_offset_ptr: &bit_offset) != |
277 | UINT32_MAX) { |
278 | m_skip_size = bit_offset / 8u; |
279 | } else { |
280 | auto ast_ctx = node_type.GetTypeSystem().dyn_cast_or_null<TypeSystemClang>(); |
281 | if (!ast_ctx) |
282 | return; |
283 | CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier( |
284 | type_name: llvm::StringRef(), |
285 | type_fields: {{"ptr0" , ast_ctx->GetBasicType(type: lldb::eBasicTypeVoid).GetPointerType()}, |
286 | {"ptr1" , ast_ctx->GetBasicType(type: lldb::eBasicTypeVoid).GetPointerType()}, |
287 | {"ptr2" , ast_ctx->GetBasicType(type: lldb::eBasicTypeVoid).GetPointerType()}, |
288 | {"cw" , ast_ctx->GetBasicType(type: lldb::eBasicTypeBool)}, |
289 | {"payload" , (m_element_type.GetCompleteType(), m_element_type)}}); |
290 | std::string child_name; |
291 | uint32_t child_byte_size; |
292 | int32_t child_byte_offset = 0; |
293 | uint32_t child_bitfield_bit_size; |
294 | uint32_t child_bitfield_bit_offset; |
295 | bool child_is_base_class; |
296 | bool child_is_deref_of_parent; |
297 | uint64_t language_flags; |
298 | if (tree_node_type |
299 | .GetChildCompilerTypeAtIndex( |
300 | exe_ctx: nullptr, idx: 4, transparent_pointers: true, omit_empty_base_classes: true, ignore_array_bounds: true, child_name, child_byte_size, |
301 | child_byte_offset, child_bitfield_bit_size, |
302 | child_bitfield_bit_offset, child_is_base_class, |
303 | child_is_deref_of_parent, valobj: nullptr, language_flags) |
304 | .IsValid()) |
305 | m_skip_size = (uint32_t)child_byte_offset; |
306 | } |
307 | } |
308 | |
309 | lldb::ValueObjectSP |
310 | lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex( |
311 | uint32_t idx) { |
312 | static ConstString g_cc_("__cc_" ), g_cc("__cc" ); |
313 | static ConstString g_nc("__nc" ); |
314 | uint32_t num_children = CalculateNumChildrenIgnoringErrors(); |
315 | if (idx >= num_children) |
316 | return lldb::ValueObjectSP(); |
317 | if (m_tree == nullptr || m_root_node == nullptr) |
318 | return lldb::ValueObjectSP(); |
319 | |
320 | MapIterator iterator(m_root_node, num_children); |
321 | |
322 | const bool need_to_skip = (idx > 0); |
323 | size_t actual_advancde = idx; |
324 | if (need_to_skip) { |
325 | auto cached_iterator = m_iterators.find(x: idx - 1); |
326 | if (cached_iterator != m_iterators.end()) { |
327 | iterator = cached_iterator->second; |
328 | actual_advancde = 1; |
329 | } |
330 | } |
331 | |
332 | ValueObjectSP iterated_sp(iterator.advance(count: actual_advancde)); |
333 | if (!iterated_sp) { |
334 | // this tree is garbage - stop |
335 | m_tree = |
336 | nullptr; // this will stop all future searches until an Update() happens |
337 | return iterated_sp; |
338 | } |
339 | if (GetDataType()) { |
340 | if (!need_to_skip) { |
341 | Status error; |
342 | iterated_sp = iterated_sp->Dereference(error); |
343 | if (!iterated_sp || error.Fail()) { |
344 | m_tree = nullptr; |
345 | return lldb::ValueObjectSP(); |
346 | } |
347 | GetValueOffset(node: iterated_sp); |
348 | auto child_sp = iterated_sp->GetChildMemberWithName(name: "__value_" ); |
349 | if (child_sp) |
350 | iterated_sp = child_sp; |
351 | else |
352 | iterated_sp = iterated_sp->GetSyntheticChildAtOffset( |
353 | offset: m_skip_size, type: m_element_type, can_create: true); |
354 | if (!iterated_sp) { |
355 | m_tree = nullptr; |
356 | return lldb::ValueObjectSP(); |
357 | } |
358 | } else { |
359 | // because of the way our debug info is made, we need to read item 0 |
360 | // first so that we can cache information used to generate other elements |
361 | if (m_skip_size == UINT32_MAX) |
362 | GetChildAtIndex(idx: 0); |
363 | if (m_skip_size == UINT32_MAX) { |
364 | m_tree = nullptr; |
365 | return lldb::ValueObjectSP(); |
366 | } |
367 | iterated_sp = iterated_sp->GetSyntheticChildAtOffset( |
368 | offset: m_skip_size, type: m_element_type, can_create: true); |
369 | if (!iterated_sp) { |
370 | m_tree = nullptr; |
371 | return lldb::ValueObjectSP(); |
372 | } |
373 | } |
374 | } else { |
375 | m_tree = nullptr; |
376 | return lldb::ValueObjectSP(); |
377 | } |
378 | // at this point we have a valid |
379 | // we need to copy current_sp into a new object otherwise we will end up with |
380 | // all items named __value_ |
381 | StreamString name; |
382 | name.Printf(format: "[%" PRIu64 "]" , (uint64_t)idx); |
383 | auto potential_child_sp = iterated_sp->Clone(new_name: ConstString(name.GetString())); |
384 | if (potential_child_sp) { |
385 | switch (potential_child_sp->GetNumChildrenIgnoringErrors()) { |
386 | case 1: { |
387 | auto child0_sp = potential_child_sp->GetChildAtIndex(idx: 0); |
388 | if (child0_sp && |
389 | (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc)) |
390 | potential_child_sp = child0_sp->Clone(new_name: ConstString(name.GetString())); |
391 | break; |
392 | } |
393 | case 2: { |
394 | auto child0_sp = potential_child_sp->GetChildAtIndex(idx: 0); |
395 | auto child1_sp = potential_child_sp->GetChildAtIndex(idx: 1); |
396 | if (child0_sp && |
397 | (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) && |
398 | child1_sp && child1_sp->GetName() == g_nc) |
399 | potential_child_sp = child0_sp->Clone(new_name: ConstString(name.GetString())); |
400 | break; |
401 | } |
402 | } |
403 | } |
404 | m_iterators[idx] = iterator; |
405 | return potential_child_sp; |
406 | } |
407 | |
408 | lldb::ChildCacheState |
409 | lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() { |
410 | m_count = UINT32_MAX; |
411 | m_tree = m_root_node = nullptr; |
412 | m_iterators.clear(); |
413 | m_tree = m_backend.GetChildMemberWithName(name: "__tree_" ).get(); |
414 | if (!m_tree) |
415 | return lldb::ChildCacheState::eRefetch; |
416 | m_root_node = m_tree->GetChildMemberWithName(name: "__begin_node_" ).get(); |
417 | return lldb::ChildCacheState::eRefetch; |
418 | } |
419 | |
420 | bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: |
421 | MightHaveChildren() { |
422 | return true; |
423 | } |
424 | |
425 | size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: |
426 | GetIndexOfChildWithName(ConstString name) { |
427 | return ExtractIndexFromString(item_name: name.GetCString()); |
428 | } |
429 | |
430 | SyntheticChildrenFrontEnd * |
431 | lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator( |
432 | CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { |
433 | return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr); |
434 | } |
435 | |