1 //===-- LibCxxMap.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/DataBufferHeap.h" 17 #include "lldb/Utility/Endian.h" 18 #include "lldb/Utility/Status.h" 19 #include "lldb/Utility/Stream.h" 20 #include "lldb/lldb-enumerations.h" 21 #include "lldb/lldb-forward.h" 22 #include <cstdint> 23 #include <locale> 24 #include <optional> 25 26 using namespace lldb; 27 using namespace lldb_private; 28 using namespace lldb_private::formatters; 29 30 // The flattened layout of the std::__tree_iterator::__ptr_ looks 31 // as follows: 32 // 33 // The following shows the contiguous block of memory: 34 // 35 // +-----------------------------+ class __tree_end_node 36 // __ptr_ | pointer __left_; | 37 // +-----------------------------+ class __tree_node_base 38 // | pointer __right_; | 39 // | __parent_pointer __parent_; | 40 // | bool __is_black_; | 41 // +-----------------------------+ class __tree_node 42 // | __node_value_type __value_; | <<< our key/value pair 43 // +-----------------------------+ 44 // 45 // where __ptr_ has type __iter_pointer. 46 47 class MapEntry { 48 public: 49 MapEntry() = default; MapEntry(ValueObjectSP entry_sp)50 explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} MapEntry(ValueObject * entry)51 explicit MapEntry(ValueObject *entry) 52 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 53 left() const54 ValueObjectSP left() const { 55 if (!m_entry_sp) 56 return m_entry_sp; 57 return m_entry_sp->GetSyntheticChildAtOffset( 58 0, m_entry_sp->GetCompilerType(), true); 59 } 60 right() const61 ValueObjectSP right() const { 62 if (!m_entry_sp) 63 return m_entry_sp; 64 return m_entry_sp->GetSyntheticChildAtOffset( 65 m_entry_sp->GetProcessSP()->GetAddressByteSize(), 66 m_entry_sp->GetCompilerType(), true); 67 } 68 parent() const69 ValueObjectSP parent() const { 70 if (!m_entry_sp) 71 return m_entry_sp; 72 return m_entry_sp->GetSyntheticChildAtOffset( 73 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(), 74 m_entry_sp->GetCompilerType(), true); 75 } 76 value() const77 uint64_t value() const { 78 if (!m_entry_sp) 79 return 0; 80 return m_entry_sp->GetValueAsUnsigned(0); 81 } 82 error() const83 bool error() const { 84 if (!m_entry_sp) 85 return true; 86 return m_entry_sp->GetError().Fail(); 87 } 88 null() const89 bool null() const { return (value() == 0); } 90 GetEntry() const91 ValueObjectSP GetEntry() const { return m_entry_sp; } 92 SetEntry(ValueObjectSP entry)93 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } 94 operator ==(const MapEntry & rhs) const95 bool operator==(const MapEntry &rhs) const { 96 return (rhs.m_entry_sp.get() == m_entry_sp.get()); 97 } 98 99 private: 100 ValueObjectSP m_entry_sp; 101 }; 102 103 class MapIterator { 104 public: MapIterator(ValueObject * entry,size_t depth=0)105 MapIterator(ValueObject *entry, size_t depth = 0) 106 : m_entry(entry), m_max_depth(depth), m_error(false) {} 107 108 MapIterator() = default; 109 value()110 ValueObjectSP value() { return m_entry.GetEntry(); } 111 advance(size_t count)112 ValueObjectSP advance(size_t count) { 113 ValueObjectSP fail; 114 if (m_error) 115 return fail; 116 size_t steps = 0; 117 while (count > 0) { 118 next(); 119 count--, steps++; 120 if (m_error || m_entry.null() || (steps > m_max_depth)) 121 return fail; 122 } 123 return m_entry.GetEntry(); 124 } 125 126 private: 127 /// Mimicks libc++'s __tree_next algorithm, which libc++ uses 128 /// in its __tree_iteartor::operator++. next()129 void next() { 130 if (m_entry.null()) 131 return; 132 MapEntry right(m_entry.right()); 133 if (!right.null()) { 134 m_entry = tree_min(std::move(right)); 135 return; 136 } 137 size_t steps = 0; 138 while (!is_left_child(m_entry)) { 139 if (m_entry.error()) { 140 m_error = true; 141 return; 142 } 143 m_entry.SetEntry(m_entry.parent()); 144 steps++; 145 if (steps > m_max_depth) { 146 m_entry = MapEntry(); 147 return; 148 } 149 } 150 m_entry = MapEntry(m_entry.parent()); 151 } 152 153 /// Mimicks libc++'s __tree_min algorithm. tree_min(MapEntry x)154 MapEntry tree_min(MapEntry x) { 155 if (x.null()) 156 return MapEntry(); 157 MapEntry left(x.left()); 158 size_t steps = 0; 159 while (!left.null()) { 160 if (left.error()) { 161 m_error = true; 162 return MapEntry(); 163 } 164 x = left; 165 left.SetEntry(x.left()); 166 steps++; 167 if (steps > m_max_depth) 168 return MapEntry(); 169 } 170 return x; 171 } 172 is_left_child(const MapEntry & x)173 bool is_left_child(const MapEntry &x) { 174 if (x.null()) 175 return false; 176 MapEntry rhs(x.parent()); 177 rhs.SetEntry(rhs.left()); 178 return x.value() == rhs.value(); 179 } 180 181 MapEntry m_entry; 182 size_t m_max_depth = 0; 183 bool m_error = false; 184 }; 185 186 namespace lldb_private { 187 namespace formatters { 188 class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd { 189 public: 190 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); 191 192 ~LibcxxStdMapSyntheticFrontEnd() override = default; 193 194 llvm::Expected<uint32_t> CalculateNumChildren() override; 195 196 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override; 197 198 lldb::ChildCacheState Update() override; 199 200 bool MightHaveChildren() override; 201 202 size_t GetIndexOfChildWithName(ConstString name) override; 203 204 private: 205 /// Returns the ValueObject for the __tree_node type that 206 /// holds the key/value pair of the node at index \ref idx. 207 /// 208 /// \param[in] idx The child index that we're looking to get 209 /// the key/value pair for. 210 /// 211 /// \param[in] max_depth The maximum search depth after which 212 /// we stop trying to find the key/value 213 /// pair for. 214 /// 215 /// \returns On success, returns the ValueObjectSP corresponding 216 /// to the __tree_node's __value_ member (which holds 217 /// the key/value pair the formatter wants to display). 218 /// On failure, will return nullptr. 219 ValueObjectSP GetKeyValuePair(size_t idx, size_t max_depth); 220 221 ValueObject *m_tree = nullptr; 222 ValueObject *m_root_node = nullptr; 223 CompilerType m_node_ptr_type; 224 size_t m_count = UINT32_MAX; 225 std::map<size_t, MapIterator> m_iterators; 226 }; 227 228 class LibCxxMapIteratorSyntheticFrontEnd : public SyntheticChildrenFrontEnd { 229 public: 230 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); 231 232 llvm::Expected<uint32_t> CalculateNumChildren() override; 233 234 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override; 235 236 lldb::ChildCacheState Update() override; 237 238 bool MightHaveChildren() override; 239 240 size_t GetIndexOfChildWithName(ConstString name) override; 241 242 ~LibCxxMapIteratorSyntheticFrontEnd() override = default; 243 244 private: 245 ValueObjectSP m_pair_sp = nullptr; 246 }; 247 } // namespace formatters 248 } // namespace lldb_private 249 250 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)251 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) 252 : SyntheticChildrenFrontEnd(*valobj_sp) { 253 if (valobj_sp) 254 Update(); 255 } 256 257 llvm::Expected<uint32_t> lldb_private::formatters:: CalculateNumChildren()258 LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren() { 259 if (m_count != UINT32_MAX) 260 return m_count; 261 262 if (m_tree == nullptr) 263 return 0; 264 265 ValueObjectSP size_node(m_tree->GetChildMemberWithName("__pair3_")); 266 if (!size_node) 267 return 0; 268 269 size_node = GetFirstValueOfLibCXXCompressedPair(*size_node); 270 271 if (!size_node) 272 return 0; 273 274 m_count = size_node->GetValueAsUnsigned(0); 275 return m_count; 276 } 277 278 ValueObjectSP GetKeyValuePair(size_t idx,size_t max_depth)279 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetKeyValuePair( 280 size_t idx, size_t max_depth) { 281 MapIterator iterator(m_root_node, max_depth); 282 283 size_t advance_by = idx; 284 if (idx > 0) { 285 // If we have already created the iterator for the previous 286 // index, we can start from there and advance by 1. 287 auto cached_iterator = m_iterators.find(idx - 1); 288 if (cached_iterator != m_iterators.end()) { 289 iterator = cached_iterator->second; 290 advance_by = 1; 291 } 292 } 293 294 ValueObjectSP iterated_sp(iterator.advance(advance_by)); 295 if (!iterated_sp) 296 // this tree is garbage - stop 297 return nullptr; 298 299 if (!m_node_ptr_type.IsValid()) 300 return nullptr; 301 302 // iterated_sp is a __iter_pointer at this point. 303 // We can cast it to a __node_pointer (which is what libc++ does). 304 auto value_type_sp = iterated_sp->Cast(m_node_ptr_type); 305 if (!value_type_sp) 306 return nullptr; 307 308 // Finally, get the key/value pair. 309 value_type_sp = value_type_sp->GetChildMemberWithName("__value_"); 310 if (!value_type_sp) 311 return nullptr; 312 313 m_iterators[idx] = iterator; 314 315 return value_type_sp; 316 } 317 318 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx)319 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex( 320 uint32_t idx) { 321 static ConstString g_cc_("__cc_"), g_cc("__cc"); 322 static ConstString g_nc("__nc"); 323 uint32_t num_children = CalculateNumChildrenIgnoringErrors(); 324 if (idx >= num_children) 325 return nullptr; 326 327 if (m_tree == nullptr || m_root_node == nullptr) 328 return nullptr; 329 330 ValueObjectSP key_val_sp = GetKeyValuePair(idx, /*max_depth=*/num_children); 331 if (!key_val_sp) { 332 // this will stop all future searches until an Update() happens 333 m_tree = nullptr; 334 return nullptr; 335 } 336 337 // at this point we have a valid 338 // we need to copy current_sp into a new object otherwise we will end up with 339 // all items named __value_ 340 StreamString name; 341 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 342 auto potential_child_sp = key_val_sp->Clone(ConstString(name.GetString())); 343 if (potential_child_sp) { 344 switch (potential_child_sp->GetNumChildrenIgnoringErrors()) { 345 case 1: { 346 auto child0_sp = potential_child_sp->GetChildAtIndex(0); 347 if (child0_sp && 348 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc)) 349 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 350 break; 351 } 352 case 2: { 353 auto child0_sp = potential_child_sp->GetChildAtIndex(0); 354 auto child1_sp = potential_child_sp->GetChildAtIndex(1); 355 if (child0_sp && 356 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) && 357 child1_sp && child1_sp->GetName() == g_nc) 358 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 359 break; 360 } 361 } 362 } 363 return potential_child_sp; 364 } 365 366 lldb::ChildCacheState Update()367 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() { 368 m_count = UINT32_MAX; 369 m_tree = m_root_node = nullptr; 370 m_iterators.clear(); 371 m_tree = m_backend.GetChildMemberWithName("__tree_").get(); 372 if (!m_tree) 373 return lldb::ChildCacheState::eRefetch; 374 m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get(); 375 m_node_ptr_type = 376 m_tree->GetCompilerType().GetDirectNestedTypeWithName("__node_pointer"); 377 378 return lldb::ChildCacheState::eRefetch; 379 } 380 381 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: MightHaveChildren()382 MightHaveChildren() { 383 return true; 384 } 385 386 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: GetIndexOfChildWithName(ConstString name)387 GetIndexOfChildWithName(ConstString name) { 388 return ExtractIndexFromString(name.GetCString()); 389 } 390 391 SyntheticChildrenFrontEnd * LibcxxStdMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)392 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator( 393 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 394 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr); 395 } 396 397 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd:: LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)398 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) 399 : SyntheticChildrenFrontEnd(*valobj_sp) { 400 if (valobj_sp) 401 Update(); 402 } 403 404 lldb::ChildCacheState Update()405 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::Update() { 406 m_pair_sp.reset(); 407 408 ValueObjectSP valobj_sp = m_backend.GetSP(); 409 if (!valobj_sp) 410 return lldb::ChildCacheState::eRefetch; 411 412 TargetSP target_sp(valobj_sp->GetTargetSP()); 413 if (!target_sp) 414 return lldb::ChildCacheState::eRefetch; 415 416 // m_backend is a std::map::iterator 417 // ...which is a __map_iterator<__tree_iterator<..., __node_pointer, ...>> 418 // 419 // Then, __map_iterator::__i_ is a __tree_iterator 420 auto tree_iter_sp = valobj_sp->GetChildMemberWithName("__i_"); 421 if (!tree_iter_sp) 422 return lldb::ChildCacheState::eRefetch; 423 424 // Type is __tree_iterator::__node_pointer 425 // (We could alternatively also get this from the template argument) 426 auto node_pointer_type = 427 tree_iter_sp->GetCompilerType().GetDirectNestedTypeWithName( 428 "__node_pointer"); 429 if (!node_pointer_type.IsValid()) 430 return lldb::ChildCacheState::eRefetch; 431 432 // __ptr_ is a __tree_iterator::__iter_pointer 433 auto iter_pointer_sp = tree_iter_sp->GetChildMemberWithName("__ptr_"); 434 if (!iter_pointer_sp) 435 return lldb::ChildCacheState::eRefetch; 436 437 // Cast the __iter_pointer to a __node_pointer (which stores our key/value 438 // pair) 439 auto node_pointer_sp = iter_pointer_sp->Cast(node_pointer_type); 440 if (!node_pointer_sp) 441 return lldb::ChildCacheState::eRefetch; 442 443 auto key_value_sp = node_pointer_sp->GetChildMemberWithName("__value_"); 444 if (!key_value_sp) 445 return lldb::ChildCacheState::eRefetch; 446 447 // Create the synthetic child, which is a pair where the key and value can be 448 // retrieved by querying the synthetic frontend for 449 // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second") 450 // respectively. 451 // 452 // std::map stores the actual key/value pair in value_type::__cc_ (or 453 // previously __cc). 454 key_value_sp = key_value_sp->Clone(ConstString("pair")); 455 if (key_value_sp->GetNumChildrenIgnoringErrors() == 1) { 456 auto child0_sp = key_value_sp->GetChildAtIndex(0); 457 if (child0_sp && 458 (child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc")) 459 key_value_sp = child0_sp->Clone(ConstString("pair")); 460 } 461 462 m_pair_sp = key_value_sp; 463 464 return lldb::ChildCacheState::eRefetch; 465 } 466 467 llvm::Expected<uint32_t> lldb_private::formatters:: CalculateNumChildren()468 LibCxxMapIteratorSyntheticFrontEnd::CalculateNumChildren() { 469 return 2; 470 } 471 472 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx)473 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::GetChildAtIndex( 474 uint32_t idx) { 475 if (!m_pair_sp) 476 return nullptr; 477 478 return m_pair_sp->GetChildAtIndex(idx); 479 } 480 481 bool lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd:: MightHaveChildren()482 MightHaveChildren() { 483 return true; 484 } 485 486 size_t lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd:: GetIndexOfChildWithName(ConstString name)487 GetIndexOfChildWithName(ConstString name) { 488 if (!m_pair_sp) 489 return UINT32_MAX; 490 491 return m_pair_sp->GetIndexOfChildWithName(name); 492 } 493 494 SyntheticChildrenFrontEnd * LibCxxMapIteratorSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)495 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEndCreator( 496 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 497 return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp) 498 : nullptr); 499 } 500