1 //===-- LibCxxList.cpp ------------------------------------------*- C++ -*-===//
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 "lldb/Core/ValueObject.h"
12 #include "lldb/Core/ValueObjectConstResult.h"
13 #include "lldb/DataFormatters/FormattersHelpers.h"
14 #include "lldb/Symbol/ClangASTContext.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
GetValueOfCompressedPair(ValueObject & pair)293 static ValueObjectSP GetValueOfCompressedPair(ValueObject &pair) {
294 ValueObjectSP value = pair.GetChildMemberWithName(ConstString("__value_"), true);
295 if (! value) {
296 // pre-r300140 member name
297 value = pair.GetChildMemberWithName(ConstString("__first_"), true);
298 }
299 return value;
300 }
301
Update()302 bool ForwardListFrontEnd::Update() {
303 AbstractListFrontEnd::Update();
304
305 Status err;
306 ValueObjectSP backend_addr(m_backend.AddressOf(err));
307 if (err.Fail() || !backend_addr)
308 return false;
309
310 ValueObjectSP impl_sp(
311 m_backend.GetChildMemberWithName(ConstString("__before_begin_"), true));
312 if (!impl_sp)
313 return false;
314 impl_sp = GetValueOfCompressedPair(*impl_sp);
315 if (!impl_sp)
316 return false;
317 m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
318 return false;
319 }
320
ListFrontEnd(lldb::ValueObjectSP valobj_sp)321 ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp)
322 : AbstractListFrontEnd(*valobj_sp), m_node_address(), m_tail(nullptr) {
323 if (valobj_sp)
324 Update();
325 }
326
CalculateNumChildren()327 size_t ListFrontEnd::CalculateNumChildren() {
328 if (m_count != UINT32_MAX)
329 return m_count;
330 if (!m_head || !m_tail || m_node_address == 0)
331 return 0;
332 ValueObjectSP size_alloc(
333 m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
334 if (size_alloc) {
335 ValueObjectSP value = GetValueOfCompressedPair(*size_alloc);
336 if (value) {
337 m_count = value->GetValueAsUnsigned(UINT32_MAX);
338 }
339 }
340 if (m_count != UINT32_MAX) {
341 return m_count;
342 } else {
343 uint64_t next_val = m_head->GetValueAsUnsigned(0);
344 uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
345 if (next_val == 0 || prev_val == 0)
346 return 0;
347 if (next_val == m_node_address)
348 return 0;
349 if (next_val == prev_val)
350 return 1;
351 uint64_t size = 2;
352 ListEntry current(m_head);
353 while (current.next() && current.next().value() != m_node_address) {
354 size++;
355 current = current.next();
356 if (size > m_list_capping_size)
357 break;
358 }
359 return m_count = (size - 1);
360 }
361 }
362
GetChildAtIndex(size_t idx)363 lldb::ValueObjectSP ListFrontEnd::GetChildAtIndex(size_t idx) {
364 static ConstString g_value("__value_");
365 static ConstString g_next("__next_");
366
367 if (idx >= CalculateNumChildren())
368 return lldb::ValueObjectSP();
369
370 if (!m_head || !m_tail || m_node_address == 0)
371 return lldb::ValueObjectSP();
372
373 if (HasLoop(idx + 1))
374 return lldb::ValueObjectSP();
375
376 ValueObjectSP current_sp = GetItem(idx);
377 if (!current_sp)
378 return lldb::ValueObjectSP();
379
380 current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
381 if (!current_sp)
382 return lldb::ValueObjectSP();
383
384 if (current_sp->GetName() == g_next) {
385 ProcessSP process_sp(current_sp->GetProcessSP());
386 if (!process_sp)
387 return lldb::ValueObjectSP();
388
389 // if we grabbed the __next_ pointer, then the child is one pointer deep-er
390 lldb::addr_t addr = current_sp->GetParent()->GetPointerValue();
391 addr = addr + 2 * process_sp->GetAddressByteSize();
392 ExecutionContext exe_ctx(process_sp);
393 current_sp =
394 CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type);
395 if (!current_sp)
396 return lldb::ValueObjectSP();
397 }
398
399 // we need to copy current_sp into a new object otherwise we will end up with
400 // all items named __value_
401 DataExtractor data;
402 Status error;
403 current_sp->GetData(data, error);
404 if (error.Fail())
405 return lldb::ValueObjectSP();
406
407 StreamString name;
408 name.Printf("[%" PRIu64 "]", (uint64_t)idx);
409 return CreateValueObjectFromData(name.GetString(), data,
410 m_backend.GetExecutionContextRef(),
411 m_element_type);
412 }
413
Update()414 bool ListFrontEnd::Update() {
415 AbstractListFrontEnd::Update();
416 m_tail = nullptr;
417 m_node_address = 0;
418
419 Status err;
420 ValueObjectSP backend_addr(m_backend.AddressOf(err));
421 if (err.Fail() || !backend_addr)
422 return false;
423 m_node_address = backend_addr->GetValueAsUnsigned(0);
424 if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
425 return false;
426 ValueObjectSP impl_sp(
427 m_backend.GetChildMemberWithName(ConstString("__end_"), true));
428 if (!impl_sp)
429 return false;
430 m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
431 m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
432 return false;
433 }
434
LibcxxStdListSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)435 SyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator(
436 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
437 return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr);
438 }
439
440 SyntheticChildrenFrontEnd *
LibcxxStdForwardListSyntheticFrontEndCreator(CXXSyntheticChildren *,lldb::ValueObjectSP valobj_sp)441 formatters::LibcxxStdForwardListSyntheticFrontEndCreator(
442 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
443 return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr;
444 }
445