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