contrib/llvm-project/lldb/source/Plugins/Language/CPlusPlus/LibCxxList.cpp

   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
  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(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
  69 private:
  70   ValueObjectSP m_entry_sp;
  71 };
  72
  73 class ListIterator {
  74 public:
  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
 103 protected:
 104   void next() { m_entry = m_entry.next(); }
 105
 106   void prev() { m_entry = m_entry.prev(); }
 107
 108 private:
 109   ListEntry m_entry;
 110 };
 111
 112 class AbstractListFrontEnd : public SyntheticChildrenFrontEnd {
 113 public:
 114   size_t GetIndexOfChildWithName(ConstString name) override {
 115     return ExtractIndexFromString(name.GetCString());
 116   }
 117   bool MightHaveChildren() override { return true; }
 118   bool Update() override;
 119
 120 protected:
 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
 141 class ForwardListFrontEnd : public AbstractListFrontEnd {
 142 public:
 143   ForwardListFrontEnd(ValueObject &valobj);
 144
 145   size_t CalculateNumChildren() override;
 146   ValueObjectSP GetChildAtIndex(size_t idx) override;
 147   bool Update() override;
 148 };
 149
 150 class ListFrontEnd : public AbstractListFrontEnd {
 151 public:
 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
 162 private:
 163   lldb::addr_t m_node_address;
 164   ValueObject *m_tail;
 165 };
 166
 167 } // end anonymous namespace
 168
 169 bool 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
 195 bool 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
 229 ValueObjectSP 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
 244 ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj)
 245     : AbstractListFrontEnd(valobj) {
 246   Update();
 247 }
 248
 249 size_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
 262 ValueObjectSP 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
 293 static 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
 302 bool 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
 321 ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp)
 322     : AbstractListFrontEnd(*valobj_sp), m_node_address(), m_tail(nullptr) {
 323   if (valobj_sp)
 324     Update();
 325 }
 326
 327 size_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
 363 lldb::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
 414 bool 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
 435 SyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator(
 436     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
 437   return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr);
 438 }
 439
 440 SyntheticChildrenFrontEnd *
 441 formatters::LibcxxStdForwardListSyntheticFrontEndCreator(
 442     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
 443   return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr;
 444 }