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