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 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
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 } // namespace formatters
55 } // namespace lldb_private
56
57 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)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
65 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
CalculateNumChildren()66 CalculateNumChildren() {
67 return m_num_elements;
68 }
69
consumeInlineNamespace(llvm::StringRef & name)70 static 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
isStdTemplate(ConstString type_name,llvm::StringRef type)82 static 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
isUnorderedMap(ConstString type_name)90 static bool isUnorderedMap(ConstString type_name) {
91 return isStdTemplate(type_name, "unordered_map") ||
92 isStdTemplate(type_name, "unordered_multimap");
93 }
94
95 lldb::ValueObjectSP lldb_private::formatters::
GetChildAtIndex(size_t idx)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
211 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
Update()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
255 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
MightHaveChildren()256 MightHaveChildren() {
257 return true;
258 }
259
260 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
GetIndexOfChildWithName(ConstString name)261 GetIndexOfChildWithName(ConstString name) {
262 return ExtractIndexFromString(name.GetCString());
263 }
264
265 SyntheticChildrenFrontEnd *
LibcxxStdUnorderedMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)266 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
267 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
268 return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
269 : nullptr);
270 }
271