// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package dwarf

import (
	
	
	
	
	
)

// A LineReader reads a sequence of LineEntry structures from a DWARF
// "line" section for a single compilation unit. LineEntries occur in
// order of increasing PC and each LineEntry gives metadata for the
// instructions from that LineEntry's PC to just before the next
// LineEntry's PC. The last entry will have its EndSequence field set.
type LineReader struct {
	buf buf

	// Original .debug_line section data. Used by Seek.
	section []byte

	str     []byte // .debug_str
	lineStr []byte // .debug_line_str

	// Header information
	version              uint16
	addrsize             int
	segmentSelectorSize  int
	minInstructionLength int
	maxOpsPerInstruction int
	defaultIsStmt        bool
	lineBase             int
	lineRange            int
	opcodeBase           int
	opcodeLengths        []int
	directories          []string
	fileEntries          []*LineFile

	programOffset Offset // section offset of line number program
	endOffset     Offset // section offset of byte following program

	initialFileEntries int // initial length of fileEntries

	// Current line number program state machine registers
	state     LineEntry // public state
	fileIndex int       // private state
}

// A LineEntry is a row in a DWARF line table.
type LineEntry struct {
	// Address is the program-counter value of a machine
	// instruction generated by the compiler. This LineEntry
	// applies to each instruction from Address to just before the
	// Address of the next LineEntry.
	Address uint64

	// OpIndex is the index of an operation within a VLIW
	// instruction. The index of the first operation is 0. For
	// non-VLIW architectures, it will always be 0. Address and
	// OpIndex together form an operation pointer that can
	// reference any individual operation within the instruction
	// stream.
	OpIndex int

	// File is the source file corresponding to these
	// instructions.
	File *LineFile

	// Line is the source code line number corresponding to these
	// instructions. Lines are numbered beginning at 1. It may be
	// 0 if these instructions cannot be attributed to any source
	// line.
	Line int

	// Column is the column number within the source line of these
	// instructions. Columns are numbered beginning at 1. It may
	// be 0 to indicate the "left edge" of the line.
	Column int

	// IsStmt indicates that Address is a recommended breakpoint
	// location, such as the beginning of a line, statement, or a
	// distinct subpart of a statement.
	IsStmt bool

	// BasicBlock indicates that Address is the beginning of a
	// basic block.
	BasicBlock bool

	// PrologueEnd indicates that Address is one (of possibly
	// many) PCs where execution should be suspended for a
	// breakpoint on entry to the containing function.
	//
	// Added in DWARF 3.
	PrologueEnd bool

	// EpilogueBegin indicates that Address is one (of possibly
	// many) PCs where execution should be suspended for a
	// breakpoint on exit from this function.
	//
	// Added in DWARF 3.
	EpilogueBegin bool

	// ISA is the instruction set architecture for these
	// instructions. Possible ISA values should be defined by the
	// applicable ABI specification.
	//
	// Added in DWARF 3.
	ISA int

	// Discriminator is an arbitrary integer indicating the block
	// to which these instructions belong. It serves to
	// distinguish among multiple blocks that may all have with
	// the same source file, line, and column. Where only one
	// block exists for a given source position, it should be 0.
	//
	// Added in DWARF 3.
	Discriminator int

	// EndSequence indicates that Address is the first byte after
	// the end of a sequence of target machine instructions. If it
	// is set, only this and the Address field are meaningful. A
	// line number table may contain information for multiple
	// potentially disjoint instruction sequences. The last entry
	// in a line table should always have EndSequence set.
	EndSequence bool
}

// A LineFile is a source file referenced by a DWARF line table entry.
type LineFile struct {
	Name   string
	Mtime  uint64 // Implementation defined modification time, or 0 if unknown
	Length int    // File length, or 0 if unknown
}

