// fastQueryPos parses the position string and returns a queryPos.
// It parses only a single file and does not run the type checker.
func fastQueryPos(ctxt *build.Context, pos string) (*queryPos, error) {
	filename, startOffset, endOffset, err := parsePos(pos)
	if err != nil {
		return nil, err
	}

	// Parse the file, opening it the file via the build.Context
	// so that we observe the effects of the -modified flag.
	fset := token.NewFileSet()
	cwd, _ := os.Getwd()
	f, err := buildutil.ParseFile(fset, ctxt, nil, cwd, filename, parser.Mode(0))
	// ParseFile usually returns a partial file along with an error.
	// Only fail if there is no file.
	if f == nil {
		return nil, err
	}
	if !f.Pos().IsValid() {
		return nil, fmt.Errorf("%s is not a Go source file", filename)
	}

	start, end, err := fileOffsetToPos(fset.File(f.Pos()), startOffset, endOffset)
	if err != nil {
		return nil, err
	}

	path, exact := astutil.PathEnclosingInterval(f, start, end)
	if path == nil {
		return nil, fmt.Errorf("no syntax here")
	}

	return &queryPos{fset, start, end, path, exact, nil}, nil
}

// fastQueryPos parses the position string and returns a queryPos.
// It parses only a single file and does not run the type checker.
func fastQueryPos(pos string) (*queryPos, error) {
	filename, startOffset, endOffset, err := parsePos(pos)
	if err != nil {
		return nil, err
	}

	fset := token.NewFileSet()
	f, err := parser.ParseFile(fset, filename, nil, 0)
	// ParseFile usually returns a partial file along with an error.
	// Only fail if there is no file.
	if f == nil {
		return nil, err
	}

	start, end, err := fileOffsetToPos(fset.File(f.Pos()), startOffset, endOffset)
	if err != nil {
		return nil, err
	}

	path, exact := astutil.PathEnclosingInterval(f, start, end)
	if path == nil {
		return nil, fmt.Errorf("no syntax here")
	}

	return &queryPos{fset, start, end, path, exact, nil}, nil
}

func findNodeChain(f *ast.File, pos token.Pos) []ast.Node {
	defer func() {
		if r := recover(); r != nil {
			lg("findnodechain recovered r=%v", r)
			fail()
		}
	}()
	chain, _ := astutil.PathEnclosingInterval(f, pos, pos+1)
	return chain
}

// PathEnclosingInterval returns the PackageInfo and ast.Node that
// contain source interval [start, end), and all the node's ancestors
// up to the AST root.  It searches all ast.Files of all packages in prog.
// exact is defined as for astutil.PathEnclosingInterval.
//
// The zero value is returned if not found.
//
func (prog *Program) PathEnclosingInterval(start, end token.Pos) (pkg *PackageInfo, path []ast.Node, exact bool) {
	for _, info := range prog.AllPackages {
		for _, f := range info.Files {
			if !tokenFileContainsPos(prog.Fset.File(f.Pos()), start) {
				continue
			}
			if path, exact := astutil.PathEnclosingInterval(f, start, end); path != nil {
				return info, path, exact
			}
		}
	}
	return nil, nil, false
}

func TestPathEnclosingInterval_Paths(t *testing.T) {
	// For these tests, we check only the path of the enclosing
	// node, but not its complete text because it's often quite
	// large when !exact.
	tests := []struct {
		substr string // first occurrence of this string indicates interval
		path   string // the pathToString(),exact of the expected path
	}{
		{"// add",
			"[BlockStmt FuncDecl File],false"},
		{"(x + y",
			"[ParenExpr AssignStmt BlockStmt FuncDecl File],false"},
		{"x +",
			"[BinaryExpr ParenExpr AssignStmt BlockStmt FuncDecl File],false"},
		{"z := (x",
			"[AssignStmt BlockStmt FuncDecl File],false"},
		{"func f",
			"[FuncDecl File],false"},
		{"func f()",
			"[FuncDecl File],false"},
		{" f()",
			"[FuncDecl File],false"},
		{"() {}",
			"[FuncDecl File],false"},
		{"// Hello",
			"[File],false"},
		{" f",
			"[Ident FuncDecl File],true"},
		{"func ",
			"[FuncDecl File],true"},
		{"mai",
			"[Ident File],true"},
		{"f() // NB",
			"[CallExpr ExprStmt BlockStmt FuncDecl File],true"},
	}
	for _, test := range tests {
		f, start, end := findInterval(t, new(token.FileSet), input, test.substr)
		if f == nil {
			continue
		}

		path, exact := astutil.PathEnclosingInterval(f, start, end)
		if got := fmt.Sprintf("%s,%v", pathToString(path), exact); got != test.path {
			t.Errorf("PathEnclosingInterval(%q): got %q, want %q",
				test.substr, got, test.path)
			continue
		}
	}
}

