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 LineSequence LineTable.h "lldb/Symbol/LineTable.h" An abstract base
24/// class used during symbol table creation.
25class LineSequence {
26public:
27 LineSequence();
28
29 virtual ~LineSequence() = default;
30
31 virtual void Clear() = 0;
32
33private:
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.
40class LineTable {
41public:
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 FindLineEntriesForFileIndex(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 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 file_idx(_file_idx) {}
226
227 int bsearch_compare(const void *key, const void *arrmem);
228
229 void Clear() {
230 file_addr = LLDB_INVALID_ADDRESS;
231 line = 0;
232 column = 0;
233 file_idx = 0;
234 is_start_of_statement = false;
235 is_start_of_basic_block = false;
236 is_prologue_end = false;
237 is_epilogue_begin = false;
238 is_terminal_entry = false;
239 }
240
241 static int Compare(const Entry &lhs, const Entry &rhs) {
242// Compare the sections before calling
243#define SCALAR_COMPARE(a, b) \
244 if (a < b) \
245 return -1; \
246 if (a > b) \
247 return +1
248 SCALAR_COMPARE(lhs.file_addr, rhs.file_addr);
249 SCALAR_COMPARE(lhs.line, rhs.line);
250 SCALAR_COMPARE(lhs.column, rhs.column);
251 SCALAR_COMPARE(lhs.is_start_of_statement, rhs.is_start_of_statement);
252 SCALAR_COMPARE(lhs.is_start_of_basic_block, rhs.is_start_of_basic_block);
253 // rhs and lhs reversed on purpose below.
254 SCALAR_COMPARE(rhs.is_prologue_end, lhs.is_prologue_end);
255 SCALAR_COMPARE(lhs.is_epilogue_begin, rhs.is_epilogue_begin);
256 // rhs and lhs reversed on purpose below.
257 SCALAR_COMPARE(rhs.is_terminal_entry, lhs.is_terminal_entry);
258 SCALAR_COMPARE(lhs.file_idx, rhs.file_idx);
259#undef SCALAR_COMPARE
260 return 0;
261 }
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 static bool EntryAddressLessThan(const Entry &lhs, const Entry &rhs) {
275 return lhs.file_addr < rhs.file_addr;
276 }
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
305protected:
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 LineSequenceImpl() = default;
327
328 ~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
338private:
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 std::function<bool(T, uint16_t)> file_idx_matcher) {
347 const size_t count = m_entries.size();
348 size_t best_match = UINT32_MAX;
349
350 if (!line_entry_ptr)
351 return best_match;
352
353 const uint32_t line = src_location_spec.GetLine().value_or(u: 0);
354 const uint16_t column =
355 src_location_spec.GetColumn().value_or(LLDB_INVALID_COLUMN_NUMBER);
356 const bool exact_match = src_location_spec.GetExactMatch();
357
358 for (size_t idx = start_idx; idx < count; ++idx) {
359 // Skip line table rows that terminate the previous row (is_terminal_entry
360 // is non-zero)
361 if (m_entries[idx].is_terminal_entry)
362 continue;
363
364 if (!file_idx_matcher(file_idx, m_entries[idx].file_idx))
365 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 if (column == LLDB_INVALID_COLUMN_NUMBER) {
373 if (m_entries[idx].line < line) {
374 continue;
375 } else if (m_entries[idx].line == line) {
376 ConvertEntryAtIndexToLineEntry(idx, line_entry&: *line_entry_ptr);
377 return idx;
378 } else if (!exact_match) {
379 if (best_match == UINT32_MAX ||
380 m_entries[idx].line < m_entries[best_match].line)
381 best_match = idx;
382 }
383 } else {
384 if (m_entries[idx].line < line) {
385 continue;
386 } else if (m_entries[idx].line == line &&
387 m_entries[idx].column == column) {
388 ConvertEntryAtIndexToLineEntry(idx, line_entry&: *line_entry_ptr);
389 return idx;
390 } else if (!exact_match) {
391 if (best_match == UINT32_MAX)
392 best_match = idx;
393 else if (m_entries[idx].line < m_entries[best_match].line)
394 best_match = idx;
395 else if (m_entries[idx].line == m_entries[best_match].line)
396 if (m_entries[idx].column &&
397 m_entries[idx].column < m_entries[best_match].column)
398 best_match = idx;
399 }
400 }
401 }
402
403 if (best_match != UINT32_MAX) {
404 if (line_entry_ptr)
405 ConvertEntryAtIndexToLineEntry(idx: best_match, line_entry&: *line_entry_ptr);
406 return best_match;
407 }
408 return UINT32_MAX;
409 }
410};
411
412} // namespace lldb_private
413
414#endif // LLDB_SYMBOL_LINETABLE_H
415

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