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