// PathEnclosingInterval returns the PackageInfo and ast.Node that
// contain source interval [start, end), and all the node's ancestors
// up to the AST root.  It searches all ast.Files of all packages in prog.
// exact is defined as for astutil.PathEnclosingInterval.
//
// The zero value is returned if not found.
//
func (prog *Program) PathEnclosingInterval(start, end token.Pos) (pkg *PackageInfo, path []ast.Node, exact bool) {
	for _, info := range prog.AllPackages {
		for _, f := range info.Files {
			if f.Pos() == token.NoPos {
				// This can happen if the parser saw
				// too many errors and bailed out.
				// (Use parser.AllErrors to prevent that.)
				continue
			}
			if !tokenFileContainsPos(prog.Fset.File(f.Pos()), start) {
				continue
			}
			if path, exact := astutil.PathEnclosingInterval(f, start, end); path != nil {
				return info, path, exact
			}
		}
	}
	return nil, nil, false
}

// fastQueryPos parses the position string and returns a queryPos.
// It parses only a single file and does not run the type checker.
func fastQueryPos(pos string) (*queryPos, error) {
	filename, startOffset, endOffset, err := parsePos(pos)
	if err != nil {
		return nil, err
	}

	fset := token.NewFileSet()
	f, err := parser.ParseFile(fset, filename, nil, 0)
	if err != nil {
		return nil, err
	}

	start, end, err := fileOffsetToPos(fset.File(f.Pos()), startOffset, endOffset)
	if err != nil {
		return nil, err
	}

	path, exact := astutil.PathEnclosingInterval(f, start, end)
	if path == nil {
		return nil, fmt.Errorf("no syntax here")
	}

	return &queryPos{fset, start, end, path, exact, nil}, nil
}

func TestEnclosingFunction(t *testing.T) {
	tests := []struct {
		input  string // the input file
		substr string // first occurrence of this string denotes interval
		fn     string // name of expected containing function
	}{
		// We use distinctive numbers as syntactic landmarks.

		// Ordinary function:
		{`package main
		  func f() { println(1003) }`,
			"100", "main.f"},
		// Methods:
		{`package main
                  type T int
		  func (t T) f() { println(200) }`,
			"200", "(main.T).f"},
		// Function literal:
		{`package main
		  func f() { println(func() { print(300) }) }`,
			"300", "main.f$1"},
		// Doubly nested
		{`package main
		  func f() { println(func() { print(func() { print(350) })})}`,
			"350", "main.f$1$1"},
		// Implicit init for package-level var initializer.
		{"package main; var a = 400", "400", "main.init"},
		// No code for constants:
		{"package main; const a = 500", "500", "(none)"},
		// Explicit init()
		{"package main; func init() { println(600) }", "600", "main.init#1"},
		// Multiple explicit init functions:
		{`package main
		  func init() { println("foo") }
		  func init() { println(800) }`,
			"800", "main.init#2"},
		// init() containing FuncLit.
		{`package main
		  func init() { println(func(){print(900)}) }`,
			"900", "main.init#1$1"},
	}
	for _, test := range tests {
		conf := loader.Config{Fset: token.NewFileSet()}
		f, start, end := findInterval(t, conf.Fset, test.input, test.substr)
		if f == nil {
			continue
		}
		path, exact := astutil.PathEnclosingInterval(f, start, end)
		if !exact {
			t.Errorf("EnclosingFunction(%q) not exact", test.substr)
			continue
		}

		conf.CreateFromFiles("main", f)

		iprog, err := conf.Load()
		if err != nil {
			t.Error(err)
			continue
		}
		prog := ssautil.CreateProgram(iprog, 0)
		pkg := prog.Package(iprog.Created[0].Pkg)
		pkg.Build()

		name := "(none)"
		fn := ssa.EnclosingFunction(pkg, path)
		if fn != nil {
			name = fn.String()
		}

		if name != test.fn {
			t.Errorf("EnclosingFunction(%q in %q) got %s, want %s",
				test.substr, test.input, name, test.fn)
			continue
		}

		// While we're here: test HasEnclosingFunction.
		if has := ssa.HasEnclosingFunction(pkg, path); has != (fn != nil) {
			t.Errorf("HasEnclosingFunction(%q in %q) got %v, want %v",
				test.substr, test.input, has, fn != nil)
			continue
		}
	}
}

