1//===-- LibCxxList.cpp ------------------------------------------*- C++ -*-===// 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-exception 6// 7//===----------------------------------------------------------------------===// 8 9#include "LibCxx.h" 10 11#include "lldb/Core/ValueObject.h" 12#include "lldb/Core/ValueObjectConstResult.h" 13#include "lldb/DataFormatters/FormattersHelpers.h" 14#include "lldb/Symbol/ClangASTContext.h" 15#include "lldb/Target/Target.h" 16#include "lldb/Utility/DataBufferHeap.h" 17#include "lldb/Utility/Endian.h" 18#include "lldb/Utility/Status.h" 19#include "lldb/Utility/Stream.h" 20 21using namespace lldb; 22using namespace lldb_private; 23using namespace lldb_private::formatters; 24 25namespace { 26 27class ListEntry { 28public: 29 ListEntry() = default; 30 ListEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} 31 ListEntry(const ListEntry &rhs) = default; 32 ListEntry(ValueObject *entry) 33 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 34 35 ListEntry next() { 36 static ConstString g_next("__next_"); 37 38 if (!m_entry_sp) 39 return ListEntry(); 40 return ListEntry(m_entry_sp->GetChildMemberWithName(g_next, true)); 41 } 42 43 ListEntry prev() { 44 static ConstString g_prev("__prev_"); 45 46 if (!m_entry_sp) 47 return ListEntry(); 48 return ListEntry(m_entry_sp->GetChildMemberWithName(g_prev, true)); 49 } 50 51 uint64_t value() const { 52 if (!m_entry_sp) 53 return 0; 54 return m_entry_sp->GetValueAsUnsigned(0); 55 } 56 57 bool null() { return (value() == 0); } 58 59 explicit operator bool() { return GetEntry() && !null(); } 60 61 ValueObjectSP GetEntry() { return m_entry_sp; } 62 63 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } 64 65 bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); } 66 67 bool operator!=(const ListEntry &rhs) const { return !(*this == rhs); } 68 69private: 70 ValueObjectSP m_entry_sp; 71}; 72 73class ListIterator { 74public: 75 ListIterator() = default; 76 ListIterator(ListEntry entry) : m_entry(entry) {} 77 ListIterator(ValueObjectSP entry) : m_entry(entry) {} 78 ListIterator(const ListIterator &rhs) = default; 79 ListIterator(ValueObject *entry) : m_entry(entry) {} 80 81 ValueObjectSP value() { return m_entry.GetEntry(); } 82 83 ValueObjectSP advance(size_t count) { 84 if (count == 0) 85 return m_entry.GetEntry(); 86 if (count == 1) { 87 next(); 88 return m_entry.GetEntry(); 89 } 90 while (count > 0) { 91 next(); 92 count--; 93 if (m_entry.null()) 94 return lldb::ValueObjectSP(); 95 } 96 return m_entry.GetEntry(); 97 } 98 99 bool operator==(const ListIterator &rhs) const { 100 return (rhs.m_entry == m_entry); 101 } 102 103protected: 104 void next() { m_entry = m_entry.next(); } 105 106 void prev() { m_entry = m_entry.prev(); } 107 108private: 109 ListEntry m_entry; 110}; 111 112class AbstractListFrontEnd : public SyntheticChildrenFrontEnd { 113public: 114 size_t GetIndexOfChildWithName(ConstString name) override { 115 return ExtractIndexFromString(name.GetCString()); 116 } 117 bool MightHaveChildren() override { return true; } 118 bool Update() override; 119 120protected: 121 AbstractListFrontEnd(ValueObject &valobj) 122 : SyntheticChildrenFrontEnd(valobj) {} 123 124 size_t m_count; 125 ValueObject *m_head; 126 127 static constexpr bool g_use_loop_detect = true; 128 size_t m_loop_detected; // The number of elements that have had loop detection 129 // run over them. 130 ListEntry m_slow_runner; // Used for loop detection 131 ListEntry m_fast_runner; // Used for loop detection 132 133 size_t m_list_capping_size; 134 CompilerType m_element_type; 135 std::map<size_t, ListIterator> m_iterators; 136 137 bool HasLoop(size_t count); 138 ValueObjectSP GetItem(size_t idx); 139}; 140 141class ForwardListFrontEnd : public AbstractListFrontEnd { 142public: 143 ForwardListFrontEnd(ValueObject &valobj); 144 145 size_t CalculateNumChildren() override; 146 ValueObjectSP GetChildAtIndex(size_t idx) override; 147 bool Update() override; 148}; 149 150class ListFrontEnd : public AbstractListFrontEnd { 151public: 152 ListFrontEnd(lldb::ValueObjectSP valobj_sp); 153 154 ~ListFrontEnd() override = default; 155 156 size_t CalculateNumChildren() override; 157 158 lldb::ValueObjectSP GetChildAtIndex(size_t idx) override; 159 160 bool Update() override; 161 162private: 163 lldb::addr_t m_node_address; 164 ValueObject *m_tail; 165}; 166 167} // end anonymous namespace 168 169bool AbstractListFrontEnd::Update() { 170 m_loop_detected = 0; 171 m_count = UINT32_MAX; 172 m_head = nullptr; 173 m_list_capping_size = 0; 174 m_slow_runner.SetEntry(nullptr); 175 m_fast_runner.SetEntry(nullptr); 176 m_iterators.clear(); 177 178 if (m_backend.GetTargetSP()) 179 m_list_capping_size = 180 m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay(); 181 if (m_list_capping_size == 0) 182 m_list_capping_size = 255; 183 184 CompilerType list_type = m_backend.GetCompilerType(); 185 if (list_type.IsReferenceType()) 186 list_type = list_type.GetNonReferenceType(); 187 188 if (list_type.GetNumTemplateArguments() == 0) 189 return false; 190 m_element_type = list_type.GetTypeTemplateArgument(0); 191 192 return false; 193} 194 195bool AbstractListFrontEnd::HasLoop(size_t count) { 196 if (!g_use_loop_detect) 197 return false; 198 // don't bother checking for a loop if we won't actually need to jump nodes 199 if (m_count < 2) 200 return false; 201 202 if (m_loop_detected == 0) { 203 // This is the first time we are being run (after the last update). Set up 204 // the loop invariant for the first element. 205 m_slow_runner = ListEntry(m_head).next(); 206 m_fast_runner = m_slow_runner.next(); 207 m_loop_detected = 1; 208 } 209 210 // Loop invariant: 211 // Loop detection has been run over the first m_loop_detected elements. If 212 // m_slow_runner == m_fast_runner then the loop has been detected after 213 // m_loop_detected elements. 214 const size_t steps_to_run = std::min(count, m_count); 215 while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner && 216 m_slow_runner != m_fast_runner) { 217 218 m_slow_runner = m_slow_runner.next(); 219 m_fast_runner = m_fast_runner.next().next(); 220 m_loop_detected++; 221 } 222 if (count <= m_loop_detected) 223 return false; // No loop in the first m_loop_detected elements. 224 if (!m_slow_runner || !m_fast_runner) 225 return false; // Reached the end of the list. Definitely no loops. 226 return m_slow_runner == m_fast_runner; 227} 228 229ValueObjectSP AbstractListFrontEnd::GetItem(size_t idx) { 230 size_t advance = idx; 231 ListIterator current(m_head); 232 if (idx > 0) { 233 auto cached_iterator = m_iterators.find(idx - 1); 234 if (cached_iterator != m_iterators.end()) { 235 current = cached_iterator->second; 236 advance = 1; 237 } 238 } 239 ValueObjectSP value_sp = current.advance(advance); 240 m_iterators[idx] = current; 241 return value_sp; 242} 243 244ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj) 245 : AbstractListFrontEnd(valobj) { 246 Update(); 247} 248 249size_t ForwardListFrontEnd::CalculateNumChildren() { 250 if (m_count != UINT32_MAX) 251 return m_count; 252 253 ListEntry current(m_head); 254 m_count = 0; 255 while (current && m_count < m_list_capping_size) { 256 ++m_count; 257 current = current.next(); 258 } 259 return m_count; 260} 261 262ValueObjectSP ForwardListFrontEnd::GetChildAtIndex(size_t idx) { 263 if (idx >= CalculateNumChildren()) 264 return nullptr; 265 266 if (!m_head) 267 return nullptr; 268 269 if (HasLoop(idx + 1)) 270 return nullptr; 271 272 ValueObjectSP current_sp = GetItem(idx); 273 if (!current_sp) 274 return nullptr; 275 276 current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child 277 if (!current_sp) 278 return nullptr; 279 280 // we need to copy current_sp into a new object otherwise we will end up with 281 // all items named __value_ 282 DataExtractor data; 283 Status error; 284 current_sp->GetData(data, error); 285 if (error.Fail()) 286 return nullptr; 287 288 return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data, 289 m_backend.GetExecutionContextRef(), 290 m_element_type); 291} 292 293static ValueObjectSP GetValueOfCompressedPair(ValueObject &pair) { 294 ValueObjectSP value = pair.GetChildMemberWithName(ConstString("__value_"), true); 295 if (! value) { 296 // pre-r300140 member name 297 value = pair.GetChildMemberWithName(ConstString("__first_"), true); 298 } 299 return value; 300} 301 302bool ForwardListFrontEnd::Update() { 303 AbstractListFrontEnd::Update(); 304 305 Status err; 306 ValueObjectSP backend_addr(m_backend.AddressOf(err)); 307 if (err.Fail() || !backend_addr) 308 return false; 309 310 ValueObjectSP impl_sp( 311 m_backend.GetChildMemberWithName(ConstString("__before_begin_"), true)); 312 if (!impl_sp) 313 return false; 314 impl_sp = GetValueOfCompressedPair(*impl_sp); 315 if (!impl_sp) 316 return false; 317 m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get(); 318 return false; 319} 320 321ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp) 322 : AbstractListFrontEnd(*valobj_sp), m_node_address(), m_tail(nullptr) { 323 if (valobj_sp) 324 Update(); 325} 326 327size_t ListFrontEnd::CalculateNumChildren() { 328 if (m_count != UINT32_MAX) 329 return m_count; 330 if (!m_head || !m_tail || m_node_address == 0) 331 return 0; 332 ValueObjectSP size_alloc( 333 m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true)); 334 if (size_alloc) { 335 ValueObjectSP value = GetValueOfCompressedPair(*size_alloc); 336 if (value) { 337 m_count = value->GetValueAsUnsigned(UINT32_MAX); 338 } 339 } 340 if (m_count != UINT32_MAX) { 341 return m_count; 342 } else { 343 uint64_t next_val = m_head->GetValueAsUnsigned(0); 344 uint64_t prev_val = m_tail->GetValueAsUnsigned(0); 345 if (next_val == 0 || prev_val == 0) 346 return 0; 347 if (next_val == m_node_address) 348 return 0; 349 if (next_val == prev_val) 350 return 1; 351 uint64_t size = 2; 352 ListEntry current(m_head); 353 while (current.next() && current.next().value() != m_node_address) { 354 size++; 355 current = current.next(); 356 if (size > m_list_capping_size) 357 break; 358 } 359 return m_count = (size - 1); 360 } 361} 362 363lldb::ValueObjectSP ListFrontEnd::GetChildAtIndex(size_t idx) { 364 static ConstString g_value("__value_"); 365 static ConstString g_next("__next_"); 366 367 if (idx >= CalculateNumChildren()) 368 return lldb::ValueObjectSP(); 369 370 if (!m_head || !m_tail || m_node_address == 0) 371 return lldb::ValueObjectSP(); 372 373 if (HasLoop(idx + 1)) 374 return lldb::ValueObjectSP(); 375 376 ValueObjectSP current_sp = GetItem(idx); 377 if (!current_sp) 378 return lldb::ValueObjectSP(); 379 380 current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child 381 if (!current_sp) 382 return lldb::ValueObjectSP(); 383 384 if (current_sp->GetName() == g_next) { 385 ProcessSP process_sp(current_sp->GetProcessSP()); 386 if (!process_sp) 387 return lldb::ValueObjectSP(); 388 389 // if we grabbed the __next_ pointer, then the child is one pointer deep-er 390 lldb::addr_t addr = current_sp->GetParent()->GetPointerValue(); 391 addr = addr + 2 * process_sp->GetAddressByteSize(); 392 ExecutionContext exe_ctx(process_sp); 393 current_sp = 394 CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type); 395 if (!current_sp) 396 return lldb::ValueObjectSP(); 397 } 398 399 // we need to copy current_sp into a new object otherwise we will end up with 400 // all items named __value_ 401 DataExtractor data; 402 Status error; 403 current_sp->GetData(data, error); 404 if (error.Fail()) 405 return lldb::ValueObjectSP(); 406 407 StreamString name; 408 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 409 return CreateValueObjectFromData(name.GetString(), data, 410 m_backend.GetExecutionContextRef(), 411 m_element_type); 412} 413 414bool ListFrontEnd::Update() { 415 AbstractListFrontEnd::Update(); 416 m_tail = nullptr; 417 m_node_address = 0; 418 419 Status err; 420 ValueObjectSP backend_addr(m_backend.AddressOf(err)); 421 if (err.Fail() || !backend_addr) 422 return false; 423 m_node_address = backend_addr->GetValueAsUnsigned(0); 424 if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS) 425 return false; 426 ValueObjectSP impl_sp( 427 m_backend.GetChildMemberWithName(ConstString("__end_"), true)); 428 if (!impl_sp) 429 return false; 430 m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get(); 431 m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get(); 432 return false; 433} 434 435SyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator( 436 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 437 return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr); 438} 439 440SyntheticChildrenFrontEnd * 441formatters::LibcxxStdForwardListSyntheticFrontEndCreator( 442 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 443 return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr; 444} 445