contrib/llvm/tools/lldb/source/Plugins/Language/CPlusPlus/LibCxxMap.cpp

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