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