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
24using namespace lldb;
25using namespace lldb_private;
26using namespace lldb_private::formatters;
27
28class ListEntry
29{
30public:
31    ListEntry () {}
32    ListEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
33    ListEntry (const ListEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {}
34    ListEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
35
36    ValueObjectSP
37    next ()
38    {
39        if (!m_entry_sp)
40            return m_entry_sp;
41        return m_entry_sp->GetChildMemberWithName(ConstString("__next_"), true);
42    }
43
44    ValueObjectSP
45    prev ()
46    {
47        if (!m_entry_sp)
48            return m_entry_sp;
49        return m_entry_sp->GetChildMemberWithName(ConstString("__prev_"), true);
50    }
51
52    uint64_t
53    value ()
54    {
55        if (!m_entry_sp)
56            return 0;
57        return m_entry_sp->GetValueAsUnsigned(0);
58    }
59
60    bool
61    null()
62    {
63        return (value() == 0);
64    }
65
66    ValueObjectSP
67    GetEntry ()
68    {
69        return m_entry_sp;
70    }
71
72    void
73    SetEntry (ValueObjectSP entry)
74    {
75        m_entry_sp = entry;
76    }
77
78    bool
79    operator == (const ListEntry& rhs) const
80    {
81        return (rhs.m_entry_sp.get() == m_entry_sp.get());
82    }
83
84private:
85    ValueObjectSP m_entry_sp;
86};
87
88class ListIterator
89{
90public:
91    ListIterator () {}
92    ListIterator (ListEntry entry) : m_entry(entry) {}
93    ListIterator (ValueObjectSP entry) : m_entry(entry) {}
94    ListIterator (const ListIterator& rhs) : m_entry(rhs.m_entry) {}
95    ListIterator (ValueObject* entry) : m_entry(entry) {}
96
97    ValueObjectSP
98    value ()
99    {
100        return m_entry.GetEntry();
101    }
102
103    ValueObjectSP
104    advance (size_t count)
105    {
106        if (count == 0)
107            return m_entry.GetEntry();
108        if (count == 1)
109        {
110            next ();
111            return m_entry.GetEntry();
112        }
113        while (count > 0)
114        {
115            next ();
116            count--;
117            if (m_entry.null())
118                return lldb::ValueObjectSP();
119        }
120        return m_entry.GetEntry();
121    }
122
123    bool
124    operator == (const ListIterator& rhs) const
125    {
126        return (rhs.m_entry == m_entry);
127    }
128
129protected:
130    void
131    next ()
132    {
133        m_entry.SetEntry(m_entry.next());
134    }
135
136    void
137    prev ()
138    {
139        m_entry.SetEntry(m_entry.prev());
140    }
141private:
142    ListEntry m_entry;
143};
144
145lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) :
146SyntheticChildrenFrontEnd(*valobj_sp.get()),
147m_list_capping_size(0),
148m_node_address(),
149m_head(NULL),
150m_tail(NULL),
151m_element_type(),
152m_count(UINT32_MAX),
153m_children()
154{
155    if (valobj_sp)
156        Update();
157}
158
159bool
160lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::HasLoop()
161{
162    if (g_use_loop_detect == false)
163        return false;
164    ListEntry slow(m_head);
165    ListEntry fast1(m_head);
166    ListEntry fast2(m_head);
167    while (slow.next() && slow.next()->GetValueAsUnsigned(0) != m_node_address)
168    {
169        auto slow_value = slow.value();
170        fast1.SetEntry(fast2.next());
171        fast2.SetEntry(fast1.next());
172        if (fast1.value() == slow_value || fast2.value() == slow_value)
173            return true;
174        slow.SetEntry(slow.next());
175    }
176    return false;
177}
178
179size_t
180lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::CalculateNumChildren ()
181{
182    if (m_count != UINT32_MAX)
183        return m_count;
184    if (!m_head || !m_tail || m_node_address == 0)
185        return 0;
186    ValueObjectSP size_alloc(m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
187    if (size_alloc)
188    {
189        ValueObjectSP first(size_alloc->GetChildMemberWithName(ConstString("__first_"), true));
190        if (first)
191        {
192            m_count = first->GetValueAsUnsigned(UINT32_MAX);
193        }
194    }
195    if (m_count != UINT32_MAX)
196    {
197        if (!HasLoop())
198            return m_count;
199        return m_count = 0;
200    }
201    else
202    {
203        uint64_t next_val = m_head->GetValueAsUnsigned(0);
204        uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
205        if (next_val == 0 || prev_val == 0)
206            return 0;
207        if (next_val == m_node_address)
208            return 0;
209        if (next_val == prev_val)
210            return 1;
211        if (HasLoop())
212            return 0;
213        uint64_t size = 2;
214        ListEntry current(m_head);
215        while (current.next() && current.next()->GetValueAsUnsigned(0) != m_node_address)
216        {
217            size++;
218            current.SetEntry(current.next());
219            if (size > m_list_capping_size)
220                break;
221        }
222        return m_count = (size-1);
223    }
224}
225
226lldb::ValueObjectSP
227lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetChildAtIndex (size_t idx)
228{
229    if (idx >= CalculateNumChildren())
230        return lldb::ValueObjectSP();
231
232    if (!m_head || !m_tail || m_node_address == 0)
233        return lldb::ValueObjectSP();
234
235    auto cached = m_children.find(idx);
236    if (cached != m_children.end())
237        return cached->second;
238
239    ListIterator current(m_head);
240    ValueObjectSP current_sp(current.advance(idx));
241    if (!current_sp)
242        return lldb::ValueObjectSP();
243    current_sp = current_sp->GetChildMemberWithName(ConstString("__value_"), true);
244    if (!current_sp)
245        return lldb::ValueObjectSP();
246    // we need to copy current_sp into a new object otherwise we will end up with all items named __value_
247    DataExtractor data;
248    current_sp->GetData(data);
249    StreamString name;
250    name.Printf("[%zu]",idx);
251    return (m_children[idx] = ValueObject::CreateValueObjectFromData(name.GetData(), data, m_backend.GetExecutionContextRef(), m_element_type));
252}
253
254bool
255lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::Update()
256{
257    m_head = m_tail = NULL;
258    m_node_address = 0;
259    m_count = UINT32_MAX;
260    Error err;
261    ValueObjectSP backend_addr(m_backend.AddressOf(err));
262    m_list_capping_size = 0;
263    if (m_backend.GetTargetSP())
264        m_list_capping_size = m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
265    if (m_list_capping_size == 0)
266        m_list_capping_size = 255;
267    if (err.Fail() || backend_addr.get() == NULL)
268        return false;
269    m_node_address = backend_addr->GetValueAsUnsigned(0);
270    if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
271        return false;
272    ValueObjectSP impl_sp(m_backend.GetChildMemberWithName(ConstString("__end_"),true));
273    if (!impl_sp)
274        return false;
275    ClangASTType list_type = m_backend.GetClangType();
276    if (list_type.IsReferenceType())
277        list_type = list_type.GetNonReferenceType();
278
279    if (list_type.GetNumTemplateArguments() == 0)
280        return false;
281    lldb::TemplateArgumentKind kind;
282    m_element_type = list_type.GetTemplateArgument(0, kind);
283    m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
284    m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
285    return false;
286}
287
288bool
289lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::MightHaveChildren ()
290{
291    return true;
292}
293
294size_t
295lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name)
296{
297    return ExtractIndexFromString(name.GetCString());
298}
299
300lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::~LibcxxStdListSyntheticFrontEnd ()
301{}
302
303SyntheticChildrenFrontEnd*
304lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp)
305{
306    if (!valobj_sp)
307        return NULL;
308    return (new LibcxxStdListSyntheticFrontEnd(valobj_sp));
309}
310
311