contrib/llvm/tools/lldb/source/Plugins/Language/CPlusPlus/LibCxxList.cpp

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