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