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
24 using namespace lldb;
25 using namespace lldb_private;
26 using namespace lldb_private::formatters;
27
28 namespace lldb_private {
29 namespace formatters {
30 class LibcxxStdUnorderedMapSyntheticFrontEnd
31 : public SyntheticChildrenFrontEnd {
32 public:
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
45 private:
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
58 class LibCxxUnorderedMapIteratorSyntheticFrontEnd
59 : public SyntheticChildrenFrontEnd {
60 public:
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
73 private:
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
82 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)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
90 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()91 LibcxxStdUnorderedMapSyntheticFrontEnd::CalculateNumChildren() {
92 return m_num_elements;
93 }
94
isUnorderedMap(ConstString type_name)95 static bool isUnorderedMap(ConstString type_name) {
96 return isStdTemplate(type_name, "unordered_map") ||
97 isStdTemplate(type_name, "unordered_multimap");
98 }
99
100 CompilerType lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
GetElementType(CompilerType table_type)101 GetElementType(CompilerType table_type) {
102 auto element_type =
103 table_type.GetDirectNestedTypeWithName("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(element_type.GetTypeName(), "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(m_backend.GetCompilerType()
117 .GetNonReferenceType()
118 .GetCanonicalType()
119 .GetTypeName())) {
120 std::string name;
121 CompilerType field_type =
122 element_type.GetFieldAtIndex(0, name, nullptr, nullptr, nullptr);
123 CompilerType actual_type = field_type.GetTypedefedType();
124 if (isStdTemplate(actual_type.GetTypeName(), "pair"))
125 return actual_type;
126 }
127
128 return element_type;
129 }
130
131 CompilerType lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
GetNodeType()132 GetNodeType() {
133 auto table_sp = m_backend.GetChildMemberWithName("__table_");
134 if (!table_sp)
135 return {};
136
137 auto [node_sp, is_compressed_pair] = GetValueOrOldCompressedPair(
138 *table_sp, /*anon_struct_idx=*/1, "__first_node_", "__p1_");
139 if (is_compressed_pair)
140 node_sp = GetFirstValueOfLibCXXCompressedPair(*node_sp);
141
142 if (!node_sp)
143 return {};
144
145 return node_sp->GetCompilerType().GetTypeTemplateArgument(0).GetPointeeType();
146 }
147
148 lldb::ValueObjectSP lldb_private::formatters::
GetChildAtIndex(uint32_t idx)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("__value_");
165 ValueObjectSP hash_sp = node_sp->GetChildMemberWithName("__hash_");
166 if (!hash_sp || !value_sp) {
167 node_sp = m_next_element->Cast(m_node_type.GetPointerType())
168 ->Dereference(error);
169 if (!node_sp || error.Fail())
170 return nullptr;
171
172 hash_sp = node_sp->GetChildMemberWithName("__hash_");
173 if (!hash_sp)
174 return nullptr;
175
176 value_sp = node_sp->GetChildMemberWithName("__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(2);
186 if (!anon_union_sp)
187 return nullptr;
188
189 value_sp = anon_union_sp->GetChildMemberWithName("__value_");
190 if (!value_sp)
191 return nullptr;
192 }
193 }
194 m_elements_cache.push_back(
195 {value_sp.get(), hash_sp->GetValueAsUnsigned(0)});
196 m_next_element = node_sp->GetChildMemberWithName("__next_").get();
197 if (!m_next_element || m_next_element->GetValueAsUnsigned(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("[%" 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(stream.GetString(), data, exe_ctx,
215 m_element_type);
216 }
217
218 llvm::Expected<size_t>
219 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
CalculateNumChildrenImpl(ValueObject & table)220 CalculateNumChildrenImpl(ValueObject &table) {
221 auto [size_sp, is_compressed_pair] = GetValueOrOldCompressedPair(
222 table, /*anon_struct_idx=*/2, "__size_", "__p2_");
223 if (!is_compressed_pair && size_sp)
224 return size_sp->GetValueAsUnsigned(0);
225
226 if (!is_compressed_pair)
227 return llvm::createStringError("Unsupported std::unordered_map layout.");
228
229 ValueObjectSP num_elements_sp = GetFirstValueOfLibCXXCompressedPair(*size_sp);
230
231 if (!num_elements_sp)
232 return llvm::createStringError(
233 "Unexpected std::unordered_map layout: failed to retrieve first member "
234 "in old __compressed_pair layout.");
235
236 return num_elements_sp->GetValueAsUnsigned(0);
237 }
238
GetTreePointer(ValueObject & table)239 static ValueObjectSP GetTreePointer(ValueObject &table) {
240 auto [tree_sp, is_compressed_pair] = GetValueOrOldCompressedPair(
241 table, /*anon_struct_idx=*/1, "__first_node_", "__p1_");
242 if (is_compressed_pair)
243 tree_sp = GetFirstValueOfLibCXXCompressedPair(*tree_sp);
244
245 if (!tree_sp)
246 return nullptr;
247
248 return tree_sp->GetChildMemberWithName("__next_");
249 }
250
251 lldb::ChildCacheState
Update()252 lldb_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("__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_sp->GetCompilerType());
265 if (!m_element_type)
266 return lldb::ChildCacheState::eRefetch;
267
268 ValueObjectSP tree_sp = GetTreePointer(*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_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
288 llvm::Expected<size_t>
289 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)290 GetIndexOfChildWithName(ConstString name) {
291 auto optional_idx = formatters::ExtractIndexFromString(name.GetCString());
292 if (!optional_idx) {
293 return llvm::createStringError("Type has no child named '%s'",
294 name.AsCString());
295 }
296 return *optional_idx;
297 }
298
299 SyntheticChildrenFrontEnd *
LibcxxStdUnorderedMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)300 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
301 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
302 return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
303 : nullptr);
304 }
305
306 lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)307 LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
308 : SyntheticChildrenFrontEnd(*valobj_sp) {
309 if (valobj_sp)
310 Update();
311 }
312
313 lldb::ChildCacheState lldb_private::formatters::
Update()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("__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(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(node_pointer_type);
349 if (!hash_node_sp)
350 return lldb::ChildCacheState::eRefetch;
351
352 auto key_value_sp = hash_node_sp->GetChildMemberWithName("__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(2);
362 if (!anon_union_sp)
363 return lldb::ChildCacheState::eRefetch;
364
365 key_value_sp = anon_union_sp->GetChildMemberWithName("__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(ConstString("pair"));
378 if (potential_child_sp)
379 if (potential_child_sp->GetNumChildrenIgnoringErrors() == 1)
380 if (auto child0_sp = potential_child_sp->GetChildAtIndex(0);
381 child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc")
382 potential_child_sp = child0_sp->Clone(ConstString("pair"));
383
384 m_pair_sp = potential_child_sp;
385
386 return lldb::ChildCacheState::eRefetch;
387 }
388
389 llvm::Expected<uint32_t> lldb_private::formatters::
CalculateNumChildren()390 LibCxxUnorderedMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
391 return 2;
392 }
393
394 lldb::ValueObjectSP lldb_private::formatters::
GetChildAtIndex(uint32_t idx)395 LibCxxUnorderedMapIteratorSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
396 if (m_pair_sp)
397 return m_pair_sp->GetChildAtIndex(idx);
398 return lldb::ValueObjectSP();
399 }
400
401 llvm::Expected<size_t>
402 lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)403 GetIndexOfChildWithName(ConstString name) {
404 if (name == "first")
405 return 0;
406 if (name == "second")
407 return 1;
408 return llvm::createStringError("Type has no child named '%s'",
409 name.AsCString());
410 }
411
412 SyntheticChildrenFrontEnd *
LibCxxUnorderedMapIteratorSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)413 lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEndCreator(
414 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
415 return (valobj_sp ? new LibCxxUnorderedMapIteratorSyntheticFrontEnd(valobj_sp)
416 : nullptr);
417 }
418