// LineReader returns a new reader for the line table of compilation
// unit cu, which must be an Entry with tag TagCompileUnit.
//
// If this compilation unit has no line table, it returns nil, nil.
func ( *Data) ( *Entry) (*LineReader, error) {
	if .line == nil {
		// No line tables available.
		return nil, nil
	}

	// Get line table information from cu.
	,  := .Val(AttrStmtList).(int64)
	if ! {
		// cu has no line table.
		return nil, nil
	}
	if  > int64(len(.line)) {
		return nil, errors.New("AttrStmtList value out of range")
	}
	// AttrCompDir is optional if all file names are absolute. Use
	// the empty string if it's not present.
	,  := .Val(AttrCompDir).(string)

	// Create the LineReader.
	 := &.unit[.offsetToUnit(.Offset)]
	 := makeBuf(, , "line", Offset(), .line[:])
	// The compilation directory is implicitly directories[0].
	 := LineReader{
		buf:     ,
		section: .line,
		str:     .str,
		lineStr: .lineStr,
	}

	// Read the header.
	if  := .readHeader();  != nil {
		return nil, 
	}

	// Initialize line reader state.
	.Reset()

	return &, nil
}

// readHeader reads the line number program header from r.buf and sets
// all of the header fields in r.
func ( *LineReader) ( string) error {
	 := &.buf

	// Read basic header fields [DWARF2 6.2.4].
	 := .off
	,  := .unitLength()
	.endOffset = .off + 
	if .endOffset > .off+Offset(len(.data)) {
		return DecodeError{"line", , fmt.Sprintf("line table end %d exceeds section size %d", .endOffset, .off+Offset(len(.data)))}
	}
	.version = .uint16()
	if .err == nil && (.version < 2 || .version > 5) {
		// DWARF goes to all this effort to make new opcodes
		// backward-compatible, and then adds fields right in
		// the middle of the header in new versions, so we're
		// picky about only supporting known line table
		// versions.
		return DecodeError{"line", , fmt.Sprintf("unknown line table version %d", .version)}
	}
	if .version >= 5 {
		.addrsize = int(.uint8())
		.segmentSelectorSize = int(.uint8())
	} else {
		.addrsize = .format.addrsize()
		.segmentSelectorSize = 0
	}
	var  Offset
	if  {
		 = Offset(.uint64())
	} else {
		 = Offset(.uint32())
	}
	.programOffset = .off + 
	.minInstructionLength = int(.uint8())
	if .version >= 4 {
		// [DWARF4 6.2.4]
		.maxOpsPerInstruction = int(.uint8())
	} else {
		.maxOpsPerInstruction = 1
	}
	.defaultIsStmt = .uint8() != 0
	.lineBase = int(int8(.uint8()))
	.lineRange = int(.uint8())

	// Validate header.
	if .err != nil {
		return .err
	}
	if .maxOpsPerInstruction == 0 {
		return DecodeError{"line", , "invalid maximum operations per instruction: 0"}
	}
	if .lineRange == 0 {
		return DecodeError{"line", , "invalid line range: 0"}
	}

	// Read standard opcode length table. This table starts with opcode 1.
	.opcodeBase = int(.uint8())
	.opcodeLengths = make([]int, .opcodeBase)
	for  := 1;  < .opcodeBase; ++ {
		.opcodeLengths[] = int(.uint8())
	}

	// Validate opcode lengths.
	if .err != nil {
		return .err
	}
	for ,  := range .opcodeLengths {
		if ,  := knownOpcodeLengths[];  &&  !=  {
			return DecodeError{"line", , fmt.Sprintf("opcode %d expected to have length %d, but has length %d", , , )}
		}
	}

	if .version < 5 {
		// Read include directories table.
		.directories = []string{}
		for {
			 := .string()
			if .err != nil {
				return .err
			}
			if len() == 0 {
				break
			}
			if !pathIsAbs() {
				// Relative paths are implicitly relative to
				// the compilation directory.
				 = pathJoin(, )
			}
			.directories = append(.directories, )
		}

		// Read file name list. File numbering starts with 1,
		// so leave the first entry nil.
		.fileEntries = make([]*LineFile, 1)
		for {
			if ,  := .readFileEntry();  != nil {
				return 
			} else if  {
				break
			}
		}
	} else {
		 := .readLNCTFormat()
		 := .uint()
		.directories = make([]string, )
		for  := range .directories {
			, , ,  := .readLNCT(, )
			if  != nil {
				return 
			}
			.directories[] = 
		}
		 := .readLNCTFormat()
		 = .uint()
		.fileEntries = make([]*LineFile, )
		for  := range .fileEntries {
			, , ,  := .readLNCT(, )
			if  != nil {
				return 
			}
			.fileEntries[] = &LineFile{, , int()}
		}
	}

	.initialFileEntries = len(.fileEntries)

	return .err
}

