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