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
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  explicit MapEntry(ValueObject *entry)
30      : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
31
32  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
40  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
49  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
58  uint64_t value() const {
59    if (!m_entry_sp)
60      return 0;
61    return m_entry_sp->GetValueAsUnsigned(0);
62  }
63
64  bool error() const {
65    if (!m_entry_sp)
66      return true;
67    return m_entry_sp->GetError().Fail();
68  }
69
70  bool null() const { return (value() == 0); }
71
72  ValueObjectSP GetEntry() const { return m_entry_sp; }
73
74  void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
75
76  bool operator==(const MapEntry &rhs) const {
77    return (rhs.m_entry_sp.get() == m_entry_sp.get());
78  }
79
80private:
81  ValueObjectSP m_entry_sp;
82};
83
84class MapIterator {
85public:
86  MapIterator() = default;
87  MapIterator(MapEntry entry, size_t depth = 0)
88      : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {}
89  MapIterator(ValueObjectSP entry, size_t depth = 0)
90      : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {}
91  MapIterator(const MapIterator &rhs)
92      : m_entry(rhs.m_entry), m_max_depth(rhs.m_max_depth), m_error(false) {}
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
98  ValueObjectSP value() { return m_entry.GetEntry(); }
99
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
114protected:
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
139private:
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
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
172namespace lldb_private {
173namespace formatters {
174class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
175public:
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
190private:
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
205lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
206    LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
207    : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(), m_iterators() {
208  if (valobj_sp)
209    Update();
210}
211
212size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
213    CalculateNumChildren() {
214  if (m_count != UINT32_MAX)
215    return m_count;
216  if (m_tree == nullptr)
217    return 0;
218  ValueObjectSP m_item(m_tree->GetChildMemberWithName("__pair3_"));
219  if (!m_item)
220    return 0;
221
222  switch (m_item->GetCompilerType().GetNumDirectBaseClasses()) {
223  case 1:
224    // Assume a pre llvm r300140 __compressed_pair implementation:
225    m_item = m_item->GetChildMemberWithName("__first_");
226    break;
227  case 2: {
228    // Assume a post llvm r300140 __compressed_pair implementation:
229    ValueObjectSP first_elem_parent = m_item->GetChildAtIndex(0);
230    m_item = first_elem_parent->GetChildMemberWithName("__value_");
231    break;
232  }
233  default:
234    return false;
235  }
236
237  if (!m_item)
238    return 0;
239  m_count = m_item->GetValueAsUnsigned(0);
240  return m_count;
241}
242
243bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() {
244  if (m_element_type.IsValid())
245    return true;
246  m_element_type.Clear();
247  ValueObjectSP deref;
248  Status error;
249  deref = m_root_node->Dereference(error);
250  if (!deref || error.Fail())
251    return false;
252  deref = deref->GetChildMemberWithName("__value_");
253  if (deref) {
254    m_element_type = deref->GetCompilerType();
255    return true;
256  }
257  deref = m_backend.GetChildAtNamePath({"__tree_", "__pair3_"});
258  if (!deref)
259    return false;
260  m_element_type = deref->GetCompilerType()
261                       .GetTypeTemplateArgument(1)
262                       .GetTypeTemplateArgument(1);
263  if (m_element_type) {
264    std::string name;
265    uint64_t bit_offset_ptr;
266    uint32_t bitfield_bit_size_ptr;
267    bool is_bitfield_ptr;
268    m_element_type = m_element_type.GetFieldAtIndex(
269        0, name, &bit_offset_ptr, &bitfield_bit_size_ptr, &is_bitfield_ptr);
270    m_element_type = m_element_type.GetTypedefedType();
271    return m_element_type.IsValid();
272  } else {
273    m_element_type = m_backend.GetCompilerType().GetTypeTemplateArgument(0);
274    return m_element_type.IsValid();
275  }
276}
277
278void lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset(
279    const lldb::ValueObjectSP &node) {
280  if (m_skip_size != UINT32_MAX)
281    return;
282  if (!node)
283    return;
284  CompilerType node_type(node->GetCompilerType());
285  uint64_t bit_offset;
286  if (node_type.GetIndexOfFieldWithName("__value_", nullptr, &bit_offset) !=
287      UINT32_MAX) {
288    m_skip_size = bit_offset / 8u;
289  } else {
290    auto ast_ctx = node_type.GetTypeSystem().dyn_cast_or_null<TypeSystemClang>();
291    if (!ast_ctx)
292      return;
293    CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier(
294        llvm::StringRef(),
295        {{"ptr0", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},
296         {"ptr1", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},
297         {"ptr2", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},
298         {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)},
299         {"payload", (m_element_type.GetCompleteType(), m_element_type)}});
300    std::string child_name;
301    uint32_t child_byte_size;
302    int32_t child_byte_offset = 0;
303    uint32_t child_bitfield_bit_size;
304    uint32_t child_bitfield_bit_offset;
305    bool child_is_base_class;
306    bool child_is_deref_of_parent;
307    uint64_t language_flags;
308    if (tree_node_type
309            .GetChildCompilerTypeAtIndex(
310                nullptr, 4, true, true, true, child_name, child_byte_size,
311                child_byte_offset, child_bitfield_bit_size,
312                child_bitfield_bit_offset, child_is_base_class,
313                child_is_deref_of_parent, nullptr, language_flags)
314            .IsValid())
315      m_skip_size = (uint32_t)child_byte_offset;
316  }
317}
318
319lldb::ValueObjectSP
320lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex(
321    size_t idx) {
322  static ConstString g_cc_("__cc_"), g_cc("__cc");
323  static ConstString g_nc("__nc");
324
325  if (idx >= CalculateNumChildren())
326    return lldb::ValueObjectSP();
327  if (m_tree == nullptr || m_root_node == nullptr)
328    return lldb::ValueObjectSP();
329
330  MapIterator iterator(m_root_node, CalculateNumChildren());
331
332  const bool need_to_skip = (idx > 0);
333  size_t actual_advancde = idx;
334  if (need_to_skip) {
335    auto cached_iterator = m_iterators.find(idx - 1);
336    if (cached_iterator != m_iterators.end()) {
337      iterator = cached_iterator->second;
338      actual_advancde = 1;
339    }
340  }
341
342  ValueObjectSP iterated_sp(iterator.advance(actual_advancde));
343  if (!iterated_sp) {
344    // this tree is garbage - stop
345    m_tree =
346        nullptr; // this will stop all future searches until an Update() happens
347    return iterated_sp;
348  }
349  if (GetDataType()) {
350    if (!need_to_skip) {
351      Status error;
352      iterated_sp = iterated_sp->Dereference(error);
353      if (!iterated_sp || error.Fail()) {
354        m_tree = nullptr;
355        return lldb::ValueObjectSP();
356      }
357      GetValueOffset(iterated_sp);
358      auto child_sp = iterated_sp->GetChildMemberWithName("__value_");
359      if (child_sp)
360        iterated_sp = child_sp;
361      else
362        iterated_sp = iterated_sp->GetSyntheticChildAtOffset(
363            m_skip_size, m_element_type, true);
364      if (!iterated_sp) {
365        m_tree = nullptr;
366        return lldb::ValueObjectSP();
367      }
368    } else {
369      // because of the way our debug info is made, we need to read item 0
370      // first so that we can cache information used to generate other elements
371      if (m_skip_size == UINT32_MAX)
372        GetChildAtIndex(0);
373      if (m_skip_size == UINT32_MAX) {
374        m_tree = nullptr;
375        return lldb::ValueObjectSP();
376      }
377      iterated_sp = iterated_sp->GetSyntheticChildAtOffset(
378          m_skip_size, m_element_type, true);
379      if (!iterated_sp) {
380        m_tree = nullptr;
381        return lldb::ValueObjectSP();
382      }
383    }
384  } else {
385    m_tree = nullptr;
386    return lldb::ValueObjectSP();
387  }
388  // at this point we have a valid
389  // we need to copy current_sp into a new object otherwise we will end up with
390  // all items named __value_
391  StreamString name;
392  name.Printf("[%" PRIu64 "]", (uint64_t)idx);
393  auto potential_child_sp = iterated_sp->Clone(ConstString(name.GetString()));
394  if (potential_child_sp) {
395    switch (potential_child_sp->GetNumChildren()) {
396    case 1: {
397      auto child0_sp = potential_child_sp->GetChildAtIndex(0);
398      if (child0_sp &&
399          (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))
400        potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
401      break;
402    }
403    case 2: {
404      auto child0_sp = potential_child_sp->GetChildAtIndex(0);
405      auto child1_sp = potential_child_sp->GetChildAtIndex(1);
406      if (child0_sp &&
407          (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&
408          child1_sp && child1_sp->GetName() == g_nc)
409        potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
410      break;
411    }
412    }
413  }
414  m_iterators[idx] = iterator;
415  return potential_child_sp;
416}
417
418bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() {
419  m_count = UINT32_MAX;
420  m_tree = m_root_node = nullptr;
421  m_iterators.clear();
422  m_tree = m_backend.GetChildMemberWithName("__tree_").get();
423  if (!m_tree)
424    return false;
425  m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get();
426  return false;
427}
428
429bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
430    MightHaveChildren() {
431  return true;
432}
433
434size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
435    GetIndexOfChildWithName(ConstString name) {
436  return ExtractIndexFromString(name.GetCString());
437}
438
439SyntheticChildrenFrontEnd *
440lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
441    CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
442  return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
443}
444