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; 169 bool m_error; 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.GetOpaqueQualType() && m_element_type.GetTypeSystem()) 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 TypeSystemClang *ast_ctx = 299 llvm::dyn_cast_or_null<TypeSystemClang>(node_type.GetTypeSystem()); 300 if (!ast_ctx) 301 return; 302 CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier( 303 ConstString(), 304 {{"ptr0", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 305 {"ptr1", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 306 {"ptr2", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 307 {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)}, 308 {"payload", (m_element_type.GetCompleteType(), m_element_type)}}); 309 std::string child_name; 310 uint32_t child_byte_size; 311 int32_t child_byte_offset = 0; 312 uint32_t child_bitfield_bit_size; 313 uint32_t child_bitfield_bit_offset; 314 bool child_is_base_class; 315 bool child_is_deref_of_parent; 316 uint64_t language_flags; 317 if (tree_node_type 318 .GetChildCompilerTypeAtIndex( 319 nullptr, 4, true, true, true, child_name, child_byte_size, 320 child_byte_offset, child_bitfield_bit_size, 321 child_bitfield_bit_offset, child_is_base_class, 322 child_is_deref_of_parent, nullptr, language_flags) 323 .IsValid()) 324 m_skip_size = (uint32_t)child_byte_offset; 325 } 326 } 327 328 lldb::ValueObjectSP 329 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex( 330 size_t idx) { 331 static ConstString g_cc("__cc"); 332 static ConstString g_nc("__nc"); 333 static ConstString g_value_("__value_"); 334 335 if (idx >= CalculateNumChildren()) 336 return lldb::ValueObjectSP(); 337 if (m_tree == nullptr || m_root_node == nullptr) 338 return lldb::ValueObjectSP(); 339 340 MapIterator iterator(m_root_node, CalculateNumChildren()); 341 342 const bool need_to_skip = (idx > 0); 343 size_t actual_advancde = idx; 344 if (need_to_skip) { 345 auto cached_iterator = m_iterators.find(idx - 1); 346 if (cached_iterator != m_iterators.end()) { 347 iterator = cached_iterator->second; 348 actual_advancde = 1; 349 } 350 } 351 352 ValueObjectSP iterated_sp(iterator.advance(actual_advancde)); 353 if (!iterated_sp) { 354 // this tree is garbage - stop 355 m_tree = 356 nullptr; // this will stop all future searches until an Update() happens 357 return iterated_sp; 358 } 359 if (GetDataType()) { 360 if (!need_to_skip) { 361 Status error; 362 iterated_sp = iterated_sp->Dereference(error); 363 if (!iterated_sp || error.Fail()) { 364 m_tree = nullptr; 365 return lldb::ValueObjectSP(); 366 } 367 GetValueOffset(iterated_sp); 368 auto child_sp = iterated_sp->GetChildMemberWithName(g_value_, true); 369 if (child_sp) 370 iterated_sp = child_sp; 371 else 372 iterated_sp = iterated_sp->GetSyntheticChildAtOffset( 373 m_skip_size, m_element_type, true); 374 if (!iterated_sp) { 375 m_tree = nullptr; 376 return lldb::ValueObjectSP(); 377 } 378 } else { 379 // because of the way our debug info is made, we need to read item 0 380 // first so that we can cache information used to generate other elements 381 if (m_skip_size == UINT32_MAX) 382 GetChildAtIndex(0); 383 if (m_skip_size == UINT32_MAX) { 384 m_tree = nullptr; 385 return lldb::ValueObjectSP(); 386 } 387 iterated_sp = iterated_sp->GetSyntheticChildAtOffset( 388 m_skip_size, m_element_type, true); 389 if (!iterated_sp) { 390 m_tree = nullptr; 391 return lldb::ValueObjectSP(); 392 } 393 } 394 } else { 395 m_tree = nullptr; 396 return lldb::ValueObjectSP(); 397 } 398 // at this point we have a valid 399 // we need to copy current_sp into a new object otherwise we will end up with 400 // all items named __value_ 401 DataExtractor data; 402 Status error; 403 iterated_sp->GetData(data, error); 404 if (error.Fail()) { 405 m_tree = nullptr; 406 return lldb::ValueObjectSP(); 407 } 408 StreamString name; 409 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 410 auto potential_child_sp = CreateValueObjectFromData( 411 name.GetString(), data, m_backend.GetExecutionContextRef(), 412 m_element_type); 413 if (potential_child_sp) { 414 switch (potential_child_sp->GetNumChildren()) { 415 case 1: { 416 auto child0_sp = potential_child_sp->GetChildAtIndex(0, true); 417 if (child0_sp && 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 && child0_sp->GetName() == g_cc && child1_sp && 425 child1_sp->GetName() == g_nc) 426 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 427 break; 428 } 429 } 430 } 431 m_iterators[idx] = iterator; 432 return potential_child_sp; 433 } 434 435 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() { 436 static ConstString g_tree_("__tree_"); 437 static ConstString g_begin_node_("__begin_node_"); 438 m_count = UINT32_MAX; 439 m_tree = m_root_node = nullptr; 440 m_iterators.clear(); 441 m_tree = m_backend.GetChildMemberWithName(g_tree_, true).get(); 442 if (!m_tree) 443 return false; 444 m_root_node = m_tree->GetChildMemberWithName(g_begin_node_, true).get(); 445 return false; 446 } 447 448 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 449 MightHaveChildren() { 450 return true; 451 } 452 453 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 454 GetIndexOfChildWithName(ConstString name) { 455 return ExtractIndexFromString(name.GetCString()); 456 } 457 458 SyntheticChildrenFrontEnd * 459 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator( 460 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 461 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr); 462 } 463