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