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/Core/ValueObject.h" 13 #include "lldb/Core/ValueObjectConstResult.h" 14 #include "lldb/DataFormatters/FormattersHelpers.h" 15 #include "lldb/Target/Target.h" 16 #include "lldb/Utility/ConstString.h" 17 #include "lldb/Utility/DataBufferHeap.h" 18 #include "lldb/Utility/Endian.h" 19 #include "lldb/Utility/Status.h" 20 #include "lldb/Utility/Stream.h" 21 #include "llvm/ADT/StringRef.h" 22 23 using namespace lldb; 24 using namespace lldb_private; 25 using namespace lldb_private::formatters; 26 27 namespace lldb_private { 28 namespace formatters { 29 class LibcxxStdUnorderedMapSyntheticFrontEnd 30 : public SyntheticChildrenFrontEnd { 31 public: 32 LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); 33 34 ~LibcxxStdUnorderedMapSyntheticFrontEnd() override = default; 35 36 size_t CalculateNumChildren() override; 37 38 lldb::ValueObjectSP GetChildAtIndex(size_t idx) override; 39 40 bool Update() override; 41 42 bool MightHaveChildren() override; 43 44 size_t GetIndexOfChildWithName(ConstString name) override; 45 46 private: 47 CompilerType m_element_type; 48 CompilerType m_node_type; 49 ValueObject *m_tree = nullptr; 50 size_t m_num_elements = 0; 51 ValueObject *m_next_element = nullptr; 52 std::vector<std::pair<ValueObject *, uint64_t>> m_elements_cache; 53 }; 54 } // namespace formatters 55 } // namespace lldb_private 56 57 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd:: 58 LibcxxStdUnorderedMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) 59 : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(), 60 m_elements_cache() { 61 if (valobj_sp) 62 Update(); 63 } 64 65 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd:: 66 CalculateNumChildren() { 67 return m_num_elements; 68 } 69 70 static void consumeInlineNamespace(llvm::StringRef &name) { 71 // Delete past an inline namespace, if any: __[a-zA-Z0-9_]+:: 72 auto scratch = name; 73 if (scratch.consume_front("__") && std::isalnum(scratch[0])) { 74 scratch = scratch.drop_while([](char c) { return std::isalnum(c); }); 75 if (scratch.consume_front("::")) { 76 // Successfully consumed a namespace. 77 name = scratch; 78 } 79 } 80 } 81 82 static bool isStdTemplate(ConstString type_name, llvm::StringRef type) { 83 llvm::StringRef name = type_name.GetStringRef(); 84 // The type name may be prefixed with `std::__<inline-namespace>::`. 85 if (name.consume_front("std::")) 86 consumeInlineNamespace(name); 87 return name.consume_front(type) && name.starts_with("<"); 88 } 89 90 static bool isUnorderedMap(ConstString type_name) { 91 return isStdTemplate(type_name, "unordered_map") || 92 isStdTemplate(type_name, "unordered_multimap"); 93 } 94 95 lldb::ValueObjectSP lldb_private::formatters:: 96 LibcxxStdUnorderedMapSyntheticFrontEnd::GetChildAtIndex(size_t idx) { 97 if (idx >= CalculateNumChildren()) 98 return lldb::ValueObjectSP(); 99 if (m_tree == nullptr) 100 return lldb::ValueObjectSP(); 101 102 while (idx >= m_elements_cache.size()) { 103 if (m_next_element == nullptr) 104 return lldb::ValueObjectSP(); 105 106 Status error; 107 ValueObjectSP node_sp = m_next_element->Dereference(error); 108 if (!node_sp || error.Fail()) 109 return lldb::ValueObjectSP(); 110 111 ValueObjectSP value_sp = node_sp->GetChildMemberWithName("__value_"); 112 ValueObjectSP hash_sp = node_sp->GetChildMemberWithName("__hash_"); 113 if (!hash_sp || !value_sp) { 114 if (!m_element_type) { 115 auto p1_sp = m_backend.GetChildAtNamePath({"__table_", "__p1_"}); 116 if (!p1_sp) 117 return nullptr; 118 119 ValueObjectSP first_sp = nullptr; 120 switch (p1_sp->GetCompilerType().GetNumDirectBaseClasses()) { 121 case 1: 122 // Assume a pre llvm r300140 __compressed_pair implementation: 123 first_sp = p1_sp->GetChildMemberWithName("__first_"); 124 break; 125 case 2: { 126 // Assume a post llvm r300140 __compressed_pair implementation: 127 ValueObjectSP first_elem_parent_sp = 128 p1_sp->GetChildAtIndex(0); 129 first_sp = p1_sp->GetChildMemberWithName("__value_"); 130 break; 131 } 132 default: 133 return nullptr; 134 } 135 136 if (!first_sp) 137 return nullptr; 138 m_element_type = first_sp->GetCompilerType(); 139 m_element_type = m_element_type.GetTypeTemplateArgument(0); 140 m_element_type = m_element_type.GetPointeeType(); 141 m_node_type = m_element_type; 142 m_element_type = m_element_type.GetTypeTemplateArgument(0); 143 // This synthetic provider is used for both unordered_(multi)map and 144 // unordered_(multi)set. For unordered_map, the element type has an 145 // additional type layer, an internal struct (`__hash_value_type`) 146 // that wraps a std::pair. Peel away the internal wrapper type - whose 147 // structure is of no value to users, to expose the std::pair. This 148 // matches the structure returned by the std::map synthetic provider. 149 if (isUnorderedMap(m_backend.GetTypeName())) { 150 std::string name; 151 CompilerType field_type = m_element_type.GetFieldAtIndex( 152 0, name, nullptr, nullptr, nullptr); 153 CompilerType actual_type = field_type.GetTypedefedType(); 154 if (isStdTemplate(actual_type.GetTypeName(), "pair")) 155 m_element_type = actual_type; 156 } 157 } 158 if (!m_node_type) 159 return nullptr; 160 node_sp = m_next_element->Cast(m_node_type.GetPointerType()) 161 ->Dereference(error); 162 if (!node_sp || error.Fail()) 163 return nullptr; 164 165 hash_sp = node_sp->GetChildMemberWithName("__hash_"); 166 if (!hash_sp) 167 return nullptr; 168 169 value_sp = node_sp->GetChildMemberWithName("__value_"); 170 if (!value_sp) { 171 // clang-format off 172 // Since D101206 (ba79fb2e1f), libc++ wraps the `__value_` in an 173 // anonymous union. 174 // Child 0: __hash_node_base base class 175 // Child 1: __hash_ 176 // Child 2: anonymous union 177 // clang-format on 178 auto anon_union_sp = node_sp->GetChildAtIndex(2); 179 if (!anon_union_sp) 180 return nullptr; 181 182 value_sp = anon_union_sp->GetChildMemberWithName("__value_"); 183 if (!value_sp) 184 return nullptr; 185 } 186 } 187 m_elements_cache.push_back( 188 {value_sp.get(), hash_sp->GetValueAsUnsigned(0)}); 189 m_next_element = node_sp->GetChildMemberWithName("__next_").get(); 190 if (!m_next_element || m_next_element->GetValueAsUnsigned(0) == 0) 191 m_next_element = nullptr; 192 } 193 194 std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx]; 195 if (!val_hash.first) 196 return lldb::ValueObjectSP(); 197 StreamString stream; 198 stream.Printf("[%" PRIu64 "]", (uint64_t)idx); 199 DataExtractor data; 200 Status error; 201 val_hash.first->GetData(data, error); 202 if (error.Fail()) 203 return lldb::ValueObjectSP(); 204 const bool thread_and_frame_only_if_stopped = true; 205 ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock( 206 thread_and_frame_only_if_stopped); 207 return CreateValueObjectFromData(stream.GetString(), data, exe_ctx, 208 m_element_type); 209 } 210 211 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd:: 212 Update() { 213 m_num_elements = 0; 214 m_next_element = nullptr; 215 m_elements_cache.clear(); 216 ValueObjectSP table_sp = m_backend.GetChildMemberWithName("__table_"); 217 if (!table_sp) 218 return false; 219 220 ValueObjectSP p2_sp = table_sp->GetChildMemberWithName("__p2_"); 221 ValueObjectSP num_elements_sp = nullptr; 222 llvm::SmallVector<llvm::StringRef, 3> next_path; 223 switch (p2_sp->GetCompilerType().GetNumDirectBaseClasses()) { 224 case 1: 225 // Assume a pre llvm r300140 __compressed_pair implementation: 226 num_elements_sp = p2_sp->GetChildMemberWithName("__first_"); 227 next_path.append({"__p1_", "__first_", "__next_"}); 228 break; 229 case 2: { 230 // Assume a post llvm r300140 __compressed_pair implementation: 231 ValueObjectSP first_elem_parent = p2_sp->GetChildAtIndex(0); 232 num_elements_sp = first_elem_parent->GetChildMemberWithName("__value_"); 233 next_path.append({"__p1_", "__value_", "__next_"}); 234 break; 235 } 236 default: 237 return false; 238 } 239 240 if (!num_elements_sp) 241 return false; 242 243 m_tree = table_sp->GetChildAtNamePath(next_path).get(); 244 if (m_tree == nullptr) 245 return false; 246 247 m_num_elements = num_elements_sp->GetValueAsUnsigned(0); 248 249 if (m_num_elements > 0) 250 m_next_element = 251 table_sp->GetChildAtNamePath(next_path).get(); 252 return false; 253 } 254 255 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd:: 256 MightHaveChildren() { 257 return true; 258 } 259 260 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd:: 261 GetIndexOfChildWithName(ConstString name) { 262 return ExtractIndexFromString(name.GetCString()); 263 } 264 265 SyntheticChildrenFrontEnd * 266 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator( 267 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 268 return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp) 269 : nullptr); 270 } 271