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