LibCxxMap.cpp revision 360784 
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
21using namespace lldb;
22using namespace lldb_private;
23using namespace lldb_private::formatters;
24
25class MapEntry {
26public:
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
81private:
82  ValueObjectSP m_entry_sp;
83};
84
85class MapIterator {
86public:
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
115protected:
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
140private:
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
173namespace lldb_private {
174namespace formatters {
175class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
176public:
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
191private:
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
206lldb_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
215size_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
250bool 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
289void 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
331lldb::ValueObjectSP
332lldb_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
438bool 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
451bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
452    MightHaveChildren() {
453  return true;
454}
455
456size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
457    GetIndexOfChildWithName(ConstString name) {
458  return ExtractIndexFromString(name.GetCString());
459}
460
461SyntheticChildrenFrontEnd *
462lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
463    CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
464  return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
465}
466