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 LT_COMPARE (a.line, b.line); 123 LT_COMPARE (a.column, b.column); 124 LT_COMPARE (a.is_start_of_statement, b.is_start_of_statement); 125 LT_COMPARE (a.is_start_of_basic_block, b.is_start_of_basic_block); 126 // b and a reversed on purpose below. 127 LT_COMPARE (b.is_prologue_end, a.is_prologue_end); 128 LT_COMPARE (a.is_epilogue_begin, b.is_epilogue_begin); 129 // b and a reversed on purpose below. 130 LT_COMPARE (b.is_terminal_entry, a.is_terminal_entry); 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 if (pos != end_pos) 231 { 232 uint32_t match_idx = std::distance (begin_pos, pos); 233 success = ConvertEntryAtIndexToLineEntry(match_idx, line_entry); 234 if (index_ptr != NULL && success) 235 *index_ptr = match_idx; 236 } 237 } 238 } 239 return success; 240 } 241 242 243 bool 244 LineTable::ConvertEntryAtIndexToLineEntry (uint32_t idx, LineEntry &line_entry) 245 { 246 if (idx < m_entries.size()) 247 { 248 const Entry& entry = m_entries[idx]; 249 line_entry.range.GetBaseAddress().SetSection(m_section_list.GetSectionAtIndex (entry.sect_idx)); 250 line_entry.range.GetBaseAddress().SetOffset(entry.sect_offset); 251 if (!entry.is_terminal_entry && idx + 1 < m_entries.size()) 252 { 253 const Entry& next_entry = m_entries[idx+1]; 254 if (next_entry.sect_idx == entry.sect_idx) 255 { 256 line_entry.range.SetByteSize(next_entry.sect_offset - entry.sect_offset); 257 } 258 else 259 { 260 Address next_line_addr(m_section_list.GetSectionAtIndex (next_entry.sect_idx), next_entry.sect_offset); 261 line_entry.range.SetByteSize(next_line_addr.GetFileAddress() - line_entry.range.GetBaseAddress().GetFileAddress()); 262 } 263 } 264 else 265 line_entry.range.SetByteSize(0); 266 line_entry.file = m_comp_unit->GetSupportFiles().GetFileSpecAtIndex (entry.file_idx); 267 line_entry.line = entry.line; 268 line_entry.column = entry.column; 269 line_entry.is_start_of_statement = entry.is_start_of_statement; 270 line_entry.is_start_of_basic_block = entry.is_start_of_basic_block; 271 line_entry.is_prologue_end = entry.is_prologue_end; 272 line_entry.is_epilogue_begin = entry.is_epilogue_begin; 273 line_entry.is_terminal_entry = entry.is_terminal_entry; 274 return true; 275 } 276 return false; 277 } 278 279 uint32_t 280 LineTable::FindLineEntryIndexByFileIndex 281 ( 282 uint32_t start_idx, 283 const std::vector<uint32_t> &file_indexes, 284 uint32_t line, 285 bool exact, 286 LineEntry* line_entry_ptr 287 ) 288 { 289 290 const size_t count = m_entries.size(); 291 std::vector<uint32_t>::const_iterator begin_pos = file_indexes.begin(); 292 std::vector<uint32_t>::const_iterator end_pos = file_indexes.end(); 293 size_t best_match = UINT32_MAX; 294 295 for (size_t idx = start_idx; idx < count; ++idx) 296 { 297 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 298 if (m_entries[idx].is_terminal_entry) 299 continue; 300 301 if (find (begin_pos, end_pos, m_entries[idx].file_idx) == end_pos) 302 continue; 303 304 // Exact match always wins. Otherwise try to find the closest line > the desired 305 // line. 306 // FIXME: Maybe want to find the line closest before and the line closest after and 307 // if they're not in the same function, don't return a match. 308 309 if (m_entries[idx].line < line) 310 { 311 continue; 312 } 313 else if (m_entries[idx].line == line) 314 { 315 if (line_entry_ptr) 316 ConvertEntryAtIndexToLineEntry (idx, *line_entry_ptr); 317 return idx; 318 } 319 else if (!exact) 320 { 321 if (best_match == UINT32_MAX) 322 best_match = idx; 323 else if (m_entries[idx].line < m_entries[best_match].line) 324 best_match = idx; 325 } 326 } 327 328 if (best_match != UINT32_MAX) 329 { 330 if (line_entry_ptr) 331 ConvertEntryAtIndexToLineEntry (best_match, *line_entry_ptr); 332 return best_match; 333 } 334 return UINT32_MAX; 335 } 336 337 uint32_t 338 LineTable::FindLineEntryIndexByFileIndex (uint32_t start_idx, uint32_t file_idx, uint32_t line, bool exact, LineEntry* line_entry_ptr) 339 { 340 const size_t count = m_entries.size(); 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 (m_entries[idx].file_idx != file_idx) 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 size_t 386 LineTable::FineLineEntriesForFileIndex (uint32_t file_idx, 387 bool append, 388 SymbolContextList &sc_list) 389 { 390 391 if (!append) 392 sc_list.Clear(); 393 394 size_t num_added = 0; 395 const size_t count = m_entries.size(); 396 if (count > 0) 397 { 398 SymbolContext sc (m_comp_unit); 399 400 for (size_t idx = 0; idx < count; ++idx) 401 { 402 // Skip line table rows that terminate the previous row (is_terminal_entry is non-zero) 403 if (m_entries[idx].is_terminal_entry) 404 continue; 405 406 if (m_entries[idx].file_idx == file_idx) 407 { 408 if (ConvertEntryAtIndexToLineEntry (idx, sc.line_entry)) 409 { 410 ++num_added; 411 sc_list.Append(sc); 412 } 413 } 414 } 415 } 416 return num_added; 417 } 418 419 420 void 421 LineTable::Dump (Stream *s, Target *target, Address::DumpStyle style, Address::DumpStyle fallback_style, bool show_line_ranges) 422 { 423 const size_t count = m_entries.size(); 424 LineEntry line_entry; 425 FileSpec prev_file; 426 for (size_t idx = 0; idx < count; ++idx) 427 { 428 ConvertEntryAtIndexToLineEntry (idx, line_entry); 429 line_entry.Dump (s, target, prev_file != line_entry.file, style, fallback_style, show_line_ranges); 430 s->EOL(); 431 prev_file = line_entry.file; 432 } 433 } 434 435 436 void 437 LineTable::GetDescription (Stream *s, Target *target, DescriptionLevel level) 438 { 439 const size_t count = m_entries.size(); 440 LineEntry line_entry; 441 for (size_t idx = 0; idx < count; ++idx) 442 { 443 ConvertEntryAtIndexToLineEntry (idx, line_entry); 444 line_entry.GetDescription (s, level, m_comp_unit, target, true); 445 s->EOL(); 446 } 447 } 448 449 450 451