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