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
26 using namespace lldb;
27 using namespace lldb_private;
28 using 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
47 class MapEntry {
48 public:
49 MapEntry() = default;
MapEntry(ValueObjectSP entry_sp)50 explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
MapEntry(ValueObject * entry)51 explicit MapEntry(ValueObject *entry)
52 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
53
left() const54 ValueObjectSP left() const {
55 if (!m_entry_sp)
56 return m_entry_sp;
57 return m_entry_sp->GetSyntheticChildAtOffset(
58 0, m_entry_sp->GetCompilerType(), true);
59 }
60
right() const61 ValueObjectSP right() const {
62 if (!m_entry_sp)
63 return m_entry_sp;
64 return m_entry_sp->GetSyntheticChildAtOffset(
65 m_entry_sp->GetProcessSP()->GetAddressByteSize(),
66 m_entry_sp->GetCompilerType(), true);
67 }
68
parent() const69 ValueObjectSP parent() const {
70 if (!m_entry_sp)
71 return m_entry_sp;
72 return m_entry_sp->GetSyntheticChildAtOffset(
73 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(),
74 m_entry_sp->GetCompilerType(), true);
75 }
76
value() const77 uint64_t value() const {
78 if (!m_entry_sp)
79 return 0;
80 return m_entry_sp->GetValueAsUnsigned(0);
81 }
82
error() const83 bool error() const {
84 if (!m_entry_sp)
85 return true;
86 return m_entry_sp->GetError().Fail();
87 }
88
null() const89 bool null() const { return (value() == 0); }
90
GetEntry() const91 ValueObjectSP GetEntry() const { return m_entry_sp; }
92
SetEntry(ValueObjectSP entry)93 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
94
operator ==(const MapEntry & rhs) const95 bool operator==(const MapEntry &rhs) const {
96 return (rhs.m_entry_sp.get() == m_entry_sp.get());
97 }
98
99 private:
100 ValueObjectSP m_entry_sp;
101 };
102
103 class MapIterator {
104 public:
MapIterator(ValueObject * entry,size_t depth=0)105 MapIterator(ValueObject *entry, size_t depth = 0)
106 : m_entry(entry), m_max_depth(depth), m_error(false) {}
107
108 MapIterator() = default;
109
value()110 ValueObjectSP value() { return m_entry.GetEntry(); }
111
advance(size_t count)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
126 private:
127 /// Mimicks libc++'s __tree_next algorithm, which libc++ uses
128 /// in its __tree_iteartor::operator++.
next()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(std::move(right));
135 return;
136 }
137 size_t steps = 0;
138 while (!is_left_child(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.
tree_min(MapEntry x)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
is_left_child(const MapEntry & x)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
186 namespace lldb_private {
187 namespace formatters {
188 class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
189 public:
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
202 private:
203 llvm::Expected<uint32_t>
204 CalculateNumChildrenForOldCompressedPairLayout(ValueObject &pair);
205
206 /// Returns the ValueObject for the __tree_node type that
207 /// holds the key/value pair of the node at index \ref idx.
208 ///
209 /// \param[in] idx The child index that we're looking to get
210 /// the key/value pair for.
211 ///
212 /// \param[in] max_depth The maximum search depth after which
213 /// we stop trying to find the key/value
214 /// pair for.
215 ///
216 /// \returns On success, returns the ValueObjectSP corresponding
217 /// to the __tree_node's __value_ member (which holds
218 /// the key/value pair the formatter wants to display).
219 /// On failure, will return nullptr.
220 ValueObjectSP GetKeyValuePair(size_t idx, size_t max_depth);
221
222 ValueObject *m_tree = nullptr;
223 ValueObject *m_root_node = nullptr;
224 CompilerType m_node_ptr_type;
225 size_t m_count = UINT32_MAX;
226 std::map<size_t, MapIterator> m_iterators;
227 };
228
229 class LibCxxMapIteratorSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
230 public:
231 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
232
233 llvm::Expected<uint32_t> CalculateNumChildren() override;
234
235 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
236
237 lldb::ChildCacheState Update() override;
238
239 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override;
240
241 ~LibCxxMapIteratorSyntheticFrontEnd() override = default;
242
243 private:
244 ValueObjectSP m_pair_sp = nullptr;
245 };
246 } // namespace formatters
247 } // namespace lldb_private
248
249 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)250 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
251 : SyntheticChildrenFrontEnd(*valobj_sp) {
252 if (valobj_sp)
253 Update();
254 }
255
256 llvm::Expected<uint32_t>
257 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
CalculateNumChildrenForOldCompressedPairLayout(ValueObject & pair)258 CalculateNumChildrenForOldCompressedPairLayout(ValueObject &pair) {
259 auto node_sp = GetFirstValueOfLibCXXCompressedPair(pair);
260
261 if (!node_sp)
262 return 0;
263
264 m_count = node_sp->GetValueAsUnsigned(0);
265
266 return m_count;
267 }
268
269 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()270 LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren() {
271 if (m_count != UINT32_MAX)
272 return m_count;
273
274 if (m_tree == nullptr)
275 return 0;
276
277 auto [size_sp, is_compressed_pair] = GetValueOrOldCompressedPair(
278 *m_tree, /*anon_struct_idx=*/2, "__size_", "__pair3_");
279 if (!size_sp)
280 return llvm::createStringError("Unexpected std::map layout");
281
282 if (is_compressed_pair)
283 return CalculateNumChildrenForOldCompressedPairLayout(*size_sp);
284
285 m_count = size_sp->GetValueAsUnsigned(0);
286 return m_count;
287 }
288
289 ValueObjectSP
GetKeyValuePair(size_t idx,size_t max_depth)290 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetKeyValuePair(
291 size_t idx, size_t max_depth) {
292 MapIterator iterator(m_root_node, max_depth);
293
294 size_t advance_by = idx;
295 if (idx > 0) {
296 // If we have already created the iterator for the previous
297 // index, we can start from there and advance by 1.
298 auto cached_iterator = m_iterators.find(idx - 1);
299 if (cached_iterator != m_iterators.end()) {
300 iterator = cached_iterator->second;
301 advance_by = 1;
302 }
303 }
304
305 ValueObjectSP iterated_sp(iterator.advance(advance_by));
306 if (!iterated_sp)
307 // this tree is garbage - stop
308 return nullptr;
309
310 if (!m_node_ptr_type.IsValid())
311 return nullptr;
312
313 // iterated_sp is a __iter_pointer at this point.
314 // We can cast it to a __node_pointer (which is what libc++ does).
315 auto value_type_sp = iterated_sp->Cast(m_node_ptr_type);
316 if (!value_type_sp)
317 return nullptr;
318
319 // Finally, get the key/value pair.
320 value_type_sp = value_type_sp->GetChildMemberWithName("__value_");
321 if (!value_type_sp)
322 return nullptr;
323
324 m_iterators[idx] = iterator;
325
326 return value_type_sp;
327 }
328
329 lldb::ValueObjectSP
GetChildAtIndex(uint32_t idx)330 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex(
331 uint32_t idx) {
332 static ConstString g_cc_("__cc_"), g_cc("__cc");
333 static ConstString g_nc("__nc");
334 uint32_t num_children = CalculateNumChildrenIgnoringErrors();
335 if (idx >= num_children)
336 return nullptr;
337
338 if (m_tree == nullptr || m_root_node == nullptr)
339 return nullptr;
340
341 ValueObjectSP key_val_sp = GetKeyValuePair(idx, /*max_depth=*/num_children);
342 if (!key_val_sp) {
343 // this will stop all future searches until an Update() happens
344 m_tree = nullptr;
345 return nullptr;
346 }
347
348 // at this point we have a valid
349 // we need to copy current_sp into a new object otherwise we will end up with
350 // all items named __value_
351 StreamString name;
352 name.Printf("[%" PRIu64 "]", (uint64_t)idx);
353 auto potential_child_sp = key_val_sp->Clone(ConstString(name.GetString()));
354 if (potential_child_sp) {
355 switch (potential_child_sp->GetNumChildrenIgnoringErrors()) {
356 case 1: {
357 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
358 if (child0_sp &&
359 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))
360 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
361 break;
362 }
363 case 2: {
364 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
365 auto child1_sp = potential_child_sp->GetChildAtIndex(1);
366 if (child0_sp &&
367 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&
368 child1_sp && child1_sp->GetName() == g_nc)
369 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
370 break;
371 }
372 }
373 }
374 return potential_child_sp;
375 }
376
377 lldb::ChildCacheState
Update()378 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() {
379 m_count = UINT32_MAX;
380 m_tree = m_root_node = nullptr;
381 m_iterators.clear();
382 m_tree = m_backend.GetChildMemberWithName("__tree_").get();
383 if (!m_tree)
384 return lldb::ChildCacheState::eRefetch;
385
386 m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get();
387 m_node_ptr_type =
388 m_tree->GetCompilerType().GetDirectNestedTypeWithName("__node_pointer");
389
390 return lldb::ChildCacheState::eRefetch;
391 }
392
393 llvm::Expected<size_t> lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)394 GetIndexOfChildWithName(ConstString name) {
395 auto optional_idx = formatters::ExtractIndexFromString(name.GetCString());
396 if (!optional_idx) {
397 return llvm::createStringError("Type has no child named '%s'",
398 name.AsCString());
399 }
400 return *optional_idx;
401 }
402
403 SyntheticChildrenFrontEnd *
LibcxxStdMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)404 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
405 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
406 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
407 }
408
409 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)410 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
411 : SyntheticChildrenFrontEnd(*valobj_sp) {
412 if (valobj_sp)
413 Update();
414 }
415
416 lldb::ChildCacheState
Update()417 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::Update() {
418 m_pair_sp.reset();
419
420 ValueObjectSP valobj_sp = m_backend.GetSP();
421 if (!valobj_sp)
422 return lldb::ChildCacheState::eRefetch;
423
424 TargetSP target_sp(valobj_sp->GetTargetSP());
425 if (!target_sp)
426 return lldb::ChildCacheState::eRefetch;
427
428 // m_backend is a std::map::iterator
429 // ...which is a __map_iterator<__tree_iterator<..., __node_pointer, ...>>
430 //
431 // Then, __map_iterator::__i_ is a __tree_iterator
432 auto tree_iter_sp = valobj_sp->GetChildMemberWithName("__i_");
433 if (!tree_iter_sp)
434 return lldb::ChildCacheState::eRefetch;
435
436 // Type is __tree_iterator::__node_pointer
437 // (We could alternatively also get this from the template argument)
438 auto node_pointer_type =
439 tree_iter_sp->GetCompilerType().GetDirectNestedTypeWithName(
440 "__node_pointer");
441 if (!node_pointer_type.IsValid())
442 return lldb::ChildCacheState::eRefetch;
443
444 // __ptr_ is a __tree_iterator::__iter_pointer
445 auto iter_pointer_sp = tree_iter_sp->GetChildMemberWithName("__ptr_");
446 if (!iter_pointer_sp)
447 return lldb::ChildCacheState::eRefetch;
448
449 // Cast the __iter_pointer to a __node_pointer (which stores our key/value
450 // pair)
451 auto node_pointer_sp = iter_pointer_sp->Cast(node_pointer_type);
452 if (!node_pointer_sp)
453 return lldb::ChildCacheState::eRefetch;
454
455 auto key_value_sp = node_pointer_sp->GetChildMemberWithName("__value_");
456 if (!key_value_sp)
457 return lldb::ChildCacheState::eRefetch;
458
459 // Create the synthetic child, which is a pair where the key and value can be
460 // retrieved by querying the synthetic frontend for
461 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
462 // respectively.
463 //
464 // std::map stores the actual key/value pair in value_type::__cc_ (or
465 // previously __cc).
466 key_value_sp = key_value_sp->Clone(ConstString("pair"));
467 if (key_value_sp->GetNumChildrenIgnoringErrors() == 1) {
468 auto child0_sp = key_value_sp->GetChildAtIndex(0);
469 if (child0_sp &&
470 (child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc"))
471 key_value_sp = child0_sp->Clone(ConstString("pair"));
472 }
473
474 m_pair_sp = key_value_sp;
475
476 return lldb::ChildCacheState::eRefetch;
477 }
478
479 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()480 LibCxxMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
481 return 2;
482 }
483
484 lldb::ValueObjectSP
GetChildAtIndex(uint32_t idx)485 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::GetChildAtIndex(
486 uint32_t idx) {
487 if (!m_pair_sp)
488 return nullptr;
489
490 return m_pair_sp->GetChildAtIndex(idx);
491 }
492
493 llvm::Expected<size_t>
494 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)495 GetIndexOfChildWithName(ConstString name) {
496 if (!m_pair_sp)
497 return llvm::createStringError("Type has no child named '%s'",
498 name.AsCString());
499
500 return m_pair_sp->GetIndexOfChildWithName(name);
501 }
502
503 SyntheticChildrenFrontEnd *
LibCxxMapIteratorSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)504 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEndCreator(
505 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
506 return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp)
507 : nullptr);
508 }
509