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 if (m_count != UINT32_MAX) 215 return m_count; 216 if (m_tree == nullptr) 217 return 0; 218 ValueObjectSP m_item(m_tree->GetChildMemberWithName("__pair3_", true)); 219 if (!m_item) 220 return 0; 221 222 switch (m_item->GetCompilerType().GetNumDirectBaseClasses()) { 223 case 1: 224 // Assume a pre llvm r300140 __compressed_pair implementation: 225 m_item = m_item->GetChildMemberWithName("__first_", true); 226 break; 227 case 2: { 228 // Assume a post llvm r300140 __compressed_pair implementation: 229 ValueObjectSP first_elem_parent = m_item->GetChildAtIndex(0, true); 230 m_item = first_elem_parent->GetChildMemberWithName("__value_", true); 231 break; 232 } 233 default: 234 return false; 235 } 236 237 if (!m_item) 238 return 0; 239 m_count = m_item->GetValueAsUnsigned(0); 240 return m_count; 241 } 242 243 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() { 244 static ConstString g_tree_("__tree_"); 245 static ConstString g_pair3("__pair3_"); 246 247 if (m_element_type.IsValid()) 248 return true; 249 m_element_type.Clear(); 250 ValueObjectSP deref; 251 Status error; 252 deref = m_root_node->Dereference(error); 253 if (!deref || error.Fail()) 254 return false; 255 deref = deref->GetChildMemberWithName("__value_", true); 256 if (deref) { 257 m_element_type = deref->GetCompilerType(); 258 return true; 259 } 260 deref = m_backend.GetChildAtNamePath({g_tree_, g_pair3}); 261 if (!deref) 262 return false; 263 m_element_type = deref->GetCompilerType() 264 .GetTypeTemplateArgument(1) 265 .GetTypeTemplateArgument(1); 266 if (m_element_type) { 267 std::string name; 268 uint64_t bit_offset_ptr; 269 uint32_t bitfield_bit_size_ptr; 270 bool is_bitfield_ptr; 271 m_element_type = m_element_type.GetFieldAtIndex( 272 0, name, &bit_offset_ptr, &bitfield_bit_size_ptr, &is_bitfield_ptr); 273 m_element_type = m_element_type.GetTypedefedType(); 274 return m_element_type.IsValid(); 275 } else { 276 m_element_type = m_backend.GetCompilerType().GetTypeTemplateArgument(0); 277 return m_element_type.IsValid(); 278 } 279 } 280 281 void lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset( 282 const lldb::ValueObjectSP &node) { 283 if (m_skip_size != UINT32_MAX) 284 return; 285 if (!node) 286 return; 287 CompilerType node_type(node->GetCompilerType()); 288 uint64_t bit_offset; 289 if (node_type.GetIndexOfFieldWithName("__value_", nullptr, &bit_offset) != 290 UINT32_MAX) { 291 m_skip_size = bit_offset / 8u; 292 } else { 293 auto ast_ctx = node_type.GetTypeSystem().dyn_cast_or_null<TypeSystemClang>(); 294 if (!ast_ctx) 295 return; 296 CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier( 297 ConstString(), 298 {{"ptr0", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 299 {"ptr1", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 300 {"ptr2", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 301 {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)}, 302 {"payload", (m_element_type.GetCompleteType(), m_element_type)}}); 303 std::string child_name; 304 uint32_t child_byte_size; 305 int32_t child_byte_offset = 0; 306 uint32_t child_bitfield_bit_size; 307 uint32_t child_bitfield_bit_offset; 308 bool child_is_base_class; 309 bool child_is_deref_of_parent; 310 uint64_t language_flags; 311 if (tree_node_type 312 .GetChildCompilerTypeAtIndex( 313 nullptr, 4, true, true, true, child_name, child_byte_size, 314 child_byte_offset, child_bitfield_bit_size, 315 child_bitfield_bit_offset, child_is_base_class, 316 child_is_deref_of_parent, nullptr, language_flags) 317 .IsValid()) 318 m_skip_size = (uint32_t)child_byte_offset; 319 } 320 } 321 322 lldb::ValueObjectSP 323 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex( 324 size_t idx) { 325 static ConstString g_cc_("__cc_"), g_cc("__cc"); 326 static ConstString g_nc("__nc"); 327 328 if (idx >= CalculateNumChildren()) 329 return lldb::ValueObjectSP(); 330 if (m_tree == nullptr || m_root_node == nullptr) 331 return lldb::ValueObjectSP(); 332 333 MapIterator iterator(m_root_node, CalculateNumChildren()); 334 335 const bool need_to_skip = (idx > 0); 336 size_t actual_advancde = idx; 337 if (need_to_skip) { 338 auto cached_iterator = m_iterators.find(idx - 1); 339 if (cached_iterator != m_iterators.end()) { 340 iterator = cached_iterator->second; 341 actual_advancde = 1; 342 } 343 } 344 345 ValueObjectSP iterated_sp(iterator.advance(actual_advancde)); 346 if (!iterated_sp) { 347 // this tree is garbage - stop 348 m_tree = 349 nullptr; // this will stop all future searches until an Update() happens 350 return iterated_sp; 351 } 352 if (GetDataType()) { 353 if (!need_to_skip) { 354 Status error; 355 iterated_sp = iterated_sp->Dereference(error); 356 if (!iterated_sp || error.Fail()) { 357 m_tree = nullptr; 358 return lldb::ValueObjectSP(); 359 } 360 GetValueOffset(iterated_sp); 361 auto child_sp = iterated_sp->GetChildMemberWithName("__value_", true); 362 if (child_sp) 363 iterated_sp = child_sp; 364 else 365 iterated_sp = iterated_sp->GetSyntheticChildAtOffset( 366 m_skip_size, m_element_type, true); 367 if (!iterated_sp) { 368 m_tree = nullptr; 369 return lldb::ValueObjectSP(); 370 } 371 } else { 372 // because of the way our debug info is made, we need to read item 0 373 // first so that we can cache information used to generate other elements 374 if (m_skip_size == UINT32_MAX) 375 GetChildAtIndex(0); 376 if (m_skip_size == UINT32_MAX) { 377 m_tree = nullptr; 378 return lldb::ValueObjectSP(); 379 } 380 iterated_sp = iterated_sp->GetSyntheticChildAtOffset( 381 m_skip_size, m_element_type, true); 382 if (!iterated_sp) { 383 m_tree = nullptr; 384 return lldb::ValueObjectSP(); 385 } 386 } 387 } else { 388 m_tree = nullptr; 389 return lldb::ValueObjectSP(); 390 } 391 // at this point we have a valid 392 // we need to copy current_sp into a new object otherwise we will end up with 393 // all items named __value_ 394 StreamString name; 395 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 396 auto potential_child_sp = iterated_sp->Clone(ConstString(name.GetString())); 397 if (potential_child_sp) { 398 switch (potential_child_sp->GetNumChildren()) { 399 case 1: { 400 auto child0_sp = potential_child_sp->GetChildAtIndex(0, true); 401 if (child0_sp && 402 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc)) 403 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 404 break; 405 } 406 case 2: { 407 auto child0_sp = potential_child_sp->GetChildAtIndex(0, true); 408 auto child1_sp = potential_child_sp->GetChildAtIndex(1, true); 409 if (child0_sp && 410 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) && 411 child1_sp && child1_sp->GetName() == g_nc) 412 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 413 break; 414 } 415 } 416 } 417 m_iterators[idx] = iterator; 418 return potential_child_sp; 419 } 420 421 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() { 422 m_count = UINT32_MAX; 423 m_tree = m_root_node = nullptr; 424 m_iterators.clear(); 425 m_tree = m_backend.GetChildMemberWithName("__tree_", true).get(); 426 if (!m_tree) 427 return false; 428 m_root_node = m_tree->GetChildMemberWithName("__begin_node_", true).get(); 429 return false; 430 } 431 432 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 433 MightHaveChildren() { 434 return true; 435 } 436 437 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 438 GetIndexOfChildWithName(ConstString name) { 439 return ExtractIndexFromString(name.GetCString()); 440 } 441 442 SyntheticChildrenFrontEnd * 443 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator( 444 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 445 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr); 446 } 447