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 = table_type.GetTypedefedType().GetTypeTemplateArgument(idx: 0);
103
104 // This synthetic provider is used for both unordered_(multi)map and
105 // unordered_(multi)set. For unordered_map, the element type has an
106 // additional type layer, an internal struct (`__hash_value_type`)
107 // that wraps a std::pair. Peel away the internal wrapper type - whose
108 // structure is of no value to users, to expose the std::pair. This
109 // matches the structure returned by the std::map synthetic provider.
110 if (isUnorderedMap(
111 type_name: m_backend.GetCompilerType().GetCanonicalType().GetTypeName())) {
112 std::string name;
113 CompilerType field_type =
114 element_type.GetFieldAtIndex(idx: 0, name, bit_offset_ptr: nullptr, bitfield_bit_size_ptr: nullptr, is_bitfield_ptr: nullptr);
115 CompilerType actual_type = field_type.GetTypedefedType();
116 if (isStdTemplate(type_name: actual_type.GetTypeName(), type: "pair"))
117 return actual_type;
118 }
119
120 return element_type;
121}
122
123CompilerType lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
124 GetNodeType() {
125 auto node_sp = m_backend.GetChildAtNamePath(names: {"__table_", "__first_node_"});
126
127 if (!node_sp) {
128 auto p1_sp = m_backend.GetChildAtNamePath(names: {"__table_", "__p1_"});
129 if (!p1_sp)
130 return {};
131
132 if (!isOldCompressedPairLayout(pair_obj&: *p1_sp))
133 return {};
134
135 node_sp = GetFirstValueOfLibCXXCompressedPair(pair&: *p1_sp);
136 if (!node_sp)
137 return {};
138 }
139
140 assert(node_sp);
141
142 return node_sp->GetCompilerType().GetTypeTemplateArgument(idx: 0).GetPointeeType();
143}
144
145lldb::ValueObjectSP lldb_private::formatters::
146 LibcxxStdUnorderedMapSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
147 if (idx >= CalculateNumChildrenIgnoringErrors())
148 return lldb::ValueObjectSP();
149 if (m_tree == nullptr)
150 return lldb::ValueObjectSP();
151
152 while (idx >= m_elements_cache.size()) {
153 if (m_next_element == nullptr)
154 return lldb::ValueObjectSP();
155
156 Status error;
157 ValueObjectSP node_sp = m_next_element->Dereference(error);
158 if (!node_sp || error.Fail())
159 return lldb::ValueObjectSP();
160
161 ValueObjectSP value_sp = node_sp->GetChildMemberWithName(name: "__value_");
162 ValueObjectSP hash_sp = node_sp->GetChildMemberWithName(name: "__hash_");
163 if (!hash_sp || !value_sp) {
164 node_sp = m_next_element->Cast(compiler_type: m_node_type.GetPointerType())
165 ->Dereference(error);
166 if (!node_sp || error.Fail())
167 return nullptr;
168
169 hash_sp = node_sp->GetChildMemberWithName(name: "__hash_");
170 if (!hash_sp)
171 return nullptr;
172
173 value_sp = node_sp->GetChildMemberWithName(name: "__value_");
174 if (!value_sp) {
175 // clang-format off
176 // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
177 // anonymous union.
178 // Child 0: __hash_node_base base class
179 // Child 1: __hash_
180 // Child 2: anonymous union
181 // clang-format on
182 auto anon_union_sp = node_sp->GetChildAtIndex(idx: 2);
183 if (!anon_union_sp)
184 return nullptr;
185
186 value_sp = anon_union_sp->GetChildMemberWithName(name: "__value_");
187 if (!value_sp)
188 return nullptr;
189 }
190 }
191 m_elements_cache.push_back(
192 x: {value_sp.get(), hash_sp->GetValueAsUnsigned(fail_value: 0)});
193 m_next_element = node_sp->GetChildMemberWithName(name: "__next_").get();
194 if (!m_next_element || m_next_element->GetValueAsUnsigned(fail_value: 0) == 0)
195 m_next_element = nullptr;
196 }
197
198 std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx];
199 if (!val_hash.first)
200 return lldb::ValueObjectSP();
201 StreamString stream;
202 stream.Printf(format: "[%" PRIu64 "]", (uint64_t)idx);
203 DataExtractor data;
204 Status error;
205 val_hash.first->GetData(data, error);
206 if (error.Fail())
207 return lldb::ValueObjectSP();
208 const bool thread_and_frame_only_if_stopped = true;
209 ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock(
210 thread_and_frame_only_if_stopped);
211 return CreateValueObjectFromData(name: stream.GetString(), data, exe_ctx,
212 type: m_element_type);
213}
214
215llvm::Expected<size_t>
216lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
217 CalculateNumChildrenImpl(ValueObject &table) {
218 if (auto size_sp = table.GetChildMemberWithName(name: "__size_"))
219 return size_sp->GetValueAsUnsigned(fail_value: 0);
220
221 ValueObjectSP p2_sp = table.GetChildMemberWithName(name: "__p2_");
222 if (!p2_sp)
223 return llvm::createStringError(
224 Fmt: "Unexpected std::unordered_map layout: __p2_ member not found.");
225
226 if (!isOldCompressedPairLayout(pair_obj&: *p2_sp))
227 return llvm::createStringError(Fmt: "Unexpected std::unordered_map layout: old "
228 "__compressed_pair layout not found.");
229
230 ValueObjectSP num_elements_sp = GetFirstValueOfLibCXXCompressedPair(pair&: *p2_sp);
231
232 if (!num_elements_sp)
233 return llvm::createStringError(
234 Fmt: "Unexpected std::unordered_map layout: failed to retrieve first member "
235 "in old __compressed_pair layout.");
236
237 return num_elements_sp->GetValueAsUnsigned(fail_value: 0);
238}
239
240static ValueObjectSP GetTreePointer(ValueObject &table) {
241 ValueObjectSP tree_sp = table.GetChildMemberWithName(name: "__first_node_");
242 if (!tree_sp) {
243 ValueObjectSP p1_sp = table.GetChildMemberWithName(name: "__p1_");
244 if (!p1_sp)
245 return nullptr;
246
247 if (!isOldCompressedPairLayout(pair_obj&: *p1_sp))
248 return nullptr;
249
250 tree_sp = GetFirstValueOfLibCXXCompressedPair(pair&: *p1_sp);
251 if (!tree_sp)
252 return nullptr;
253 }
254
255 return tree_sp->GetChildMemberWithName(name: "__next_");
256}
257
258lldb::ChildCacheState
259lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::Update() {
260 m_num_elements = 0;
261 m_next_element = nullptr;
262 m_elements_cache.clear();
263 ValueObjectSP table_sp = m_backend.GetChildMemberWithName(name: "__table_");
264 if (!table_sp)
265 return lldb::ChildCacheState::eRefetch;
266
267 m_node_type = GetNodeType();
268 if (!m_node_type)
269 return lldb::ChildCacheState::eRefetch;
270
271 m_element_type = GetElementType(table_type: table_sp->GetCompilerType());
272 if (!m_element_type)
273 return lldb::ChildCacheState::eRefetch;
274
275 ValueObjectSP tree_sp = GetTreePointer(table&: *table_sp);
276 if (!tree_sp)
277 return lldb::ChildCacheState::eRefetch;
278
279 m_tree = tree_sp.get();
280
281 if (auto num_elems_or_err = CalculateNumChildrenImpl(table&: *table_sp))
282 m_num_elements = *num_elems_or_err;
283 else {
284 LLDB_LOG_ERRORV(GetLog(LLDBLog::DataFormatters),
285 num_elems_or_err.takeError(), "{0}");
286 return lldb::ChildCacheState::eRefetch;
287 }
288
289 if (m_num_elements > 0)
290 m_next_element = m_tree;
291
292 return lldb::ChildCacheState::eRefetch;
293}
294
295llvm::Expected<size_t>
296lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
297 GetIndexOfChildWithName(ConstString name) {
298 auto optional_idx = formatters::ExtractIndexFromString(item_name: name.GetCString());
299 if (!optional_idx) {
300 return llvm::createStringError(Fmt: "Type has no child named '%s'",
301 Vals: name.AsCString());
302 }
303 return *optional_idx;
304}
305
306SyntheticChildrenFrontEnd *
307lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
308 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
309 return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
310 : nullptr);
311}
312
313lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
314 LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
315 : SyntheticChildrenFrontEnd(*valobj_sp) {
316 if (valobj_sp)
317 Update();
318}
319
320lldb::ChildCacheState lldb_private::formatters::
321 LibCxxUnorderedMapIteratorSyntheticFrontEnd::Update() {
322 m_pair_sp.reset();
323
324 ValueObjectSP valobj_sp = m_backend.GetSP();
325 if (!valobj_sp)
326 return lldb::ChildCacheState::eRefetch;
327
328 TargetSP target_sp(valobj_sp->GetTargetSP());
329
330 if (!target_sp)
331 return lldb::ChildCacheState::eRefetch;
332
333 // Get the unordered_map::iterator
334 // m_backend is an 'unordered_map::iterator', aka a
335 // '__hash_map_iterator<__hash_table::iterator>'
336 //
337 // __hash_map_iterator::__i_ is a __hash_table::iterator (aka
338 // __hash_iterator<__node_pointer>)
339 auto hash_iter_sp = valobj_sp->GetChildMemberWithName(name: "__i_");
340 if (!hash_iter_sp)
341 return lldb::ChildCacheState::eRefetch;
342
343 // Type is '__hash_iterator<__node_pointer>'
344 auto hash_iter_type = hash_iter_sp->GetCompilerType();
345 if (!hash_iter_type.IsValid())
346 return lldb::ChildCacheState::eRefetch;
347
348 // Type is '__node_pointer'
349 auto node_pointer_type = hash_iter_type.GetTypeTemplateArgument(idx: 0);
350 if (!node_pointer_type.IsValid())
351 return lldb::ChildCacheState::eRefetch;
352
353 // Cast the __hash_iterator to a __node_pointer (which stores our key/value
354 // pair)
355 auto hash_node_sp = hash_iter_sp->Cast(compiler_type: node_pointer_type);
356 if (!hash_node_sp)
357 return lldb::ChildCacheState::eRefetch;
358
359 auto key_value_sp = hash_node_sp->GetChildMemberWithName(name: "__value_");
360 if (!key_value_sp) {
361 // clang-format off
362 // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
363 // anonymous union.
364 // Child 0: __hash_node_base base class
365 // Child 1: __hash_
366 // Child 2: anonymous union
367 // clang-format on
368 auto anon_union_sp = hash_node_sp->GetChildAtIndex(idx: 2);
369 if (!anon_union_sp)
370 return lldb::ChildCacheState::eRefetch;
371
372 key_value_sp = anon_union_sp->GetChildMemberWithName(name: "__value_");
373 if (!key_value_sp)
374 return lldb::ChildCacheState::eRefetch;
375 }
376
377 // Create the synthetic child, which is a pair where the key and value can be
378 // retrieved by querying the synthetic frontend for
379 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
380 // respectively.
381 //
382 // std::unordered_map stores the actual key/value pair in
383 // __hash_value_type::__cc_ (or previously __cc).
384 auto potential_child_sp = key_value_sp->Clone(new_name: ConstString("pair"));
385 if (potential_child_sp)
386 if (potential_child_sp->GetNumChildrenIgnoringErrors() == 1)
387 if (auto child0_sp = potential_child_sp->GetChildAtIndex(idx: 0);
388 child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc")
389 potential_child_sp = child0_sp->Clone(new_name: ConstString("pair"));
390
391 m_pair_sp = potential_child_sp;
392
393 return lldb::ChildCacheState::eRefetch;
394}
395
396llvm::Expected<uint32_t> lldb_private::formatters::
397 LibCxxUnorderedMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
398 return 2;
399}
400
401lldb::ValueObjectSP lldb_private::formatters::
402 LibCxxUnorderedMapIteratorSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
403 if (m_pair_sp)
404 return m_pair_sp->GetChildAtIndex(idx);
405 return lldb::ValueObjectSP();
406}
407
408llvm::Expected<size_t>
409lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
410 GetIndexOfChildWithName(ConstString name) {
411 if (name == "first")
412 return 0;
413 if (name == "second")
414 return 1;
415 return llvm::createStringError(Fmt: "Type has no child named '%s'",
416 Vals: name.AsCString());
417}
418
419SyntheticChildrenFrontEnd *
420lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEndCreator(
421 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
422 return (valobj_sp ? new LibCxxUnorderedMapIteratorSyntheticFrontEnd(valobj_sp)
423 : nullptr);
424}
425

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