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 = 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       value_sp = node_sp->GetChildMemberWithName("__value_");
166       hash_sp = node_sp->GetChildMemberWithName("__hash_");
167       if (!value_sp || !hash_sp)
168         return nullptr;
169     }
170     m_elements_cache.push_back(
171         {value_sp.get(), hash_sp->GetValueAsUnsigned(0)});
172     m_next_element = node_sp->GetChildMemberWithName("__next_").get();
173     if (!m_next_element || m_next_element->GetValueAsUnsigned(0) == 0)
174       m_next_element = nullptr;
175   }
176 
177   std::pair<ValueObject *, uint64_t> val_hash = m_elements_cache[idx];
178   if (!val_hash.first)
179     return lldb::ValueObjectSP();
180   StreamString stream;
181   stream.Printf("[%" PRIu64 "]", (uint64_t)idx);
182   DataExtractor data;
183   Status error;
184   val_hash.first->GetData(data, error);
185   if (error.Fail())
186     return lldb::ValueObjectSP();
187   const bool thread_and_frame_only_if_stopped = true;
188   ExecutionContext exe_ctx = val_hash.first->GetExecutionContextRef().Lock(
189       thread_and_frame_only_if_stopped);
190   return CreateValueObjectFromData(stream.GetString(), data, exe_ctx,
191                                    m_element_type);
192 }
193 
194 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
195     Update() {
196   m_num_elements = 0;
197   m_next_element = nullptr;
198   m_elements_cache.clear();
199   ValueObjectSP table_sp = m_backend.GetChildMemberWithName("__table_");
200   if (!table_sp)
201     return false;
202 
203   ValueObjectSP p2_sp = table_sp->GetChildMemberWithName("__p2_");
204   ValueObjectSP num_elements_sp = nullptr;
205   llvm::SmallVector<llvm::StringRef, 3> next_path;
206   switch (p2_sp->GetCompilerType().GetNumDirectBaseClasses()) {
207   case 1:
208     // Assume a pre llvm r300140 __compressed_pair implementation:
209     num_elements_sp = p2_sp->GetChildMemberWithName("__first_");
210     next_path.append({"__p1_", "__first_", "__next_"});
211     break;
212   case 2: {
213     // Assume a post llvm r300140 __compressed_pair implementation:
214     ValueObjectSP first_elem_parent = p2_sp->GetChildAtIndex(0);
215     num_elements_sp = first_elem_parent->GetChildMemberWithName("__value_");
216     next_path.append({"__p1_", "__value_", "__next_"});
217     break;
218   }
219   default:
220     return false;
221   }
222 
223   if (!num_elements_sp)
224     return false;
225 
226   m_tree = table_sp->GetChildAtNamePath(next_path).get();
227   if (m_tree == nullptr)
228     return false;
229 
230   m_num_elements = num_elements_sp->GetValueAsUnsigned(0);
231 
232   if (m_num_elements > 0)
233     m_next_element =
234         table_sp->GetChildAtNamePath(next_path).get();
235   return false;
236 }
237 
238 bool lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
239     MightHaveChildren() {
240   return true;
241 }
242 
243 size_t lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEnd::
244     GetIndexOfChildWithName(ConstString name) {
245   return ExtractIndexFromString(name.GetCString());
246 }
247 
248 SyntheticChildrenFrontEnd *
249 lldb_private::formatters::LibcxxStdUnorderedMapSyntheticFrontEndCreator(
250     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
251   return (valobj_sp ? new LibcxxStdUnorderedMapSyntheticFrontEnd(valobj_sp)
252                     : nullptr);
253 }
254