Coverage Report

Created: 2022-01-15 10:30

/Users/buildslave/jenkins/workspace/coverage/llvm-project/lldb/include/lldb/Symbol/LineTable.h
Line
Count
Source (jump to first uncovered line)
1
//===-- LineTable.h ---------------------------------------------*- C++ -*-===//
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
#ifndef LLDB_SYMBOL_LINETABLE_H
10
#define LLDB_SYMBOL_LINETABLE_H
11
12
#include "lldb/Core/Address.h"
13
#include "lldb/Core/ModuleChild.h"
14
#include "lldb/Core/Section.h"
15
#include "lldb/Core/SourceLocationSpec.h"
16
#include "lldb/Symbol/LineEntry.h"
17
#include "lldb/Utility/RangeMap.h"
18
#include "lldb/lldb-private.h"
19
#include <vector>
20
21
namespace lldb_private {
22
23
/// \class LineSequence LineTable.h "lldb/Symbol/LineTable.h" An abstract base
24
/// class used during symbol table creation.
25
class LineSequence {
26
public:
27
  LineSequence();
28
29
31.9k
  virtual ~LineSequence() = default;
30
31
  virtual void Clear() = 0;
32
33
private:
34
  LineSequence(const LineSequence &) = delete;
35
  const LineSequence &operator=(const LineSequence &) = delete;
36
};
37
38
/// \class LineTable LineTable.h "lldb/Symbol/LineTable.h"
39
/// A line table class.
40
class LineTable {
41
public:
42
  /// Construct with compile unit.
43
  ///
44
  /// \param[in] comp_unit
45
  ///     The compile unit to which this line table belongs.
46
  LineTable(CompileUnit *comp_unit);
47
48
  /// Construct with entries found in \a sequences.
49
  ///
50
  /// \param[in] sequences
51
  ///     Unsorted list of line sequences.
52
  LineTable(CompileUnit *comp_unit,
53
            std::vector<std::unique_ptr<LineSequence>> &&sequences);
54
55
  /// Destructor.
56
  ~LineTable();
57
58
  /// Adds a new line entry to this line table.
59
  ///
60
  /// All line entries are maintained in file address order.
61
  ///
62
  /// \param[in] line_entry
63
  ///     A const reference to a new line_entry to add to this line
64
  ///     table.
65
  ///
66
  /// \see Address::DumpStyle
67
  //  void
68
  //  AddLineEntry (const LineEntry& line_entry);
69
70
  // Called when you can't guarantee the addresses are in increasing order
71
  void InsertLineEntry(lldb::addr_t file_addr, uint32_t line, uint16_t column,
72
                       uint16_t file_idx, bool is_start_of_statement,
73
                       bool is_start_of_basic_block, bool is_prologue_end,
74
                       bool is_epilogue_begin, bool is_terminal_entry);
75
76
  // Used to instantiate the LineSequence helper class
77
  static std::unique_ptr<LineSequence> CreateLineSequenceContainer();
78
79
  // Append an entry to a caller-provided collection that will later be
80
  // inserted in this line table.
81
  static void AppendLineEntryToSequence(LineSequence *sequence, lldb::addr_t file_addr,
82
                                 uint32_t line, uint16_t column,
83
                                 uint16_t file_idx, bool is_start_of_statement,
84
                                 bool is_start_of_basic_block,
85
                                 bool is_prologue_end, bool is_epilogue_begin,
86
                                 bool is_terminal_entry);
87
88
  // Insert a sequence of entries into this line table.
89
  void InsertSequence(LineSequence *sequence);
90
91
  /// Dump all line entries in this line table to the stream \a s.
92
  ///
93
  /// \param[in] s
94
  ///     The stream to which to dump the object description.
95
  ///
96
  /// \param[in] style
97
  ///     The display style for the address.
98
  ///
99
  /// \see Address::DumpStyle
100
  void Dump(Stream *s, Target *target, Address::DumpStyle style,
101
            Address::DumpStyle fallback_style, bool show_line_ranges);
102
103
  void GetDescription(Stream *s, Target *target, lldb::DescriptionLevel level);
104
105
  /// Find a line entry that contains the section offset address \a so_addr.
106
  ///
107
  /// \param[in] so_addr
108
  ///     A section offset address object containing the address we
109
  ///     are searching for.
110
  ///
111
  /// \param[out] line_entry
112
  ///     A copy of the line entry that was found if \b true is
113
  ///     returned, otherwise \a entry is left unmodified.
114
  ///
115
  /// \param[out] index_ptr
116
  ///     A pointer to a 32 bit integer that will get the actual line
117
  ///     entry index if it is not nullptr.
118
  ///
119
  /// \return
120
  ///     Returns \b true if \a so_addr is contained in a line entry
121
  ///     in this line table, \b false otherwise.
122
  bool FindLineEntryByAddress(const Address &so_addr, LineEntry &line_entry,
123
                              uint32_t *index_ptr = nullptr);
124
125
  /// Find a line entry index that has a matching file index and source line
126
  /// number.
127
  ///
128
  /// Finds the next line entry that has a matching \a file_idx and source
129
  /// line number \a line starting at the \a start_idx entries into the line
130
  /// entry collection.
131
  ///
132
  /// \param[in] start_idx
133
  ///     The number of entries to skip when starting the search.
134
  ///
135
  /// \param[out] file_idx
136
  ///     The file index to search for that should be found prior
137
  ///     to calling this function using the following functions:
138
  ///     CompileUnit::GetSupportFiles()
139
  ///     FileSpecList::FindFileIndex (uint32_t, const FileSpec &) const
140
  ///
141
  /// \param[in] src_location_spec
142
  ///     The source location specifier to match.
143
  ///
144
  /// \param[out] line_entry_ptr
145
  ///     A pointer to a line entry object that will get a copy of
146
  ///     the line entry if \b true is returned, otherwise \a
147
  ///     line_entry is left untouched.
148
  ///
149
  /// \return
150
  ///     Returns \b true if a matching line entry is found in this
151
  ///     line table, \b false otherwise.
152
  ///
153
  /// \see CompileUnit::GetSupportFiles()
154
  /// \see FileSpecList::FindFileIndex (uint32_t, const FileSpec &) const
155
  uint32_t
156
  FindLineEntryIndexByFileIndex(uint32_t start_idx, uint32_t file_idx,
157
                                const SourceLocationSpec &src_location_spec,
158
                                LineEntry *line_entry_ptr);
159
160
  uint32_t FindLineEntryIndexByFileIndex(
161
      uint32_t start_idx, const std::vector<uint32_t> &file_idx,
162
      const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr);
163
164
  size_t FineLineEntriesForFileIndex(uint32_t file_idx, bool append,
165
                                     SymbolContextList &sc_list);
166
167
  /// Get the line entry from the line table at index \a idx.
168
  ///
169
  /// \param[in] idx
170
  ///     An index into the line table entry collection.
171
  ///
172
  /// \return
173
  ///     A valid line entry if \a idx is a valid index, or an invalid
174
  ///     line entry if \a idx is not valid.
175
  ///
176
  /// \see LineTable::GetSize()
177
  /// \see LineEntry::IsValid() const
178
  bool GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry);
179
180
  /// Gets the size of the line table in number of line table entries.
181
  ///
182
  /// \return
183
  ///     The number of line table entries in this line table.
184
  uint32_t GetSize() const;
185
186
  typedef lldb_private::RangeVector<lldb::addr_t, lldb::addr_t, 32>
187
      FileAddressRanges;
188
189
  /// Gets all contiguous file address ranges for the entire line table.
190
  ///
191
  /// \param[out] file_ranges
192
  ///     A collection of file address ranges that will be filled in
193
  ///     by this function.
194
  ///
195
  /// \param[out] append
196
  ///     If \b true, then append to \a file_ranges, otherwise clear
197
  ///     \a file_ranges prior to adding any ranges.
198
  ///
199
  /// \return
200
  ///     The number of address ranges added to \a file_ranges
201
  size_t GetContiguousFileAddressRanges(FileAddressRanges &file_ranges,
202
                                        bool append);
203
204
  typedef RangeDataVector<lldb::addr_t, lldb::addr_t, lldb::addr_t>
205
      FileRangeMap;
206
207
  LineTable *LinkLineTable(const FileRangeMap &file_range_map);
208
209
  struct Entry {
210
    Entry()
211
        : line(0), is_start_of_statement(false), is_start_of_basic_block(false),
212
          is_prologue_end(false), is_epilogue_begin(false),
213
23.5k
          is_terminal_entry(false) {}
214
215
    Entry(lldb::addr_t _file_addr, uint32_t _line, uint16_t _column,
216
          uint16_t _file_idx, bool _is_start_of_statement,
217
          bool _is_start_of_basic_block, bool _is_prologue_end,
218
          bool _is_epilogue_begin, bool _is_terminal_entry)
219
        : file_addr(_file_addr), line(_line),
220
          is_start_of_statement(_is_start_of_statement),
221
          is_start_of_basic_block(_is_start_of_basic_block),
222
          is_prologue_end(_is_prologue_end),
223
          is_epilogue_begin(_is_epilogue_begin),
224
          is_terminal_entry(_is_terminal_entry), column(_column),
225
535k
          file_idx(_file_idx) {}
226
227
    int bsearch_compare(const void *key, const void *arrmem);
228
229
0
    void Clear() {
230
0
      file_addr = LLDB_INVALID_ADDRESS;
231
0
      line = 0;
232
0
      column = 0;
233
0
      file_idx = 0;
234
0
      is_start_of_statement = false;
235
0
      is_start_of_basic_block = false;
236
0
      is_prologue_end = false;
237
0
      is_epilogue_begin = false;
238
0
      is_terminal_entry = false;
239
0
    }
240
241
0
    static int Compare(const Entry &lhs, const Entry &rhs) {
242
0
// Compare the sections before calling
243
0
#define SCALAR_COMPARE(a, b)                                                   \
244
0
  if (a < b)                                                                   \
245
0
    return -1;                                                                 \
246
0
  if (a > b)                                                                   \
247
0
  return +1
248
0
      SCALAR_COMPARE(lhs.file_addr, rhs.file_addr);
249
0
      SCALAR_COMPARE(lhs.line, rhs.line);
250
0
      SCALAR_COMPARE(lhs.column, rhs.column);
251
0
      SCALAR_COMPARE(lhs.is_start_of_statement, rhs.is_start_of_statement);
252
0
      SCALAR_COMPARE(lhs.is_start_of_basic_block, rhs.is_start_of_basic_block);
253
0
      // rhs and lhs reversed on purpose below.
254
0
      SCALAR_COMPARE(rhs.is_prologue_end, lhs.is_prologue_end);
255
0
      SCALAR_COMPARE(lhs.is_epilogue_begin, rhs.is_epilogue_begin);
256
0
      // rhs and lhs reversed on purpose below.
257
0
      SCALAR_COMPARE(rhs.is_terminal_entry, lhs.is_terminal_entry);
258
0
      SCALAR_COMPARE(lhs.file_idx, rhs.file_idx);
259
0
#undef SCALAR_COMPARE
260
0
      return 0;
261
0
    }
262
263
    class LessThanBinaryPredicate {
264
    public:
265
      LessThanBinaryPredicate(LineTable *line_table);
266
      bool operator()(const LineTable::Entry &, const LineTable::Entry &) const;
267
      bool operator()(const std::unique_ptr<LineSequence> &,
268
                      const std::unique_ptr<LineSequence> &) const;
269
270
    protected:
271
      LineTable *m_line_table;
272
    };
273
274
158k
    static bool EntryAddressLessThan(const Entry &lhs, const Entry &rhs) {
275
158k
      return lhs.file_addr < rhs.file_addr;
276
158k
    }
277
278
    // Member variables.
279
    /// The file address for this line entry.
280
    lldb::addr_t file_addr = LLDB_INVALID_ADDRESS;
281
    /// The source line number, or zero if there is no line number
282
    /// information.
283
    uint32_t line : 27;
284
    /// Indicates this entry is the beginning of a statement.
285
    uint32_t is_start_of_statement : 1;
286
    /// Indicates this entry is the beginning of a basic block.
287
    uint32_t is_start_of_basic_block : 1;
288
    /// Indicates this entry is one (of possibly many) where execution
289
    /// should be suspended for an entry breakpoint of a function.
290
    uint32_t is_prologue_end : 1;
291
    /// Indicates this entry is one (of possibly many) where execution
292
    /// should be suspended for an exit breakpoint of a function.
293
    uint32_t is_epilogue_begin : 1;
294
    /// Indicates this entry is that of the first byte after the end
295
    /// of a sequence of target machine instructions.
296
    uint32_t is_terminal_entry : 1;
297
    /// The column number of the source line, or zero if there is no
298
    /// column information.
299
    uint16_t column = 0;
300
    /// The file index into CompileUnit's file table, or zero if there
301
    /// is no file information.
302
    uint16_t file_idx = 0;
303
  };
304
305
protected:
306
  struct EntrySearchInfo {
307
    LineTable *line_table;
308
    lldb_private::Section *a_section;
309
    Entry *a_entry;
310
  };
311
312
  // Types
313
  typedef std::vector<lldb_private::Section *>
314
      section_collection; ///< The collection type for the sections.
315
  typedef std::vector<Entry>
316
      entry_collection; ///< The collection type for the line entries.
317
  // Member variables.
318
  CompileUnit
319
      *m_comp_unit; ///< The compile unit that this line table belongs to.
320
  entry_collection
321
      m_entries; ///< The collection of line entries in this line table.
322
323
  // Helper class
324
  class LineSequenceImpl : public LineSequence {
325
  public:
326
31.9k
    LineSequenceImpl() = default;
327
328
31.9k
    ~LineSequenceImpl() override = default;
329
330
    void Clear() override;
331
332
    entry_collection
333
        m_entries; ///< The collection of line entries in this sequence.
334
  };
335
336
  bool ConvertEntryAtIndexToLineEntry(uint32_t idx, LineEntry &line_entry);
337
338
private:
339
  LineTable(const LineTable &) = delete;
340
  const LineTable &operator=(const LineTable &) = delete;
341
342
  template <typename T>
343
  uint32_t FindLineEntryIndexByFileIndexImpl(
344
      uint32_t start_idx, T file_idx,
345
      const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr,
346
8.42k
      std::function<bool(T, uint16_t)> file_idx_matcher) {
347
8.42k
    const size_t count = m_entries.size();
348
8.42k
    size_t best_match = UINT32_MAX;
349
350
8.42k
    if (!line_entry_ptr)
351
0
      return best_match;
352
353
8.42k
    const uint32_t line = src_location_spec.GetLine().getValueOr(0);
354
8.42k
    const uint16_t column =
355
8.42k
        src_location_spec.GetColumn().getValueOr(LLDB_INVALID_COLUMN_NUMBER);
356
8.42k
    const bool exact_match = src_location_spec.GetExactMatch();
357
358
1.24M
    for (size_t idx = start_idx; idx < count; 
++idx1.23M
) {
359
      // Skip line table rows that terminate the previous row (is_terminal_entry
360
      // is non-zero)
361
1.23M
      if (m_entries[idx].is_terminal_entry)
362
73.5k
        continue;
363
364
1.16M
      if (!file_idx_matcher(file_idx, m_entries[idx].file_idx))
365
946k
        continue;
366
367
      // Exact match always wins.  Otherwise try to find the closest line > the
368
      // desired line.
369
      // FIXME: Maybe want to find the line closest before and the line closest
370
      // after and if they're not in the same function, don't return a match.
371
372
219k
      if (column == LLDB_INVALID_COLUMN_NUMBER) {
373
218k
        if (m_entries[idx].line < line) {
374
166k
          continue;
375
166k
        } else 
if (51.0k
m_entries[idx].line == line51.0k
) {
376
5.05k
          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
377
5.05k
          return idx;
378
45.9k
        } else if (!exact_match) {
379
8.59k
          if (best_match == UINT32_MAX ||
380
8.59k
              
m_entries[idx].line < m_entries[best_match].line8.01k
)
381
622
            best_match = idx;
382
8.59k
        }
383
218k
      } else {
384
993
        if (m_entries[idx].line < line) {
385
474
          continue;
386
519
        } else if (m_entries[idx].line == line &&
387
519
                   
m_entries[idx].column == column96
) {
388
12
          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
389
12
          return idx;
390
507
        } else if (!exact_match) {
391
239
          if (best_match == UINT32_MAX)
392
17
            best_match = idx;
393
222
          else if (m_entries[idx].line < m_entries[best_match].line)
394
6
            best_match = idx;
395
216
          else if (m_entries[idx].line == m_entries[best_match].line)
396
60
            if (m_entries[idx].column &&
397
60
                
m_entries[idx].column < m_entries[best_match].column57
)
398
12
              best_match = idx;
399
239
        }
400
993
      }
401
219k
    }
402
403
3.35k
    if (best_match != UINT32_MAX) {
404
344
      if (line_entry_ptr)
405
344
        ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
406
344
      return best_match;
407
344
    }
408
3.01k
    return UINT32_MAX;
409
3.35k
  }
unsigned int lldb_private::LineTable::FindLineEntryIndexByFileIndexImpl<unsigned int>(unsigned int, unsigned int, lldb_private::SourceLocationSpec const&, lldb_private::LineEntry*, std::__1::function<bool (unsigned int, unsigned short)>)
Line
Count
Source
346
8.16k
      std::function<bool(T, uint16_t)> file_idx_matcher) {
347
8.16k
    const size_t count = m_entries.size();
348
8.16k
    size_t best_match = UINT32_MAX;
349
350
8.16k
    if (!line_entry_ptr)
351
0
      return best_match;
352
353
8.16k
    const uint32_t line = src_location_spec.GetLine().getValueOr(0);
354
8.16k
    const uint16_t column =
355
8.16k
        src_location_spec.GetColumn().getValueOr(LLDB_INVALID_COLUMN_NUMBER);
356
8.16k
    const bool exact_match = src_location_spec.GetExactMatch();
357
358
1.21M
    for (size_t idx = start_idx; idx < count; 
++idx1.20M
) {
359
      // Skip line table rows that terminate the previous row (is_terminal_entry
360
      // is non-zero)
361
1.21M
      if (m_entries[idx].is_terminal_entry)
362
73.3k
        continue;
363
364
1.13M
      if (!file_idx_matcher(file_idx, m_entries[idx].file_idx))
365
946k
        continue;
366
367
      // Exact match always wins.  Otherwise try to find the closest line > the
368
      // desired line.
369
      // FIXME: Maybe want to find the line closest before and the line closest
370
      // after and if they're not in the same function, don't return a match.
371
372
193k
      if (column == LLDB_INVALID_COLUMN_NUMBER) {
373
192k
        if (m_entries[idx].line < line) {
374
142k
          continue;
375
142k
        } else 
if (50.2k
m_entries[idx].line == line50.2k
) {
376
4.91k
          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
377
4.91k
          return idx;
378
45.2k
        } else if (!exact_match) {
379
8.21k
          if (best_match == UINT32_MAX ||
380
8.21k
              
m_entries[idx].line < m_entries[best_match].line7.67k
)
381
580
            best_match = idx;
382
8.21k
        }
383
192k
      } else {
384
993
        if (m_entries[idx].line < line) {
385
474
          continue;
386
519
        } else if (m_entries[idx].line == line &&
387
519
                   
m_entries[idx].column == column96
) {
388
12
          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
389
12
          return idx;
390
507
        } else if (!exact_match) {
391
239
          if (best_match == UINT32_MAX)
392
17
            best_match = idx;
393
222
          else if (m_entries[idx].line < m_entries[best_match].line)
394
6
            best_match = idx;
395
216
          else if (m_entries[idx].line == m_entries[best_match].line)
396
60
            if (m_entries[idx].column &&
397
60
                
m_entries[idx].column < m_entries[best_match].column57
)
398
12
              best_match = idx;
399
239
        }
400
993
      }
401
193k
    }
402
403
3.23k
    if (best_match != UINT32_MAX) {
404
302
      if (line_entry_ptr)
405
302
        ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
406
302
      return best_match;
407
302
    }
408
2.93k
    return UINT32_MAX;
409
3.23k
  }
