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 LineTable LineTable.h "lldb/Symbol/LineTable.h" |
24 | /// A line table class. |
25 | class LineTable { |
26 | public: |
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 | |
319 | protected: |
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 | |
339 | private: |
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 | |