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