1//===- DWARFDebugLine.cpp -------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
10#include "llvm/ADT/Optional.h"
11#include "llvm/ADT/SmallString.h"
12#include "llvm/ADT/SmallVector.h"
13#include "llvm/ADT/StringRef.h"
14#include "llvm/BinaryFormat/Dwarf.h"
15#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
16#include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
17#include "llvm/Support/Errc.h"
18#include "llvm/Support/Format.h"
19#include "llvm/Support/FormatVariadic.h"
20#include "llvm/Support/WithColor.h"
21#include "llvm/Support/raw_ostream.h"
22#include <algorithm>
23#include <cassert>
24#include <cinttypes>
25#include <cstdint>
26#include <cstdio>
27#include <utility>
28
29using namespace llvm;
30using namespace dwarf;
31
32using FileLineInfoKind = DILineInfoSpecifier::FileLineInfoKind;
33
34namespace {
35
36struct ContentDescriptor {
37  dwarf::LineNumberEntryFormat Type;
38  dwarf::Form Form;
39};
40
41using ContentDescriptors = SmallVector<ContentDescriptor, 4>;
42
43} // end anonymous namespace
44
45static bool versionIsSupported(uint16_t Version) {
46  return Version >= 2 && Version <= 5;
47}
48
49void DWARFDebugLine::ContentTypeTracker::trackContentType(
50    dwarf::LineNumberEntryFormat ContentType) {
51  switch (ContentType) {
52  case dwarf::DW_LNCT_timestamp:
53    HasModTime = true;
54    break;
55  case dwarf::DW_LNCT_size:
56    HasLength = true;
57    break;
58  case dwarf::DW_LNCT_MD5:
59    HasMD5 = true;
60    break;
61  case dwarf::DW_LNCT_LLVM_source:
62    HasSource = true;
63    break;
64  default:
65    // We only care about values we consider optional, and new values may be
66    // added in the vendor extension range, so we do not match exhaustively.
67    break;
68  }
69}
70
71DWARFDebugLine::Prologue::Prologue() { clear(); }
72
73bool DWARFDebugLine::Prologue::hasFileAtIndex(uint64_t FileIndex) const {
74  uint16_t DwarfVersion = getVersion();
75  assert(DwarfVersion != 0 &&
76         "line table prologue has no dwarf version information");
77  if (DwarfVersion >= 5)
78    return FileIndex < FileNames.size();
79  return FileIndex != 0 && FileIndex <= FileNames.size();
80}
81
82const llvm::DWARFDebugLine::FileNameEntry &
83DWARFDebugLine::Prologue::getFileNameEntry(uint64_t Index) const {
84  uint16_t DwarfVersion = getVersion();
85  assert(DwarfVersion != 0 &&
86         "line table prologue has no dwarf version information");
87  // In DWARF v5 the file names are 0-indexed.
88  if (DwarfVersion >= 5)
89    return FileNames[Index];
90  return FileNames[Index - 1];
91}
92
93void DWARFDebugLine::Prologue::clear() {
94  TotalLength = PrologueLength = 0;
95  SegSelectorSize = 0;
96  MinInstLength = MaxOpsPerInst = DefaultIsStmt = LineBase = LineRange = 0;
97  OpcodeBase = 0;
98  FormParams = dwarf::FormParams({0, 0, DWARF32});
99  ContentTypes = ContentTypeTracker();
100  StandardOpcodeLengths.clear();
101  IncludeDirectories.clear();
102  FileNames.clear();
103}
104
105void DWARFDebugLine::Prologue::dump(raw_ostream &OS,
106                                    DIDumpOptions DumpOptions) const {
107  if (!totalLengthIsValid())
108    return;
109  int OffsetDumpWidth = 2 * dwarf::getDwarfOffsetByteSize(FormParams.Format);
110  OS << "Line table prologue:\n"
111     << format("    total_length: 0x%0*" PRIx64 "\n", OffsetDumpWidth,
112               TotalLength)
113     << "          format: " << dwarf::FormatString(FormParams.Format) << "\n"
114     << format("         version: %u\n", getVersion());
115  if (!versionIsSupported(getVersion()))
116    return;
117  if (getVersion() >= 5)
118    OS << format("    address_size: %u\n", getAddressSize())
119       << format(" seg_select_size: %u\n", SegSelectorSize);
120  OS << format(" prologue_length: 0x%0*" PRIx64 "\n", OffsetDumpWidth,
121               PrologueLength)
122     << format(" min_inst_length: %u\n", MinInstLength)
123     << format(getVersion() >= 4 ? "max_ops_per_inst: %u\n" : "", MaxOpsPerInst)
124     << format(" default_is_stmt: %u\n", DefaultIsStmt)
125     << format("       line_base: %i\n", LineBase)
126     << format("      line_range: %u\n", LineRange)
127     << format("     opcode_base: %u\n", OpcodeBase);
128
129  for (uint32_t I = 0; I != StandardOpcodeLengths.size(); ++I)
130    OS << formatv("standard_opcode_lengths[{0}] = {1}\n",
131                  static_cast<dwarf::LineNumberOps>(I + 1),
132                  StandardOpcodeLengths[I]);
133
134  if (!IncludeDirectories.empty()) {
135    // DWARF v5 starts directory indexes at 0.
136    uint32_t DirBase = getVersion() >= 5 ? 0 : 1;
137    for (uint32_t I = 0; I != IncludeDirectories.size(); ++I) {
138      OS << format("include_directories[%3u] = ", I + DirBase);
139      IncludeDirectories[I].dump(OS, DumpOptions);
140      OS << '\n';
141    }
142  }
143
144  if (!FileNames.empty()) {
145    // DWARF v5 starts file indexes at 0.
146    uint32_t FileBase = getVersion() >= 5 ? 0 : 1;
147    for (uint32_t I = 0; I != FileNames.size(); ++I) {
148      const FileNameEntry &FileEntry = FileNames[I];
149      OS <<   format("file_names[%3u]:\n", I + FileBase);
150      OS <<          "           name: ";
151      FileEntry.Name.dump(OS, DumpOptions);
152      OS << '\n'
153         <<   format("      dir_index: %" PRIu64 "\n", FileEntry.DirIdx);
154      if (ContentTypes.HasMD5)
155        OS <<        "   md5_checksum: " << FileEntry.Checksum.digest() << '\n';
156      if (ContentTypes.HasModTime)
157        OS << format("       mod_time: 0x%8.8" PRIx64 "\n", FileEntry.ModTime);
158      if (ContentTypes.HasLength)
159        OS << format("         length: 0x%8.8" PRIx64 "\n", FileEntry.Length);
160      if (ContentTypes.HasSource) {
161        OS <<        "         source: ";
162        FileEntry.Source.dump(OS, DumpOptions);
163        OS << '\n';
164      }
165    }
166  }
167}
168
169// Parse v2-v4 directory and file tables.
170static Error
171parseV2DirFileTables(const DWARFDataExtractor &DebugLineData,
172                     uint64_t *OffsetPtr,
173                     DWARFDebugLine::ContentTypeTracker &ContentTypes,
174                     std::vector<DWARFFormValue> &IncludeDirectories,
175                     std::vector<DWARFDebugLine::FileNameEntry> &FileNames) {
176  while (true) {
177    Error Err = Error::success();
178    StringRef S = DebugLineData.getCStrRef(OffsetPtr, &Err);
179    if (Err) {
180      consumeError(std::move(Err));
181      return createStringError(errc::invalid_argument,
182                               "include directories table was not null "
183                               "terminated before the end of the prologue");
184    }
185    if (S.empty())
186      break;
187    DWARFFormValue Dir =
188        DWARFFormValue::createFromPValue(dwarf::DW_FORM_string, S.data());
189    IncludeDirectories.push_back(Dir);
190  }
191
192  ContentTypes.HasModTime = true;
193  ContentTypes.HasLength = true;
194
195  while (true) {
196    Error Err = Error::success();
197    StringRef Name = DebugLineData.getCStrRef(OffsetPtr, &Err);
198    if (!Err && Name.empty())
199      break;
200
201    DWARFDebugLine::FileNameEntry FileEntry;
202    FileEntry.Name =
203        DWARFFormValue::createFromPValue(dwarf::DW_FORM_string, Name.data());
204    FileEntry.DirIdx = DebugLineData.getULEB128(OffsetPtr, &Err);
205    FileEntry.ModTime = DebugLineData.getULEB128(OffsetPtr, &Err);
206    FileEntry.Length = DebugLineData.getULEB128(OffsetPtr, &Err);
207
208    if (Err) {
209      consumeError(std::move(Err));
210      return createStringError(
211          errc::invalid_argument,
212          "file names table was not null terminated before "
213          "the end of the prologue");
214    }
215    FileNames.push_back(FileEntry);
216  }
217
218  return Error::success();
219}
220
221// Parse v5 directory/file entry content descriptions.
222// Returns the descriptors, or an error if we did not find a path or ran off
223// the end of the prologue.
224static llvm::Expected<ContentDescriptors>
225parseV5EntryFormat(const DWARFDataExtractor &DebugLineData, uint64_t *OffsetPtr,
226                   DWARFDebugLine::ContentTypeTracker *ContentTypes) {
227  Error Err = Error::success();
228  ContentDescriptors Descriptors;
229  int FormatCount = DebugLineData.getU8(OffsetPtr, &Err);
230  bool HasPath = false;
231  for (int I = 0; I != FormatCount && !Err; ++I) {
232    ContentDescriptor Descriptor;
233    Descriptor.Type =
234        dwarf::LineNumberEntryFormat(DebugLineData.getULEB128(OffsetPtr, &Err));
235    Descriptor.Form = dwarf::Form(DebugLineData.getULEB128(OffsetPtr, &Err));
236    if (Descriptor.Type == dwarf::DW_LNCT_path)
237      HasPath = true;
238    if (ContentTypes)
239      ContentTypes->trackContentType(Descriptor.Type);
240    Descriptors.push_back(Descriptor);
241  }
242
243  if (Err)
244    return createStringError(errc::invalid_argument,
245                             "failed to parse entry content descriptors: %s",
246                             toString(std::move(Err)).c_str());
247
248  if (!HasPath)
249    return createStringError(errc::invalid_argument,
250                             "failed to parse entry content descriptions"
251                             " because no path was found");
252  return Descriptors;
253}
254
255static Error
256parseV5DirFileTables(const DWARFDataExtractor &DebugLineData,
257                     uint64_t *OffsetPtr, const dwarf::FormParams &FormParams,
258                     const DWARFContext &Ctx, const DWARFUnit *U,
259                     DWARFDebugLine::ContentTypeTracker &ContentTypes,
260                     std::vector<DWARFFormValue> &IncludeDirectories,
261                     std::vector<DWARFDebugLine::FileNameEntry> &FileNames) {
262  // Get the directory entry description.
263  llvm::Expected<ContentDescriptors> DirDescriptors =
264      parseV5EntryFormat(DebugLineData, OffsetPtr, nullptr);
265  if (!DirDescriptors)
266    return DirDescriptors.takeError();
267
268  // Get the directory entries, according to the format described above.
269  uint64_t DirEntryCount = DebugLineData.getULEB128(OffsetPtr);
270  for (uint64_t I = 0; I != DirEntryCount; ++I) {
271    for (auto Descriptor : *DirDescriptors) {
272      DWARFFormValue Value(Descriptor.Form);
273      switch (Descriptor.Type) {
274      case DW_LNCT_path:
275        if (!Value.extractValue(DebugLineData, OffsetPtr, FormParams, &Ctx, U))
276          return createStringError(errc::invalid_argument,
277                                   "failed to parse directory entry because "
278                                   "extracting the form value failed");
279        IncludeDirectories.push_back(Value);
280        break;
281      default:
282        if (!Value.skipValue(DebugLineData, OffsetPtr, FormParams))
283          return createStringError(errc::invalid_argument,
284                                   "failed to parse directory entry because "
285                                   "skipping the form value failed");
286      }
287    }
288  }
289
290  // Get the file entry description.
291  llvm::Expected<ContentDescriptors> FileDescriptors =
292      parseV5EntryFormat(DebugLineData, OffsetPtr, &ContentTypes);
293  if (!FileDescriptors)
294    return FileDescriptors.takeError();
295
296  // Get the file entries, according to the format described above.
297  uint64_t FileEntryCount = DebugLineData.getULEB128(OffsetPtr);
298  for (uint64_t I = 0; I != FileEntryCount; ++I) {
299    DWARFDebugLine::FileNameEntry FileEntry;
300    for (auto Descriptor : *FileDescriptors) {
301      DWARFFormValue Value(Descriptor.Form);
302      if (!Value.extractValue(DebugLineData, OffsetPtr, FormParams, &Ctx, U))
303        return createStringError(errc::invalid_argument,
304                                 "failed to parse file entry because "
305                                 "extracting the form value failed");
306      switch (Descriptor.Type) {
307      case DW_LNCT_path:
308        FileEntry.Name = Value;
309        break;
310      case DW_LNCT_LLVM_source:
311        FileEntry.Source = Value;
312        break;
313      case DW_LNCT_directory_index:
314        FileEntry.DirIdx = Value.getAsUnsignedConstant().getValue();
315        break;
316      case DW_LNCT_timestamp:
317        FileEntry.ModTime = Value.getAsUnsignedConstant().getValue();
318        break;
319      case DW_LNCT_size:
320        FileEntry.Length = Value.getAsUnsignedConstant().getValue();
321        break;
322      case DW_LNCT_MD5:
323        if (!Value.getAsBlock() || Value.getAsBlock().getValue().size() != 16)
324          return createStringError(
325              errc::invalid_argument,
326              "failed to parse file entry because the MD5 hash is invalid");
327        std::uninitialized_copy_n(Value.getAsBlock().getValue().begin(), 16,
328                                  FileEntry.Checksum.Bytes.begin());
329        break;
330      default:
331        break;
332      }
333    }
334    FileNames.push_back(FileEntry);
335  }
336  return Error::success();
337}
338
339uint64_t DWARFDebugLine::Prologue::getLength() const {
340  uint64_t Length = PrologueLength + sizeofTotalLength() +
341                    sizeof(getVersion()) + sizeofPrologueLength();
342  if (getVersion() >= 5)
343    Length += 2; // Address + Segment selector sizes.
344  return Length;
345}
346
347Error DWARFDebugLine::Prologue::parse(
348    DWARFDataExtractor DebugLineData, uint64_t *OffsetPtr,
349    function_ref<void(Error)> RecoverableErrorHandler, const DWARFContext &Ctx,
350    const DWARFUnit *U) {
351  const uint64_t PrologueOffset = *OffsetPtr;
352
353  clear();
354  DataExtractor::Cursor Cursor(*OffsetPtr);
355  std::tie(TotalLength, FormParams.Format) =
356      DebugLineData.getInitialLength(Cursor);
357
358  DebugLineData =
359      DWARFDataExtractor(DebugLineData, Cursor.tell() + TotalLength);
360  FormParams.Version = DebugLineData.getU16(Cursor);
361  if (Cursor && !versionIsSupported(getVersion())) {
362    // Treat this error as unrecoverable - we cannot be sure what any of
363    // the data represents including the length field, so cannot skip it or make
364    // any reasonable assumptions.
365    *OffsetPtr = Cursor.tell();
366    return createStringError(
367        errc::not_supported,
368        "parsing line table prologue at offset 0x%8.8" PRIx64
369        ": unsupported version %" PRIu16,
370        PrologueOffset, getVersion());
371  }
372
373  if (getVersion() >= 5) {
374    FormParams.AddrSize = DebugLineData.getU8(Cursor);
375    assert((!Cursor || DebugLineData.getAddressSize() == 0 ||
376            DebugLineData.getAddressSize() == getAddressSize()) &&
377           "Line table header and data extractor disagree");
378    SegSelectorSize = DebugLineData.getU8(Cursor);
379  }
380
381  PrologueLength =
382      DebugLineData.getRelocatedValue(Cursor, sizeofPrologueLength());
383  const uint64_t EndPrologueOffset = PrologueLength + Cursor.tell();
384  DebugLineData = DWARFDataExtractor(DebugLineData, EndPrologueOffset);
385  MinInstLength = DebugLineData.getU8(Cursor);
386  if (getVersion() >= 4)
387    MaxOpsPerInst = DebugLineData.getU8(Cursor);
388  DefaultIsStmt = DebugLineData.getU8(Cursor);
389  LineBase = DebugLineData.getU8(Cursor);
390  LineRange = DebugLineData.getU8(Cursor);
391  OpcodeBase = DebugLineData.getU8(Cursor);
392
393  if (Cursor && OpcodeBase == 0) {
394    // If the opcode base is 0, we cannot read the standard opcode lengths (of
395    // which there are supposed to be one fewer than the opcode base). Assume
396    // there are no standard opcodes and continue parsing.
397    RecoverableErrorHandler(createStringError(
398        errc::invalid_argument,
399        "parsing line table prologue at offset 0x%8.8" PRIx64
400        " found opcode base of 0. Assuming no standard opcodes",
401        PrologueOffset));
402  } else if (Cursor) {
403    StandardOpcodeLengths.reserve(OpcodeBase - 1);
404    for (uint32_t I = 1; I < OpcodeBase; ++I) {
405      uint8_t OpLen = DebugLineData.getU8(Cursor);
406      StandardOpcodeLengths.push_back(OpLen);
407    }
408  }
409
410  *OffsetPtr = Cursor.tell();
411  // A corrupt file name or directory table does not prevent interpretation of
412  // the main line program, so check the cursor state now so that its errors can
413  // be handled separately.
414  if (!Cursor)
415    return createStringError(
416        errc::invalid_argument,
417        "parsing line table prologue at offset 0x%8.8" PRIx64 ": %s",
418        PrologueOffset, toString(Cursor.takeError()).c_str());
419
420  Error E =
421      getVersion() >= 5
422          ? parseV5DirFileTables(DebugLineData, OffsetPtr, FormParams, Ctx, U,
423                                 ContentTypes, IncludeDirectories, FileNames)
424          : parseV2DirFileTables(DebugLineData, OffsetPtr, ContentTypes,
425                                 IncludeDirectories, FileNames);
426  if (E) {
427    RecoverableErrorHandler(joinErrors(
428        createStringError(
429            errc::invalid_argument,
430            "parsing line table prologue at 0x%8.8" PRIx64
431            " found an invalid directory or file table description at"
432            " 0x%8.8" PRIx64,
433            PrologueOffset, *OffsetPtr),
434        std::move(E)));
435    return Error::success();
436  }
437
438  assert(*OffsetPtr <= EndPrologueOffset);
439  if (*OffsetPtr != EndPrologueOffset) {
440    RecoverableErrorHandler(createStringError(
441        errc::invalid_argument,
442        "unknown data in line table prologue at offset 0x%8.8" PRIx64
443        ": parsing ended (at offset 0x%8.8" PRIx64
444        ") before reaching the prologue end at offset 0x%8.8" PRIx64,
445        PrologueOffset, *OffsetPtr, EndPrologueOffset));
446  }
447  return Error::success();
448}
449
450DWARFDebugLine::Row::Row(bool DefaultIsStmt) { reset(DefaultIsStmt); }
451
452void DWARFDebugLine::Row::postAppend() {
453  Discriminator = 0;
454  BasicBlock = false;
455  PrologueEnd = false;
456  EpilogueBegin = false;
457}
458
459void DWARFDebugLine::Row::reset(bool DefaultIsStmt) {
460  Address.Address = 0;
461  Address.SectionIndex = object::SectionedAddress::UndefSection;
462  Line = 1;
463  Column = 0;
464  File = 1;
465  Isa = 0;
466  Discriminator = 0;
467  IsStmt = DefaultIsStmt;
468  BasicBlock = false;
469  EndSequence = false;
470  PrologueEnd = false;
471  EpilogueBegin = false;
472}
473
474void DWARFDebugLine::Row::dumpTableHeader(raw_ostream &OS, unsigned Indent) {
475  OS.indent(Indent)
476      << "Address            Line   Column File   ISA Discriminator Flags\n";
477  OS.indent(Indent)
478      << "------------------ ------ ------ ------ --- ------------- "
479         "-------------\n";
480}
481
482void DWARFDebugLine::Row::dump(raw_ostream &OS) const {
483  OS << format("0x%16.16" PRIx64 " %6u %6u", Address.Address, Line, Column)
484     << format(" %6u %3u %13u ", File, Isa, Discriminator)
485     << (IsStmt ? " is_stmt" : "") << (BasicBlock ? " basic_block" : "")
486     << (PrologueEnd ? " prologue_end" : "")
487     << (EpilogueBegin ? " epilogue_begin" : "")
488     << (EndSequence ? " end_sequence" : "") << '\n';
489}
490
491DWARFDebugLine::Sequence::Sequence() { reset(); }
492
493void DWARFDebugLine::Sequence::reset() {
494  LowPC = 0;
495  HighPC = 0;
496  SectionIndex = object::SectionedAddress::UndefSection;
497  FirstRowIndex = 0;
498  LastRowIndex = 0;
499  Empty = true;
500}
501
502DWARFDebugLine::LineTable::LineTable() { clear(); }
503
504void DWARFDebugLine::LineTable::dump(raw_ostream &OS,
505                                     DIDumpOptions DumpOptions) const {
506  Prologue.dump(OS, DumpOptions);
507
508  if (!Rows.empty()) {
509    OS << '\n';
510    Row::dumpTableHeader(OS, 0);
511    for (const Row &R : Rows) {
512      R.dump(OS);
513    }
514  }
515
516  // Terminate the table with a final blank line to clearly delineate it from
517  // later dumps.
518  OS << '\n';
519}
520
521void DWARFDebugLine::LineTable::clear() {
522  Prologue.clear();
523  Rows.clear();
524  Sequences.clear();
525}
526
527DWARFDebugLine::ParsingState::ParsingState(
528    struct LineTable *LT, uint64_t TableOffset,
529    function_ref<void(Error)> ErrorHandler)
530    : LineTable(LT), LineTableOffset(TableOffset), ErrorHandler(ErrorHandler) {
531  resetRowAndSequence();
532}
533
534void DWARFDebugLine::ParsingState::resetRowAndSequence() {
535  Row.reset(LineTable->Prologue.DefaultIsStmt);
536  Sequence.reset();
537}
538
539void DWARFDebugLine::ParsingState::appendRowToMatrix() {
540  unsigned RowNumber = LineTable->Rows.size();
541  if (Sequence.Empty) {
542    // Record the beginning of instruction sequence.
543    Sequence.Empty = false;
544    Sequence.LowPC = Row.Address.Address;
545    Sequence.FirstRowIndex = RowNumber;
546  }
547  LineTable->appendRow(Row);
548  if (Row.EndSequence) {
549    // Record the end of instruction sequence.
550    Sequence.HighPC = Row.Address.Address;
551    Sequence.LastRowIndex = RowNumber + 1;
552    Sequence.SectionIndex = Row.Address.SectionIndex;
553    if (Sequence.isValid())
554      LineTable->appendSequence(Sequence);
555    Sequence.reset();
556  }
557  Row.postAppend();
558}
559
560const DWARFDebugLine::LineTable *
561DWARFDebugLine::getLineTable(uint64_t Offset) const {
562  LineTableConstIter Pos = LineTableMap.find(Offset);
563  if (Pos != LineTableMap.end())
564    return &Pos->second;
565  return nullptr;
566}
567
568Expected<const DWARFDebugLine::LineTable *> DWARFDebugLine::getOrParseLineTable(
569    DWARFDataExtractor &DebugLineData, uint64_t Offset, const DWARFContext &Ctx,
570    const DWARFUnit *U, function_ref<void(Error)> RecoverableErrorHandler) {
571  if (!DebugLineData.isValidOffset(Offset))
572    return createStringError(errc::invalid_argument, "offset 0x%8.8" PRIx64
573                       " is not a valid debug line section offset",
574                       Offset);
575
576  std::pair<LineTableIter, bool> Pos =
577      LineTableMap.insert(LineTableMapTy::value_type(Offset, LineTable()));
578  LineTable *LT = &Pos.first->second;
579  if (Pos.second) {
580    if (Error Err =
581            LT->parse(DebugLineData, &Offset, Ctx, U, RecoverableErrorHandler))
582      return std::move(Err);
583    return LT;
584  }
585  return LT;
586}
587
588static StringRef getOpcodeName(uint8_t Opcode, uint8_t OpcodeBase) {
589  assert(Opcode != 0);
590  if (Opcode < OpcodeBase)
591    return LNStandardString(Opcode);
592  return "special";
593}
594
595uint64_t DWARFDebugLine::ParsingState::advanceAddr(uint64_t OperationAdvance,
596                                                   uint8_t Opcode,
597                                                   uint64_t OpcodeOffset) {
598  StringRef OpcodeName = getOpcodeName(Opcode, LineTable->Prologue.OpcodeBase);
599  // For versions less than 4, the MaxOpsPerInst member is set to 0, as the
600  // maximum_operations_per_instruction field wasn't introduced until DWARFv4.
601  // Don't warn about bad values in this situation.
602  if (ReportAdvanceAddrProblem && LineTable->Prologue.getVersion() >= 4 &&
603      LineTable->Prologue.MaxOpsPerInst != 1)
604    ErrorHandler(createStringError(
605        errc::not_supported,
606        "line table program at offset 0x%8.8" PRIx64
607        " contains a %s opcode at offset 0x%8.8" PRIx64
608        ", but the prologue maximum_operations_per_instruction value is %" PRId8
609        ", which is unsupported. Assuming a value of 1 instead",
610        LineTableOffset, OpcodeName.data(), OpcodeOffset,
611        LineTable->Prologue.MaxOpsPerInst));
612  if (ReportAdvanceAddrProblem && LineTable->Prologue.MinInstLength == 0)
613    ErrorHandler(
614        createStringError(errc::invalid_argument,
615                          "line table program at offset 0x%8.8" PRIx64
616                          " contains a %s opcode at offset 0x%8.8" PRIx64
617                          ", but the prologue minimum_instruction_length value "
618                          "is 0, which prevents any address advancing",
619                          LineTableOffset, OpcodeName.data(), OpcodeOffset));
620  ReportAdvanceAddrProblem = false;
621  uint64_t AddrOffset = OperationAdvance * LineTable->Prologue.MinInstLength;
622  Row.Address.Address += AddrOffset;
623  return AddrOffset;
624}
625
626DWARFDebugLine::ParsingState::AddrAndAdjustedOpcode
627DWARFDebugLine::ParsingState::advanceAddrForOpcode(uint8_t Opcode,
628                                                   uint64_t OpcodeOffset) {
629  assert(Opcode == DW_LNS_const_add_pc ||
630         Opcode >= LineTable->Prologue.OpcodeBase);
631  if (ReportBadLineRange && LineTable->Prologue.LineRange == 0) {
632    StringRef OpcodeName =
633        getOpcodeName(Opcode, LineTable->Prologue.OpcodeBase);
634    ErrorHandler(
635        createStringError(errc::not_supported,
636                          "line table program at offset 0x%8.8" PRIx64
637                          " contains a %s opcode at offset 0x%8.8" PRIx64
638                          ", but the prologue line_range value is 0. The "
639                          "address and line will not be adjusted",
640                          LineTableOffset, OpcodeName.data(), OpcodeOffset));
641    ReportBadLineRange = false;
642  }
643
644  uint8_t OpcodeValue = Opcode;
645  if (Opcode == DW_LNS_const_add_pc)
646    OpcodeValue = 255;
647  uint8_t AdjustedOpcode = OpcodeValue - LineTable->Prologue.OpcodeBase;
648  uint64_t OperationAdvance =
649      LineTable->Prologue.LineRange != 0
650          ? AdjustedOpcode / LineTable->Prologue.LineRange
651          : 0;
652  uint64_t AddrOffset = advanceAddr(OperationAdvance, Opcode, OpcodeOffset);
653  return {AddrOffset, AdjustedOpcode};
654}
655
656DWARFDebugLine::ParsingState::AddrAndLineDelta
657DWARFDebugLine::ParsingState::handleSpecialOpcode(uint8_t Opcode,
658                                                  uint64_t OpcodeOffset) {
659  // A special opcode value is chosen based on the amount that needs
660  // to be added to the line and address registers. The maximum line
661  // increment for a special opcode is the value of the line_base
662  // field in the header, plus the value of the line_range field,
663  // minus 1 (line base + line range - 1). If the desired line
664  // increment is greater than the maximum line increment, a standard
665  // opcode must be used instead of a special opcode. The "address
666  // advance" is calculated by dividing the desired address increment
667  // by the minimum_instruction_length field from the header. The
668  // special opcode is then calculated using the following formula:
669  //
670  //  opcode = (desired line increment - line_base) +
671  //           (line_range * address advance) + opcode_base
672  //
673  // If the resulting opcode is greater than 255, a standard opcode
674  // must be used instead.
675  //
676  // To decode a special opcode, subtract the opcode_base from the
677  // opcode itself to give the adjusted opcode. The amount to
678  // increment the address register is the result of the adjusted
679  // opcode divided by the line_range multiplied by the
680  // minimum_instruction_length field from the header. That is:
681  //
682  //  address increment = (adjusted opcode / line_range) *
683  //                      minimum_instruction_length
684  //
685  // The amount to increment the line register is the line_base plus
686  // the result of the adjusted opcode modulo the line_range. That is:
687  //
688  // line increment = line_base + (adjusted opcode % line_range)
689
690  DWARFDebugLine::ParsingState::AddrAndAdjustedOpcode AddrAdvanceResult =
691      advanceAddrForOpcode(Opcode, OpcodeOffset);
692  int32_t LineOffset = 0;
693  if (LineTable->Prologue.LineRange != 0)
694    LineOffset =
695        LineTable->Prologue.LineBase +
696        (AddrAdvanceResult.AdjustedOpcode % LineTable->Prologue.LineRange);
697  Row.Line += LineOffset;
698  return {AddrAdvanceResult.AddrDelta, LineOffset};
699}
700
701/// Parse a ULEB128 using the specified \p Cursor. \returns the parsed value on
702/// success, or None if \p Cursor is in a failing state.
703template <typename T>
704static Optional<T> parseULEB128(DWARFDataExtractor &Data,
705                                DataExtractor::Cursor &Cursor) {
706  T Value = Data.getULEB128(Cursor);
707  if (Cursor)
708    return Value;
709  return None;
710}
711
712Error DWARFDebugLine::LineTable::parse(
713    DWARFDataExtractor &DebugLineData, uint64_t *OffsetPtr,
714    const DWARFContext &Ctx, const DWARFUnit *U,
715    function_ref<void(Error)> RecoverableErrorHandler, raw_ostream *OS,
716    bool Verbose) {
717  assert((OS || !Verbose) && "cannot have verbose output without stream");
718  const uint64_t DebugLineOffset = *OffsetPtr;
719
720  clear();
721
722  Error PrologueErr =
723      Prologue.parse(DebugLineData, OffsetPtr, RecoverableErrorHandler, Ctx, U);
724
725  if (OS) {
726    DIDumpOptions DumpOptions;
727    DumpOptions.Verbose = Verbose;
728    Prologue.dump(*OS, DumpOptions);
729  }
730
731  if (PrologueErr) {
732    // Ensure there is a blank line after the prologue to clearly delineate it
733    // from later dumps.
734    if (OS)
735      *OS << "\n";
736    return PrologueErr;
737  }
738
739  uint64_t ProgramLength = Prologue.TotalLength + Prologue.sizeofTotalLength();
740  if (!DebugLineData.isValidOffsetForDataOfSize(DebugLineOffset,
741                                                ProgramLength)) {
742    assert(DebugLineData.size() > DebugLineOffset &&
743           "prologue parsing should handle invalid offset");
744    uint64_t BytesRemaining = DebugLineData.size() - DebugLineOffset;
745    RecoverableErrorHandler(
746        createStringError(errc::invalid_argument,
747                          "line table program with offset 0x%8.8" PRIx64
748                          " has length 0x%8.8" PRIx64 " but only 0x%8.8" PRIx64
749                          " bytes are available",
750                          DebugLineOffset, ProgramLength, BytesRemaining));
751    // Continue by capping the length at the number of remaining bytes.
752    ProgramLength = BytesRemaining;
753  }
754
755  // Create a DataExtractor which can only see the data up to the end of the
756  // table, to prevent reading past the end.
757  const uint64_t EndOffset = DebugLineOffset + ProgramLength;
758  DWARFDataExtractor TableData(DebugLineData, EndOffset);
759
760  // See if we should tell the data extractor the address size.
761  if (TableData.getAddressSize() == 0)
762    TableData.setAddressSize(Prologue.getAddressSize());
763  else
764    assert(Prologue.getAddressSize() == 0 ||
765           Prologue.getAddressSize() == TableData.getAddressSize());
766
767  ParsingState State(this, DebugLineOffset, RecoverableErrorHandler);
768
769  *OffsetPtr = DebugLineOffset + Prologue.getLength();
770  if (OS && *OffsetPtr < EndOffset) {
771    *OS << '\n';
772    Row::dumpTableHeader(*OS, /*Indent=*/Verbose ? 12 : 0);
773  }
774  while (*OffsetPtr < EndOffset) {
775    DataExtractor::Cursor Cursor(*OffsetPtr);
776
777    if (Verbose)
778      *OS << format("0x%08.08" PRIx64 ": ", *OffsetPtr);
779
780    uint64_t OpcodeOffset = *OffsetPtr;
781    uint8_t Opcode = TableData.getU8(Cursor);
782    size_t RowCount = Rows.size();
783
784    if (Cursor && Verbose)
785      *OS << format("%02.02" PRIx8 " ", Opcode);
786
787    if (Opcode == 0) {
788      // Extended Opcodes always start with a zero opcode followed by
789      // a uleb128 length so you can skip ones you don't know about
790      uint64_t Len = TableData.getULEB128(Cursor);
791      uint64_t ExtOffset = Cursor.tell();
792
793      // Tolerate zero-length; assume length is correct and soldier on.
794      if (Len == 0) {
795        if (Cursor && Verbose)
796          *OS << "Badly formed extended line op (length 0)\n";
797        if (!Cursor) {
798          if (Verbose)
799            *OS << "\n";
800          RecoverableErrorHandler(Cursor.takeError());
801        }
802        *OffsetPtr = Cursor.tell();
803        continue;
804      }
805
806      uint8_t SubOpcode = TableData.getU8(Cursor);
807      // OperandOffset will be the same as ExtOffset, if it was not possible to
808      // read the SubOpcode.
809      uint64_t OperandOffset = Cursor.tell();
810      if (Verbose)
811        *OS << LNExtendedString(SubOpcode);
812      switch (SubOpcode) {
813      case DW_LNE_end_sequence:
814        // Set the end_sequence register of the state machine to true and
815        // append a row to the matrix using the current values of the
816        // state-machine registers. Then reset the registers to the initial
817        // values specified above. Every statement program sequence must end
818        // with a DW_LNE_end_sequence instruction which creates a row whose
819        // address is that of the byte after the last target machine instruction
820        // of the sequence.
821        State.Row.EndSequence = true;
822        // No need to test the Cursor is valid here, since it must be to get
823        // into this code path - if it were invalid, the default case would be
824        // followed.
825        if (Verbose) {
826          *OS << "\n";
827          OS->indent(12);
828        }
829        if (OS)
830          State.Row.dump(*OS);
831        State.appendRowToMatrix();
832        State.resetRowAndSequence();
833        break;
834
835      case DW_LNE_set_address:
836        // Takes a single relocatable address as an operand. The size of the
837        // operand is the size appropriate to hold an address on the target
838        // machine. Set the address register to the value given by the
839        // relocatable address. All of the other statement program opcodes
840        // that affect the address register add a delta to it. This instruction
841        // stores a relocatable value into it instead.
842        //
843        // Make sure the extractor knows the address size.  If not, infer it
844        // from the size of the operand.
845        {
846          uint8_t ExtractorAddressSize = TableData.getAddressSize();
847          uint64_t OpcodeAddressSize = Len - 1;
848          if (ExtractorAddressSize != OpcodeAddressSize &&
849              ExtractorAddressSize != 0)
850            RecoverableErrorHandler(createStringError(
851                errc::invalid_argument,
852                "mismatching address size at offset 0x%8.8" PRIx64
853                " expected 0x%2.2" PRIx8 " found 0x%2.2" PRIx64,
854                ExtOffset, ExtractorAddressSize, Len - 1));
855
856          // Assume that the line table is correct and temporarily override the
857          // address size. If the size is unsupported, give up trying to read
858          // the address and continue to the next opcode.
859          if (OpcodeAddressSize != 1 && OpcodeAddressSize != 2 &&
860              OpcodeAddressSize != 4 && OpcodeAddressSize != 8) {
861            RecoverableErrorHandler(createStringError(
862                errc::invalid_argument,
863                "address size 0x%2.2" PRIx64
864                " of DW_LNE_set_address opcode at offset 0x%8.8" PRIx64
865                " is unsupported",
866                OpcodeAddressSize, ExtOffset));
867            TableData.skip(Cursor, OpcodeAddressSize);
868          } else {
869            TableData.setAddressSize(OpcodeAddressSize);
870            State.Row.Address.Address = TableData.getRelocatedAddress(
871                Cursor, &State.Row.Address.SectionIndex);
872
873            // Restore the address size if the extractor already had it.
874            if (ExtractorAddressSize != 0)
875              TableData.setAddressSize(ExtractorAddressSize);
876          }
877
878          if (Cursor && Verbose)
879            *OS << format(" (0x%16.16" PRIx64 ")", State.Row.Address.Address);
880        }
881        break;
882
883      case DW_LNE_define_file:
884        // Takes 4 arguments. The first is a null terminated string containing
885        // a source file name. The second is an unsigned LEB128 number
886        // representing the directory index of the directory in which the file
887        // was found. The third is an unsigned LEB128 number representing the
888        // time of last modification of the file. The fourth is an unsigned
889        // LEB128 number representing the length in bytes of the file. The time
890        // and length fields may contain LEB128(0) if the information is not
891        // available.
892        //
893        // The directory index represents an entry in the include_directories
894        // section of the statement program prologue. The index is LEB128(0)
895        // if the file was found in the current directory of the compilation,
896        // LEB128(1) if it was found in the first directory in the
897        // include_directories section, and so on. The directory index is
898        // ignored for file names that represent full path names.
899        //
900        // The files are numbered, starting at 1, in the order in which they
901        // appear; the names in the prologue come before names defined by
902        // the DW_LNE_define_file instruction. These numbers are used in the
903        // the file register of the state machine.
904        {
905          FileNameEntry FileEntry;
906          const char *Name = TableData.getCStr(Cursor);
907          FileEntry.Name =
908              DWARFFormValue::createFromPValue(dwarf::DW_FORM_string, Name);
909          FileEntry.DirIdx = TableData.getULEB128(Cursor);
910          FileEntry.ModTime = TableData.getULEB128(Cursor);
911          FileEntry.Length = TableData.getULEB128(Cursor);
912          Prologue.FileNames.push_back(FileEntry);
913          if (Cursor && Verbose)
914            *OS << " (" << Name << ", dir=" << FileEntry.DirIdx << ", mod_time="
915                << format("(0x%16.16" PRIx64 ")", FileEntry.ModTime)
916                << ", length=" << FileEntry.Length << ")";
917        }
918        break;
919
920      case DW_LNE_set_discriminator:
921        State.Row.Discriminator = TableData.getULEB128(Cursor);
922        if (Cursor && Verbose)
923          *OS << " (" << State.Row.Discriminator << ")";
924        break;
925
926      default:
927        if (Cursor && Verbose)
928          *OS << format("Unrecognized extended op 0x%02.02" PRIx8, SubOpcode)
929              << format(" length %" PRIx64, Len);
930        // Len doesn't include the zero opcode byte or the length itself, but
931        // it does include the sub_opcode, so we have to adjust for that.
932        TableData.skip(Cursor, Len - 1);
933        break;
934      }
935      // Make sure the length as recorded in the table and the standard length
936      // for the opcode match. If they don't, continue from the end as claimed
937      // by the table. Similarly, continue from the claimed end in the event of
938      // a parsing error.
939      uint64_t End = ExtOffset + Len;
940      if (Cursor && Cursor.tell() != End)
941        RecoverableErrorHandler(createStringError(
942            errc::illegal_byte_sequence,
943            "unexpected line op length at offset 0x%8.8" PRIx64
944            " expected 0x%2.2" PRIx64 " found 0x%2.2" PRIx64,
945            ExtOffset, Len, Cursor.tell() - ExtOffset));
946      if (!Cursor && Verbose) {
947        DWARFDataExtractor::Cursor ByteCursor(OperandOffset);
948        uint8_t Byte = TableData.getU8(ByteCursor);
949        if (ByteCursor) {
950          *OS << " (<parsing error>";
951          do {
952            *OS << format(" %2.2" PRIx8, Byte);
953            Byte = TableData.getU8(ByteCursor);
954          } while (ByteCursor);
955          *OS << ")";
956        }
957
958        // The only parse failure in this case should be if the end was reached.
959        // In that case, throw away the error, as the main Cursor's error will
960        // be sufficient.
961        consumeError(ByteCursor.takeError());
962      }
963      *OffsetPtr = End;
964    } else if (Opcode < Prologue.OpcodeBase) {
965      if (Verbose)
966        *OS << LNStandardString(Opcode);
967      switch (Opcode) {
968      // Standard Opcodes
969      case DW_LNS_copy:
970        // Takes no arguments. Append a row to the matrix using the
971        // current values of the state-machine registers.
972        if (Verbose) {
973          *OS << "\n";
974          OS->indent(12);
975        }
976        if (OS)
977          State.Row.dump(*OS);
978        State.appendRowToMatrix();
979        break;
980
981      case DW_LNS_advance_pc:
982        // Takes a single unsigned LEB128 operand, multiplies it by the
983        // min_inst_length field of the prologue, and adds the
984        // result to the address register of the state machine.
985        if (Optional<uint64_t> Operand =
986                parseULEB128<uint64_t>(TableData, Cursor)) {
987          uint64_t AddrOffset =
988              State.advanceAddr(*Operand, Opcode, OpcodeOffset);
989          if (Verbose)
990            *OS << " (" << AddrOffset << ")";
991        }
992        break;
993
994      case DW_LNS_advance_line:
995        // Takes a single signed LEB128 operand and adds that value to
996        // the line register of the state machine.
997        {
998          int64_t LineDelta = TableData.getSLEB128(Cursor);
999          if (Cursor) {
1000            State.Row.Line += LineDelta;
1001            if (Verbose)
1002              *OS << " (" << State.Row.Line << ")";
1003          }
1004        }
1005        break;
1006
1007      case DW_LNS_set_file:
1008        // Takes a single unsigned LEB128 operand and stores it in the file
1009        // register of the state machine.
1010        if (Optional<uint16_t> File =
1011                parseULEB128<uint16_t>(TableData, Cursor)) {
1012          State.Row.File = *File;
1013          if (Verbose)
1014            *OS << " (" << State.Row.File << ")";
1015        }
1016        break;
1017
1018      case DW_LNS_set_column:
1019        // Takes a single unsigned LEB128 operand and stores it in the
1020        // column register of the state machine.
1021        if (Optional<uint16_t> Column =
1022                parseULEB128<uint16_t>(TableData, Cursor)) {
1023          State.Row.Column = *Column;
1024          if (Verbose)
1025            *OS << " (" << State.Row.Column << ")";
1026        }
1027        break;
1028
1029      case DW_LNS_negate_stmt:
1030        // Takes no arguments. Set the is_stmt register of the state
1031        // machine to the logical negation of its current value.
1032        State.Row.IsStmt = !State.Row.IsStmt;
1033        break;
1034
1035      case DW_LNS_set_basic_block:
1036        // Takes no arguments. Set the basic_block register of the
1037        // state machine to true
1038        State.Row.BasicBlock = true;
1039        break;
1040
1041      case DW_LNS_const_add_pc:
1042        // Takes no arguments. Add to the address register of the state
1043        // machine the address increment value corresponding to special
1044        // opcode 255. The motivation for DW_LNS_const_add_pc is this:
1045        // when the statement program needs to advance the address by a
1046        // small amount, it can use a single special opcode, which occupies
1047        // a single byte. When it needs to advance the address by up to
1048        // twice the range of the last special opcode, it can use
1049        // DW_LNS_const_add_pc followed by a special opcode, for a total
1050        // of two bytes. Only if it needs to advance the address by more
1051        // than twice that range will it need to use both DW_LNS_advance_pc
1052        // and a special opcode, requiring three or more bytes.
1053        {
1054          uint64_t AddrOffset =
1055              State.advanceAddrForOpcode(Opcode, OpcodeOffset).AddrDelta;
1056          if (Verbose)
1057            *OS << format(" (0x%16.16" PRIx64 ")", AddrOffset);
1058        }
1059        break;
1060
1061      case DW_LNS_fixed_advance_pc:
1062        // Takes a single uhalf operand. Add to the address register of
1063        // the state machine the value of the (unencoded) operand. This
1064        // is the only extended opcode that takes an argument that is not
1065        // a variable length number. The motivation for DW_LNS_fixed_advance_pc
1066        // is this: existing assemblers cannot emit DW_LNS_advance_pc or
1067        // special opcodes because they cannot encode LEB128 numbers or
1068        // judge when the computation of a special opcode overflows and
1069        // requires the use of DW_LNS_advance_pc. Such assemblers, however,
1070        // can use DW_LNS_fixed_advance_pc instead, sacrificing compression.
1071        {
1072          uint16_t PCOffset =
1073              TableData.getRelocatedValue(Cursor, 2);
1074          if (Cursor) {
1075            State.Row.Address.Address += PCOffset;
1076            if (Verbose)
1077              *OS << format(" (0x%4.4" PRIx16 ")", PCOffset);
1078          }
1079        }
1080        break;
1081
1082      case DW_LNS_set_prologue_end:
1083        // Takes no arguments. Set the prologue_end register of the
1084        // state machine to true
1085        State.Row.PrologueEnd = true;
1086        break;
1087
1088      case DW_LNS_set_epilogue_begin:
1089        // Takes no arguments. Set the basic_block register of the
1090        // state machine to true
1091        State.Row.EpilogueBegin = true;
1092        break;
1093
1094      case DW_LNS_set_isa:
1095        // Takes a single unsigned LEB128 operand and stores it in the
1096        // ISA register of the state machine.
1097        if (Optional<uint8_t> Isa = parseULEB128<uint8_t>(TableData, Cursor)) {
1098          State.Row.Isa = *Isa;
1099          if (Verbose)
1100            *OS << " (" << (uint64_t)State.Row.Isa << ")";
1101        }
1102        break;
1103
1104      default:
1105        // Handle any unknown standard opcodes here. We know the lengths
1106        // of such opcodes because they are specified in the prologue
1107        // as a multiple of LEB128 operands for each opcode.
1108        {
1109          assert(Opcode - 1U < Prologue.StandardOpcodeLengths.size());
1110          if (Verbose)
1111            *OS << "Unrecognized standard opcode";
1112          uint8_t OpcodeLength = Prologue.StandardOpcodeLengths[Opcode - 1];
1113          std::vector<uint64_t> Operands;
1114          for (uint8_t I = 0; I < OpcodeLength; ++I) {
1115            if (Optional<uint64_t> Value =
1116                    parseULEB128<uint64_t>(TableData, Cursor))
1117              Operands.push_back(*Value);
1118            else
1119              break;
1120          }
1121          if (Verbose && !Operands.empty()) {
1122            *OS << " (operands: ";
1123            bool First = true;
1124            for (uint64_t Value : Operands) {
1125              if (!First)
1126                *OS << ", ";
1127              First = false;
1128              *OS << format("0x%16.16" PRIx64, Value);
1129            }
1130            if (Verbose)
1131              *OS << ')';
1132          }
1133        }
1134        break;
1135      }
1136
1137      *OffsetPtr = Cursor.tell();
1138    } else {
1139      // Special Opcodes.
1140      ParsingState::AddrAndLineDelta Delta =
1141          State.handleSpecialOpcode(Opcode, OpcodeOffset);
1142
1143      if (Verbose) {
1144        *OS << "address += " << Delta.Address << ",  line += " << Delta.Line
1145            << "\n";
1146        OS->indent(12);
1147      }
1148      if (OS)
1149        State.Row.dump(*OS);
1150
1151      State.appendRowToMatrix();
1152      *OffsetPtr = Cursor.tell();
1153    }
1154
1155    // When a row is added to the matrix, it is also dumped, which includes a
1156    // new line already, so don't add an extra one.
1157    if (Verbose && Rows.size() == RowCount)
1158      *OS << "\n";
1159
1160    // Most parse failures other than when parsing extended opcodes are due to
1161    // failures to read ULEBs. Bail out of parsing, since we don't know where to
1162    // continue reading from as there is no stated length for such byte
1163    // sequences. Print the final trailing new line if needed before doing so.
1164    if (!Cursor && Opcode != 0) {
1165      if (Verbose)
1166        *OS << "\n";
1167      return Cursor.takeError();
1168    }
1169
1170    if (!Cursor)
1171      RecoverableErrorHandler(Cursor.takeError());
1172  }
1173
1174  if (!State.Sequence.Empty)
1175    RecoverableErrorHandler(createStringError(
1176        errc::illegal_byte_sequence,
1177        "last sequence in debug line table at offset 0x%8.8" PRIx64
1178        " is not terminated",
1179        DebugLineOffset));
1180
1181  // Sort all sequences so that address lookup will work faster.
1182  if (!Sequences.empty()) {
1183    llvm::sort(Sequences, Sequence::orderByHighPC);
1184    // Note: actually, instruction address ranges of sequences should not
1185    // overlap (in shared objects and executables). If they do, the address
1186    // lookup would still work, though, but result would be ambiguous.
1187    // We don't report warning in this case. For example,
1188    // sometimes .so compiled from multiple object files contains a few
1189    // rudimentary sequences for address ranges [0x0, 0xsomething).
1190  }
1191
1192  // Terminate the table with a final blank line to clearly delineate it from
1193  // later dumps.
1194  if (OS)
1195    *OS << "\n";
1196
1197  return Error::success();
1198}
1199
1200uint32_t DWARFDebugLine::LineTable::findRowInSeq(
1201    const DWARFDebugLine::Sequence &Seq,
1202    object::SectionedAddress Address) const {
1203  if (!Seq.containsPC(Address))
1204    return UnknownRowIndex;
1205  assert(Seq.SectionIndex == Address.SectionIndex);
1206  // In some cases, e.g. first instruction in a function, the compiler generates
1207  // two entries, both with the same address. We want the last one.
1208  //
1209  // In general we want a non-empty range: the last row whose address is less
1210  // than or equal to Address. This can be computed as upper_bound - 1.
1211  DWARFDebugLine::Row Row;
1212  Row.Address = Address;
1213  RowIter FirstRow = Rows.begin() + Seq.FirstRowIndex;
1214  RowIter LastRow = Rows.begin() + Seq.LastRowIndex;
1215  assert(FirstRow->Address.Address <= Row.Address.Address &&
1216         Row.Address.Address < LastRow[-1].Address.Address);
1217  RowIter RowPos = std::upper_bound(FirstRow + 1, LastRow - 1, Row,
1218                                    DWARFDebugLine::Row::orderByAddress) -
1219                   1;
1220  assert(Seq.SectionIndex == RowPos->Address.SectionIndex);
1221  return RowPos - Rows.begin();
1222}
1223
1224uint32_t DWARFDebugLine::LineTable::lookupAddress(
1225    object::SectionedAddress Address) const {
1226
1227  // Search for relocatable addresses
1228  uint32_t Result = lookupAddressImpl(Address);
1229
1230  if (Result != UnknownRowIndex ||
1231      Address.SectionIndex == object::SectionedAddress::UndefSection)
1232    return Result;
1233
1234  // Search for absolute addresses
1235  Address.SectionIndex = object::SectionedAddress::UndefSection;
1236  return lookupAddressImpl(Address);
1237}
1238
1239uint32_t DWARFDebugLine::LineTable::lookupAddressImpl(
1240    object::SectionedAddress Address) const {
1241  // First, find an instruction sequence containing the given address.
1242  DWARFDebugLine::Sequence Sequence;
1243  Sequence.SectionIndex = Address.SectionIndex;
1244  Sequence.HighPC = Address.Address;
1245  SequenceIter It = llvm::upper_bound(Sequences, Sequence,
1246                                      DWARFDebugLine::Sequence::orderByHighPC);
1247  if (It == Sequences.end() || It->SectionIndex != Address.SectionIndex)
1248    return UnknownRowIndex;
1249  return findRowInSeq(*It, Address);
1250}
1251
1252bool DWARFDebugLine::LineTable::lookupAddressRange(
1253    object::SectionedAddress Address, uint64_t Size,
1254    std::vector<uint32_t> &Result) const {
1255
1256  // Search for relocatable addresses
1257  if (lookupAddressRangeImpl(Address, Size, Result))
1258    return true;
1259
1260  if (Address.SectionIndex == object::SectionedAddress::UndefSection)
1261    return false;
1262
1263  // Search for absolute addresses
1264  Address.SectionIndex = object::SectionedAddress::UndefSection;
1265  return lookupAddressRangeImpl(Address, Size, Result);
1266}
1267
1268bool DWARFDebugLine::LineTable::lookupAddressRangeImpl(
1269    object::SectionedAddress Address, uint64_t Size,
1270    std::vector<uint32_t> &Result) const {
1271  if (Sequences.empty())
1272    return false;
1273  uint64_t EndAddr = Address.Address + Size;
1274  // First, find an instruction sequence containing the given address.
1275  DWARFDebugLine::Sequence Sequence;
1276  Sequence.SectionIndex = Address.SectionIndex;
1277  Sequence.HighPC = Address.Address;
1278  SequenceIter LastSeq = Sequences.end();
1279  SequenceIter SeqPos = llvm::upper_bound(
1280      Sequences, Sequence, DWARFDebugLine::Sequence::orderByHighPC);
1281  if (SeqPos == LastSeq || !SeqPos->containsPC(Address))
1282    return false;
1283
1284  SequenceIter StartPos = SeqPos;
1285
1286  // Add the rows from the first sequence to the vector, starting with the
1287  // index we just calculated
1288
1289  while (SeqPos != LastSeq && SeqPos->LowPC < EndAddr) {
1290    const DWARFDebugLine::Sequence &CurSeq = *SeqPos;
1291    // For the first sequence, we need to find which row in the sequence is the
1292    // first in our range.
1293    uint32_t FirstRowIndex = CurSeq.FirstRowIndex;
1294    if (SeqPos == StartPos)
1295      FirstRowIndex = findRowInSeq(CurSeq, Address);
1296
1297    // Figure out the last row in the range.
1298    uint32_t LastRowIndex =
1299        findRowInSeq(CurSeq, {EndAddr - 1, Address.SectionIndex});
1300    if (LastRowIndex == UnknownRowIndex)
1301      LastRowIndex = CurSeq.LastRowIndex - 1;
1302
1303    assert(FirstRowIndex != UnknownRowIndex);
1304    assert(LastRowIndex != UnknownRowIndex);
1305
1306    for (uint32_t I = FirstRowIndex; I <= LastRowIndex; ++I) {
1307      Result.push_back(I);
1308    }
1309
1310    ++SeqPos;
1311  }
1312
1313  return true;
1314}
1315
1316Optional<StringRef> DWARFDebugLine::LineTable::getSourceByIndex(uint64_t FileIndex,
1317                                                                FileLineInfoKind Kind) const {
1318  if (Kind == FileLineInfoKind::None || !Prologue.hasFileAtIndex(FileIndex))
1319    return None;
1320  const FileNameEntry &Entry = Prologue.getFileNameEntry(FileIndex);
1321  if (Optional<const char *> source = Entry.Source.getAsCString())
1322    return StringRef(*source);
1323  return None;
1324}
1325
1326static bool isPathAbsoluteOnWindowsOrPosix(const Twine &Path) {
1327  // Debug info can contain paths from any OS, not necessarily
1328  // an OS we're currently running on. Moreover different compilation units can
1329  // be compiled on different operating systems and linked together later.
1330  return sys::path::is_absolute(Path, sys::path::Style::posix) ||
1331         sys::path::is_absolute(Path, sys::path::Style::windows);
1332}
1333
1334bool DWARFDebugLine::Prologue::getFileNameByIndex(
1335    uint64_t FileIndex, StringRef CompDir, FileLineInfoKind Kind,
1336    std::string &Result, sys::path::Style Style) const {
1337  if (Kind == FileLineInfoKind::None || !hasFileAtIndex(FileIndex))
1338    return false;
1339  const FileNameEntry &Entry = getFileNameEntry(FileIndex);
1340  Optional<const char *> Name = Entry.Name.getAsCString();
1341  if (!Name)
1342    return false;
1343  StringRef FileName = *Name;
1344  if (Kind == FileLineInfoKind::RawValue ||
1345      isPathAbsoluteOnWindowsOrPosix(FileName)) {
1346    Result = std::string(FileName);
1347    return true;
1348  }
1349  if (Kind == FileLineInfoKind::BaseNameOnly) {
1350    Result = std::string(llvm::sys::path::filename(FileName));
1351    return true;
1352  }
1353
1354  SmallString<16> FilePath;
1355  StringRef IncludeDir;
1356  // Be defensive about the contents of Entry.
1357  if (getVersion() >= 5) {
1358    // DirIdx 0 is the compilation directory, so don't include it for
1359    // relative names.
1360    if ((Entry.DirIdx != 0 || Kind != FileLineInfoKind::RelativeFilePath) &&
1361        Entry.DirIdx < IncludeDirectories.size())
1362      IncludeDir = IncludeDirectories[Entry.DirIdx].getAsCString().getValue();
1363  } else {
1364    if (0 < Entry.DirIdx && Entry.DirIdx <= IncludeDirectories.size())
1365      IncludeDir =
1366          IncludeDirectories[Entry.DirIdx - 1].getAsCString().getValue();
1367  }
1368
1369  // For absolute paths only, include the compilation directory of compile unit.
1370  // We know that FileName is not absolute, the only way to have an absolute
1371  // path at this point would be if IncludeDir is absolute.
1372  if (Kind == FileLineInfoKind::AbsoluteFilePath && !CompDir.empty() &&
1373      !isPathAbsoluteOnWindowsOrPosix(IncludeDir))
1374    sys::path::append(FilePath, Style, CompDir);
1375
1376  assert((Kind == FileLineInfoKind::AbsoluteFilePath ||
1377          Kind == FileLineInfoKind::RelativeFilePath) &&
1378         "invalid FileLineInfo Kind");
1379
1380  // sys::path::append skips empty strings.
1381  sys::path::append(FilePath, Style, IncludeDir, FileName);
1382  Result = std::string(FilePath.str());
1383  return true;
1384}
1385
1386bool DWARFDebugLine::LineTable::getFileLineInfoForAddress(
1387    object::SectionedAddress Address, const char *CompDir,
1388    FileLineInfoKind Kind, DILineInfo &Result) const {
1389  // Get the index of row we're looking for in the line table.
1390  uint32_t RowIndex = lookupAddress(Address);
1391  if (RowIndex == -1U)
1392    return false;
1393  // Take file number and line/column from the row.
1394  const auto &Row = Rows[RowIndex];
1395  if (!getFileNameByIndex(Row.File, CompDir, Kind, Result.FileName))
1396    return false;
1397  Result.Line = Row.Line;
1398  Result.Column = Row.Column;
1399  Result.Discriminator = Row.Discriminator;
1400  Result.Source = getSourceByIndex(Row.File, Kind);
1401  return true;
1402}
1403
1404// We want to supply the Unit associated with a .debug_line[.dwo] table when
1405// we dump it, if possible, but still dump the table even if there isn't a Unit.
1406// Therefore, collect up handles on all the Units that point into the
1407// line-table section.
1408static DWARFDebugLine::SectionParser::LineToUnitMap
1409buildLineToUnitMap(DWARFDebugLine::SectionParser::cu_range CUs,
1410                   DWARFDebugLine::SectionParser::tu_range TUs) {
1411  DWARFDebugLine::SectionParser::LineToUnitMap LineToUnit;
1412  for (const auto &CU : CUs)
1413    if (auto CUDIE = CU->getUnitDIE())
1414      if (auto StmtOffset = toSectionOffset(CUDIE.find(DW_AT_stmt_list)))
1415        LineToUnit.insert(std::make_pair(*StmtOffset, &*CU));
1416  for (const auto &TU : TUs)
1417    if (auto TUDIE = TU->getUnitDIE())
1418      if (auto StmtOffset = toSectionOffset(TUDIE.find(DW_AT_stmt_list)))
1419        LineToUnit.insert(std::make_pair(*StmtOffset, &*TU));
1420  return LineToUnit;
1421}
1422
1423DWARFDebugLine::SectionParser::SectionParser(DWARFDataExtractor &Data,
1424                                             const DWARFContext &C,
1425                                             cu_range CUs, tu_range TUs)
1426    : DebugLineData(Data), Context(C) {
1427  LineToUnit = buildLineToUnitMap(CUs, TUs);
1428  if (!DebugLineData.isValidOffset(Offset))
1429    Done = true;
1430}
1431
1432bool DWARFDebugLine::Prologue::totalLengthIsValid() const {
1433  return TotalLength != 0u;
1434}
1435
1436DWARFDebugLine::LineTable DWARFDebugLine::SectionParser::parseNext(
1437    function_ref<void(Error)> RecoverableErrorHandler,
1438    function_ref<void(Error)> UnrecoverableErrorHandler, raw_ostream *OS,
1439    bool Verbose) {
1440  assert(DebugLineData.isValidOffset(Offset) &&
1441         "parsing should have terminated");
1442  DWARFUnit *U = prepareToParse(Offset);
1443  uint64_t OldOffset = Offset;
1444  LineTable LT;
1445  if (Error Err = LT.parse(DebugLineData, &Offset, Context, U,
1446                           RecoverableErrorHandler, OS, Verbose))
1447    UnrecoverableErrorHandler(std::move(Err));
1448  moveToNextTable(OldOffset, LT.Prologue);
1449  return LT;
1450}
1451
1452void DWARFDebugLine::SectionParser::skip(
1453    function_ref<void(Error)> RecoverableErrorHandler,
1454    function_ref<void(Error)> UnrecoverableErrorHandler) {
1455  assert(DebugLineData.isValidOffset(Offset) &&
1456         "parsing should have terminated");
1457  DWARFUnit *U = prepareToParse(Offset);
1458  uint64_t OldOffset = Offset;
1459  LineTable LT;
1460  if (Error Err = LT.Prologue.parse(DebugLineData, &Offset,
1461                                    RecoverableErrorHandler, Context, U))
1462    UnrecoverableErrorHandler(std::move(Err));
1463  moveToNextTable(OldOffset, LT.Prologue);
1464}
1465
1466DWARFUnit *DWARFDebugLine::SectionParser::prepareToParse(uint64_t Offset) {
1467  DWARFUnit *U = nullptr;
1468  auto It = LineToUnit.find(Offset);
1469  if (It != LineToUnit.end())
1470    U = It->second;
1471  DebugLineData.setAddressSize(U ? U->getAddressByteSize() : 0);
1472  return U;
1473}
1474
1475void DWARFDebugLine::SectionParser::moveToNextTable(uint64_t OldOffset,
1476                                                    const Prologue &P) {
1477  // If the length field is not valid, we don't know where the next table is, so
1478  // cannot continue to parse. Mark the parser as done, and leave the Offset
1479  // value as it currently is. This will be the end of the bad length field.
1480  if (!P.totalLengthIsValid()) {
1481    Done = true;
1482    return;
1483  }
1484
1485  Offset = OldOffset + P.TotalLength + P.sizeofTotalLength();
1486  if (!DebugLineData.isValidOffset(Offset)) {
1487    Done = true;
1488  }
1489}
1490