LibCxxMap.cpp revision 52f792329be5db8e38961350589e97e8f2823acd 
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 MapEntry
29{
30public:
31    MapEntry () {}
32    MapEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
33    MapEntry (const MapEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {}
34    MapEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
35
36    ValueObjectSP
37    left ()
38    {
39        if (!m_entry_sp)
40            return m_entry_sp;
41        return m_entry_sp->GetChildMemberWithName(ConstString("__left_"), true);
42    }
43
44    ValueObjectSP
45    right ()
46    {
47        if (!m_entry_sp)
48            return m_entry_sp;
49        return m_entry_sp->GetChildMemberWithName(ConstString("__right_"), true);
50    }
51
52    ValueObjectSP
53    parent ()
54    {
55        if (!m_entry_sp)
56            return m_entry_sp;
57        return m_entry_sp->GetChildMemberWithName(ConstString("__parent_"), true);
58    }
59
60    uint64_t
61    value ()
62    {
63        if (!m_entry_sp)
64            return 0;
65        return m_entry_sp->GetValueAsUnsigned(0);
66    }
67
68    bool
69    error ()
70    {
71        if (!m_entry_sp)
72            return true;
73        return m_entry_sp->GetError().Fail();
74    }
75
76    bool
77    null()
78    {
79        return (value() == 0);
80    }
81
82    ValueObjectSP
83    GetEntry ()
84    {
85        return m_entry_sp;
86    }
87
88    void
89    SetEntry (ValueObjectSP entry)
90    {
91        m_entry_sp = entry;
92    }
93
94    bool
95    operator == (const MapEntry& rhs) const
96    {
97        return (rhs.m_entry_sp.get() == m_entry_sp.get());
98    }
99
100private:
101    ValueObjectSP m_entry_sp;
102};
103
104class MapIterator
105{
106public:
107    MapIterator () {}
108    MapIterator (MapEntry entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {}
109    MapIterator (ValueObjectSP entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {}
110    MapIterator (const MapIterator& rhs) : m_entry(rhs.m_entry),m_max_depth(rhs.m_max_depth), m_error(false) {}
111    MapIterator (ValueObject* entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {}
112
113    ValueObjectSP
114    value ()
115    {
116        return m_entry.GetEntry();
117    }
118
119    ValueObjectSP
120    advance (size_t count)
121    {
122        if (m_error)
123            return lldb::ValueObjectSP();
124        if (count == 0)
125            return m_entry.GetEntry();
126        if (count == 1)
127        {
128            next ();
129            return m_entry.GetEntry();
130        }
131        size_t steps = 0;
132        while (count > 0)
133        {
134            if (m_error)
135                return lldb::ValueObjectSP();
136            next ();
137            count--;
138            if (m_entry.null())
139                return lldb::ValueObjectSP();
140            steps++;
141            if (steps > m_max_depth)
142                return lldb::ValueObjectSP();
143        }
144        return m_entry.GetEntry();
145    }
146protected:
147    void
148    next ()
149    {
150        m_entry.SetEntry(increment(m_entry.GetEntry()));
151    }
152
153private:
154    ValueObjectSP
155    tree_min (ValueObjectSP x_sp)
156    {
157        MapEntry x(x_sp);
158        if (x.null())
159            return ValueObjectSP();
160        MapEntry left(x.left());
161        size_t steps = 0;
162        while (left.null() == false)
163        {
164            if (left.error())
165            {
166                m_error = true;
167                return lldb::ValueObjectSP();
168            }
169            x.SetEntry(left.GetEntry());
170            left.SetEntry(x.left());
171            steps++;
172            if (steps > m_max_depth)
173                return lldb::ValueObjectSP();
174        }
175        return x.GetEntry();
176    }
177
178    ValueObjectSP
179    tree_max (ValueObjectSP x_sp)
180    {
181        MapEntry x(x_sp);
182        if (x.null())
183            return ValueObjectSP();
184        MapEntry right(x.right());
185        size_t steps = 0;
186        while (right.null() == false)
187        {
188            if (right.error())
189                return lldb::ValueObjectSP();
190            x.SetEntry(right.GetEntry());
191            right.SetEntry(x.right());
192            steps++;
193            if (steps > m_max_depth)
194                return lldb::ValueObjectSP();
195        }
196        return x.GetEntry();
197    }
198
199    bool
200    is_left_child (ValueObjectSP x_sp)
201    {
202        MapEntry x(x_sp);
203        if (x.null())
204            return false;
205        MapEntry rhs(x.parent());
206        rhs.SetEntry(rhs.left());
207        return x.value() == rhs.value();
208    }
209
210    ValueObjectSP
211    increment (ValueObjectSP x_sp)
212    {
213        MapEntry node(x_sp);
214        if (node.null())
215            return ValueObjectSP();
216        MapEntry right(node.right());
217        if (right.null() == false)
218            return tree_min(right.GetEntry());
219        size_t steps = 0;
220        while (!is_left_child(node.GetEntry()))
221        {
222            if (node.error())
223            {
224                m_error = true;
225                return lldb::ValueObjectSP();
226            }
227            node.SetEntry(node.parent());
228            steps++;
229            if (steps > m_max_depth)
230                return lldb::ValueObjectSP();
231        }
232        return node.parent();
233    }
234
235    MapEntry m_entry;
236    size_t m_max_depth;
237    bool m_error;
238};
239
240lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::LibcxxStdMapSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) :
241SyntheticChildrenFrontEnd(*valobj_sp.get()),
242m_tree(NULL),
243m_root_node(NULL),
244m_element_type(),
245m_skip_size(UINT32_MAX),
246m_count(UINT32_MAX),
247m_children()
248{
249    if (valobj_sp)
250        Update();
251}
252
253size_t
254lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren ()
255{
256    if (m_count != UINT32_MAX)
257        return m_count;
258    if (m_tree == NULL)
259        return 0;
260    ValueObjectSP m_item(m_tree->GetChildMemberWithName(ConstString("__pair3_"), true));
261    if (!m_item)
262        return 0;
263    m_item = m_item->GetChildMemberWithName(ConstString("__first_"), true);
264    if (!m_item)
265        return 0;
266    m_count = m_item->GetValueAsUnsigned(0);
267    return m_count;
268}
269
270bool
271lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType()
272{
273    if (m_element_type.GetOpaqueQualType() && m_element_type.GetASTContext())
274        return true;
275    m_element_type.Clear();
276    ValueObjectSP deref;
277    Error error;
278    deref = m_root_node->Dereference(error);
279    if (!deref || error.Fail())
280        return false;
281    deref = deref->GetChildMemberWithName(ConstString("__value_"), true);
282    if (!deref)
283        return false;
284    m_element_type = deref->GetClangType();
285    return true;
286}
287
288void
289lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset (const lldb::ValueObjectSP& node)
290{
291    if (m_skip_size != UINT32_MAX)
292        return;
293    if (!node)
294        return;
295    ClangASTType node_type(node->GetClangType());
296    uint64_t bit_offset;
297    if (node_type.GetIndexOfFieldWithName("__value_", NULL, &bit_offset) == UINT32_MAX)
298        return;
299    m_skip_size = bit_offset / 8u;
300}
301
302lldb::ValueObjectSP
303lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex (size_t idx)
304{
305    if (idx >= CalculateNumChildren())
306        return lldb::ValueObjectSP();
307    if (m_tree == NULL || m_root_node == NULL)
308        return lldb::ValueObjectSP();
309
310    auto cached = m_children.find(idx);
311    if (cached != m_children.end())
312        return cached->second;
313
314    bool need_to_skip = (idx > 0);
315    MapIterator iterator(m_root_node, CalculateNumChildren());
316    ValueObjectSP iterated_sp(iterator.advance(idx));
317    if (iterated_sp.get() == NULL)
318    {
319        // this tree is garbage - stop
320        m_tree = NULL; // this will stop all future searches until an Update() happens
321        return iterated_sp;
322    }
323    if (GetDataType())
324    {
325        if (!need_to_skip)
326        {
327            Error error;
328            iterated_sp = iterated_sp->Dereference(error);
329            if (!iterated_sp || error.Fail())
330            {
331                m_tree = NULL;
332                return lldb::ValueObjectSP();
333            }
334            GetValueOffset(iterated_sp);
335            iterated_sp = iterated_sp->GetChildMemberWithName(ConstString("__value_"), true);
336            if (!iterated_sp)
337            {
338                m_tree = NULL;
339                return lldb::ValueObjectSP();
340            }
341        }
342        else
343        {
344            // because of the way our debug info is made, we need to read item 0 first
345            // so that we can cache information used to generate other elements
346            if (m_skip_size == UINT32_MAX)
347                GetChildAtIndex(0);
348            if (m_skip_size == UINT32_MAX)
349            {
350                m_tree = NULL;
351                return lldb::ValueObjectSP();
352            }
353            iterated_sp = iterated_sp->GetSyntheticChildAtOffset(m_skip_size, m_element_type, true);
354            if (!iterated_sp)
355            {
356                m_tree = NULL;
357                return lldb::ValueObjectSP();
358            }
359        }
360    }
361    else
362    {
363        m_tree = NULL;
364        return lldb::ValueObjectSP();
365    }
366    // at this point we have a valid
367    // we need to copy current_sp into a new object otherwise we will end up with all items named __value_
368    DataExtractor data;
369    iterated_sp->GetData(data);
370    StreamString name;
371    name.Printf("[%zu]",idx);
372    return (m_children[idx] = ValueObject::CreateValueObjectFromData(name.GetData(), data, m_backend.GetExecutionContextRef(), m_element_type));
373}
374
375bool
376lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update()
377{
378    m_count = UINT32_MAX;
379    m_tree = m_root_node = NULL;
380    m_children.clear();
381    m_tree = m_backend.GetChildMemberWithName(ConstString("__tree_"), true).get();
382    if (!m_tree)
383        return false;
384    m_root_node = m_tree->GetChildMemberWithName(ConstString("__begin_node_"), true).get();
385    return false;
386}
387
388bool
389lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::MightHaveChildren ()
390{
391    return true;
392}
393
394size_t
395lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name)
396{
397    return ExtractIndexFromString(name.GetCString());
398}
399
400lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::~LibcxxStdMapSyntheticFrontEnd ()
401{}
402
403SyntheticChildrenFrontEnd*
404lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp)
405{
406    if (!valobj_sp)
407        return NULL;
408    return (new LibcxxStdMapSyntheticFrontEnd(valobj_sp));
409}
410