package runtime

import (
	"runtime/internal/atomic"
	"runtime/internal/sys"
	"unsafe"
)

	callers []uintptr

	frames     []Frame
	frameStore [2]Frame
}

	PC uintptr

	Func *Func

	Function string

	File string
	Line int

	Entry uintptr

	funcInfo funcInfo
}

func CallersFrames(callers []uintptr) *Frames {
	f := &Frames{callers: callers}
	f.frames = f.frameStore[:0]
	return f
}

func (ci *Frames) Next() (frame Frame, more bool) {

		if len(ci.callers) == 0 {
			break
		}
		pc := ci.callers[0]
		ci.callers = ci.callers[1:]
		funcInfo := findfunc(pc)
		if !funcInfo.valid() {

				ci.frames = append(ci.frames, expandCgoFrames(pc)...)
			}
			continue
		}
		f := funcInfo._Func()
		entry := f.Entry()

			pc--
		}
		name := funcname(funcInfo)
		if inldata := funcdata(funcInfo, _FUNCDATA_InlTree); inldata != nil {

			ix := pcdatavalue1(funcInfo, _PCDATA_InlTreeIndex, pc, nil, false)

				f = nil

			}
		}
		ci.frames = append(ci.frames, Frame{
			PC:       pc,
			Func:     f,
			Function: name,
			Entry:    entry,

		})
	}

	switch len(ci.frames) {
	case 0: // In the rare case when there are no frames at all, we return Frame{}.
		return
	case 1:
		frame = ci.frames[0]
		ci.frames = ci.frameStore[:0]
	case 2:
		frame = ci.frames[0]
		ci.frameStore[0] = ci.frames[1]
		ci.frames = ci.frameStore[:1]
	default:
		frame = ci.frames[0]
		ci.frames = ci.frames[1:]
	}
	more = len(ci.frames) > 0

		file, line := funcline1(frame.funcInfo, frame.PC, false)
		frame.File, frame.Line = file, int(line)
	}
	return
}

func runtime_expandFinalInlineFrame(stk []uintptr) []uintptr {
	if len(stk) == 0 {
		return stk
	}
	pc := stk[len(stk)-1]
	tracepc := pc - 1

	f := findfunc(tracepc)

		return stk
	}

	inldata := funcdata(f, _FUNCDATA_InlTree)

		return stk
	}

	lastFuncID := funcID_normal

	stk = stk[:len(stk)-1]

	var cache pcvalueCache
	inltree := (*[1 << 20]inlinedCall)(inldata)
	for {
		ix := pcdatavalue(f, _PCDATA_InlTreeIndex, tracepc, &cache)
		if ix < 0 {
			break
		}

		} else {
			stk = append(stk, pc)
		}

		tracepc = f.entry + uintptr(inltree[ix].parentPc)
		pc = tracepc + 1
	}

	stk = append(stk, pc)

	return stk
}

func expandCgoFrames(pc uintptr) []Frame {
	arg := cgoSymbolizerArg{pc: pc}
	callCgoSymbolizer(&arg)

		return nil
	}

	var frames []Frame
	for {
		frames = append(frames, Frame{
			PC:       pc,
			Func:     nil,
			Function: gostring(arg.funcName),
			File:     gostring(arg.file),
			Line:     int(arg.lineno),

		})
		if arg.more == 0 {
			break
		}
		callCgoSymbolizer(&arg)
	}

	arg.pc = 0
	callCgoSymbolizer(&arg)

	return frames
}

type Func struct {
	opaque struct{} // unexported field to disallow conversions
}

func (f *Func) raw() *_func {
	return (*_func)(unsafe.Pointer(f))
}

func (f *Func) funcInfo() funcInfo {
	fn := f.raw()
	return funcInfo{fn, findmoduledatap(fn.entry)}
}

const (
	_PCDATA_UnsafePoint   = 0
	_PCDATA_StackMapIndex = 1
	_PCDATA_InlTreeIndex  = 2

	_FUNCDATA_ArgsPointerMaps    = 0
	_FUNCDATA_LocalsPointerMaps  = 1
	_FUNCDATA_StackObjects       = 2
	_FUNCDATA_InlTree            = 3
	_FUNCDATA_OpenCodedDeferInfo = 4

	_ArgsSizeUnknown = -0x80000000
)

	_PCDATA_UnsafePointSafe   = -1 // Safe for async preemption
	_PCDATA_UnsafePointUnsafe = -2 // Unsafe for async preemption

	_PCDATA_Restart1 = -3
	_PCDATA_Restart2 = -4

	_PCDATA_RestartAtEntry = -5
)

