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