1 //===-- LibCxxList.cpp ------------------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 // C Includes 11 // C++ Includes 12 // Other libraries and framework includes 13 // Project includes 14 #include "LibCxx.h" 15 16 #include "lldb/Core/DataBufferHeap.h" 17 #include "lldb/Core/Error.h" 18 #include "lldb/Core/Stream.h" 19 #include "lldb/Core/ValueObject.h" 20 #include "lldb/Core/ValueObjectConstResult.h" 21 #include "lldb/DataFormatters/FormattersHelpers.h" 22 #include "lldb/Host/Endian.h" 23 #include "lldb/Symbol/ClangASTContext.h" 24 #include "lldb/Target/Target.h" 25 26 using namespace lldb; 27 using namespace lldb_private; 28 using namespace lldb_private::formatters; 29 30 class MapEntry 31 { 32 public: 33 MapEntry() = default; 34 explicit MapEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} 35 MapEntry (const MapEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {} 36 explicit MapEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 37 38 ValueObjectSP 39 left () const 40 { 41 static ConstString g_left("__left_"); 42 if (!m_entry_sp) 43 return m_entry_sp; 44 return m_entry_sp->GetChildMemberWithName(g_left, true); 45 } 46 47 ValueObjectSP 48 right () const 49 { 50 static ConstString g_right("__right_"); 51 if (!m_entry_sp) 52 return m_entry_sp; 53 return m_entry_sp->GetChildMemberWithName(g_right, true); 54 } 55 56 ValueObjectSP 57 parent () const 58 { 59 static ConstString g_parent("__parent_"); 60 if (!m_entry_sp) 61 return m_entry_sp; 62 return m_entry_sp->GetChildMemberWithName(g_parent, true); 63 } 64 65 uint64_t 66 value () const 67 { 68 if (!m_entry_sp) 69 return 0; 70 return m_entry_sp->GetValueAsUnsigned(0); 71 } 72 73 bool 74 error () const 75 { 76 if (!m_entry_sp) 77 return true; 78 return m_entry_sp->GetError().Fail(); 79 } 80 81 bool 82 null() const 83 { 84 return (value() == 0); 85 } 86 87 ValueObjectSP 88 GetEntry () const 89 { 90 return m_entry_sp; 91 } 92 93 void 94 SetEntry (ValueObjectSP entry) 95 { 96 m_entry_sp = entry; 97 } 98 99 bool 100 operator == (const MapEntry& rhs) const 101 { 102 return (rhs.m_entry_sp.get() == m_entry_sp.get()); 103 } 104 105 private: 106 ValueObjectSP m_entry_sp; 107 }; 108 109 class MapIterator 110 { 111 public: 112 MapIterator() = default; 113 MapIterator (MapEntry entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {} 114 MapIterator (ValueObjectSP entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {} 115 MapIterator (const MapIterator& rhs) : m_entry(rhs.m_entry),m_max_depth(rhs.m_max_depth), m_error(false) {} 116 MapIterator (ValueObject* entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {} 117 118 ValueObjectSP 119 value () 120 { 121 return m_entry.GetEntry(); 122 } 123 124 ValueObjectSP 125 advance (size_t count) 126 { 127 ValueObjectSP fail(nullptr); 128 if (m_error) 129 return fail; 130 size_t steps = 0; 131 while (count > 0) 132 { 133 next(); 134 count--, steps++; 135 if (m_error || 136 m_entry.null() || 137 (steps > m_max_depth)) 138 return fail; 139 } 140 return m_entry.GetEntry(); 141 } 142 143 protected: 144 void 145 next () 146 { 147 if (m_entry.null()) 148 return; 149 MapEntry right(m_entry.right()); 150 if (right.null() == false) 151 { 152 m_entry = tree_min(std::move(right)); 153 return; 154 } 155 size_t steps = 0; 156 while (!is_left_child(m_entry)) 157 { 158 if (m_entry.error()) 159 { 160 m_error = true; 161 return; 162 } 163 m_entry.SetEntry(m_entry.parent()); 164 steps++; 165 if (steps > m_max_depth) 166 { 167 m_entry = MapEntry(); 168 return; 169 } 170 } 171 m_entry = MapEntry(m_entry.parent()); 172 } 173 174 private: 175 MapEntry 176 tree_min (MapEntry&& x) 177 { 178 if (x.null()) 179 return MapEntry(); 180 MapEntry left(x.left()); 181 size_t steps = 0; 182 while (left.null() == false) 183 { 184 if (left.error()) 185 { 186 m_error = true; 187 return MapEntry(); 188 } 189 x = left; 190 left.SetEntry(x.left()); 191 steps++; 192 if (steps > m_max_depth) 193 return MapEntry(); 194 } 195 return x; 196 } 197 198 bool 199 is_left_child (const MapEntry& x) 200 { 201 if (x.null()) 202 return false; 203 MapEntry rhs(x.parent()); 204 rhs.SetEntry(rhs.left()); 205 return x.value() == rhs.value(); 206 } 207 208 MapEntry m_entry; 209 size_t m_max_depth; 210 bool m_error; 211 }; 212 213 namespace lldb_private { 214 namespace formatters { 215 class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd 216 { 217 public: 218 LibcxxStdMapSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp); 219 220 ~LibcxxStdMapSyntheticFrontEnd() override = default; 221 222 size_t 223 CalculateNumChildren() override; 224 225 lldb::ValueObjectSP 226 GetChildAtIndex(size_t idx) override; 227 228 bool 229 Update() override; 230 231 bool 232 MightHaveChildren() override; 233 234 size_t 235 GetIndexOfChildWithName(const ConstString &name) override; 236 237 private: 238 bool 239 GetDataType(); 240 241 void 242 GetValueOffset (const lldb::ValueObjectSP& node); 243 244 ValueObject* m_tree; 245 ValueObject* m_root_node; 246 CompilerType m_element_type; 247 uint32_t m_skip_size; 248 size_t m_count; 249 std::map<size_t, lldb::ValueObjectSP> m_children; 250 std::map<size_t, MapIterator> m_iterators; 251 }; 252 } // namespace formatters 253 } // namespace lldb_private 254 255 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::LibcxxStdMapSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) : 256 SyntheticChildrenFrontEnd(*valobj_sp.get()), 257 m_tree(NULL), 258 m_root_node(NULL), 259 m_element_type(), 260 m_skip_size(UINT32_MAX), 261 m_count(UINT32_MAX), 262 m_children(), 263 m_iterators() 264 { 265 if (valobj_sp) 266 Update(); 267 } 268 269 size_t 270 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren () 271 { 272 static ConstString g___pair3_("__pair3_"); 273 static ConstString g___first_("__first_"); 274 275 if (m_count != UINT32_MAX) 276 return m_count; 277 if (m_tree == NULL) 278 return 0; 279 ValueObjectSP m_item(m_tree->GetChildMemberWithName(g___pair3_, true)); 280 if (!m_item) 281 return 0; 282 m_item = m_item->GetChildMemberWithName(g___first_, true); 283 if (!m_item) 284 return 0; 285 m_count = m_item->GetValueAsUnsigned(0); 286 return m_count; 287 } 288 289 bool 290 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() 291 { 292 static ConstString g___value_("__value_"); 293 294 if (m_element_type.GetOpaqueQualType() && m_element_type.GetTypeSystem()) 295 return true; 296 m_element_type.Clear(); 297 ValueObjectSP deref; 298 Error error; 299 deref = m_root_node->Dereference(error); 300 if (!deref || error.Fail()) 301 return false; 302 deref = deref->GetChildMemberWithName(g___value_, true); 303 if (!deref) 304 return false; 305 m_element_type = deref->GetCompilerType(); 306 return true; 307 } 308 309 void 310 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset (const lldb::ValueObjectSP& node) 311 { 312 if (m_skip_size != UINT32_MAX) 313 return; 314 if (!node) 315 return; 316 CompilerType node_type(node->GetCompilerType()); 317 uint64_t bit_offset; 318 if (node_type.GetIndexOfFieldWithName("__value_", NULL, &bit_offset) == UINT32_MAX) 319 return; 320 m_skip_size = bit_offset / 8u; 321 } 322 323 lldb::ValueObjectSP 324 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex (size_t idx) 325 { 326 static ConstString g___cc("__cc"); 327 static ConstString g___nc("__nc"); 328 static ConstString g___value_("__value_"); 329 330 331 if (idx >= CalculateNumChildren()) 332 return lldb::ValueObjectSP(); 333 if (m_tree == NULL || m_root_node == NULL) 334 return lldb::ValueObjectSP(); 335 336 auto cached = m_children.find(idx); 337 if (cached != m_children.end()) 338 return cached->second; 339 340 MapIterator iterator(m_root_node, CalculateNumChildren()); 341 342 const bool need_to_skip = (idx > 0); 343 size_t actual_advancde = idx; 344 if (need_to_skip) 345 { 346 auto cached_iterator = m_iterators.find(idx-1); 347 if (cached_iterator != m_iterators.end()) 348 { 349 iterator = cached_iterator->second; 350 actual_advancde = 1; 351 } 352 } 353 354 ValueObjectSP iterated_sp(iterator.advance(actual_advancde)); 355 if (iterated_sp.get() == NULL) 356 { 357 // this tree is garbage - stop 358 m_tree = NULL; // this will stop all future searches until an Update() happens 359 return iterated_sp; 360 } 361 if (GetDataType()) 362 { 363 if (!need_to_skip) 364 { 365 Error error; 366 iterated_sp = iterated_sp->Dereference(error); 367 if (!iterated_sp || error.Fail()) 368 { 369 m_tree = NULL; 370 return lldb::ValueObjectSP(); 371 } 372 GetValueOffset(iterated_sp); 373 iterated_sp = iterated_sp->GetChildMemberWithName(g___value_, true); 374 if (!iterated_sp) 375 { 376 m_tree = NULL; 377 return lldb::ValueObjectSP(); 378 } 379 } 380 else 381 { 382 // because of the way our debug info is made, we need to read item 0 first 383 // so that we can cache information used to generate other elements 384 if (m_skip_size == UINT32_MAX) 385 GetChildAtIndex(0); 386 if (m_skip_size == UINT32_MAX) 387 { 388 m_tree = NULL; 389 return lldb::ValueObjectSP(); 390 } 391 iterated_sp = iterated_sp->GetSyntheticChildAtOffset(m_skip_size, m_element_type, true); 392 if (!iterated_sp) 393 { 394 m_tree = NULL; 395 return lldb::ValueObjectSP(); 396 } 397 } 398 } 399 else 400 { 401 m_tree = NULL; 402 return lldb::ValueObjectSP(); 403 } 404 // at this point we have a valid 405 // we need to copy current_sp into a new object otherwise we will end up with all items named __value_ 406 DataExtractor data; 407 Error error; 408 iterated_sp->GetData(data, error); 409 if (error.Fail()) 410 { 411 m_tree = NULL; 412 return lldb::ValueObjectSP(); 413 } 414 StreamString name; 415 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 416 auto potential_child_sp = CreateValueObjectFromData(name.GetData(), data, m_backend.GetExecutionContextRef(), m_element_type); 417 if (potential_child_sp) 418 { 419 switch (potential_child_sp->GetNumChildren()) 420 { 421 case 1: 422 { 423 auto child0_sp = potential_child_sp->GetChildAtIndex(0, true); 424 if (child0_sp && child0_sp->GetName() == g___cc) 425 potential_child_sp = child0_sp; 426 break; 427 } 428 case 2: 429 { 430 auto child0_sp = potential_child_sp->GetChildAtIndex(0, true); 431 auto child1_sp = potential_child_sp->GetChildAtIndex(1, true); 432 if (child0_sp && child0_sp->GetName() == g___cc && 433 child1_sp && child1_sp->GetName() == g___nc) 434 potential_child_sp = child0_sp; 435 break; 436 } 437 } 438 potential_child_sp->SetName(ConstString(name.GetData())); 439 } 440 m_iterators[idx] = iterator; 441 return (m_children[idx] = potential_child_sp); 442 } 443 444 bool 445 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() 446 { 447 static ConstString g___tree_("__tree_"); 448 static ConstString g___begin_node_("__begin_node_"); 449 m_count = UINT32_MAX; 450 m_tree = m_root_node = NULL; 451 m_children.clear(); 452 m_iterators.clear(); 453 m_tree = m_backend.GetChildMemberWithName(g___tree_, true).get(); 454 if (!m_tree) 455 return false; 456 m_root_node = m_tree->GetChildMemberWithName(g___begin_node_, true).get(); 457 return false; 458 } 459 460 bool 461 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::MightHaveChildren () 462 { 463 return true; 464 } 465 466 size_t 467 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name) 468 { 469 return ExtractIndexFromString(name.GetCString()); 470 } 471 472 SyntheticChildrenFrontEnd* 473 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp) 474 { 475 if (!valobj_sp) 476 return NULL; 477 return (new LibcxxStdMapSyntheticFrontEnd(valobj_sp)); 478 } 479