1292932Sdim//===-- LibCxxList.cpp ------------------------------------------*- C++ -*-===// 2292932Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6292932Sdim// 7292932Sdim//===----------------------------------------------------------------------===// 8292932Sdim 9292932Sdim#include "LibCxx.h" 10292932Sdim 11292932Sdim#include "lldb/Core/ValueObject.h" 12292932Sdim#include "lldb/Core/ValueObjectConstResult.h" 13292932Sdim#include "lldb/DataFormatters/FormattersHelpers.h" 14292932Sdim#include "lldb/Symbol/ClangASTContext.h" 15292932Sdim#include "lldb/Target/Target.h" 16321369Sdim#include "lldb/Utility/DataBufferHeap.h" 17321369Sdim#include "lldb/Utility/Endian.h" 18321369Sdim#include "lldb/Utility/Status.h" 19321369Sdim#include "lldb/Utility/Stream.h" 20292932Sdim 21292932Sdimusing namespace lldb; 22292932Sdimusing namespace lldb_private; 23292932Sdimusing namespace lldb_private::formatters; 24292932Sdim 25292932Sdimnamespace { 26292932Sdim 27314564Sdimclass ListEntry { 28314564Sdimpublic: 29314564Sdim ListEntry() = default; 30314564Sdim ListEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} 31314564Sdim ListEntry(const ListEntry &rhs) = default; 32314564Sdim ListEntry(ValueObject *entry) 33314564Sdim : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 34292932Sdim 35314564Sdim ListEntry next() { 36314564Sdim static ConstString g_next("__next_"); 37292932Sdim 38314564Sdim if (!m_entry_sp) 39314564Sdim return ListEntry(); 40314564Sdim return ListEntry(m_entry_sp->GetChildMemberWithName(g_next, true)); 41314564Sdim } 42292932Sdim 43314564Sdim ListEntry prev() { 44314564Sdim static ConstString g_prev("__prev_"); 45292932Sdim 46314564Sdim if (!m_entry_sp) 47314564Sdim return ListEntry(); 48314564Sdim return ListEntry(m_entry_sp->GetChildMemberWithName(g_prev, true)); 49314564Sdim } 50292932Sdim 51314564Sdim uint64_t value() const { 52314564Sdim if (!m_entry_sp) 53314564Sdim return 0; 54314564Sdim return m_entry_sp->GetValueAsUnsigned(0); 55314564Sdim } 56292932Sdim 57314564Sdim bool null() { return (value() == 0); } 58292932Sdim 59314564Sdim explicit operator bool() { return GetEntry() && !null(); } 60292932Sdim 61314564Sdim ValueObjectSP GetEntry() { return m_entry_sp; } 62292932Sdim 63314564Sdim void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } 64292932Sdim 65314564Sdim bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); } 66292932Sdim 67314564Sdim bool operator!=(const ListEntry &rhs) const { return !(*this == rhs); } 68314564Sdim 69314564Sdimprivate: 70314564Sdim ValueObjectSP m_entry_sp; 71314564Sdim}; 72314564Sdim 73314564Sdimclass ListIterator { 74314564Sdimpublic: 75314564Sdim ListIterator() = default; 76314564Sdim ListIterator(ListEntry entry) : m_entry(entry) {} 77314564Sdim ListIterator(ValueObjectSP entry) : m_entry(entry) {} 78314564Sdim ListIterator(const ListIterator &rhs) = default; 79314564Sdim ListIterator(ValueObject *entry) : m_entry(entry) {} 80314564Sdim 81314564Sdim ValueObjectSP value() { return m_entry.GetEntry(); } 82314564Sdim 83314564Sdim ValueObjectSP advance(size_t count) { 84314564Sdim if (count == 0) 85314564Sdim return m_entry.GetEntry(); 86314564Sdim if (count == 1) { 87314564Sdim next(); 88314564Sdim return m_entry.GetEntry(); 89314564Sdim } 90314564Sdim while (count > 0) { 91314564Sdim next(); 92314564Sdim count--; 93314564Sdim if (m_entry.null()) 94314564Sdim return lldb::ValueObjectSP(); 95314564Sdim } 96314564Sdim return m_entry.GetEntry(); 97314564Sdim } 98314564Sdim 99314564Sdim bool operator==(const ListIterator &rhs) const { 100314564Sdim return (rhs.m_entry == m_entry); 101314564Sdim } 102314564Sdim 103314564Sdimprotected: 104314564Sdim void next() { m_entry = m_entry.next(); } 105314564Sdim 106314564Sdim void prev() { m_entry = m_entry.prev(); } 107314564Sdim 108314564Sdimprivate: 109314564Sdim ListEntry m_entry; 110314564Sdim}; 111314564Sdim 112327952Sdimclass AbstractListFrontEnd : public SyntheticChildrenFrontEnd { 113314564Sdimpublic: 114353358Sdim size_t GetIndexOfChildWithName(ConstString name) override { 115327952Sdim return ExtractIndexFromString(name.GetCString()); 116327952Sdim } 117327952Sdim bool MightHaveChildren() override { return true; } 118327952Sdim bool Update() override; 119292932Sdim 120327952Sdimprotected: 121327952Sdim AbstractListFrontEnd(ValueObject &valobj) 122327952Sdim : SyntheticChildrenFrontEnd(valobj) {} 123292932Sdim 124327952Sdim size_t m_count; 125327952Sdim ValueObject *m_head; 126292932Sdim 127327952Sdim static constexpr bool g_use_loop_detect = true; 128327952Sdim size_t m_loop_detected; // The number of elements that have had loop detection 129327952Sdim // run over them. 130327952Sdim ListEntry m_slow_runner; // Used for loop detection 131327952Sdim ListEntry m_fast_runner; // Used for loop detection 132292932Sdim 133327952Sdim size_t m_list_capping_size; 134327952Sdim CompilerType m_element_type; 135327952Sdim std::map<size_t, ListIterator> m_iterators; 136327952Sdim 137327952Sdim bool HasLoop(size_t count); 138327952Sdim ValueObjectSP GetItem(size_t idx); 139327952Sdim}; 140327952Sdim 141327952Sdimclass ForwardListFrontEnd : public AbstractListFrontEnd { 142327952Sdimpublic: 143327952Sdim ForwardListFrontEnd(ValueObject &valobj); 144327952Sdim 145327952Sdim size_t CalculateNumChildren() override; 146327952Sdim ValueObjectSP GetChildAtIndex(size_t idx) override; 147314564Sdim bool Update() override; 148327952Sdim}; 149314564Sdim 150327952Sdimclass ListFrontEnd : public AbstractListFrontEnd { 151327952Sdimpublic: 152327952Sdim ListFrontEnd(lldb::ValueObjectSP valobj_sp); 153314564Sdim 154327952Sdim ~ListFrontEnd() override = default; 155314564Sdim 156327952Sdim size_t CalculateNumChildren() override; 157314564Sdim 158327952Sdim lldb::ValueObjectSP GetChildAtIndex(size_t idx) override; 159314564Sdim 160327952Sdim bool Update() override; 161314564Sdim 162327952Sdimprivate: 163314564Sdim lldb::addr_t m_node_address; 164314564Sdim ValueObject *m_tail; 165314564Sdim}; 166292932Sdim 167327952Sdim} // end anonymous namespace 168327952Sdim 169327952Sdimbool AbstractListFrontEnd::Update() { 170327952Sdim m_loop_detected = 0; 171327952Sdim m_count = UINT32_MAX; 172327952Sdim m_head = nullptr; 173327952Sdim m_list_capping_size = 0; 174327952Sdim m_slow_runner.SetEntry(nullptr); 175327952Sdim m_fast_runner.SetEntry(nullptr); 176327952Sdim m_iterators.clear(); 177327952Sdim 178327952Sdim if (m_backend.GetTargetSP()) 179327952Sdim m_list_capping_size = 180327952Sdim m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay(); 181327952Sdim if (m_list_capping_size == 0) 182327952Sdim m_list_capping_size = 255; 183327952Sdim 184327952Sdim CompilerType list_type = m_backend.GetCompilerType(); 185327952Sdim if (list_type.IsReferenceType()) 186327952Sdim list_type = list_type.GetNonReferenceType(); 187327952Sdim 188327952Sdim if (list_type.GetNumTemplateArguments() == 0) 189327952Sdim return false; 190327952Sdim m_element_type = list_type.GetTypeTemplateArgument(0); 191327952Sdim 192327952Sdim return false; 193292932Sdim} 194292932Sdim 195327952Sdimbool AbstractListFrontEnd::HasLoop(size_t count) { 196314564Sdim if (!g_use_loop_detect) 197314564Sdim return false; 198314564Sdim // don't bother checking for a loop if we won't actually need to jump nodes 199314564Sdim if (m_count < 2) 200314564Sdim return false; 201292932Sdim 202314564Sdim if (m_loop_detected == 0) { 203314564Sdim // This is the first time we are being run (after the last update). Set up 204341825Sdim // the loop invariant for the first element. 205314564Sdim m_slow_runner = ListEntry(m_head).next(); 206314564Sdim m_fast_runner = m_slow_runner.next(); 207314564Sdim m_loop_detected = 1; 208314564Sdim } 209292932Sdim 210314564Sdim // Loop invariant: 211314564Sdim // Loop detection has been run over the first m_loop_detected elements. If 212341825Sdim // m_slow_runner == m_fast_runner then the loop has been detected after 213341825Sdim // m_loop_detected elements. 214314564Sdim const size_t steps_to_run = std::min(count, m_count); 215314564Sdim while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner && 216314564Sdim m_slow_runner != m_fast_runner) { 217292932Sdim 218314564Sdim m_slow_runner = m_slow_runner.next(); 219314564Sdim m_fast_runner = m_fast_runner.next().next(); 220314564Sdim m_loop_detected++; 221314564Sdim } 222314564Sdim if (count <= m_loop_detected) 223314564Sdim return false; // No loop in the first m_loop_detected elements. 224314564Sdim if (!m_slow_runner || !m_fast_runner) 225314564Sdim return false; // Reached the end of the list. Definitely no loops. 226314564Sdim return m_slow_runner == m_fast_runner; 227292932Sdim} 228292932Sdim 229327952SdimValueObjectSP AbstractListFrontEnd::GetItem(size_t idx) { 230327952Sdim size_t advance = idx; 231327952Sdim ListIterator current(m_head); 232327952Sdim if (idx > 0) { 233327952Sdim auto cached_iterator = m_iterators.find(idx - 1); 234327952Sdim if (cached_iterator != m_iterators.end()) { 235327952Sdim current = cached_iterator->second; 236327952Sdim advance = 1; 237327952Sdim } 238327952Sdim } 239327952Sdim ValueObjectSP value_sp = current.advance(advance); 240327952Sdim m_iterators[idx] = current; 241327952Sdim return value_sp; 242327952Sdim} 243327952Sdim 244327952SdimForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj) 245327952Sdim : AbstractListFrontEnd(valobj) { 246327952Sdim Update(); 247327952Sdim} 248327952Sdim 249327952Sdimsize_t ForwardListFrontEnd::CalculateNumChildren() { 250314564Sdim if (m_count != UINT32_MAX) 251314564Sdim return m_count; 252327952Sdim 253327952Sdim ListEntry current(m_head); 254327952Sdim m_count = 0; 255327952Sdim while (current && m_count < m_list_capping_size) { 256327952Sdim ++m_count; 257327952Sdim current = current.next(); 258327952Sdim } 259327952Sdim return m_count; 260327952Sdim} 261327952Sdim 262327952SdimValueObjectSP ForwardListFrontEnd::GetChildAtIndex(size_t idx) { 263327952Sdim if (idx >= CalculateNumChildren()) 264327952Sdim return nullptr; 265327952Sdim 266327952Sdim if (!m_head) 267327952Sdim return nullptr; 268327952Sdim 269327952Sdim if (HasLoop(idx + 1)) 270327952Sdim return nullptr; 271327952Sdim 272327952Sdim ValueObjectSP current_sp = GetItem(idx); 273327952Sdim if (!current_sp) 274327952Sdim return nullptr; 275327952Sdim 276327952Sdim current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child 277327952Sdim if (!current_sp) 278327952Sdim return nullptr; 279327952Sdim 280327952Sdim // we need to copy current_sp into a new object otherwise we will end up with 281327952Sdim // all items named __value_ 282327952Sdim DataExtractor data; 283327952Sdim Status error; 284327952Sdim current_sp->GetData(data, error); 285327952Sdim if (error.Fail()) 286327952Sdim return nullptr; 287327952Sdim 288327952Sdim return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data, 289327952Sdim m_backend.GetExecutionContextRef(), 290327952Sdim m_element_type); 291327952Sdim} 292327952Sdim 293327952Sdimstatic ValueObjectSP GetValueOfCompressedPair(ValueObject &pair) { 294327952Sdim ValueObjectSP value = pair.GetChildMemberWithName(ConstString("__value_"), true); 295327952Sdim if (! value) { 296327952Sdim // pre-r300140 member name 297327952Sdim value = pair.GetChildMemberWithName(ConstString("__first_"), true); 298327952Sdim } 299327952Sdim return value; 300327952Sdim} 301327952Sdim 302327952Sdimbool ForwardListFrontEnd::Update() { 303327952Sdim AbstractListFrontEnd::Update(); 304327952Sdim 305327952Sdim Status err; 306327952Sdim ValueObjectSP backend_addr(m_backend.AddressOf(err)); 307327952Sdim if (err.Fail() || !backend_addr) 308327952Sdim return false; 309327952Sdim 310327952Sdim ValueObjectSP impl_sp( 311327952Sdim m_backend.GetChildMemberWithName(ConstString("__before_begin_"), true)); 312327952Sdim if (!impl_sp) 313327952Sdim return false; 314327952Sdim impl_sp = GetValueOfCompressedPair(*impl_sp); 315327952Sdim if (!impl_sp) 316327952Sdim return false; 317327952Sdim m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get(); 318327952Sdim return false; 319327952Sdim} 320327952Sdim 321327952SdimListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp) 322327952Sdim : AbstractListFrontEnd(*valobj_sp), m_node_address(), m_tail(nullptr) { 323327952Sdim if (valobj_sp) 324327952Sdim Update(); 325327952Sdim} 326327952Sdim 327327952Sdimsize_t ListFrontEnd::CalculateNumChildren() { 328327952Sdim if (m_count != UINT32_MAX) 329327952Sdim return m_count; 330314564Sdim if (!m_head || !m_tail || m_node_address == 0) 331314564Sdim return 0; 332314564Sdim ValueObjectSP size_alloc( 333314564Sdim m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true)); 334314564Sdim if (size_alloc) { 335327952Sdim ValueObjectSP value = GetValueOfCompressedPair(*size_alloc); 336327952Sdim if (value) { 337327952Sdim m_count = value->GetValueAsUnsigned(UINT32_MAX); 338292932Sdim } 339314564Sdim } 340314564Sdim if (m_count != UINT32_MAX) { 341314564Sdim return m_count; 342314564Sdim } else { 343314564Sdim uint64_t next_val = m_head->GetValueAsUnsigned(0); 344314564Sdim uint64_t prev_val = m_tail->GetValueAsUnsigned(0); 345314564Sdim if (next_val == 0 || prev_val == 0) 346314564Sdim return 0; 347314564Sdim if (next_val == m_node_address) 348314564Sdim return 0; 349314564Sdim if (next_val == prev_val) 350314564Sdim return 1; 351314564Sdim uint64_t size = 2; 352314564Sdim ListEntry current(m_head); 353314564Sdim while (current.next() && current.next().value() != m_node_address) { 354314564Sdim size++; 355314564Sdim current = current.next(); 356314564Sdim if (size > m_list_capping_size) 357314564Sdim break; 358292932Sdim } 359314564Sdim return m_count = (size - 1); 360314564Sdim } 361292932Sdim} 362292932Sdim 363327952Sdimlldb::ValueObjectSP ListFrontEnd::GetChildAtIndex(size_t idx) { 364314564Sdim static ConstString g_value("__value_"); 365314564Sdim static ConstString g_next("__next_"); 366314564Sdim 367314564Sdim if (idx >= CalculateNumChildren()) 368314564Sdim return lldb::ValueObjectSP(); 369314564Sdim 370314564Sdim if (!m_head || !m_tail || m_node_address == 0) 371314564Sdim return lldb::ValueObjectSP(); 372314564Sdim 373314564Sdim if (HasLoop(idx + 1)) 374314564Sdim return lldb::ValueObjectSP(); 375314564Sdim 376327952Sdim ValueObjectSP current_sp = GetItem(idx); 377314564Sdim if (!current_sp) 378314564Sdim return lldb::ValueObjectSP(); 379314564Sdim 380314564Sdim current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child 381314564Sdim if (!current_sp) 382314564Sdim return lldb::ValueObjectSP(); 383314564Sdim 384314564Sdim if (current_sp->GetName() == g_next) { 385314564Sdim ProcessSP process_sp(current_sp->GetProcessSP()); 386314564Sdim if (!process_sp) 387353358Sdim return lldb::ValueObjectSP(); 388314564Sdim 389314564Sdim // if we grabbed the __next_ pointer, then the child is one pointer deep-er 390314564Sdim lldb::addr_t addr = current_sp->GetParent()->GetPointerValue(); 391314564Sdim addr = addr + 2 * process_sp->GetAddressByteSize(); 392314564Sdim ExecutionContext exe_ctx(process_sp); 393314564Sdim current_sp = 394314564Sdim CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type); 395353358Sdim if (!current_sp) 396353358Sdim return lldb::ValueObjectSP(); 397314564Sdim } 398314564Sdim 399314564Sdim // we need to copy current_sp into a new object otherwise we will end up with 400314564Sdim // all items named __value_ 401314564Sdim DataExtractor data; 402321369Sdim Status error; 403314564Sdim current_sp->GetData(data, error); 404314564Sdim if (error.Fail()) 405314564Sdim return lldb::ValueObjectSP(); 406314564Sdim 407314564Sdim StreamString name; 408314564Sdim name.Printf("[%" PRIu64 "]", (uint64_t)idx); 409314564Sdim return CreateValueObjectFromData(name.GetString(), data, 410314564Sdim m_backend.GetExecutionContextRef(), 411314564Sdim m_element_type); 412292932Sdim} 413292932Sdim 414327952Sdimbool ListFrontEnd::Update() { 415327952Sdim AbstractListFrontEnd::Update(); 416327952Sdim m_tail = nullptr; 417314564Sdim m_node_address = 0; 418292932Sdim 419321369Sdim Status err; 420314564Sdim ValueObjectSP backend_addr(m_backend.AddressOf(err)); 421314564Sdim if (err.Fail() || !backend_addr) 422314564Sdim return false; 423314564Sdim m_node_address = backend_addr->GetValueAsUnsigned(0); 424314564Sdim if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS) 425314564Sdim return false; 426314564Sdim ValueObjectSP impl_sp( 427314564Sdim m_backend.GetChildMemberWithName(ConstString("__end_"), true)); 428314564Sdim if (!impl_sp) 429314564Sdim return false; 430314564Sdim m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get(); 431314564Sdim m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get(); 432314564Sdim return false; 433292932Sdim} 434292932Sdim 435327952SdimSyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator( 436327952Sdim CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 437327952Sdim return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr); 438292932Sdim} 439292932Sdim 440314564SdimSyntheticChildrenFrontEnd * 441327952Sdimformatters::LibcxxStdForwardListSyntheticFrontEndCreator( 442314564Sdim CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 443327952Sdim return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr; 444292932Sdim} 445