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

// No testdata on Android.

//go:build !android
// +build !android

package pointer_test

// This test uses 'expectation' comments embedded within testdata/*.go
// files to specify the expected pointer analysis behaviour.
// See below for grammar.

import (
	"bytes"
	"errors"
	"fmt"
	"go/token"
	"go/types"
	"io/ioutil"
	"os"
	"path/filepath"
	"regexp"
	"strconv"
	"strings"
	"testing"
	"unsafe"

	"golang.org/x/tools/go/callgraph"
	"golang.org/x/tools/go/packages"
	"golang.org/x/tools/go/pointer"
	"golang.org/x/tools/go/ssa"
	"golang.org/x/tools/go/ssa/ssautil"
	"golang.org/x/tools/go/types/typeutil"
	"golang.org/x/tools/internal/typeparams"
)

var inputs = []string{
	"testdata/a_test.go",
	"testdata/another.go",
	"testdata/arrayreflect.go",
	"testdata/arrays.go",
	"testdata/channels.go",
	"testdata/chanreflect.go",
	"testdata/context.go",
	"testdata/conv.go",
	"testdata/extended.go",
	"testdata/finalizer.go",
	"testdata/flow.go",
	"testdata/fmtexcerpt.go",
	"testdata/func.go",
	"testdata/funcreflect.go",
	"testdata/hello.go", // NB: causes spurious failure of HVN cross-check
	"testdata/interfaces.go",
	"testdata/issue9002.go",
	"testdata/mapreflect.go",
	"testdata/maps.go",
	"testdata/panic.go",
	"testdata/recur.go",
	"testdata/reflect.go",
	"testdata/rtti.go",
	"testdata/structreflect.go",
	"testdata/structs.go",
	// "testdata/timer.go", // TODO(adonovan): fix broken assumptions about runtime timers
}

var raceEnabled = false

// Expectation grammar:
//
// @calls f -> g
//
//	A 'calls' expectation asserts that edge (f, g) appears in the
//	callgraph.  f and g are notated as per Function.String(), which
//	may contain spaces (e.g. promoted method in anon struct).
//
// @pointsto a | b | c
//
//		A 'pointsto' expectation asserts that the points-to set of its
//		operand contains exactly the set of labels {a,b,c} notated as per
//		labelString.
//
//		A 'pointsto' expectation must appear on the same line as a
//		print(x) statement; the expectation's operand is x.
//
//		If one of the strings is "...", the expectation asserts that the
//		points-to set at least the other labels.
//
//		We use '|' because label names may contain spaces, e.g.  methods
//		of anonymous structs.
//
//	 Assertions within generic functions are treated as a union of all
//	 of the instantiations.
//
//		From a theoretical perspective, concrete types in interfaces are
//		labels too, but they are represented differently and so have a
//		different expectation, @types, below.
//
// @types t | u | v
//
//		A 'types' expectation asserts that the set of possible dynamic
//		types of its interface operand is exactly {t,u,v}, notated per
//		go/types.Type.String(). In other words, it asserts that the type
//		component of the interface may point to that set of concrete type
//		literals.  It also works for reflect.Value, though the types
//		needn't be concrete in that case.
//
//		A 'types' expectation must appear on the same line as a
//		print(x) statement; the expectation's operand is x.
//
//		If one of the strings is "...", the expectation asserts that the
//		interface's type may point to at least the other types.
//
//		We use '|' because type names may contain spaces.
//
//	 Assertions within generic functions are treated as a union of all
//	 of the instantiations.
//
// @warning "regexp"
//
//	A 'warning' expectation asserts that the analysis issues a
//	warning that matches the regular expression within the string
//	literal.
//
// @line id
//
//	A line directive associates the name "id" with the current
//	file:line.  The string form of labels will use this id instead of
//	a file:line, making @pointsto expectations more robust against
//	perturbations in the source file.
//	(NB, anon functions still include line numbers.)
type expectation struct {
	kind     string // "pointsto" | "pointstoquery" | "types" | "calls" | "warning"
	filepath string
	linenum  int // source line number, 1-based
	args     []string
	query    string             // extended query
	extended []*pointer.Pointer // extended query pointer [per instantiation]
	types    []types.Type       // for types
}

func (e *expectation) String() string {
	return fmt.Sprintf("@%s[%s]", e.kind, strings.Join(e.args, " | "))
}