type funcID uint8

const (
	funcID_normal funcID = iota // not a special function
	funcID_runtime_main
	funcID_goexit
	funcID_jmpdefer
	funcID_mcall
	funcID_morestack
	funcID_mstart
	funcID_rt0_go
	funcID_asmcgocall
	funcID_sigpanic
	funcID_runfinq
	funcID_gcBgMarkWorker
	funcID_systemstack_switch
	funcID_systemstack
	funcID_cgocallback
	funcID_gogo
	funcID_externalthreadhandler
	funcID_debugCallV1
	funcID_gopanic
	funcID_panicwrap
	funcID_handleAsyncEvent
	funcID_asyncPreempt
	funcID_wrapper // any autogenerated code (hash/eq algorithms, method wrappers, etc.)
)

type pcHeader struct {
	magic          uint32  // 0xFFFFFFFA
	pad1, pad2     uint8   // 0,0
	minLC          uint8   // min instruction size
	ptrSize        uint8   // size of a ptr in bytes
	nfunc          int     // number of functions in the module
	nfiles         uint    // number of entries in the file tab.
	funcnameOffset uintptr // offset to the funcnametab variable from pcHeader
	cuOffset       uintptr // offset to the cutab variable from pcHeader
	filetabOffset  uintptr // offset to the filetab variable from pcHeader
	pctabOffset    uintptr // offset to the pctab varible from pcHeader
	pclnOffset     uintptr // offset to the pclntab variable from pcHeader
}

type moduledata struct {
	pcHeader     *pcHeader
	funcnametab  []byte
	cutab        []uint32
	filetab      []byte
	pctab        []byte
	pclntable    []byte
	ftab         []functab
	findfunctab  uintptr
	minpc, maxpc uintptr

	text, etext           uintptr
	noptrdata, enoptrdata uintptr
	data, edata           uintptr
	bss, ebss             uintptr
	noptrbss, enoptrbss   uintptr
	end, gcdata, gcbss    uintptr
	types, etypes         uintptr

	textsectmap []textsect
	typelinks   []int32 // offsets from types
	itablinks   []*itab

	ptab []ptabEntry

	pluginpath string
	pkghashes  []modulehash

	modulename   string
	modulehashes []modulehash

	hasmain uint8 // 1 if module contains the main function, 0 otherwise

	gcdatamask, gcbssmask bitvector

	typemap map[typeOff]*_type // offset to *_rtype in previous module

	bad bool // module failed to load and should be ignored

	next *moduledata
}

type modulehash struct {
	modulename   string
	linktimehash string
	runtimehash  *string
}

var pinnedTypemaps []map[typeOff]*_type

var firstmoduledata moduledata  // linker symbol
var lastmoduledatap *moduledata // linker symbol
var modulesSlice *[]*moduledata // see activeModules

func activeModules() []*moduledata {
	p := (*[]*moduledata)(atomic.Loadp(unsafe.Pointer(&modulesSlice)))
	if p == nil {
		return nil
	}
	return *p
}

func modulesinit() {
	modules := new([]*moduledata)
	for md := &firstmoduledata; md != nil; md = md.next {
		if md.bad {
			continue
		}
		*modules = append(*modules, md)
		if md.gcdatamask == (bitvector{}) {
			md.gcdatamask = progToPointerMask((*byte)(unsafe.Pointer(md.gcdata)), md.edata-md.data)
			md.gcbssmask = progToPointerMask((*byte)(unsafe.Pointer(md.gcbss)), md.ebss-md.bss)
		}
	}

	for i, md := range *modules {
		if md.hasmain != 0 {
			(*modules)[0] = md
			(*modules)[i] = &firstmoduledata
			break
		}
	}

	atomicstorep(unsafe.Pointer(&modulesSlice), unsafe.Pointer(modules))
}

type functab struct {
	entry   uintptr
	funcoff uintptr
}

type textsect struct {
	vaddr    uintptr // prelinked section vaddr
	length   uintptr // section length
	baseaddr uintptr // relocated section address
}

const minfunc = 16                 // minimum function size
const pcbucketsize = 256 * minfunc // size of bucket in the pc->func lookup table

type findfuncbucket struct {
	idx        uint32
	subbuckets [16]byte
}