// lnctForm is a pair of an LNCT code and a form. This represents an
// entry in the directory name or file name description in the DWARF 5
// line number program header.
type lnctForm struct {
	lnct int
	form format
}

// readLNCTFormat reads an LNCT format description.
func ( *LineReader) () []lnctForm {
	 := .buf.uint8()
	 := make([]lnctForm, )
	for  := range  {
		[].lnct = int(.buf.uint())
		[].form = format(.buf.uint())
	}
	return 
}

// readLNCT reads a sequence of LNCT entries and returns path information.
func ( *LineReader) ( []lnctForm,  bool) ( string,  uint64,  uint64,  error) {
	var  string
	for ,  := range  {
		var  string
		var  uint64
		switch .form {
		case formString:
			 = .buf.string()
		case formStrp, formLineStrp:
			var  uint64
			if  {
				 = .buf.uint64()
			} else {
				 = uint64(.buf.uint32())
			}
			if uint64(int()) !=  {
				return "", 0, 0, DecodeError{"line", .buf.off, "strp/line_strp offset out of range"}
			}
			var  buf
			if .form == formStrp {
				 = makeBuf(.buf.dwarf, .buf.format, "str", 0, .str)
			} else {
				 = makeBuf(.buf.dwarf, .buf.format, "line_str", 0, .lineStr)
			}
			.skip(int())
			 = .string()
			if .err != nil {
				return "", 0, 0, DecodeError{"line", .buf.off, .err.Error()}
			}
		case formStrpSup:
			// Supplemental sections not yet supported.
			if  {
				.buf.uint64()
			} else {
				.buf.uint32()
			}
		case formStrx:
			// .debug_line.dwo sections not yet supported.
			.buf.uint()
		case formStrx1:
			.buf.uint8()
		case formStrx2:
			.buf.uint16()
		case formStrx3:
			.buf.uint24()
		case formStrx4:
			.buf.uint32()
		case formData1:
			 = uint64(.buf.uint8())
		case formData2:
			 = uint64(.buf.uint16())
		case formData4:
			 = uint64(.buf.uint32())
		case formData8:
			 = .buf.uint64()
		case formData16:
			.buf.bytes(16)
		case formDwarfBlock:
			.buf.bytes(int(.buf.uint()))
		case formUdata:
			 = .buf.uint()
		}

		switch .lnct {
		case lnctPath:
			 = 
		case lnctDirectoryIndex:
			if  >= uint64(len(.directories)) {
				return "", 0, 0, DecodeError{"line", .buf.off, "directory index out of range"}
			}
			 = .directories[]
		case lnctTimestamp:
			 = 
		case lnctSize:
			 = 
		case lnctMD5:
			// Ignored.
		}
	}

	if  != "" &&  != "" {
		 = pathJoin(, )
	}

	return , , , nil
}

