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/DataFormatters/FormattersHelpers.h"
13#include "lldb/Target/Target.h"
14#include "lldb/Utility/ConstString.h"
15#include "lldb/Utility/DataBufferHeap.h"
16#include "lldb/Utility/Endian.h"
17#include "lldb/Utility/Status.h"
18#include "lldb/Utility/Stream.h"
19#include "lldb/ValueObject/ValueObject.h"
20#include "lldb/ValueObject/ValueObjectConstResult.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/Support/Error.h"
23
24using namespace lldb;
25using namespace lldb_private;
26using namespace lldb_private::formatters;
27
28namespace lldb_private {
29namespace formatters {
30class LibcxxStdUnorderedMapSyntheticFrontEnd
31 : public SyntheticChildrenFrontEnd {
32public:
33 LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
34
35 ~LibcxxStdUnorderedMapSyntheticFrontEnd() override = default;
36
37 llvm::Expected<uint32_t> CalculateNumChildren() override;
38
39 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
40
41 lldb::ChildCacheState Update() override;
42
43 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override;
44
45private:
46 CompilerType GetNodeType();
47 CompilerType GetElementType(CompilerType table_type);
48 llvm::Expected<size_t> CalculateNumChildrenImpl(ValueObject &table);
49
50 CompilerType m_element_type;
51 CompilerType m_node_type;
52 ValueObject *m_tree = nullptr;
53 size_t m_num_elements = 0;
54 ValueObject *m_next_element = nullptr;
55 std::vector<std::pair<ValueObject *, uint64_t>> m_elements_cache;
56};
57
58class LibCxxUnorderedMapIteratorSyntheticFrontEnd
59 : public SyntheticChildrenFrontEnd {
60public:
61 LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
62
63 ~LibCxxUnorderedMapIteratorSyntheticFrontEnd() override = default;
64
65 llvm::Expected<uint32_t> CalculateNumChildren() override;
66
67 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
68
69 lldb::ChildCacheState Update() override;
70
71 llvm::Expected<size_t> GetIndexOfChildWithName(ConstString name) override;
72
73private:
74 lldb::ValueObjectSP m_pair_sp; ///< ValueObject for the key/value pair
75 ///< that the iterator currently points
76 ///< to.
77};
78
79} // namespace formatters
80} // namespace lldb_private
81
82lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
83 LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
84 : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(),
85 m_elements_cache() {
86 if (valobj_sp)
87 Update();
88}
89
90llvm::Expected<uint32_t> lldb_private::formatters::
91 LibcxxStdUnorderedMapSyntheticFrontEnd::CalculateNumChildren() {
92 return m_num_elements;
93}
94
95static bool isUnorderedMap(ConstString type_name) {
96 return isStdTemplate(type_name, type: "unordered_map") ||
97 isStdTemplate(type_name, type: "unordered_multimap");
98}
99
100CompilerType lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
101 GetElementType(CompilerType table_type) {
102 auto element_type =
103 table_type.GetDirectNestedTypeWithName(name: "value_type").GetTypedefedType();
104
105 // In newer unordered_map layouts, the std::pair element type isn't wrapped
106 // in any helper types. So return it directly.
107 if (isStdTemplate(type_name: element_type.GetTypeName(), type: "pair"))
108 return element_type;
109
110 // This synthetic provider is used for both unordered_(multi)map and
111 // unordered_(multi)set. For older unordered_map layouts, the element type has
112 // an additional type layer, an internal struct (`__hash_value_type`) that
113 // wraps a std::pair. Peel away the internal wrapper type - whose structure is
114 // of no value to users, to expose the std::pair. This matches the structure
115 // returned by the std::map synthetic provider.
116 if (isUnorderedMap(type_name: m_backend.GetCompilerType()
117 .GetNonReferenceType()
118 .GetCanonicalType()
119 .GetTypeName())) {
120 std::string name;
121 CompilerType field_type =
122 element_type.GetFieldAtIndex(idx: 0, name, bit_offset_ptr: nullptr, bitfield_bit_size_ptr: nullptr, is_bitfield_ptr: nullptr);
123 CompilerType actual_type = field_type.GetTypedefedType();
124 if (isStdTemplate(type_name: actual_type.GetTypeName(), type: "pair"))
125 return actual_type;
126 }
127
128 return element_type;
129}
130
131CompilerType lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
132 GetNodeType() {
133 auto table_sp = m_backend.GetChildMemberWithName(name: "__table_");
134 if (!table_sp)
135 return {};
136
137 auto [node_sp, is_compressed_pair] = GetValueOrOldCompressedPair(
138 obj&: *table_sp, /*anon_struct_idx=*/1, child_name: "__first_node_", compressed_pair_name: "__p1_");
139 if (is_compressed_pair)
140 node_sp = GetFirstValueOfLibCXXCompressedPair(pair&: *node_sp);
141
142 if (!node_sp)
143 return {};
144
145 return node_sp->GetCompilerType().GetTypeTemplateArgument(idx: 0).GetPointeeType();
146}
147
148lldb::ValueObjectSP lldb_private::formatters::
149 LibcxxStdUnorderedMapSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
150 if (idx >= CalculateNumChildrenIgnoringErrors())
151 return lldb::ValueObjectSP();
152 if (m_tree == nullptr)
153 return lldb::ValueObjectSP();
154
155 while (idx >= m_elements_cache.size()) {
156 if (m_next_element == nullptr)
157 return lldb::ValueObjectSP();
158
159 Status error;
160 ValueObjectSP node_sp = m_next_element->Dereference(error);
161 if (!node_sp || error.Fail())
162 return lldb::ValueObjectSP();
163
164 ValueObjectSP value_sp = node_sp->GetChildMemberWithName(name: "__value_");
165 ValueObjectSP hash_sp = node_sp->GetChildMemberWithName(name: "__hash_");
166 if (!hash_sp || !value_sp) {
167 node_sp = m_next_element->Cast(compiler_type: m_node_type.GetPointerType())
168 ->Dereference(error);
169 if (!node_sp || error.Fail())
170 return nullptr;
171
172 hash_sp = node_sp->GetChildMemberWithName(name: "__hash_");
173 if (!hash_sp)
174 return nullptr;
175
176 value_sp = node_sp->GetChildMemberWithName(name: "__value_");
177 if (!value_sp) {
178 // clang-format off
179 // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
180 // anonymous union.
181 // Child 0: __hash_node_base base class
182 // Child 1: __hash_
183 // Child 2: anonymous union
184 // clang-format on
185 auto anon_union_sp = node_sp->GetChildAtIndex(idx: 2);
186 if (!anon_union_sp)
187 return nullptr;
188
189 value_sp = anon_union_sp->GetChildMemberWithName(name: "__value_");
190 if (!value_sp)
191 return nullptr;
192 }
193 }
194 m_elements_cache.push_back(
195 x: {value_sp.get(), hash_sp->GetValueAsUnsigned(fail_value: 0)});
196 m_next_element = node_sp->GetChildMemberWithName(name: "__next_").get();
197 if (!m_next_element || m_next_element->GetValueAsUnsigned(fail_value: 0) == 0)
198 m_next_element = nullptr;
199 }
200
201 std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx];
202 if (!val_hash.first)
203 return lldb::ValueObjectSP();
204 StreamString stream;
205 stream.Printf(format: "[%" PRIu64 "]", (uint64_t)idx);
206 DataExtractor data;
207 Status error;
208 val_hash.first->GetData(data, error);
209 if (error.Fail())
210 return lldb::ValueObjectSP();
211 const bool thread_and_frame_only_if_stopped = true;
212 ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock(
213 thread_and_frame_only_if_stopped);
214 return CreateValueObjectFromData(name: stream.GetString(), data, exe_ctx,
215 type: m_element_type);
216}
217
218llvm::Expected<size_t>
219lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
220 CalculateNumChildrenImpl(ValueObject &table) {
221 auto [size_sp, is_compressed_pair] = GetValueOrOldCompressedPair(
222 obj&: table, /*anon_struct_idx=*/2, child_name: "__size_", compressed_pair_name: "__p2_");
223 if (!is_compressed_pair && size_sp)
224 return size_sp->GetValueAsUnsigned(fail_value: 0);
225
226 if (!is_compressed_pair)
227 return llvm::createStringError(Fmt: "Unsupported std::unordered_map layout.");
228
229 ValueObjectSP num_elements_sp = GetFirstValueOfLibCXXCompressedPair(pair&: *size_sp);
230
231 if (!num_elements_sp)
232 return llvm::createStringError(
233 Fmt: "Unexpected std::unordered_map layout: failed to retrieve first member "
234 "in old __compressed_pair layout.");
235
236 return num_elements_sp->GetValueAsUnsigned(fail_value: 0);
237}
238
239static ValueObjectSP GetTreePointer(ValueObject &table) {
240 auto [tree_sp, is_compressed_pair] = GetValueOrOldCompressedPair(
241 obj&: table, /*anon_struct_idx=*/1, child_name: "__first_node_", compressed_pair_name: "__p1_");
242 if (is_compressed_pair)
243 tree_sp = GetFirstValueOfLibCXXCompressedPair(pair&: *tree_sp);
244
245 if (!tree_sp)
246 return nullptr;
247
248 return tree_sp->GetChildMemberWithName(name: "__next_");
249}
250
251lldb::ChildCacheState
252lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::Update() {
253 m_num_elements = 0;
254 m_next_element = nullptr;
255 m_elements_cache.clear();
256 ValueObjectSP table_sp = m_backend.GetChildMemberWithName(name: "__table_");
257 if (!table_sp)
258 return lldb::ChildCacheState::eRefetch;
259
260 m_node_type = GetNodeType();
261 if (!m_node_type)
262 return lldb::ChildCacheState::eRefetch;
263
264 m_element_type = GetElementType(table_type: table_sp->GetCompilerType());
265 if (!m_element_type)
266 return lldb::ChildCacheState::eRefetch;
267
268 ValueObjectSP tree_sp = GetTreePointer(table&: *table_sp);
269 if (!tree_sp)
270 return lldb::ChildCacheState::eRefetch;
271
272 m_tree = tree_sp.get();
273
274 if (auto num_elems_or_err = CalculateNumChildrenImpl(table&: *table_sp))
275 m_num_elements = *num_elems_or_err;
276 else {
277 LLDB_LOG_ERRORV(GetLog(LLDBLog::DataFormatters),
278 num_elems_or_err.takeError(), "{0}");
279 return lldb::ChildCacheState::eRefetch;
280 }
281
282 if (m_num_elements > 0)
283 m_next_element = m_tree;
284
285 return lldb::ChildCacheState::eRefetch;
286}
287
288llvm::Expected<size_t>
289lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
290 GetIndexOfChildWithName(ConstString name) {
291 auto optional_idx = formatters::ExtractIndexFromString(item_name: name.GetCString());
292 if (!optional_idx) {
293 return llvm::createStringError(Fmt: "Type has no child named '%s'",
294 Vals: name.AsCString());
295 }
296 return *optional_idx;
297}
298
299SyntheticChildrenFrontEnd *
300lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
301 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
302 return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
303 : nullptr);
304}
305
306lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
307 LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
308 : SyntheticChildrenFrontEnd(*valobj_sp) {
309 if (valobj_sp)
310 Update();
311}
312
313lldb::ChildCacheState lldb_private::formatters::
314 LibCxxUnorderedMapIteratorSyntheticFrontEnd::Update() {
315 m_pair_sp.reset();
316
317 ValueObjectSP valobj_sp = m_backend.GetSP();
318 if (!valobj_sp)
319 return lldb::ChildCacheState::eRefetch;
320
321 TargetSP target_sp(valobj_sp->GetTargetSP());
322
323 if (!target_sp)
324 return lldb::ChildCacheState::eRefetch;
325
326 // Get the unordered_map::iterator
327 // m_backend is an 'unordered_map::iterator', aka a
328 // '__hash_map_iterator<__hash_table::iterator>'
329 //
330 // __hash_map_iterator::__i_ is a __hash_table::iterator (aka
331 // __hash_iterator<__node_pointer>)
332 auto hash_iter_sp = valobj_sp->GetChildMemberWithName(name: "__i_");
333 if (!hash_iter_sp)
334 return lldb::ChildCacheState::eRefetch;
335
336 // Type is '__hash_iterator<__node_pointer>'
337 auto hash_iter_type = hash_iter_sp->GetCompilerType();
338 if (!hash_iter_type.IsValid())
339 return lldb::ChildCacheState::eRefetch;
340
341 // Type is '__node_pointer'
342 auto node_pointer_type = hash_iter_type.GetTypeTemplateArgument(idx: 0);
343 if (!node_pointer_type.IsValid())
344 return lldb::ChildCacheState::eRefetch;
345
346 // Cast the __hash_iterator to a __node_pointer (which stores our key/value
347 // pair)
348 auto hash_node_sp = hash_iter_sp->Cast(compiler_type: node_pointer_type);
349 if (!hash_node_sp)
350 return lldb::ChildCacheState::eRefetch;
351
352 auto key_value_sp = hash_node_sp->GetChildMemberWithName(name: "__value_");
353 if (!key_value_sp) {
354 // clang-format off
355 // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
356 // anonymous union.
357 // Child 0: __hash_node_base base class
358 // Child 1: __hash_
359 // Child 2: anonymous union
360 // clang-format on
361 auto anon_union_sp = hash_node_sp->GetChildAtIndex(idx: 2);
362 if (!anon_union_sp)
363 return lldb::ChildCacheState::eRefetch;
364
365 key_value_sp = anon_union_sp->GetChildMemberWithName(name: "__value_");
366 if (!key_value_sp)
367 return lldb::ChildCacheState::eRefetch;
368 }
369
370 // Create the synthetic child, which is a pair where the key and value can be
371 // retrieved by querying the synthetic frontend for
372 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
373 // respectively.
374 //
375 // std::unordered_map stores the actual key/value pair in
376 // __hash_value_type::__cc_ (or previously __cc).
377 auto potential_child_sp = key_value_sp->Clone(new_name: ConstString("pair"));
378 if (potential_child_sp)
379 if (potential_child_sp->GetNumChildrenIgnoringErrors() == 1)
380 if (auto child0_sp = potential_child_sp->GetChildAtIndex(idx: 0);
381 child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc")
382 potential_child_sp = child0_sp->Clone(new_name: ConstString("pair"));
383
384 m_pair_sp = potential_child_sp;
385
386 return lldb::ChildCacheState::eRefetch;
387}
388
389llvm::Expected<uint32_t> lldb_private::formatters::
390 LibCxxUnorderedMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
391 return 2;
392}
393
394lldb::ValueObjectSP lldb_private::formatters::
395 LibCxxUnorderedMapIteratorSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
396 if (m_pair_sp)
397 return m_pair_sp->GetChildAtIndex(idx);
398 return lldb::ValueObjectSP();
399}
400
401llvm::Expected<size_t>
402lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
403 GetIndexOfChildWithName(ConstString name) {
404 if (name == "first")
405 return 0;
406 if (name == "second")
407 return 1;
408 return llvm::createStringError(Fmt: "Type has no child named '%s'",
409 Vals: name.AsCString());
410}
411
412SyntheticChildrenFrontEnd *
413lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEndCreator(
414 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
415 return (valobj_sp ? new LibCxxUnorderedMapIteratorSyntheticFrontEnd(valobj_sp)
416 : nullptr);
417}
418

source code of lldb/source/Plugins/Language/CPlusPlus/LibCxxUnorderedMap.cpp