LLDB mainline
LibCxxList.cpp
Go to the documentation of this file.
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
15#include "lldb/Target/Target.h"
17#include "lldb/Utility/Endian.h"
18#include "lldb/Utility/Status.h"
19#include "lldb/Utility/Stream.h"
20
21using namespace lldb;
22using namespace lldb_private;
23using namespace lldb_private::formatters;
24
25namespace {
26
27class ListEntry {
28public:
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 if (!m_entry_sp)
36 return ListEntry();
37 return ListEntry(m_entry_sp->GetChildMemberWithName("__next_"));
38 }
39
40 ListEntry prev() {
41 if (!m_entry_sp)
42 return ListEntry();
43 return ListEntry(m_entry_sp->GetChildMemberWithName("__prev_"));
44 }
45
46 uint64_t value() const {
47 if (!m_entry_sp)
48 return 0;
49 return m_entry_sp->GetValueAsUnsigned(0);
50 }
51
52 bool null() { return (value() == 0); }
53
54 explicit operator bool() { return GetEntry() && !null(); }
55
56 ValueObjectSP GetEntry() { return m_entry_sp; }
57
58 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
59
60 bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); }
61
62 bool operator!=(const ListEntry &rhs) const { return !(*this == rhs); }
63
64private:
65 ValueObjectSP m_entry_sp;
66};
67
68class ListIterator {
69public:
70 ListIterator() = default;
71 ListIterator(ListEntry entry) : m_entry(std::move(entry)) {}
72 ListIterator(ValueObjectSP entry) : m_entry(std::move(entry)) {}
73 ListIterator(ValueObject *entry) : m_entry(entry) {}
74
75 ValueObjectSP value() { return m_entry.GetEntry(); }
76
77 ValueObjectSP advance(size_t count) {
78 if (count == 0)
79 return m_entry.GetEntry();
80 if (count == 1) {
81 next();
82 return m_entry.GetEntry();
83 }
84 while (count > 0) {
85 next();
86 count--;
87 if (m_entry.null())
88 return lldb::ValueObjectSP();
89 }
90 return m_entry.GetEntry();
91 }
92
93 bool operator==(const ListIterator &rhs) const {
94 return (rhs.m_entry == m_entry);
95 }
96
97protected:
98 void next() { m_entry = m_entry.next(); }
99
100 void prev() { m_entry = m_entry.prev(); }
101
102private:
103 ListEntry m_entry;
104};
105
106class AbstractListFrontEnd : public SyntheticChildrenFrontEnd {
107public:
108 size_t GetIndexOfChildWithName(ConstString name) override {
109 return ExtractIndexFromString(name.GetCString());
110 }
111 bool MightHaveChildren() override { return true; }
112 lldb::ChildCacheState Update() override;
113
114protected:
115 AbstractListFrontEnd(ValueObject &valobj)
116 : SyntheticChildrenFrontEnd(valobj) {}
117
118 size_t m_count = 0;
119 ValueObject *m_head = nullptr;
120
121 static constexpr bool g_use_loop_detect = true;
122 size_t m_loop_detected = 0; // The number of elements that have had loop
123 // detection run over them.
124 ListEntry m_slow_runner; // Used for loop detection
125 ListEntry m_fast_runner; // Used for loop detection
126
127 size_t m_list_capping_size = 0;
128 CompilerType m_element_type;
129 std::map<size_t, ListIterator> m_iterators;
130
131 bool HasLoop(size_t count);
132 ValueObjectSP GetItem(size_t idx);
133};
134
135class ForwardListFrontEnd : public AbstractListFrontEnd {
136public:
137 ForwardListFrontEnd(ValueObject &valobj);
138
139 llvm::Expected<uint32_t> CalculateNumChildren() override;
140 ValueObjectSP GetChildAtIndex(uint32_t idx) override;
141 lldb::ChildCacheState Update() override;
142};
143
144class ListFrontEnd : public AbstractListFrontEnd {
145public:
146 ListFrontEnd(lldb::ValueObjectSP valobj_sp);
147
148 ~ListFrontEnd() override = default;
149
150 llvm::Expected<uint32_t> CalculateNumChildren() override;
151
152 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override;
153
154 lldb::ChildCacheState Update() override;
155
156private:
157 lldb::addr_t m_node_address = 0;
158 ValueObject *m_tail = nullptr;
159};
160
161} // end anonymous namespace
162
163lldb::ChildCacheState AbstractListFrontEnd::Update() {
164 m_loop_detected = 0;
165 m_count = UINT32_MAX;
166 m_head = nullptr;
167 m_list_capping_size = 0;
168 m_slow_runner.SetEntry(nullptr);
169 m_fast_runner.SetEntry(nullptr);
170 m_iterators.clear();
171
172 if (m_backend.GetTargetSP())
173 m_list_capping_size =
174 m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
175 if (m_list_capping_size == 0)
176 m_list_capping_size = 255;
177
178 CompilerType list_type = m_backend.GetCompilerType();
179 if (list_type.IsReferenceType())
180 list_type = list_type.GetNonReferenceType();
181
182 if (list_type.GetNumTemplateArguments() == 0)
184 m_element_type = list_type.GetTypeTemplateArgument(0);
185
187}
188
189bool AbstractListFrontEnd::HasLoop(size_t count) {
190 if (!g_use_loop_detect)
191 return false;
192 // don't bother checking for a loop if we won't actually need to jump nodes
193 if (m_count < 2)
194 return false;
195
196 if (m_loop_detected == 0) {
197 // This is the first time we are being run (after the last update). Set up
198 // the loop invariant for the first element.
199 m_slow_runner = ListEntry(m_head).next();
200 m_fast_runner = m_slow_runner.next();
201 m_loop_detected = 1;
202 }
203
204 // Loop invariant:
205 // Loop detection has been run over the first m_loop_detected elements. If
206 // m_slow_runner == m_fast_runner then the loop has been detected after
207 // m_loop_detected elements.
208 const size_t steps_to_run = std::min(count, m_count);
209 while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner &&
210 m_slow_runner != m_fast_runner) {
211
212 m_slow_runner = m_slow_runner.next();
213 m_fast_runner = m_fast_runner.next().next();
214 m_loop_detected++;
215 }
216 if (count <= m_loop_detected)
217 return false; // No loop in the first m_loop_detected elements.
218 if (!m_slow_runner || !m_fast_runner)
219 return false; // Reached the end of the list. Definitely no loops.
220 return m_slow_runner == m_fast_runner;
221}
222
223ValueObjectSP AbstractListFrontEnd::GetItem(size_t idx) {
224 size_t advance = idx;
225 ListIterator current(m_head);
226 if (idx > 0) {
227 auto cached_iterator = m_iterators.find(idx - 1);
228 if (cached_iterator != m_iterators.end()) {
229 current = cached_iterator->second;
230 advance = 1;
231 }
232 }
233 ValueObjectSP value_sp = current.advance(advance);
234 m_iterators[idx] = current;
235 return value_sp;
236}
237
238ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj)
239 : AbstractListFrontEnd(valobj) {
240 Update();
241}
242
243llvm::Expected<uint32_t> ForwardListFrontEnd::CalculateNumChildren() {
244 if (m_count != UINT32_MAX)
245 return m_count;
246
247 ListEntry current(m_head);
248 m_count = 0;
249 while (current && m_count < m_list_capping_size) {
250 ++m_count;
251 current = current.next();
252 }
253 return m_count;
254}
255
256ValueObjectSP ForwardListFrontEnd::GetChildAtIndex(uint32_t idx) {
257 if (idx >= CalculateNumChildrenIgnoringErrors())
258 return nullptr;
259
260 if (!m_head)
261 return nullptr;
262
263 if (HasLoop(idx + 1))
264 return nullptr;
265
266 ValueObjectSP current_sp = GetItem(idx);
267 if (!current_sp)
268 return nullptr;
269
270 current_sp = current_sp->GetChildAtIndex(1); // get the __value_ child
271 if (!current_sp)
272 return nullptr;
273
274 // we need to copy current_sp into a new object otherwise we will end up with
275 // all items named __value_
276 DataExtractor data;
278 current_sp->GetData(data, error);
279 if (error.Fail())
280 return nullptr;
281
282 return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data,
283 m_backend.GetExecutionContextRef(),
284 m_element_type);
285}
286
287lldb::ChildCacheState ForwardListFrontEnd::Update() {
288 AbstractListFrontEnd::Update();
289
290 Status err;
291 ValueObjectSP backend_addr(m_backend.AddressOf(err));
292 if (err.Fail() || !backend_addr)
294
295 ValueObjectSP impl_sp(m_backend.GetChildMemberWithName("__before_begin_"));
296 if (!impl_sp)
298 impl_sp = GetFirstValueOfLibCXXCompressedPair(*impl_sp);
299 if (!impl_sp)
301 m_head = impl_sp->GetChildMemberWithName("__next_").get();
303}
304
305ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp)
306 : AbstractListFrontEnd(*valobj_sp) {
307 if (valobj_sp)
308 Update();
309}
310
311llvm::Expected<uint32_t> ListFrontEnd::CalculateNumChildren() {
312 if (m_count != UINT32_MAX)
313 return m_count;
314 if (!m_head || !m_tail || m_node_address == 0)
315 return 0;
316 ValueObjectSP size_alloc(m_backend.GetChildMemberWithName("__size_alloc_"));
317 if (size_alloc) {
319 if (value) {
320 m_count = value->GetValueAsUnsigned(UINT32_MAX);
321 }
322 }
323 if (m_count != UINT32_MAX) {
324 return m_count;
325 } else {
326 uint64_t next_val = m_head->GetValueAsUnsigned(0);
327 uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
328 if (next_val == 0 || prev_val == 0)
329 return 0;
330 if (next_val == m_node_address)
331 return 0;
332 if (next_val == prev_val)
333 return 1;
334 uint64_t size = 2;
335 ListEntry current(m_head);
336 while (current.next() && current.next().value() != m_node_address) {
337 size++;
338 current = current.next();
339 if (size > m_list_capping_size)
340 break;
341 }
342 return m_count = (size - 1);
343 }
344}
345
346lldb::ValueObjectSP ListFrontEnd::GetChildAtIndex(uint32_t idx) {
347 static ConstString g_value("__value_");
348 static ConstString g_next("__next_");
349
350 if (idx >= CalculateNumChildrenIgnoringErrors())
351 return lldb::ValueObjectSP();
352
353 if (!m_head || !m_tail || m_node_address == 0)
354 return lldb::ValueObjectSP();
355
356 if (HasLoop(idx + 1))
357 return lldb::ValueObjectSP();
358
359 ValueObjectSP current_sp = GetItem(idx);
360 if (!current_sp)
361 return lldb::ValueObjectSP();
362
363 current_sp = current_sp->GetChildAtIndex(1); // get the __value_ child
364 if (!current_sp)
365 return lldb::ValueObjectSP();
366
367 if (current_sp->GetName() == g_next) {
368 ProcessSP process_sp(current_sp->GetProcessSP());
369 if (!process_sp)
370 return lldb::ValueObjectSP();
371
372 // if we grabbed the __next_ pointer, then the child is one pointer deep-er
373 lldb::addr_t addr = current_sp->GetParent()->GetPointerValue();
374 addr = addr + 2 * process_sp->GetAddressByteSize();
375 ExecutionContext exe_ctx(process_sp);
376 current_sp =
377 CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type);
378 if (!current_sp)
379 return lldb::ValueObjectSP();
380 }
381
382 // we need to copy current_sp into a new object otherwise we will end up with
383 // all items named __value_
384 DataExtractor data;
386 current_sp->GetData(data, error);
387 if (error.Fail())
388 return lldb::ValueObjectSP();
389
390 StreamString name;
391 name.Printf("[%" PRIu64 "]", (uint64_t)idx);
392 return CreateValueObjectFromData(name.GetString(), data,
393 m_backend.GetExecutionContextRef(),
394 m_element_type);
395}
396
397lldb::ChildCacheState ListFrontEnd::Update() {
398 AbstractListFrontEnd::Update();
399 m_tail = nullptr;
400 m_node_address = 0;
401
402 Status err;
403 ValueObjectSP backend_addr(m_backend.AddressOf(err));
404 if (err.Fail() || !backend_addr)
406 m_node_address = backend_addr->GetValueAsUnsigned(0);
407 if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
409 ValueObjectSP impl_sp(m_backend.GetChildMemberWithName("__end_"));
410 if (!impl_sp)
412 m_head = impl_sp->GetChildMemberWithName("__next_").get();
413 m_tail = impl_sp->GetChildMemberWithName("__prev_").get();
415}
416
419 return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr);
420}
421
425 return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr;
426}
static llvm::raw_ostream & error(Stream &strm)
static std::optional< size_t > CalculateNumChildren(CompilerType container_elem_type, uint64_t num_elements, CompilerType element_type)
Calculates the number of elements stored in a container (with element type 'container_elem_type') as ...
Definition: VectorType.cpp:198
Generic representation of a type in a programming language.
Definition: CompilerType.h:36
CompilerType GetTypeTemplateArgument(size_t idx, bool expand_pack=false) const
size_t GetNumTemplateArguments(bool expand_pack=false) const
Return the number of template arguments the type has.
CompilerType GetNonReferenceType() const
If this type is a reference to a type (L value or R value reference), return a new type with the refe...
bool IsReferenceType(CompilerType *pointee_type=nullptr, bool *is_rvalue=nullptr) const
A uniqued constant string class.
Definition: ConstString.h:40
const char * GetCString() const
Get the string value as a C string.
Definition: ConstString.h:214
An data extractor class.
Definition: DataExtractor.h:48
"lldb/Target/ExecutionContext.h" A class that contains an execution context.
An error handling class.
Definition: Status.h:44
bool Fail() const
Test for error condition.
Definition: Status.cpp:181
llvm::StringRef GetString() const
size_t Printf(const char *format,...) __attribute__((format(printf
Output printf formatted output to the stream.
Definition: Stream.cpp:134
virtual lldb::ChildCacheState Update()=0
This function is assumed to always succeed and if it fails, the front-end should know to deal with it...
virtual size_t GetIndexOfChildWithName(ConstString name)=0
#define LLDB_INVALID_ADDRESS
Definition: lldb-defines.h:82
#define UINT32_MAX
Definition: lldb-defines.h:19
size_t ExtractIndexFromString(const char *item_name)
lldb::ValueObjectSP GetFirstValueOfLibCXXCompressedPair(ValueObject &pair)
Definition: LibCxx.cpp:49
SyntheticChildrenFrontEnd * LibcxxStdListSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxList.cpp:417
SyntheticChildrenFrontEnd * LibcxxStdForwardListSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxList.cpp:423
A class that represents a running process on the host machine.
Definition: SBAttachInfo.h:14
bool operator!=(const Address &lhs, const Address &rhs)
Definition: Address.cpp:1029
Definition: SBAddress.h:15
ChildCacheState
Specifies if children need to be re-computed after a call to SyntheticChildrenFrontEnd::Update.
@ eRefetch
Children need to be recomputed dynamically.
std::shared_ptr< lldb_private::ValueObject > ValueObjectSP
Definition: lldb-forward.h:472
std::shared_ptr< lldb_private::Process > ProcessSP
Definition: lldb-forward.h:381
uint64_t addr_t
Definition: lldb-types.h:79
bool LLDB_API operator==(const SBAddress &lhs, const SBAddress &rhs)
Definition: SBAddress.cpp:60