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