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

source code of lldb/include/lldb/Symbol/LineTable.h