408 lines · cpp
1//===-- MsvcStlTree.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 "MsvcStl.h"10 11#include "lldb/DataFormatters/FormattersHelpers.h"12#include "lldb/Utility/Status.h"13#include "lldb/ValueObject/ValueObject.h"14#include "lldb/lldb-enumerations.h"15#include "lldb/lldb-forward.h"16#include <cstdint>17#include <optional>18 19using namespace lldb;20using namespace lldb_private;21using namespace lldb_private::formatters;22 23// A Node looks as follows:24// struct _Tree_node {25// _Tree_node *_Left;26// _Tree_node *_Parent;27// _Tree_node *_Right;28// char _Color;29// char _Isnil; // true (!= 0) if head or nil node30// value_type _Myval;31// };32 33namespace {34 35class MapEntry {36public:37 MapEntry() = default;38 explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}39 explicit MapEntry(ValueObject *entry)40 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}41 42 ValueObjectSP left() const {43 if (!m_entry_sp)44 return m_entry_sp;45 return m_entry_sp->GetSyntheticChildAtOffset(46 0, m_entry_sp->GetCompilerType(), true);47 }48 49 ValueObjectSP right() const {50 if (!m_entry_sp)51 return m_entry_sp;52 return m_entry_sp->GetSyntheticChildAtOffset(53 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(),54 m_entry_sp->GetCompilerType(), true);55 }56 57 ValueObjectSP parent() const {58 if (!m_entry_sp)59 return m_entry_sp;60 return m_entry_sp->GetSyntheticChildAtOffset(61 m_entry_sp->GetProcessSP()->GetAddressByteSize(),62 m_entry_sp->GetCompilerType(), true);63 }64 65 uint64_t value() const {66 if (!m_entry_sp)67 return 0;68 return m_entry_sp->GetValueAsUnsigned(0);69 }70 71 bool is_nil() const {72 if (!m_entry_sp)73 return true;74 auto isnil_sp = m_entry_sp->GetChildMemberWithName("_Isnil");75 if (!isnil_sp)76 return true;77 return isnil_sp->GetValueAsUnsigned(1) != 0;78 }79 80 bool error() const {81 if (!m_entry_sp)82 return true;83 return m_entry_sp->GetError().Fail();84 }85 86 bool is_nullptr() const { return (value() == 0); }87 88 ValueObjectSP GetEntry() const { return m_entry_sp; }89 90 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }91 92 bool operator==(const MapEntry &rhs) const {93 return (rhs.m_entry_sp.get() == m_entry_sp.get());94 }95 96private:97 ValueObjectSP m_entry_sp;98};99 100class MapIterator {101public:102 MapIterator(ValueObject *entry, size_t depth = 0)103 : m_entry(entry), m_max_depth(depth) {}104 105 MapIterator() = default;106 107 ValueObjectSP value() { return m_entry.GetEntry(); }108 109 ValueObjectSP advance(size_t count) {110 ValueObjectSP fail;111 if (m_error)112 return fail;113 size_t steps = 0;114 while (count > 0) {115 next();116 count--, steps++;117 if (m_error || m_entry.is_nullptr() || (steps > m_max_depth))118 return fail;119 }120 return m_entry.GetEntry();121 }122 123private:124 /// Mimicks _Tree_unchecked_const_iterator::operator++()125 void next() {126 if (m_entry.is_nullptr())127 return;128 MapEntry right(m_entry.right());129 if (!right.is_nil()) {130 m_entry = tree_min(std::move(right));131 return;132 }133 size_t steps = 0;134 MapEntry pnode(m_entry.parent());135 while (!pnode.is_nil() &&136 m_entry.value() == MapEntry(pnode.right()).value()) {137 m_entry = pnode;138 steps++;139 if (steps > m_max_depth) {140 m_entry = MapEntry();141 return;142 }143 pnode.SetEntry(m_entry.parent());144 }145 m_entry = std::move(pnode);146 }147 148 /// Mimicks MSVC STL's _Min() algorithm (finding the leftmost node in the149 /// subtree).150 MapEntry tree_min(MapEntry pnode) {151 if (pnode.is_nullptr())152 return MapEntry();153 MapEntry left(pnode.left());154 size_t steps = 0;155 while (!left.is_nil()) {156 if (left.error()) {157 m_error = true;158 return MapEntry();159 }160 pnode = left;161 left.SetEntry(pnode.left());162 steps++;163 if (steps > m_max_depth)164 return MapEntry();165 }166 return pnode;167 }168 169 MapEntry m_entry;170 size_t m_max_depth = 0;171 bool m_error = false;172};173 174} // namespace175 176namespace lldb_private {177namespace formatters {178class MsvcStlTreeSyntheticFrontEnd : public SyntheticChildrenFrontEnd {179public:180 MsvcStlTreeSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);181 182 ~MsvcStlTreeSyntheticFrontEnd() override = default;183 184 llvm::Expected<uint32_t> CalculateNumChildren() override;185 186 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;187 188 lldb::ChildCacheState Update() override;189 190 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override;191 192private:193 /// Returns the ValueObject for the _Tree_node at index \ref idx.194 ///195 /// \param[in] idx The child index that we're looking to get the value for.196 ///197 /// \param[in] max_depth The maximum search depth after which we stop trying198 /// to find the node for.199 ///200 /// \returns On success, returns the ValueObjectSP corresponding to the201 /// _Tree_node's _Myval member.202 /// On failure, nullptr is returned.203 ValueObjectSP GetValueAt(size_t idx, size_t max_depth);204 205 ValueObject *m_tree = nullptr;206 ValueObject *m_begin_node = nullptr;207 size_t m_count = UINT32_MAX;208 std::map<size_t, MapIterator> m_iterators;209};210 211class MsvcStlTreeIterSyntheticFrontEnd : public SyntheticChildrenFrontEnd {212public:213 MsvcStlTreeIterSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)214 : SyntheticChildrenFrontEnd(*valobj_sp) {}215 216 llvm::Expected<uint32_t> CalculateNumChildren() override {217 if (!m_inner_sp)218 return 0;219 return m_inner_sp->GetNumChildren();220 }221 222 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override {223 if (!m_inner_sp)224 return nullptr;225 return m_inner_sp->GetChildAtIndex(idx);226 }227 228 lldb::ChildCacheState Update() override;229 230 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override {231 if (!m_inner_sp)232 return llvm::createStringError("There are no children.");233 return m_inner_sp->GetIndexOfChildWithName(name);234 }235 236 lldb::ValueObjectSP GetSyntheticValue() override { return m_inner_sp; }237 238private:239 ValueObjectSP m_inner_sp;240};241 242} // namespace formatters243} // namespace lldb_private244 245lldb_private::formatters::MsvcStlTreeSyntheticFrontEnd::246 MsvcStlTreeSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)247 : SyntheticChildrenFrontEnd(*valobj_sp) {248 if (valobj_sp)249 Update();250}251 252llvm::Expected<uint32_t>253lldb_private::formatters::MsvcStlTreeSyntheticFrontEnd::CalculateNumChildren() {254 if (m_count != UINT32_MAX)255 return m_count;256 257 if (m_tree == nullptr)258 return 0;259 260 if (auto node_sp = m_tree->GetChildMemberWithName("_Mysize")) {261 m_count = node_sp->GetValueAsUnsigned(0);262 return m_count;263 }264 265 return llvm::createStringError("Failed to read size.");266}267 268ValueObjectSP269lldb_private::formatters::MsvcStlTreeSyntheticFrontEnd::GetValueAt(270 size_t idx, size_t max_depth) {271 MapIterator iterator(m_begin_node, max_depth);272 273 size_t advance_by = idx;274 if (idx > 0) {275 // If we have already created the iterator for the previous276 // index, we can start from there and advance by 1.277 auto cached_iterator = m_iterators.find(idx - 1);278 if (cached_iterator != m_iterators.end()) {279 iterator = cached_iterator->second;280 advance_by = 1;281 }282 }283 284 ValueObjectSP iterated_sp(iterator.advance(advance_by));285 if (!iterated_sp)286 // this tree is garbage - stop287 return nullptr;288 289 ValueObjectSP value_sp = iterated_sp->GetChildMemberWithName("_Myval");290 if (!value_sp)291 return nullptr;292 293 m_iterators[idx] = iterator;294 295 return value_sp;296}297 298lldb::ValueObjectSP299lldb_private::formatters::MsvcStlTreeSyntheticFrontEnd::GetChildAtIndex(300 uint32_t idx) {301 uint32_t num_children = CalculateNumChildrenIgnoringErrors();302 if (idx >= num_children)303 return nullptr;304 305 if (m_tree == nullptr || m_begin_node == nullptr)306 return nullptr;307 308 ValueObjectSP val_sp = GetValueAt(idx, /*max_depth=*/num_children);309 if (!val_sp) {310 // this will stop all future searches until an Update() happens311 m_tree = nullptr;312 return nullptr;313 }314 315 // at this point we have a valid pair316 // we need to copy current_sp into a new object otherwise we will end up with317 // all items named _Myval318 StreamString name;319 name.Printf("[%" PRIu64 "]", (uint64_t)idx);320 return val_sp->Clone(ConstString(name.GetString()));321}322 323lldb::ChildCacheState324lldb_private::formatters::MsvcStlTreeSyntheticFrontEnd::Update() {325 m_count = UINT32_MAX;326 m_tree = m_begin_node = nullptr;327 m_iterators.clear();328 m_tree =329 m_backend.GetChildAtNamePath({"_Mypair", "_Myval2", "_Myval2"}).get();330 if (!m_tree)331 return lldb::ChildCacheState::eRefetch;332 333 m_begin_node = m_tree->GetChildAtNamePath({"_Myhead", "_Left"}).get();334 335 return lldb::ChildCacheState::eRefetch;336}337 338llvm::Expected<size_t>339lldb_private::formatters::MsvcStlTreeSyntheticFrontEnd::GetIndexOfChildWithName(340 ConstString name) {341 auto optional_idx = formatters::ExtractIndexFromString(name.GetCString());342 if (!optional_idx) {343 return llvm::createStringError("Type has no child named '%s'",344 name.AsCString());345 }346 return *optional_idx;347}348 349lldb::ChildCacheState MsvcStlTreeIterSyntheticFrontEnd::Update() {350 m_inner_sp = nullptr;351 auto node_sp = m_backend.GetChildMemberWithName("_Ptr");352 if (!node_sp)353 return lldb::eRefetch;354 355 MapEntry entry(node_sp.get());356 if (entry.is_nil())357 return lldb::eRefetch; // end358 359 m_inner_sp = node_sp->GetChildMemberWithName("_Myval");360 return lldb::eRefetch;361}362 363bool formatters::IsMsvcStlTreeIter(ValueObject &valobj) {364 return valobj.GetChildMemberWithName("_Ptr") != nullptr;365}366 367bool formatters::MsvcStlTreeIterSummaryProvider(368 ValueObject &valobj, Stream &stream, const TypeSummaryOptions &options) {369 auto valobj_sp = valobj.GetNonSyntheticValue();370 if (!valobj_sp)371 return false;372 auto node_sp = valobj_sp->GetChildMemberWithName("_Ptr");373 if (!node_sp)374 return false;375 376 MapEntry entry(node_sp.get());377 if (entry.is_nil()) {378 stream.Printf("end");379 return true;380 }381 382 auto value_sp = node_sp->GetChildMemberWithName("_Myval");383 if (!value_sp)384 return false;385 386 auto *summary = value_sp->GetSummaryAsCString();387 if (summary)388 stream << summary;389 return true;390}391 392SyntheticChildrenFrontEnd *393lldb_private::formatters::MsvcStlTreeIterSyntheticFrontEndCreator(394 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {395 return (valobj_sp ? new MsvcStlTreeIterSyntheticFrontEnd(valobj_sp)396 : nullptr);397}398 399bool formatters::IsMsvcStlMapLike(ValueObject &valobj) {400 return valobj.GetChildMemberWithName("_Mypair") != nullptr;401}402 403SyntheticChildrenFrontEnd *404lldb_private::formatters::MsvcStlMapLikeSyntheticFrontEndCreator(405 lldb::ValueObjectSP valobj_sp) {406 return (valobj_sp ? new MsvcStlTreeSyntheticFrontEnd(valobj_sp) : nullptr);407}408