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