641 lines · cpp
1//===-- GenericList.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#include "MsvcStl.h"11 12#include "lldb/DataFormatters/FormattersHelpers.h"13#include "lldb/Target/Target.h"14#include "lldb/Utility/Status.h"15#include "lldb/ValueObject/ValueObject.h"16#include "lldb/ValueObject/ValueObjectConstResult.h"17#include "lldb/lldb-enumerations.h"18 19using namespace lldb;20using namespace lldb_private;21using namespace lldb_private::formatters;22 23namespace {24 25enum class StlType {26 LibCxx,27 MsvcStl,28};29 30template <StlType Stl> class ListEntry {31public:32 ListEntry() = default;33 ListEntry(ValueObjectSP entry_sp) : m_entry_sp(std::move(entry_sp)) {}34 ListEntry(ValueObject *entry)35 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}36 37 uint64_t value() const {38 if (!m_entry_sp)39 return 0;40 return m_entry_sp->GetValueAsUnsigned(0);41 }42 43 ListEntry next();44 ListEntry prev();45 46 bool null() { return (value() == 0); }47 48 explicit operator bool() { return GetEntry() && !null(); }49 50 ValueObjectSP GetEntry() { return m_entry_sp; }51 52 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }53 54 bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); }55 56 bool operator!=(const ListEntry &rhs) const { return !(*this == rhs); }57 58private:59 ValueObjectSP m_entry_sp;60};61 62template <> ListEntry<StlType::LibCxx> ListEntry<StlType::LibCxx>::next() {63 if (!m_entry_sp)64 return ListEntry();65 return ListEntry(m_entry_sp->GetChildMemberWithName("__next_"));66}67 68template <> ListEntry<StlType::LibCxx> ListEntry<StlType::LibCxx>::prev() {69 if (!m_entry_sp)70 return ListEntry();71 return ListEntry(m_entry_sp->GetChildMemberWithName("__prev_"));72}73 74template <> ListEntry<StlType::MsvcStl> ListEntry<StlType::MsvcStl>::next() {75 if (!m_entry_sp)76 return ListEntry();77 return ListEntry(m_entry_sp->GetChildMemberWithName("_Next"));78}79 80template <> ListEntry<StlType::MsvcStl> ListEntry<StlType::MsvcStl>::prev() {81 if (!m_entry_sp)82 return ListEntry();83 return ListEntry(m_entry_sp->GetChildMemberWithName("_Prev"));84}85 86template <StlType Stl> class ListIterator {87public:88 ListIterator() = default;89 ListIterator(ListEntry<Stl> entry) : m_entry(std::move(entry)) {}90 ListIterator(ValueObjectSP entry) : m_entry(std::move(entry)) {}91 ListIterator(ValueObject *entry) : m_entry(entry) {}92 93 ValueObjectSP value() { return m_entry.GetEntry(); }94 95 ValueObjectSP advance(size_t count) {96 if (count == 0)97 return m_entry.GetEntry();98 if (count == 1) {99 next();100 return m_entry.GetEntry();101 }102 while (count > 0) {103 next();104 count--;105 if (m_entry.null())106 return lldb::ValueObjectSP();107 }108 return m_entry.GetEntry();109 }110 111 bool operator==(const ListIterator &rhs) const {112 return (rhs.m_entry == m_entry);113 }114 115protected:116 void next() { m_entry = m_entry.next(); }117 118 void prev() { m_entry = m_entry.prev(); }119 120private:121 ListEntry<Stl> m_entry;122};123 124template <StlType Stl>125class AbstractListFrontEnd : public SyntheticChildrenFrontEnd {126public:127 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override {128 auto optional_idx = formatters::ExtractIndexFromString(name.GetCString());129 if (!optional_idx) {130 return llvm::createStringError("Type has no child named '%s'",131 name.AsCString());132 }133 return *optional_idx;134 }135 lldb::ChildCacheState Update() override;136 137protected:138 AbstractListFrontEnd(ValueObject &valobj)139 : SyntheticChildrenFrontEnd(valobj) {}140 141 size_t m_count = 0;142 ValueObject *m_head = nullptr;143 144 static constexpr bool g_use_loop_detect = true;145 size_t m_loop_detected = 0; // The number of elements that have had loop146 // detection run over them.147 ListEntry<Stl> m_slow_runner; // Used for loop detection148 ListEntry<Stl> m_fast_runner; // Used for loop detection149 150 size_t m_list_capping_size = 0;151 CompilerType m_element_type;152 std::map<size_t, ListIterator<Stl>> m_iterators;153 154 bool HasLoop(size_t count);155 ValueObjectSP GetItem(size_t idx);156};157 158class LibCxxForwardListFrontEnd : public AbstractListFrontEnd<StlType::LibCxx> {159public:160 LibCxxForwardListFrontEnd(ValueObject &valobj);161 162 llvm::Expected<uint32_t> CalculateNumChildren() override;163 ValueObjectSP GetChildAtIndex(uint32_t idx) override;164 lldb::ChildCacheState Update() override;165};166 167class LibCxxListFrontEnd : public AbstractListFrontEnd<StlType::LibCxx> {168public:169 LibCxxListFrontEnd(lldb::ValueObjectSP valobj_sp);170 171 llvm::Expected<uint32_t> CalculateNumChildren() override;172 173 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;174 175 lldb::ChildCacheState Update() override;176 177private:178 lldb::addr_t m_node_address = 0;179 ValueObject *m_tail = nullptr;180};181 182class MsvcStlForwardListFrontEnd183 : public AbstractListFrontEnd<StlType::MsvcStl> {184public:185 MsvcStlForwardListFrontEnd(ValueObject &valobj);186 187 llvm::Expected<uint32_t> CalculateNumChildren() override;188 ValueObjectSP GetChildAtIndex(uint32_t idx) override;189 lldb::ChildCacheState Update() override;190};191 192class MsvcStlListFrontEnd : public AbstractListFrontEnd<StlType::MsvcStl> {193public:194 MsvcStlListFrontEnd(lldb::ValueObjectSP valobj_sp);195 196 llvm::Expected<uint32_t> CalculateNumChildren() override;197 198 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;199 200 lldb::ChildCacheState Update() override;201 202private:203 ValueObject *m_tail = nullptr;204};205 206} // end anonymous namespace207 208template <StlType Stl>209lldb::ChildCacheState AbstractListFrontEnd<Stl>::Update() {210 m_loop_detected = 0;211 m_count = UINT32_MAX;212 m_head = nullptr;213 m_list_capping_size = 0;214 m_slow_runner.SetEntry(nullptr);215 m_fast_runner.SetEntry(nullptr);216 m_iterators.clear();217 218 if (m_backend.GetTargetSP())219 m_list_capping_size =220 m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();221 if (m_list_capping_size == 0)222 m_list_capping_size = 255;223 224 CompilerType list_type = m_backend.GetCompilerType();225 if (list_type.IsReferenceType())226 list_type = list_type.GetNonReferenceType();227 228 if (list_type.GetNumTemplateArguments() == 0)229 return lldb::ChildCacheState::eRefetch;230 m_element_type = list_type.GetTypeTemplateArgument(0);231 232 return lldb::ChildCacheState::eRefetch;233}234 235template <StlType Stl> bool AbstractListFrontEnd<Stl>::HasLoop(size_t count) {236 if (!g_use_loop_detect)237 return false;238 // don't bother checking for a loop if we won't actually need to jump nodes239 if (m_count < 2)240 return false;241 242 if (m_loop_detected == 0) {243 // This is the first time we are being run (after the last update). Set up244 // the loop invariant for the first element.245 m_slow_runner = ListEntry<Stl>(m_head).next();246 m_fast_runner = m_slow_runner.next();247 m_loop_detected = 1;248 }249 250 // Loop invariant:251 // Loop detection has been run over the first m_loop_detected elements. If252 // m_slow_runner == m_fast_runner then the loop has been detected after253 // m_loop_detected elements.254 const size_t steps_to_run = std::min(count, m_count);255 while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner &&256 m_slow_runner != m_fast_runner) {257 258 m_slow_runner = m_slow_runner.next();259 m_fast_runner = m_fast_runner.next().next();260 m_loop_detected++;261 }262 if (count <= m_loop_detected)263 return false; // No loop in the first m_loop_detected elements.264 if (!m_slow_runner || !m_fast_runner)265 return false; // Reached the end of the list. Definitely no loops.266 return m_slow_runner == m_fast_runner;267}268 269template <StlType Stl>270ValueObjectSP AbstractListFrontEnd<Stl>::GetItem(size_t idx) {271 size_t advance = idx;272 ListIterator<Stl> current(m_head);273 if (idx > 0) {274 auto cached_iterator = m_iterators.find(idx - 1);275 if (cached_iterator != m_iterators.end()) {276 current = cached_iterator->second;277 advance = 1;278 }279 }280 ValueObjectSP value_sp = current.advance(advance);281 m_iterators[idx] = current;282 return value_sp;283}284 285LibCxxForwardListFrontEnd::LibCxxForwardListFrontEnd(ValueObject &valobj)286 : AbstractListFrontEnd(valobj) {287 Update();288}289 290llvm::Expected<uint32_t> LibCxxForwardListFrontEnd::CalculateNumChildren() {291 if (m_count != UINT32_MAX)292 return m_count;293 294 ListEntry<StlType::LibCxx> current(m_head);295 m_count = 0;296 while (current && m_count < m_list_capping_size) {297 ++m_count;298 current = current.next();299 }300 return m_count;301}302 303ValueObjectSP LibCxxForwardListFrontEnd::GetChildAtIndex(uint32_t idx) {304 if (idx >= CalculateNumChildrenIgnoringErrors())305 return nullptr;306 307 if (!m_head)308 return nullptr;309 310 if (HasLoop(idx + 1))311 return nullptr;312 313 ValueObjectSP current_sp = GetItem(idx);314 if (!current_sp)315 return nullptr;316 317 current_sp = current_sp->GetChildAtIndex(1); // get the __value_ child318 if (!current_sp)319 return nullptr;320 321 // we need to copy current_sp into a new object otherwise we will end up with322 // all items named __value_323 DataExtractor data;324 Status error;325 current_sp->GetData(data, error);326 if (error.Fail())327 return nullptr;328 329 return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data,330 m_backend.GetExecutionContextRef(),331 m_element_type);332}333 334lldb::ChildCacheState LibCxxForwardListFrontEnd::Update() {335 AbstractListFrontEnd::Update();336 337 Status err;338 ValueObjectSP backend_addr(m_backend.AddressOf(err));339 if (err.Fail() || !backend_addr)340 return lldb::ChildCacheState::eRefetch;341 342 auto list_base_sp = m_backend.GetChildAtIndex(0);343 if (!list_base_sp)344 return lldb::ChildCacheState::eRefetch;345 346 // Anonymous strucutre index is in base class at index 0.347 auto [impl_sp, is_compressed_pair] =348 GetValueOrOldCompressedPair(*list_base_sp, /*anon_struct_idx=*/0,349 "__before_begin_", "__before_begin_");350 if (!impl_sp)351 return ChildCacheState::eRefetch;352 353 if (is_compressed_pair)354 impl_sp = GetFirstValueOfLibCXXCompressedPair(*impl_sp);355 356 if (!impl_sp)357 return ChildCacheState::eRefetch;358 359 m_head = impl_sp->GetChildMemberWithName("__next_").get();360 361 return ChildCacheState::eRefetch;362}363 364LibCxxListFrontEnd::LibCxxListFrontEnd(lldb::ValueObjectSP valobj_sp)365 : AbstractListFrontEnd(*valobj_sp) {366 if (valobj_sp)367 Update();368}369 370llvm::Expected<uint32_t> LibCxxListFrontEnd::CalculateNumChildren() {371 if (m_count != UINT32_MAX)372 return m_count;373 if (!m_head || !m_tail || m_node_address == 0)374 return 0;375 376 auto [size_node_sp, is_compressed_pair] = GetValueOrOldCompressedPair(377 m_backend, /*anon_struct_idx=*/1, "__size_", "__size_alloc_");378 if (is_compressed_pair)379 size_node_sp = GetFirstValueOfLibCXXCompressedPair(*size_node_sp);380 381 if (size_node_sp)382 m_count = size_node_sp->GetValueAsUnsigned(UINT32_MAX);383 384 if (m_count != UINT32_MAX)385 return m_count;386 387 uint64_t next_val = m_head->GetValueAsUnsigned(0);388 uint64_t prev_val = m_tail->GetValueAsUnsigned(0);389 if (next_val == 0 || prev_val == 0)390 return 0;391 if (next_val == m_node_address)392 return 0;393 if (next_val == prev_val)394 return 1;395 uint64_t size = 2;396 ListEntry<StlType::LibCxx> current(m_head);397 while (current.next() && current.next().value() != m_node_address) {398 size++;399 current = current.next();400 if (size > m_list_capping_size)401 break;402 }403 return m_count = (size - 1);404}405 406lldb::ValueObjectSP LibCxxListFrontEnd::GetChildAtIndex(uint32_t idx) {407 static ConstString g_value("__value_");408 static ConstString g_next("__next_");409 410 if (idx >= CalculateNumChildrenIgnoringErrors())411 return lldb::ValueObjectSP();412 413 if (!m_head || !m_tail || m_node_address == 0)414 return lldb::ValueObjectSP();415 416 if (HasLoop(idx + 1))417 return lldb::ValueObjectSP();418 419 ValueObjectSP current_sp = GetItem(idx);420 if (!current_sp)421 return lldb::ValueObjectSP();422 423 current_sp = current_sp->GetChildAtIndex(1); // get the __value_ child424 if (!current_sp)425 return lldb::ValueObjectSP();426 427 if (current_sp->GetName() == g_next) {428 ProcessSP process_sp(current_sp->GetProcessSP());429 if (!process_sp)430 return lldb::ValueObjectSP();431 432 // if we grabbed the __next_ pointer, then the child is one pointer deep-er433 lldb::addr_t addr = current_sp->GetParent()->GetPointerValue().address;434 addr = addr + 2 * process_sp->GetAddressByteSize();435 ExecutionContext exe_ctx(process_sp);436 current_sp =437 CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type);438 if (!current_sp)439 return lldb::ValueObjectSP();440 }441 442 // we need to copy current_sp into a new object otherwise we will end up with443 // all items named __value_444 DataExtractor data;445 Status error;446 current_sp->GetData(data, error);447 if (error.Fail())448 return lldb::ValueObjectSP();449 450 StreamString name;451 name.Printf("[%" PRIu64 "]", (uint64_t)idx);452 return CreateValueObjectFromData(name.GetString(), data,453 m_backend.GetExecutionContextRef(),454 m_element_type);455}456 457lldb::ChildCacheState LibCxxListFrontEnd::Update() {458 AbstractListFrontEnd::Update();459 m_tail = nullptr;460 m_node_address = 0;461 462 Status err;463 ValueObjectSP backend_addr(m_backend.AddressOf(err));464 if (err.Fail() || !backend_addr)465 return lldb::ChildCacheState::eRefetch;466 m_node_address = backend_addr->GetValueAsUnsigned(0);467 if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)468 return lldb::ChildCacheState::eRefetch;469 ValueObjectSP impl_sp(m_backend.GetChildMemberWithName("__end_"));470 if (!impl_sp)471 return lldb::ChildCacheState::eRefetch;472 m_head = impl_sp->GetChildMemberWithName("__next_").get();473 m_tail = impl_sp->GetChildMemberWithName("__prev_").get();474 return lldb::ChildCacheState::eRefetch;475}476 477MsvcStlForwardListFrontEnd::MsvcStlForwardListFrontEnd(ValueObject &valobj)478 : AbstractListFrontEnd(valobj) {479 Update();480}481 482llvm::Expected<uint32_t> MsvcStlForwardListFrontEnd::CalculateNumChildren() {483 if (m_count != UINT32_MAX)484 return m_count;485 486 ListEntry<StlType::MsvcStl> current(m_head);487 m_count = 0;488 while (current && m_count < m_list_capping_size) {489 ++m_count;490 current = current.next();491 }492 return m_count;493}494 495ValueObjectSP MsvcStlForwardListFrontEnd::GetChildAtIndex(uint32_t idx) {496 if (idx >= CalculateNumChildrenIgnoringErrors())497 return nullptr;498 499 if (!m_head)500 return nullptr;501 502 if (HasLoop(idx + 1))503 return nullptr;504 505 ValueObjectSP current_sp = GetItem(idx);506 if (!current_sp)507 return nullptr;508 509 current_sp = current_sp->GetChildAtIndex(1); // get the _Myval child510 if (!current_sp)511 return nullptr;512 513 // we need to copy current_sp into a new object otherwise we will end up with514 // all items named _Myval515 DataExtractor data;516 Status error;517 current_sp->GetData(data, error);518 if (error.Fail())519 return nullptr;520 521 return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data,522 m_backend.GetExecutionContextRef(),523 m_element_type);524}525 526lldb::ChildCacheState MsvcStlForwardListFrontEnd::Update() {527 AbstractListFrontEnd::Update();528 529 if (auto head_sp =530 m_backend.GetChildAtNamePath({"_Mypair", "_Myval2", "_Myhead"}))531 m_head = head_sp.get();532 533 return ChildCacheState::eRefetch;534}535 536MsvcStlListFrontEnd::MsvcStlListFrontEnd(lldb::ValueObjectSP valobj_sp)537 : AbstractListFrontEnd(*valobj_sp) {538 if (valobj_sp)539 Update();540}541 542llvm::Expected<uint32_t> MsvcStlListFrontEnd::CalculateNumChildren() {543 if (m_count != UINT32_MAX)544 return m_count;545 if (!m_head || !m_tail)546 return 0;547 548 auto size_sp =549 m_backend.GetChildAtNamePath({"_Mypair", "_Myval2", "_Mysize"});550 if (!size_sp)551 return llvm::createStringError("Failed to resolve size.");552 553 m_count = size_sp->GetValueAsUnsigned(UINT32_MAX);554 if (m_count == UINT32_MAX)555 return llvm::createStringError("Failed to read size value.");556 557 return m_count;558}559 560lldb::ValueObjectSP MsvcStlListFrontEnd::GetChildAtIndex(uint32_t idx) {561 if (idx >= CalculateNumChildrenIgnoringErrors())562 return lldb::ValueObjectSP();563 564 if (!m_head || !m_tail)565 return lldb::ValueObjectSP();566 567 if (HasLoop(idx + 1))568 return lldb::ValueObjectSP();569 570 ValueObjectSP current_sp = GetItem(idx);571 if (!current_sp)572 return lldb::ValueObjectSP();573 574 current_sp = current_sp->GetChildAtIndex(2); // get the _Myval child575 if (!current_sp)576 return lldb::ValueObjectSP();577 578 // we need to copy current_sp into a new object otherwise we will end up with579 // all items named _Myval580 DataExtractor data;581 Status error;582 current_sp->GetData(data, error);583 if (error.Fail())584 return lldb::ValueObjectSP();585 586 StreamString name;587 name.Printf("[%" PRIu64 "]", (uint64_t)idx);588 return CreateValueObjectFromData(name.GetString(), data,589 m_backend.GetExecutionContextRef(),590 m_element_type);591}592 593lldb::ChildCacheState MsvcStlListFrontEnd::Update() {594 AbstractListFrontEnd::Update();595 m_tail = nullptr;596 m_head = nullptr;597 598 ValueObjectSP last =599 m_backend.GetChildAtNamePath({"_Mypair", "_Myval2", "_Myhead"});600 if (!last)601 return lldb::ChildCacheState::eRefetch;602 ValueObjectSP first = last->GetChildMemberWithName("_Next");603 if (!first)604 return lldb::ChildCacheState::eRefetch;605 606 m_head = first.get();607 m_tail = last.get();608 609 return lldb::ChildCacheState::eRefetch;610}611 612SyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator(613 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {614 return (valobj_sp ? new LibCxxListFrontEnd(valobj_sp) : nullptr);615}616 617SyntheticChildrenFrontEnd *618formatters::LibcxxStdForwardListSyntheticFrontEndCreator(619 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {620 return valobj_sp ? new LibCxxForwardListFrontEnd(*valobj_sp) : nullptr;621}622 623bool formatters::IsMsvcStlList(ValueObject &valobj) {624 if (auto valobj_sp = valobj.GetNonSyntheticValue())625 return valobj_sp->GetChildMemberWithName("_Mypair") != nullptr;626 627 return false;628}629 630SyntheticChildrenFrontEnd *631formatters::MsvcStlListSyntheticFrontEndCreator(CXXSyntheticChildren *,632 lldb::ValueObjectSP valobj_sp) {633 return (valobj_sp ? new MsvcStlListFrontEnd(valobj_sp) : nullptr);634}635 636SyntheticChildrenFrontEnd *637formatters::MsvcStlForwardListSyntheticFrontEndCreator(638 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {639 return valobj_sp ? new MsvcStlForwardListFrontEnd(*valobj_sp) : nullptr;640}641