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 
12 #include "lldb/Core/ValueObject.h"
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 
21 using namespace lldb;
22 using namespace lldb_private;
23 using namespace lldb_private::formatters;
24 
25 namespace {
26 
27 class ListEntry {
28 public:
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 
68 private:
69  ValueObjectSP m_entry_sp;
70 };
71 
72 class ListIterator {
73 public:
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 
101 protected:
102  void next() { m_entry = m_entry.next(); }
103 
104  void prev() { m_entry = m_entry.prev(); }
105 
106 private:
107  ListEntry m_entry;
108 };
109 
110 class AbstractListFrontEnd : public SyntheticChildrenFrontEnd {
111 public:
112  size_t GetIndexOfChildWithName(ConstString name) override {
113  return ExtractIndexFromString(name.GetCString());
114  }
115  bool MightHaveChildren() override { return true; }
116  bool Update() override;
117 
118 protected:
119  AbstractListFrontEnd(ValueObject &valobj)
120  : SyntheticChildrenFrontEnd(valobj) {}
121 
122  size_t m_count;
123  ValueObject *m_head;
124 
125  static constexpr bool g_use_loop_detect = true;
126  size_t m_loop_detected; // The number of elements that have had loop detection
127  // 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;
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 
139 class ForwardListFrontEnd : public AbstractListFrontEnd {
140 public:
141  ForwardListFrontEnd(ValueObject &valobj);
142 
143  size_t CalculateNumChildren() override;
144  ValueObjectSP GetChildAtIndex(size_t idx) override;
145  bool Update() override;
146 };
147 
148 class ListFrontEnd : public AbstractListFrontEnd {
149 public:
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 
160 private:
161  lldb::addr_t m_node_address;
162  ValueObject *m_tail;
163 };
164 
165 } // end anonymous namespace
166 
167 bool 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 
193 bool 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 
227 ValueObjectSP 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 
242 ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj)
243  : AbstractListFrontEnd(valobj) {
244  Update();
245 }
246 
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 
260 ValueObjectSP 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;
281  Status error;
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 
291 bool 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 
310 ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp)
311  : AbstractListFrontEnd(*valobj_sp), m_node_address(), m_tail(nullptr) {
312  if (valobj_sp)
313  Update();
314 }
315 
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 
352 lldb::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;
391  Status error;
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 
403 bool 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 }
lldb_private::CompilerType::GetNonReferenceType
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...
Definition: CompilerType.cpp:394
lldb_private::ExecutionContext
Definition: ExecutionContext.h:292
lldb_private::CompilerType::GetNumTemplateArguments
size_t GetNumTemplateArguments() const
Definition: CompilerType.cpp:662
CalculateNumChildren
static size_t CalculateNumChildren(CompilerType container_type, CompilerType element_type, lldb_private::ExecutionContextScope *exe_scope=nullptr)
Definition: VectorType.cpp:169
lldb_private::SyntheticChildrenFrontEnd
Definition: TypeSynthetic.h:27
lldb::addr_t
uint64_t addr_t
Definition: lldb-types.h:83
lldb_private::StreamString::GetString
llvm::StringRef GetString() const
Definition: StreamString.cpp:51
Target.h
lldb_private::CompilerType::GetTypeTemplateArgument
CompilerType GetTypeTemplateArgument(size_t idx) const
Definition: CompilerType.cpp:675
error
static llvm::raw_ostream & error(Stream &strm)
Definition: CommandReturnObject.cpp:17
lldb_private::DataExtractor
Definition: DataExtractor.h:48
TypeSystemClang.h
lldb_private::Status::Fail
bool Fail() const
Test for error condition.
Definition: Status.cpp:182
lldb_private::formatters::GetValueOfLibCXXCompressedPair
lldb::ValueObjectSP GetValueOfLibCXXCompressedPair(ValueObject &pair)
Definition: FormattersHelpers.cpp:150
lldb_private::ConstString
Definition: ConstString.h:40
lldb_private::StreamString
Definition: StreamString.h:23
lldb::operator==
bool LLDB_API operator==(const SBAddress &lhs, const SBAddress &rhs)
Definition: SBAddress.cpp:63
lldb_private::CompilerType::IsReferenceType
bool IsReferenceType(CompilerType *pointee_type=nullptr, bool *is_rvalue=nullptr) const
Definition: CompilerType.cpp:175
ValueObject.h
lldb_private::operator!=
bool operator!=(const Address &lhs, const Address &rhs)
Definition: Address.cpp:1005
ValueObjectConstResult.h
lldb_private::formatters::LibcxxStdListSyntheticFrontEndCreator
SyntheticChildrenFrontEnd * LibcxxStdListSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxList.cpp:424
lldb_private::Status
Definition: Status.h:44
lldb_private::ValueObject
ValueObject:
Definition: ValueObject.h:105
lldb_private::formatters::LibcxxStdForwardListSyntheticFrontEndCreator
SyntheticChildrenFrontEnd * LibcxxStdForwardListSyntheticFrontEndCreator(CXXSyntheticChildren *, lldb::ValueObjectSP)
Definition: LibCxxList.cpp:430
UINT32_MAX
#define UINT32_MAX
Definition: lldb-defines.h:31
LLDB_INVALID_ADDRESS
#define LLDB_INVALID_ADDRESS
Definition: lldb-defines.h:86
lldb_private::ConstString::GetCString
const char * GetCString() const
Get the string value as a C string.
Definition: ConstString.h:216
lldb_private::CompilerType
Generic representation of a type in a programming language.
Definition: CompilerType.h:33
lldb_private::Stream::Printf
size_t Printf(const char *format,...) __attribute__((format(printf
Output printf formatted output to the stream.
Definition: Stream.cpp:107
Status.h
lldb_private::formatters
Definition: CXXFunctionPointer.h:15
lldb_private
A class that represents a running process on the host machine.
Definition: SBCommandInterpreterRunOptions.h:16
LibCxx.h
Stream.h
lldb_private::CXXSyntheticChildren
Definition: TypeSynthetic.h:358
FormattersHelpers.h
lldb
Definition: SBAddress.h:15
Endian.h
lldb_private::formatters::ExtractIndexFromString
size_t ExtractIndexFromString(const char *item_name)
Definition: FormattersHelpers.cpp:119
DataBufferHeap.h