unsigned int lldb_private::LineTable::FindLineEntryIndexByFileIndexImpl<std::__1::vector<unsigned int, std::__1::allocator<unsigned int> > >(unsigned int, std::__1::vector<unsigned int, std::__1::allocator<unsigned int> >, lldb_private::SourceLocationSpec const&, lldb_private::LineEntry*, std::__1::function<bool (std::__1::vector<unsigned int, std::__1::allocator<unsigned int> >, unsigned short)>)
Line
Count
Source
346
260
      std::function<bool(T, uint16_t)> file_idx_matcher) {
347
260
    const size_t count = m_entries.size();
348
260
    size_t best_match = UINT32_MAX;
349
350
260
    if (!line_entry_ptr)
351
0
      return best_match;
352
353
260
    const uint32_t line = src_location_spec.GetLine().getValueOr(0);
354
260
    const uint16_t column =
355
260
        src_location_spec.GetColumn().getValueOr(LLDB_INVALID_COLUMN_NUMBER);
356
260
    const bool exact_match = src_location_spec.GetExactMatch();
357
358
26.1k
    for (size_t idx = start_idx; idx < count; 
++idx25.8k
) {
359
      // Skip line table rows that terminate the previous row (is_terminal_entry
360
      // is non-zero)
361
26.0k
      if (m_entries[idx].is_terminal_entry)
362
233
        continue;
363
364
25.8k
      if (!file_idx_matcher(file_idx, m_entries[idx].file_idx))
365
468
        continue;
366
367
      // Exact match always wins.  Otherwise try to find the closest line > the
368
      // desired line.
369
      // FIXME: Maybe want to find the line closest before and the line closest
370
      // after and if they're not in the same function, don't return a match.
371
372
25.3k
      if (column == LLDB_INVALID_COLUMN_NUMBER) {
373
25.3k
        if (m_entries[idx].line < line) {
374
24.4k
          continue;
375
24.4k
        } else 
if (847
m_entries[idx].line == line847
) {
376
135
          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
377
135
          return idx;
378
712
        } else if (!exact_match) {
379
382
          if (best_match == UINT32_MAX ||
380
382
              
m_entries[idx].line < m_entries[best_match].line340
)
381
42
            best_match = idx;
382
382
        }
383
25.3k
      } else {
384
0
        if (m_entries[idx].line < line) {
385
0
          continue;
386
0
        } else if (m_entries[idx].line == line &&
387
0
                   m_entries[idx].column == column) {
388
0
          ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
389
0
          return idx;
390
0
        } else if (!exact_match) {
391
0
          if (best_match == UINT32_MAX)
392
0
            best_match = idx;
393
0
          else if (m_entries[idx].line < m_entries[best_match].line)
394
0
            best_match = idx;
395
0
          else if (m_entries[idx].line == m_entries[best_match].line)
396
0
            if (m_entries[idx].column &&
397
0
                m_entries[idx].column < m_entries[best_match].column)
398
0
              best_match = idx;
399
0
        }
400
0
      }
401
25.3k
    }
402
403
125
    if (best_match != UINT32_MAX) {
404
42
      if (line_entry_ptr)
405
42
        ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
406
42
      return best_match;
407
42
    }
408
83
    return UINT32_MAX;
409
125
  }
410
};
411
412
} // namespace lldb_private
413
414
#endif // LLDB_SYMBOL_LINETABLE_H