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