func moduledataverify() {
	for datap := &firstmoduledata; datap != nil; datap = datap.next {
		moduledataverify1(datap)
	}
}

const debugPcln = false

	hdr := datap.pcHeader
	if hdr.magic != 0xfffffffa || hdr.pad1 != 0 || hdr.pad2 != 0 || hdr.minLC != sys.PCQuantum || hdr.ptrSize != sys.PtrSize {
		println("runtime: function symbol table header:", hex(hdr.magic), hex(hdr.pad1), hex(hdr.pad2), hex(hdr.minLC), hex(hdr.ptrSize))
		throw("invalid function symbol table\n")
	}

	nftab := len(datap.ftab) - 1

		if datap.ftab[i].entry > datap.ftab[i+1].entry {
			f1 := funcInfo{(*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[i].funcoff])), datap}
			f2 := funcInfo{(*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[i+1].funcoff])), datap}
			f2name := "end"
			if i+1 < nftab {
				f2name = funcname(f2)
			}
			println("function symbol table not sorted by program counter:", hex(datap.ftab[i].entry), funcname(f1), ">", hex(datap.ftab[i+1].entry), f2name)
			for j := 0; j <= i; j++ {
				print("\t", hex(datap.ftab[j].entry), " ", funcname(funcInfo{(*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[j].funcoff])), datap}), "\n")
			}
			if GOOS == "aix" && isarchive {
				println("-Wl,-bnoobjreorder is mandatory on aix/ppc64 with c-archive")
			}
			throw("invalid runtime symbol table")
		}
	}

	if datap.minpc != datap.ftab[0].entry ||
		datap.maxpc != datap.ftab[nftab].entry {
		throw("minpc or maxpc invalid")
	}

	for _, modulehash := range datap.modulehashes {
		if modulehash.linktimehash != *modulehash.runtimehash {
			println("abi mismatch detected between", datap.modulename, "and", modulehash.modulename)
			throw("abi mismatch")
		}
	}
}

func FuncForPC(pc uintptr) *Func {
	f := findfunc(pc)
	if !f.valid() {
		return nil
	}

		if ix := pcdatavalue1(f, _PCDATA_InlTreeIndex, pc, nil, false); ix >= 0 {
			inltree := (*[1 << 20]inlinedCall)(inldata)
			name := funcnameFromNameoff(f, inltree[ix].func_)
			file, line := funcline(f, pc)
			fi := &funcinl{
				entry: f.entry, // entry of the real (the outermost) function.
				name:  name,
				file:  file,
				line:  int(line),
			}
			return (*Func)(unsafe.Pointer(fi))
		}
	}
	return f._Func()
}

func (f *Func) Name() string {
	if f == nil {
		return ""
	}
	fn := f.raw()
	if fn.entry == 0 { // inlined version
		fi := (*funcinl)(unsafe.Pointer(fn))
		return fi.name
	}
	return funcname(f.funcInfo())
}

func (f *Func) Entry() uintptr {
	fn := f.raw()
	if fn.entry == 0 { // inlined version
		fi := (*funcinl)(unsafe.Pointer(fn))
		return fi.entry
	}
	return fn.entry
}

func (f *Func) FileLine(pc uintptr) (file string, line int) {
	fn := f.raw()
	if fn.entry == 0 { // inlined version
		fi := (*funcinl)(unsafe.Pointer(fn))
		return fi.file, fi.line

	file, line32 := funcline1(f.funcInfo(), pc, false)
	return file, int(line32)
}

func findmoduledatap(pc uintptr) *moduledata {
	for datap := &firstmoduledata; datap != nil; datap = datap.next {
		if datap.minpc <= pc && pc < datap.maxpc {
			return datap
		}
	}
	return nil
}

type funcInfo struct {
	*_func
	datap *moduledata
}

func (f funcInfo) valid() bool {
	return f._func != nil
}

func (f funcInfo) _Func() *Func {
	return (*Func)(unsafe.Pointer(f._func))
}

func findfunc(pc uintptr) funcInfo {
	datap := findmoduledatap(pc)
	if datap == nil {
		return funcInfo{}
	}
	const nsub = uintptr(len(findfuncbucket{}.subbuckets))

	x := pc - datap.minpc
	b := x / pcbucketsize
	i := x % pcbucketsize / (pcbucketsize / nsub)

	ffb := (*findfuncbucket)(add(unsafe.Pointer(datap.findfunctab), b*unsafe.Sizeof(findfuncbucket{})))
	idx := ffb.idx + uint32(ffb.subbuckets[i])

	if idx >= uint32(len(datap.ftab)) {
		idx = uint32(len(datap.ftab) - 1)
	}

		for datap.ftab[idx].entry > pc && idx > 0 {
			idx--
		}
		if idx == 0 {
			throw("findfunc: bad findfunctab entry idx")
		}

		for datap.ftab[idx+1].entry <= pc {
			idx++
		}
	}
	funcoff := datap.ftab[idx].funcoff

		return funcInfo{}
	}
	return funcInfo{(*_func)(unsafe.Pointer(&datap.pclntable[funcoff])), datap}
}