// readFileEntry reads a file entry from either the header or a
// DW_LNE_define_file extended opcode and adds it to r.fileEntries. A
// true return value indicates that there are no more entries to read.
func ( *LineReader) () (bool, error) {
	 := .buf.string()
	if .buf.err != nil {
		return false, .buf.err
	}
	if len() == 0 {
		return true, nil
	}
	 := .buf.off
	 := int(.buf.uint())
	if !pathIsAbs() {
		if  >= len(.directories) {
			return false, DecodeError{"line", , "directory index too large"}
		}
		 = pathJoin(.directories[], )
	}
	 := .buf.uint()
	 := int(.buf.uint())

	// If this is a dynamically added path and the cursor was
	// backed up, we may have already added this entry. Avoid
	// updating existing line table entries in this case. This
	// avoids an allocation and potential racy access to the slice
	// backing store if the user called Files.
	if len(.fileEntries) < cap(.fileEntries) {
		 := .fileEntries[:len(.fileEntries)+1]
		if [len()-1] != nil {
			// We already processed this addition.
			.fileEntries = 
			return false, nil
		}
	}
	.fileEntries = append(.fileEntries, &LineFile{, , })
	return false, nil
}

// updateFile updates r.state.File after r.fileIndex has
// changed or r.fileEntries has changed.
func ( *LineReader) () {
	if .fileIndex < len(.fileEntries) {
		.state.File = .fileEntries[.fileIndex]
	} else {
		.state.File = nil
	}
}

// Next sets *entry to the next row in this line table and moves to
// the next row. If there are no more entries and the line table is
// properly terminated, it returns io.EOF.
//
// Rows are always in order of increasing entry.Address, but
// entry.Line may go forward or backward.
func ( *LineReader) ( *LineEntry) error {
	if .buf.err != nil {
		return .buf.err
	}

	// Execute opcodes until we reach an opcode that emits a line
	// table entry.
	for {
		if len(.buf.data) == 0 {
			return io.EOF
		}
		 := .step()
		if .buf.err != nil {
			return .buf.err
		}
		if  {
			return nil
		}
	}
}

// knownOpcodeLengths gives the opcode lengths (in varint arguments)
// of known standard opcodes.
var knownOpcodeLengths = map[int]int{
	lnsCopy:             0,
	lnsAdvancePC:        1,
	lnsAdvanceLine:      1,
	lnsSetFile:          1,
	lnsNegateStmt:       0,
	lnsSetBasicBlock:    0,
	lnsConstAddPC:       0,
	lnsSetPrologueEnd:   0,
	lnsSetEpilogueBegin: 0,
	lnsSetISA:           1,
	// lnsFixedAdvancePC takes a uint8 rather than a varint; it's
	// unclear what length the header is supposed to claim, so
	// ignore it.
}

// step processes the next opcode and updates r.state. If the opcode
// emits a row in the line table, this updates *entry and returns
// true.
func ( *LineReader) ( *LineEntry) bool {
	 := int(.buf.uint8())

	if  >= .opcodeBase {
		// Special opcode [DWARF2 6.2.5.1, DWARF4 6.2.5.1]
		 :=  - .opcodeBase
		.advancePC( / .lineRange)
		 := .lineBase + %.lineRange
		.state.Line += 
		goto 
	}

	switch  {
	case 0:
		// Extended opcode [DWARF2 6.2.5.3]
		 := Offset(.buf.uint())
		 := .buf.off
		 := .buf.uint8()

		switch  {
		case lneEndSequence:
			.state.EndSequence = true
			* = .state
			.resetState()

		case lneSetAddress:
			switch .addrsize {
			case 1:
				.state.Address = uint64(.buf.uint8())
			case 2:
				.state.Address = uint64(.buf.uint16())
			case 4:
				.state.Address = uint64(.buf.uint32())
			case 8:
				.state.Address = .buf.uint64()
			default:
				.buf.error("unknown address size")
			}

		case lneDefineFile:
			if ,  := .readFileEntry();  != nil {
				.buf.err = 
				return false
			} else if  {
				.buf.err = DecodeError{"line", , "malformed DW_LNE_define_file operation"}
				return false
			}
			.updateFile()

		case lneSetDiscriminator:
			// [DWARF4 6.2.5.3]
			.state.Discriminator = int(.buf.uint())
		}

		.buf.skip(int( +  - .buf.off))

		if  == lneEndSequence {
			return true
		}

	// Standard opcodes [DWARF2 6.2.5.2]
	case lnsCopy:
		goto 

	case lnsAdvancePC:
		.advancePC(int(.buf.uint()))

	case lnsAdvanceLine:
		.state.Line += int(.buf.int())

	case lnsSetFile:
		.fileIndex = int(.buf.uint())
		.updateFile()

	case lnsSetColumn:
		.state.Column = int(.buf.uint())

	case lnsNegateStmt:
		.state.IsStmt = !.state.IsStmt

	case lnsSetBasicBlock:
		.state.BasicBlock = true

	case lnsConstAddPC:
		.advancePC((255 - .opcodeBase) / .lineRange)

	case lnsFixedAdvancePC:
		.state.Address += uint64(.buf.uint16())

	// DWARF3 standard opcodes [DWARF3 6.2.5.2]
	case lnsSetPrologueEnd:
		.state.PrologueEnd = true

	case lnsSetEpilogueBegin:
		.state.EpilogueBegin = true

	case lnsSetISA:
		.state.ISA = int(.buf.uint())

	default:
		// Unhandled standard opcode. Skip the number of
		// arguments that the prologue says this opcode has.
		for  := 0;  < .opcodeLengths[]; ++ {
			.buf.uint()
		}
	}
	return false

:
	* = .state
	.state.BasicBlock = false
	.state.PrologueEnd = false
	.state.EpilogueBegin = false
	.state.Discriminator = 0
	return true
}

