lldb/source/Plugins/Language/CPlusPlus/LibCxxUnorderedMap.cpp

   1 //===-- LibCxxUnorderedMap.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/DataFormatters/FormattersHelpers.h"
  13 #include "lldb/Target/Target.h"
  14 #include "lldb/Utility/ConstString.h"
  15 #include "lldb/Utility/DataBufferHeap.h"
  16 #include "lldb/Utility/Endian.h"
  17 #include "lldb/Utility/Status.h"
  18 #include "lldb/Utility/Stream.h"
  19 #include "lldb/ValueObject/ValueObject.h"
  20 #include "lldb/ValueObject/ValueObjectConstResult.h"
  21 #include "llvm/ADT/StringRef.h"
  22 #include "llvm/Support/Error.h"
  23
  24 using namespace lldb;
  25 using namespace lldb_private;
  26 using namespace lldb_private::formatters;
  27
  28 namespace lldb_private {
  29 namespace formatters {
  30 class LibcxxStdUnorderedMapSyntheticFrontEnd
  31     : public SyntheticChildrenFrontEnd {
  32 public:
  33   LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
  34
  35   ~LibcxxStdUnorderedMapSyntheticFrontEnd() override = default;
  36
  37   llvm::Expected<uint32_t> CalculateNumChildren() override;
  38
  39   lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
  40
  41   lldb::ChildCacheState Update() override;
  42
  43   bool MightHaveChildren() override;
  44
  45   size_t GetIndexOfChildWithName(ConstString name) override;
  46
  47 private:
  48   CompilerType GetNodeType();
  49   CompilerType GetElementType(CompilerType node_type);
  50   llvm::Expected<size_t> CalculateNumChildrenImpl(ValueObject &table);
  51
  52   CompilerType m_element_type;
  53   CompilerType m_node_type;
  54   ValueObject *m_tree = nullptr;
  55   size_t m_num_elements = 0;
  56   ValueObject *m_next_element = nullptr;
  57   std::vector<std::pair<ValueObject *, uint64_t>> m_elements_cache;
  58 };
  59
  60 class LibCxxUnorderedMapIteratorSyntheticFrontEnd
  61     : public SyntheticChildrenFrontEnd {
  62 public:
  63   LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
  64
  65   ~LibCxxUnorderedMapIteratorSyntheticFrontEnd() override = default;
  66
  67   llvm::Expected<uint32_t> CalculateNumChildren() override;
  68
  69   lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
  70
  71   lldb::ChildCacheState Update() override;
  72
  73   bool MightHaveChildren() override;
  74
  75   size_t GetIndexOfChildWithName(ConstString name) override;
  76
  77 private:
  78   lldb::ValueObjectSP m_pair_sp; ///< ValueObject for the key/value pair
  79                                  ///< that the iterator currently points
  80                                  ///< to.
  81 };
  82
  83 } // namespace formatters
  84 } // namespace lldb_private
  85
  86 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
  87     LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
  88     : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(),
  89       m_elements_cache() {
  90   if (valobj_sp)
  91     Update();
  92 }
  93
  94 llvm::Expected<uint32_t> lldb_private::formatters::
  95     LibcxxStdUnorderedMapSyntheticFrontEnd::CalculateNumChildren() {
  96   return m_num_elements;
  97 }
  98
  99 static bool isUnorderedMap(ConstString type_name) {
 100   return isStdTemplate(type_name, "unordered_map") ||
 101          isStdTemplate(type_name, "unordered_multimap");
 102 }
 103
 104 CompilerType lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
 105     GetElementType(CompilerType node_type) {
 106   CompilerType element_type = node_type.GetTypeTemplateArgument(0);
 107
 108   // This synthetic provider is used for both unordered_(multi)map and
 109   // unordered_(multi)set. For unordered_map, the element type has an
 110   // additional type layer, an internal struct (`__hash_value_type`)
 111   // that wraps a std::pair. Peel away the internal wrapper type - whose
 112   // structure is of no value to users, to expose the std::pair. This
 113   // matches the structure returned by the std::map synthetic provider.
 114   if (isUnorderedMap(m_backend.GetTypeName())) {
 115     std::string name;
 116     CompilerType field_type =
 117         element_type.GetFieldAtIndex(0, name, nullptr, nullptr, nullptr);
 118     CompilerType actual_type = field_type.GetTypedefedType();
 119     if (isStdTemplate(actual_type.GetTypeName(), "pair"))
 120       element_type = actual_type;
 121   }
 122
 123   return element_type;
 124 }
 125
 126 CompilerType lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
 127     GetNodeType() {
 128   auto node_sp = m_backend.GetChildAtNamePath({"__table_", "__first_node_"});
 129
 130   if (!node_sp) {
 131     auto p1_sp = m_backend.GetChildAtNamePath({"__table_", "__p1_"});
 132     if (!p1_sp)
 133       return {};
 134
 135     if (!isOldCompressedPairLayout(*p1_sp))
 136       return {};
 137
 138     node_sp = GetFirstValueOfLibCXXCompressedPair(*p1_sp);
 139     if (!node_sp)
 140       return {};
 141   }
 142
 143   assert(node_sp);
 144
 145   return node_sp->GetCompilerType().GetTypeTemplateArgument(0).GetPointeeType();
 146 }
 147
 148 lldb::ValueObjectSP lldb_private::formatters::
 149     LibcxxStdUnorderedMapSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
 150   if (idx >= CalculateNumChildrenIgnoringErrors())
 151     return lldb::ValueObjectSP();
 152   if (m_tree == nullptr)
 153     return lldb::ValueObjectSP();
 154
 155   while (idx >= m_elements_cache.size()) {
 156     if (m_next_element == nullptr)
 157       return lldb::ValueObjectSP();
 158
 159     Status error;
 160     ValueObjectSP node_sp = m_next_element->Dereference(error);
 161     if (!node_sp || error.Fail())
 162       return lldb::ValueObjectSP();
 163
 164     ValueObjectSP value_sp = node_sp->GetChildMemberWithName("__value_");
 165     ValueObjectSP hash_sp = node_sp->GetChildMemberWithName("__hash_");
 166     if (!hash_sp || !value_sp) {
 167       if (!m_element_type) {
 168         m_node_type = GetNodeType();
 169         if (!m_node_type)
 170           return nullptr;
 171
 172         m_element_type = GetElementType(m_node_type);
 173       }
 174       node_sp = m_next_element->Cast(m_node_type.GetPointerType())
 175               ->Dereference(error);
 176       if (!node_sp || error.Fail())
 177           return nullptr;
 178
 179       hash_sp = node_sp->GetChildMemberWithName("__hash_");
 180       if (!hash_sp)
 181         return nullptr;
 182
 183       value_sp = node_sp->GetChildMemberWithName("__value_");
 184       if (!value_sp) {
 185         // clang-format off
 186         // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
 187         // anonymous union.
 188         // Child 0: __hash_node_base base class
 189         // Child 1: __hash_
 190         // Child 2: anonymous union
 191         // clang-format on
 192         auto anon_union_sp = node_sp->GetChildAtIndex(2);
 193         if (!anon_union_sp)
 194           return nullptr;
 195
 196         value_sp = anon_union_sp->GetChildMemberWithName("__value_");
 197         if (!value_sp)
 198           return nullptr;
 199       }
 200     }
 201     m_elements_cache.push_back(
 202         {value_sp.get(), hash_sp->GetValueAsUnsigned(0)});
 203     m_next_element = node_sp->GetChildMemberWithName("__next_").get();
 204     if (!m_next_element || m_next_element->GetValueAsUnsigned(0) == 0)
 205       m_next_element = nullptr;
 206   }
 207
 208   std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx];
 209   if (!val_hash.first)
 210     return lldb::ValueObjectSP();
 211   StreamString stream;
 212   stream.Printf("[%" PRIu64 "]", (uint64_t)idx);
 213   DataExtractor data;
 214   Status error;
 215   val_hash.first->GetData(data, error);
 216   if (error.Fail())
 217     return lldb::ValueObjectSP();
 218   const bool thread_and_frame_only_if_stopped = true;
 219   ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock(
 220       thread_and_frame_only_if_stopped);
 221   return CreateValueObjectFromData(stream.GetString(), data, exe_ctx,
 222                                    m_element_type);
 223 }
 224
 225 llvm::Expected<size_t>
 226 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
 227     CalculateNumChildrenImpl(ValueObject &table) {
 228   if (auto size_sp = table.GetChildMemberWithName("__size_"))
 229     return size_sp->GetValueAsUnsigned(0);
 230
 231   ValueObjectSP p2_sp = table.GetChildMemberWithName("__p2_");
 232   if (!p2_sp)
 233     return llvm::createStringError(
 234         "Unexpected std::unordered_map layout: __p2_ member not found.");
 235
 236   if (!isOldCompressedPairLayout(*p2_sp))
 237     return llvm::createStringError("Unexpected std::unordered_map layout: old "
 238                                    "__compressed_pair layout not found.");
 239
 240   ValueObjectSP num_elements_sp = GetFirstValueOfLibCXXCompressedPair(*p2_sp);
 241
 242   if (!num_elements_sp)
 243     return llvm::createStringError(
 244         "Unexpected std::unordered_map layout: failed to retrieve first member "
 245         "in old __compressed_pair layout.");
 246
 247   return num_elements_sp->GetValueAsUnsigned(0);
 248 }
 249
 250 static ValueObjectSP GetTreePointer(ValueObject &table) {
 251   ValueObjectSP tree_sp = table.GetChildMemberWithName("__first_node_");
 252   if (!tree_sp) {
 253     ValueObjectSP p1_sp = table.GetChildMemberWithName("__p1_");
 254     if (!p1_sp)
 255       return nullptr;
 256
 257     if (!isOldCompressedPairLayout(*p1_sp))
 258       return nullptr;
 259
 260     tree_sp = GetFirstValueOfLibCXXCompressedPair(*p1_sp);
 261     if (!tree_sp)
 262       return nullptr;
 263   }
 264
 265   return tree_sp->GetChildMemberWithName("__next_");
 266 }
 267
 268 lldb::ChildCacheState
 269 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::Update() {
 270   m_num_elements = 0;
 271   m_next_element = nullptr;
 272   m_elements_cache.clear();
 273   ValueObjectSP table_sp = m_backend.GetChildMemberWithName("__table_");
 274   if (!table_sp)
 275     return lldb::ChildCacheState::eRefetch;
 276
 277   ValueObjectSP tree_sp = GetTreePointer(*table_sp);
 278   if (!tree_sp)
 279     return lldb::ChildCacheState::eRefetch;
 280
 281   m_tree = tree_sp.get();
 282
 283   if (auto num_elems_or_err = CalculateNumChildrenImpl(*table_sp))
 284     m_num_elements = *num_elems_or_err;
 285   else {
 286     LLDB_LOG_ERRORV(GetLog(LLDBLog::DataFormatters),
 287                     num_elems_or_err.takeError(), "{0}");
 288     return lldb::ChildCacheState::eRefetch;
 289   }
 290
 291   if (m_num_elements > 0)
 292     m_next_element = m_tree;
 293
 294   return lldb::ChildCacheState::eRefetch;
 295 }
 296
 297 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
 298     MightHaveChildren() {
 299   return true;
 300 }
 301
 302 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
 303     GetIndexOfChildWithName(ConstString name) {
 304   return ExtractIndexFromString(name.GetCString());
 305 }
 306
 307 SyntheticChildrenFrontEnd *
 308 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
 309     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
 310   return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
 311                     : nullptr);
 312 }
 313
 314 lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
 315     LibCxxUnorderedMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
 316     : SyntheticChildrenFrontEnd(*valobj_sp) {
 317   if (valobj_sp)
 318     Update();
 319 }
 320
 321 lldb::ChildCacheState lldb_private::formatters::
 322     LibCxxUnorderedMapIteratorSyntheticFrontEnd::Update() {
 323   m_pair_sp.reset();
 324
 325   ValueObjectSP valobj_sp = m_backend.GetSP();
 326   if (!valobj_sp)
 327     return lldb::ChildCacheState::eRefetch;
 328
 329   TargetSP target_sp(valobj_sp->GetTargetSP());
 330
 331   if (!target_sp)
 332     return lldb::ChildCacheState::eRefetch;
 333
 334   // Get the unordered_map::iterator
 335   // m_backend is an 'unordered_map::iterator', aka a
 336   // '__hash_map_iterator<__hash_table::iterator>'
 337   //
 338   // __hash_map_iterator::__i_ is a __hash_table::iterator (aka
 339   // __hash_iterator<__node_pointer>)
 340   auto hash_iter_sp = valobj_sp->GetChildMemberWithName("__i_");
 341   if (!hash_iter_sp)
 342     return lldb::ChildCacheState::eRefetch;
 343
 344   // Type is '__hash_iterator<__node_pointer>'
 345   auto hash_iter_type = hash_iter_sp->GetCompilerType();
 346   if (!hash_iter_type.IsValid())
 347     return lldb::ChildCacheState::eRefetch;
 348
 349   // Type is '__node_pointer'
 350   auto node_pointer_type = hash_iter_type.GetTypeTemplateArgument(0);
 351   if (!node_pointer_type.IsValid())
 352     return lldb::ChildCacheState::eRefetch;
 353
 354   // Cast the __hash_iterator to a __node_pointer (which stores our key/value
 355   // pair)
 356   auto hash_node_sp = hash_iter_sp->Cast(node_pointer_type);
 357   if (!hash_node_sp)
 358     return lldb::ChildCacheState::eRefetch;
 359
 360   auto key_value_sp = hash_node_sp->GetChildMemberWithName("__value_");
 361   if (!key_value_sp) {
 362     // clang-format off
 363     // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an
 364     // anonymous union.
 365     // Child 0: __hash_node_base base class
 366     // Child 1: __hash_
 367     // Child 2: anonymous union
 368     // clang-format on
 369     auto anon_union_sp = hash_node_sp->GetChildAtIndex(2);
 370     if (!anon_union_sp)
 371       return lldb::ChildCacheState::eRefetch;
 372
 373     key_value_sp = anon_union_sp->GetChildMemberWithName("__value_");
 374     if (!key_value_sp)
 375       return lldb::ChildCacheState::eRefetch;
 376   }
 377
 378   // Create the synthetic child, which is a pair where the key and value can be
 379   // retrieved by querying the synthetic frontend for
 380   // GetIndexOfChildWithName("first") and GetIndexOfChildWithName("second")
 381   // respectively.
 382   //
 383   // std::unordered_map stores the actual key/value pair in
 384   // __hash_value_type::__cc_ (or previously __cc).
 385   auto potential_child_sp = key_value_sp->Clone(ConstString("pair"));
 386   if (potential_child_sp)
 387     if (potential_child_sp->GetNumChildrenIgnoringErrors() == 1)
 388       if (auto child0_sp = potential_child_sp->GetChildAtIndex(0);
 389           child0_sp->GetName() == "__cc_" || child0_sp->GetName() == "__cc")
 390         potential_child_sp = child0_sp->Clone(ConstString("pair"));
 391
 392   m_pair_sp = potential_child_sp;
 393
 394   return lldb::ChildCacheState::eRefetch;
 395 }
 396
 397 llvm::Expected<uint32_t> lldb_private::formatters::
 398     LibCxxUnorderedMapIteratorSyntheticFrontEnd::CalculateNumChildren() {
 399   return 2;
 400 }
 401
 402 lldb::ValueObjectSP lldb_private::formatters::
 403     LibCxxUnorderedMapIteratorSyntheticFrontEnd::GetChildAtIndex(uint32_t idx) {
 404   if (m_pair_sp)
 405     return m_pair_sp->GetChildAtIndex(idx);
 406   return lldb::ValueObjectSP();
 407 }
 408
 409 bool lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
 410     MightHaveChildren() {
 411   return true;
 412 }
 413
 414 size_t lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEnd::
 415     GetIndexOfChildWithName(ConstString name) {
 416   if (name == "first")
 417     return 0;
 418   if (name == "second")
 419     return 1;
 420   return UINT32_MAX;
 421 }
 422
 423 SyntheticChildrenFrontEnd *
 424 lldb_private::formatters::LibCxxUnorderedMapIteratorSyntheticFrontEndCreator(
 425     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
 426   return (valobj_sp ? new LibCxxUnorderedMapIteratorSyntheticFrontEnd(valobj_sp)
 427                     : nullptr);
 428 }