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
23 using namespace lldb;
24 using namespace lldb_private;
25 using namespace lldb_private::formatters;
26
27 namespace lldb_private {
28 namespace formatters {
29 class LibcxxStdUnorderedMapSyntheticFrontEnd
30 : public SyntheticChildrenFrontEnd {
31 public:
32 LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
33
34 ~LibcxxStdUnorderedMapSyntheticFrontEnd() override = default;
35
36 llvm::Expected<uint32_t> CalculateNumChildren() override;
37
38 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
39
40 lldb::ChildCacheState Update() override;
41
42 bool MightHaveChildren() override;
43
44 size_t GetIndexOfChildWithName(ConstString name) override;
45
46 private:
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
55 class LibCxxUnorderedMapIteratorSyntheticFrontEnd
56 : public SyntheticChildrenFrontEnd {
57 public:
58 LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
59
60 ~LibCxxUnorderedMapIteratorSyntheticFrontEnd() override = default;
61
62 llvm::Expected<uint32_t> CalculateNumChildren() override;
63
64 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
65
66 lldb::ChildCacheState Update() override;
67
68 bool MightHaveChildren() override;
69
70 size_t GetIndexOfChildWithName(ConstString name) override;
71
72 private:
73 lldb::ValueObjectSP m_pair_sp; ///< ValueObject for the key/value pair
74 ///< that the iterator currently points
75 ///< to.
76 };
77
78 } // namespace formatters
79 } // namespace lldb_private
80
81 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)82 LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
83 : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(),
84 m_elements_cache() {
85 if (valobj_sp)
86 Update();
87 }
88
89 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()90 LibcxxStdUnorderedMapSyntheticFrontEnd::CalculateNumChildren() {
91 return m_num_elements;
92 }
93
consumeInlineNamespace(llvm::StringRef & name)94 static void consumeInlineNamespace(llvm::StringRef &name) {
95 // Delete past an inline namespace, if any: __[a-zA-Z0-9_]+::
96 auto scratch = name;
97 if (scratch.consume_front("__") && std::isalnum(scratch[0])) {
98 scratch = scratch.drop_while([](char c) { return std::isalnum(c); });
99 if (scratch.consume_front("::")) {
100 // Successfully consumed a namespace.
101 name = scratch;
102 }
103 }
104 }
105
isStdTemplate(ConstString type_name,llvm::StringRef type)106 static bool isStdTemplate(ConstString type_name, llvm::StringRef type) {
107 llvm::StringRef name = type_name.GetStringRef();
108 // The type name may be prefixed with `std::__<inline-namespace>::`.
109 if (name.consume_front("std::"))
110 consumeInlineNamespace(name);
111 return name.consume_front(type) && name.starts_with("<");
112 }
113
isUnorderedMap(ConstString type_name)114 static bool isUnorderedMap(ConstString type_name) {
115 return isStdTemplate(type_name, "unordered_map") ||
116 isStdTemplate(type_name, "unordered_multimap");
117 }
118
119 lldb::ValueObjectSP lldb_private::formatters::
GetChildAtIndex(uint32_t idx)120 LibcxxStdUnorderedMapSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
121 if (idx >= CalculateNumChildrenIgnoringErrors())
122 return lldb::ValueObjectSP();
123 if (m_tree == nullptr)
124 return lldb::ValueObjectSP();
125
126 while (idx >= m_elements_cache.size()) {
127 if (m_next_element == nullptr)
128 return lldb::ValueObjectSP();
129
130 Status error;
131 ValueObjectSP node_sp = m_next_element->Dereference(error);
132 if (!node_sp || error.Fail())
133 return lldb::ValueObjectSP();
134
135 ValueObjectSP value_sp = node_sp->GetChildMemberWithName("__value_");
136 ValueObjectSP hash_sp = node_sp->GetChildMemberWithName("__hash_");
137 if (!hash_sp || !value_sp) {
138 if (!m_element_type) {
139 auto p1_sp = m_backend.GetChildAtNamePath({"__table_", "__p1_"});
140 if (!p1_sp)
141 return nullptr;
142
143 ValueObjectSP first_sp = GetFirstValueOfLibCXXCompressedPair(*p1_sp);
144 if (!first_sp)
145 return nullptr;
146
147 m_element_type = first_sp->GetCompilerType();
148 m_element_type = m_element_type.GetTypeTemplateArgument(0);
149 m_element_type = m_element_type.GetPointeeType();
150 m_node_type = m_element_type;
151 m_element_type = m_element_type.GetTypeTemplateArgument(0);
152 // This synthetic provider is used for both unordered_(multi)map and
153 // unordered_(multi)set. For unordered_map, the element type has an
154 // additional type layer, an internal struct (`__hash_value_type`)
155 // that wraps a std::pair. Peel away the internal wrapper type - whose
156 // structure is of no value to users, to expose the std::pair. This
157 // matches the structure returned by the std::map synthetic provider.
158 if (isUnorderedMap(m_backend.GetTypeName())) {
159 std::string name;
160 CompilerType field_type = m_element_type.GetFieldAtIndex(
161 0, name, nullptr, nullptr, nullptr);
162 CompilerType actual_type = field_type.GetTypedefedType();
163 if (isStdTemplate(actual_type.GetTypeName(), "pair"))
164 m_element_type = actual_type;
165 }
166 }
167 if (!m_node_type)
168 return nullptr;
169 node_sp = m_next_element->Cast(m_node_type.GetPointerType())
170 ->Dereference(error);
171 if (!node_sp || error.Fail())
172 return nullptr;
173
174 hash_sp = node_sp->GetChildMemberWithName("__hash_");
175 if (!hash_sp)
176 return nullptr;
177
178 value_sp = node_sp->GetChildMemberWithName("__value_");
179 if (!value_sp) {
180 // clang-format off
181 // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
182 // anonymous union.
183 // Child 0: __hash_node_base base class
184 // Child 1: __hash_
185 // Child 2: anonymous union
186 // clang-format on
187 auto anon_union_sp = node_sp->GetChildAtIndex(2);
188 if (!anon_union_sp)
189 return nullptr;
190
191 value_sp = anon_union_sp->GetChildMemberWithName("__value_");
192 if (!value_sp)
193 return nullptr;
194 }
195 }
196 m_elements_cache.push_back(
197 {value_sp.get(), hash_sp->GetValueAsUnsigned(0)});
198 m_next_element = node_sp->GetChildMemberWithName("__next_").get();
199 if (!m_next_element || m_next_element->GetValueAsUnsigned(0) == 0)
200 m_next_element = nullptr;
201 }
202
203 std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx];
204 if (!val_hash.first)
205 return lldb::ValueObjectSP();
206 StreamString stream;
207 stream.Printf("[%" PRIu64 "]", (uint64_t)idx);
208 DataExtractor data;
209 Status error;
210 val_hash.first->GetData(data, error);
211 if (error.Fail())
212 return lldb::ValueObjectSP();
213 const bool thread_and_frame_only_if_stopped = true;
214 ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock(
215 thread_and_frame_only_if_stopped);
216 return CreateValueObjectFromData(stream.GetString(), data, exe_ctx,
217 m_element_type);
218 }
219
220 lldb::ChildCacheState
Update()221 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::Update() {
222 m_num_elements = 0;
223 m_next_element = nullptr;
224 m_elements_cache.clear();
225 ValueObjectSP table_sp = m_backend.GetChildMemberWithName("__table_");
226 if (!table_sp)
227 return lldb::ChildCacheState::eRefetch;
228
229 ValueObjectSP p2_sp = table_sp->GetChildMemberWithName("__p2_");
230 if (!p2_sp)
231 return lldb::ChildCacheState::eRefetch;
232
233 ValueObjectSP num_elements_sp = GetFirstValueOfLibCXXCompressedPair(*p2_sp);
234 if (!num_elements_sp)
235 return lldb::ChildCacheState::eRefetch;
236
237 ValueObjectSP p1_sp = table_sp->GetChildMemberWithName("__p1_");
238 if (!p1_sp)
239 return lldb::ChildCacheState::eRefetch;
240
241 ValueObjectSP value_sp = GetFirstValueOfLibCXXCompressedPair(*p1_sp);
242 if (!value_sp)
243 return lldb::ChildCacheState::eRefetch;
244
245 m_tree = value_sp->GetChildMemberWithName("__next_").get();
246 if (m_tree == nullptr)
247 return lldb::ChildCacheState::eRefetch;
248
249 m_num_elements = num_elements_sp->GetValueAsUnsigned(0);
250
251 if (m_num_elements > 0)
252 m_next_element = m_tree;
253
254 return lldb::ChildCacheState::eRefetch;
255 }
256
257 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
MightHaveChildren()258 MightHaveChildren() {
259 return true;
260 }
261
262 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)263 GetIndexOfChildWithName(ConstString name) {
264 return ExtractIndexFromString(name.GetCString());
265 }
266
267 SyntheticChildrenFrontEnd *
LibcxxStdUnorderedMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)268 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
269 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
270 return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
271 : nullptr);
272 }
273
274 lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)275 LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
276 : SyntheticChildrenFrontEnd(*valobj_sp) {
277 if (valobj_sp)
278 Update();
279 }
280
281 lldb::ChildCacheState lldb_private::formatters::
Update()282 LibCxxUnorderedMapIteratorSyntheticFrontEnd::Update() {
283 m_pair_sp.reset();
284
285 ValueObjectSP valobj_sp = m_backend.GetSP();
286 if (!valobj_sp)
287 return lldb::ChildCacheState::eRefetch;
288
289 TargetSP target_sp(valobj_sp->GetTargetSP());
290
291 if (!target_sp)
292 return lldb::ChildCacheState::eRefetch;
293
294 // Get the unordered_map::iterator
295 // m_backend is an 'unordered_map::iterator', aka a
296 // '__hash_map_iterator<__hash_table::iterator>'
297 //
298 // __hash_map_iterator::__i_ is a __hash_table::iterator (aka
299 // __hash_iterator<__node_pointer>)
300 auto hash_iter_sp = valobj_sp->GetChildMemberWithName("__i_");
301 if (!hash_iter_sp)
302 return lldb::ChildCacheState::eRefetch;
303
304 // Type is '__hash_iterator<__node_pointer>'
305 auto hash_iter_type = hash_iter_sp->GetCompilerType();
306 if (!hash_iter_type.IsValid())
307 return lldb::ChildCacheState::eRefetch;
308
309 // Type is '__node_pointer'
310 auto node_pointer_type = hash_iter_type.GetTypeTemplateArgument(0);
311 if (!node_pointer_type.IsValid())
312 return lldb::ChildCacheState::eRefetch;
313
314 // Cast the __hash_iterator to a __node_pointer (which stores our key/value
315 // pair)
316 auto hash_node_sp = hash_iter_sp->Cast(node_pointer_type);
317 if (!hash_node_sp)
318 return lldb::ChildCacheState::eRefetch;
319
320 auto key_value_sp = hash_node_sp->GetChildMemberWithName("__value_");
321 if (!key_value_sp) {
322 // clang-format off
323 // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
324 // anonymous union.
325 // Child 0: __hash_node_base base class
326 // Child 1: __hash_
327 // Child 2: anonymous union
328 // clang-format on
329 auto anon_union_sp = hash_node_sp->GetChildAtIndex(2);
330 if (!anon_union_sp)
331 return lldb::ChildCacheState::eRefetch;
332
333 key_value_sp = anon_union_sp->GetChildMemberWithName("__value_");
334 if (!key_value_sp)
335 return lldb::ChildCacheState::eRefetch;
336 }
337
338 // Create the synthetic child, which is a pair where the key and value can be
339 // retrieved by querying the synthetic frontend for
340 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
341 // respectively.
342 //
343 // std::unordered_map stores the actual key/value pair in
344 // __hash_value_type::__cc_ (or previously __cc).
345 auto potential_child_sp = key_value_sp->Clone(ConstString("pair"));
346 if (potential_child_sp)
347 if (potential_child_sp->GetNumChildrenIgnoringErrors() == 1)
348 if (auto child0_sp = potential_child_sp->GetChildAtIndex(0);
349 child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc")
350 potential_child_sp = child0_sp->Clone(ConstString("pair"));
351
352 m_pair_sp = potential_child_sp;
353
354 return lldb::ChildCacheState::eRefetch;
355 }
356
357 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()358 LibCxxUnorderedMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
359 return 2;
360 }
361
362 lldb::ValueObjectSP lldb_private::formatters::
GetChildAtIndex(uint32_t idx)363 LibCxxUnorderedMapIteratorSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
364 if (m_pair_sp)
365 return m_pair_sp->GetChildAtIndex(idx);
366 return lldb::ValueObjectSP();
367 }
368
369 bool lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
MightHaveChildren()370 MightHaveChildren() {
371 return true;
372 }
373
374 size_t lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)375 GetIndexOfChildWithName(ConstString name) {
376 if (name == "first")
377 return 0;
378 if (name == "second")
379 return 1;
380 return UINT32_MAX;
381 }
382
383 SyntheticChildrenFrontEnd *
LibCxxUnorderedMapIteratorSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)384 lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEndCreator(
385 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
386 return (valobj_sp ? new LibCxxUnorderedMapIteratorSyntheticFrontEnd(valobj_sp)
387 : nullptr);
388 }
389