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/DataBufferHeap.h"
  17 #include "lldb/Core/Error.h"
  18 #include "lldb/Core/Stream.h"
  19 #include "lldb/Core/ValueObject.h"
  20 #include "lldb/Core/ValueObjectConstResult.h"
  21 #include "lldb/DataFormatters/FormattersHelpers.h"
  22 #include "lldb/Host/Endian.h"
  23 #include "lldb/Symbol/ClangASTContext.h"
  24 #include "lldb/Target/Target.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 } // end anonymous namespace
 118
 119 namespace lldb_private {
 120 namespace formatters {
 121 class LibcxxStdListSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
 122 public:
 123   LibcxxStdListSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
 124
 125   ~LibcxxStdListSyntheticFrontEnd() override = default;
 126
 127   size_t CalculateNumChildren() override;
 128
 129   lldb::ValueObjectSP GetChildAtIndex(size_t idx) override;
 130
 131   bool Update() override;
 132
 133   bool MightHaveChildren() override;
 134
 135   size_t GetIndexOfChildWithName(const ConstString &name) override;
 136
 137 private:
 138   bool HasLoop(size_t count);
 139
 140   size_t m_list_capping_size;
 141   static const bool g_use_loop_detect = true;
 142
 143   size_t m_loop_detected; // The number of elements that have had loop detection
 144                           // run over them.
 145   ListEntry m_slow_runner; // Used for loop detection
 146   ListEntry m_fast_runner; // Used for loop detection
 147
 148   lldb::addr_t m_node_address;
 149   ValueObject *m_head;
 150   ValueObject *m_tail;
 151   CompilerType m_element_type;
 152   size_t m_count;
 153   std::map<size_t, ListIterator> m_iterators;
 154 };
 155 } // namespace formatters
 156 } // namespace lldb_private
 157
 158 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
 159     LibcxxStdListSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
 160     : SyntheticChildrenFrontEnd(*valobj_sp), m_list_capping_size(0),
 161       m_loop_detected(0), m_node_address(), m_head(nullptr), m_tail(nullptr),
 162       m_element_type(), m_count(UINT32_MAX), m_iterators() {
 163   if (valobj_sp)
 164     Update();
 165 }
 166
 167 bool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::HasLoop(
 168     size_t count) {
 169   if (!g_use_loop_detect)
 170     return false;
 171   // don't bother checking for a loop if we won't actually need to jump nodes
 172   if (m_count < 2)
 173     return false;
 174
 175   if (m_loop_detected == 0) {
 176     // This is the first time we are being run (after the last update). Set up
 177     // the loop
 178     // invariant for the first element.
 179     m_slow_runner = ListEntry(m_head).next();
 180     m_fast_runner = m_slow_runner.next();
 181     m_loop_detected = 1;
 182   }
 183
 184   // Loop invariant:
 185   // Loop detection has been run over the first m_loop_detected elements. If
 186   // m_slow_runner ==
 187   // m_fast_runner then the loop has been detected after m_loop_detected
 188   // elements.
 189   const size_t steps_to_run = std::min(count, m_count);
 190   while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner &&
 191          m_slow_runner != m_fast_runner) {
 192
 193     m_slow_runner = m_slow_runner.next();
 194     m_fast_runner = m_fast_runner.next().next();
 195     m_loop_detected++;
 196   }
 197   if (count <= m_loop_detected)
 198     return false; // No loop in the first m_loop_detected elements.
 199   if (!m_slow_runner || !m_fast_runner)
 200     return false; // Reached the end of the list. Definitely no loops.
 201   return m_slow_runner == m_fast_runner;
 202 }
 203
 204 size_t lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
 205     CalculateNumChildren() {
 206   if (m_count != UINT32_MAX)
 207     return m_count;
 208   if (!m_head || !m_tail || m_node_address == 0)
 209     return 0;
 210   ValueObjectSP size_alloc(
 211       m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
 212   if (size_alloc) {
 213     ValueObjectSP first(
 214         size_alloc->GetChildMemberWithName(ConstString("__first_"), true));
 215     if (first) {
 216       m_count = first->GetValueAsUnsigned(UINT32_MAX);
 217     }
 218   }
 219   if (m_count != UINT32_MAX) {
 220     return m_count;
 221   } else {
 222     uint64_t next_val = m_head->GetValueAsUnsigned(0);
 223     uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
 224     if (next_val == 0 || prev_val == 0)
 225       return 0;
 226     if (next_val == m_node_address)
 227       return 0;
 228     if (next_val == prev_val)
 229       return 1;
 230     uint64_t size = 2;
 231     ListEntry current(m_head);
 232     while (current.next() && current.next().value() != m_node_address) {
 233       size++;
 234       current = current.next();
 235       if (size > m_list_capping_size)
 236         break;
 237     }
 238     return m_count = (size - 1);
 239   }
 240 }
 241
 242 lldb::ValueObjectSP
 243 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetChildAtIndex(
 244     size_t idx) {
 245   static ConstString g_value("__value_");
 246   static ConstString g_next("__next_");
 247
 248   if (idx >= CalculateNumChildren())
 249     return lldb::ValueObjectSP();
 250
 251   if (!m_head || !m_tail || m_node_address == 0)
 252     return lldb::ValueObjectSP();
 253
 254   if (HasLoop(idx + 1))
 255     return lldb::ValueObjectSP();
 256
 257   size_t actual_advance = idx;
 258
 259   ListIterator current(m_head);
 260   if (idx > 0) {
 261     auto cached_iterator = m_iterators.find(idx - 1);
 262     if (cached_iterator != m_iterators.end()) {
 263       current = cached_iterator->second;
 264       actual_advance = 1;
 265     }
 266   }
 267
 268   ValueObjectSP current_sp(current.advance(actual_advance));
 269   if (!current_sp)
 270     return lldb::ValueObjectSP();
 271
 272   m_iterators[idx] = current;
 273
 274   current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
 275   if (!current_sp)
 276     return lldb::ValueObjectSP();
 277
 278   if (current_sp->GetName() == g_next) {
 279     ProcessSP process_sp(current_sp->GetProcessSP());
 280     if (!process_sp)
 281       return nullptr;
 282
 283     // if we grabbed the __next_ pointer, then the child is one pointer deep-er
 284     lldb::addr_t addr = current_sp->GetParent()->GetPointerValue();
 285     addr = addr + 2 * process_sp->GetAddressByteSize();
 286     ExecutionContext exe_ctx(process_sp);
 287     current_sp =
 288         CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type);
 289   }
 290
 291   // we need to copy current_sp into a new object otherwise we will end up with
 292   // all items named __value_
 293   DataExtractor data;
 294   Error error;
 295   current_sp->GetData(data, error);
 296   if (error.Fail())
 297     return lldb::ValueObjectSP();
 298
 299   StreamString name;
 300   name.Printf("[%" PRIu64 "]", (uint64_t)idx);
 301   return CreateValueObjectFromData(name.GetString(), data,
 302                                    m_backend.GetExecutionContextRef(),
 303                                    m_element_type);
 304 }
 305
 306 bool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::Update() {
 307   m_iterators.clear();
 308   m_head = m_tail = nullptr;
 309   m_node_address = 0;
 310   m_count = UINT32_MAX;
 311   m_loop_detected = 0;
 312   m_slow_runner.SetEntry(nullptr);
 313   m_fast_runner.SetEntry(nullptr);
 314
 315   Error err;
 316   ValueObjectSP backend_addr(m_backend.AddressOf(err));
 317   m_list_capping_size = 0;
 318   if (m_backend.GetTargetSP())
 319     m_list_capping_size =
 320         m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
 321   if (m_list_capping_size == 0)
 322     m_list_capping_size = 255;
 323   if (err.Fail() || !backend_addr)
 324     return false;
 325   m_node_address = backend_addr->GetValueAsUnsigned(0);
 326   if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
 327     return false;
 328   ValueObjectSP impl_sp(
 329       m_backend.GetChildMemberWithName(ConstString("__end_"), true));
 330   if (!impl_sp)
 331     return false;
 332   CompilerType list_type = m_backend.GetCompilerType();
 333   if (list_type.IsReferenceType())
 334     list_type = list_type.GetNonReferenceType();
 335
 336   if (list_type.GetNumTemplateArguments() == 0)
 337     return false;
 338   lldb::TemplateArgumentKind kind;
 339   m_element_type = list_type.GetTemplateArgument(0, kind);
 340   m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
 341   m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
 342   return false;
 343 }
 344
 345 bool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
 346     MightHaveChildren() {
 347   return true;
 348 }
 349
 350 size_t lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
 351     GetIndexOfChildWithName(const ConstString &name) {
 352   return ExtractIndexFromString(name.GetCString());
 353 }
 354
 355 SyntheticChildrenFrontEnd *
 356 lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator(
 357     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
 358   return (valobj_sp ? new LibcxxStdListSyntheticFrontEnd(valobj_sp) : nullptr);
 359 }