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