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 #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 bool MightHaveChildren() override;
201
202 size_t GetIndexOfChildWithName(ConstString name) override;
203
204 private:
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
228 class LibCxxMapIteratorSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
229 public:
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 bool MightHaveChildren() override;
239
240 size_t GetIndexOfChildWithName(ConstString name) override;
241
242 ~LibCxxMapIteratorSyntheticFrontEnd() override = default;
243
244 private:
245 ValueObjectSP m_pair_sp = nullptr;
246 };
247 } // namespace formatters
248 } // namespace lldb_private
249
250 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)251 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
252 : SyntheticChildrenFrontEnd(*valobj_sp) {
253 if (valobj_sp)
254 Update();
255 }
256
257 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()258 LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren() {
259 if (m_count != UINT32_MAX)
260 return m_count;
261
262 if (m_tree == nullptr)
263 return 0;
264
265 ValueObjectSP size_node(m_tree->GetChildMemberWithName("__pair3_"));
266 if (!size_node)
267 return 0;
268
269 size_node = GetFirstValueOfLibCXXCompressedPair(*size_node);
270
271 if (!size_node)
272 return 0;
273
274 m_count = size_node->GetValueAsUnsigned(0);
275 return m_count;
276 }
277
278 ValueObjectSP
GetKeyValuePair(size_t idx,size_t max_depth)279 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetKeyValuePair(
280 size_t idx, size_t max_depth) {
281 MapIterator iterator(m_root_node, max_depth);
282
283 size_t advance_by = idx;
284 if (idx > 0) {
285 // If we have already created the iterator for the previous
286 // index, we can start from there and advance by 1.
287 auto cached_iterator = m_iterators.find(idx - 1);
288 if (cached_iterator != m_iterators.end()) {
289 iterator = cached_iterator->second;
290 advance_by = 1;
291 }
292 }
293
294 ValueObjectSP iterated_sp(iterator.advance(advance_by));
295 if (!iterated_sp)
296 // this tree is garbage - stop
297 return nullptr;
298
299 if (!m_node_ptr_type.IsValid())
300 return nullptr;
301
302 // iterated_sp is a __iter_pointer at this point.
303 // We can cast it to a __node_pointer (which is what libc++ does).
304 auto value_type_sp = iterated_sp->Cast(m_node_ptr_type);
305 if (!value_type_sp)
306 return nullptr;
307
308 // Finally, get the key/value pair.
309 value_type_sp = value_type_sp->GetChildMemberWithName("__value_");
310 if (!value_type_sp)
311 return nullptr;
312
313 m_iterators[idx] = iterator;
314
315 return value_type_sp;
316 }
317
318 lldb::ValueObjectSP
GetChildAtIndex(uint32_t idx)319 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex(
320 uint32_t idx) {
321 static ConstString g_cc_("__cc_"), g_cc("__cc");
322 static ConstString g_nc("__nc");
323 uint32_t num_children = CalculateNumChildrenIgnoringErrors();
324 if (idx >= num_children)
325 return nullptr;
326
327 if (m_tree == nullptr || m_root_node == nullptr)
328 return nullptr;
329
330 ValueObjectSP key_val_sp = GetKeyValuePair(idx, /*max_depth=*/num_children);
331 if (!key_val_sp) {
332 // this will stop all future searches until an Update() happens
333 m_tree = nullptr;
334 return nullptr;
335 }
336
337 // at this point we have a valid
338 // we need to copy current_sp into a new object otherwise we will end up with
339 // all items named __value_
340 StreamString name;
341 name.Printf("[%" PRIu64 "]", (uint64_t)idx);
342 auto potential_child_sp = key_val_sp->Clone(ConstString(name.GetString()));
343 if (potential_child_sp) {
344 switch (potential_child_sp->GetNumChildrenIgnoringErrors()) {
345 case 1: {
346 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
347 if (child0_sp &&
348 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))
349 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
350 break;
351 }
352 case 2: {
353 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
354 auto child1_sp = potential_child_sp->GetChildAtIndex(1);
355 if (child0_sp &&
356 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&
357 child1_sp && child1_sp->GetName() == g_nc)
358 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
359 break;
360 }
361 }
362 }
363 return potential_child_sp;
364 }
365
366 lldb::ChildCacheState
Update()367 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() {
368 m_count = UINT32_MAX;
369 m_tree = m_root_node = nullptr;
370 m_iterators.clear();
371 m_tree = m_backend.GetChildMemberWithName("__tree_").get();
372 if (!m_tree)
373 return lldb::ChildCacheState::eRefetch;
374 m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get();
375 m_node_ptr_type =
376 m_tree->GetCompilerType().GetDirectNestedTypeWithName("__node_pointer");
377
378 return lldb::ChildCacheState::eRefetch;
379 }
380
381 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
MightHaveChildren()382 MightHaveChildren() {
383 return true;
384 }
385
386 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)387 GetIndexOfChildWithName(ConstString name) {
388 return ExtractIndexFromString(name.GetCString());
389 }
390
391 SyntheticChildrenFrontEnd *
LibcxxStdMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)392 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
393 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
394 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
395 }
396
397 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)398 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
399 : SyntheticChildrenFrontEnd(*valobj_sp) {
400 if (valobj_sp)
401 Update();
402 }
403
404 lldb::ChildCacheState
Update()405 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::Update() {
406 m_pair_sp.reset();
407
408 ValueObjectSP valobj_sp = m_backend.GetSP();
409 if (!valobj_sp)
410 return lldb::ChildCacheState::eRefetch;
411
412 TargetSP target_sp(valobj_sp->GetTargetSP());
413 if (!target_sp)
414 return lldb::ChildCacheState::eRefetch;
415
416 // m_backend is a std::map::iterator
417 // ...which is a __map_iterator<__tree_iterator<..., __node_pointer, ...>>
418 //
419 // Then, __map_iterator::__i_ is a __tree_iterator
420 auto tree_iter_sp = valobj_sp->GetChildMemberWithName("__i_");
421 if (!tree_iter_sp)
422 return lldb::ChildCacheState::eRefetch;
423
424 // Type is __tree_iterator::__node_pointer
425 // (We could alternatively also get this from the template argument)
426 auto node_pointer_type =
427 tree_iter_sp->GetCompilerType().GetDirectNestedTypeWithName(
428 "__node_pointer");
429 if (!node_pointer_type.IsValid())
430 return lldb::ChildCacheState::eRefetch;
431
432 // __ptr_ is a __tree_iterator::__iter_pointer
433 auto iter_pointer_sp = tree_iter_sp->GetChildMemberWithName("__ptr_");
434 if (!iter_pointer_sp)
435 return lldb::ChildCacheState::eRefetch;
436
437 // Cast the __iter_pointer to a __node_pointer (which stores our key/value
438 // pair)
439 auto node_pointer_sp = iter_pointer_sp->Cast(node_pointer_type);
440 if (!node_pointer_sp)
441 return lldb::ChildCacheState::eRefetch;
442
443 auto key_value_sp = node_pointer_sp->GetChildMemberWithName("__value_");
444 if (!key_value_sp)
445 return lldb::ChildCacheState::eRefetch;
446
447 // Create the synthetic child, which is a pair where the key and value can be
448 // retrieved by querying the synthetic frontend for
449 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
450 // respectively.
451 //
452 // std::map stores the actual key/value pair in value_type::__cc_ (or
453 // previously __cc).
454 key_value_sp = key_value_sp->Clone(ConstString("pair"));
455 if (key_value_sp->GetNumChildrenIgnoringErrors() == 1) {
456 auto child0_sp = key_value_sp->GetChildAtIndex(0);
457 if (child0_sp &&
458 (child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc"))
459 key_value_sp = child0_sp->Clone(ConstString("pair"));
460 }
461
462 m_pair_sp = key_value_sp;
463
464 return lldb::ChildCacheState::eRefetch;
465 }
466
467 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()468 LibCxxMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
469 return 2;
470 }
471
472 lldb::ValueObjectSP
GetChildAtIndex(uint32_t idx)473 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::GetChildAtIndex(
474 uint32_t idx) {
475 if (!m_pair_sp)
476 return nullptr;
477
478 return m_pair_sp->GetChildAtIndex(idx);
479 }
480
481 bool lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
MightHaveChildren()482 MightHaveChildren() {
483 return true;
484 }
485
486 size_t lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)487 GetIndexOfChildWithName(ConstString name) {
488 if (!m_pair_sp)
489 return UINT32_MAX;
490
491 return m_pair_sp->GetIndexOfChildWithName(name);
492 }
493
494 SyntheticChildrenFrontEnd *
LibCxxMapIteratorSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)495 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEndCreator(
496 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
497 return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp)
498 : nullptr);
499 }
500