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