type pcvalueCache struct {
	entries [2][8]pcvalueCacheEnt
}

	targetpc uintptr

	val int32
}

func pcvalueCacheKey(targetpc uintptr) uintptr {
	return (targetpc / sys.PtrSize) % uintptr(len(pcvalueCache{}.entries))
}

func pcvalue(f funcInfo, off uint32, targetpc uintptr, cache *pcvalueCache, strict bool) (int32, uintptr) {
	if off == 0 {
		return -1, 0
	}

	if cache != nil {
		x := pcvalueCacheKey(targetpc)

			ent := &cache.entries[x][i]
			if ent.off == off && ent.targetpc == targetpc {
				return ent.val, 0
			}
		}
	}

	if !f.valid() {
		if strict && panicking == 0 {
			print("runtime: no module data for ", hex(f.entry), "\n")
			throw("no module data")
		}
		return -1, 0
	}
	datap := f.datap
	p := datap.pctab[off:]
	pc := f.entry
	prevpc := pc
	val := int32(-1)
	for {
		var ok bool
		p, ok = step(p, &pc, &val, pc == f.entry)
		if !ok {
			break
		}

			if cache != nil {
				x := pcvalueCacheKey(targetpc)
				e := &cache.entries[x]
				ci := fastrand() % uint32(len(cache.entries[x]))
				e[ci] = e[0]
				e[0] = pcvalueCacheEnt{
					targetpc: targetpc,
					off:      off,
					val:      val,
				}
			}

			return val, prevpc
		}
		prevpc = pc
	}

	if panicking != 0 || !strict {
		return -1, 0
	}

	print("runtime: invalid pc-encoded table f=", funcname(f), " pc=", hex(pc), " targetpc=", hex(targetpc), " tab=", p, "\n")

	p = datap.pctab[off:]
	pc = f.entry
	val = -1
	for {
		var ok bool
		p, ok = step(p, &pc, &val, pc == f.entry)
		if !ok {
			break
		}
		print("\tvalue=", val, " until pc=", hex(pc), "\n")
	}

	throw("invalid runtime symbol table")
	return -1, 0
}

func cfuncname(f funcInfo) *byte {
	if !f.valid() || f.nameoff == 0 {
		return nil
	}
	return &f.datap.funcnametab[f.nameoff]
}

func funcname(f funcInfo) string {
	return gostringnocopy(cfuncname(f))
}

func funcpkgpath(f funcInfo) string {
	name := funcname(f)
	i := len(name) - 1
	for ; i > 0; i-- {
		if name[i] == '/' {
			break
		}
	}
	for ; i < len(name); i++ {
		if name[i] == '.' {
			break
		}
	}
	return name[:i]
}

func cfuncnameFromNameoff(f funcInfo, nameoff int32) *byte {
	if !f.valid() {
		return nil
	}
	return &f.datap.funcnametab[nameoff]
}

func funcnameFromNameoff(f funcInfo, nameoff int32) string {
	return gostringnocopy(cfuncnameFromNameoff(f, nameoff))
}

