LLDB mainline
LibCxxMap.cpp
Go to the documentation of this file.
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
13#include "lldb/Target/Target.h"
15#include "lldb/Utility/Endian.h"
16#include "lldb/Utility/Status.h"
17#include "lldb/Utility/Stream.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
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
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
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
77 uint64_t value() const {
78 if (!m_entry_sp)
79 return 0;
80 return m_entry_sp->GetValueAsUnsigned(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:
101};
102
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
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(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 }
144 steps++;
145 if (steps > m_max_depth) {
146 m_entry = MapEntry();
147 return;
148 }
149 }
151 }
152
153 /// Mimicks libc++'s __tree_min algorithm.
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
182 size_t m_max_depth = 0;
183 bool m_error = false;
184};
185
186namespace lldb_private {
187namespace formatters {
189public:
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
204private:
205 llvm::Expected<uint32_t> CalculateNumChildrenForOldCompressedPairLayout();
206
207 /// Returns the ValueObject for the __tree_node type that
208 /// holds the key/value pair of the node at index \ref idx.
209 ///
210 /// \param[in] idx The child index that we're looking to get
211 /// the key/value pair for.
212 ///
213 /// \param[in] max_depth The maximum search depth after which
214 /// we stop trying to find the key/value
215 /// pair for.
216 ///
217 /// \returns On success, returns the ValueObjectSP corresponding
218 /// to the __tree_node's __value_ member (which holds
219 /// the key/value pair the formatter wants to display).
220 /// On failure, will return nullptr.
221 ValueObjectSP GetKeyValuePair(size_t idx, size_t max_depth);
222
223 ValueObject *m_tree = nullptr;
227 std::map<size_t, MapIterator> m_iterators;
228};
229
231public:
233
234 llvm::Expected<uint32_t> CalculateNumChildren() override;
235
236 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
237
238 lldb::ChildCacheState Update() override;
239
240 bool MightHaveChildren() override;
241
242 size_t GetIndexOfChildWithName(ConstString name) override;
243
245
246private:
248};
249} // namespace formatters
250} // namespace lldb_private
251
254 : SyntheticChildrenFrontEnd(*valobj_sp) {
255 if (valobj_sp)
256 Update();
257}
258
259llvm::Expected<uint32_t>
262 ValueObjectSP node_sp(m_tree->GetChildMemberWithName("__pair3_"));
263 if (!node_sp)
264 return 0;
265
266 if (!isOldCompressedPairLayout(*node_sp))
267 return llvm::createStringError("Unexpected std::map layout: expected "
268 "old __compressed_pair layout.");
269
270 node_sp = GetFirstValueOfLibCXXCompressedPair(*node_sp);
271
272 if (!node_sp)
273 return 0;
274
275 m_count = node_sp->GetValueAsUnsigned(0);
276
277 return m_count;
278}
279
280llvm::Expected<uint32_t> lldb_private::formatters::
282 if (m_count != UINT32_MAX)
283 return m_count;
284
285 if (m_tree == nullptr)
286 return 0;
287
288 if (auto node_sp = m_tree->GetChildMemberWithName("__size_")) {
289 m_count = node_sp->GetValueAsUnsigned(0);
290 return m_count;
291 }
292
293 return CalculateNumChildrenForOldCompressedPairLayout();
294}
295
298 size_t idx, size_t max_depth) {
299 MapIterator iterator(m_root_node, max_depth);
300
301 size_t advance_by = idx;
302 if (idx > 0) {
303 // If we have already created the iterator for the previous
304 // index, we can start from there and advance by 1.
305 auto cached_iterator = m_iterators.find(idx - 1);
306 if (cached_iterator != m_iterators.end()) {
307 iterator = cached_iterator->second;
308 advance_by = 1;
309 }
310 }
311
312 ValueObjectSP iterated_sp(iterator.advance(advance_by));
313 if (!iterated_sp)
314 // this tree is garbage - stop
315 return nullptr;
316
317 if (!m_node_ptr_type.IsValid())
318 return nullptr;
319
320 // iterated_sp is a __iter_pointer at this point.
321 // We can cast it to a __node_pointer (which is what libc++ does).
322 auto value_type_sp = iterated_sp->Cast(m_node_ptr_type);
323 if (!value_type_sp)
324 return nullptr;
325
326 // Finally, get the key/value pair.
327 value_type_sp = value_type_sp->GetChildMemberWithName("__value_");
328 if (!value_type_sp)
329 return nullptr;
330
331 m_iterators[idx] = iterator;
332
333 return value_type_sp;
334}
335
338 uint32_t idx) {
339 static ConstString g_cc_("__cc_"), g_cc("__cc");
340 static ConstString g_nc("__nc");
341 uint32_t num_children = CalculateNumChildrenIgnoringErrors();
342 if (idx >= num_children)
343 return nullptr;
344
345 if (m_tree == nullptr || m_root_node == nullptr)
346 return nullptr;
347
348 ValueObjectSP key_val_sp = GetKeyValuePair(idx, /*max_depth=*/num_children);
349 if (!key_val_sp) {
350 // this will stop all future searches until an Update() happens
351 m_tree = nullptr;
352 return nullptr;
353 }
354
355 // at this point we have a valid
356 // we need to copy current_sp into a new object otherwise we will end up with
357 // all items named __value_
358 StreamString name;
359 name.Printf("[%" PRIu64 "]", (uint64_t)idx);
360 auto potential_child_sp = key_val_sp->Clone(ConstString(name.GetString()));
361 if (potential_child_sp) {
362 switch (potential_child_sp->GetNumChildrenIgnoringErrors()) {
363 case 1: {
364 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
365 if (child0_sp &&
366 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))
367 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
368 break;
369 }
370 case 2: {
371 auto child0_sp = potential_child_sp->GetChildAtIndex(0);
372 auto child1_sp = potential_child_sp->GetChildAtIndex(1);
373 if (child0_sp &&
374 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&
375 child1_sp && child1_sp->GetName() == g_nc)
376 potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
377 break;
378 }
379 }
380 }
381 return potential_child_sp;
382}
383
386 m_count = UINT32_MAX;
387 m_tree = m_root_node = nullptr;
388 m_iterators.clear();
389 m_tree = m_backend.GetChildMemberWithName("__tree_").get();
390 if (!m_tree)
392
393 m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get();
394 m_node_ptr_type =
395 m_tree->GetCompilerType().GetDirectNestedTypeWithName("__node_pointer");
396
398}
399
402 return true;
403}
404
407 return ExtractIndexFromString(name.GetCString());
408}
409
413 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
414}
415
418 : SyntheticChildrenFrontEnd(*valobj_sp) {
419 if (valobj_sp)
420 Update();
421}
422
425 m_pair_sp.reset();
426
427 ValueObjectSP valobj_sp = m_backend.GetSP();
428 if (!valobj_sp)
430
431 TargetSP target_sp(valobj_sp->GetTargetSP());
432 if (!target_sp)
434
435 // m_backend is a std::map::iterator
436 // ...which is a __map_iterator<__tree_iterator<..., __node_pointer, ...>>
437 //
438 // Then, __map_iterator::__i_ is a __tree_iterator
439 auto tree_iter_sp = valobj_sp->GetChildMemberWithName("__i_");
440 if (!tree_iter_sp)
442
443 // Type is __tree_iterator::__node_pointer
444 // (We could alternatively also get this from the template argument)
445 auto node_pointer_type =
446 tree_iter_sp->GetCompilerType().GetDirectNestedTypeWithName(
447 "__node_pointer");
448 if (!node_pointer_type.IsValid())
450
451 // __ptr_ is a __tree_iterator::__iter_pointer
452 auto iter_pointer_sp = tree_iter_sp->GetChildMemberWithName("__ptr_");
453 if (!iter_pointer_sp)
455
456 // Cast the __iter_pointer to a __node_pointer (which stores our key/value
457 // pair)
458 auto node_pointer_sp = iter_pointer_sp->Cast(node_pointer_type);
459 if (!node_pointer_sp)
461
462 auto key_value_sp = node_pointer_sp->GetChildMemberWithName("__value_");
463 if (!key_value_sp)
465
466 // Create the synthetic child, which is a pair where the key and value can be
467 // retrieved by querying the synthetic frontend for
468 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
469 // respectively.
470 //
471 // std::map stores the actual key/value pair in value_type::__cc_ (or
472 // previously __cc).
473 key_value_sp = key_value_sp->Clone(ConstString("pair"));
474 if (key_value_sp->GetNumChildrenIgnoringErrors() == 1) {
475 auto child0_sp = key_value_sp->GetChildAtIndex(0);
476 if (child0_sp &&
477 (child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc"))
478 key_value_sp = child0_sp->Clone(ConstString("pair"));
479 }
480
481 m_pair_sp = key_value_sp;
482
484}
485
486llvm::Expected<uint32_t> lldb_private::formatters::
488 return 2;
489}
490
493 uint32_t idx) {
494 if (!m_pair_sp)
495 return nullptr;
496
497 return m_pair_sp->GetChildAtIndex(idx);
498}
499
502 return true;
503}
504
507 if (!m_pair_sp)
508 return UINT32_MAX;
509
510 return m_pair_sp->GetIndexOfChildWithName(name);
511}
512
516 return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp)
517 : nullptr);
518}
ValueObjectSP right() const
Definition: LibCxxMap.cpp:61
bool null() const
Definition: LibCxxMap.cpp:89
ValueObjectSP left() const
Definition: LibCxxMap.cpp:54
MapEntry(ValueObject *entry)
Definition: LibCxxMap.cpp:51
ValueObjectSP parent() const
Definition: LibCxxMap.cpp:69
void SetEntry(ValueObjectSP entry)
Definition: LibCxxMap.cpp:93
MapEntry()=default
ValueObjectSP m_entry_sp
Definition: LibCxxMap.cpp:100
ValueObjectSP GetEntry() const
Definition: LibCxxMap.cpp:91
uint64_t value() const
Definition: LibCxxMap.cpp:77
bool operator==(const MapEntry &rhs) const
Definition: LibCxxMap.cpp:95
MapEntry(ValueObjectSP entry_sp)
Definition: LibCxxMap.cpp:50
bool error() const
Definition: LibCxxMap.cpp:83
ValueObjectSP advance(size_t count)
Definition: LibCxxMap.cpp:112
MapIterator(ValueObject *entry, size_t depth=0)
Definition: LibCxxMap.cpp:105
ValueObjectSP value()
Definition: LibCxxMap.cpp:110
size_t m_max_depth
Definition: LibCxxMap.cpp:182
MapEntry m_entry
Definition: LibCxxMap.cpp:181
void next()
Mimicks libc++'s __tree_next algorithm, which libc++ uses in its __tree_iteartor::operator++.
Definition: LibCxxMap.cpp:129
MapIterator()=default
bool is_left_child(const MapEntry &x)
Definition: LibCxxMap.cpp:173
MapEntry tree_min(MapEntry x)
Mimicks libc++'s __tree_min algorithm.
Definition: LibCxxMap.cpp:154
Generic representation of a type in a programming language.
Definition: CompilerType.h:36
A uniqued constant string class.
Definition: ConstString.h:40
const char * GetCString() const
Get the string value as a C string.
Definition: ConstString.h:216
llvm::StringRef GetString() const
size_t Printf(const char *format,...) __attribute__((format(printf
Output printf formatted output to the stream.
Definition: Stream.cpp:134
llvm::Expected< uint32_t > CalculateNumChildren() override
Definition: LibCxxMap.cpp:487
lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override
Definition: LibCxxMap.cpp:492
size_t GetIndexOfChildWithName(ConstString name) override
Definition: LibCxxMap.cpp:506
lldb::ChildCacheState Update() override
This function is assumed to always succeed and if it fails, the front-end should know to deal with it...
Definition: LibCxxMap.cpp:424
LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
Definition: LibCxxMap.cpp:417
lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override
Definition: LibCxxMap.cpp:337
llvm::Expected< uint32_t > CalculateNumChildrenForOldCompressedPairLayout()
Definition: LibCxxMap.cpp:261
size_t GetIndexOfChildWithName(ConstString name) override
Definition: LibCxxMap.cpp:406
lldb::ChildCacheState Update() override
This function is assumed to always succeed and if it fails, the front-end should know to deal with it...
Definition: LibCxxMap.cpp:385
llvm::Expected< uint32_t > CalculateNumChildren() override
Definition: LibCxxMap.cpp:281
LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
Definition: LibCxxMap.cpp:253
ValueObjectSP GetKeyValuePair(size_t idx, size_t max_depth)
Returns the ValueObject for the __tree_node type that holds the key/value pair of the node at index i...
Definition: LibCxxMap.cpp:297
#define UINT32_MAX
Definition: lldb-defines.h:19
size_t ExtractIndexFromString(const char *item_name)
lldb::ValueObjectSP GetFirstValueOfLibCXXCompressedPair(ValueObject &pair)
Definition: LibCxx.cpp:76
SyntheticChildrenFrontEnd * LibcxxStdMapSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxMap.cpp:411
bool isOldCompressedPairLayout(ValueObject &pair_obj)
Definition: LibCxx.cpp:50
SyntheticChildrenFrontEnd * LibCxxMapIteratorSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxMap.cpp:514
A class that represents a running process on the host machine.
Definition: SBAddress.h:15
ChildCacheState
Specifies if children need to be re-computed after a call to SyntheticChildrenFrontEnd::Update.
@ eRefetch
Children need to be recomputed dynamically.
std::shared_ptr< lldb_private::ValueObject > ValueObjectSP
Definition: lldb-forward.h:484
std::shared_ptr< lldb_private::Target > TargetSP
Definition: lldb-forward.h:448