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/Module.h" 12 #include "lldb/Core/Section.h" 13 #include "lldb/Core/Stream.h" 14 #include "lldb/Symbol/CompileUnit.h" 15 #include "lldb/Symbol/LineTable.h" 16 #include <algorithm> 17 18 using namespace lldb; 19 using namespace lldb_private; 20 21 //---------------------------------------------------------------------- 22 // LineTable constructor 23 //---------------------------------------------------------------------- 24 LineTable::LineTable(CompileUnit* comp_unit) : 25 m_comp_unit(comp_unit), 26 m_entries() 27 { 28 } 29 30 //---------------------------------------------------------------------- 31 // Destructor 32 //---------------------------------------------------------------------- 33 LineTable::~LineTable() 34 { 35 } 36 37 void 38 LineTable::InsertLineEntry 39 ( 40 lldb::addr_t file_addr, 41 uint32_t line, 42 uint16_t column, 43 uint16_t file_idx, 44 bool is_start_of_statement, 45 bool is_start_of_basic_block, 46 bool is_prologue_end, 47 bool is_epilogue_begin, 48 bool is_terminal_entry 49 ) 50 { 51 Entry entry(file_addr, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry); 52 53 entry_collection::iterator begin_pos = m_entries.begin(); 54 entry_collection::iterator end_pos = m_entries.end(); 55 LineTable::Entry::LessThanBinaryPredicate less_than_bp(this); 56 entry_collection::iterator pos = upper_bound(begin_pos, end_pos, entry, less_than_bp); 57 58 // Stream s(stdout); 59 // s << "\n\nBefore:\n"; 60 // Dump (&s, Address::DumpStyleFileAddress); 61 m_entries.insert(pos, entry); 62 // s << "After:\n"; 63 // Dump (&s, Address::DumpStyleFileAddress); 64 } 65 66 LineSequence::LineSequence() 67 { 68 } 69 70 void 71 LineTable::LineSequenceImpl::Clear() 72 { 73 m_entries.clear(); 74 } 75 76 LineSequence* LineTable::CreateLineSequenceContainer () 77 { 78 return new LineTable::LineSequenceImpl(); 79 } 80 81 void 82 LineTable::AppendLineEntryToSequence 83 ( 84 LineSequence* sequence, 85 lldb::addr_t file_addr, 86 uint32_t line, 87 uint16_t column, 88 uint16_t file_idx, 89 bool is_start_of_statement, 90 bool is_start_of_basic_block, 91 bool is_prologue_end, 92 bool is_epilogue_begin, 93 bool is_terminal_entry 94 ) 95 { 96 assert(sequence != NULL); 97 LineSequenceImpl* seq = reinterpret_cast<LineSequenceImpl*>(sequence); 98 Entry entry(file_addr, line, column, file_idx, is_start_of_statement, is_start_of_basic_block, is_prologue_end, is_epilogue_begin, is_terminal_entry); 99 seq->m_entries.push_back (entry); 100 } 101 102 void 103 LineTable::InsertSequence (LineSequence* sequence) 104 { 105 assert(sequence != NULL); 106 LineSequenceImpl* seq = reinterpret_cast<LineSequenceImpl*>(sequence); 107 if (seq->m_entries.empty()) 108 return; 109 Entry& entry = seq->m_entries.front(); 110 111 // If the first entry address in this sequence is greater than or equal to 112 // the address of the last item in our entry collection, just append. 113 if (m_entries.empty() || !Entry::EntryAddressLessThan(entry, m_entries.back())) 114 { 115 m_entries.insert(m_entries.end(), 116 seq->m_entries.begin(), 117 seq->m_entries.end()); 118 return; 119 } 120 121 // Otherwise, find where this belongs in the collection 122 entry_collection::iterator begin_pos = m_entries.begin(); 123 entry_collection::iterator end_pos = m_entries.end(); 124 LineTable::Entry::LessThanBinaryPredicate less_than_bp(this); 125 entry_collection::iterator pos = upper_bound(begin_pos, end_pos, entry, less_than_bp); 126 #ifdef LLDB_CONFIGURATION_DEBUG 127 // If we aren't inserting at the beginning, the previous entry should 128 // terminate a sequence. 129 if (pos != begin_pos) 130 { 131 entry_collection::iterator prev_pos = pos - 1; 132 assert(prev_pos->is_terminal_entry); 133 } 134 #endif 135 m_entries.insert(pos, seq->m_entries.begin(), seq->m_entries.end()); 136 } 137 138 //---------------------------------------------------------------------- 139 LineTable::Entry::LessThanBinaryPredicate::LessThanBinaryPredicate(LineTable *line_table) : 140 m_line_table (line_table) 141 { 142 } 143 144 bool 145 LineTable::Entry::LessThanBinaryPredicate::operator() (const LineTable::Entry& a, const LineTable::Entry& b) const 146 { 147 #define LT_COMPARE(a,b) if (a != b) return a < b 148 LT_COMPARE (a.file_addr, b.file_addr); 149 // b and a reversed on purpose below. 150 LT_COMPARE (b.is_terminal_entry, a.is_terminal_entry); 151 LT_COMPARE (a.line, b.line); 152 LT_COMPARE (a.column, b.column); 153 LT_COMPARE (a.is_start_of_statement, b.is_start_of_statement); 154 LT_COMPARE (a.is_start_of_basic_block, b.is_start_of_basic_block); 155 // b and a reversed on purpose below. 156 LT_COMPARE (b.is_prologue_end, a.is_prologue_end); 157 LT_COMPARE (a.is_epilogue_begin, b.is_epilogue_begin); 158 LT_COMPARE (a.file_idx, b.file_idx); 159 return false; 160 #undef LT_COMPARE 161 } 162 163 164 165 uint32_t 166 LineTable::GetSize() const 167 { 168 return m_entries.size(); 169 } 170 171 bool 172 LineTable::GetLineEntryAtIndex(uint32_t idx, LineEntry& line_entry) 173 { 174 if (idx < m_entries.size()) 175 { 176 ConvertEntryAtIndexToLineEntry (idx, line_entry); 177 return true; 178 } 179 line_entry.Clear(); 180 return false; 181 } 182 183 bool 184 LineTable::FindLineEntryByAddress (const Address &so_addr, LineEntry& line_entry, uint32_t *index_ptr) 185 { 186 if (index_ptr != NULL ) 187 *index_ptr = UINT32_MAX; 188 189 bool success = false; 190 191 if (so_addr.GetModule().get() == m_comp_unit->GetModule().get()) 192 { 193 Entry search_entry; 194 search_entry.file_addr = so_addr.GetFileAddress(); 195 if (search_entry.file_addr != LLDB_INVALID_ADDRESS) 196 { 197 entry_collection::const_iterator begin_pos = m_entries.begin(); 198 entry_collection::const_iterator end_pos = m_entries.end(); 199 entry_collection::const_iterator pos = lower_bound(begin_pos, end_pos, search_entry, Entry::EntryAddressLessThan); 200 if (pos != end_pos) 201 { 202 if (pos != begin_pos) 203 { 204 if (pos->file_addr != search_entry.file_addr) 205 --pos; 206 else if (pos->file_addr == search_entry.file_addr) 207 { 208 // If this is a termination entry, it should't match since 209 // entries with the "is_terminal_entry" member set to true 210 // are termination entries that define the range for the 211 // previous entry. 212 if (pos->is_terminal_entry) 213 { 214 // The matching entry is a terminal entry, so we skip 215 // ahead to the next entry to see if there is another 216 // entry following this one whose section/offset matches. 217 ++pos; 218 if (pos != end_pos) 219 { 220 if (pos->file_addr != search_entry.file_addr) 221 pos = end_pos; 222 } 223 } 224 225 if (pos != end_pos) 226 { 227 // While in the same section/offset backup to find the first 228 // line entry that matches the address in case there are 229 // multiple 230 while (pos != begin_pos) 231 { 232 entry_collection::const_iterator prev_pos = pos - 1; 233 if (prev_pos->file_addr == search_entry.file_addr && 234 prev_pos->is_terminal_entry == false) 235 --pos; 236 else 237 break; 238 } 239 } 240 } 241 242 } 243 244 // Make sure we have a valid match and that the match isn't a terminating 245 // entry for a previous line... 246 if (pos != end_pos && pos->is_terminal_entry == false) 247 { 248 uint32_t match_idx = std::distance (begin_pos, pos); 249 success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry); 250 if (index_ptr != NULL && success) 251 *index_ptr = match_idx; 252 } 253 } 254 } 255 } 256 return success; 257 } 258 259 260 bool 261 LineTable::ConvertEntryAtIndexToLineEntry (uint32_t idx, LineEntry &line_entry) 262 { 263 if (idx < m_entries.size()) 264 { 265 const Entry& entry = m_entries[idx]; 266 ModuleSP module_sp (m_comp_unit->GetModule()); 267 if (module_sp && module_sp->ResolveFileAddress(entry.file_addr, line_entry.range.GetBaseAddress())) 268 { 269 if (!entry.is_terminal_entry && idx + 1 < m_entries.size()) 270 line_entry.range.SetByteSize(m_entries[idx+1].file_addr - entry.file_addr); 271 else 272 line_entry.range.SetByteSize(0); 273 274 line_entry.file = m_comp_unit->GetSupportFiles().GetFileSpecAtIndex (entry.file_idx); 275 line_entry.line = entry.line; 276 line_entry.column = entry.column; 277 line_entry.is_start_of_statement = entry.is_start_of_statement; 278 line_entry.is_start_of_basic_block = entry.is_start_of_basic_block; 279 line_entry.is_prologue_end = entry.is_prologue_end; 280 line_entry.is_epilogue_begin = entry.is_epilogue_begin; 281 line_entry.is_terminal_entry = entry.is_terminal_entry; 282 return true; 283 } 284 } 285 return false; 286 } 287 288 uint32_t 289 LineTable::FindLineEntryIndexByFileIndex 290 ( 291 uint32_t start_idx, 292 const std::vector<uint32_t> &file_indexes, 293 uint32_t line, 294 bool exact, 295 LineEntry* line_entry_ptr 296 ) 297 { 298 299 const size_t count = m_entries.size(); 300 std::vector<uint32_t>::const_iterator begin_pos = file_indexes.begin(); 301 std::vector<uint32_t>::const_iterator end_pos = file_indexes.end(); 302 size_t best_match = UINT32_MAX; 303 304 for (size_t idx = start_idx; idx < count; ++idx) 305 { 306 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 307 if (m_entries[idx].is_terminal_entry) 308 continue; 309 310 if (find (begin_pos, end_pos, m_entries[idx].file_idx) == end_pos) 311 continue; 312 313 // Exact match always wins. Otherwise try to find the closest line > the desired 314 // line. 315 // FIXME: Maybe want to find the line closest before and the line closest after and 316 // if they're not in the same function, don't return a match. 317 318 if (m_entries[idx].line < line) 319 { 320 continue; 321 } 322 else if (m_entries[idx].line == line) 323 { 324 if (line_entry_ptr) 325 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr); 326 return idx; 327 } 328 else if (!exact) 329 { 330 if (best_match == UINT32_MAX) 331 best_match = idx; 332 else if (m_entries[idx].line < m_entries[best_match].line) 333 best_match = idx; 334 } 335 } 336 337 if (best_match != UINT32_MAX) 338 { 339 if (line_entry_ptr) 340 ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr); 341 return best_match; 342 } 343 return UINT32_MAX; 344 } 345 346 uint32_t 347 LineTable::FindLineEntryIndexByFileIndex (uint32_t start_idx, uint32_t file_idx, uint32_t line, bool exact, LineEntry* line_entry_ptr) 348 { 349 const size_t count = m_entries.size(); 350 size_t best_match = UINT32_MAX; 351 352 for (size_t idx = start_idx; idx < count; ++idx) 353 { 354 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 355 if (m_entries[idx].is_terminal_entry) 356 continue; 357 358 if (m_entries[idx].file_idx != file_idx) 359 continue; 360 361 // Exact match always wins. Otherwise try to find the closest line > the desired 362 // line. 363 // FIXME: Maybe want to find the line closest before and the line closest after and 364 // if they're not in the same function, don't return a match. 365 366 if (m_entries[idx].line < line) 367 { 368 continue; 369 } 370 else if (m_entries[idx].line == line) 371 { 372 if (line_entry_ptr) 373 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr); 374 return idx; 375 } 376 else if (!exact) 377 { 378 if (best_match == UINT32_MAX) 379 best_match = idx; 380 else if (m_entries[idx].line < m_entries[best_match].line) 381 best_match = idx; 382 } 383 } 384 385 if (best_match != UINT32_MAX) 386 { 387 if (line_entry_ptr) 388 ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr); 389 return best_match; 390 } 391 return UINT32_MAX; 392 } 393 394 size_t 395 LineTable::FineLineEntriesForFileIndex (uint32_t file_idx, 396 bool append, 397 SymbolContextList &sc_list) 398 { 399 400 if (!append) 401 sc_list.Clear(); 402 403 size_t num_added = 0; 404 const size_t count = m_entries.size(); 405 if (count > 0) 406 { 407 SymbolContext sc (m_comp_unit); 408 409 for (size_t idx = 0; idx < count; ++idx) 410 { 411 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 412 if (m_entries[idx].is_terminal_entry) 413 continue; 414 415 if (m_entries[idx].file_idx == file_idx) 416 { 417 if (ConvertEntryAtIndexToLineEntry (idx, sc.line_entry)) 418 { 419 ++num_added; 420 sc_list.Append(sc); 421 } 422 } 423 } 424 } 425 return num_added; 426 } 427 428 429 void 430 LineTable::Dump (Stream *s, Target *target, Address::DumpStyle style, Address::DumpStyle fallback_style, bool show_line_ranges) 431 { 432 const size_t count = m_entries.size(); 433 LineEntry line_entry; 434 FileSpec prev_file; 435 for (size_t idx = 0; idx < count; ++idx) 436 { 437 ConvertEntryAtIndexToLineEntry (idx, line_entry); 438 line_entry.Dump (s, target, prev_file != line_entry.file, style, fallback_style, show_line_ranges); 439 s->EOL(); 440 prev_file = line_entry.file; 441 } 442 } 443 444 445 void 446 LineTable::GetDescription (Stream *s, Target *target, DescriptionLevel level) 447 { 448 const size_t count = m_entries.size(); 449 LineEntry line_entry; 450 for (size_t idx = 0; idx < count; ++idx) 451 { 452 ConvertEntryAtIndexToLineEntry (idx, line_entry); 453 line_entry.GetDescription (s, level, m_comp_unit, target, true); 454 s->EOL(); 455 } 456 } 457 458 size_t 459 LineTable::GetContiguousFileAddressRanges (FileAddressRanges &file_ranges, bool append) 460 { 461 if (!append) 462 file_ranges.Clear(); 463 const size_t initial_count = file_ranges.GetSize(); 464 465 const size_t count = m_entries.size(); 466 LineEntry line_entry; 467 FileAddressRanges::Entry range (LLDB_INVALID_ADDRESS, 0); 468 for (size_t idx = 0; idx < count; ++idx) 469 { 470 const Entry& entry = m_entries[idx]; 471 472 if (entry.is_terminal_entry) 473 { 474 if (range.GetRangeBase() != LLDB_INVALID_ADDRESS) 475 { 476 range.SetRangeEnd(entry.file_addr); 477 file_ranges.Append(range); 478 range.Clear(LLDB_INVALID_ADDRESS); 479 } 480 } 481 else if (range.GetRangeBase() == LLDB_INVALID_ADDRESS) 482 { 483 range.SetRangeBase(entry.file_addr); 484 } 485 } 486 return file_ranges.GetSize() - initial_count; 487 } 488 489 LineTable * 490 LineTable::LinkLineTable (const FileRangeMap &file_range_map) 491 { 492 std::unique_ptr<LineTable> line_table_ap (new LineTable (m_comp_unit)); 493 LineSequenceImpl sequence; 494 const size_t count = m_entries.size(); 495 LineEntry line_entry; 496 const FileRangeMap::Entry *file_range_entry = NULL; 497 const FileRangeMap::Entry *prev_file_range_entry = NULL; 498 lldb::addr_t prev_file_addr = LLDB_INVALID_ADDRESS; 499 bool prev_entry_was_linked = false; 500 bool range_changed = false; 501 for (size_t idx = 0; idx < count; ++idx) 502 { 503 const Entry& entry = m_entries[idx]; 504 505 const bool end_sequence = entry.is_terminal_entry; 506 const lldb::addr_t lookup_file_addr = entry.file_addr - (end_sequence ? 1 : 0); 507 if (file_range_entry == NULL || !file_range_entry->Contains(lookup_file_addr)) 508 { 509 prev_file_range_entry = file_range_entry; 510 file_range_entry = file_range_map.FindEntryThatContains(lookup_file_addr); 511 range_changed = true; 512 } 513 514 lldb::addr_t prev_end_entry_linked_file_addr = LLDB_INVALID_ADDRESS; 515 lldb::addr_t entry_linked_file_addr = LLDB_INVALID_ADDRESS; 516 517 bool terminate_previous_entry = false; 518 if (file_range_entry) 519 { 520 entry_linked_file_addr = entry.file_addr - file_range_entry->GetRangeBase() + file_range_entry->data; 521 // Determine if we need to terminate the previous entry when the previous 522 // entry was not contguous with this one after being linked. 523 if (range_changed && prev_file_range_entry) 524 { 525 prev_end_entry_linked_file_addr = std::min<lldb::addr_t>(entry.file_addr, prev_file_range_entry->GetRangeEnd()) - prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data; 526 if (prev_end_entry_linked_file_addr != entry_linked_file_addr) 527 terminate_previous_entry = prev_entry_was_linked; 528 } 529 } 530 else if (prev_entry_was_linked) 531 { 532 // This entry doesn't have a remapping and it needs to be removed. 533 // Watch out in case we need to terminate a previous entry needs to 534 // be terminated now that one line entry in a sequence is not longer valid. 535 if (!entry.is_terminal_entry && 536 !sequence.m_entries.empty() && 537 !sequence.m_entries.back().is_terminal_entry) 538 { 539 terminate_previous_entry = true; 540 } 541 } 542 543 if (terminate_previous_entry && !sequence.m_entries.empty()) 544 { 545 assert (prev_file_addr != LLDB_INVALID_ADDRESS); 546 sequence.m_entries.push_back(sequence.m_entries.back()); 547 if (prev_end_entry_linked_file_addr == LLDB_INVALID_ADDRESS) 548 prev_end_entry_linked_file_addr = std::min<lldb::addr_t>(entry.file_addr,prev_file_range_entry->GetRangeEnd()) - prev_file_range_entry->GetRangeBase() + prev_file_range_entry->data; 549 sequence.m_entries.back().file_addr = prev_end_entry_linked_file_addr; 550 sequence.m_entries.back().is_terminal_entry = true; 551 552 // Append the sequence since we just terminated the previous one 553 line_table_ap->InsertSequence (&sequence); 554 sequence.Clear(); 555 prev_entry_was_linked = false; 556 } 557 558 // Now link the current entry 559 if (file_range_entry) 560 { 561 // This entry has an address remapping and it needs to have its address relinked 562 sequence.m_entries.push_back(entry); 563 sequence.m_entries.back().file_addr = entry_linked_file_addr; 564 } 565 566 // If we have items in the sequence and the last entry is a terminal entry, 567 // insert this sequence into our new line table. 568 if (!sequence.m_entries.empty() && sequence.m_entries.back().is_terminal_entry) 569 { 570 line_table_ap->InsertSequence (&sequence); 571 sequence.Clear(); 572 prev_entry_was_linked = false; 573 } 574 else 575 { 576 prev_entry_was_linked = file_range_entry != NULL; 577 } 578 prev_file_addr = entry.file_addr; 579 range_changed = false; 580 } 581 if (line_table_ap->m_entries.empty()) 582 return NULL; 583 return line_table_ap.release(); 584 } 585 586 587 588 589