func funcfile(f funcInfo, fileno int32) string {
	datap := f.datap
	if !f.valid() {
		return "?"

	if fileoff := datap.cutab[f.cuOffset+uint32(fileno)]; fileoff != ^uint32(0) {
		return gostringnocopy(&datap.filetab[fileoff])

	return "?"
}

func funcline1(f funcInfo, targetpc uintptr, strict bool) (file string, line int32) {
	datap := f.datap
	if !f.valid() {
		return "?", 0
	}
	fileno, _ := pcvalue(f, f.pcfile, targetpc, nil, strict)
	line, _ = pcvalue(f, f.pcln, targetpc, nil, strict)

		return "?", 0
	}
	file = funcfile(f, fileno)
	return
}

func funcline(f funcInfo, targetpc uintptr) (file string, line int32) {
	return funcline1(f, targetpc, true)
}

func funcspdelta(f funcInfo, targetpc uintptr, cache *pcvalueCache) int32 {
	x, _ := pcvalue(f, f.pcsp, targetpc, cache, true)
	if x&(sys.PtrSize-1) != 0 {
		print("invalid spdelta ", funcname(f), " ", hex(f.entry), " ", hex(targetpc), " ", hex(f.pcsp), " ", x, "\n")
	}
	return x
}

func funcMaxSPDelta(f funcInfo) int32 {
	datap := f.datap
	p := datap.pctab[f.pcsp:]
	pc := f.entry
	val := int32(-1)
	max := int32(0)
	for {
		var ok bool
		p, ok = step(p, &pc, &val, pc == f.entry)
		if !ok {
			return max
		}
		if val > max {
			max = val
		}
	}
}

func pcdatastart(f funcInfo, table uint32) uint32 {
	return *(*uint32)(add(unsafe.Pointer(&f.nfuncdata), unsafe.Sizeof(f.nfuncdata)+uintptr(table)*4))
}

func pcdatavalue(f funcInfo, table uint32, targetpc uintptr, cache *pcvalueCache) int32 {
	if table >= f.npcdata {
		return -1
	}
	r, _ := pcvalue(f, pcdatastart(f, table), targetpc, cache, true)
	return r
}

func pcdatavalue1(f funcInfo, table uint32, targetpc uintptr, cache *pcvalueCache, strict bool) int32 {
	if table >= f.npcdata {
		return -1
	}
	r, _ := pcvalue(f, pcdatastart(f, table), targetpc, cache, strict)
	return r
}

func pcdatavalue2(f funcInfo, table uint32, targetpc uintptr) (int32, uintptr) {
	if table >= f.npcdata {
		return -1, 0
	}
	return pcvalue(f, pcdatastart(f, table), targetpc, nil, true)
}

func funcdata(f funcInfo, i uint8) unsafe.Pointer {
	if i < 0 || i >= f.nfuncdata {
		return nil
	}
	p := add(unsafe.Pointer(&f.nfuncdata), unsafe.Sizeof(f.nfuncdata)+uintptr(f.npcdata)*4)
	if sys.PtrSize == 8 && uintptr(p)&4 != 0 {
		if uintptr(unsafe.Pointer(f._func))&4 != 0 {
			println("runtime: misaligned func", f._func)
		}
		p = add(p, 4)
	}
	return *(*unsafe.Pointer)(add(p, uintptr(i)*sys.PtrSize))
}

	uvdelta := uint32(p[0])
	if uvdelta == 0 && !first {
		return nil, false
	}
	n := uint32(1)
	if uvdelta&0x80 != 0 {
		n, uvdelta = readvarint(p)
	}
	*val += int32(-(uvdelta & 1) ^ (uvdelta >> 1))
	p = p[n:]

	pcdelta := uint32(p[0])
	n = 1
	if pcdelta&0x80 != 0 {
		n, pcdelta = readvarint(p)
	}
	p = p[n:]
	*pc += uintptr(pcdelta * sys.PCQuantum)
	return p, true
}

func readvarint(p []byte) (read uint32, val uint32) {
	var v, shift, n uint32
	for {
		b := p[n]
		n++
		v |= uint32(b&0x7F) << (shift & 31)
		if b&0x80 == 0 {
			break
		}
		shift += 7
	}
	return n, v
}

type stackmap struct {
	n        int32   // number of bitmaps
	nbit     int32   // number of bits in each bitmap
	bytedata [1]byte // bitmaps, each starting on a byte boundary
}

	if stackDebug > 0 && (n < 0 || n >= stkmap.n) {
		throw("stackmapdata: index out of range")
	}
	return bitvector{stkmap.nbit, addb(&stkmap.bytedata[0], uintptr(n*((stkmap.nbit+7)>>3)))}
}

type inlinedCall struct {
	parent   int16  // index of parent in the inltree, or < 0
	funcID   funcID // type of the called function
	_        byte
	file     int32 // perCU file index for inlined call. See cmd/link:pcln.go
	line     int32 // line number of the call site
	func_    int32 // offset into pclntab for name of called function
	parentPc int32 // position of an instruction whose source position is the call site (offset from entry)