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