// Copyright 2019 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.

// Writes dwarf information to object files.

package obj

import (
	"cmd/internal/dwarf"
	"fmt"
)

// Generate a sequence of opcodes that is as short as possible.
// See section 6.2.5
const (
	LINE_BASE   = -4
	LINE_RANGE  = 10
	PC_RANGE    = (255 - OPCODE_BASE) / LINE_RANGE
	OPCODE_BASE = 11
)

// generateDebugLinesSymbol fills the debug lines symbol of a given function.
//
// It's worth noting that this function doesn't generate the full debug_lines
// DWARF section, saving that for the linker. This function just generates the
// state machine part of debug_lines. The full table is generated by the
// linker.  Also, we use the file numbers from the full package (not just the
// function in question) when generating the state machine. We do this so we
// don't have to do a fixup on the indices when writing the full section.
func (ctxt *Link) generateDebugLinesSymbol(s, lines *LSym) {
	dctxt := dwCtxt{ctxt}

	// The Pcfile table is used to generate the debug_lines section, and the file
	// indices for that data could differ from the files we write out for the
	// debug_lines section. Here we generate a LUT between those two indices.
	fileNums := make(map[int32]int64)
	for i, filename := range s.Func.Pcln.File {
		if symbolIndex := ctxt.PosTable.FileIndex(filename); symbolIndex >= 0 {
			fileNums[int32(i)] = int64(symbolIndex) + 1
		} else {
			panic(fmt.Sprintf("First time we've seen filename: %q", filename))
		}
	}

	// Set up the debug_lines state machine.
	// NB: This state machine is reset to this state when we've finished
	// generating the line table. See below.
	// TODO: Once delve can support multiple DW_LNS_end_statements, we don't have
	// to do this.
	is_stmt := uint8(1)
	pc := s.Func.Text.Pc
	line := 1
	file := 1

	// The linker will insert the DW_LNE_set_address once determined; therefore,
	// it's omitted here.

	// Generate the actual line information.
	// We use the pcline and pcfile to generate this section, and it's suboptimal.
	// Likely better would be to generate this dirrectly from the progs and not
	// parse those tables.
	// TODO: Generate from the progs if it's faster.
	pcfile := NewPCIter(uint32(ctxt.Arch.Arch.MinLC))
	pcline := NewPCIter(uint32(ctxt.Arch.Arch.MinLC))
	pcstmt := NewPCIter(uint32(ctxt.Arch.Arch.MinLC))
	pcfile.Init(s.Func.Pcln.Pcfile.P)
	pcline.Init(s.Func.Pcln.Pcline.P)
	var pctostmtData Pcdata
	funcpctab(ctxt, &pctostmtData, s, "pctostmt", pctostmt, nil)
	pcstmt.Init(pctostmtData.P)
	var thispc uint32

	for !pcfile.Done && !pcline.Done {
		// Only changed if it advanced
		if int32(file) != pcfile.Value {
			dctxt.AddUint8(lines, dwarf.DW_LNS_set_file)
			dwarf.Uleb128put(dctxt, lines, fileNums[pcfile.Value])
			file = int(pcfile.Value)
		}

		// Only changed if it advanced
		if is_stmt != uint8(pcstmt.Value) {
			new_stmt := uint8(pcstmt.Value)
			switch new_stmt &^ 1 {
			case PrologueEnd:
				dctxt.AddUint8(lines, uint8(dwarf.DW_LNS_set_prologue_end))
			case EpilogueBegin:
				// TODO if there is a use for this, add it.
				// Don't forget to increase OPCODE_BASE by 1 and add entry for standard_opcode_lengths[11]
				panic("unsupported EpilogueBegin")
			}
			new_stmt &= 1
			if is_stmt != new_stmt {
				is_stmt = new_stmt
				dctxt.AddUint8(lines, uint8(dwarf.DW_LNS_negate_stmt))
			}
		}

		// putpcldelta makes a row in the DWARF matrix, always, even if line is unchanged.
		putpclcdelta(ctxt, dctxt, lines, uint64(s.Func.Text.Pc+int64(thispc)-pc), int64(pcline.Value)-int64(line))

		pc = s.Func.Text.Pc + int64(thispc)
		line = int(pcline.Value)

		// Take the minimum step forward for the three iterators
		thispc = pcfile.NextPC
		if pcline.NextPC < thispc {
			thispc = pcline.NextPC
		}
		if !pcstmt.Done && pcstmt.NextPC < thispc {
			thispc = pcstmt.NextPC
		}

		if pcfile.NextPC == thispc {
			pcfile.Next()
		}
		if !pcstmt.Done && pcstmt.NextPC == thispc {
			pcstmt.Next()
		}
		if pcline.NextPC == thispc {
			pcline.Next()
		}
	}

	// Because these symbols will be concatenated together by the linker, we need
	// to reset the state machine that controls the debug symbols. The fields in
	// the state machine that need to be reset are:
	//   file = 1
	//   line = 1
	//   column = 0
	//   is_stmt = set in header, we assume true
	//   basic_block = false
	// Careful readers of the DWARF specification will note that we don't reset
	// the address of the state machine -- but this will happen at the beginning
	// of the NEXT block of opcodes. (See the SetAddress call above.)
	dctxt.AddUint8(lines, dwarf.DW_LNS_set_file)
	dwarf.Uleb128put(dctxt, lines, 1)
	dctxt.AddUint8(lines, dwarf.DW_LNS_advance_line)
	dwarf.Sleb128put(dctxt, lines, int64(1-line))
	if is_stmt != 1 {
		dctxt.AddUint8(lines, dwarf.DW_LNS_negate_stmt)
	}
	dctxt.AddUint8(lines, dwarf.DW_LNS_copy)
}

