1 //===-- LineTable.cpp -------------------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "lldb/Core/Address.h"
11 #include "lldb/Core/Section.h"
12 #include "lldb/Core/Stream.h"
13 #include "lldb/Symbol/CompileUnit.h"
14 #include "lldb/Symbol/LineTable.h"
15 #include <algorithm>
16 
17 using namespace lldb;
18 using namespace lldb_private;
19 
20 //----------------------------------------------------------------------
21 // LineTable constructor
22 //----------------------------------------------------------------------
23 LineTable::LineTable(CompileUnit* comp_unit) :
24     m_comp_unit(comp_unit),
25     m_section_list(),
26     m_entries()
27 {
28 }
29 
30 //----------------------------------------------------------------------
31 // Destructor
32 //----------------------------------------------------------------------
33 LineTable::~LineTable()
34 {
35 }
36 
37 //void
38 //LineTable::AddLineEntry(const LineEntry& entry)
39 //{
40 //  // Do a binary search for the correct entry and insert it
41 //  m_line_entries.insert(std::upper_bound(m_line_entries.begin(), m_line_entries.end(), entry), entry);
42 //}
43 
44 void
45 LineTable::AppendLineEntry
46 (
47     SectionSP& section_sp,
48     lldb::addr_t section_offset,
49     uint32_t line,
50     uint16_t column,
51     uint16_t file_idx,
52     bool is_start_of_statement,
53     bool is_start_of_basic_block,
54     bool is_prologue_end,
55     bool is_epilogue_begin,
56     bool is_terminal_entry
57 )
58 {
59     uint32_t sect_idx = m_section_list.AddUniqueSection (section_sp);
60     // Make sure we don't user more than 256 sections as that is all we have
61     // room for in the LineTable::Entry::m_sect_idx. If this assert fires,
62     // we will need to m_sect_idx have more bits...
63     assert((section_offset & 0xffffffffff000000ull) == 0);
64     Entry entry(sect_idx, section_offset, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry);
65     m_entries.push_back (entry);
66 }
67 
68 
69 void
70 LineTable::InsertLineEntry
71 (
72     SectionSP& section_sp,
73     lldb::addr_t section_offset,
74     uint32_t line,
75     uint16_t column,
76     uint16_t file_idx,
77     bool is_start_of_statement,
78     bool is_start_of_basic_block,
79     bool is_prologue_end,
80     bool is_epilogue_begin,
81     bool is_terminal_entry
82 )
83 {
84     SectionSP line_section_sp(section_sp);
85     const Section *linked_section = line_section_sp->GetLinkedSection();
86     if (linked_section)
87     {
88         section_offset += line_section_sp->GetLinkedOffset();
89         line_section_sp = linked_section->GetSharedPointer();
90         assert(line_section_sp.get());
91     }
92 
93     uint32_t sect_idx = m_section_list.AddUniqueSection (line_section_sp);
94     // Make sure we don't user more than 256 sections as that is all we have
95     // room for in the LineTable::Entry::m_sect_idx. If this assert fires,
96     // we will need to m_sect_idx have more bits...
97     assert((section_offset & 0xffffffffff000000ull) == 0);
98     Entry entry(sect_idx, section_offset, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry);
99 
100     entry_collection::iterator begin_pos = m_entries.begin();
101     entry_collection::iterator end_pos = m_entries.end();
102     LineTable::Entry::LessThanBinaryPredicate less_than_bp(this);
103     entry_collection::iterator pos = upper_bound(begin_pos, end_pos, entry, less_than_bp);
104 
105 //  Stream s(stdout);
106 //  s << "\n\nBefore:\n";
107 //  Dump (&s, Address::DumpStyleFileAddress);
108     m_entries.insert(pos, entry);
109 //  s << "After:\n";
110 //  Dump (&s, Address::DumpStyleFileAddress);
111 }
112 
113 //----------------------------------------------------------------------
114 LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(LineTable *line_table) :
115     m_line_table (line_table)
116 {
117 }
118 
119 bool
120 LineTable::Entry::LessThanBinaryPredicate::operator() (const LineTable::Entry& a, const LineTable::Entry& b) const
121 {
122     if (a.sect_idx == b.sect_idx)
123     {
124         #define LT_COMPARE(a,b) if (a != b) return a < b
125         LT_COMPARE (a.sect_offset, b.sect_offset);
126         LT_COMPARE (a.line, b.line);
127         LT_COMPARE (a.column, b.column);
128         LT_COMPARE (a.is_start_of_statement, b.is_start_of_statement);
129         LT_COMPARE (a.is_start_of_basic_block, b.is_start_of_basic_block);
130         // b and a reversed on purpose below.
131         LT_COMPARE (b.is_prologue_end, a.is_prologue_end);
132         LT_COMPARE (a.is_epilogue_begin, b.is_epilogue_begin);
133         // b and a reversed on purpose below.
134         LT_COMPARE (b.is_terminal_entry, a.is_terminal_entry);
135         LT_COMPARE (a.file_idx, b.file_idx);
136         return false;
137         #undef LT_COMPARE
138     }
139 
140     const Section *a_section = m_line_table->GetSectionForEntryIndex (a.sect_idx);
141     const Section *b_section = m_line_table->GetSectionForEntryIndex (b.sect_idx);
142     return Section::Compare(*a_section, *b_section) < 0;
143 }
144 
145 
146 Section *
147 LineTable::GetSectionForEntryIndex (uint32_t idx)
148 {
149     if (idx < m_section_list.GetSize())
150         return m_section_list.GetSectionAtIndex(idx).get();
151     return NULL;
152 }
153 
154 uint32_t
155 LineTable::GetSize() const
156 {
157     return m_entries.size();
158 }
159 
160 bool
161 LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry& line_entry)
162 {
163     if (idx < m_entries.size())
164     {
165         ConvertEntryAtIndexToLineEntry (idx, line_entry);
166         return true;
167     }
168     line_entry.Clear();
169     return false;
170 }
171 
172 bool
173 LineTable::FindLineEntryByAddress (const Address &so_addr, LineEntry& line_entry, uint32_t *index_ptr)
174 {
175     if (index_ptr != NULL )
176         *index_ptr = UINT32_MAX;
177 
178     bool success = false;
179     uint32_t sect_idx = m_section_list.FindSectionIndex (so_addr.GetSection());
180     if (sect_idx != UINT32_MAX)
181     {
182         Entry search_entry;
183         search_entry.sect_idx = sect_idx;
184         search_entry.sect_offset = so_addr.GetOffset();
185 
186         entry_collection::const_iterator begin_pos = m_entries.begin();
187         entry_collection::const_iterator end_pos = m_entries.end();
188         entry_collection::const_iterator pos = lower_bound(begin_pos, end_pos, search_entry, Entry::EntryAddressLessThan);
189         if (pos != end_pos)
190         {
191             if (pos != begin_pos)
192             {
193                 if (pos->sect_offset != search_entry.sect_offset)
194                     --pos;
195                 else if (pos->sect_offset == search_entry.sect_offset)
196                 {
197                     while (pos != begin_pos)
198                     {
199                         entry_collection::const_iterator prev_pos = pos - 1;
200                         if (prev_pos->sect_idx    == search_entry.sect_idx &&
201                             prev_pos->sect_offset == search_entry.sect_offset)
202                             --pos;
203                         else
204                             break;
205                     }
206                 }
207 
208             }
209             uint32_t match_idx = std::distance (begin_pos, pos);
210             success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry);
211             if (index_ptr != NULL && success)
212                 *index_ptr = match_idx;
213         }
214     }
215     return success;
216 }
217 
218 
219 bool
220 LineTable::ConvertEntryAtIndexToLineEntry (uint32_t idx, LineEntry &line_entry)
221 {
222     if (idx < m_entries.size())
223     {
224         const Entry& entry = m_entries[idx];
225         line_entry.range.GetBaseAddress().SetSection(m_section_list.GetSectionAtIndex (entry.sect_idx).get());
226         line_entry.range.GetBaseAddress().SetOffset(entry.sect_offset);
227         if (!entry.is_terminal_entry && idx + 1 < m_entries.size())
228         {
229             const Entry& next_entry = m_entries[idx+1];
230             if (next_entry.sect_idx == entry.sect_idx)
231             {
232                 line_entry.range.SetByteSize(next_entry.sect_offset - entry.sect_offset);
233             }
234             else
235             {
236                 Address next_line_addr(m_section_list.GetSectionAtIndex (next_entry.sect_idx).get(), next_entry.sect_offset);
237                 line_entry.range.SetByteSize(next_line_addr.GetFileAddress() - line_entry.range.GetBaseAddress().GetFileAddress());
238             }
239         }
240         else
241             line_entry.range.SetByteSize(0);
242         line_entry.file = m_comp_unit->GetSupportFiles().GetFileSpecAtIndex (entry.file_idx);
243         line_entry.line = entry.line;
244         line_entry.column = entry.column;
245         line_entry.is_start_of_statement = entry.is_start_of_statement;
246         line_entry.is_start_of_basic_block = entry.is_start_of_basic_block;
247         line_entry.is_prologue_end = entry.is_prologue_end;
248         line_entry.is_epilogue_begin = entry.is_epilogue_begin;
249         line_entry.is_terminal_entry = entry.is_terminal_entry;
250         return true;
251     }
252     return false;
253 }
254 
255 uint32_t
256 LineTable::FindLineEntryIndexByFileIndex (uint32_t start_idx, uint32_t file_idx, uint32_t line, bool exact, LineEntry* line_entry_ptr)
257 {
258     const size_t count = m_entries.size();
259     size_t best_match = UINT_MAX;
260 
261     for (size_t idx = start_idx; idx < count; ++idx)
262     {
263         // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero)
264         if (m_entries[idx].is_terminal_entry)
265             continue;
266 
267         if (m_entries[idx].file_idx != file_idx)
268             continue;
269 
270         // Exact match always wins.  Otherwise try to find the closest line > the desired
271         // line.
272         // FIXME: Maybe want to find the line closest before and the line closest after and
273         // if they're not in the same function, don't return a match.
274 
275         if (m_entries[idx].line < line)
276         {
277             continue;
278         }
279         else if (m_entries[idx].line == line)
280         {
281             if (line_entry_ptr)
282                 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr);
283             return idx;
284         }
285         else if (!exact)
286         {
287             if (best_match == UINT32_MAX)
288                 best_match = idx;
289             else if (m_entries[idx].line < m_entries[best_match].line)
290                 best_match = idx;
291         }
292     }
293 
294     if (best_match != UINT_MAX)
295     {
296         if (line_entry_ptr)
297             ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr);
298         return best_match;
299     }
300     return UINT_MAX;
301 }
302 
303 void
304 LineTable::Dump (Stream *s, Process *process, Address::DumpStyle style, Address::DumpStyle fallback_style, bool show_line_ranges)
305 {
306     const size_t count = m_entries.size();
307     LineEntry line_entry;
308     FileSpec prev_file;
309     for (size_t idx = 0; idx < count; ++idx)
310     {
311         ConvertEntryAtIndexToLineEntry (idx, line_entry);
312         line_entry.Dump (s, process, prev_file != line_entry.file, style, fallback_style, show_line_ranges);
313         s->EOL();
314         prev_file = line_entry.file;
315     }
316 }
317 
318 
319 void
320 LineTable::GetDescription (Stream *s, Process *process, DescriptionLevel level)
321 {
322     const size_t count = m_entries.size();
323     LineEntry line_entry;
324     for (size_t idx = 0; idx < count; ++idx)
325     {
326         ConvertEntryAtIndexToLineEntry (idx, line_entry);
327         line_entry.GetDescription (s, level, m_comp_unit, process, true);
328         s->EOL();
329     }
330 }
331 
332 
333 
334