xref: /freebsd/contrib/llvm-project/lldb/source/Plugins/Language/CPlusPlus/LibCxxMap.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
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  #include "lldb/lldb-enumerations.h"
21  #include "lldb/lldb-forward.h"
22  #include <cstdint>
23  #include <locale>
24  #include <optional>
25  
26  using namespace lldb;
27  using namespace lldb_private;
28  using namespace lldb_private::formatters;
29  
30  // The flattened layout of the std::__tree_iterator::__ptr_ looks
31  // as follows:
32  //
33  // The following shows the contiguous block of memory:
34  //
35  //        +-----------------------------+ class __tree_end_node
36  // __ptr_ | pointer __left_;            |
37  //        +-----------------------------+ class __tree_node_base
38  //        | pointer __right_;           |
39  //        | __parent_pointer __parent_; |
40  //        | bool __is_black_;           |
41  //        +-----------------------------+ class __tree_node
42  //        | __node_value_type __value_; | <<< our key/value pair
43  //        +-----------------------------+
44  //
45  // where __ptr_ has type __iter_pointer.
46  
47  class MapEntry {
48  public:
49    MapEntry() = default;
MapEntry(ValueObjectSP entry_sp)50    explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
MapEntry(ValueObject * entry)51    explicit MapEntry(ValueObject *entry)
52        : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
53  
left() const54    ValueObjectSP left() const {
55      if (!m_entry_sp)
56        return m_entry_sp;
57      return m_entry_sp->GetSyntheticChildAtOffset(
58          0, m_entry_sp->GetCompilerType(), true);
59    }
60  
right() const61    ValueObjectSP right() const {
62      if (!m_entry_sp)
63        return m_entry_sp;
64      return m_entry_sp->GetSyntheticChildAtOffset(
65          m_entry_sp->GetProcessSP()->GetAddressByteSize(),
66          m_entry_sp->GetCompilerType(), true);
67    }
68  
parent() const69    ValueObjectSP parent() const {
70      if (!m_entry_sp)
71        return m_entry_sp;
72      return m_entry_sp->GetSyntheticChildAtOffset(
73          2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(),
74          m_entry_sp->GetCompilerType(), true);
75    }
76  
value() const77    uint64_t value() const {
78      if (!m_entry_sp)
79        return 0;
80      return m_entry_sp->GetValueAsUnsigned(0);
81    }
82  
error() const83    bool error() const {
84      if (!m_entry_sp)
85        return true;
86      return m_entry_sp->GetError().Fail();
87    }
88  
null() const89    bool null() const { return (value() == 0); }
90  
GetEntry() const91    ValueObjectSP GetEntry() const { return m_entry_sp; }
92  
SetEntry(ValueObjectSP entry)93    void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
94  
operator ==(const MapEntry & rhs) const95    bool operator==(const MapEntry &rhs) const {
96      return (rhs.m_entry_sp.get() == m_entry_sp.get());
97    }
98  
99  private:
100    ValueObjectSP m_entry_sp;
101  };
102  
103  class MapIterator {
104  public:
MapIterator(ValueObject * entry,size_t depth=0)105    MapIterator(ValueObject *entry, size_t depth = 0)
106        : m_entry(entry), m_max_depth(depth), m_error(false) {}
107  
108    MapIterator() = default;
109  
value()110    ValueObjectSP value() { return m_entry.GetEntry(); }
111  
advance(size_t count)112    ValueObjectSP advance(size_t count) {
113      ValueObjectSP fail;
114      if (m_error)
115        return fail;
116      size_t steps = 0;
117      while (count > 0) {
118        next();
119        count--, steps++;
120        if (m_error || m_entry.null() || (steps > m_max_depth))
121          return fail;
122      }
123      return m_entry.GetEntry();
124    }
125  
126  private:
127    /// Mimicks libc++'s __tree_next algorithm, which libc++ uses
128    /// in its __tree_iteartor::operator++.
next()129    void next() {
130      if (m_entry.null())
131        return;
132      MapEntry right(m_entry.right());
133      if (!right.null()) {
134        m_entry = tree_min(std::move(right));
135        return;
136      }
137      size_t steps = 0;
138      while (!is_left_child(m_entry)) {
139        if (m_entry.error()) {
140          m_error = true;
141          return;
142        }
143        m_entry.SetEntry(m_entry.parent());
144        steps++;
145        if (steps > m_max_depth) {
146          m_entry = MapEntry();
147          return;
148        }
149      }
150      m_entry = MapEntry(m_entry.parent());
151    }
152  
153    /// Mimicks libc++'s __tree_min algorithm.
tree_min(MapEntry x)154    MapEntry tree_min(MapEntry x) {
155      if (x.null())
156        return MapEntry();
157      MapEntry left(x.left());
158      size_t steps = 0;
159      while (!left.null()) {
160        if (left.error()) {
161          m_error = true;
162          return MapEntry();
163        }
164        x = left;
165        left.SetEntry(x.left());
166        steps++;
167        if (steps > m_max_depth)
168          return MapEntry();
169      }
170      return x;
171    }
172  
is_left_child(const MapEntry & x)173    bool is_left_child(const MapEntry &x) {
174      if (x.null())
175        return false;
176      MapEntry rhs(x.parent());
177      rhs.SetEntry(rhs.left());
178      return x.value() == rhs.value();
179    }
180  
181    MapEntry m_entry;
182    size_t m_max_depth = 0;
183    bool m_error = false;
184  };
185  
186  namespace lldb_private {
187  namespace formatters {
188  class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
189  public:
190    LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
191  
192    ~LibcxxStdMapSyntheticFrontEnd() override = default;
193  
194    llvm::Expected<uint32_t> CalculateNumChildren() override;
195  
196    lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
197  
198    lldb::ChildCacheState Update() override;
199  
200    bool MightHaveChildren() override;
201  
202    size_t GetIndexOfChildWithName(ConstString name) override;
203  
204  private:
205    /// Returns the ValueObject for the __tree_node type that
206    /// holds the key/value pair of the node at index \ref idx.
207    ///
208    /// \param[in] idx The child index that we're looking to get
209    ///                the key/value pair for.
210    ///
211    /// \param[in] max_depth The maximum search depth after which
212    ///                      we stop trying to find the key/value
213    ///                      pair for.
214    ///
215    /// \returns On success, returns the ValueObjectSP corresponding
216    ///          to the __tree_node's __value_ member (which holds
217    ///          the key/value pair the formatter wants to display).
218    ///          On failure, will return nullptr.
219    ValueObjectSP GetKeyValuePair(size_t idx, size_t max_depth);
220  
221    ValueObject *m_tree = nullptr;
222    ValueObject *m_root_node = nullptr;
223    CompilerType m_node_ptr_type;
224    size_t m_count = UINT32_MAX;
225    std::map<size_t, MapIterator> m_iterators;
226  };
227  
228  class LibCxxMapIteratorSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
229  public:
230    LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
231  
232    llvm::Expected<uint32_t> CalculateNumChildren() override;
233  
234    lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
235  
236    lldb::ChildCacheState Update() override;
237  
238    bool MightHaveChildren() override;
239  
240    size_t GetIndexOfChildWithName(ConstString name) override;
241  
242    ~LibCxxMapIteratorSyntheticFrontEnd() override = default;
243  
244  private:
245    ValueObjectSP m_pair_sp = nullptr;
246  };
247  } // namespace formatters
248  } // namespace lldb_private
249  
250  lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)251      LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
252      : SyntheticChildrenFrontEnd(*valobj_sp) {
253    if (valobj_sp)
254      Update();
255  }
256  
257  llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()258      LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren() {
259    if (m_count != UINT32_MAX)
260      return m_count;
261  
262    if (m_tree == nullptr)
263      return 0;
264  
265    ValueObjectSP size_node(m_tree->GetChildMemberWithName("__pair3_"));
266    if (!size_node)
267      return 0;
268  
269    size_node = GetFirstValueOfLibCXXCompressedPair(*size_node);
270  
271    if (!size_node)
272      return 0;
273  
274    m_count = size_node->GetValueAsUnsigned(0);
275    return m_count;
276  }
277  
278  ValueObjectSP
GetKeyValuePair(size_t idx,size_t max_depth)279  lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetKeyValuePair(
280      size_t idx, size_t max_depth) {
281    MapIterator iterator(m_root_node, max_depth);
282  
283    size_t advance_by = idx;
284    if (idx > 0) {
285      // If we have already created the iterator for the previous
286      // index, we can start from there and advance by 1.
287      auto cached_iterator = m_iterators.find(idx - 1);
288      if (cached_iterator != m_iterators.end()) {
289        iterator = cached_iterator->second;
290        advance_by = 1;
291      }
292    }
293  
294    ValueObjectSP iterated_sp(iterator.advance(advance_by));
295    if (!iterated_sp)
296      // this tree is garbage - stop
297      return nullptr;
298  
299    if (!m_node_ptr_type.IsValid())
300      return nullptr;
301  
302    // iterated_sp is a __iter_pointer at this point.
303    // We can cast it to a __node_pointer (which is what libc++ does).
304    auto value_type_sp = iterated_sp->Cast(m_node_ptr_type);
305    if (!value_type_sp)
306      return nullptr;
307  
308    // Finally, get the key/value pair.
309    value_type_sp = value_type_sp->GetChildMemberWithName("__value_");
310    if (!value_type_sp)
311      return nullptr;
312  
313    m_iterators[idx] = iterator;
314  
315    return value_type_sp;
316  }
317  
318  lldb::ValueObjectSP
GetChildAtIndex(uint32_t idx)319  lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex(
320      uint32_t idx) {
321    static ConstString g_cc_("__cc_"), g_cc("__cc");
322    static ConstString g_nc("__nc");
323    uint32_t num_children = CalculateNumChildrenIgnoringErrors();
324    if (idx >= num_children)
325      return nullptr;
326  
327    if (m_tree == nullptr || m_root_node == nullptr)
328      return nullptr;
329  
330    ValueObjectSP key_val_sp = GetKeyValuePair(idx, /*max_depth=*/num_children);
331    if (!key_val_sp) {
332      // this will stop all future searches until an Update() happens
333      m_tree = nullptr;
334      return nullptr;
335    }
336  
337    // at this point we have a valid
338    // we need to copy current_sp into a new object otherwise we will end up with
339    // all items named __value_
340    StreamString name;
341    name.Printf("[%" PRIu64 "]", (uint64_t)idx);
342    auto potential_child_sp = key_val_sp->Clone(ConstString(name.GetString()));
343    if (potential_child_sp) {
344      switch (potential_child_sp->GetNumChildrenIgnoringErrors()) {
345      case 1: {
346        auto child0_sp = potential_child_sp->GetChildAtIndex(0);
347        if (child0_sp &&
348            (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))
349          potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
350        break;
351      }
352      case 2: {
353        auto child0_sp = potential_child_sp->GetChildAtIndex(0);
354        auto child1_sp = potential_child_sp->GetChildAtIndex(1);
355        if (child0_sp &&
356            (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&
357            child1_sp && child1_sp->GetName() == g_nc)
358          potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));
359        break;
360      }
361      }
362    }
363    return potential_child_sp;
364  }
365  
366  lldb::ChildCacheState
Update()367  lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() {
368    m_count = UINT32_MAX;
369    m_tree = m_root_node = nullptr;
370    m_iterators.clear();
371    m_tree = m_backend.GetChildMemberWithName("__tree_").get();
372    if (!m_tree)
373      return lldb::ChildCacheState::eRefetch;
374    m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get();
375    m_node_ptr_type =
376        m_tree->GetCompilerType().GetDirectNestedTypeWithName("__node_pointer");
377  
378    return lldb::ChildCacheState::eRefetch;
379  }
380  
381  bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
MightHaveChildren()382      MightHaveChildren() {
383    return true;
384  }
385  
386  size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)387      GetIndexOfChildWithName(ConstString name) {
388    return ExtractIndexFromString(name.GetCString());
389  }
390  
391  SyntheticChildrenFrontEnd *
LibcxxStdMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)392  lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(
393      CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
394    return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr);
395  }
396  
397  lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)398      LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
399      : SyntheticChildrenFrontEnd(*valobj_sp) {
400    if (valobj_sp)
401      Update();
402  }
403  
404  lldb::ChildCacheState
Update()405  lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::Update() {
406    m_pair_sp.reset();
407  
408    ValueObjectSP valobj_sp = m_backend.GetSP();
409    if (!valobj_sp)
410      return lldb::ChildCacheState::eRefetch;
411  
412    TargetSP target_sp(valobj_sp->GetTargetSP());
413    if (!target_sp)
414      return lldb::ChildCacheState::eRefetch;
415  
416    // m_backend is a std::map::iterator
417    // ...which is a __map_iterator<__tree_iterator<..., __node_pointer, ...>>
418    //
419    // Then, __map_iterator::__i_ is a __tree_iterator
420    auto tree_iter_sp = valobj_sp->GetChildMemberWithName("__i_");
421    if (!tree_iter_sp)
422      return lldb::ChildCacheState::eRefetch;
423  
424    // Type is __tree_iterator::__node_pointer
425    // (We could alternatively also get this from the template argument)
426    auto node_pointer_type =
427        tree_iter_sp->GetCompilerType().GetDirectNestedTypeWithName(
428            "__node_pointer");
429    if (!node_pointer_type.IsValid())
430      return lldb::ChildCacheState::eRefetch;
431  
432    // __ptr_ is a __tree_iterator::__iter_pointer
433    auto iter_pointer_sp = tree_iter_sp->GetChildMemberWithName("__ptr_");
434    if (!iter_pointer_sp)
435      return lldb::ChildCacheState::eRefetch;
436  
437    // Cast the __iter_pointer to a __node_pointer (which stores our key/value
438    // pair)
439    auto node_pointer_sp = iter_pointer_sp->Cast(node_pointer_type);
440    if (!node_pointer_sp)
441      return lldb::ChildCacheState::eRefetch;
442  
443    auto key_value_sp = node_pointer_sp->GetChildMemberWithName("__value_");
444    if (!key_value_sp)
445      return lldb::ChildCacheState::eRefetch;
446  
447    // Create the synthetic child, which is a pair where the key and value can be
448    // retrieved by querying the synthetic frontend for
449    // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
450    // respectively.
451    //
452    // std::map stores the actual key/value pair in value_type::__cc_ (or
453    // previously __cc).
454    key_value_sp = key_value_sp->Clone(ConstString("pair"));
455    if (key_value_sp->GetNumChildrenIgnoringErrors() == 1) {
456      auto child0_sp = key_value_sp->GetChildAtIndex(0);
457      if (child0_sp &&
458          (child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc"))
459        key_value_sp = child0_sp->Clone(ConstString("pair"));
460    }
461  
462    m_pair_sp = key_value_sp;
463  
464    return lldb::ChildCacheState::eRefetch;
465  }
466  
467  llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()468      LibCxxMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
469    return 2;
470  }
471  
472  lldb::ValueObjectSP
GetChildAtIndex(uint32_t idx)473  lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::GetChildAtIndex(
474      uint32_t idx) {
475    if (!m_pair_sp)
476      return nullptr;
477  
478    return m_pair_sp->GetChildAtIndex(idx);
479  }
480  
481  bool lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
MightHaveChildren()482      MightHaveChildren() {
483    return true;
484  }
485  
486  size_t lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)487      GetIndexOfChildWithName(ConstString name) {
488    if (!m_pair_sp)
489      return UINT32_MAX;
490  
491    return m_pair_sp->GetIndexOfChildWithName(name);
492  }
493  
494  SyntheticChildrenFrontEnd *
LibCxxMapIteratorSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)495  lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEndCreator(
496      CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
497    return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp)
498                      : nullptr);
499  }
500