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