Coverage Report

Created: 2022-01-15 10:30

/Users/buildslave/jenkins/workspace/coverage/llvm-project/lldb/source/Plugins/Language/CPlusPlus/LibCxxList.cpp
Line
Count
Source (jump to first uncovered line)
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
11
#include "Plugins/TypeSystem/Clang/TypeSystemClang.h"
12
#include "lldb/Core/ValueObject.h"
13
#include "lldb/Core/ValueObjectConstResult.h"
14
#include "lldb/DataFormatters/FormattersHelpers.h"
15
#include "lldb/Target/Target.h"
16
#include "lldb/Utility/DataBufferHeap.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
2.74k
  ListEntry() = default;
30
12.2k
  ListEntry(ValueObjectSP entry_sp) : m_entry_sp(std::move(entry_sp)) {}
31
  ListEntry(ValueObject *entry)
32
2.64k
      : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {}
33
34
12.2k
  ListEntry next() {
35
12.2k
    static ConstString g_next("__next_");
36
37
12.2k
    if (!m_entry_sp)
38
0
      return ListEntry();
39
12.2k
    return ListEntry(m_entry_sp->GetChildMemberWithName(g_next, true));
40
12.2k
  }
41
42
0
  ListEntry prev() {
43
0
    static ConstString g_prev("__prev_");
44
0
45
0
    if (!m_entry_sp)
46
0
      return ListEntry();
47
0
    return ListEntry(m_entry_sp->GetChildMemberWithName(g_prev, true));
48
0
  }
49
50
12.2k
  uint64_t value() const {
51
12.2k
    if (!m_entry_sp)
52
0
      return 0;
53
12.2k
    return m_entry_sp->GetValueAsUnsigned(0);
54
12.2k
  }
55
56
7.36k
  bool null() { return (value() == 0); }
57
58
7.36k
  explicit operator bool() { return GetEntry() && 
!null()7.36k
; }
59
60
9.91k
  ValueObjectSP GetEntry() { return m_entry_sp; }
61
62
404
  void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }
63
64
2.44k
  bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); }
65
66
2.44k
  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
2.54k
  ListIterator() = default;
75
0
  ListIterator(ListEntry entry) : m_entry(std::move(entry)) {}
76
0
  ListIterator(ValueObjectSP entry) : m_entry(std::move(entry)) {}
77
2.54k
  ListIterator(ValueObject *entry) : m_entry(entry) {}
78
79
0
  ValueObjectSP value() { return m_entry.GetEntry(); }
80
81
2.54k
  ValueObjectSP advance(size_t count) {
82
2.54k
    if (count == 0)
83
83
      return m_entry.GetEntry();
84
2.46k
    if (count == 1) {
85
2.46k
      next();
86
2.46k
      return m_entry.GetEntry();
87
2.46k
    }
88
0
    while (count > 0) {
89
0
      next();
90
0
      count--;
91
0
      if (m_entry.null())
92
0
        return lldb::ValueObjectSP();
93
0
    }
94
0
    return m_entry.GetEntry();
95
0
  }
96
97
0
  bool operator==(const ListIterator &rhs) const {
98
0
    return (rhs.m_entry == m_entry);
99
0
  }
100
101
protected:
102
2.46k
  void next() { m_entry = m_entry.next(); }
103
104
0
  void prev() { m_entry = m_entry.prev(); }
105
106
private:
107
  ListEntry m_entry;
