1 //===-- LibCxxList.cpp ------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
12 // Other libraries and framework includes
16 #include "lldb/Core/ValueObject.h"
17 #include "lldb/Core/ValueObjectConstResult.h"
18 #include "lldb/DataFormatters/FormattersHelpers.h"
19 #include "lldb/Symbol/ClangASTContext.h"
20 #include "lldb/Target/Target.h"
21 #include "lldb/Utility/DataBufferHeap.h"
22 #include "lldb/Utility/Endian.h"
23 #include "lldb/Utility/Status.h"
24 #include "lldb/Utility/Stream.h"
27 using namespace lldb_private;
28 using namespace lldb_private::formatters;
34 ListEntry() = default;
35 ListEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}
36 ListEntry(const ListEntry &rhs) = default;
37 ListEntry(ValueObject *entry)
38 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
41 static ConstString g_next("__next_");
45 return ListEntry(m_entry_sp->GetChildMemberWithName(g_next, true));
49 static ConstString g_prev("__prev_");
53 return ListEntry(m_entry_sp->GetChildMemberWithName(g_prev, true));
56 uint64_t value() const {
59 return m_entry_sp->GetValueAsUnsigned(0);
62 bool null() { return (value() == 0); }
64 explicit operator bool() { return GetEntry() && !null(); }
66 ValueObjectSP GetEntry() { return m_entry_sp; }
68 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
70 bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); }
72 bool operator!=(const ListEntry &rhs) const { return !(*this == rhs); }
75 ValueObjectSP m_entry_sp;
80 ListIterator() = default;
81 ListIterator(ListEntry entry) : m_entry(entry) {}
82 ListIterator(ValueObjectSP entry) : m_entry(entry) {}
83 ListIterator(const ListIterator &rhs) = default;
84 ListIterator(ValueObject *entry) : m_entry(entry) {}
86 ValueObjectSP value() { return m_entry.GetEntry(); }
88 ValueObjectSP advance(size_t count) {
90 return m_entry.GetEntry();
93 return m_entry.GetEntry();
99 return lldb::ValueObjectSP();
101 return m_entry.GetEntry();
104 bool operator==(const ListIterator &rhs) const {
105 return (rhs.m_entry == m_entry);
109 void next() { m_entry = m_entry.next(); }
111 void prev() { m_entry = m_entry.prev(); }
117 class AbstractListFrontEnd : public SyntheticChildrenFrontEnd {
119 size_t GetIndexOfChildWithName(const ConstString &name) override {
120 return ExtractIndexFromString(name.GetCString());
122 bool MightHaveChildren() override { return true; }
123 bool Update() override;
126 AbstractListFrontEnd(ValueObject &valobj)
127 : SyntheticChildrenFrontEnd(valobj) {}
132 static constexpr bool g_use_loop_detect = true;
133 size_t m_loop_detected; // The number of elements that have had loop detection
135 ListEntry m_slow_runner; // Used for loop detection
136 ListEntry m_fast_runner; // Used for loop detection
138 size_t m_list_capping_size;
139 CompilerType m_element_type;
140 std::map<size_t, ListIterator> m_iterators;
142 bool HasLoop(size_t count);
143 ValueObjectSP GetItem(size_t idx);
146 class ForwardListFrontEnd : public AbstractListFrontEnd {
148 ForwardListFrontEnd(ValueObject &valobj);
150 size_t CalculateNumChildren() override;
151 ValueObjectSP GetChildAtIndex(size_t idx) override;
152 bool Update() override;
155 class ListFrontEnd : public AbstractListFrontEnd {
157 ListFrontEnd(lldb::ValueObjectSP valobj_sp);
159 ~ListFrontEnd() override = default;
161 size_t CalculateNumChildren() override;
163 lldb::ValueObjectSP GetChildAtIndex(size_t idx) override;
165 bool Update() override;
168 lldb::addr_t m_node_address;
172 } // end anonymous namespace
174 bool AbstractListFrontEnd::Update() {
176 m_count = UINT32_MAX;
178 m_list_capping_size = 0;
179 m_slow_runner.SetEntry(nullptr);
180 m_fast_runner.SetEntry(nullptr);
183 if (m_backend.GetTargetSP())
184 m_list_capping_size =
185 m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
186 if (m_list_capping_size == 0)
187 m_list_capping_size = 255;
189 CompilerType list_type = m_backend.GetCompilerType();
190 if (list_type.IsReferenceType())
191 list_type = list_type.GetNonReferenceType();
193 if (list_type.GetNumTemplateArguments() == 0)
195 m_element_type = list_type.GetTypeTemplateArgument(0);
200 bool AbstractListFrontEnd::HasLoop(size_t count) {
201 if (!g_use_loop_detect)
203 // don't bother checking for a loop if we won't actually need to jump nodes
207 if (m_loop_detected == 0) {
208 // This is the first time we are being run (after the last update). Set up
209 // the loop invariant for the first element.
210 m_slow_runner = ListEntry(m_head).next();
211 m_fast_runner = m_slow_runner.next();
216 // Loop detection has been run over the first m_loop_detected elements. If
217 // m_slow_runner == m_fast_runner then the loop has been detected after
218 // m_loop_detected elements.
219 const size_t steps_to_run = std::min(count, m_count);
220 while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner &&
221 m_slow_runner != m_fast_runner) {
223 m_slow_runner = m_slow_runner.next();
224 m_fast_runner = m_fast_runner.next().next();
227 if (count <= m_loop_detected)
228 return false; // No loop in the first m_loop_detected elements.
229 if (!m_slow_runner || !m_fast_runner)
230 return false; // Reached the end of the list. Definitely no loops.
231 return m_slow_runner == m_fast_runner;
234 ValueObjectSP AbstractListFrontEnd::GetItem(size_t idx) {
235 size_t advance = idx;
236 ListIterator current(m_head);
238 auto cached_iterator = m_iterators.find(idx - 1);
239 if (cached_iterator != m_iterators.end()) {
240 current = cached_iterator->second;
244 ValueObjectSP value_sp = current.advance(advance);
245 m_iterators[idx] = current;
249 ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj)
250 : AbstractListFrontEnd(valobj) {
254 size_t ForwardListFrontEnd::CalculateNumChildren() {
255 if (m_count != UINT32_MAX)
258 ListEntry current(m_head);
260 while (current && m_count < m_list_capping_size) {
262 current = current.next();
267 ValueObjectSP ForwardListFrontEnd::GetChildAtIndex(size_t idx) {
268 if (idx >= CalculateNumChildren())
274 if (HasLoop(idx + 1))
277 ValueObjectSP current_sp = GetItem(idx);
281 current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
285 // we need to copy current_sp into a new object otherwise we will end up with
286 // all items named __value_
289 current_sp->GetData(data, error);
293 return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data,
294 m_backend.GetExecutionContextRef(),
298 static ValueObjectSP GetValueOfCompressedPair(ValueObject &pair) {
299 ValueObjectSP value = pair.GetChildMemberWithName(ConstString("__value_"), true);
301 // pre-r300140 member name
302 value = pair.GetChildMemberWithName(ConstString("__first_"), true);
307 bool ForwardListFrontEnd::Update() {
308 AbstractListFrontEnd::Update();
311 ValueObjectSP backend_addr(m_backend.AddressOf(err));
312 if (err.Fail() || !backend_addr)
315 ValueObjectSP impl_sp(
316 m_backend.GetChildMemberWithName(ConstString("__before_begin_"), true));
319 impl_sp = GetValueOfCompressedPair(*impl_sp);
322 m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
326 ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp)
327 : AbstractListFrontEnd(*valobj_sp), m_node_address(), m_tail(nullptr) {
332 size_t ListFrontEnd::CalculateNumChildren() {
333 if (m_count != UINT32_MAX)
335 if (!m_head || !m_tail || m_node_address == 0)
337 ValueObjectSP size_alloc(
338 m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
340 ValueObjectSP value = GetValueOfCompressedPair(*size_alloc);
342 m_count = value->GetValueAsUnsigned(UINT32_MAX);
345 if (m_count != UINT32_MAX) {
348 uint64_t next_val = m_head->GetValueAsUnsigned(0);
349 uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
350 if (next_val == 0 || prev_val == 0)
352 if (next_val == m_node_address)
354 if (next_val == prev_val)
357 ListEntry current(m_head);
358 while (current.next() && current.next().value() != m_node_address) {
360 current = current.next();
361 if (size > m_list_capping_size)
364 return m_count = (size - 1);
368 lldb::ValueObjectSP ListFrontEnd::GetChildAtIndex(size_t idx) {
369 static ConstString g_value("__value_");
370 static ConstString g_next("__next_");
372 if (idx >= CalculateNumChildren())
373 return lldb::ValueObjectSP();
375 if (!m_head || !m_tail || m_node_address == 0)
376 return lldb::ValueObjectSP();
378 if (HasLoop(idx + 1))
379 return lldb::ValueObjectSP();
381 ValueObjectSP current_sp = GetItem(idx);
383 return lldb::ValueObjectSP();
385 current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
387 return lldb::ValueObjectSP();
389 if (current_sp->GetName() == g_next) {
390 ProcessSP process_sp(current_sp->GetProcessSP());
394 // if we grabbed the __next_ pointer, then the child is one pointer deep-er
395 lldb::addr_t addr = current_sp->GetParent()->GetPointerValue();
396 addr = addr + 2 * process_sp->GetAddressByteSize();
397 ExecutionContext exe_ctx(process_sp);
399 CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type);
402 // we need to copy current_sp into a new object otherwise we will end up with
403 // all items named __value_
406 current_sp->GetData(data, error);
408 return lldb::ValueObjectSP();
411 name.Printf("[%" PRIu64 "]", (uint64_t)idx);
412 return CreateValueObjectFromData(name.GetString(), data,
413 m_backend.GetExecutionContextRef(),
417 bool ListFrontEnd::Update() {
418 AbstractListFrontEnd::Update();
423 ValueObjectSP backend_addr(m_backend.AddressOf(err));
424 if (err.Fail() || !backend_addr)
426 m_node_address = backend_addr->GetValueAsUnsigned(0);
427 if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
429 ValueObjectSP impl_sp(
430 m_backend.GetChildMemberWithName(ConstString("__end_"), true));
433 m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
434 m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
438 SyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator(
439 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
440 return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr);
443 SyntheticChildrenFrontEnd *
444 formatters::LibcxxStdForwardListSyntheticFrontEndCreator(
445 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
446 return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr;