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