func TestObjValueLookup(t *testing.T) {
	if runtime.GOOS == "android" {
		t.Skipf("no testdata directory on %s", runtime.GOOS)
	}

	conf := loader.Config{ParserMode: parser.ParseComments}
	f, err := conf.ParseFile("testdata/objlookup.go", nil)
	if err != nil {
		t.Error(err)
		return
	}
	conf.CreateFromFiles("main", f)

	// Maps each var Ident (represented "name:linenum") to the
	// kind of ssa.Value we expect (represented "Constant", "&Alloc").
	expectations := make(map[string]string)

	// Find all annotations of form x::BinOp, &y::Alloc, etc.
	re := regexp.MustCompile(`(\b|&)?(\w*)::(\w*)\b`)
	for _, c := range f.Comments {
		text := c.Text()
		pos := conf.Fset.Position(c.Pos())
		for _, m := range re.FindAllStringSubmatch(text, -1) {
			key := fmt.Sprintf("%s:%d", m[2], pos.Line)
			value := m[1] + m[3]
			expectations[key] = value
		}
	}

	iprog, err := conf.Load()
	if err != nil {
		t.Error(err)
		return
	}

	prog := ssautil.CreateProgram(iprog, 0 /*|ssa.PrintFunctions*/)
	mainInfo := iprog.Created[0]
	mainPkg := prog.Package(mainInfo.Pkg)
	mainPkg.SetDebugMode(true)
	mainPkg.Build()

	var varIds []*ast.Ident
	var varObjs []*types.Var
	for id, obj := range mainInfo.Defs {
		// Check invariants for func and const objects.
		switch obj := obj.(type) {
		case *types.Func:
			checkFuncValue(t, prog, obj)

		case *types.Const:
			checkConstValue(t, prog, obj)

		case *types.Var:
			if id.Name == "_" {
				continue
			}
			varIds = append(varIds, id)
			varObjs = append(varObjs, obj)
		}
	}
	for id, obj := range mainInfo.Uses {
		if obj, ok := obj.(*types.Var); ok {
			varIds = append(varIds, id)
			varObjs = append(varObjs, obj)
		}
	}

	// Check invariants for var objects.
	// The result varies based on the specific Ident.
	for i, id := range varIds {
		obj := varObjs[i]
		ref, _ := astutil.PathEnclosingInterval(f, id.Pos(), id.Pos())
		pos := prog.Fset.Position(id.Pos())
		exp := expectations[fmt.Sprintf("%s:%d", id.Name, pos.Line)]
		if exp == "" {
			t.Errorf("%s: no expectation for var ident %s ", pos, id.Name)
			continue
		}
		wantAddr := false
		if exp[0] == '&' {
			wantAddr = true
			exp = exp[1:]
		}
		checkVarValue(t, prog, mainPkg, ref, obj, exp, wantAddr)
	}
}

