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