// advancePC advances "operation pointer" (the combination of Address
// and OpIndex) in r.state by opAdvance steps.
func ( *LineReader) ( int) {
	 := .state.OpIndex + 
	.state.Address += uint64(.minInstructionLength * ( / .maxOpsPerInstruction))
	.state.OpIndex =  % .maxOpsPerInstruction
}

// A LineReaderPos represents a position in a line table.
type LineReaderPos struct {
	// off is the current offset in the DWARF line section.
	off Offset
	// numFileEntries is the length of fileEntries.
	numFileEntries int
	// state and fileIndex are the statement machine state at
	// offset off.
	state     LineEntry
	fileIndex int
}

// Tell returns the current position in the line table.
func ( *LineReader) () LineReaderPos {
	return LineReaderPos{.buf.off, len(.fileEntries), .state, .fileIndex}
}

// Seek restores the line table reader to a position returned by Tell.
//
// The argument pos must have been returned by a call to Tell on this
// line table.
func ( *LineReader) ( LineReaderPos) {
	.buf.off = .off
	.buf.data = .section[.buf.off:.endOffset]
	.fileEntries = .fileEntries[:.numFileEntries]
	.state = .state
	.fileIndex = .fileIndex
}

// Reset repositions the line table reader at the beginning of the
// line table.
func ( *LineReader) () {
	// Reset buffer to the line number program offset.
	.buf.off = .programOffset
	.buf.data = .section[.buf.off:.endOffset]

	// Reset file entries list.
	.fileEntries = .fileEntries[:.initialFileEntries]

	// Reset line number program state.
	.resetState()
}

// resetState resets r.state to its default values
func ( *LineReader) () {
	// Reset the state machine registers to the defaults given in
	// [DWARF4 6.2.2].
	.state = LineEntry{
		Address:       0,
		OpIndex:       0,
		File:          nil,
		Line:          1,
		Column:        0,
		IsStmt:        .defaultIsStmt,
		BasicBlock:    false,
		PrologueEnd:   false,
		EpilogueBegin: false,
		ISA:           0,
		Discriminator: 0,
	}
	.fileIndex = 1
	.updateFile()
}

// Files returns the file name table of this compilation unit as of
// the current position in the line table. The file name table may be
// referenced from attributes in this compilation unit such as
// AttrDeclFile.
//
// Entry 0 is always nil, since file index 0 represents "no file".
//
// The file name table of a compilation unit is not fixed. Files
// returns the file table as of the current position in the line
// table. This may contain more entries than the file table at an
// earlier position in the line table, though existing entries never
// change.
func ( *LineReader) () []*LineFile {
	return .fileEntries
}