func (e *expectation) errorf(format string, args ...interface{}) {
	fmt.Printf("%s:%d: ", e.filepath, e.linenum)
	fmt.Printf(format, args...)
	fmt.Println()
}

func (e *expectation) needsProbe() bool {
	return e.kind == "pointsto" || e.kind == "pointstoquery" || e.kind == "types"
}

// Find probes (call to print(x)) of same source file/line as expectation.
//
// May match multiple calls for different instantiations.
func findProbes(prog *ssa.Program, probes map[*ssa.CallCommon]bool, e *expectation) []*ssa.CallCommon {
	var calls []*ssa.CallCommon
	for call := range probes {
		pos := prog.Fset.Position(call.Pos())
		if pos.Line == e.linenum && pos.Filename == e.filepath {
			// TODO(adonovan): send this to test log (display only on failure).
			// fmt.Printf("%s:%d: info: found probe for %s: %s\n",
			// 	e.filepath, e.linenum, e, p.arg0) // debugging
			calls = append(calls, call)
		}
	}
	return calls
}

// Find points to sets of probes (call to print(x)).
func probesPointTo(calls []*ssa.CallCommon, queries map[ssa.Value]pointer.Pointer) []pointer.PointsToSet {
	ptss := make([]pointer.PointsToSet, len(calls))
	for i, call := range calls {
		ptss[i] = queries[call.Args[0]].PointsTo()
	}
	return ptss
}

// Find the types of the probes (call to print(x)).
// Returns an error if type of the probe cannot point.
func probesPointToTypes(calls []*ssa.CallCommon) ([]types.Type, error) {
	tProbes := make([]types.Type, len(calls))
	for i, call := range calls {
		tProbes[i] = call.Args[0].Type()
		if !pointer.CanPoint(tProbes[i]) {
			return nil, fmt.Errorf("expectation on non-pointerlike operand: %s", tProbes[i])
		}
	}
	return tProbes, nil
}

