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