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

source code of lldb/source/Plugins/Language/CPlusPlus/LibCxxList.cpp