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 21 using namespace lldb; 22 using namespace lldb_private; 23 using namespace lldb_private::formatters; 24 25 class MapEntry { 26 public: 27 MapEntry() = default; 28 explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} 29 explicit MapEntry(ValueObject *entry) 30 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 31 32 ValueObjectSP left() const { 33 static ConstString g_left("__left_"); 34 if (!m_entry_sp) 35 return m_entry_sp; 36 return m_entry_sp->GetSyntheticChildAtOffset( 37 0, m_entry_sp->GetCompilerType(), true); 38 } 39 40 ValueObjectSP right() const { 41 static ConstString g_right("__right_"); 42 if (!m_entry_sp) 43 return m_entry_sp; 44 return m_entry_sp->GetSyntheticChildAtOffset( 45 m_entry_sp->GetProcessSP()->GetAddressByteSize(), 46 m_entry_sp->GetCompilerType(), true); 47 } 48 49 ValueObjectSP parent() const { 50 static ConstString g_parent("__parent_"); 51 if (!m_entry_sp) 52 return m_entry_sp; 53 return m_entry_sp->GetSyntheticChildAtOffset( 54 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(), 55 m_entry_sp->GetCompilerType(), true); 56 } 57 58 uint64_t value() const { 59 if (!m_entry_sp) 60 return 0; 61 return m_entry_sp->GetValueAsUnsigned(0); 62 } 63 64 bool error() const { 65 if (!m_entry_sp) 66 return true; 67 return m_entry_sp->GetError().Fail(); 68 } 69 70 bool null() const { return (value() == 0); } 71 72 ValueObjectSP GetEntry() const { return m_entry_sp; } 73 74 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } 75 76 bool operator==(const MapEntry &rhs) const { 77 return (rhs.m_entry_sp.get() == m_entry_sp.get()); 78 } 79 80 private: 81 ValueObjectSP m_entry_sp; 82 }; 83 84 class MapIterator { 85 public: 86 MapIterator() = default; 87 MapIterator(MapEntry entry, size_t depth = 0) 88 : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {} 89 MapIterator(ValueObjectSP entry, size_t depth = 0) 90 : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {} 91 MapIterator(const MapIterator &rhs) 92 : m_entry(rhs.m_entry), m_max_depth(rhs.m_max_depth), m_error(false) {} 93 MapIterator(ValueObject *entry, size_t depth = 0) 94 : m_entry(entry), m_max_depth(depth), m_error(false) {} 95 96 MapIterator &operator=(const MapIterator &) = default; 97 98 ValueObjectSP value() { return m_entry.GetEntry(); } 99 100 ValueObjectSP advance(size_t count) { 101 ValueObjectSP fail; 102 if (m_error) 103 return fail; 104 size_t steps = 0; 105 while (count > 0) { 106 next(); 107 count--, steps++; 108 if (m_error || m_entry.null() || (steps > m_max_depth)) 109 return fail; 110 } 111 return m_entry.GetEntry(); 112 } 113 114 protected: 115 void next() { 116 if (m_entry.null()) 117 return; 118 MapEntry right(m_entry.right()); 119 if (!right.null()) { 120 m_entry = tree_min(std::move(right)); 121 return; 122 } 123 size_t steps = 0; 124 while (!is_left_child(m_entry)) { 125 if (m_entry.error()) { 126 m_error = true; 127 return; 128 } 129 m_entry.SetEntry(m_entry.parent()); 130 steps++; 131 if (steps > m_max_depth) { 132 m_entry = MapEntry(); 133 return; 134 } 135 } 136 m_entry = MapEntry(m_entry.parent()); 137 } 138 139 private: 140 MapEntry tree_min(MapEntry x) { 141 if (x.null()) 142 return MapEntry(); 143 MapEntry left(x.left()); 144 size_t steps = 0; 145 while (!left.null()) { 146 if (left.error()) { 147 m_error = true; 148 return MapEntry(); 149 } 150 x = left; 151 left.SetEntry(x.left()); 152 steps++; 153 if (steps > m_max_depth) 154 return MapEntry(); 155 } 156 return x; 157 } 158 159 bool is_left_child(const MapEntry &x) { 160 if (x.null()) 161 return false; 162 MapEntry rhs(x.parent()); 163 rhs.SetEntry(rhs.left()); 164 return x.value() == rhs.value(); 165 } 166 167 MapEntry m_entry; 168 size_t m_max_depth = 0; 169 bool m_error = false; 170 }; 171 172 namespace lldb_private { 173 namespace formatters { 174 class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd { 175 public: 176 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); 177 178 ~LibcxxStdMapSyntheticFrontEnd() override = default; 179 180 size_t CalculateNumChildren() override; 181 182 lldb::ValueObjectSP GetChildAtIndex(size_t idx) override; 183 184 bool Update() override; 185 186 bool MightHaveChildren() override; 187 188 size_t GetIndexOfChildWithName(ConstString name) override; 189 190 private: 191 bool GetDataType(); 192 193 void GetValueOffset(const lldb::ValueObjectSP &node); 194 195 ValueObject *m_tree = nullptr; 196 ValueObject *m_root_node = nullptr; 197 CompilerType m_element_type; 198 uint32_t m_skip_size = UINT32_MAX; 199 size_t m_count = UINT32_MAX; 200 std::map<size_t, MapIterator> m_iterators; 201 }; 202 } // namespace formatters 203 } // namespace lldb_private 204 205 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 206 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) 207 : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(), m_iterators() { 208 if (valobj_sp) 209 Update(); 210 } 211 212 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 213 CalculateNumChildren() { 214 static ConstString g_pair3_("__pair3_"); 215 static ConstString g_first_("__first_"); 216 static ConstString g_value_("__value_"); 217 218 if (m_count != UINT32_MAX) 219 return m_count; 220 if (m_tree == nullptr) 221 return 0; 222 ValueObjectSP m_item(m_tree->GetChildMemberWithName(g_pair3_, true)); 223 if (!m_item) 224 return 0; 225 226 switch (m_item->GetCompilerType().GetNumDirectBaseClasses()) { 227 case 1: 228 // Assume a pre llvm r300140 __compressed_pair implementation: 229 m_item = m_item->GetChildMemberWithName(g_first_, true); 230 break; 231 case 2: { 232 // Assume a post llvm r300140 __compressed_pair implementation: 233 ValueObjectSP first_elem_parent = m_item->GetChildAtIndex(0, true); 234 m_item = first_elem_parent->GetChildMemberWithName(g_value_, true); 235 break; 236 } 237 default: 238 return false; 239 } 240 241 if (!m_item) 242 return 0; 243 m_count = m_item->GetValueAsUnsigned(0); 244 return m_count; 245 } 246 247 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() { 248 static ConstString g_value_("__value_"); 249 static ConstString g_tree_("__tree_"); 250 static ConstString g_pair3("__pair3_"); 251 252 if (m_element_type.IsValid()) 253 return true; 254 m_element_type.Clear(); 255 ValueObjectSP deref; 256 Status error; 257 deref = m_root_node->Dereference(error); 258 if (!deref || error.Fail()) 259 return false; 260 deref = deref->GetChildMemberWithName(g_value_, true); 261 if (deref) { 262 m_element_type = deref->GetCompilerType(); 263 return true; 264 } 265 deref = m_backend.GetChildAtNamePath({g_tree_, g_pair3}); 266 if (!deref) 267 return false; 268 m_element_type = deref->GetCompilerType() 269 .GetTypeTemplateArgument(1) 270 .GetTypeTemplateArgument(1); 271 if (m_element_type) { 272 std::string name; 273 uint64_t bit_offset_ptr; 274 uint32_t bitfield_bit_size_ptr; 275 bool is_bitfield_ptr; 276 m_element_type = m_element_type.GetFieldAtIndex( 277 0, name, &bit_offset_ptr, &bitfield_bit_size_ptr, &is_bitfield_ptr); 278 m_element_type = m_element_type.GetTypedefedType(); 279 return m_element_type.IsValid(); 280 } else { 281 m_element_type = m_backend.GetCompilerType().GetTypeTemplateArgument(0); 282 return m_element_type.IsValid(); 283 } 284 } 285 286 void lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset( 287 const lldb::ValueObjectSP &node) { 288 if (m_skip_size != UINT32_MAX) 289 return; 290 if (!node) 291 return; 292 CompilerType node_type(node->GetCompilerType()); 293 uint64_t bit_offset; 294 if (node_type.GetIndexOfFieldWithName("__value_", nullptr, &bit_offset) != 295 UINT32_MAX) { 296 m_skip_size = bit_offset / 8u; 297 } else { 298 auto ast_ctx = node_type.GetTypeSystem().dyn_cast_or_null<TypeSystemClang>(); 299 if (!ast_ctx) 300 return; 301 CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier( 302 ConstString(), 303 {{"ptr0", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 304 {"ptr1", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 305 {"ptr2", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 306 {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)}, 307 {"payload", (m_element_type.GetCompleteType(), m_element_type)}}); 308 std::string child_name; 309 uint32_t child_byte_size; 310 int32_t child_byte_offset = 0; 311 uint32_t child_bitfield_bit_size; 312 uint32_t child_bitfield_bit_offset; 313 bool child_is_base_class; 314 bool child_is_deref_of_parent; 315 uint64_t language_flags; 316 if (tree_node_type 317 .GetChildCompilerTypeAtIndex( 318 nullptr, 4, true, true, true, child_name, child_byte_size, 319 child_byte_offset, child_bitfield_bit_size, 320 child_bitfield_bit_offset, child_is_base_class, 321 child_is_deref_of_parent, nullptr, language_flags) 322 .IsValid()) 323 m_skip_size = (uint32_t)child_byte_offset; 324 } 325 } 326 327 lldb::ValueObjectSP 328 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex( 329 size_t idx) { 330 static ConstString g_cc_("__cc_"), g_cc("__cc"); 331 static ConstString g_nc("__nc"); 332 static ConstString g_value_("__value_"); 333 334 if (idx >= CalculateNumChildren()) 335 return lldb::ValueObjectSP(); 336 if (m_tree == nullptr || m_root_node == nullptr) 337 return lldb::ValueObjectSP(); 338 339 MapIterator iterator(m_root_node, CalculateNumChildren()); 340 341 const bool need_to_skip = (idx > 0); 342 size_t actual_advancde = idx; 343 if (need_to_skip) { 344 auto cached_iterator = m_iterators.find(idx - 1); 345 if (cached_iterator != m_iterators.end()) { 346 iterator = cached_iterator->second; 347 actual_advancde = 1; 348 } 349 } 350 351 ValueObjectSP iterated_sp(iterator.advance(actual_advancde)); 352 if (!iterated_sp) { 353 // this tree is garbage - stop 354 m_tree = 355 nullptr; // this will stop all future searches until an Update() happens 356 return iterated_sp; 357 } 358 if (GetDataType()) { 359 if (!need_to_skip) { 360 Status error; 361 iterated_sp = iterated_sp->Dereference(error); 362 if (!iterated_sp || error.Fail()) { 363 m_tree = nullptr; 364 return lldb::ValueObjectSP(); 365 } 366 GetValueOffset(iterated_sp); 367 auto child_sp = iterated_sp->GetChildMemberWithName(g_value_, true); 368 if (child_sp) 369 iterated_sp = child_sp; 370 else 371 iterated_sp = iterated_sp->GetSyntheticChildAtOffset( 372 m_skip_size, m_element_type, true); 373 if (!iterated_sp) { 374 m_tree = nullptr; 375 return lldb::ValueObjectSP(); 376 } 377 } else { 378 // because of the way our debug info is made, we need to read item 0 379 // first so that we can cache information used to generate other elements 380 if (m_skip_size == UINT32_MAX) 381 GetChildAtIndex(0); 382 if (m_skip_size == UINT32_MAX) { 383 m_tree = nullptr; 384 return lldb::ValueObjectSP(); 385 } 386 iterated_sp = iterated_sp->GetSyntheticChildAtOffset( 387 m_skip_size, m_element_type, true); 388 if (!iterated_sp) { 389 m_tree = nullptr; 390 return lldb::ValueObjectSP(); 391 } 392 } 393 } else { 394 m_tree = nullptr; 395 return lldb::ValueObjectSP(); 396 } 397 // at this point we have a valid 398 // we need to copy current_sp into a new object otherwise we will end up with 399 // all items named __value_ 400 DataExtractor data; 401 Status error; 402 iterated_sp->GetData(data, error); 403 if (error.Fail()) { 404 m_tree = nullptr; 405 return lldb::ValueObjectSP(); 406 } 407 StreamString name; 408 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 409 auto potential_child_sp = CreateValueObjectFromData( 410 name.GetString(), data, m_backend.GetExecutionContextRef(), 411 m_element_type); 412 if (potential_child_sp) { 413 switch (potential_child_sp->GetNumChildren()) { 414 case 1: { 415 auto child0_sp = potential_child_sp->GetChildAtIndex(0, true); 416 if (child0_sp && 417 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc)) 418 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 419 break; 420 } 421 case 2: { 422 auto child0_sp = potential_child_sp->GetChildAtIndex(0, true); 423 auto child1_sp = potential_child_sp->GetChildAtIndex(1, true); 424 if (child0_sp && 425 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) && 426 child1_sp && child1_sp->GetName() == g_nc) 427 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 428 break; 429 } 430 } 431 } 432 m_iterators[idx] = iterator; 433 return potential_child_sp; 434 } 435 436 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() { 437 static ConstString g_tree_("__tree_"); 438 static ConstString g_begin_node_("__begin_node_"); 439 m_count = UINT32_MAX; 440 m_tree = m_root_node = nullptr; 441 m_iterators.clear(); 442 m_tree = m_backend.GetChildMemberWithName(g_tree_, true).get(); 443 if (!m_tree) 444 return false; 445 m_root_node = m_tree->GetChildMemberWithName(g_begin_node_, true).get(); 446 return false; 447 } 448 449 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 450 MightHaveChildren() { 451 return true; 452 } 453 454 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 455 GetIndexOfChildWithName(ConstString name) { 456 return ExtractIndexFromString(name.GetCString()); 457 } 458 459 SyntheticChildrenFrontEnd * 460 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator( 461 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 462 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr); 463 } 464