// ErrUnknownPC is the error returned by LineReader.ScanPC when the
// seek PC is not covered by any entry in the line table.
var ErrUnknownPC = errors.New("ErrUnknownPC")

// SeekPC sets *entry to the LineEntry that includes pc and positions
// the reader on the next entry in the line table. If necessary, this
// will seek backwards to find pc.
//
// If pc is not covered by any entry in this line table, SeekPC
// returns ErrUnknownPC. In this case, *entry and the final seek
// position are unspecified.
//
// Note that DWARF line tables only permit sequential, forward scans.
// Hence, in the worst case, this takes time linear in the size of the
// line table. If the caller wishes to do repeated fast PC lookups, it
// should build an appropriate index of the line table.
func ( *LineReader) ( uint64,  *LineEntry) error {
	if  := .Next();  != nil {
		return 
	}
	if .Address >  {
		// We're too far. Start at the beginning of the table.
		.Reset()
		if  := .Next();  != nil {
			return 
		}
		if .Address >  {
			// The whole table starts after pc.
			.Reset()
			return ErrUnknownPC
		}
	}

	// Scan until we pass pc, then back up one.
	for {
		var  LineEntry
		 := .Tell()
		if  := .Next(&);  != nil {
			if  == io.EOF {
				return ErrUnknownPC
			}
			return 
		}
		if .Address >  {
			if .EndSequence {
				// pc is in a hole in the table.
				return ErrUnknownPC
			}
			// entry is the desired entry. Back up the
			// cursor to "next" and return success.
			.Seek()
			return nil
		}
		* = 
	}
}

// pathIsAbs reports whether path is an absolute path (or "full path
// name" in DWARF parlance). This is in "whatever form makes sense for
// the host system", so this accepts both UNIX-style and DOS-style
// absolute paths. We avoid the filepath package because we want this
// to behave the same regardless of our host system and because we
// don't know what system the paths came from.
func pathIsAbs( string) bool {
	_,  = splitDrive()
	return len() > 0 && ([0] == '/' || [0] == '\\')
}

// pathJoin joins dirname and filename. filename must be relative.
// DWARF paths can be UNIX-style or DOS-style, so this handles both.
func pathJoin(,  string) string {
	if len() == 0 {
		return 
	}
	// dirname should be absolute, which means we can determine
	// whether it's a DOS path reasonably reliably by looking for
	// a drive letter or UNC path.
	,  := splitDrive()
	if  == "" {
		// UNIX-style path.
		return path.Join(, )
	}
	// DOS-style path.
	,  := splitDrive()
	if  != "" {
		if !strings.EqualFold(, ) {
			// Different drives. There's not much we can
			// do here, so just ignore the directory.
			return  + 
		}
		// Drives are the same. Ignore drive on filename.
	}
	if !(strings.HasSuffix(, "/") || strings.HasSuffix(, `\`)) &&  != "" {
		 := `\`
		if strings.HasPrefix(, "/") {
			 = `/`
		}
		 += 
	}
	return  +  + 
}

// splitDrive splits the DOS drive letter or UNC share point from
// path, if any. path == drive + rest
func splitDrive( string) (,  string) {
	if len() >= 2 && [1] == ':' {
		if  := [0]; 'a' <=  &&  <= 'z' || 'A' <=  &&  <= 'Z' {
			return [:2], [2:]
		}
	}
	if len() > 3 && ([0] == '\\' || [0] == '/') && ([1] == '\\' || [1] == '/') {
		// Normalize the path so we can search for just \ below.
		 := strings.Replace(, "/", `\`, -1)
		// Get the host part, which must be non-empty.
		 := strings.IndexByte([2:], '\\') + 2
		if  > 2 {
			// Get the mount-point part, which must be non-empty.
			 := strings.IndexByte([+1:], '\\') +  + 1
			if  >  {
				return [:], [:]
			}
		}
	}
	return "", 
}