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