108
};
109
110
class AbstractListFrontEnd : public SyntheticChildrenFrontEnd {
111
public:
112
0
  size_t GetIndexOfChildWithName(ConstString name) override {
113
0
    return ExtractIndexFromString(name.GetCString());
114
0
  }
115
39
  bool MightHaveChildren() override { return true; }
116
  bool Update() override;
117
118
protected:
119
  AbstractListFrontEnd(ValueObject &valobj)
120
101
      : 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
15
  ~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
202
bool AbstractListFrontEnd::Update() {
168
202
  m_loop_detected = 0;
169
202
  m_count = UINT32_MAX;
170
202
  m_head = nullptr;
171
202
  m_list_capping_size = 0;
172
202
  m_slow_runner.SetEntry(nullptr);
173
202
  m_fast_runner.SetEntry(nullptr);
174
202
  m_iterators.clear();
175
176
202
  if (m_backend.GetTargetSP())
177
202
    m_list_capping_size =
178
202
        m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay();
179
202
  if (m_list_capping_size == 0)
180
0
    m_list_capping_size = 255;
181
182
202
  CompilerType list_type = m_backend.GetCompilerType();
183
202
  if (list_type.IsReferenceType())
184
24
    list_type = list_type.GetNonReferenceType();
185
186
202
  if (list_type.GetNumTemplateArguments() == 0)
187
0
    return false;
188
202
  m_element_type = list_type.GetTypeTemplateArgument(0);
189
190
202
  return false;
191
202
}
192
193
2.54k
bool AbstractListFrontEnd::HasLoop(size_t count) {
194
2.54k
  if (!g_use_loop_detect)
195
0
    return false;
196
  // don't bother checking for a loop if we won't actually need to jump nodes
197
2.54k
  if (m_count < 2)
198
27
    return false;
199
200
2.51k
  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
56
    m_slow_runner = ListEntry(m_head).next();
204
56
    m_fast_runner = m_slow_runner.next();
205
56
    m_loop_detected = 1;
206
56
  }
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
2.51k
  const size_t steps_to_run = std::min(count, m_count);
213
4.96k
  while (m_loop_detected < steps_to_run && 
m_slow_runner2.46k
&&
m_fast_runner2.46k
&&
214
4.96k
         
m_slow_runner != m_fast_runner2.44k
) {
215
216
2.44k
    m_slow_runner = m_slow_runner.next();
217
2.44k
    m_fast_runner = m_fast_runner.next().next();
218
2.44k
    m_loop_detected++;
219
2.44k
  }
220
2.51k
  if (count <= m_loop_detected)
221
2.50k
    return false; // No loop in the first m_loop_detected elements.
222
18
  if (!m_slow_runner || !m_fast_runner)
223
18
    return false; // Reached the end of the list. Definitely no loops.
224
0
  return m_slow_runner == m_fast_runner;
225
18
}
226
227
2.54k
ValueObjectSP AbstractListFrontEnd::GetItem(size_t idx) {
228
2.54k
  size_t advance = idx;
229
2.54k
  ListIterator current(m_head);
230
2.54k
  if (idx > 0) {
231
2.46k
    auto cached_iterator = m_iterators.find(idx - 1);
232
2.46k
    if (cached_iterator != m_iterators.end()) {
233
2.46k
      current = cached_iterator->second;
234
2.46k
      advance = 1;
235
2.46k
    }
236
2.46k
  }
237
2.54k
  ValueObjectSP value_sp = current.advance(advance);
238
2.54k
  m_iterators[idx] = current;
239
2.54k
  return value_sp;
240
2.54k
}
241
242
ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj)
243
42
    : AbstractListFrontEnd(valobj) {
244
42
  Update();
245
42
}
246
247
2.41k
size_t ForwardListFrontEnd::CalculateNumChildren() {
248
2.41k
  if (m_count != UINT32_MAX)
249
2.37k
    return m_count;
250
251
42
  ListEntry current(m_head);
252
42
  m_count = 0;
253
2.40k
  while (current && 
m_count < m_list_capping_size2.37k
) {
254
2.36k
    ++m_count;
255
2.36k
    current = current.next();
256
2.36k
  }
257
42
  return m_count;
258
2.41k
}
259
260
2.37k
ValueObjectSP ForwardListFrontEnd::GetChildAtIndex(size_t idx) {
261
2.37k
  if (idx >= CalculateNumChildren())
262
0
    return nullptr;
263
264
2.37k
  if (!m_head)
265
0
    return nullptr;
266
267
2.37k
  if (HasLoop(idx + 1))
268
0
    return nullptr;
269
270
2.37k
  ValueObjectSP current_sp = GetItem(idx);
271
2.37k
  if (!current_sp)
272
0
    return nullptr;
273
274
2.37k
  current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
275
2.37k
  if (!current_sp)
276
12
    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
2.35k
  DataExtractor data;
281
2.35k
  Status error;
282
2.35k
  current_sp->GetData(data, error);
283
2.35k
  if (error.Fail())
284
0
    return nullptr;
285
286
2.35k
  return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data,
287
2.35k
                                   m_backend.GetExecutionContextRef(),
288
2.35k
                                   m_element_type);