func doOneInput(t *testing.T, input, fpath string) bool {
	cfg := &packages.Config{
		Mode:  packages.LoadAllSyntax,
		Tests: true,
	}
	pkgs, err := packages.Load(cfg, fpath)
	if err != nil {
		fmt.Println(err)
		return false
	}
	if packages.PrintErrors(pkgs) > 0 {
		fmt.Println("loaded packages have errors")
		return false
	}

	// SSA creation + building.
	mode := ssa.SanityCheckFunctions | ssa.InstantiateGenerics
	prog, ssaPkgs := ssautil.AllPackages(pkgs, mode)
	prog.Build()

	// main underlying packages.Package.
	mainPpkg := pkgs[0]
	mainpkg := ssaPkgs[0]
	ptrmain := mainpkg // main package for the pointer analysis
	if mainpkg.Func("main") == nil {
		// For test programs without main, such as testdata/a_test.go,
		// the package with the original code is "main [main.test]" and
		// the package with the main is "main.test".
		for i, pkg := range pkgs {
			if pkg.ID == mainPpkg.ID+".test" {
				ptrmain = ssaPkgs[i]
			} else if pkg.ID == fmt.Sprintf("%s [%s.test]", mainPpkg.ID, mainPpkg.ID) {
				mainpkg = ssaPkgs[i]
			}
		}
	}

	// files in mainPpkg.
	mainFiles := make(map[*token.File]bool)
	for _, syn := range mainPpkg.Syntax {
		mainFiles[prog.Fset.File(syn.Pos())] = true
	}

	// Find all calls to the built-in print(x).  Analytically,
	// print is a no-op, but it's a convenient hook for testing
	// the PTS of an expression, so our tests use it.
	// Exclude generic bodies as these should be dead code for pointer.
	// Instance of generics are included.
	probes := make(map[*ssa.CallCommon]bool)
	for fn := range ssautil.AllFunctions(prog) {
		if isGenericBody(fn) {
			continue // skip generic bodies
		}
		// TODO(taking): Switch to a more principled check like fn.declaredPackage() == mainPkg if Origin is exported.
		if fn.Pkg == mainpkg || (fn.Pkg == nil && mainFiles[prog.Fset.File(fn.Pos())]) {
			for _, b := range fn.Blocks {
				for _, instr := range b.Instrs {
					if instr, ok := instr.(ssa.CallInstruction); ok {
						call := instr.Common()
						if b, ok := call.Value.(*ssa.Builtin); ok && b.Name() == "print" && len(call.Args) == 1 {
							probes[instr.Common()] = true
						}
					}
				}
			}
		}
	}

	ok := true

	lineMapping := make(map[string]string) // maps "file:line" to @line tag

	// Parse expectations in this input.
	var exps []*expectation
	re := regexp.MustCompile("// *@([a-z]*) *(.*)$")
	lines := strings.Split(input, "\n")
	for linenum, line := range lines {
		linenum++ // make it 1-based
		if matches := re.FindAllStringSubmatch(line, -1); matches != nil {
			match := matches[0]
			kind, rest := match[1], match[2]
			e := &expectation{kind: kind, filepath: fpath, linenum: linenum}

			if kind == "line" {
				if rest == "" {
					ok = false
					e.errorf("@%s expectation requires identifier", kind)
				} else {
					lineMapping[fmt.Sprintf("%s:%d", fpath, linenum)] = rest
				}
				continue
			}

			if e.needsProbe() && !strings.Contains(line, "print(") {
				ok = false
				e.errorf("@%s expectation must follow call to print(x)", kind)
				continue
			}

			switch kind {
			case "pointsto":
				e.args = split(rest, "|")

			case "pointstoquery":
				args := strings.SplitN(rest, " ", 2)
				e.query = args[0]
				e.args = split(args[1], "|")
			case "types":
				for _, typstr := range split(rest, "|") {
					var t types.Type = types.Typ[types.Invalid] // means "..."
					if typstr != "..." {
						tv, err := types.Eval(prog.Fset, mainpkg.Pkg, mainPpkg.Syntax[0].Pos(), typstr)
						if err != nil {
							ok = false
							// Don't print err since its location is bad.
							e.errorf("'%s' is not a valid type: %s", typstr, err)
							continue
						}
						t = tv.Type
					}
					e.types = append(e.types, t)
				}

			case "calls":
				e.args = split(rest, "->")
				// TODO(adonovan): eagerly reject the
				// expectation if fn doesn't denote
				// existing function, rather than fail
				// the expectation after analysis.
				if len(e.args) != 2 {
					ok = false
					e.errorf("@calls expectation wants 'caller -> callee' arguments")
					continue
				}

			case "warning":
				lit, err := strconv.Unquote(strings.TrimSpace(rest))
				if err != nil {
					ok = false
					e.errorf("couldn't parse @warning operand: %s", err.Error())
					continue
				}
				e.args = append(e.args, lit)

			default:
				ok = false
				e.errorf("unknown expectation kind: %s", e)
				continue
			}
			exps = append(exps, e)
		}
	}

	var log bytes.Buffer
	fmt.Fprintf(&log, "Input: %s\n", fpath)

	// Run the analysis.
	config := &pointer.Config{
		Reflection:     true,
		BuildCallGraph: true,
		Mains:          []*ssa.Package{ptrmain},
		Log:            &log,
	}
	for probe := range probes {
		v := probe.Args[0]
		pos := prog.Fset.Position(probe.Pos())
		for _, e := range exps {
			if e.linenum == pos.Line && e.filepath == pos.Filename && e.kind == "pointstoquery" {
				extended, err := config.AddExtendedQuery(v, e.query)
				if err != nil {
					panic(err)
				}
				e.extended = append(e.extended, extended)
			}
		}
		if pointer.CanPoint(v.Type()) {
			config.AddQuery(v)
		}
	}

	// Print the log is there was an error or a panic.
	complete := false
	defer func() {
		if !complete || !ok {
			log.WriteTo(os.Stderr)
		}
	}()

	result, err := pointer.Analyze(config)
	if err != nil {
		panic(err) // internal error in pointer analysis
	}

	// Check the expectations.
	for _, e := range exps {
		var tProbes []types.Type
		var calls []*ssa.CallCommon
		var ptss []pointer.PointsToSet
		if e.needsProbe() {
			calls = findProbes(prog, probes, e)
			if len(calls) == 0 {
				ok = false
				e.errorf("unreachable print() statement has expectation %s", e)
				continue
			}
			if e.extended == nil {
				ptss = probesPointTo(calls, result.Queries)
			} else {
				ptss = make([]pointer.PointsToSet, len(e.extended))
				for i, p := range e.extended {
					ptss[i] = p.PointsTo()
				}
			}

			var err error
			tProbes, err = probesPointToTypes(calls)
			if err != nil {
				ok = false
				e.errorf(err.Error())
				continue
			}
		}

		switch e.kind {
		case "pointsto", "pointstoquery":
			if !checkPointsToExpectation(e, ptss, lineMapping, prog) {
				ok = false
			}

		case "types":
			if !checkTypesExpectation(e, ptss, tProbes) {
				ok = false
			}

		case "calls":
			if !checkCallsExpectation(prog, e, result.CallGraph) {
				ok = false
			}

		case "warning":
			if !checkWarningExpectation(prog, e, result.Warnings) {
				ok = false
			}
		}
	}

	complete = true

	// ok = false // debugging: uncomment to always see log

	return ok
}

