contrib/llvm-project/lldb/source/Plugins/Language/CPlusPlus/LibCxxMap.cpp

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