LibCxxList.cpp revision 321369
1292932Sdim//===-- LibCxxList.cpp ------------------------------------------*- C++ -*-===// 2292932Sdim// 3292932Sdim// The LLVM Compiler Infrastructure 4292932Sdim// 5292932Sdim// This file is distributed under the University of Illinois Open Source 6292932Sdim// License. See LICENSE.TXT for details. 7292932Sdim// 8292932Sdim//===----------------------------------------------------------------------===// 9292932Sdim 10292932Sdim// C Includes 11292932Sdim// C++ Includes 12292932Sdim// Other libraries and framework includes 13292932Sdim// Project includes 14292932Sdim#include "LibCxx.h" 15292932Sdim 16292932Sdim#include "lldb/Core/ValueObject.h" 17292932Sdim#include "lldb/Core/ValueObjectConstResult.h" 18292932Sdim#include "lldb/DataFormatters/FormattersHelpers.h" 19292932Sdim#include "lldb/Symbol/ClangASTContext.h" 20292932Sdim#include "lldb/Target/Target.h" 21321369Sdim#include "lldb/Utility/DataBufferHeap.h" 22321369Sdim#include "lldb/Utility/Endian.h" 23321369Sdim#include "lldb/Utility/Status.h" 24321369Sdim#include "lldb/Utility/Stream.h" 25292932Sdim 26292932Sdimusing namespace lldb; 27292932Sdimusing namespace lldb_private; 28292932Sdimusing namespace lldb_private::formatters; 29292932Sdim 30292932Sdimnamespace { 31292932Sdim 32314564Sdimclass ListEntry { 33314564Sdimpublic: 34314564Sdim ListEntry() = default; 35314564Sdim ListEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} 36314564Sdim ListEntry(const ListEntry &rhs) = default; 37314564Sdim ListEntry(ValueObject *entry) 38314564Sdim : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 39292932Sdim 40314564Sdim ListEntry next() { 41314564Sdim static ConstString g_next("__next_"); 42292932Sdim 43314564Sdim if (!m_entry_sp) 44314564Sdim return ListEntry(); 45314564Sdim return ListEntry(m_entry_sp->GetChildMemberWithName(g_next, true)); 46314564Sdim } 47292932Sdim 48314564Sdim ListEntry prev() { 49314564Sdim static ConstString g_prev("__prev_"); 50292932Sdim 51314564Sdim if (!m_entry_sp) 52314564Sdim return ListEntry(); 53314564Sdim return ListEntry(m_entry_sp->GetChildMemberWithName(g_prev, true)); 54314564Sdim } 55292932Sdim 56314564Sdim uint64_t value() const { 57314564Sdim if (!m_entry_sp) 58314564Sdim return 0; 59314564Sdim return m_entry_sp->GetValueAsUnsigned(0); 60314564Sdim } 61292932Sdim 62314564Sdim bool null() { return (value() == 0); } 63292932Sdim 64314564Sdim explicit operator bool() { return GetEntry() && !null(); } 65292932Sdim 66314564Sdim ValueObjectSP GetEntry() { return m_entry_sp; } 67292932Sdim 68314564Sdim void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } 69292932Sdim 70314564Sdim bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); } 71292932Sdim 72314564Sdim bool operator!=(const ListEntry &rhs) const { return !(*this == rhs); } 73314564Sdim 74314564Sdimprivate: 75314564Sdim ValueObjectSP m_entry_sp; 76314564Sdim}; 77314564Sdim 78314564Sdimclass ListIterator { 79314564Sdimpublic: 80314564Sdim ListIterator() = default; 81314564Sdim ListIterator(ListEntry entry) : m_entry(entry) {} 82314564Sdim ListIterator(ValueObjectSP entry) : m_entry(entry) {} 83314564Sdim ListIterator(const ListIterator &rhs) = default; 84314564Sdim ListIterator(ValueObject *entry) : m_entry(entry) {} 85314564Sdim 86314564Sdim ValueObjectSP value() { return m_entry.GetEntry(); } 87314564Sdim 88314564Sdim ValueObjectSP advance(size_t count) { 89314564Sdim if (count == 0) 90314564Sdim return m_entry.GetEntry(); 91314564Sdim if (count == 1) { 92314564Sdim next(); 93314564Sdim return m_entry.GetEntry(); 94314564Sdim } 95314564Sdim while (count > 0) { 96314564Sdim next(); 97314564Sdim count--; 98314564Sdim if (m_entry.null()) 99314564Sdim return lldb::ValueObjectSP(); 100314564Sdim } 101314564Sdim return m_entry.GetEntry(); 102314564Sdim } 103314564Sdim 104314564Sdim bool operator==(const ListIterator &rhs) const { 105314564Sdim return (rhs.m_entry == m_entry); 106314564Sdim } 107314564Sdim 108314564Sdimprotected: 109314564Sdim void next() { m_entry = m_entry.next(); } 110314564Sdim 111314564Sdim void prev() { m_entry = m_entry.prev(); } 112314564Sdim 113314564Sdimprivate: 114314564Sdim ListEntry m_entry; 115314564Sdim}; 116314564Sdim 117292932Sdim} // end anonymous namespace 118292932Sdim 119292932Sdimnamespace lldb_private { 120314564Sdimnamespace formatters { 121314564Sdimclass LibcxxStdListSyntheticFrontEnd : public SyntheticChildrenFrontEnd { 122314564Sdimpublic: 123314564Sdim LibcxxStdListSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); 124292932Sdim 125314564Sdim ~LibcxxStdListSyntheticFrontEnd() override = default; 126292932Sdim 127314564Sdim size_t CalculateNumChildren() override; 128292932Sdim 129314564Sdim lldb::ValueObjectSP GetChildAtIndex(size_t idx) override; 130292932Sdim 131314564Sdim bool Update() override; 132314564Sdim 133314564Sdim bool MightHaveChildren() override; 134314564Sdim 135314564Sdim size_t GetIndexOfChildWithName(const ConstString &name) override; 136314564Sdim 137314564Sdimprivate: 138314564Sdim bool HasLoop(size_t count); 139314564Sdim 140314564Sdim size_t m_list_capping_size; 141314564Sdim static const bool g_use_loop_detect = true; 142314564Sdim 143314564Sdim size_t m_loop_detected; // The number of elements that have had loop detection 144314564Sdim // run over them. 145314564Sdim ListEntry m_slow_runner; // Used for loop detection 146314564Sdim ListEntry m_fast_runner; // Used for loop detection 147314564Sdim 148314564Sdim lldb::addr_t m_node_address; 149314564Sdim ValueObject *m_head; 150314564Sdim ValueObject *m_tail; 151314564Sdim CompilerType m_element_type; 152314564Sdim size_t m_count; 153314564Sdim std::map<size_t, ListIterator> m_iterators; 154314564Sdim}; 155314564Sdim} // namespace formatters 156292932Sdim} // namespace lldb_private 157292932Sdim 158314564Sdimlldb_private::formatters::LibcxxStdListSyntheticFrontEnd:: 159314564Sdim LibcxxStdListSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) 160314564Sdim : SyntheticChildrenFrontEnd(*valobj_sp), m_list_capping_size(0), 161314564Sdim m_loop_detected(0), m_node_address(), m_head(nullptr), m_tail(nullptr), 162314564Sdim m_element_type(), m_count(UINT32_MAX), m_iterators() { 163314564Sdim if (valobj_sp) 164314564Sdim Update(); 165292932Sdim} 166292932Sdim 167314564Sdimbool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::HasLoop( 168314564Sdim size_t count) { 169314564Sdim if (!g_use_loop_detect) 170314564Sdim return false; 171314564Sdim // don't bother checking for a loop if we won't actually need to jump nodes 172314564Sdim if (m_count < 2) 173314564Sdim return false; 174292932Sdim 175314564Sdim if (m_loop_detected == 0) { 176314564Sdim // This is the first time we are being run (after the last update). Set up 177314564Sdim // the loop 178314564Sdim // invariant for the first element. 179314564Sdim m_slow_runner = ListEntry(m_head).next(); 180314564Sdim m_fast_runner = m_slow_runner.next(); 181314564Sdim m_loop_detected = 1; 182314564Sdim } 183292932Sdim 184314564Sdim // Loop invariant: 185314564Sdim // Loop detection has been run over the first m_loop_detected elements. If 186314564Sdim // m_slow_runner == 187314564Sdim // m_fast_runner then the loop has been detected after m_loop_detected 188314564Sdim // elements. 189314564Sdim const size_t steps_to_run = std::min(count, m_count); 190314564Sdim while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner && 191314564Sdim m_slow_runner != m_fast_runner) { 192292932Sdim 193314564Sdim m_slow_runner = m_slow_runner.next(); 194314564Sdim m_fast_runner = m_fast_runner.next().next(); 195314564Sdim m_loop_detected++; 196314564Sdim } 197314564Sdim if (count <= m_loop_detected) 198314564Sdim return false; // No loop in the first m_loop_detected elements. 199314564Sdim if (!m_slow_runner || !m_fast_runner) 200314564Sdim return false; // Reached the end of the list. Definitely no loops. 201314564Sdim return m_slow_runner == m_fast_runner; 202292932Sdim} 203292932Sdim 204314564Sdimsize_t lldb_private::formatters::LibcxxStdListSyntheticFrontEnd:: 205314564Sdim CalculateNumChildren() { 206314564Sdim if (m_count != UINT32_MAX) 207314564Sdim return m_count; 208314564Sdim if (!m_head || !m_tail || m_node_address == 0) 209314564Sdim return 0; 210314564Sdim ValueObjectSP size_alloc( 211314564Sdim m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true)); 212314564Sdim if (size_alloc) { 213314564Sdim ValueObjectSP first( 214314564Sdim size_alloc->GetChildMemberWithName(ConstString("__first_"), true)); 215314564Sdim if (first) { 216314564Sdim m_count = first->GetValueAsUnsigned(UINT32_MAX); 217292932Sdim } 218314564Sdim } 219314564Sdim if (m_count != UINT32_MAX) { 220314564Sdim return m_count; 221314564Sdim } else { 222314564Sdim uint64_t next_val = m_head->GetValueAsUnsigned(0); 223314564Sdim uint64_t prev_val = m_tail->GetValueAsUnsigned(0); 224314564Sdim if (next_val == 0 || prev_val == 0) 225314564Sdim return 0; 226314564Sdim if (next_val == m_node_address) 227314564Sdim return 0; 228314564Sdim if (next_val == prev_val) 229314564Sdim return 1; 230314564Sdim uint64_t size = 2; 231314564Sdim ListEntry current(m_head); 232314564Sdim while (current.next() && current.next().value() != m_node_address) { 233314564Sdim size++; 234314564Sdim current = current.next(); 235314564Sdim if (size > m_list_capping_size) 236314564Sdim break; 237292932Sdim } 238314564Sdim return m_count = (size - 1); 239314564Sdim } 240292932Sdim} 241292932Sdim 242292932Sdimlldb::ValueObjectSP 243314564Sdimlldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetChildAtIndex( 244314564Sdim size_t idx) { 245314564Sdim static ConstString g_value("__value_"); 246314564Sdim static ConstString g_next("__next_"); 247314564Sdim 248314564Sdim if (idx >= CalculateNumChildren()) 249314564Sdim return lldb::ValueObjectSP(); 250314564Sdim 251314564Sdim if (!m_head || !m_tail || m_node_address == 0) 252314564Sdim return lldb::ValueObjectSP(); 253314564Sdim 254314564Sdim if (HasLoop(idx + 1)) 255314564Sdim return lldb::ValueObjectSP(); 256314564Sdim 257314564Sdim size_t actual_advance = idx; 258314564Sdim 259314564Sdim ListIterator current(m_head); 260314564Sdim if (idx > 0) { 261314564Sdim auto cached_iterator = m_iterators.find(idx - 1); 262314564Sdim if (cached_iterator != m_iterators.end()) { 263314564Sdim current = cached_iterator->second; 264314564Sdim actual_advance = 1; 265292932Sdim } 266314564Sdim } 267314564Sdim 268314564Sdim ValueObjectSP current_sp(current.advance(actual_advance)); 269314564Sdim if (!current_sp) 270314564Sdim return lldb::ValueObjectSP(); 271314564Sdim 272314564Sdim m_iterators[idx] = current; 273314564Sdim 274314564Sdim current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child 275314564Sdim if (!current_sp) 276314564Sdim return lldb::ValueObjectSP(); 277314564Sdim 278314564Sdim if (current_sp->GetName() == g_next) { 279314564Sdim ProcessSP process_sp(current_sp->GetProcessSP()); 280314564Sdim if (!process_sp) 281314564Sdim return nullptr; 282314564Sdim 283314564Sdim // if we grabbed the __next_ pointer, then the child is one pointer deep-er 284314564Sdim lldb::addr_t addr = current_sp->GetParent()->GetPointerValue(); 285314564Sdim addr = addr + 2 * process_sp->GetAddressByteSize(); 286314564Sdim ExecutionContext exe_ctx(process_sp); 287314564Sdim current_sp = 288314564Sdim CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type); 289314564Sdim } 290314564Sdim 291314564Sdim // we need to copy current_sp into a new object otherwise we will end up with 292314564Sdim // all items named __value_ 293314564Sdim DataExtractor data; 294321369Sdim Status error; 295314564Sdim current_sp->GetData(data, error); 296314564Sdim if (error.Fail()) 297314564Sdim return lldb::ValueObjectSP(); 298314564Sdim 299314564Sdim StreamString name; 300314564Sdim name.Printf("[%" PRIu64 "]", (uint64_t)idx); 301314564Sdim return CreateValueObjectFromData(name.GetString(), data, 302314564Sdim m_backend.GetExecutionContextRef(), 303314564Sdim m_element_type); 304292932Sdim} 305292932Sdim 306314564Sdimbool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::Update() { 307314564Sdim m_iterators.clear(); 308314564Sdim m_head = m_tail = nullptr; 309314564Sdim m_node_address = 0; 310314564Sdim m_count = UINT32_MAX; 311314564Sdim m_loop_detected = 0; 312314564Sdim m_slow_runner.SetEntry(nullptr); 313314564Sdim m_fast_runner.SetEntry(nullptr); 314292932Sdim 315321369Sdim Status err; 316314564Sdim ValueObjectSP backend_addr(m_backend.AddressOf(err)); 317314564Sdim m_list_capping_size = 0; 318314564Sdim if (m_backend.GetTargetSP()) 319314564Sdim m_list_capping_size = 320314564Sdim m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay(); 321314564Sdim if (m_list_capping_size == 0) 322314564Sdim m_list_capping_size = 255; 323314564Sdim if (err.Fail() || !backend_addr) 324314564Sdim return false; 325314564Sdim m_node_address = backend_addr->GetValueAsUnsigned(0); 326314564Sdim if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS) 327314564Sdim return false; 328314564Sdim ValueObjectSP impl_sp( 329314564Sdim m_backend.GetChildMemberWithName(ConstString("__end_"), true)); 330314564Sdim if (!impl_sp) 331314564Sdim return false; 332314564Sdim CompilerType list_type = m_backend.GetCompilerType(); 333314564Sdim if (list_type.IsReferenceType()) 334314564Sdim list_type = list_type.GetNonReferenceType(); 335292932Sdim 336314564Sdim if (list_type.GetNumTemplateArguments() == 0) 337292932Sdim return false; 338314564Sdim lldb::TemplateArgumentKind kind; 339314564Sdim m_element_type = list_type.GetTemplateArgument(0, kind); 340314564Sdim m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get(); 341314564Sdim m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get(); 342314564Sdim return false; 343292932Sdim} 344292932Sdim 345314564Sdimbool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd:: 346314564Sdim MightHaveChildren() { 347314564Sdim return true; 348292932Sdim} 349292932Sdim 350314564Sdimsize_t lldb_private::formatters::LibcxxStdListSyntheticFrontEnd:: 351314564Sdim GetIndexOfChildWithName(const ConstString &name) { 352314564Sdim return ExtractIndexFromString(name.GetCString()); 353292932Sdim} 354292932Sdim 355314564SdimSyntheticChildrenFrontEnd * 356314564Sdimlldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator( 357314564Sdim CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 358314564Sdim return (valobj_sp ? new LibcxxStdListSyntheticFrontEnd(valobj_sp) : nullptr); 359292932Sdim} 360