1//===-- LibCxxUnorderedMap.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/ConstString.h"
17#include "lldb/Utility/DataBufferHeap.h"
18#include "lldb/Utility/Endian.h"
19#include "lldb/Utility/Status.h"
20#include "lldb/Utility/Stream.h"
21#include "llvm/ADT/StringRef.h"
22
23using namespace lldb;
24using namespace lldb_private;
25using namespace lldb_private::formatters;
26
27namespace lldb_private {
28namespace formatters {
29class LibcxxStdUnorderedMapSyntheticFrontEnd
30    : public SyntheticChildrenFrontEnd {
31public:
32  LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
33
34  ~LibcxxStdUnorderedMapSyntheticFrontEnd() override = default;
35
36  size_t CalculateNumChildren() override;
37
38  lldb::ValueObjectSP GetChildAtIndex(size_t idx) override;
39
40  bool Update() override;
41
42  bool MightHaveChildren() override;
43
44  size_t GetIndexOfChildWithName(ConstString name) override;
45
46private:
47  CompilerType m_element_type;
48  CompilerType m_node_type;
49  ValueObject *m_tree = nullptr;
50  size_t m_num_elements = 0;
51  ValueObject *m_next_element = nullptr;
52  std::vector<std::pair<ValueObject *, uint64_t>> m_elements_cache;
53};
54} // namespace formatters
55} // namespace lldb_private
56
57lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
58    LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
59    : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(),
60      m_elements_cache() {
61  if (valobj_sp)
62    Update();
63}
64
65size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
66    CalculateNumChildren() {
67  return m_num_elements;
68}
69
70static void consumeInlineNamespace(llvm::StringRef &name) {
71  // Delete past an inline namespace, if any: __[a-zA-Z0-9_]+::
72  auto scratch = name;
73  if (scratch.consume_front("__") && std::isalnum(scratch[0])) {
74    scratch = scratch.drop_while([](char c) { return std::isalnum(c); });
75    if (scratch.consume_front("::")) {
76      // Successfully consumed a namespace.
77      name = scratch;
78    }
79  }
80}
81
82static bool isStdTemplate(ConstString type_name, llvm::StringRef type) {
83  llvm::StringRef name = type_name.GetStringRef();
84  // The type name may be prefixed with `std::__<inline-namespace>::`.
85  if (name.consume_front("std::"))
86    consumeInlineNamespace(name);
87  return name.consume_front(type) && name.starts_with("<");
88}
89
90static bool isUnorderedMap(ConstString type_name) {
91  return isStdTemplate(type_name, "unordered_map") ||
92         isStdTemplate(type_name, "unordered_multimap");
93}
94
95lldb::ValueObjectSP lldb_private::formatters::
96    LibcxxStdUnorderedMapSyntheticFrontEnd::GetChildAtIndex(size_t idx) {
97  if (idx >= CalculateNumChildren())
98    return lldb::ValueObjectSP();
99  if (m_tree == nullptr)
100    return lldb::ValueObjectSP();
101
102  while (idx >= m_elements_cache.size()) {
103    if (m_next_element == nullptr)
104      return lldb::ValueObjectSP();
105
106    Status error;
107    ValueObjectSP node_sp = m_next_element->Dereference(error);
108    if (!node_sp || error.Fail())
109      return lldb::ValueObjectSP();
110
111    ValueObjectSP value_sp = node_sp->GetChildMemberWithName("__value_");
112    ValueObjectSP hash_sp = node_sp->GetChildMemberWithName("__hash_");
113    if (!hash_sp || !value_sp) {
114      if (!m_element_type) {
115        auto p1_sp = m_backend.GetChildAtNamePath({"__table_", "__p1_"});
116        if (!p1_sp)
117          return nullptr;
118
119        ValueObjectSP first_sp = nullptr;
120        switch (p1_sp->GetCompilerType().GetNumDirectBaseClasses()) {
121        case 1:
122          // Assume a pre llvm r300140 __compressed_pair implementation:
123          first_sp = p1_sp->GetChildMemberWithName("__first_");
124          break;
125        case 2: {
126          // Assume a post llvm r300140 __compressed_pair implementation:
127          ValueObjectSP first_elem_parent_sp =
128            p1_sp->GetChildAtIndex(0);
129          first_sp = p1_sp->GetChildMemberWithName("__value_");
130          break;
131        }
132        default:
133          return nullptr;
134        }
135
136        if (!first_sp)
137          return nullptr;
138        m_element_type = first_sp->GetCompilerType();
139        m_element_type = m_element_type.GetTypeTemplateArgument(0);
140        m_element_type = m_element_type.GetPointeeType();
141        m_node_type = m_element_type;
142        m_element_type = m_element_type.GetTypeTemplateArgument(0);
143        // This synthetic provider is used for both unordered_(multi)map and
144        // unordered_(multi)set. For unordered_map, the element type has an
145        // additional type layer, an internal struct (`__hash_value_type`)
146        // that wraps a std::pair. Peel away the internal wrapper type - whose
147        // structure is of no value to users, to expose the std::pair. This
148        // matches the structure returned by the std::map synthetic provider.
149        if (isUnorderedMap(m_backend.GetTypeName())) {
150          std::string name;
151          CompilerType field_type = m_element_type.GetFieldAtIndex(
152              0, name, nullptr, nullptr, nullptr);
153          CompilerType actual_type = field_type.GetTypedefedType();
154          if (isStdTemplate(actual_type.GetTypeName(), "pair"))
155            m_element_type = actual_type;
156        }
157      }
158      if (!m_node_type)
159        return nullptr;
160      node_sp = m_next_element->Cast(m_node_type.GetPointerType())
161              ->Dereference(error);
162      if (!node_sp || error.Fail())
163          return nullptr;
164
165      hash_sp = node_sp->GetChildMemberWithName("__hash_");
166      if (!hash_sp)
167        return nullptr;
168
169      value_sp = node_sp->GetChildMemberWithName("__value_");
170      if (!value_sp) {
171        // clang-format off
172        // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
173        // anonymous union.
174        // Child 0: __hash_node_base base class
175        // Child 1: __hash_
176        // Child 2: anonymous union
177        // clang-format on
178        auto anon_union_sp = node_sp->GetChildAtIndex(2);
179        if (!anon_union_sp)
180          return nullptr;
181
182        value_sp = anon_union_sp->GetChildMemberWithName("__value_");
183        if (!value_sp)
184          return nullptr;
185      }
186    }
187    m_elements_cache.push_back(
188        {value_sp.get(), hash_sp->GetValueAsUnsigned(0)});
189    m_next_element = node_sp->GetChildMemberWithName("__next_").get();
190    if (!m_next_element || m_next_element->GetValueAsUnsigned(0) == 0)
191      m_next_element = nullptr;
192  }
193
194  std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx];
195  if (!val_hash.first)
196    return lldb::ValueObjectSP();
197  StreamString stream;
198  stream.Printf("[%" PRIu64 "]", (uint64_t)idx);
199  DataExtractor data;
200  Status error;
201  val_hash.first->GetData(data, error);
202  if (error.Fail())
203    return lldb::ValueObjectSP();
204  const bool thread_and_frame_only_if_stopped = true;
205  ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock(
206      thread_and_frame_only_if_stopped);
207  return CreateValueObjectFromData(stream.GetString(), data, exe_ctx,
208                                   m_element_type);
209}
210
211bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
212    Update() {
213  m_num_elements = 0;
214  m_next_element = nullptr;
215  m_elements_cache.clear();
216  ValueObjectSP table_sp = m_backend.GetChildMemberWithName("__table_");
217  if (!table_sp)
218    return false;
219
220  ValueObjectSP p2_sp = table_sp->GetChildMemberWithName("__p2_");
221  ValueObjectSP num_elements_sp = nullptr;
222  llvm::SmallVector<llvm::StringRef, 3> next_path;
223  switch (p2_sp->GetCompilerType().GetNumDirectBaseClasses()) {
224  case 1:
225    // Assume a pre llvm r300140 __compressed_pair implementation:
226    num_elements_sp = p2_sp->GetChildMemberWithName("__first_");
227    next_path.append({"__p1_", "__first_", "__next_"});
228    break;
229  case 2: {
230    // Assume a post llvm r300140 __compressed_pair implementation:
231    ValueObjectSP first_elem_parent = p2_sp->GetChildAtIndex(0);
232    num_elements_sp = first_elem_parent->GetChildMemberWithName("__value_");
233    next_path.append({"__p1_", "__value_", "__next_"});
234    break;
235  }
236  default:
237    return false;
238  }
239
240  if (!num_elements_sp)
241    return false;
242
243  m_tree = table_sp->GetChildAtNamePath(next_path).get();
244  if (m_tree == nullptr)
245    return false;
246
247  m_num_elements = num_elements_sp->GetValueAsUnsigned(0);
248
249  if (m_num_elements > 0)
250    m_next_element =
251        table_sp->GetChildAtNamePath(next_path).get();
252  return false;
253}
254
255bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
256    MightHaveChildren() {
257  return true;
258}
259
260size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
261    GetIndexOfChildWithName(ConstString name) {
262  return ExtractIndexFromString(name.GetCString());
263}
264
265SyntheticChildrenFrontEnd *
266lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
267    CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
268  return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
269                    : nullptr);
270}
271