// Ensure that, in debug mode, we can determine the ssa.Value
// corresponding to every ast.Expr.
func TestValueForExpr(t *testing.T) {
	if runtime.GOOS == "android" {
		t.Skipf("no testdata dir on %s", runtime.GOOS)
	}

	conf := loader.Config{ParserMode: parser.ParseComments}
	f, err := conf.ParseFile("testdata/valueforexpr.go", nil)
	if err != nil {
		t.Error(err)
		return
	}
	conf.CreateFromFiles("main", f)

	iprog, err := conf.Load()
	if err != nil {
		t.Error(err)
		return
	}

	mainInfo := iprog.Created[0]

	prog := ssautil.CreateProgram(iprog, 0)
	mainPkg := prog.Package(mainInfo.Pkg)
	mainPkg.SetDebugMode(true)
	mainPkg.Build()

	if false {
		// debugging
		for _, mem := range mainPkg.Members {
			if fn, ok := mem.(*ssa.Function); ok {
				fn.WriteTo(os.Stderr)
			}
		}
	}

	// Find the actual AST node for each canonical position.
	parenExprByPos := make(map[token.Pos]*ast.ParenExpr)
	ast.Inspect(f, func(n ast.Node) bool {
		if n != nil {
			if e, ok := n.(*ast.ParenExpr); ok {
				parenExprByPos[e.Pos()] = e
			}
		}
		return true
	})

	// Find all annotations of form /*@kind*/.
	for _, c := range f.Comments {
		text := strings.TrimSpace(c.Text())
		if text == "" || text[0] != '@' {
			continue
		}
		text = text[1:]
		pos := c.End() + 1
		position := prog.Fset.Position(pos)
		var e ast.Expr
		if target := parenExprByPos[pos]; target == nil {
			t.Errorf("%s: annotation doesn't precede ParenExpr: %q", position, text)
			continue
		} else {
			e = target.X
		}

		path, _ := astutil.PathEnclosingInterval(f, pos, pos)
		if path == nil {
			t.Errorf("%s: can't find AST path from root to comment: %s", position, text)
			continue
		}

		fn := ssa.EnclosingFunction(mainPkg, path)
		if fn == nil {
			t.Errorf("%s: can't find enclosing function", position)
			continue
		}

		v, gotAddr := fn.ValueForExpr(e) // (may be nil)
		got := strings.TrimPrefix(fmt.Sprintf("%T", v), "*ssa.")
		if want := text; got != want {
			t.Errorf("%s: got value %q, want %q", position, got, want)
		}
		if v != nil {
			T := v.Type()
			if gotAddr {
				T = T.Underlying().(*types.Pointer).Elem() // deref
			}
			if !types.Identical(T, mainInfo.TypeOf(e)) {
				t.Errorf("%s: got type %s, want %s", position, mainInfo.TypeOf(e), T)
			}
		}
	}
}

func TestPathEnclosingInterval_Exact(t *testing.T) {
	// For the exact tests, we check that a substring is mapped to
	// the canonical string for the node it denotes.
	tests := []struct {
		substr string // first occurrence of this string indicates interval
		node   string // complete text of expected containing node
	}{
		{"package",
			input[11 : len(input)-1]},
		{"\npack",
			input[11 : len(input)-1]},
		{"main",
			"main"},
		{"import",
			"import \"fmt\""},
		{"\"fmt\"",
			"\"fmt\""},
		{"\nfunc f() {}\n",
			"func f() {}"},
		{"x ",
			"x"},
		{" y",
			"y"},
		{"z",
			"z"},
		{" + ",
			"x + y"},
		{" :=",
			"z := (x + y)"},
		{"x + y",
			"x + y"},
		{"(x + y)",
			"(x + y)"},
		{" (x + y) ",
			"(x + y)"},
		{" (x + y) // add",
			"(x + y)"},
		{"func",
			"func f() {}"},
		{"func f() {}",
			"func f() {}"},
		{"\nfun",
			"func f() {}"},
		{" f",
			"f"},
	}
	for _, test := range tests {
		f, start, end := findInterval(t, new(token.FileSet), input, test.substr)
		if f == nil {
			continue
		}

		path, exact := astutil.PathEnclosingInterval(f, start, end)
		if !exact {
			t.Errorf("PathEnclosingInterval(%q) not exact", test.substr)
			continue
		}

		if len(path) == 0 {
			if test.node != "" {
				t.Errorf("PathEnclosingInterval(%q).path: got [], want %q",
					test.substr, test.node)
			}
			continue
		}

		if got := input[path[0].Pos():path[0].End()]; got != test.node {
			t.Errorf("PathEnclosingInterval(%q): got %q, want %q (path was %s)",
				test.substr, got, test.node, pathToString(path))
			continue
		}
	}
}