289
2.35k
}
290
291
84
bool ForwardListFrontEnd::Update() {
292
84
  AbstractListFrontEnd::Update();
293
294
84
  Status err;
295
84
  ValueObjectSP backend_addr(m_backend.AddressOf(err));
296
84
  if (err.Fail() || !backend_addr)
297
0
    return false;
298
299
84
  ValueObjectSP impl_sp(
300
84
      m_backend.GetChildMemberWithName(ConstString("__before_begin_"), true));
301
84
  if (!impl_sp)
302
0
    return false;
303
84
  impl_sp = GetValueOfLibCXXCompressedPair(*impl_sp);
304
84
  if (!impl_sp)
305
0
    return false;
306
84
  m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
307
84
  return false;
308
84
}
309
310
ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp)
311
59
    : AbstractListFrontEnd(*valobj_sp), m_node_address(), m_tail(nullptr) {
312
59
  if (valobj_sp)
313
59
    Update();
314
59
}
315
316
235
size_t ListFrontEnd::CalculateNumChildren() {
317
235
  if (m_count != UINT32_MAX)
318
176
    return m_count;
319
59
  if (!m_head || !m_tail || m_node_address == 0)
320
0
    return 0;
321
59
  ValueObjectSP size_alloc(
322
59
      m_backend.GetChildMemberWithName(ConstString("__size_alloc_"), true));
323
59
  if (size_alloc) {
324
59
    ValueObjectSP value = GetValueOfLibCXXCompressedPair(*size_alloc);
325
59
    if (value) {
326
59
      m_count = value->GetValueAsUnsigned(UINT32_MAX);
327
59
    }
328
59
  }
329
59
  if (m_count != UINT32_MAX) {
330
59
    return m_count;
331
59
  } else {
332
0
    uint64_t next_val = m_head->GetValueAsUnsigned(0);
333
0
    uint64_t prev_val = m_tail->GetValueAsUnsigned(0);
334
0
    if (next_val == 0 || prev_val == 0)
335
0
      return 0;
336
0
    if (next_val == m_node_address)
337
0
      return 0;
338
0
    if (next_val == prev_val)
339
0
      return 1;
340
0
    uint64_t size = 2;
341
0
    ListEntry current(m_head);
342
0
    while (current.next() && current.next().value() != m_node_address) {
343
0
      size++;
344
0
      current = current.next();
345
0
      if (size > m_list_capping_size)
346
0
        break;
347
0
    }
348
0
    return m_count = (size - 1);
349
0
  }
350
59
}
351
352
176
lldb::ValueObjectSP ListFrontEnd::GetChildAtIndex(size_t idx) {
353
176
  static ConstString g_value("__value_");
354
176
  static ConstString g_next("__next_");
355
356
176
  if (idx >= CalculateNumChildren())
357
0
    return lldb::ValueObjectSP();
358
359
176
  if (!m_head || !m_tail || m_node_address == 0)
360
0
    return lldb::ValueObjectSP();
361
362
176
  if (HasLoop(idx + 1))
363
0
    return lldb::ValueObjectSP();
364
365
176
  ValueObjectSP current_sp = GetItem(idx);
366
176
  if (!current_sp)
367
0
    return lldb::ValueObjectSP();
368
369
176
  current_sp = current_sp->GetChildAtIndex(1, true); // get the __value_ child
370
176
  if (!current_sp)
371
0
    return lldb::ValueObjectSP();
372
373
176
  if (current_sp->GetName() == g_next) {
374
176
    ProcessSP process_sp(current_sp->GetProcessSP());
375
176
    if (!process_sp)
376
0
      return lldb::ValueObjectSP();
377
378
    // if we grabbed the __next_ pointer, then the child is one pointer deep-er
379
176
    lldb::addr_t addr = current_sp->GetParent()->GetPointerValue();
380
176
    addr = addr + 2 * process_sp->GetAddressByteSize();
381
176
    ExecutionContext exe_ctx(process_sp);
382
176
    current_sp =
383
176
        CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type);
384
176
    if (!current_sp)
385
0
      return lldb::ValueObjectSP();
386
176
  }
387
388
  // we need to copy current_sp into a new object otherwise we will end up with
389
  // all items named __value_
390
176
  DataExtractor data;
391
176
  Status error;
392
176
  current_sp->GetData(data, error);
393
176
  if (error.Fail())
394
0
    return lldb::ValueObjectSP();
395
396
176
  StreamString name;
397
176
  name.Printf("[%" PRIu64 "]", (uint64_t)idx);
398
176
  return CreateValueObjectFromData(name.GetString(), data,
399
176
                                   m_backend.GetExecutionContextRef(),
400
176
                                   m_element_type);
401
176
}
402
403
118
bool ListFrontEnd::Update() {
404
118
  AbstractListFrontEnd::Update();
405
118
  m_tail = nullptr;
406
118
  m_node_address = 0;
407
408
118
  Status err;
409
118
  ValueObjectSP backend_addr(m_backend.AddressOf(err));
410
118
  if (err.Fail() || !backend_addr)
411
0
    return false;
412
118
  m_node_address = backend_addr->GetValueAsUnsigned(0);
413
118
  if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS)
414
0
    return false;
415
118
  ValueObjectSP impl_sp(
416
118
      m_backend.GetChildMemberWithName(ConstString("__end_"), true));
417
118
  if (!impl_sp)
418
0
    return false;
419
118
  m_head = impl_sp->GetChildMemberWithName(ConstString("__next_"), true).get();
420
118
  m_tail = impl_sp->GetChildMemberWithName(ConstString("__prev_"), true).get();
421
118
  return false;
422
118
}
423
424
SyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator(
425
59
    CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
426
59
  return (valobj_sp ? new ListFrontEnd(valobj_sp) : 
nullptr0
);
427
59
}
428
429
SyntheticChildrenFrontEnd *
430
formatters::LibcxxStdForwardListSyntheticFrontEndCreator(
431
42
    CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {
432
42
  return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : 
nullptr0
;
433
42
}