func labelString(l *pointer.Label, lineMapping map[string]string, prog *ssa.Program) string {
	// Functions and Globals need no pos suffix,
	// nor do allocations in intrinsic operations
	// (for which we'll print the function name).
	switch l.Value().(type) {
	case nil, *ssa.Function, *ssa.Global:
		return l.String()
	}

	str := l.String()
	if pos := l.Pos(); pos != token.NoPos {
		// Append the position, using a @line tag instead of a line number, if defined.
		posn := prog.Fset.Position(pos)
		s := fmt.Sprintf("%s:%d", posn.Filename, posn.Line)
		if tag, ok := lineMapping[s]; ok {
			return fmt.Sprintf("%s@%s:%d", str, tag, posn.Column)
		}
		str = fmt.Sprintf("%s@%s", str, posn)
	}
	return str
}

func checkPointsToExpectation(e *expectation, ptss []pointer.PointsToSet, lineMapping map[string]string, prog *ssa.Program) bool {
	expected := make(map[string]int)
	surplus := make(map[string]int)
	exact := true
	for _, g := range e.args {
		if g == "..." {
			exact = false
			continue
		}
		expected[g]++
	}
	// Find the set of labels that the probe's
	// argument (x in print(x)) may point to.
	for _, pts := range ptss { // treat ptss as union of points-to sets.
		for _, label := range pts.Labels() {
			name := labelString(label, lineMapping, prog)
			if expected[name] > 0 {
				expected[name]--
			} else if exact {
				surplus[name]++
			}
		}
	}
	// Report multiset difference:
	ok := true
	for _, count := range expected {
		if count > 0 {
			ok = false
			e.errorf("value does not alias these expected labels: %s", join(expected))
			break
		}
	}
	for _, count := range surplus {
		if count > 0 {
			ok = false
			e.errorf("value may additionally alias these labels: %s", join(surplus))
			break
		}
	}
	return ok
}

func checkTypesExpectation(e *expectation, ptss []pointer.PointsToSet, typs []types.Type) bool {
	var expected typeutil.Map
	var surplus typeutil.Map
	exact := true
	for _, g := range e.types {
		if g == types.Typ[types.Invalid] {
			exact = false
			continue
		}
		expected.Set(g, struct{}{})
	}

	if len(typs) != len(ptss) {
		e.errorf("@types expectation internal error differing number of types(%d) and points to sets (%d)", len(typs), len(ptss))
		return false
	}

	// Find the set of types that the probe's
	// argument (x in print(x)) may contain.
	for i := range ptss {
		var Ts []types.Type
		if pointer.CanHaveDynamicTypes(typs[i]) {
			Ts = ptss[i].DynamicTypes().Keys()
		} else {
			Ts = append(Ts, typs[i]) // static type
		}
		for _, T := range Ts {
			if expected.At(T) != nil {
				expected.Delete(T)
			} else if exact {
				surplus.Set(T, struct{}{})
			}
		}
	}
	// Report set difference:
	ok := true
	if expected.Len() > 0 {
		ok = false
		e.errorf("interface cannot contain these types: %s", expected.KeysString())
	}
	if surplus.Len() > 0 {
		ok = false
		e.errorf("interface may additionally contain these types: %s", surplus.KeysString())
	}
	return ok
}

var errOK = errors.New("OK")

func checkCallsExpectation(prog *ssa.Program, e *expectation, cg *callgraph.Graph) bool {
	found := make(map[string]int)
	err := callgraph.GraphVisitEdges(cg, func(edge *callgraph.Edge) error {
		// Name-based matching is inefficient but it allows us to
		// match functions whose names that would not appear in an
		// index ("<root>") or which are not unique ("func@1.2").
		if edge.Caller.Func.String() == e.args[0] {
			calleeStr := edge.Callee.Func.String()
			if calleeStr == e.args[1] {
				return errOK // expectation satisfied; stop the search
			}
			found[calleeStr]++
		}
		return nil
	})
	if err == errOK {
		return true
	}
	if len(found) == 0 {
		e.errorf("didn't find any calls from %s", e.args[0])
	}
	e.errorf("found no call from %s to %s, but only to %s",
		e.args[0], e.args[1], join(found))
	return false
}

