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) {}
MapEntry(ValueObject * entry)29 explicit MapEntry(ValueObject *entry)
30 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
31
left() const32 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 0, m_entry_sp->GetCompilerType(), true);
38 }
39
right() const40 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 m_entry_sp->GetProcessSP()->GetAddressByteSize(),
46 m_entry_sp->GetCompilerType(), true);
47 }
48
parent() const49 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 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(),
55 m_entry_sp->GetCompilerType(), true);
56 }
57
value() const58 uint64_t value() const {
59 if (!m_entry_sp)
60 return 0;
61 return m_entry_sp->GetValueAsUnsigned(0);
62 }
63
error() const64 bool error() const {
65 if (!m_entry_sp)
66 return true;
67 return m_entry_sp->GetError().Fail();
68 }
69
null() const70 bool null() const { return (value() == 0); }
71
GetEntry() const72 ValueObjectSP GetEntry() const { return m_entry_sp; }
73
SetEntry(ValueObjectSP entry)74 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
75
operator ==(const MapEntry & rhs) const76 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;
MapIterator(MapEntry entry,size_t depth=0)87 MapIterator(MapEntry entry, size_t depth = 0)
88 : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {}
MapIterator(ValueObjectSP entry,size_t depth=0)89 MapIterator(ValueObjectSP entry, size_t depth = 0)
90 : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {}
MapIterator(const MapIterator & rhs)91 MapIterator(const MapIterator &rhs)
92 : m_entry(rhs.m_entry), m_max_depth(rhs.m_max_depth), m_error(false) {}
MapIterator(ValueObject * entry,size_t depth=0)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
value()98 ValueObjectSP value() { return m_entry.GetEntry(); }
99
advance(size_t count)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:
next()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(std::move(right));
121 return;
122 }
123 size_t steps = 0;
124 while (!is_left_child(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:
tree_min(MapEntry x)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
is_left_child(const MapEntry & x)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 size_t CalculateNumChildren() override;
181
182 lldb::ValueObjectSP GetChildAtIndex(size_t idx) override;
183
184 bool 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::
LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)206 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
207 : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(), m_iterators() {
208 if (valobj_sp)
209 Update();
210 }
211
212 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
CalculateNumChildren()213 CalculateNumChildren() {
214 if (m_count != UINT32_MAX)
215 return m_count;
216 if (m_tree == nullptr)
217 return 0;
218 ValueObjectSP m_item(m_tree->GetChildMemberWithName("__pair3_"));
219 if (!m_item)
220 return 0;
221
222 switch (m_item->GetCompilerType().GetNumDirectBaseClasses()) {
223 case 1:
224 // Assume a pre llvm r300140 __compressed_pair implementation:
225 m_item = m_item->GetChildMemberWithName("__first_");
226 break;
227 case 2: {
228 // Assume a post llvm r300140 __compressed_pair implementation:
229 ValueObjectSP first_elem_parent = m_item->GetChildAtIndex(0);
230 m_item = first_elem_parent->GetChildMemberWithName("__value_");
231 break;
232 }
233 default:
234 return false;
235 }
236
237 if (!m_item)
238 return 0;
239 m_count = m_item->GetValueAsUnsigned(0);
240 return m_count;
241 }
242
GetDataType()243 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() {
244 if (m_element_type.IsValid())
245 return true;
246 m_element_type.Clear();
247 ValueObjectSP deref;
248 Status error;
249 deref = m_root_node->Dereference(error);
250 if (!deref || error.Fail())
251 return false;
252 deref = deref->GetChildMemberWithName("__value_");
253 if (deref) {
254 m_element_type = deref->GetCompilerType();
255 return true;
256 }
257 deref = m_backend.GetChildAtNamePath({"__tree_", "__pair3_"});
258 if (!deref)
259 return false;
260 m_element_type = deref->GetCompilerType()
261 .GetTypeTemplateArgument(1)
262 .GetTypeTemplateArgument(1);
263 if (m_element_type) {
264 std::string name;
265 uint64_t bit_offset_ptr;
266 uint32_t bitfield_bit_size_ptr;
267 bool is_bitfield_ptr;
268 m_element_type = m_element_type.GetFieldAtIndex(
269 0, name, &bit_offset_ptr, &bitfield_bit_size_ptr, &is_bitfield_ptr);
270 m_element_type = m_element_type.GetTypedefedType();
271 return m_element_type.IsValid();
272 } else {
273 m_element_type = m_backend.GetCompilerType().GetTypeTemplateArgument(0);
274 return m_element_type.IsValid();
275 }
276 }
277
GetValueOffset(const lldb::ValueObjectSP & node)278 void lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset(
279 const lldb::ValueObjectSP &node) {
280 if (m_skip_size != UINT32_MAX)
281 return;
282 if (!node)
283 return;
284 CompilerType node_type(node->GetCompilerType());
285 uint64_t bit_offset;
286 if (node_type.GetIndexOfFieldWithName("__value_", nullptr, &bit_offset) !=
287 UINT32_MAX) {
288 m_skip_size = bit_offset / 8u;
289 } else {
290 auto ast_ctx = node_type.GetTypeSystem().dyn_cast_or_null<TypeSystemClang>();
291 if (!ast_ctx)
292 return;
293 CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier(
294 llvm::StringRef(),
295 {{"ptr0", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},
296 {"ptr1", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},
297 {"ptr2", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},
298 {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)},
299 {"payload", (m_element_type.GetCompleteType(), m_element_type)}});
300 std::string child_name;
301 uint32_t child_byte_size;
302 int32_t child_byte_offset = 0;
303 uint32_t child_bitfield_bit_size;
304 uint32_t child_bitfield_bit_offset;
305 bool child_is_base_class;
306 bool child_is_deref_of_parent;
307 uint64_t language_flags;
308 if (tree_node_type
309 .GetChildCompilerTypeAtIndex(
310 nullptr, 4, true, true, true, child_name, child_byte_size,
311 child_byte_offset, child_bitfield_bit_size,
312 child_bitfield_bit_offset, child_is_base_class,
313 child_is_deref_of_parent, nullptr, language_flags)
314 .IsValid())
315 m_skip_size = (uint32_t)child_byte_offset;
316 }
317 }
318
319 lldb::ValueObjectSP
GetChildAtIndex(size_t idx)320 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex(
321 size_t idx) {
322 static ConstString g_cc_("__cc_"), g_cc("__cc");
323 static ConstString g_nc("__nc");
324
325 if (idx >= CalculateNumChildren())
326 return lldb::ValueObjectSP();
327 if (m_tree == nullptr || m_root_node == nullptr)
328 return lldb::ValueObjectSP();
329
330 MapIterator iterator(m_root_node, CalculateNumChildren());
331
332 const bool need_to_skip = (idx > 0);
333 size_t actual_advancde = idx;
334 if (need_to_skip) {
335 auto cached_iterator = m_iterators.find(idx - 1);
336 if (cached_iterator != m_iterators.end()) {
337 iterator = cached_iterator->second;
338 actual_advancde = 1;
339 }
340 }
341
342 ValueObjectSP iterated_sp(iterator.advance(actual_advancde));
343 if (!iterated_sp) {
344 // this tree is garbage - stop
345 m_tree =
346 nullptr; // this will stop all future searches until an Update() happens
347 return iterated_sp;
348 }
349 if (GetDataType()) {
350 if (!need_to_skip) {
351 Status error;
352 iterated_sp = iterated_sp->Dereference(error);
353 if (!iterated_sp || error.Fail()) {
354 m_tree = nullptr;
355 return lldb::ValueObjectSP();
356 }
357 GetValueOffset(iterated_sp);
358 auto child_sp = iterated_sp->GetChildMemberWithName("__value_");
359 if (child_sp)
360 iterated_sp = child_sp;
361 else
362 iterated_sp = iterated_sp->GetSyntheticChildAtOffset(
363 m_skip_size, m_element_type, true);
364 if (!iterated_sp) {
365 m_tree = nullptr;
366 return lldb::ValueObjectSP();
367 }
368 } else {
369 // because of the way our debug info is made, we need to read item 0
370 // first so that we can cache information used to generate other elements
371 if (m_skip_size == UINT32_MAX)
372 GetChildAtIndex(0);
373 if (m_skip_size == UINT32_MAX) {
374 m_tree = nullptr;
375 return lldb::ValueObjectSP();
376 }
377 iterated_sp = iterated_sp->GetSyntheticChildAtOffset(
378 m_skip_size, m_element_type, true);
379 if (!iterated_sp) {
380 m_tree = nullptr;
381 return lldb::ValueObjectSP();
382 }
383 }
384 } else {
385 m_tree = nullptr;
386 return lldb::ValueObjectSP();
387 }
388 // at this point we have a valid
389 // we need to copy current_sp into a new object otherwise we will end up with
390 // all items named __value_
391 StreamString name;
392 name.Printf("[%" PRIu64 "]", (uint64_t)idx);
393 auto potential_child_sp = iterated_sp->Clone(ConstString(name.GetString()));
394 if (potential_child_sp) {
395 switch (potential_child_sp->GetNumChildren()) {
396 case 1: {
397 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
398 if (child0_sp &&
399 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))
400 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
401 break;
402 }
403 case 2: {
404 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
405 auto child1_sp = potential_child_sp->GetChildAtIndex(1);
406 if (child0_sp &&
407 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&
408 child1_sp && child1_sp->GetName() == g_nc)
409 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
410 break;
411 }
412 }
413 }
414 m_iterators[idx] = iterator;
415 return potential_child_sp;
416 }
417
Update()418 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() {
419 m_count = UINT32_MAX;
420 m_tree = m_root_node = nullptr;
421 m_iterators.clear();
422 m_tree = m_backend.GetChildMemberWithName("__tree_").get();
423 if (!m_tree)
424 return false;
425 m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get();
426 return false;
427 }
428
429 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
MightHaveChildren()430 MightHaveChildren() {
431 return true;
432 }
433
434 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)435 GetIndexOfChildWithName(ConstString name) {
436 return ExtractIndexFromString(name.GetCString());
437 }
438
439 SyntheticChildrenFrontEnd *
LibcxxStdMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)440 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
441 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
442 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
443 }
444