contrib/llvm/tools/lldb/source/Symbol/LineTable.cpp

   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