lldb/Symbol/LineTable.h

0001 //===-- LineTable.h ---------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLDB_SYMBOL_LINETABLE_H
0010 #define LLDB_SYMBOL_LINETABLE_H
0011
0012 #include "lldb/Core/Address.h"
0013 #include "lldb/Core/ModuleChild.h"
0014 #include "lldb/Core/Section.h"
0015 #include "lldb/Core/SourceLocationSpec.h"
0016 #include "lldb/Symbol/LineEntry.h"
0017 #include "lldb/Utility/RangeMap.h"
0018 #include "lldb/lldb-private.h"
0019 #include <vector>
0020
0021 namespace lldb_private {
0022
0023 /// \class LineSequence LineTable.h "lldb/Symbol/LineTable.h" An abstract base
0024 /// class used during symbol table creation.
0025 class LineSequence {
0026 public:
0027   LineSequence();
0028
0029   virtual ~LineSequence() = default;
0030
0031   virtual void Clear() = 0;
0032
0033 private:
0034   LineSequence(const LineSequence &) = delete;
0035   const LineSequence &operator=(const LineSequence &) = delete;
0036 };
0037
0038 /// \class LineTable LineTable.h "lldb/Symbol/LineTable.h"
0039 /// A line table class.
0040 class LineTable {
0041 public:
0042   /// Construct with compile unit.
0043   ///
0044   /// \param[in] comp_unit
0045   ///     The compile unit to which this line table belongs.
0046   LineTable(CompileUnit *comp_unit);
0047
0048   /// Construct with entries found in \a sequences.
0049   ///
0050   /// \param[in] sequences
0051   ///     Unsorted list of line sequences.
0052   LineTable(CompileUnit *comp_unit,
0053             std::vector<std::unique_ptr<LineSequence>> &&sequences);
0054
0055   /// Destructor.
0056   ~LineTable();
0057
0058   /// Adds a new line entry to this line table.
0059   ///
0060   /// All line entries are maintained in file address order.
0061   ///
0062   /// \param[in] line_entry
0063   ///     A const reference to a new line_entry to add to this line
0064   ///     table.
0065   ///
0066   /// \see Address::DumpStyle
0067   //  void
0068   //  AddLineEntry (const LineEntry& line_entry);
0069
0070   // Called when you can't guarantee the addresses are in increasing order
0071   void InsertLineEntry(lldb::addr_t file_addr, uint32_t line, uint16_t column,
0072                        uint16_t file_idx, bool is_start_of_statement,
0073                        bool is_start_of_basic_block, bool is_prologue_end,
0074                        bool is_epilogue_begin, bool is_terminal_entry);
0075
0076   // Used to instantiate the LineSequence helper class
0077   static std::unique_ptr<LineSequence> CreateLineSequenceContainer();
0078
0079   // Append an entry to a caller-provided collection that will later be
0080   // inserted in this line table.
0081   static void AppendLineEntryToSequence(LineSequence *sequence, lldb::addr_t file_addr,
0082                                  uint32_t line, uint16_t column,
0083                                  uint16_t file_idx, bool is_start_of_statement,
0084                                  bool is_start_of_basic_block,
0085                                  bool is_prologue_end, bool is_epilogue_begin,
0086                                  bool is_terminal_entry);
0087
0088   // Insert a sequence of entries into this line table.
0089   void InsertSequence(LineSequence *sequence);
0090
0091   /// Dump all line entries in this line table to the stream \a s.
0092   ///
0093   /// \param[in] s
0094   ///     The stream to which to dump the object description.
0095   ///
0096   /// \param[in] style
0097   ///     The display style for the address.
0098   ///
0099   /// \see Address::DumpStyle
0100   void Dump(Stream *s, Target *target, Address::DumpStyle style,
0101             Address::DumpStyle fallback_style, bool show_line_ranges);
0102
0103   void GetDescription(Stream *s, Target *target, lldb::DescriptionLevel level);
0104
0105   /// Find a line entry that contains the section offset address \a so_addr.
0106   ///
0107   /// \param[in] so_addr
0108   ///     A section offset address object containing the address we
0109   ///     are searching for.
0110   ///
0111   /// \param[out] line_entry
0112   ///     A copy of the line entry that was found if \b true is
0113   ///     returned, otherwise \a entry is left unmodified.
0114   ///
0115   /// \param[out] index_ptr
0116   ///     A pointer to a 32 bit integer that will get the actual line
0117   ///     entry index if it is not nullptr.
0118   ///
0119   /// \return
0120   ///     Returns \b true if \a so_addr is contained in a line entry
0121   ///     in this line table, \b false otherwise.
0122   bool FindLineEntryByAddress(const Address &so_addr, LineEntry &line_entry,
0123                               uint32_t *index_ptr = nullptr);
0124
0125   /// Find a line entry index that has a matching file index and source line
0126   /// number.
0127   ///
0128   /// Finds the next line entry that has a matching \a file_idx and source
0129   /// line number \a line starting at the \a start_idx entries into the line
0130   /// entry collection.
0131   ///
0132   /// \param[in] start_idx
0133   ///     The number of entries to skip when starting the search.
0134   ///
0135   /// \param[out] file_idx
0136   ///     The file index to search for that should be found prior
0137   ///     to calling this function using the following functions:
0138   ///     CompileUnit::GetSupportFiles()
0139   ///     FileSpecList::FindFileIndex (uint32_t, const FileSpec &) const
0140   ///
0141   /// \param[in] src_location_spec
0142   ///     The source location specifier to match.
0143   ///
0144   /// \param[out] line_entry_ptr
0145   ///     A pointer to a line entry object that will get a copy of
0146   ///     the line entry if \b true is returned, otherwise \a
0147   ///     line_entry is left untouched.
0148   ///
0149   /// \return
0150   ///     Returns \b true if a matching line entry is found in this
0151   ///     line table, \b false otherwise.
0152   ///
0153   /// \see CompileUnit::GetSupportFiles()
0154   /// \see FileSpecList::FindFileIndex (uint32_t, const FileSpec &) const
0155   uint32_t
0156   FindLineEntryIndexByFileIndex(uint32_t start_idx, uint32_t file_idx,
0157                                 const SourceLocationSpec &src_location_spec,
0158                                 LineEntry *line_entry_ptr);
0159
0160   uint32_t FindLineEntryIndexByFileIndex(
0161       uint32_t start_idx, const std::vector<uint32_t> &file_idx,
0162       const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr);
0163
0164   size_t FindLineEntriesForFileIndex(uint32_t file_idx, bool append,
0165                                      SymbolContextList &sc_list);
0166
0167   /// Get the line entry from the line table at index \a idx.
0168   ///
0169   /// \param[in] idx
0170   ///     An index into the line table entry collection.
0171   ///
0172   /// \return
0173   ///     A valid line entry if \a idx is a valid index, or an invalid
0174   ///     line entry if \a idx is not valid.
0175   ///
0176   /// \see LineTable::GetSize()
0177   /// \see LineEntry::IsValid() const
0178   bool GetLineEntryAtIndex(uint32_t idx, LineEntry &line_entry);
0179
0180   /// Gets the size of the line table in number of line table entries.
0181   ///
0182   /// \return
0183   ///     The number of line table entries in this line table.
0184   uint32_t GetSize() const;
0185
0186   typedef lldb_private::RangeVector<lldb::addr_t, lldb::addr_t, 32>
0187       FileAddressRanges;
0188
0189   /// Gets all contiguous file address ranges for the entire line table.
0190   ///
0191   /// \param[out] file_ranges
0192   ///     A collection of file address ranges that will be filled in
0193   ///     by this function.
0194   ///
0195   /// \param[out] append
0196   ///     If \b true, then append to \a file_ranges, otherwise clear
0197   ///     \a file_ranges prior to adding any ranges.
0198   ///
0199   /// \return
0200   ///     The number of address ranges added to \a file_ranges
0201   size_t GetContiguousFileAddressRanges(FileAddressRanges &file_ranges,
0202                                         bool append);
0203
0204   typedef RangeDataVector<lldb::addr_t, lldb::addr_t, lldb::addr_t>
0205       FileRangeMap;
0206
0207   LineTable *LinkLineTable(const FileRangeMap &file_range_map);
0208
0209   struct Entry {
0210     Entry()
0211         : line(0), is_start_of_statement(false), is_start_of_basic_block(false),
0212           is_prologue_end(false), is_epilogue_begin(false),
0213           is_terminal_entry(false) {}
0214
0215     Entry(lldb::addr_t _file_addr, uint32_t _line, uint16_t _column,
0216           uint16_t _file_idx, bool _is_start_of_statement,
0217           bool _is_start_of_basic_block, bool _is_prologue_end,
0218           bool _is_epilogue_begin, bool _is_terminal_entry)
0219         : file_addr(_file_addr), line(_line),
0220           is_start_of_statement(_is_start_of_statement),
0221           is_start_of_basic_block(_is_start_of_basic_block),
0222           is_prologue_end(_is_prologue_end),
0223           is_epilogue_begin(_is_epilogue_begin),
0224           is_terminal_entry(_is_terminal_entry), column(_column),
0225           file_idx(_file_idx) {}
0226
0227     int bsearch_compare(const void *key, const void *arrmem);
0228
0229     void Clear() {
0230       file_addr = LLDB_INVALID_ADDRESS;
0231       line = 0;
0232       column = 0;
0233       file_idx = 0;
0234       is_start_of_statement = false;
0235       is_start_of_basic_block = false;
0236       is_prologue_end = false;
0237       is_epilogue_begin = false;
0238       is_terminal_entry = false;
0239     }
0240
0241     static int Compare(const Entry &lhs, const Entry &rhs) {
0242 // Compare the sections before calling
0243 #define SCALAR_COMPARE(a, b)                                                   \
0244   if (a < b)                                                                   \
0245     return -1;                                                                 \
0246   if (a > b)                                                                   \
0247   return +1
0248       SCALAR_COMPARE(lhs.file_addr, rhs.file_addr);
0249       SCALAR_COMPARE(lhs.line, rhs.line);
0250       SCALAR_COMPARE(lhs.column, rhs.column);
0251       SCALAR_COMPARE(lhs.is_start_of_statement, rhs.is_start_of_statement);
0252       SCALAR_COMPARE(lhs.is_start_of_basic_block, rhs.is_start_of_basic_block);
0253       // rhs and lhs reversed on purpose below.
0254       SCALAR_COMPARE(rhs.is_prologue_end, lhs.is_prologue_end);
0255       SCALAR_COMPARE(lhs.is_epilogue_begin, rhs.is_epilogue_begin);
0256       // rhs and lhs reversed on purpose below.
0257       SCALAR_COMPARE(rhs.is_terminal_entry, lhs.is_terminal_entry);
0258       SCALAR_COMPARE(lhs.file_idx, rhs.file_idx);
0259 #undef SCALAR_COMPARE
0260       return 0;
0261     }
0262
0263     class LessThanBinaryPredicate {
0264     public:
0265       LessThanBinaryPredicate(LineTable *line_table);
0266       bool operator()(const LineTable::Entry &, const LineTable::Entry &) const;
0267       bool operator()(const std::unique_ptr<LineSequence> &,
0268                       const std::unique_ptr<LineSequence> &) const;
0269
0270     protected:
0271       LineTable *m_line_table;
0272     };
0273
0274     static bool EntryAddressLessThan(const Entry &lhs, const Entry &rhs) {
0275       return lhs.file_addr < rhs.file_addr;
0276     }
0277
0278     // Member variables.
0279     /// The file address for this line entry.
0280     lldb::addr_t file_addr = LLDB_INVALID_ADDRESS;
0281     /// The source line number, or zero if there is no line number
0282     /// information.
0283     uint32_t line : 27;
0284     /// Indicates this entry is the beginning of a statement.
0285     uint32_t is_start_of_statement : 1;
0286     /// Indicates this entry is the beginning of a basic block.
0287     uint32_t is_start_of_basic_block : 1;
0288     /// Indicates this entry is one (of possibly many) where execution
0289     /// should be suspended for an entry breakpoint of a function.
0290     uint32_t is_prologue_end : 1;
0291     /// Indicates this entry is one (of possibly many) where execution
0292     /// should be suspended for an exit breakpoint of a function.
0293     uint32_t is_epilogue_begin : 1;
0294     /// Indicates this entry is that of the first byte after the end
0295     /// of a sequence of target machine instructions.
0296     uint32_t is_terminal_entry : 1;
0297     /// The column number of the source line, or zero if there is no
0298     /// column information.
0299     uint16_t column = 0;
0300     /// The file index into CompileUnit's file table, or zero if there
0301     /// is no file information.
0302     uint16_t file_idx = 0;
0303   };
0304
0305 protected:
0306   struct EntrySearchInfo {
0307     LineTable *line_table;
0308     lldb_private::Section *a_section;
0309     Entry *a_entry;
0310   };
0311
0312   // Types
0313   typedef std::vector<lldb_private::Section *>
0314       section_collection; ///< The collection type for the sections.
0315   typedef std::vector<Entry>
0316       entry_collection; ///< The collection type for the line entries.
0317   // Member variables.
0318   CompileUnit
0319       *m_comp_unit; ///< The compile unit that this line table belongs to.
0320   entry_collection
0321       m_entries; ///< The collection of line entries in this line table.
0322
0323   // Helper class
0324   class LineSequenceImpl : public LineSequence {
0325   public:
0326     LineSequenceImpl() = default;
0327
0328     ~LineSequenceImpl() override = default;
0329
0330     void Clear() override;
0331
0332     entry_collection
0333         m_entries; ///< The collection of line entries in this sequence.
0334   };
0335
0336   bool ConvertEntryAtIndexToLineEntry(uint32_t idx, LineEntry &line_entry);
0337
0338 private:
0339   LineTable(const LineTable &) = delete;
0340   const LineTable &operator=(const LineTable &) = delete;
0341
0342   template <typename T>
0343   uint32_t FindLineEntryIndexByFileIndexImpl(
0344       uint32_t start_idx, T file_idx,
0345       const SourceLocationSpec &src_location_spec, LineEntry *line_entry_ptr,
0346       std::function<bool(T, uint16_t)> file_idx_matcher) {
0347     const size_t count = m_entries.size();
0348     size_t best_match = UINT32_MAX;
0349
0350     if (!line_entry_ptr)
0351       return best_match;
0352
0353     const uint32_t line = src_location_spec.GetLine().value_or(0);
0354     const uint16_t column =
0355         src_location_spec.GetColumn().value_or(LLDB_INVALID_COLUMN_NUMBER);
0356     const bool exact_match = src_location_spec.GetExactMatch();
0357
0358     for (size_t idx = start_idx; idx < count; ++idx) {
0359       // Skip line table rows that terminate the previous row (is_terminal_entry
0360       // is non-zero)
0361       if (m_entries[idx].is_terminal_entry)
0362         continue;
0363
0364       if (!file_idx_matcher(file_idx, m_entries[idx].file_idx))
0365         continue;
0366
0367       // Exact match always wins.  Otherwise try to find the closest line > the
0368       // desired line.
0369       // FIXME: Maybe want to find the line closest before and the line closest
0370       // after and if they're not in the same function, don't return a match.
0371
0372       if (column == LLDB_INVALID_COLUMN_NUMBER) {
0373         if (m_entries[idx].line < line) {
0374           continue;
0375         } else if (m_entries[idx].line == line) {
0376           ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
0377           return idx;
0378         } else if (!exact_match) {
0379           if (best_match == UINT32_MAX ||
0380               m_entries[idx].line < m_entries[best_match].line)
0381             best_match = idx;
0382         }
0383       } else {
0384         if (m_entries[idx].line < line) {
0385           continue;
0386         } else if (m_entries[idx].line == line &&
0387                    m_entries[idx].column == column) {
0388           ConvertEntryAtIndexToLineEntry(idx, *line_entry_ptr);
0389           return idx;
0390         } else if (!exact_match) {
0391           if (best_match == UINT32_MAX)
0392             best_match = idx;
0393           else if (m_entries[idx].line < m_entries[best_match].line)
0394             best_match = idx;
0395           else if (m_entries[idx].line == m_entries[best_match].line)
0396             if (m_entries[idx].column &&
0397                 m_entries[idx].column < m_entries[best_match].column)
0398               best_match = idx;
0399         }
0400       }
0401     }
0402
0403     if (best_match != UINT32_MAX) {
0404       if (line_entry_ptr)
0405         ConvertEntryAtIndexToLineEntry(best_match, *line_entry_ptr);
0406       return best_match;
0407     }
0408     return UINT32_MAX;
0409   }
0410 };
0411
0412 } // namespace lldb_private
0413
0414 #endif // LLDB_SYMBOL_LINETABLE_H