LibCxxList.cpp revision 296417 
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
26using namespace lldb;
27using namespace lldb_private;
28using namespace lldb_private::formatters;
29
30namespace {
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
163namespace 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
209lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) :
210SyntheticChildrenFrontEnd(*valobj_sp.get()),
211m_list_capping_size(0),
212m_loop_detected(0),
213m_node_address(),
214m_head(NULL),
215m_tail(NULL),
216m_element_type(),
217m_count(UINT32_MAX),
218m_children(),
219m_iterators()
220{
221    if (valobj_sp)
222        Update();
223}
224
225bool
226lldb_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
263size_t
264lldb_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
306lldb::ValueObjectSP
307lldb_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
356bool
357lldb_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
396bool
397lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::MightHaveChildren ()
398{
399    return true;
400}
401
402size_t
403lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name)
404{
405    return ExtractIndexFromString(name.GetCString());
406}
407
408SyntheticChildrenFrontEnd*
409lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp)
410{
411    if (!valobj_sp)
412        return NULL;
413    return (new LibcxxStdListSyntheticFrontEnd(valobj_sp));
414}
415