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