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