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.startswith("<");
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 =
112         node_sp->GetChildMemberWithName(ConstString("__value_"), true);
113     ValueObjectSP hash_sp =
114         node_sp->GetChildMemberWithName(ConstString("__hash_"), true);
115     if (!hash_sp || !value_sp) {
116       if (!m_element_type) {
117         auto p1_sp = m_backend.GetChildAtNamePath({ConstString("__table_"),
118                                                    ConstString("__p1_")});
119         if (!p1_sp)
120           return nullptr;
121 
122         ValueObjectSP first_sp = nullptr;
123         switch (p1_sp->GetCompilerType().GetNumDirectBaseClasses()) {
124         case 1:
125           // Assume a pre llvm r300140 __compressed_pair implementation:
126           first_sp = p1_sp->GetChildMemberWithName(ConstString("__first_"),
127                                                    true);
128           break;
129         case 2: {
130           // Assume a post llvm r300140 __compressed_pair implementation:
131           ValueObjectSP first_elem_parent_sp =
132             p1_sp->GetChildAtIndex(0, true);
133           first_sp = p1_sp->GetChildMemberWithName(ConstString("__value_"),
134                                                    true);
135           break;
136         }
137         default:
138           return nullptr;
139         }
140 
141         if (!first_sp)
142           return nullptr;
143         m_element_type = first_sp->GetCompilerType();
144         m_element_type = m_element_type.GetTypeTemplateArgument(0);
145         m_element_type = m_element_type.GetPointeeType();
146         m_node_type = m_element_type;
147         m_element_type = m_element_type.GetTypeTemplateArgument(0);
148         // This synthetic provider is used for both unordered_(multi)map and
149         // unordered_(multi)set. For unordered_map, the element type has an
150         // additional type layer, an internal struct (`__hash_value_type`)
151         // that wraps a std::pair. Peel away the internal wrapper type - whose
152         // structure is of no value to users, to expose the std::pair. This
153         // matches the structure returned by the std::map synthetic provider.
154         if (isUnorderedMap(m_backend.GetTypeName())) {
155           std::string name;
156           CompilerType field_type = m_element_type.GetFieldAtIndex(
157               0, name, nullptr, nullptr, nullptr);
158           CompilerType actual_type = field_type.GetTypedefedType();
159           if (isStdTemplate(actual_type.GetTypeName(), "pair"))
160             m_element_type = actual_type;
161         }
162       }
163       if (!m_node_type)
164         return nullptr;
165       node_sp = node_sp->Cast(m_node_type);
166       value_sp = node_sp->GetChildMemberWithName(ConstString("__value_"), true);
167       hash_sp = node_sp->GetChildMemberWithName(ConstString("__hash_"), true);
168       if (!value_sp || !hash_sp)
169         return nullptr;
170     }
171     m_elements_cache.push_back(
172         {value_sp.get(), hash_sp->GetValueAsUnsigned(0)});
173     m_next_element =
174         node_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
175     if (!m_next_element || m_next_element->GetValueAsUnsigned(0) == 0)
176       m_next_element = nullptr;
177   }
178 
179   std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx];
180   if (!val_hash.first)
181     return lldb::ValueObjectSP();
182   StreamString stream;
183   stream.Printf("[%" PRIu64 "]", (uint64_t)idx);
184   DataExtractor data;
185   Status error;
186   val_hash.first->GetData(data, error);
187   if (error.Fail())
188     return lldb::ValueObjectSP();
189   const bool thread_and_frame_only_if_stopped = true;
190   ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock(
191       thread_and_frame_only_if_stopped);
192   return CreateValueObjectFromData(stream.GetString(), data, exe_ctx,
193                                    m_element_type);
194 }
195 
196 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
197     Update() {
198   m_num_elements = 0;
199   m_next_element = nullptr;
200   m_elements_cache.clear();
201   ValueObjectSP table_sp =
202       m_backend.GetChildMemberWithName(ConstString("__table_"), true);
203   if (!table_sp)
204     return false;
205 
206   ValueObjectSP p2_sp = table_sp->GetChildMemberWithName(
207     ConstString("__p2_"), true);
208   ValueObjectSP num_elements_sp = nullptr;
209   llvm::SmallVector<ConstString, 3> next_path;
210   switch (p2_sp->GetCompilerType().GetNumDirectBaseClasses()) {
211   case 1:
212     // Assume a pre llvm r300140 __compressed_pair implementation:
213     num_elements_sp = p2_sp->GetChildMemberWithName(
214       ConstString("__first_"), true);
215     next_path.append({ConstString("__p1_"), ConstString("__first_"),
216                       ConstString("__next_")});
217     break;
218   case 2: {
219     // Assume a post llvm r300140 __compressed_pair implementation:
220     ValueObjectSP first_elem_parent = p2_sp->GetChildAtIndex(0, true);
221     num_elements_sp = first_elem_parent->GetChildMemberWithName(
222       ConstString("__value_"), true);
223     next_path.append({ConstString("__p1_"), ConstString("__value_"),
224                       ConstString("__next_")});
225     break;
226   }
227   default:
228     return false;
229   }
230 
231   if (!num_elements_sp)
232     return false;
233 
234   m_tree = table_sp->GetChildAtNamePath(next_path).get();
235   if (m_tree == nullptr)
236     return false;
237 
238   m_num_elements = num_elements_sp->GetValueAsUnsigned(0);
239 
240   if (m_num_elements > 0)
241     m_next_element =
242         table_sp->GetChildAtNamePath(next_path).get();
243   return false;
244 }
245 
246 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
247     MightHaveChildren() {
248   return true;
249 }
250 
251 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
252     GetIndexOfChildWithName(ConstString name) {
253   return ExtractIndexFromString(name.GetCString());
254 }
255 
256 SyntheticChildrenFrontEnd *
257 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
258     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
259   return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
260                     : nullptr);
261 }
262