1 //===-- LibCxxList.cpp -------------------------------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "lldb/lldb-python.h"
11
12 #include "lldb/DataFormatters/CXXFormatterFunctions.h"
13
14 #include "lldb/Core/DataBufferHeap.h"
15 #include "lldb/Core/Error.h"
16 #include "lldb/Core/Stream.h"
17 #include "lldb/Core/ValueObject.h"
18 #include "lldb/Core/ValueObjectConstResult.h"
19 #include "lldb/Host/Endian.h"
20 #include "lldb/Symbol/ClangASTContext.h"
21 #include "lldb/Target/ObjCLanguageRuntime.h"
22 #include "lldb/Target/Target.h"
23
24 using namespace lldb;
25 using namespace lldb_private;
26 using namespace lldb_private::formatters;
27
28 class MapEntry
29 {
30 public:
MapEntry()31 MapEntry () {}
MapEntry(ValueObjectSP entry_sp)32 MapEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
MapEntry(const MapEntry & rhs)33 MapEntry (const MapEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {}
MapEntry(ValueObject * entry)34 MapEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
35
36 ValueObjectSP
left()37 left ()
38 {
39 if (!m_entry_sp)
40 return m_entry_sp;
41 return m_entry_sp->GetChildMemberWithName(ConstString("__left_"), true);
42 }
43
44 ValueObjectSP
right()45 right ()
46 {
47 if (!m_entry_sp)
48 return m_entry_sp;
49 return m_entry_sp->GetChildMemberWithName(ConstString("__right_"), true);
50 }
51
52 ValueObjectSP
parent()53 parent ()
54 {
55 if (!m_entry_sp)
56 return m_entry_sp;
57 return m_entry_sp->GetChildMemberWithName(ConstString("__parent_"), true);
58 }
59
60 uint64_t
value()61 value ()
62 {
63 if (!m_entry_sp)
64 return 0;
65 return m_entry_sp->GetValueAsUnsigned(0);
66 }
67
68 bool
error()69 error ()
70 {
71 if (!m_entry_sp)
72 return true;
73 return m_entry_sp->GetError().Fail();
74 }
75
76 bool
null()77 null()
78 {
79 return (value() == 0);
80 }
81
82 ValueObjectSP
GetEntry()83 GetEntry ()
84 {
85 return m_entry_sp;
86 }
87
88 void
SetEntry(ValueObjectSP entry)89 SetEntry (ValueObjectSP entry)
90 {
91 m_entry_sp = entry;
92 }
93
94 bool
operator ==(const MapEntry & rhs) const95 operator == (const MapEntry& rhs) const
96 {
97 return (rhs.m_entry_sp.get() == m_entry_sp.get());
98 }
99
100 private:
101 ValueObjectSP m_entry_sp;
102 };
103
104 class MapIterator
105 {
106 public:
MapIterator()107 MapIterator () {}
MapIterator(MapEntry entry,size_t depth=0)108 MapIterator (MapEntry entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {}
MapIterator(ValueObjectSP entry,size_t depth=0)109 MapIterator (ValueObjectSP entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {}
MapIterator(const MapIterator & rhs)110 MapIterator (const MapIterator& rhs) : m_entry(rhs.m_entry),m_max_depth(rhs.m_max_depth), m_error(false) {}
MapIterator(ValueObject * entry,size_t depth=0)111 MapIterator (ValueObject* entry, size_t depth = 0) : m_entry(entry), m_max_depth(depth), m_error(false) {}
112
113 ValueObjectSP
value()114 value ()
115 {
116 return m_entry.GetEntry();
117 }
118
119 ValueObjectSP
advance(size_t count)120 advance (size_t count)
121 {
122 if (m_error)
123 return lldb::ValueObjectSP();
124 if (count == 0)
125 return m_entry.GetEntry();
126 if (count == 1)
127 {
128 next ();
129 return m_entry.GetEntry();
130 }
131 size_t steps = 0;
132 while (count > 0)
133 {
134 if (m_error)
135 return lldb::ValueObjectSP();
136 next ();
137 count--;
138 if (m_entry.null())
139 return lldb::ValueObjectSP();
140 steps++;
141 if (steps > m_max_depth)
142 return lldb::ValueObjectSP();
143 }
144 return m_entry.GetEntry();
145 }
146 protected:
147 void
next()148 next ()
149 {
150 m_entry.SetEntry(increment(m_entry.GetEntry()));
151 }
152
153 private:
154 ValueObjectSP
tree_min(ValueObjectSP x_sp)155 tree_min (ValueObjectSP x_sp)
156 {
157 MapEntry x(x_sp);
158 if (x.null())
159 return ValueObjectSP();
160 MapEntry left(x.left());
161 size_t steps = 0;
162 while (left.null() == false)
163 {
164 if (left.error())
165 {
166 m_error = true;
167 return lldb::ValueObjectSP();
168 }
169 x.SetEntry(left.GetEntry());
170 left.SetEntry(x.left());
171 steps++;
172 if (steps > m_max_depth)
173 return lldb::ValueObjectSP();
174 }
175 return x.GetEntry();
176 }
177
178 ValueObjectSP
tree_max(ValueObjectSP x_sp)179 tree_max (ValueObjectSP x_sp)
180 {
181 MapEntry x(x_sp);
182 if (x.null())
183 return ValueObjectSP();
184 MapEntry right(x.right());
185 size_t steps = 0;
186 while (right.null() == false)
187 {
188 if (right.error())
189 return lldb::ValueObjectSP();
190 x.SetEntry(right.GetEntry());
191 right.SetEntry(x.right());
192 steps++;
193 if (steps > m_max_depth)
194 return lldb::ValueObjectSP();
195 }
196 return x.GetEntry();
197 }
198
199 bool
is_left_child(ValueObjectSP x_sp)200 is_left_child (ValueObjectSP x_sp)
201 {
202 MapEntry x(x_sp);
203 if (x.null())
204 return false;
205 MapEntry rhs(x.parent());
206 rhs.SetEntry(rhs.left());
207 return x.value() == rhs.value();
208 }
209
210 ValueObjectSP
increment(ValueObjectSP x_sp)211 increment (ValueObjectSP x_sp)
212 {
213 MapEntry node(x_sp);
214 if (node.null())
215 return ValueObjectSP();
216 MapEntry right(node.right());
217 if (right.null() == false)
218 return tree_min(right.GetEntry());
219 size_t steps = 0;
220 while (!is_left_child(node.GetEntry()))
221 {
222 if (node.error())
223 {
224 m_error = true;
225 return lldb::ValueObjectSP();
226 }
227 node.SetEntry(node.parent());
228 steps++;
229 if (steps > m_max_depth)
230 return lldb::ValueObjectSP();
231 }
232 return node.parent();
233 }
234
235 MapEntry m_entry;
236 size_t m_max_depth;
237 bool m_error;
238 };
239
LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)240 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::LibcxxStdMapSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) :
241 SyntheticChildrenFrontEnd(*valobj_sp.get()),
242 m_tree(NULL),
243 m_root_node(NULL),
244 m_element_type(),
245 m_skip_size(UINT32_MAX),
246 m_count(UINT32_MAX),
247 m_children()
248 {
249 if (valobj_sp)
250 Update();
251 }
252
253 size_t
CalculateNumChildren()254 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren ()
255 {
256 if (m_count != UINT32_MAX)
257 return m_count;
258 if (m_tree == NULL)
259 return 0;
260 ValueObjectSP m_item(m_tree->GetChildMemberWithName(ConstString("__pair3_"), true));
261 if (!m_item)
262 return 0;
263 m_item = m_item->GetChildMemberWithName(ConstString("__first_"), true);
264 if (!m_item)
265 return 0;
266 m_count = m_item->GetValueAsUnsigned(0);
267 return m_count;
268 }
269
270 bool
GetDataType()271 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType()
272 {
273 if (m_element_type.GetOpaqueQualType() && m_element_type.GetASTContext())
274 return true;
275 m_element_type.Clear();
276 ValueObjectSP deref;
277 Error error;
278 deref = m_root_node->Dereference(error);
279 if (!deref || error.Fail())
280 return false;
281 deref = deref->GetChildMemberWithName(ConstString("__value_"), true);
282 if (!deref)
283 return false;
284 m_element_type = deref->GetClangType();
285 return true;
286 }
287
288 void
GetValueOffset(const lldb::ValueObjectSP & node)289 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset (const lldb::ValueObjectSP& node)
290 {
291 if (m_skip_size != UINT32_MAX)
292 return;
293 if (!node)
294 return;
295 ClangASTType node_type(node->GetClangType());
296 uint64_t bit_offset;
297 if (node_type.GetIndexOfFieldWithName("__value_", NULL, &bit_offset) == UINT32_MAX)
298 return;
299 m_skip_size = bit_offset / 8u;
300 }
301
302 lldb::ValueObjectSP
GetChildAtIndex(size_t idx)303 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex (size_t idx)
304 {
305 if (idx >= CalculateNumChildren())
306 return lldb::ValueObjectSP();
307 if (m_tree == NULL || m_root_node == NULL)
308 return lldb::ValueObjectSP();
309
310 auto cached = m_children.find(idx);
311 if (cached != m_children.end())
312 return cached->second;
313
314 bool need_to_skip = (idx > 0);
315 MapIterator iterator(m_root_node, CalculateNumChildren());
316 ValueObjectSP iterated_sp(iterator.advance(idx));
317 if (iterated_sp.get() == NULL)
318 {
319 // this tree is garbage - stop
320 m_tree = NULL; // this will stop all future searches until an Update() happens
321 return iterated_sp;
322 }
323 if (GetDataType())
324 {
325 if (!need_to_skip)
326 {
327 Error error;
328 iterated_sp = iterated_sp->Dereference(error);
329 if (!iterated_sp || error.Fail())
330 {
331 m_tree = NULL;
332 return lldb::ValueObjectSP();
333 }
334 GetValueOffset(iterated_sp);
335 iterated_sp = iterated_sp->GetChildMemberWithName(ConstString("__value_"), true);
336 if (!iterated_sp)
337 {
338 m_tree = NULL;
339 return lldb::ValueObjectSP();
340 }
341 }
342 else
343 {
344 // because of the way our debug info is made, we need to read item 0 first
345 // so that we can cache information used to generate other elements
346 if (m_skip_size == UINT32_MAX)
347 GetChildAtIndex(0);
348 if (m_skip_size == UINT32_MAX)
349 {
350 m_tree = NULL;
351 return lldb::ValueObjectSP();
352 }
353 iterated_sp = iterated_sp->GetSyntheticChildAtOffset(m_skip_size, m_element_type, true);
354 if (!iterated_sp)
355 {
356 m_tree = NULL;
357 return lldb::ValueObjectSP();
358 }
359 }
360 }
361 else
362 {
363 m_tree = NULL;
364 return lldb::ValueObjectSP();
365 }
366 // at this point we have a valid
367 // we need to copy current_sp into a new object otherwise we will end up with all items named __value_
368 DataExtractor data;
369 iterated_sp->GetData(data);
370 StreamString name;
371 name.Printf("[%zu]",idx);
372 return (m_children[idx] = ValueObject::CreateValueObjectFromData(name.GetData(), data, m_backend.GetExecutionContextRef(), m_element_type));
373 }
374
375 bool
Update()376 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update()
377 {
378 m_count = UINT32_MAX;
379 m_tree = m_root_node = NULL;
380 m_children.clear();
381 m_tree = m_backend.GetChildMemberWithName(ConstString("__tree_"), true).get();
382 if (!m_tree)
383 return false;
384 m_root_node = m_tree->GetChildMemberWithName(ConstString("__begin_node_"), true).get();
385 return false;
386 }
387
388 bool
MightHaveChildren()389 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::MightHaveChildren ()
390 {
391 return true;
392 }
393
394 size_t
GetIndexOfChildWithName(const ConstString & name)395 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name)
396 {
397 return ExtractIndexFromString(name.GetCString());
398 }
399
~LibcxxStdMapSyntheticFrontEnd()400 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::~LibcxxStdMapSyntheticFrontEnd ()
401 {}
402
403 SyntheticChildrenFrontEnd*
LibcxxStdMapSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)404 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp)
405 {
406 if (!valobj_sp)
407 return NULL;
408 return (new LibcxxStdMapSyntheticFrontEnd(valobj_sp));
409 }
410