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