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