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) = default;
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->GetChildAtIndexPath({0,1}));
46         }
47 
48         ListEntry
49         prev ()
50         {
51             if (!m_entry_sp)
52                 return ListEntry();
53             return ListEntry(m_entry_sp->GetChildAtIndexPath({0,0}));
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() && !null();
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     class ListIterator
104     {
105     public:
106         ListIterator() = default;
107         ListIterator (ListEntry entry) : m_entry(entry) {}
108         ListIterator (ValueObjectSP entry) : m_entry(entry) {}
109         ListIterator(const ListIterator& rhs) = default;
110         ListIterator (ValueObject* entry) : m_entry(entry) {}
111 
112         ValueObjectSP
113         value ()
114         {
115             return m_entry.GetEntry();
116         }
117 
118         ValueObjectSP
119         advance (size_t count)
120         {
121             if (count == 0)
122                 return m_entry.GetEntry();
123             if (count == 1)
124             {
125                 next ();
126                 return m_entry.GetEntry();
127             }
128             while (count > 0)
129             {
130                 next ();
131                 count--;
132                 if (m_entry.null())
133                     return lldb::ValueObjectSP();
134             }
135             return m_entry.GetEntry();
136         }
137 
138         bool
139         operator == (const ListIterator& rhs) const
140         {
141             return (rhs.m_entry == m_entry);
142         }
143 
144     protected:
145         void
146         next ()
147         {
148             m_entry = m_entry.next();
149         }
150 
151         void
152         prev ()
153         {
154             m_entry = m_entry.prev();
155         }
156 
157     private:
158         ListEntry m_entry;
159     };
160 
161 } // end anonymous namespace
162 
163 namespace lldb_private {
164     namespace formatters {
165         class LibcxxStdListSyntheticFrontEnd : public SyntheticChildrenFrontEnd
166         {
167         public:
168             LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp);
169 
170             ~LibcxxStdListSyntheticFrontEnd() override = default;
171 
172             size_t
173             CalculateNumChildren() override;
174 
175             lldb::ValueObjectSP
176             GetChildAtIndex(size_t idx) override;
177 
178             bool
179             Update() override;
180 
181             bool
182             MightHaveChildren() override;
183 
184             size_t
185             GetIndexOfChildWithName(const ConstString &name) override;
186 
187         private:
188             bool
189             HasLoop(size_t count);
190 
191             size_t m_list_capping_size;
192             static const bool g_use_loop_detect = true;
193 
194             size_t m_loop_detected; // The number of elements that have had loop detection run over them.
195             ListEntry m_slow_runner; // Used for loop detection
196             ListEntry m_fast_runner; // Used for loop detection
197 
198             lldb::addr_t m_node_address;
199             ValueObject* m_head;
200             ValueObject* m_tail;
201             CompilerType m_element_type;
202             size_t m_count;
203             std::map<size_t, ListIterator> m_iterators;
204         };
205     } // namespace formatters
206 } // namespace lldb_private
207 
208 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::LibcxxStdListSyntheticFrontEnd (lldb::ValueObjectSP valobj_sp) :
209     SyntheticChildrenFrontEnd(*valobj_sp),
210     m_list_capping_size(0),
211     m_loop_detected(0),
212     m_node_address(),
213     m_head(nullptr),
214     m_tail(nullptr),
215     m_element_type(),
216     m_count(UINT32_MAX),
217     m_iterators()
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)
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     if (HasLoop(idx+1))
314         return lldb::ValueObjectSP();
315 
316     size_t actual_advance = idx;
317 
318     ListIterator current(m_head);
319     if (idx > 0)
320     {
321         auto cached_iterator = m_iterators.find(idx-1);
322         if (cached_iterator != m_iterators.end())
323         {
324             current = cached_iterator->second;
325             actual_advance = 1;
326         }
327     }
328 
329     ValueObjectSP current_sp(current.advance(actual_advance));
330     if (!current_sp)
331         return lldb::ValueObjectSP();
332 
333     m_iterators[idx] = current;
334 
335     current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
336     if (!current_sp)
337         return lldb::ValueObjectSP();
338     // we need to copy current_sp into a new object otherwise we will end up with all items named __value_
339     DataExtractor data;
340     Error error;
341     current_sp->GetData(data, error);
342     if (error.Fail())
343         return lldb::ValueObjectSP();
344 
345     StreamString name;
346     name.Printf("[%" PRIu64 "]", (uint64_t)idx);
347     return CreateValueObjectFromData(name.GetData(),
348                                      data,
349                                      m_backend.GetExecutionContextRef(),
350                                      m_element_type);
351 }
352 
353 bool
354 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::Update()
355 {
356     m_iterators.clear();
357     m_head = m_tail = nullptr;
358     m_node_address = 0;
359     m_count = UINT32_MAX;
360     m_loop_detected = 0;
361     m_slow_runner.SetEntry(nullptr);
362     m_fast_runner.SetEntry(nullptr);
363 
364     Error err;
365     ValueObjectSP backend_addr(m_backend.AddressOf(err));
366     m_list_capping_size = 0;
367     if (m_backend.GetTargetSP())
368         m_list_capping_size = m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
369     if (m_list_capping_size == 0)
370         m_list_capping_size = 255;
371     if (err.Fail() || !backend_addr)
372         return false;
373     m_node_address = backend_addr->GetValueAsUnsigned(0);
374     if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
375         return false;
376     ValueObjectSP impl_sp(m_backend.GetChildMemberWithName(ConstString("__end_"),true));
377     if (!impl_sp)
378         return false;
379     CompilerType list_type = m_backend.GetCompilerType();
380     if (list_type.IsReferenceType())
381         list_type = list_type.GetNonReferenceType();
382 
383     if (list_type.GetNumTemplateArguments() == 0)
384         return false;
385     lldb::TemplateArgumentKind kind;
386     m_element_type = list_type.GetTemplateArgument(0, kind);
387     m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
388     m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
389     return false;
390 }
391 
392 bool
393 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::MightHaveChildren ()
394 {
395     return true;
396 }
397 
398 size_t
399 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetIndexOfChildWithName (const ConstString &name)
400 {
401     return ExtractIndexFromString(name.GetCString());
402 }
403 
404 SyntheticChildrenFrontEnd*
405 lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator (CXXSyntheticChildren*, lldb::ValueObjectSP valobj_sp)
406 {
407     return (valobj_sp ? new LibcxxStdListSyntheticFrontEnd(valobj_sp) : nullptr);
408 }
409