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