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