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
21using namespace lldb;
22using namespace lldb_private;
23using namespace lldb_private::formatters;
24
25class MapEntry {
26public:
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
80private:
81 ValueObjectSP m_entry_sp;
82};
83
84class MapIterator {
85public:
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
114protected:
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
139private:
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
172namespace lldb_private {
173namespace formatters {
174class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
175public:
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
190private:
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
205lldb_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
212llvm::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
233bool 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
268void 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
309lldb::ValueObjectSP
310lldb_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
408lldb::ChildCacheState
409lldb_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
420bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
421 MightHaveChildren() {
422 return true;
423}
424
425size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
426 GetIndexOfChildWithName(ConstString name) {
427 return ExtractIndexFromString(item_name: name.GetCString());
428}
429
430SyntheticChildrenFrontEnd *
431lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
432 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
433 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
434}
435

source code of lldb/source/Plugins/Language/CPlusPlus/LibCxxMap.cpp