func checkWarningExpectation(prog *ssa.Program, e *expectation, warnings []pointer.Warning) bool {
	// TODO(adonovan): check the position part of the warning too?
	re, err := regexp.Compile(e.args[0])
	if err != nil {
		e.errorf("invalid regular expression in @warning expectation: %s", err.Error())
		return false
	}

	if len(warnings) == 0 {
		e.errorf("@warning %q expectation, but no warnings", e.args[0])
		return false
	}

	for _, w := range warnings {
		if re.MatchString(w.Message) {
			return true
		}
	}

	e.errorf("@warning %q expectation not satisfied; found these warnings though:", e.args[0])
	for _, w := range warnings {
		fmt.Printf("%s: warning: %s\n", prog.Fset.Position(w.Pos), w.Message)
	}
	return false
}

func TestInput(t *testing.T) {
	if testing.Short() {
		t.Skip("skipping in short mode; this test requires tons of memory; https://golang.org/issue/14113")
	}

	wd, err := os.Getwd()
	if err != nil {
		t.Errorf("os.Getwd: %s", err)
		return
	}

	// 'go test' does a chdir so that relative paths in
	// diagnostics no longer make sense relative to the invoking
	// shell's cwd.  We print a special marker so that Emacs can
	// make sense of them.
	fmt.Fprintf(os.Stderr, "Entering directory `%s'\n", wd)

	for _, filename := range inputs {
		filename := filename
		t.Run(filename, func(t *testing.T) {
			if filename == "testdata/a_test.go" {
				// For some reason this particular file is way more expensive than the others.
				if unsafe.Sizeof(unsafe.Pointer(nil)) <= 4 {
					t.Skip("skipping memory-intensive test on platform with small address space; https://golang.org/issue/14113")
				}
				if raceEnabled {
					t.Skip("skipping memory-intensive test under race detector; https://golang.org/issue/14113")
				}
			} else {
				t.Parallel()
			}

			content, err := ioutil.ReadFile(filename)
			if err != nil {
				t.Fatalf("couldn't read file '%s': %s", filename, err)
			}

			fpath, err := filepath.Abs(filename)
			if err != nil {
				t.Fatalf("couldn't get absolute path for '%s': %s", filename, err)
			}

			if !doOneInput(t, string(content), fpath) {
				t.Fail()
			}
		})
	}
}

// isGenericBody returns true if fn is the body of a generic function.
func isGenericBody(fn *ssa.Function) bool {
	sig := fn.Signature
	if typeparams.ForSignature(sig).Len() > 0 || typeparams.RecvTypeParams(sig).Len() > 0 {
		return fn.Synthetic == ""
	}
	return false
}

// join joins the elements of multiset with " | "s.
func join(set map[string]int) string {
	var buf bytes.Buffer
	sep := ""
	for name, count := range set {
		for i := 0; i < count; i++ {
			buf.WriteString(sep)
			sep = " | "
			buf.WriteString(name)
		}
	}
	return buf.String()
}

// split returns the list of sep-delimited non-empty strings in s.
func split(s, sep string) (r []string) {
	for _, elem := range strings.Split(s, sep) {
		elem = strings.TrimSpace(elem)
		if elem != "" {
			r = append(r, elem)
		}
	}
	return
}

func TestTypeParam(t *testing.T) {
	if !typeparams.Enabled {
		t.Skip("TestTypeParamInput requires type parameters")
	}
	// Based on TestInput. Keep this up to date with that.
	filename := "testdata/typeparams.go"

	if testing.Short() {
		t.Skip("skipping in short mode; this test requires tons of memory; https://golang.org/issue/14113")
	}

	wd, err := os.Getwd()
	if err != nil {
		t.Fatalf("os.Getwd: %s", err)
	}
	fmt.Fprintf(os.Stderr, "Entering directory `%s'\n", wd)

	content, err := ioutil.ReadFile(filename)
	if err != nil {
		t.Fatalf("couldn't read file '%s': %s", filename, err)
	}
	fpath, err := filepath.Abs(filename)
	if err != nil {
		t.Errorf("couldn't get absolute path for '%s': %s", filename, err)
	}

	if !doOneInput(t, string(content), fpath) {
		t.Fail()
	}
}