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 { EntryEntry206 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 EntryEntry211 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 ClearEntry225 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 CompareEntry237 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 EntryAddressLessThanEntry259 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. Sequence(Sequence && rhs)296 Sequence(Sequence &&rhs) : m_entries(std::exchange(rhs.m_entries, {})) {} 297 Sequence &operator=(Sequence &&rhs) { 298 m_entries = std::exchange(rhs.m_entries, {}); 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: LessThanBinaryPredicate(LineTable * line_table)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> FindLineEntryIndexByFileIndexImpl(uint32_t start_idx,T file_idx,const SourceLocationSpec & src_location_spec,LineEntry * line_entry_ptr,std::function<bool (T,uint16_t)> file_idx_matcher)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(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_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_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(best_match, *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