// doQuickFix tries to fix the source AST so that it compiles well.
func (s *Session) doQuickFix() error {
	const maxAttempts = 10

	s.reset()

quickFixAttempt:
	for i := 0; i < maxAttempts; i++ {
		s.TypeInfo = types.Info{
			Types: make(map[ast.Expr]types.TypeAndValue),
		}

		files := s.ExtraFiles
		files = append(files, s.File)

		config := quickfix.Config{
			Fset:     s.Fset,
			Files:    files,
			TypeInfo: &s.TypeInfo,
		}
		_, err := config.QuickFixOnce()
		if err == nil {
			break
		}

		debugf("quickFix :: err = %#v", err)

		errList, ok := err.(quickfix.ErrorList)
		if !ok {
			continue
		}

		// (try to) fix gore-specific remaining errors
		for _, err := range errList {
			err, ok := err.(types.Error)
			if !ok {
				continue
			}

			// "... used as value":
			//
			// convert
			//   __gore_pp(funcWithSideEffectReturningNoValue())
			// to
			//   funcWithSideEffectReturningNoValue()
			if strings.HasSuffix(err.Msg, " used as value") {
				nodepath, _ := astutil.PathEnclosingInterval(s.File, err.Pos, err.Pos)

				for _, node := range nodepath {
					stmt, ok := node.(ast.Stmt)
					if !ok {
						continue
					}

					for i := range s.mainBody.List {
						if s.mainBody.List[i] != stmt {
							continue
						}

						exprs := printedExprs(stmt)

						stmts := s.mainBody.List[0:i]
						for _, expr := range exprs {
							stmts = append(stmts, &ast.ExprStmt{X: expr})
						}

						s.mainBody.List = append(stmts, s.mainBody.List[i+1:]...)
						continue quickFixAttempt
					}
				}
			}
		}

		debugf("quickFix :: give up: %#v", err)
	}

	return nil
}

func (c Config) QuickFixOnce() (bool, error) {
	fset := c.Fset
	files := c.Files

	errs := []error{}
	config := &types.Config{
		Error: func(err error) {
			errs = append(errs, err)
		},
		Importer: importer.Default(),
	}

	_, err := config.Check("_quickfix", fset, files, c.TypeInfo)
	if err == nil {
		return false, nil
	}

	// apply fixes on AST later so that we won't break funcs that inspect AST by positions
	fixes := map[error]func() bool{}
	unhandled := ErrorList{}

	foundError := len(errs) > 0

	for _, err := range errs {
		err, ok := err.(types.Error)
		if !ok {
			unhandled = append(unhandled, err)
			continue
		}

		f := findFile(c.Files, err.Pos)
		if f == nil {
			e := ErrCouldNotLocate{
				Err:  err,
				Fset: fset,
			}
			unhandled = append(unhandled, e)
			continue
		}

		nodepath, _ := astutil.PathEnclosingInterval(f, err.Pos, err.Pos)

		var fix func() bool

		// - "%s declared but not used"
		// - "%q imported but not used" (+ " as %s")
		// - "label %s declared but not used" TODO
		// - "no new variables on left side of :="
		if m := declaredNotUsed.FindStringSubmatch(err.Msg); m != nil {
			identName := m[1]
			fix = func() bool {
				return fixDeclaredNotUsed(nodepath, identName)
			}
		} else if m := importedNotUsed.FindStringSubmatch(err.Msg); m != nil {
			pkgPath := m[1] // quoted string, but it's okay because this will be compared to ast.BasicLit.Value.
			fix = func() bool {
				return fixImportedNotUsed(nodepath, pkgPath)
			}
		} else if err.Msg == noNewVariablesOnDefine {
			fix = func() bool {
				return fixNoNewVariables(nodepath)
			}
		} else {
			unhandled = append(unhandled, err)
		}

		if fix != nil {
			fixes[err] = fix
		}
	}

	for err, fix := range fixes {
		if fix() == false {
			unhandled = append(unhandled, err)
		}
	}

	return foundError, unhandled.any()
}