func putpclcdelta(linkctxt *Link, dctxt dwCtxt, s *LSym, deltaPC uint64, deltaLC int64) {
	// Choose a special opcode that minimizes the number of bytes needed to
	// encode the remaining PC delta and LC delta.
	var opcode int64
	if deltaLC < LINE_BASE {
		if deltaPC >= PC_RANGE {
			opcode = OPCODE_BASE + (LINE_RANGE * PC_RANGE)
		} else {
			opcode = OPCODE_BASE + (LINE_RANGE * int64(deltaPC))
		}
	} else if deltaLC < LINE_BASE+LINE_RANGE {
		if deltaPC >= PC_RANGE {
			opcode = OPCODE_BASE + (deltaLC - LINE_BASE) + (LINE_RANGE * PC_RANGE)
			if opcode > 255 {
				opcode -= LINE_RANGE
			}
		} else {
			opcode = OPCODE_BASE + (deltaLC - LINE_BASE) + (LINE_RANGE * int64(deltaPC))
		}
	} else {
		if deltaPC <= PC_RANGE {
			opcode = OPCODE_BASE + (LINE_RANGE - 1) + (LINE_RANGE * int64(deltaPC))
			if opcode > 255 {
				opcode = 255
			}
		} else {
			// Use opcode 249 (pc+=23, lc+=5) or 255 (pc+=24, lc+=1).
			//
			// Let x=deltaPC-PC_RANGE.  If we use opcode 255, x will be the remaining
			// deltaPC that we need to encode separately before emitting 255.  If we
			// use opcode 249, we will need to encode x+1.  If x+1 takes one more
			// byte to encode than x, then we use opcode 255.
			//
			// In all other cases x and x+1 take the same number of bytes to encode,
			// so we use opcode 249, which may save us a byte in encoding deltaLC,
			// for similar reasons.
			switch deltaPC - PC_RANGE {
			// PC_RANGE is the largest deltaPC we can encode in one byte, using
			// DW_LNS_const_add_pc.
			//
			// (1<<16)-1 is the largest deltaPC we can encode in three bytes, using
			// DW_LNS_fixed_advance_pc.
			//
			// (1<<(7n))-1 is the largest deltaPC we can encode in n+1 bytes for
			// n=1,3,4,5,..., using DW_LNS_advance_pc.
			case PC_RANGE, (1 << 7) - 1, (1 << 16) - 1, (1 << 21) - 1, (1 << 28) - 1,
				(1 << 35) - 1, (1 << 42) - 1, (1 << 49) - 1, (1 << 56) - 1, (1 << 63) - 1:
				opcode = 255
			default:
				opcode = OPCODE_BASE + LINE_RANGE*PC_RANGE - 1 // 249
			}
		}
	}
	if opcode < OPCODE_BASE || opcode > 255 {
		panic(fmt.Sprintf("produced invalid special opcode %d", opcode))
	}

	// Subtract from deltaPC and deltaLC the amounts that the opcode will add.
	deltaPC -= uint64((opcode - OPCODE_BASE) / LINE_RANGE)
	deltaLC -= (opcode-OPCODE_BASE)%LINE_RANGE + LINE_BASE

	// Encode deltaPC.
	if deltaPC != 0 {
		if deltaPC <= PC_RANGE {
			// Adjust the opcode so that we can use the 1-byte DW_LNS_const_add_pc
			// instruction.
			opcode -= LINE_RANGE * int64(PC_RANGE-deltaPC)
			if opcode < OPCODE_BASE {
				panic(fmt.Sprintf("produced invalid special opcode %d", opcode))
			}
			dctxt.AddUint8(s, dwarf.DW_LNS_const_add_pc)
		} else if (1<<14) <= deltaPC && deltaPC < (1<<16) {
			dctxt.AddUint8(s, dwarf.DW_LNS_fixed_advance_pc)
			dctxt.AddUint16(s, uint16(deltaPC))
		} else {
			dctxt.AddUint8(s, dwarf.DW_LNS_advance_pc)
			dwarf.Uleb128put(dctxt, s, int64(deltaPC))
		}
	}

	// Encode deltaLC.
	if deltaLC != 0 {
		dctxt.AddUint8(s, dwarf.DW_LNS_advance_line)
		dwarf.Sleb128put(dctxt, s, deltaLC)
	}

	// Output the special opcode.
	dctxt.AddUint8(s, uint8(opcode))
}