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 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
68private:
69 ValueObjectSP m_entry_sp;
70};
71
72class ListIterator {
73public:
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
101protected:
102 void next() { m_entry = m_entry.next(); }
103
104 void prev() { m_entry = m_entry.prev(); }
105
106private:
107 ListEntry m_entry;
108};
109
110class AbstractListFrontEnd : public SyntheticChildrenFrontEnd {
111public:
112 size_t GetIndexOfChildWithName(ConstString name) override {
113 return ExtractIndexFromString(name.GetCString());
114 }
115 bool MightHaveChildren() override { return true; }
116 bool Update() override;
117
118protected:
119 AbstractListFrontEnd(ValueObject &valobj)
120 : SyntheticChildrenFrontEnd(valobj) {}
121
122 size_t m_count = 0;
123 ValueObject *m_head = nullptr;
124
125 static constexpr bool g_use_loop_detect = true;
126 size_t m_loop_detected = 0; // The number of elements that have had loop
127 // detection 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 = 0;
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
139class ForwardListFrontEnd : public AbstractListFrontEnd {
140public:
141 ForwardListFrontEnd(ValueObject &valobj);
142
143 size_t CalculateNumChildren() override;
144 ValueObjectSP GetChildAtIndex(size_t idx) override;
145 bool Update() override;
146};
147
148class ListFrontEnd : public AbstractListFrontEnd {
149public:
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
160private:
161 lldb::addr_t m_node_address = 0;
162 ValueObject *m_tail = nullptr;
163};
164
165} // end anonymous namespace
166
167bool 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
193bool 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
227ValueObjectSP 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
242ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj)
243 : AbstractListFrontEnd(valobj) {
244 Update();
245}
246
247size_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
260ValueObjectSP 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;
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
291bool 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
310ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp)
311 : AbstractListFrontEnd(*valobj_sp) {
312 if (valobj_sp)
313 Update();
314}
315
316size_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
352lldb::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;
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
403bool 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
425 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
426 return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr);
427}
428
431 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
432 return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr;
433}
static llvm::raw_ostream & error(Stream &strm)
static size_t CalculateNumChildren(CompilerType container_type, CompilerType element_type, lldb_private::ExecutionContextScope *exe_scope=nullptr)
Definition: VectorType.cpp:172
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:39
const char * GetCString() const
Get the string value as a C string.
Definition: ConstString.h:215
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:107
virtual size_t GetIndexOfChildWithName(ConstString name)=0
#define LLDB_INVALID_ADDRESS
Definition: lldb-defines.h:74
#define UINT32_MAX
Definition: lldb-defines.h:19
size_t ExtractIndexFromString(const char *item_name)
SyntheticChildrenFrontEnd * LibcxxStdListSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxList.cpp:424
lldb::ValueObjectSP GetValueOfLibCXXCompressedPair(ValueObject &pair)
SyntheticChildrenFrontEnd * LibcxxStdForwardListSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxList.cpp:430
A class that represents a running process on the host machine.
bool operator!=(const Address &lhs, const Address &rhs)
Definition: Address.cpp:1022
Definition: SBAddress.h:15
uint64_t addr_t
Definition: lldb-types.h:83
bool LLDB_API operator==(const SBAddress &lhs, const SBAddress &rhs)
Definition: SBAddress.cpp:60