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 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 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 { EntryEntry210 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 EntryEntry215 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 ClearEntry229 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 CompareEntry241 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 EntryAddressLessThanEntry274 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 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 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 338 private: 339 LineTable(const LineTable &) = delete; 340 const LineTable &operator=(const LineTable &) = delete; 341 342 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)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(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_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_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(best_match, *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