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/DataFormatters/FormattersHelpers.h"
13#include "lldb/Target/Target.h"
14#include "lldb/Utility/DataBufferHeap.h"
15#include "lldb/Utility/Endian.h"
16#include "lldb/Utility/Status.h"
17#include "lldb/Utility/Stream.h"
18#include "lldb/ValueObject/ValueObject.h"
19#include "lldb/ValueObject/ValueObjectConstResult.h"
20#include "lldb/lldb-enumerations.h"
21#include "lldb/lldb-forward.h"
22#include <cstdint>
23#include <locale>
24#include <optional>
25
26using namespace lldb;
27using namespace lldb_private;
28using namespace lldb_private::formatters;
29
30// The flattened layout of the std::__tree_iterator::__ptr_ looks
31// as follows:
32//
33// The following shows the contiguous block of memory:
34//
35// +-----------------------------+ class __tree_end_node
36// __ptr_ | pointer __left_; |
37// +-----------------------------+ class __tree_node_base
38// | pointer __right_; |
39// | __parent_pointer __parent_; |
40// | bool __is_black_; |
41// +-----------------------------+ class __tree_node
42// | __node_value_type __value_; | <<< our key/value pair
43// +-----------------------------+
44//
45// where __ptr_ has type __iter_pointer.
46
47class MapEntry {
48public:
49 MapEntry() = default;
50 explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
51 explicit MapEntry(ValueObject *entry)
52 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
53
54 ValueObjectSP left() const {
55 if (!m_entry_sp)
56 return m_entry_sp;
57 return m_entry_sp->GetSyntheticChildAtOffset(
58 offset: 0, type: m_entry_sp->GetCompilerType(), can_create: true);
59 }
60
61 ValueObjectSP right() const {
62 if (!m_entry_sp)
63 return m_entry_sp;
64 return m_entry_sp->GetSyntheticChildAtOffset(
65 offset: m_entry_sp->GetProcessSP()->GetAddressByteSize(),
66 type: m_entry_sp->GetCompilerType(), can_create: true);
67 }
68
69 ValueObjectSP parent() const {
70 if (!m_entry_sp)
71 return m_entry_sp;
72 return m_entry_sp->GetSyntheticChildAtOffset(
73 offset: 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(),
74 type: m_entry_sp->GetCompilerType(), can_create: true);
75 }
76
77 uint64_t value() const {
78 if (!m_entry_sp)
79 return 0;
80 return m_entry_sp->GetValueAsUnsigned(fail_value: 0);
81 }
82
83 bool error() const {
84 if (!m_entry_sp)
85 return true;
86 return m_entry_sp->GetError().Fail();
87 }
88
89 bool null() const { return (value() == 0); }
90
91 ValueObjectSP GetEntry() const { return m_entry_sp; }
92
93 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
94
95 bool operator==(const MapEntry &rhs) const {
96 return (rhs.m_entry_sp.get() == m_entry_sp.get());
97 }
98
99private:
100 ValueObjectSP m_entry_sp;
101};
102
103class MapIterator {
104public:
105 MapIterator(ValueObject *entry, size_t depth = 0)
106 : m_entry(entry), m_max_depth(depth), m_error(false) {}
107
108 MapIterator() = default;
109
110 ValueObjectSP value() { return m_entry.GetEntry(); }
111
112 ValueObjectSP advance(size_t count) {
113 ValueObjectSP fail;
114 if (m_error)
115 return fail;
116 size_t steps = 0;
117 while (count > 0) {
118 next();
119 count--, steps++;
120 if (m_error || m_entry.null() || (steps > m_max_depth))
121 return fail;
122 }
123 return m_entry.GetEntry();
124 }
125
126private:
127 /// Mimicks libc++'s __tree_next algorithm, which libc++ uses
128 /// in its __tree_iteartor::operator++.
129 void next() {
130 if (m_entry.null())
131 return;
132 MapEntry right(m_entry.right());
133 if (!right.null()) {
134 m_entry = tree_min(x: std::move(right));
135 return;
136 }
137 size_t steps = 0;
138 while (!is_left_child(x: m_entry)) {
139 if (m_entry.error()) {
140 m_error = true;
141 return;
142 }
143 m_entry.SetEntry(m_entry.parent());
144 steps++;
145 if (steps > m_max_depth) {
146 m_entry = MapEntry();
147 return;
148 }
149 }
150 m_entry = MapEntry(m_entry.parent());
151 }
152
153 /// Mimicks libc++'s __tree_min algorithm.
154 MapEntry tree_min(MapEntry x) {
155 if (x.null())
156 return MapEntry();
157 MapEntry left(x.left());
158 size_t steps = 0;
159 while (!left.null()) {
160 if (left.error()) {
161 m_error = true;
162 return MapEntry();
163 }
164 x = left;
165 left.SetEntry(x.left());
166 steps++;
167 if (steps > m_max_depth)
168 return MapEntry();
169 }
170 return x;
171 }
172
173 bool is_left_child(const MapEntry &x) {
174 if (x.null())
175 return false;
176 MapEntry rhs(x.parent());
177 rhs.SetEntry(rhs.left());
178 return x.value() == rhs.value();
179 }
180
181 MapEntry m_entry;
182 size_t m_max_depth = 0;
183 bool m_error = false;
184};
185
186namespace lldb_private {
187namespace formatters {
188class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
189public:
190 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
191
192 ~LibcxxStdMapSyntheticFrontEnd() override = default;
193
194 llvm::Expected<uint32_t> CalculateNumChildren() override;
195
196 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
197
198 lldb::ChildCacheState Update() override;
199
200 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override;
201
202private:
203 llvm::Expected<uint32_t> CalculateNumChildrenForOldCompressedPairLayout();
204
205 /// Returns the ValueObject for the __tree_node type that
206 /// holds the key/value pair of the node at index \ref idx.
207 ///
208 /// \param[in] idx The child index that we're looking to get
209 /// the key/value pair for.
210 ///
211 /// \param[in] max_depth The maximum search depth after which
212 /// we stop trying to find the key/value
213 /// pair for.
214 ///
215 /// \returns On success, returns the ValueObjectSP corresponding
216 /// to the __tree_node's __value_ member (which holds
217 /// the key/value pair the formatter wants to display).
218 /// On failure, will return nullptr.
219 ValueObjectSP GetKeyValuePair(size_t idx, size_t max_depth);
220
221 ValueObject *m_tree = nullptr;
222 ValueObject *m_root_node = nullptr;
223 CompilerType m_node_ptr_type;
224 size_t m_count = UINT32_MAX;
225 std::map<size_t, MapIterator> m_iterators;
226};
227
228class LibCxxMapIteratorSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
229public:
230 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
231
232 llvm::Expected<uint32_t> CalculateNumChildren() override;
233
234 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
235
236 lldb::ChildCacheState Update() override;
237
238 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override;
239
240 ~LibCxxMapIteratorSyntheticFrontEnd() override = default;
241
242private:
243 ValueObjectSP m_pair_sp = nullptr;
244};
245} // namespace formatters
246} // namespace lldb_private
247
248lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
249 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
250 : SyntheticChildrenFrontEnd(*valobj_sp) {
251 if (valobj_sp)
252 Update();
253}
254
255llvm::Expected<uint32_t>
256lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
257 CalculateNumChildrenForOldCompressedPairLayout() {
258 ValueObjectSP node_sp(m_tree->GetChildMemberWithName(name: "__pair3_"));
259 if (!node_sp)
260 return 0;
261
262 if (!isOldCompressedPairLayout(pair_obj&: *node_sp))
263 return llvm::createStringError(Fmt: "Unexpected std::map layout: expected "
264 "old __compressed_pair layout.");
265
266 node_sp = GetFirstValueOfLibCXXCompressedPair(pair&: *node_sp);
267
268 if (!node_sp)
269 return 0;
270
271 m_count = node_sp->GetValueAsUnsigned(fail_value: 0);
272
273 return m_count;
274}
275
276llvm::Expected<uint32_t> lldb_private::formatters::
277 LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren() {
278 if (m_count != UINT32_MAX)
279 return m_count;
280
281 if (m_tree == nullptr)
282 return 0;
283
284 if (auto node_sp = m_tree->GetChildMemberWithName(name: "__size_")) {
285 m_count = node_sp->GetValueAsUnsigned(fail_value: 0);
286 return m_count;
287 }
288
289 return CalculateNumChildrenForOldCompressedPairLayout();
290}
291
292ValueObjectSP
293lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetKeyValuePair(
294 size_t idx, size_t max_depth) {
295 MapIterator iterator(m_root_node, max_depth);
296
297 size_t advance_by = idx;
298 if (idx > 0) {
299 // If we have already created the iterator for the previous
300 // index, we can start from there and advance by 1.
301 auto cached_iterator = m_iterators.find(x: idx - 1);
302 if (cached_iterator != m_iterators.end()) {
303 iterator = cached_iterator->second;
304 advance_by = 1;
305 }
306 }
307
308 ValueObjectSP iterated_sp(iterator.advance(count: advance_by));
309 if (!iterated_sp)
310 // this tree is garbage - stop
311 return nullptr;
312
313 if (!m_node_ptr_type.IsValid())
314 return nullptr;
315
316 // iterated_sp is a __iter_pointer at this point.
317 // We can cast it to a __node_pointer (which is what libc++ does).
318 auto value_type_sp = iterated_sp->Cast(compiler_type: m_node_ptr_type);
319 if (!value_type_sp)
320 return nullptr;
321
322 // Finally, get the key/value pair.
323 value_type_sp = value_type_sp->GetChildMemberWithName(name: "__value_");
324 if (!value_type_sp)
325 return nullptr;
326
327 m_iterators[idx] = iterator;
328
329 return value_type_sp;
330}
331
332lldb::ValueObjectSP
333lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex(
334 uint32_t idx) {
335 static ConstString g_cc_("__cc_"), g_cc("__cc");
336 static ConstString g_nc("__nc");
337 uint32_t num_children = CalculateNumChildrenIgnoringErrors();
338 if (idx >= num_children)
339 return nullptr;
340
341 if (m_tree == nullptr || m_root_node == nullptr)
342 return nullptr;
343
344 ValueObjectSP key_val_sp = GetKeyValuePair(idx, /*max_depth=*/num_children);
345 if (!key_val_sp) {
346 // this will stop all future searches until an Update() happens
347 m_tree = nullptr;
348 return nullptr;
349 }
350
351 // at this point we have a valid
352 // we need to copy current_sp into a new object otherwise we will end up with
353 // all items named __value_
354 StreamString name;
355 name.Printf(format: "[%" PRIu64 "]", (uint64_t)idx);
356 auto potential_child_sp = key_val_sp->Clone(new_name: ConstString(name.GetString()));
357 if (potential_child_sp) {
358 switch (potential_child_sp->GetNumChildrenIgnoringErrors()) {
359 case 1: {
360 auto child0_sp = potential_child_sp->GetChildAtIndex(idx: 0);
361 if (child0_sp &&
362 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))
363 potential_child_sp = child0_sp->Clone(new_name: ConstString(name.GetString()));
364 break;
365 }
366 case 2: {
367 auto child0_sp = potential_child_sp->GetChildAtIndex(idx: 0);
368 auto child1_sp = potential_child_sp->GetChildAtIndex(idx: 1);
369 if (child0_sp &&
370 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&
371 child1_sp && child1_sp->GetName() == g_nc)
372 potential_child_sp = child0_sp->Clone(new_name: ConstString(name.GetString()));
373 break;
374 }
375 }
376 }
377 return potential_child_sp;
378}
379
380lldb::ChildCacheState
381lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() {
382 m_count = UINT32_MAX;
383 m_tree = m_root_node = nullptr;
384 m_iterators.clear();
385 m_tree = m_backend.GetChildMemberWithName(name: "__tree_").get();
386 if (!m_tree)
387 return lldb::ChildCacheState::eRefetch;
388
389 m_root_node = m_tree->GetChildMemberWithName(name: "__begin_node_").get();
390 m_node_ptr_type =
391 m_tree->GetCompilerType().GetDirectNestedTypeWithName(name: "__node_pointer");
392
393 return lldb::ChildCacheState::eRefetch;
394}
395
396llvm::Expected<size_t> lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
397 GetIndexOfChildWithName(ConstString name) {
398 auto optional_idx = formatters::ExtractIndexFromString(item_name: name.GetCString());
399 if (!optional_idx) {
400 return llvm::createStringError(Fmt: "Type has no child named '%s'",
401 Vals: name.AsCString());
402 }
403 return *optional_idx;
404}
405
406SyntheticChildrenFrontEnd *
407lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
408 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
409 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
410}
411
412lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
413 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
414 : SyntheticChildrenFrontEnd(*valobj_sp) {
415 if (valobj_sp)
416 Update();
417}
418
419lldb::ChildCacheState
420lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::Update() {
421 m_pair_sp.reset();
422
423 ValueObjectSP valobj_sp = m_backend.GetSP();
424 if (!valobj_sp)
425 return lldb::ChildCacheState::eRefetch;
426
427 TargetSP target_sp(valobj_sp->GetTargetSP());
428 if (!target_sp)
429 return lldb::ChildCacheState::eRefetch;
430
431 // m_backend is a std::map::iterator
432 // ...which is a __map_iterator<__tree_iterator<..., __node_pointer, ...>>
433 //
434 // Then, __map_iterator::__i_ is a __tree_iterator
435 auto tree_iter_sp = valobj_sp->GetChildMemberWithName(name: "__i_");
436 if (!tree_iter_sp)
437 return lldb::ChildCacheState::eRefetch;
438
439 // Type is __tree_iterator::__node_pointer
440 // (We could alternatively also get this from the template argument)
441 auto node_pointer_type =
442 tree_iter_sp->GetCompilerType().GetDirectNestedTypeWithName(
443 name: "__node_pointer");
444 if (!node_pointer_type.IsValid())
445 return lldb::ChildCacheState::eRefetch;
446
447 // __ptr_ is a __tree_iterator::__iter_pointer
448 auto iter_pointer_sp = tree_iter_sp->GetChildMemberWithName(name: "__ptr_");
449 if (!iter_pointer_sp)
450 return lldb::ChildCacheState::eRefetch;
451
452 // Cast the __iter_pointer to a __node_pointer (which stores our key/value
453 // pair)
454 auto node_pointer_sp = iter_pointer_sp->Cast(compiler_type: node_pointer_type);
455 if (!node_pointer_sp)
456 return lldb::ChildCacheState::eRefetch;
457
458 auto key_value_sp = node_pointer_sp->GetChildMemberWithName(name: "__value_");
459 if (!key_value_sp)
460 return lldb::ChildCacheState::eRefetch;
461
462 // Create the synthetic child, which is a pair where the key and value can be
463 // retrieved by querying the synthetic frontend for
464 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
465 // respectively.
466 //
467 // std::map stores the actual key/value pair in value_type::__cc_ (or
468 // previously __cc).
469 key_value_sp = key_value_sp->Clone(new_name: ConstString("pair"));
470 if (key_value_sp->GetNumChildrenIgnoringErrors() == 1) {
471 auto child0_sp = key_value_sp->GetChildAtIndex(idx: 0);
472 if (child0_sp &&
473 (child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc"))
474 key_value_sp = child0_sp->Clone(new_name: ConstString("pair"));
475 }
476
477 m_pair_sp = key_value_sp;
478
479 return lldb::ChildCacheState::eRefetch;
480}
481
482llvm::Expected<uint32_t> lldb_private::formatters::
483 LibCxxMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
484 return 2;
485}
486
487lldb::ValueObjectSP
488lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::GetChildAtIndex(
489 uint32_t idx) {
490 if (!m_pair_sp)
491 return nullptr;
492
493 return m_pair_sp->GetChildAtIndex(idx);
494}
495
496llvm::Expected<size_t>
497lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
498 GetIndexOfChildWithName(ConstString name) {
499 if (!m_pair_sp)
500 return llvm::createStringError(Fmt: "Type has no child named '%s'",
501 Vals: name.AsCString());
502
503 return m_pair_sp->GetIndexOfChildWithName(name);
504}
505
506SyntheticChildrenFrontEnd *
507lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEndCreator(
508 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
509 return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp)
510 : nullptr);
511}
512

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