contrib/llvm/tools/lldb/source/DataFormatters/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 #include "lldb/lldb-python.h"
  11
  12 #include "lldb/DataFormatters/CXXFormatterFunctions.h"
  13
  14 #include "lldb/Core/DataBufferHeap.h"
  15 #include "lldb/Core/Error.h"
  16 #include "lldb/Core/Stream.h"
  17 #include "lldb/Core/ValueObject.h"
  18 #include "lldb/Core/ValueObjectConstResult.h"
  19 #include "lldb/Host/Endian.h"
  20 #include "lldb/Symbol/ClangASTContext.h"
  21 #include "lldb/Target/ObjCLanguageRuntime.h"
  22 #include "lldb/Target/Target.h"
  23
  24 using namespace lldb;
  25 using namespace lldb_private;
  26 using namespace lldb_private::formatters;
  27
  28 namespace lldb_private {
  29     namespace formatters {
  30         class LibcxxStdListSyntheticFrontEnd : public SyntheticChildrenFrontEnd
  31         {
  32         public:
  33             LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp);
  34
  35             virtual size_t
  36             CalculateNumChildren ();
  37
  38             virtual lldb::ValueObjectSP
  39             GetChildAtIndex (size_t idx);
  40
  41             virtual bool
  42             Update();
  43
  44             virtual bool
  45             MightHaveChildren ();
  46
  47             virtual size_t
  48             GetIndexOfChildWithName (const ConstString &name);
  49
  50             virtual
  51             ~LibcxxStdListSyntheticFrontEnd ();
  52         private:
  53             bool
  54             HasLoop(size_t);
  55
  56             size_t m_list_capping_size;
  57             static const bool g_use_loop_detect = true;
  58             size_t m_loop_detected;
  59             lldb::addr_t m_node_address;
  60             ValueObject* m_head;
  61             ValueObject* m_tail;
  62             ClangASTType m_element_type;
  63             size_t m_count;
  64             std::map<size_t,lldb::ValueObjectSP> m_children;
  65         };
  66     }
  67 }
  68
  69 class ListEntry
  70 {
  71 public:
  72     ListEntry () {}
  73     ListEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
  74     ListEntry (const ListEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {}
  75     ListEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
  76
  77     ListEntry
  78     next ()
  79     {
  80         if (!m_entry_sp)
  81             return ListEntry();
  82         return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__next_"), true));
  83     }
  84
  85     ListEntry
  86     prev ()
  87     {
  88         if (!m_entry_sp)
  89             return ListEntry();
  90         return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__prev_"), true));
  91     }
  92
  93     uint64_t
  94     value ()
  95     {
  96         if (!m_entry_sp)
  97             return 0;
  98         return m_entry_sp->GetValueAsUnsigned(0);
  99     }
 100
 101     bool
 102     null()
 103     {
 104         return (value() == 0);
 105     }
 106
 107     explicit operator bool ()
 108     {
 109         return GetEntry().get() != nullptr && null() == false;
 110     }
 111
 112     ValueObjectSP
 113     GetEntry ()
 114     {
 115         return m_entry_sp;
 116     }
 117
 118     void
 119     SetEntry (ValueObjectSP entry)
 120     {
 121         m_entry_sp = entry;
 122     }
 123
 124     bool
 125     operator == (const ListEntry& rhs) const
 126     {
 127         return (rhs.m_entry_sp.get() == m_entry_sp.get());
 128     }
 129
 130 private:
 131     ValueObjectSP m_entry_sp;
 132 };
 133
 134 class ListIterator
 135 {
 136 public:
 137     ListIterator () {}
 138     ListIterator (ListEntry entry) : m_entry(entry) {}
 139     ListIterator (ValueObjectSP entry) : m_entry(entry) {}
 140     ListIterator (const ListIterator& rhs) : m_entry(rhs.m_entry) {}
 141     ListIterator (ValueObject* entry) : m_entry(entry) {}
 142
 143     ValueObjectSP
 144     value ()
 145     {
 146         return m_entry.GetEntry();
 147     }
 148
 149     ValueObjectSP
 150     advance (size_t count)
 151     {
 152         if (count == 0)
 153             return m_entry.GetEntry();
 154         if (count == 1)
 155         {
 156             next ();
 157             return m_entry.GetEntry();
 158         }
 159         while (count > 0)
 160         {
 161             next ();
 162             count--;
 163             if (m_entry.null())
 164                 return lldb::ValueObjectSP();
 165         }
 166         return m_entry.GetEntry();
 167     }
 168
 169     bool
 170     operator == (const ListIterator& rhs) const
 171     {
 172         return (rhs.m_entry == m_entry);
 173     }
 174
 175 protected:
 176     void
 177     next ()
 178     {
 179         m_entry = m_entry.next();
 180     }
 181
 182     void
 183     prev ()
 184     {
 185         m_entry = m_entry.prev();
 186     }
 187 private:
 188     ListEntry m_entry;
 189 };
 190
 191 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) :
 192 SyntheticChildrenFrontEnd(*valobj_sp.get()),
 193 m_list_capping_size(0),
 194 m_loop_detected(0),
 195 m_node_address(),
 196 m_head(NULL),
 197 m_tail(NULL),
 198 m_element_type(),
 199 m_count(UINT32_MAX),
 200 m_children()
 201 {
 202     if (valobj_sp)
 203         Update();
 204 }
 205
 206 bool
 207 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::HasLoop(size_t count)
 208 {
 209     if (g_use_loop_detect == false)
 210         return false;
 211     // don't bother checking for a loop if we won't actually need to jump nodes
 212     if (m_count < 2)
 213         return false;
 214     auto steps_left = std::min(count,m_count);
 215     auto steps_left_save = steps_left;
 216     ListEntry slow(m_head);
 217     ListEntry fast(m_head);
 218     while (steps_left-- > 0)
 219     {
 220         slow = slow.next();
 221         fast = fast.next();
 222         if (fast.next())
 223             fast = fast.next().next();
 224         else
 225             fast = nullptr;
 226         if (!slow || !fast)
 227             return false;
 228         if (slow == fast)
 229             return true;
 230     }
 231     m_loop_detected = steps_left_save;
 232     return false;
 233 }
 234
 235 size_t
 236 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::CalculateNumChildren ()
 237 {
 238     if (m_count != UINT32_MAX)
 239         return m_count;
 240     if (!m_head || !m_tail || m_node_address == 0)
 241         return 0;
 242     ValueObjectSP size_alloc(m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
 243     if (size_alloc)
 244     {
 245         ValueObjectSP first(size_alloc->GetChildMemberWithName(ConstString("__first_"), true));
 246         if (first)
 247         {
 248             m_count = first->GetValueAsUnsigned(UINT32_MAX);
 249         }
 250     }
 251     if (m_count != UINT32_MAX)
 252     {
 253         return m_count;
 254     }
 255     else
 256     {
 257         uint64_t next_val = m_head->GetValueAsUnsigned(0);
 258         uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
 259         if (next_val == 0 || prev_val == 0)
 260             return 0;
 261         if (next_val == m_node_address)
 262             return 0;
 263         if (next_val == prev_val)
 264             return 1;
 265         uint64_t size = 2;
 266         ListEntry current(m_head);
 267         while (current.next() && current.next().value() != m_node_address)
 268         {
 269             size++;
 270             current = current.next();
 271             if (size > m_list_capping_size)
 272                 break;
 273         }
 274         return m_count = (size-1);
 275     }
 276 }
 277
 278 lldb::ValueObjectSP
 279 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetChildAtIndex (size_t idx)
 280 {
 281     if (idx >= CalculateNumChildren())
 282         return lldb::ValueObjectSP();
 283
 284     if (!m_head || !m_tail || m_node_address == 0)
 285         return lldb::ValueObjectSP();
 286
 287     auto cached = m_children.find(idx);
 288     if (cached != m_children.end())
 289         return cached->second;
 290
 291     if (m_loop_detected <= idx)
 292         if (HasLoop(idx))
 293             return lldb::ValueObjectSP();
 294
 295     ListIterator current(m_head);
 296     ValueObjectSP current_sp(current.advance(idx));
 297     if (!current_sp)
 298         return lldb::ValueObjectSP();
 299     current_sp = current_sp->GetChildMemberWithName(ConstString("__value_"), true);
 300     if (!current_sp)
 301         return lldb::ValueObjectSP();
 302     // we need to copy current_sp into a new object otherwise we will end up with all items named __value_
 303     DataExtractor data;
 304     Error error;
 305     current_sp->GetData(data, error);
 306     if (error.Fail())
 307         return lldb::ValueObjectSP();
 308
 309     StreamString name;
 310     name.Printf("[%" PRIu64 "]", (uint64_t)idx);
 311     return (m_children[idx] = CreateValueObjectFromData(name.GetData(), data, m_backend.GetExecutionContextRef(), m_element_type));
 312 }
 313
 314 bool
 315 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::Update()
 316 {
 317     m_head = m_tail = NULL;
 318     m_node_address = 0;
 319     m_count = UINT32_MAX;
 320     m_loop_detected = false;
 321     Error err;
 322     ValueObjectSP backend_addr(m_backend.AddressOf(err));
 323     m_list_capping_size = 0;
 324     if (m_backend.GetTargetSP())
 325         m_list_capping_size = m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
 326     if (m_list_capping_size == 0)
 327         m_list_capping_size = 255;
 328     if (err.Fail() || backend_addr.get() == NULL)
 329         return false;
 330     m_node_address = backend_addr->GetValueAsUnsigned(0);
 331     if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
 332         return false;
 333     ValueObjectSP impl_sp(m_backend.GetChildMemberWithName(ConstString("__end_"),true));
 334     if (!impl_sp)
 335         return false;
 336     ClangASTType list_type = m_backend.GetClangType();
 337     if (list_type.IsReferenceType())
 338         list_type = list_type.GetNonReferenceType();
 339
 340     if (list_type.GetNumTemplateArguments() == 0)
 341         return false;
 342     lldb::TemplateArgumentKind kind;
 343     m_element_type = list_type.GetTemplateArgument(0, kind);
 344     m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
 345     m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
 346     return false;
 347 }
 348
 349 bool
 350 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::MightHaveChildren ()
 351 {
 352     return true;
 353 }
 354
 355 size_t
 356 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name)
 357 {
 358     return ExtractIndexFromString(name.GetCString());
 359 }
 360
 361 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::~LibcxxStdListSyntheticFrontEnd ()
 362 {}
 363
 364 SyntheticChildrenFrontEnd*
 365 lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp)
 366 {
 367     if (!valobj_sp)
 368         return NULL;
 369     return (new LibcxxStdListSyntheticFrontEnd(valobj_sp));
 370 }
 371