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