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