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 const lldb::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 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); 61 m_entries.push_back (entry); 62 } 63 64 65 void 66 LineTable::InsertLineEntry 67 ( 68 const SectionSP& section_sp, 69 lldb::addr_t section_offset, 70 uint32_t line, 71 uint16_t column, 72 uint16_t file_idx, 73 bool is_start_of_statement, 74 bool is_start_of_basic_block, 75 bool is_prologue_end, 76 bool is_epilogue_begin, 77 bool is_terminal_entry 78 ) 79 { 80 SectionSP line_section_sp; 81 SectionSP linked_section_sp (section_sp->GetLinkedSection()); 82 if (linked_section_sp) 83 { 84 section_offset += section_sp->GetLinkedOffset(); 85 line_section_sp = linked_section_sp; 86 } 87 else 88 { 89 line_section_sp = section_sp; 90 } 91 assert(line_section_sp.get()); 92 93 uint32_t sect_idx = m_section_list.AddUniqueSection (line_section_sp); 94 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); 95 96 entry_collection::iterator begin_pos = m_entries.begin(); 97 entry_collection::iterator end_pos = m_entries.end(); 98 LineTable::Entry::LessThanBinaryPredicate less_than_bp(this); 99 entry_collection::iterator pos = upper_bound(begin_pos, end_pos, entry, less_than_bp); 100 101 // Stream s(stdout); 102 // s << "\n\nBefore:\n"; 103 // Dump (&s, Address::DumpStyleFileAddress); 104 m_entries.insert(pos, entry); 105 // s << "After:\n"; 106 // Dump (&s, Address::DumpStyleFileAddress); 107 } 108 109 //---------------------------------------------------------------------- 110 LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(LineTable *line_table) : 111 m_line_table (line_table) 112 { 113 } 114 115 bool 116 LineTable::Entry::LessThanBinaryPredicate::operator() (const LineTable::Entry& a, const LineTable::Entry& b) const 117 { 118 if (a.sect_idx == b.sect_idx) 119 { 120 #define LT_COMPARE(a,b) if (a != b) return a < b 121 LT_COMPARE (a.sect_offset, b.sect_offset); 122 // b and a reversed on purpose below. 123 LT_COMPARE (b.is_terminal_entry, a.is_terminal_entry); 124 LT_COMPARE (a.line, b.line); 125 LT_COMPARE (a.column, b.column); 126 LT_COMPARE (a.is_start_of_statement, b.is_start_of_statement); 127 LT_COMPARE (a.is_start_of_basic_block, b.is_start_of_basic_block); 128 // b and a reversed on purpose below. 129 LT_COMPARE (b.is_prologue_end, a.is_prologue_end); 130 LT_COMPARE (a.is_epilogue_begin, b.is_epilogue_begin); 131 LT_COMPARE (a.file_idx, b.file_idx); 132 return false; 133 #undef LT_COMPARE 134 } 135 136 const Section *a_section = m_line_table->GetSectionForEntryIndex (a.sect_idx); 137 const Section *b_section = m_line_table->GetSectionForEntryIndex (b.sect_idx); 138 return Section::Compare(*a_section, *b_section) < 0; 139 } 140 141 142 Section * 143 LineTable::GetSectionForEntryIndex (uint32_t idx) 144 { 145 if (idx < m_section_list.GetSize()) 146 return m_section_list.GetSectionAtIndex(idx).get(); 147 return NULL; 148 } 149 150 uint32_t 151 LineTable::GetSize() const 152 { 153 return m_entries.size(); 154 } 155 156 bool 157 LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry& line_entry) 158 { 159 if (idx < m_entries.size()) 160 { 161 ConvertEntryAtIndexToLineEntry (idx, line_entry); 162 return true; 163 } 164 line_entry.Clear(); 165 return false; 166 } 167 168 bool 169 LineTable::FindLineEntryByAddress (const Address &so_addr, LineEntry& line_entry, uint32_t *index_ptr) 170 { 171 if (index_ptr != NULL ) 172 *index_ptr = UINT32_MAX; 173 174 bool success = false; 175 uint32_t sect_idx = m_section_list.FindSectionIndex (so_addr.GetSection().get()); 176 if (sect_idx != UINT32_MAX) 177 { 178 Entry search_entry; 179 search_entry.sect_idx = sect_idx; 180 search_entry.sect_offset = so_addr.GetOffset(); 181 182 entry_collection::const_iterator begin_pos = m_entries.begin(); 183 entry_collection::const_iterator end_pos = m_entries.end(); 184 entry_collection::const_iterator pos = lower_bound(begin_pos, end_pos, search_entry, Entry::EntryAddressLessThan); 185 if (pos != end_pos) 186 { 187 if (pos != begin_pos) 188 { 189 if (pos->sect_offset != search_entry.sect_offset) 190 --pos; 191 else if (pos->sect_offset == search_entry.sect_offset) 192 { 193 // If this is a termination entry, it should't match since 194 // entries with the "is_terminal_entry" member set to true 195 // are termination entries that define the range for the 196 // previous entry. 197 if (pos->is_terminal_entry) 198 { 199 // The matching entry is a terminal entry, so we skip 200 // ahead to the next entry to see if there is another 201 // entry following this one whose section/offset matches. 202 ++pos; 203 if (pos != end_pos) 204 { 205 if (pos->sect_offset != search_entry.sect_offset) 206 pos = end_pos; 207 } 208 } 209 210 if (pos != end_pos) 211 { 212 // While in the same section/offset backup to find the first 213 // line entry that matches the address in case there are 214 // multiple 215 while (pos != begin_pos) 216 { 217 entry_collection::const_iterator prev_pos = pos - 1; 218 if (prev_pos->sect_idx == search_entry.sect_idx && 219 prev_pos->sect_offset == search_entry.sect_offset && 220 prev_pos->is_terminal_entry == false) 221 --pos; 222 else 223 break; 224 } 225 } 226 } 227 228 } 229 230 // Make sure we have a valid match and that the match isn't a terminating 231 // entry for a previous line... 232 if (pos != end_pos && pos->is_terminal_entry == false) 233 { 234 uint32_t match_idx = std::distance (begin_pos, pos); 235 success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry); 236 if (index_ptr != NULL && success) 237 *index_ptr = match_idx; 238 } 239 } 240 } 241 return success; 242 } 243 244 245 bool 246 LineTable::ConvertEntryAtIndexToLineEntry (uint32_t idx, LineEntry &line_entry) 247 { 248 if (idx < m_entries.size()) 249 { 250 const Entry& entry = m_entries[idx]; 251 line_entry.range.GetBaseAddress().SetSection(m_section_list.GetSectionAtIndex (entry.sect_idx)); 252 line_entry.range.GetBaseAddress().SetOffset(entry.sect_offset); 253 if (!entry.is_terminal_entry && idx + 1 < m_entries.size()) 254 { 255 const Entry& next_entry = m_entries[idx+1]; 256 if (next_entry.sect_idx == entry.sect_idx) 257 { 258 line_entry.range.SetByteSize(next_entry.sect_offset - entry.sect_offset); 259 } 260 else 261 { 262 Address next_line_addr(m_section_list.GetSectionAtIndex (next_entry.sect_idx), next_entry.sect_offset); 263 line_entry.range.SetByteSize(next_line_addr.GetFileAddress() - line_entry.range.GetBaseAddress().GetFileAddress()); 264 } 265 } 266 else 267 line_entry.range.SetByteSize(0); 268 line_entry.file = m_comp_unit->GetSupportFiles().GetFileSpecAtIndex (entry.file_idx); 269 line_entry.line = entry.line; 270 line_entry.column = entry.column; 271 line_entry.is_start_of_statement = entry.is_start_of_statement; 272 line_entry.is_start_of_basic_block = entry.is_start_of_basic_block; 273 line_entry.is_prologue_end = entry.is_prologue_end; 274 line_entry.is_epilogue_begin = entry.is_epilogue_begin; 275 line_entry.is_terminal_entry = entry.is_terminal_entry; 276 return true; 277 } 278 return false; 279 } 280 281 uint32_t 282 LineTable::FindLineEntryIndexByFileIndex 283 ( 284 uint32_t start_idx, 285 const std::vector<uint32_t> &file_indexes, 286 uint32_t line, 287 bool exact, 288 LineEntry* line_entry_ptr 289 ) 290 { 291 292 const size_t count = m_entries.size(); 293 std::vector<uint32_t>::const_iterator begin_pos = file_indexes.begin(); 294 std::vector<uint32_t>::const_iterator end_pos = file_indexes.end(); 295 size_t best_match = UINT32_MAX; 296 297 for (size_t idx = start_idx; idx < count; ++idx) 298 { 299 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 300 if (m_entries[idx].is_terminal_entry) 301 continue; 302 303 if (find (begin_pos, end_pos, m_entries[idx].file_idx) == end_pos) 304 continue; 305 306 // Exact match always wins. Otherwise try to find the closest line > the desired 307 // line. 308 // FIXME: Maybe want to find the line closest before and the line closest after and 309 // if they're not in the same function, don't return a match. 310 311 if (m_entries[idx].line < line) 312 { 313 continue; 314 } 315 else if (m_entries[idx].line == line) 316 { 317 if (line_entry_ptr) 318 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr); 319 return idx; 320 } 321 else if (!exact) 322 { 323 if (best_match == UINT32_MAX) 324 best_match = idx; 325 else if (m_entries[idx].line < m_entries[best_match].line) 326 best_match = idx; 327 } 328 } 329 330 if (best_match != UINT32_MAX) 331 { 332 if (line_entry_ptr) 333 ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr); 334 return best_match; 335 } 336 return UINT32_MAX; 337 } 338 339 uint32_t 340 LineTable::FindLineEntryIndexByFileIndex (uint32_t start_idx, uint32_t file_idx, uint32_t line, bool exact, LineEntry* line_entry_ptr) 341 { 342 const size_t count = m_entries.size(); 343 size_t best_match = UINT32_MAX; 344 345 for (size_t idx = start_idx; idx < count; ++idx) 346 { 347 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 348 if (m_entries[idx].is_terminal_entry) 349 continue; 350 351 if (m_entries[idx].file_idx != file_idx) 352 continue; 353 354 // Exact match always wins. Otherwise try to find the closest line > the desired 355 // line. 356 // FIXME: Maybe want to find the line closest before and the line closest after and 357 // if they're not in the same function, don't return a match. 358 359 if (m_entries[idx].line < line) 360 { 361 continue; 362 } 363 else if (m_entries[idx].line == line) 364 { 365 if (line_entry_ptr) 366 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr); 367 return idx; 368 } 369 else if (!exact) 370 { 371 if (best_match == UINT32_MAX) 372 best_match = idx; 373 else if (m_entries[idx].line < m_entries[best_match].line) 374 best_match = idx; 375 } 376 } 377 378 if (best_match != UINT32_MAX) 379 { 380 if (line_entry_ptr) 381 ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr); 382 return best_match; 383 } 384 return UINT32_MAX; 385 } 386 387 size_t 388 LineTable::FineLineEntriesForFileIndex (uint32_t file_idx, 389 bool append, 390 SymbolContextList &sc_list) 391 { 392 393 if (!append) 394 sc_list.Clear(); 395 396 size_t num_added = 0; 397 const size_t count = m_entries.size(); 398 if (count > 0) 399 { 400 SymbolContext sc (m_comp_unit); 401 402 for (size_t idx = 0; idx < count; ++idx) 403 { 404 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 405 if (m_entries[idx].is_terminal_entry) 406 continue; 407 408 if (m_entries[idx].file_idx == file_idx) 409 { 410 if (ConvertEntryAtIndexToLineEntry (idx, sc.line_entry)) 411 { 412 ++num_added; 413 sc_list.Append(sc); 414 } 415 } 416 } 417 } 418 return num_added; 419 } 420 421 422 void 423 LineTable::Dump (Stream *s, Target *target, Address::DumpStyle style, Address::DumpStyle fallback_style, bool show_line_ranges) 424 { 425 const size_t count = m_entries.size(); 426 LineEntry line_entry; 427 FileSpec prev_file; 428 for (size_t idx = 0; idx < count; ++idx) 429 { 430 ConvertEntryAtIndexToLineEntry (idx, line_entry); 431 line_entry.Dump (s, target, prev_file != line_entry.file, style, fallback_style, show_line_ranges); 432 s->EOL(); 433 prev_file = line_entry.file; 434 } 435 } 436 437 438 void 439 LineTable::GetDescription (Stream *s, Target *target, DescriptionLevel level) 440 { 441 const size_t count = m_entries.size(); 442 LineEntry line_entry; 443 for (size_t idx = 0; idx < count; ++idx) 444 { 445 ConvertEntryAtIndexToLineEntry (idx, line_entry); 446 line_entry.GetDescription (s, level, m_comp_unit, target, true); 447 s->EOL(); 448 } 449 } 450 451 452 453