package pkgpath

import (
	"fmt"
	"runtime"
	"strings"
)

func findMainInit() (string, error) {
	// When using gc version go1.4.1:
	//
	// skip = 0 gives us this func, ending with something like
	// "pkgpath.init·1".
	//
	// skip = 1 gives us this package's primary init func, which calls the
	// individual "func init" bodies.
	//
	// Larger skip values take us up the import chain, eventually leading to
	// package main's primary init func, which calls the primary init funcs of
	// its imported packages.  Its name is "main.init".

	var basePC uintptr
	for i := 0; ; i++ {
		var stack [1]uintptr
		// https://github.com/golang/go/issues/23128#issuecomment-352128725
		// > If you're willing to try more implementation-dependent tricks, I
		// > believe it should still work to call runtime.Callers and then
		// > iterate over the returned PCs manually
		n := runtime.Callers(i, stack[:])
		if n == 0 {
			// Somehow we've gone too far without finding "main.init". Give up
			// without setting the program name.
			break
		}
		pc := stack[0]
		if basePC == 0 {
			basePC = pc
		}
		if runtime.FuncForPC(pc).Name() != "main.init" {
			continue
		}

		filename, ok := findPackageMainFile(pc, basePC)
		if ok {
			return filename, nil
		}
	}

	return "", fmt.Errorf("could not find main package on stack")
}

// findPackageMainFile searches through the executable for a filename
// corresponding to package main. The search begins at the startPC address. It
// progresses towards mainPC which is known to be within package main, but
// which might not have valid file/line info. The function returns the name of
// a file within package main, and whether it was able to find such a file.
func findPackageMainFile(mainPC, startPC uintptr) (string, bool) {
	// We assume that the linker puts all of the code for each package
	// in a contiguous block.
	//
	// We assume that the linker writes out packages in dependency
	// order, so the code for package "main" will be far away from the
	// code for package "runtime".
	//
	// We assume that there's code for package "main" that includes
	// valid file/line info.
	//
	// We assume that code for non-synthesized files is adjacent to
	// the code for the compiler-synthesized "main.init" function, and
	// that it lies between code for "main.init" and code for the
	// other packages.
	//
	// These assumptions hold for go1.4.3, go1.6.4, go1.7.6, go1.8.3,
	// go1.9, and go1.10beta1.

	near, far := mainPC, startPC
	for {
		fn := runtime.FuncForPC(far)

		inMain := inPackageMain(fn)
		haveFile := validFile(fn)

		if inMain && haveFile {
			filename, _ := fn.FileLine(fn.Entry())
			return filename, true
		}

		probe := midpoint(near, far)
		if probe == near || probe == far {
			// we're not making progress
			return "", false
		}

		if !inMain {
			far = probe
		} else {
			near = probe
		}
	}
}

func inPackageMain(fn *runtime.Func) bool {
	if fn == nil {
		return false
	}
	return strings.HasPrefix(fn.Name(), "main.")
}

func validFile(fn *runtime.Func) bool {
	if fn == nil {
		return false
	}
	file, _ := fn.FileLine(fn.Entry())
	return validFilename(file)
}

func validFilename(file string) bool {
	return strings.Contains(file, ".")
}

func midpoint(a, b uintptr) uintptr {
	if a > b {
		a, b = b, a
	}
	return a + (b-a)/2
}
