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 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 } // end anonymous namespace
118 
119 namespace lldb_private {
120 namespace formatters {
121 class LibcxxStdListSyntheticFrontEnd : public SyntheticChildrenFrontEnd {
122 public:
123   LibcxxStdListSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);
124 
125   ~LibcxxStdListSyntheticFrontEnd() override = default;
126 
127   size_t CalculateNumChildren() override;
128 
129   lldb::ValueObjectSP GetChildAtIndex(size_t idx) override;
130 
131   bool Update() override;
132 
133   bool MightHaveChildren() override;
134 
135   size_t GetIndexOfChildWithName(const ConstString &name) override;
136 
137 private:
138   bool HasLoop(size_t count);
139 
140   size_t m_list_capping_size;
141   static const bool g_use_loop_detect = true;
142 
143   size_t m_loop_detected; // The number of elements that have had loop detection
144                           // run over them.
145   ListEntry m_slow_runner; // Used for loop detection
146   ListEntry m_fast_runner; // Used for loop detection
147 
148   lldb::addr_t m_node_address;
149   ValueObject *m_head;
150   ValueObject *m_tail;
151   CompilerType m_element_type;
152   size_t m_count;
153   std::map<size_t, ListIterator> m_iterators;
154 };
155 } // namespace formatters
156 } // namespace lldb_private
157 
158 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
159     LibcxxStdListSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)
160     : SyntheticChildrenFrontEnd(*valobj_sp), m_list_capping_size(0),
161       m_loop_detected(0), m_node_address(), m_head(nullptr), m_tail(nullptr),
162       m_element_type(), m_count(UINT32_MAX), m_iterators() {
163   if (valobj_sp)
164     Update();
165 }
166 
167 bool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::HasLoop(
168     size_t count) {
169   if (!g_use_loop_detect)
170     return false;
171   // don't bother checking for a loop if we won't actually need to jump nodes
172   if (m_count < 2)
173     return false;
174 
175   if (m_loop_detected == 0) {
176     // This is the first time we are being run (after the last update). Set up
177     // the loop
178     // invariant for the first element.
179     m_slow_runner = ListEntry(m_head).next();
180     m_fast_runner = m_slow_runner.next();
181     m_loop_detected = 1;
182   }
183 
184   // Loop invariant:
185   // Loop detection has been run over the first m_loop_detected elements. If
186   // m_slow_runner ==
187   // m_fast_runner then the loop has been detected after m_loop_detected
188   // elements.
189   const size_t steps_to_run = std::min(count, m_count);
190   while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner &&
191          m_slow_runner != m_fast_runner) {
192 
193     m_slow_runner = m_slow_runner.next();
194     m_fast_runner = m_fast_runner.next().next();
195     m_loop_detected++;
196   }
197   if (count <= m_loop_detected)
198     return false; // No loop in the first m_loop_detected elements.
199   if (!m_slow_runner || !m_fast_runner)
200     return false; // Reached the end of the list. Definitely no loops.
201   return m_slow_runner == m_fast_runner;
202 }
203 
204 size_t lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
205     CalculateNumChildren() {
206   if (m_count != UINT32_MAX)
207     return m_count;
208   if (!m_head || !m_tail || m_node_address == 0)
209     return 0;
210   ValueObjectSP size_alloc(
211       m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
212   if (size_alloc) {
213     ValueObjectSP first(
214         size_alloc->GetChildMemberWithName(ConstString("__first_"), true));
215     if (first) {
216       m_count = first->GetValueAsUnsigned(UINT32_MAX);
217     }
218   }
219   if (m_count != UINT32_MAX) {
220     return m_count;
221   } else {
222     uint64_t next_val = m_head->GetValueAsUnsigned(0);
223     uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
224     if (next_val == 0 || prev_val == 0)
225       return 0;
226     if (next_val == m_node_address)
227       return 0;
228     if (next_val == prev_val)
229       return 1;
230     uint64_t size = 2;
231     ListEntry current(m_head);
232     while (current.next() && current.next().value() != m_node_address) {
233       size++;
234       current = current.next();
235       if (size > m_list_capping_size)
236         break;
237     }
238     return m_count = (size - 1);
239   }
240 }
241 
242 lldb::ValueObjectSP
243 lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::GetChildAtIndex(
244     size_t idx) {
245   static ConstString g_value("__value_");
246   static ConstString g_next("__next_");
247 
248   if (idx >= CalculateNumChildren())
249     return lldb::ValueObjectSP();
250 
251   if (!m_head || !m_tail || m_node_address == 0)
252     return lldb::ValueObjectSP();
253 
254   if (HasLoop(idx + 1))
255     return lldb::ValueObjectSP();
256 
257   size_t actual_advance = idx;
258 
259   ListIterator current(m_head);
260   if (idx > 0) {
261     auto cached_iterator = m_iterators.find(idx - 1);
262     if (cached_iterator != m_iterators.end()) {
263       current = cached_iterator->second;
264       actual_advance = 1;
265     }
266   }
267 
268   ValueObjectSP current_sp(current.advance(actual_advance));
269   if (!current_sp)
270     return lldb::ValueObjectSP();
271 
272   m_iterators[idx] = current;
273 
274   current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
275   if (!current_sp)
276     return lldb::ValueObjectSP();
277 
278   if (current_sp->GetName() == g_next) {
279     ProcessSP process_sp(current_sp->GetProcessSP());
280     if (!process_sp)
281       return nullptr;
282 
283     // if we grabbed the __next_ pointer, then the child is one pointer deep-er
284     lldb::addr_t addr = current_sp->GetParent()->GetPointerValue();
285     addr = addr + 2 * process_sp->GetAddressByteSize();
286     ExecutionContext exe_ctx(process_sp);
287     current_sp =
288         CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type);
289   }
290 
291   // we need to copy current_sp into a new object otherwise we will end up with
292   // all items named __value_
293   DataExtractor data;
294   Error error;
295   current_sp->GetData(data, error);
296   if (error.Fail())
297     return lldb::ValueObjectSP();
298 
299   StreamString name;
300   name.Printf("[%" PRIu64 "]", (uint64_t)idx);
301   return CreateValueObjectFromData(
302       name.GetData(), data, m_backend.GetExecutionContextRef(), m_element_type);
303 }
304 
305 bool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::Update() {
306   m_iterators.clear();
307   m_head = m_tail = nullptr;
308   m_node_address = 0;
309   m_count = UINT32_MAX;
310   m_loop_detected = 0;
311   m_slow_runner.SetEntry(nullptr);
312   m_fast_runner.SetEntry(nullptr);
313 
314   Error err;
315   ValueObjectSP backend_addr(m_backend.AddressOf(err));
316   m_list_capping_size = 0;
317   if (m_backend.GetTargetSP())
318     m_list_capping_size =
319         m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
320   if (m_list_capping_size == 0)
321     m_list_capping_size = 255;
322   if (err.Fail() || !backend_addr)
323     return false;
324   m_node_address = backend_addr->GetValueAsUnsigned(0);
325   if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
326     return false;
327   ValueObjectSP impl_sp(
328       m_backend.GetChildMemberWithName(ConstString("__end_"), true));
329   if (!impl_sp)
330     return false;
331   CompilerType list_type = m_backend.GetCompilerType();
332   if (list_type.IsReferenceType())
333     list_type = list_type.GetNonReferenceType();
334 
335   if (list_type.GetNumTemplateArguments() == 0)
336     return false;
337   lldb::TemplateArgumentKind kind;
338   m_element_type = list_type.GetTemplateArgument(0, kind);
339   m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
340   m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
341   return false;
342 }
343 
344 bool lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
345     MightHaveChildren() {
346   return true;
347 }
348 
349 size_t lldb_private::formatters::LibcxxStdListSyntheticFrontEnd::
350     GetIndexOfChildWithName(const ConstString &name) {
351   return ExtractIndexFromString(name.GetCString());
352 }
353 
354 SyntheticChildrenFrontEnd *
355 lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator(
356     CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
357   return (valobj_sp ? new LibcxxStdListSyntheticFrontEnd(valobj_sp) : nullptr);
358 }
359