509 lines · cpp
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-exception6//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_ looks31// as follows:32//33// The following shows the contiguous block of memory:34//35// +-----------------------------+ class __tree_end_node36// __ptr_ | pointer __left_; |37// +-----------------------------+ class __tree_node_base38// | pointer __right_; |39// | __parent_pointer __parent_; |40// | bool __is_black_; |41// +-----------------------------+ class __tree_node42// | __node_value_type __value_; | <<< our key/value pair43// +-----------------------------+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 0, m_entry_sp->GetCompilerType(), true);59 }60 61 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 69 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 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: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++ uses128 /// 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 }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>204 CalculateNumChildrenForOldCompressedPairLayout(ValueObject &pair);205 206 /// Returns the ValueObject for the __tree_node type that207 /// 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 get210 /// the key/value pair for.211 ///212 /// \param[in] max_depth The maximum search depth after which213 /// we stop trying to find the key/value214 /// pair for.215 ///216 /// \returns On success, returns the ValueObjectSP corresponding217 /// to the __tree_node's __value_ member (which holds218 /// 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 229class LibCxxMapIteratorSyntheticFrontEnd : public SyntheticChildrenFrontEnd {230public: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 243private:244 ValueObjectSP m_pair_sp = nullptr;245};246} // namespace formatters247} // namespace lldb_private248 249lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::250 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)251 : SyntheticChildrenFrontEnd(*valobj_sp) {252 if (valobj_sp)253 Update();254}255 256llvm::Expected<uint32_t>257lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::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 269llvm::Expected<uint32_t> lldb_private::formatters::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 289ValueObjectSP290lldb_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 previous297 // 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 - stop308 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 329lldb::ValueObjectSP330lldb_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() happens344 m_tree = nullptr;345 return nullptr;346 }347 348 // at this point we have a valid349 // we need to copy current_sp into a new object otherwise we will end up with350 // 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 377lldb::ChildCacheState378lldb_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 393llvm::Expected<size_t> lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::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 403SyntheticChildrenFrontEnd *404lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(405 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {406 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);407}408 409lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::410 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)411 : SyntheticChildrenFrontEnd(*valobj_sp) {412 if (valobj_sp)413 Update();414}415 416lldb::ChildCacheState417lldb_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::iterator429 // ...which is a __map_iterator<__tree_iterator<..., __node_pointer, ...>>430 //431 // Then, __map_iterator::__i_ is a __tree_iterator432 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_pointer437 // (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_pointer445 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/value450 // 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 be460 // retrieved by querying the synthetic frontend for461 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")462 // respectively.463 //464 // std::map stores the actual key/value pair in value_type::__cc_ (or465 // 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 479llvm::Expected<uint32_t> lldb_private::formatters::480 LibCxxMapIteratorSyntheticFrontEnd::CalculateNumChildren() {481 return 2;482}483 484lldb::ValueObjectSP485lldb_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 493llvm::Expected<size_t>494lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::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 503SyntheticChildrenFrontEnd *504lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEndCreator(505 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {506 return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp)507 : nullptr);508}509