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 "LibCxx.h"
11 
12 #include "lldb/Core/DataBufferHeap.h"
13 #include "lldb/Core/Error.h"
14 #include "lldb/Core/Stream.h"
15 #include "lldb/Core/ValueObject.h"
16 #include "lldb/Core/ValueObjectConstResult.h"
17 #include "lldb/DataFormatters/FormattersHelpers.h"
18 #include "lldb/Host/Endian.h"
19 #include "lldb/Symbol/ClangASTContext.h"
20 #include "lldb/Target/Target.h"
21 
22 using namespace lldb;
23 using namespace lldb_private;
24 using namespace lldb_private::formatters;
25 
26 namespace lldb_private {
27     namespace formatters {
28         class LibcxxStdListSyntheticFrontEnd : public SyntheticChildrenFrontEnd
29         {
30         public:
31             LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp);
32 
33             virtual size_t
34             CalculateNumChildren ();
35 
36             virtual lldb::ValueObjectSP
37             GetChildAtIndex (size_t idx);
38 
39             virtual bool
40             Update();
41 
42             virtual bool
43             MightHaveChildren ();
44 
45             virtual size_t
46             GetIndexOfChildWithName (const ConstString &name);
47 
48             virtual
49             ~LibcxxStdListSyntheticFrontEnd ();
50         private:
51             bool
52             HasLoop(size_t);
53 
54             size_t m_list_capping_size;
55             static const bool g_use_loop_detect = true;
56             size_t m_loop_detected;
57             lldb::addr_t m_node_address;
58             ValueObject* m_head;
59             ValueObject* m_tail;
60             CompilerType m_element_type;
61             size_t m_count;
62             std::map<size_t,lldb::ValueObjectSP> m_children;
63         };
64     }
65 }
66 
67 class ListEntry
68 {
69 public:
70     ListEntry () {}
71     ListEntry (ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
72     ListEntry (const ListEntry& rhs) : m_entry_sp(rhs.m_entry_sp) {}
73     ListEntry (ValueObject* entry) : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
74 
75     ListEntry
76     next ()
77     {
78         if (!m_entry_sp)
79             return ListEntry();
80         return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__next_"), true));
81     }
82 
83     ListEntry
84     prev ()
85     {
86         if (!m_entry_sp)
87             return ListEntry();
88         return ListEntry(m_entry_sp->GetChildMemberWithName(ConstString("__prev_"), true));
89     }
90 
91     uint64_t
92     value ()
93     {
94         if (!m_entry_sp)
95             return 0;
96         return m_entry_sp->GetValueAsUnsigned(0);
97     }
98 
99     bool
100     null()
101     {
102         return (value() == 0);
103     }
104 
105     explicit operator bool ()
106     {
107         return GetEntry().get() != nullptr && null() == false;
108     }
109 
110     ValueObjectSP
111     GetEntry ()
112     {
113         return m_entry_sp;
114     }
115 
116     void
117     SetEntry (ValueObjectSP entry)
118     {
119         m_entry_sp = entry;
120     }
121 
122     bool
123     operator == (const ListEntry& rhs) const
124     {
125         return (rhs.m_entry_sp.get() == m_entry_sp.get());
126     }
127 
128 private:
129     ValueObjectSP m_entry_sp;
130 };
131 
132 class ListIterator
133 {
134 public:
135     ListIterator () {}
136     ListIterator (ListEntry entry) : m_entry(entry) {}
137     ListIterator (ValueObjectSP entry) : m_entry(entry) {}
138     ListIterator (const ListIterator& rhs) : m_entry(rhs.m_entry) {}
139     ListIterator (ValueObject* entry) : m_entry(entry) {}
140 
141     ValueObjectSP
142     value ()
143     {
144         return m_entry.GetEntry();
145     }
146 
147     ValueObjectSP
148     advance (size_t count)
149     {
150         if (count == 0)
151             return m_entry.GetEntry();
152         if (count == 1)
153         {
154             next ();
155             return m_entry.GetEntry();
156         }
157         while (count > 0)
158         {
159             next ();
160             count--;
161             if (m_entry.null())
162                 return lldb::ValueObjectSP();
163         }
164         return m_entry.GetEntry();
165     }
166 
167     bool
168     operator == (const ListIterator& rhs) const
169     {
170         return (rhs.m_entry == m_entry);
171     }
172 
173 protected:
174     void
175     next ()
176     {
177         m_entry = m_entry.next();
178     }
179 
180     void
181     prev ()
182     {
183         m_entry = m_entry.prev();
184     }
185 private:
186     ListEntry m_entry;
187 };
188 
189 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) :
190 SyntheticChildrenFrontEnd(*valobj_sp.get()),
191 m_list_capping_size(0),
192 m_loop_detected(0),
193 m_node_address(),
194 m_head(NULL),
195 m_tail(NULL),
196 m_element_type(),
197 m_count(UINT32_MAX),
198 m_children()
199 {
200     if (valobj_sp)
201         Update();
202 }
203 
204 bool
205 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::HasLoop(size_t count)
206 {
207     if (g_use_loop_detect == false)
208         return false;
209     // don't bother checking for a loop if we won't actually need to jump nodes
210     if (m_count < 2)
211         return false;
212     auto steps_left = std::min(count,m_count);
213     auto steps_left_save = steps_left;
214     ListEntry slow(m_head);
215     ListEntry fast(m_head);
216     while (steps_left-- > 0)
217     {
218         slow = slow.next();
219         fast = fast.next();
220         if (fast.next())
221             fast = fast.next().next();
222         else
223             fast = nullptr;
224         if (!slow || !fast)
225             return false;
226         if (slow == fast)
227             return true;
228     }
229     m_loop_detected = steps_left_save;
230     return false;
231 }
232 
233 size_t
234 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::CalculateNumChildren ()
235 {
236     if (m_count != UINT32_MAX)
237         return m_count;
238     if (!m_head || !m_tail || m_node_address == 0)
239         return 0;
240     ValueObjectSP size_alloc(m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
241     if (size_alloc)
242     {
243         ValueObjectSP first(size_alloc->GetChildMemberWithName(ConstString("__first_"), true));
244         if (first)
245         {
246             m_count = first->GetValueAsUnsigned(UINT32_MAX);
247         }
248     }
249     if (m_count != UINT32_MAX)
250     {
251         return m_count;
252     }
253     else
254     {
255         uint64_t next_val = m_head->GetValueAsUnsigned(0);
256         uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
257         if (next_val == 0 || prev_val == 0)
258             return 0;
259         if (next_val == m_node_address)
260             return 0;
261         if (next_val == prev_val)
262             return 1;
263         uint64_t size = 2;
264         ListEntry current(m_head);
265         while (current.next() && current.next().value() != m_node_address)
266         {
267             size++;
268             current = current.next();
269             if (size > m_list_capping_size)
270                 break;
271         }
272         return m_count = (size-1);
273     }
274 }
275 
276 lldb::ValueObjectSP
277 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetChildAtIndex (size_t idx)
278 {
279     if (idx >= CalculateNumChildren())
280         return lldb::ValueObjectSP();
281 
282     if (!m_head || !m_tail || m_node_address == 0)
283         return lldb::ValueObjectSP();
284 
285     auto cached = m_children.find(idx);
286     if (cached != m_children.end())
287         return cached->second;
288 
289     if (m_loop_detected <= idx)
290         if (HasLoop(idx))
291             return lldb::ValueObjectSP();
292 
293     ListIterator current(m_head);
294     ValueObjectSP current_sp(current.advance(idx));
295     if (!current_sp)
296         return lldb::ValueObjectSP();
297     current_sp = current_sp->GetChildMemberWithName(ConstString("__value_"), true);
298     if (!current_sp)
299         return lldb::ValueObjectSP();
300     // we need to copy current_sp into a new object otherwise we will end up with all items named __value_
301     DataExtractor data;
302     Error error;
303     current_sp->GetData(data, error);
304     if (error.Fail())
305         return lldb::ValueObjectSP();
306 
307     StreamString name;
308     name.Printf("[%" PRIu64 "]", (uint64_t)idx);
309     return (m_children[idx] = CreateValueObjectFromData(name.GetData(), data, m_backend.GetExecutionContextRef(), m_element_type));
310 }
311 
312 bool
313 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::Update()
314 {
315     m_children.clear();
316     m_head = m_tail = NULL;
317     m_node_address = 0;
318     m_count = UINT32_MAX;
319     m_loop_detected = false;
320     Error err;
321     ValueObjectSP backend_addr(m_backend.AddressOf(err));
322     m_list_capping_size = 0;
323     if (m_backend.GetTargetSP())
324         m_list_capping_size = m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
325     if (m_list_capping_size == 0)
326         m_list_capping_size = 255;
327     if (err.Fail() || backend_addr.get() == NULL)
328         return false;
329     m_node_address = backend_addr->GetValueAsUnsigned(0);
330     if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
331         return false;
332     ValueObjectSP impl_sp(m_backend.GetChildMemberWithName(ConstString("__end_"),true));
333     if (!impl_sp)
334         return false;
335     CompilerType list_type = m_backend.GetCompilerType();
336     if (list_type.IsReferenceType())
337         list_type = list_type.GetNonReferenceType();
338 
339     if (list_type.GetNumTemplateArguments() == 0)
340         return false;
341     lldb::TemplateArgumentKind kind;
342     m_element_type = list_type.GetTemplateArgument(0, kind);
343     m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
344     m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
345     return false;
346 }
347 
348 bool
349 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::MightHaveChildren ()
350 {
351     return true;
352 }
353 
354 size_t
355 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name)
356 {
357     return ExtractIndexFromString(name.GetCString());
358 }
359 
360 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::~LibcxxStdListSyntheticFrontEnd ()
361 {}
362 
363 SyntheticChildrenFrontEnd*
364 lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp)
365 {
366     if (!valobj_sp)
367         return NULL;
368     return (new LibcxxStdListSyntheticFrontEnd(valobj_sp));
369 }
370 
371