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

package source

import (
	"context"
	"fmt"
	"go/ast"
	"go/printer"
	"go/token"
	"go/types"
	"path/filepath"
	"regexp"
	"sort"
	"strings"

	"golang.org/x/tools/go/ast/astutil"
	"golang.org/x/tools/internal/lsp/protocol"
	"golang.org/x/tools/internal/span"
	errors "golang.org/x/xerrors"
)

type mappedRange struct {
	spanRange span.Range
	m         *protocol.ColumnMapper

	// protocolRange is the result of converting the spanRange using the mapper.
	// It is computed on-demand.
	protocolRange *protocol.Range
}

func newMappedRange(fset *token.FileSet, m *protocol.ColumnMapper, start, end token.Pos) mappedRange {
	return mappedRange{
		spanRange: span.Range{
			FileSet:   fset,
			Start:     start,
			End:       end,
			Converter: m.Converter,
		},
		m: m,
	}
}

func (s mappedRange) Range() (protocol.Range, error) {
	if s.protocolRange == nil {
		spn, err := s.spanRange.Span()
		if err != nil {
			return protocol.Range{}, err
		}
		prng, err := s.m.Range(spn)
		if err != nil {
			return protocol.Range{}, err
		}
		s.protocolRange = &prng
	}
	return *s.protocolRange, nil
}

func (s mappedRange) Span() (span.Span, error) {
	return s.spanRange.Span()
}

func (s mappedRange) URI() span.URI {
	return s.m.URI
}

// getParsedFile is a convenience function that extracts the Package and ParseGoHandle for a File in a Snapshot.
// selectPackage is typically Narrowest/WidestPackageHandle below.
func getParsedFile(ctx context.Context, snapshot Snapshot, fh FileHandle, selectPackage PackagePolicy) (Package, ParseGoHandle, error) {
	phs, err := snapshot.PackageHandles(ctx, fh)
	if err != nil {
		return nil, nil, err
	}
	ph, err := selectPackage(phs)
	if err != nil {
		return nil, nil, err
	}
	pkg, err := ph.Check(ctx)
	if err != nil {
		return nil, nil, err
	}
	pgh, err := pkg.File(fh.Identity().URI)
	return pkg, pgh, err
}

type PackagePolicy func([]PackageHandle) (PackageHandle, error)

// NarrowestPackageHandle picks the "narrowest" package for a given file.
//
// By "narrowest" package, we mean the package with the fewest number of files
// that includes the given file. This solves the problem of test variants,
// as the test will have more files than the non-test package.
func NarrowestPackageHandle(handles []PackageHandle) (PackageHandle, error) {
	if len(handles) < 1 {
		return nil, errors.Errorf("no PackageHandles")
	}
	result := handles[0]
	for _, handle := range handles[1:] {
		if result == nil || len(handle.CompiledGoFiles()) < len(result.CompiledGoFiles()) {
			result = handle
		}
	}
	if result == nil {
		return nil, errors.Errorf("nil PackageHandles have been returned")
	}
	return result, nil
}

// WidestPackageHandle returns the PackageHandle containing the most files.
//
// This is useful for something like diagnostics, where we'd prefer to offer diagnostics
// for as many files as possible.
func WidestPackageHandle(handles []PackageHandle) (PackageHandle, error) {
	if len(handles) < 1 {
		return nil, errors.Errorf("no PackageHandles")
	}
	result := handles[0]
	for _, handle := range handles[1:] {
		if result == nil || len(handle.CompiledGoFiles()) > len(result.CompiledGoFiles()) {
			result = handle
		}
	}
	if result == nil {
		return nil, errors.Errorf("nil PackageHandles have been returned")
	}
	return result, nil
}

// SpecificPackageHandle creates a PackagePolicy to select a
// particular PackageHandle when you alread know the one you want.
func SpecificPackageHandle(desiredID string) PackagePolicy {
	return func(handles []PackageHandle) (PackageHandle, error) {
		for _, h := range handles {
			if h.ID() == desiredID {
				return h, nil
			}
		}

		return nil, fmt.Errorf("no package handle with expected id %q", desiredID)
	}
}

func IsGenerated(ctx context.Context, snapshot Snapshot, uri span.URI) bool {
	fh, err := snapshot.GetFile(uri)
	if err != nil {
		return false
	}
	ph := snapshot.View().Session().Cache().ParseGoHandle(fh, ParseHeader)
	parsed, _, _, _, err := ph.Parse(ctx)
	if err != nil {
		return false
	}
	tok := snapshot.View().Session().Cache().FileSet().File(parsed.Pos())
	if tok == nil {
		return false
	}
	for _, commentGroup := range parsed.Comments {
		for _, comment := range commentGroup.List {
			if matched := generatedRx.MatchString(comment.Text); matched {
				// Check if comment is at the beginning of the line in source.
				if pos := tok.Position(comment.Slash); pos.Column == 1 {
					return true
				}
			}
		}
	}
	return false
}

func nodeToProtocolRange(view View, pkg Package, n ast.Node) (protocol.Range, error) {
	mrng, err := posToMappedRange(view, pkg, n.Pos(), n.End())
	if err != nil {
		return protocol.Range{}, err
	}
	return mrng.Range()
}

func objToMappedRange(v View, pkg Package, obj types.Object) (mappedRange, error) {
	if pkgName, ok := obj.(*types.PkgName); ok {
		// An imported Go package has a package-local, unqualified name.
		// When the name matches the imported package name, there is no
		// identifier in the import spec with the local package name.
		//
		// For example:
		// 		import "go/ast" 	// name "ast" matches package name
		// 		import a "go/ast"  	// name "a" does not match package name
		//
		// When the identifier does not appear in the source, have the range
		// of the object be the import path, including quotes.
		if pkgName.Imported().Name() == pkgName.Name() {
			return posToMappedRange(v, pkg, obj.Pos(), obj.Pos()+token.Pos(len(pkgName.Imported().Path())+2))
		}
	}
	return nameToMappedRange(v, pkg, obj.Pos(), obj.Name())
}

func nameToMappedRange(v View, pkg Package, pos token.Pos, name string) (mappedRange, error) {
	return posToMappedRange(v, pkg, pos, pos+token.Pos(len(name)))
}

func posToMappedRange(v View, pkg Package, pos, end token.Pos) (mappedRange, error) {
	logicalFilename := v.Session().Cache().FileSet().File(pos).Position(pos).Filename
	m, err := findMapperInPackage(v, pkg, span.URIFromPath(logicalFilename))
	if err != nil {
		return mappedRange{}, err
	}
	if !pos.IsValid() {
		return mappedRange{}, errors.Errorf("invalid position for %v", pos)
	}
	if !end.IsValid() {
		return mappedRange{}, errors.Errorf("invalid position for %v", end)
	}
	return newMappedRange(v.Session().Cache().FileSet(), m, pos, end), nil
}

// Matches cgo generated comment as well as the proposed standard:
//	https://golang.org/s/generatedcode
var generatedRx = regexp.MustCompile(`// .*DO NOT EDIT\.?`)

func DetectLanguage(langID, filename string) FileKind {
	switch langID {
	case "go":
		return Go
	case "go.mod":
		return Mod
	case "go.sum":
		return Sum
	}
	// Fallback to detecting the language based on the file extension.
	switch filepath.Ext(filename) {
	case ".mod":
		return Mod
	case ".sum":
		return Sum
	default: // fallback to Go
		return Go
	}
}

func (k FileKind) String() string {
	switch k {
	case Mod:
		return "go.mod"
	case Sum:
		return "go.sum"
	default:
		return "go"
	}
}

// Returns the index and the node whose position is contained inside the node list.
func nodeAtPos(nodes []ast.Node, pos token.Pos) (ast.Node, int) {
	if nodes == nil {
		return nil, -1
	}
	for i, node := range nodes {
		if node.Pos() <= pos && pos <= node.End() {
			return node, i
		}
	}
	return nil, -1
}

// indexExprAtPos returns the index of the expression containing pos.
func exprAtPos(pos token.Pos, args []ast.Expr) int {
	for i, expr := range args {
		if expr.Pos() <= pos && pos <= expr.End() {
			return i
		}
	}
	return len(args)
}

// eachField invokes fn for each field that can be selected from a
// value of type T.
func eachField(T types.Type, fn func(*types.Var)) {
	// TODO(adonovan): this algorithm doesn't exclude ambiguous
	// selections that match more than one field/method.
	// types.NewSelectionSet should do that for us.

	// for termination on recursive types
	var seen map[*types.Struct]bool

	var visit func(T types.Type)
	visit = func(T types.Type) {
		if T, ok := deref(T).Underlying().(*types.Struct); ok {
			if seen[T] {
				return
			}

			for i := 0; i < T.NumFields(); i++ {
				f := T.Field(i)
				fn(f)
				if f.Anonymous() {
					if seen == nil {
						// Lazily create "seen" since it is only needed for
						// embedded structs.
						seen = make(map[*types.Struct]bool)
					}
					seen[T] = true
					visit(f.Type())
				}
			}
		}
	}
	visit(T)
}

// typeIsValid reports whether typ doesn't contain any Invalid types.
func typeIsValid(typ types.Type) bool {
	// Check named types separately, because we don't want
	// to call Underlying() on them to avoid problems with recursive types.
	if _, ok := typ.(*types.Named); ok {
		return true
	}

	switch typ := typ.Underlying().(type) {
	case *types.Basic:
		return typ.Kind() != types.Invalid
	case *types.Array:
		return typeIsValid(typ.Elem())
	case *types.Slice:
		return typeIsValid(typ.Elem())
	case *types.Pointer:
		return typeIsValid(typ.Elem())
	case *types.Map:
		return typeIsValid(typ.Key()) && typeIsValid(typ.Elem())
	case *types.Chan:
		return typeIsValid(typ.Elem())
	case *types.Signature:
		return typeIsValid(typ.Params()) && typeIsValid(typ.Results())
	case *types.Tuple:
		for i := 0; i < typ.Len(); i++ {
			if !typeIsValid(typ.At(i).Type()) {
				return false
			}
		}
		return true
	case *types.Struct, *types.Interface:
		// Don't bother checking structs, interfaces for validity.
		return true
	default:
		return false
	}
}

// resolveInvalid traverses the node of the AST that defines the scope
// containing the declaration of obj, and attempts to find a user-friendly
// name for its invalid type. The resulting Object and its Type are fake.
func resolveInvalid(fset *token.FileSet, obj types.Object, node ast.Node, info *types.Info) types.Object {
	var resultExpr ast.Expr
	ast.Inspect(node, func(node ast.Node) bool {
		switch n := node.(type) {
		case *ast.ValueSpec:
			for _, name := range n.Names {
				if info.Defs[name] == obj {
					resultExpr = n.Type
				}
			}
			return false
		case *ast.Field: // This case handles parameters and results of a FuncDecl or FuncLit.
			for _, name := range n.Names {
				if info.Defs[name] == obj {
					resultExpr = n.Type
				}
			}
			return false
		default:
			return true
		}
	})
	// Construct a fake type for the object and return a fake object with this type.
	typename := formatNode(fset, resultExpr)
	typ := types.NewNamed(types.NewTypeName(token.NoPos, obj.Pkg(), typename, nil), types.Typ[types.Invalid], nil)
	return types.NewVar(obj.Pos(), obj.Pkg(), obj.Name(), typ)
}

func isPointer(T types.Type) bool {
	_, ok := T.(*types.Pointer)
	return ok
}

func isVar(obj types.Object) bool {
	_, ok := obj.(*types.Var)
	return ok
}

// deref returns a pointer's element type, traversing as many levels as needed.
// Otherwise it returns typ.
func deref(typ types.Type) types.Type {
	for {
		p, ok := typ.Underlying().(*types.Pointer)
		if !ok {
			return typ
		}
		typ = p.Elem()
	}
}

func isTypeName(obj types.Object) bool {
	_, ok := obj.(*types.TypeName)
	return ok
}

func isFunc(obj types.Object) bool {
	_, ok := obj.(*types.Func)
	return ok
}

func isEmptyInterface(T types.Type) bool {
	intf, _ := T.(*types.Interface)
	return intf != nil && intf.NumMethods() == 0
}

func isUntyped(T types.Type) bool {
	if basic, ok := T.(*types.Basic); ok {
		return basic.Info()&types.IsUntyped > 0
	}
	return false
}

func isPkgName(obj types.Object) bool {
	_, ok := obj.(*types.PkgName)
	return ok
}

func isASTFile(n ast.Node) bool {
	_, ok := n.(*ast.File)
	return ok
}

func deslice(T types.Type) types.Type {
	if slice, ok := T.Underlying().(*types.Slice); ok {
		return slice.Elem()
	}
	return nil
}

// isSelector returns the enclosing *ast.SelectorExpr when pos is in the
// selector.
func enclosingSelector(path []ast.Node, pos token.Pos) *ast.SelectorExpr {
	if len(path) == 0 {
		return nil
	}

	if sel, ok := path[0].(*ast.SelectorExpr); ok {
		return sel
	}

	if _, ok := path[0].(*ast.Ident); ok && len(path) > 1 {
		if sel, ok := path[1].(*ast.SelectorExpr); ok && pos >= sel.Sel.Pos() {
			return sel
		}
	}

	return nil
}

func enclosingValueSpec(path []ast.Node) *ast.ValueSpec {
	for _, n := range path {
		if vs, ok := n.(*ast.ValueSpec); ok {
			return vs
		}
	}

	return nil
}

// typeConversion returns the type being converted to if call is a type
// conversion expression.
func typeConversion(call *ast.CallExpr, info *types.Info) types.Type {
	var ident *ast.Ident
	switch expr := call.Fun.(type) {
	case *ast.Ident:
		ident = expr
	case *ast.SelectorExpr:
		ident = expr.Sel
	default:
		return nil
	}

	// Type conversion (e.g. "float64(foo)").
	if fun, _ := info.ObjectOf(ident).(*types.TypeName); fun != nil {
		return fun.Type()
	}

	return nil
}

// fieldsAccessible returns whether s has at least one field accessible by p.
func fieldsAccessible(s *types.Struct, p *types.Package) bool {
	for i := 0; i < s.NumFields(); i++ {
		f := s.Field(i)
		if f.Exported() || f.Pkg() == p {
			return true
		}
	}
	return false
}

func formatParams(ctx context.Context, s Snapshot, pkg Package, sig *types.Signature, qf types.Qualifier) []string {
	params := make([]string, 0, sig.Params().Len())
	for i := 0; i < sig.Params().Len(); i++ {
		el := sig.Params().At(i)
		typ, err := formatFieldType(ctx, s, pkg, el)
		if err != nil {
			typ = types.TypeString(el.Type(), qf)
		}

		// Handle a variadic parameter (can only be the final parameter).
		if sig.Variadic() && i == sig.Params().Len()-1 {
			typ = strings.Replace(typ, "[]", "...", 1)
		}

		if el.Name() == "" {
			params = append(params, typ)
		} else {
			params = append(params, el.Name()+" "+typ)
		}
	}
	return params
}

func formatFieldType(ctx context.Context, s Snapshot, srcpkg Package, obj types.Object) (string, error) {
	file, pkg, err := findPosInPackage(s.View(), srcpkg, obj.Pos())
	if err != nil {
		return "", err
	}
	ident, err := findIdentifier(ctx, s, pkg, file, obj.Pos())
	if err != nil {
		return "", err
	}
	if i := ident.ident; i == nil || i.Obj == nil || i.Obj.Decl == nil {
		return "", errors.Errorf("no object for ident %v", i.Name)
	}
	f, ok := ident.ident.Obj.Decl.(*ast.Field)
	if !ok {
		return "", errors.Errorf("ident %s is not a field type", ident.Name)
	}
	return formatNode(s.View().Session().Cache().FileSet(), f.Type), nil
}

func formatNode(fset *token.FileSet, n ast.Node) string {
	var buf strings.Builder
	if err := printer.Fprint(&buf, fset, n); err != nil {
		return ""
	}
	return buf.String()
}

func formatResults(tup *types.Tuple, qf types.Qualifier) ([]string, bool) {
	var writeResultParens bool
	results := make([]string, 0, tup.Len())
	for i := 0; i < tup.Len(); i++ {
		if i >= 1 {
			writeResultParens = true
		}
		el := tup.At(i)
		typ := types.TypeString(el.Type(), qf)

		if el.Name() == "" {
			results = append(results, typ)
		} else {
			if i == 0 {
				writeResultParens = true
			}
			results = append(results, el.Name()+" "+typ)
		}
	}
	return results, writeResultParens
}

// formatType returns the detail and kind for an object of type *types.TypeName.
func formatType(typ types.Type, qf types.Qualifier) (detail string, kind protocol.CompletionItemKind) {
	if types.IsInterface(typ) {
		detail = "interface{...}"
		kind = protocol.InterfaceCompletion
	} else if _, ok := typ.(*types.Struct); ok {
		detail = "struct{...}"
		kind = protocol.StructCompletion
	} else if typ != typ.Underlying() {
		detail, kind = formatType(typ.Underlying(), qf)
	} else {
		detail = types.TypeString(typ, qf)
		kind = protocol.ClassCompletion
	}
	return detail, kind
}

func formatFunction(params []string, results []string, writeResultParens bool) string {
	var detail strings.Builder

	detail.WriteByte('(')
	for i, p := range params {
		if i > 0 {
			detail.WriteString(", ")
		}
		detail.WriteString(p)
	}
	detail.WriteByte(')')

	// Add space between parameters and results.
	if len(results) > 0 {
		detail.WriteByte(' ')
	}

	if writeResultParens {
		detail.WriteByte('(')
	}
	for i, p := range results {
		if i > 0 {
			detail.WriteString(", ")
		}
		detail.WriteString(p)
	}
	if writeResultParens {
		detail.WriteByte(')')
	}

	return detail.String()
}

func SortDiagnostics(d []Diagnostic) {
	sort.Slice(d, func(i int, j int) bool {
		return CompareDiagnostic(d[i], d[j]) < 0
	})
}

func CompareDiagnostic(a, b Diagnostic) int {
	if r := protocol.CompareRange(a.Range, b.Range); r != 0 {
		return r
	}
	if a.Source < b.Source {
		return -1
	}
	if a.Message < b.Message {
		return -1
	}
	if a.Message == b.Message {
		return 0
	}
	return 1
}

func findPosInPackage(v View, searchpkg Package, pos token.Pos) (*ast.File, Package, error) {
	tok := v.Session().Cache().FileSet().File(pos)
	if tok == nil {
		return nil, nil, errors.Errorf("no file for pos in package %s", searchpkg.ID())
	}
	uri := span.URIFromPath(tok.Name())

	var (
		ph  ParseGoHandle
		pkg Package
		err error
	)
	// Special case for ignored files.
	if v.Ignore(uri) {
		ph, err = findIgnoredFile(v, uri)
	} else {
		ph, pkg, err = FindFileInPackage(searchpkg, uri)
	}
	if err != nil {
		return nil, nil, err
	}
	file, _, _, _, err := ph.Cached()
	if err != nil {
		return nil, nil, err
	}
	if !(file.Pos() <= pos && pos <= file.End()) {
		return nil, nil, fmt.Errorf("pos %v, apparently in file %q, is not between %v and %v", pos, ph.File().Identity().URI, file.Pos(), file.End())
	}
	return file, pkg, nil
}

func findMapperInPackage(v View, searchpkg Package, uri span.URI) (*protocol.ColumnMapper, error) {
	var (
		ph  ParseGoHandle
		err error
	)
	// Special case for ignored files.
	if v.Ignore(uri) {
		ph, err = findIgnoredFile(v, uri)
	} else {
		ph, _, err = FindFileInPackage(searchpkg, uri)
	}
	if err != nil {
		return nil, err
	}
	_, _, m, _, err := ph.Cached()
	if err != nil {
		return nil, err
	}
	return m, nil
}

func findIgnoredFile(v View, uri span.URI) (ParseGoHandle, error) {
	fh, err := v.Snapshot().GetFile(uri)
	if err != nil {
		return nil, err
	}
	return v.Session().Cache().ParseGoHandle(fh, ParseFull), nil
}

// FindFileInPackage finds uri in pkg or its dependencies.
func FindFileInPackage(pkg Package, uri span.URI) (ParseGoHandle, Package, error) {
	queue := []Package{pkg}
	seen := make(map[string]bool)

	for len(queue) > 0 {
		pkg := queue[0]
		queue = queue[1:]
		seen[pkg.ID()] = true

		if f, err := pkg.File(uri); err == nil {
			return f, pkg, nil
		}
		for _, dep := range pkg.Imports() {
			if !seen[dep.ID()] {
				queue = append(queue, dep)
			}
		}
	}
	return nil, nil, errors.Errorf("no file for %s in package %s", uri, pkg.ID())
}

// prevStmt returns the statement that precedes the statement containing pos.
// For example:
//
//     foo := 1
//     bar(1 + 2<>)
//
// If "<>" is pos, prevStmt returns "foo := 1"
func prevStmt(pos token.Pos, path []ast.Node) ast.Stmt {
	var blockLines []ast.Stmt
	for i := 0; i < len(path) && blockLines == nil; i++ {
		switch n := path[i].(type) {
		case *ast.BlockStmt:
			blockLines = n.List
		case *ast.CommClause:
			blockLines = n.Body
		case *ast.CaseClause:
			blockLines = n.Body
		}
	}

	for i := len(blockLines) - 1; i >= 0; i-- {
		if blockLines[i].End() < pos {
			return blockLines[i]
		}
	}

	return nil
}

// formatZeroValue produces Go code representing the zero value of T.
func formatZeroValue(T types.Type, qf types.Qualifier) string {
	switch u := T.Underlying().(type) {
	case *types.Basic:
		switch {
		case u.Info()&types.IsNumeric > 0:
			return "0"
		case u.Info()&types.IsString > 0:
			return `""`
		case u.Info()&types.IsBoolean > 0:
			return "false"
		default:
			panic(fmt.Sprintf("unhandled basic type: %v", u))
		}
	case *types.Pointer, *types.Interface, *types.Chan, *types.Map, *types.Slice, *types.Signature:
		return "nil"
	default:
		return types.TypeString(T, qf) + "{}"
	}
}

func zeroValue(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Type) ast.Expr {
	under := typ
	if n, ok := typ.(*types.Named); ok {
		under = n.Underlying()
	}
	switch u := under.(type) {
	case *types.Basic:
		switch {
		case u.Info()&types.IsNumeric != 0:
			return &ast.BasicLit{Kind: token.INT, Value: "0"}
		case u.Info()&types.IsBoolean != 0:
			return &ast.Ident{Name: "false"}
		case u.Info()&types.IsString != 0:
			return &ast.BasicLit{Kind: token.STRING, Value: `""`}
		default:
			panic("unknown basic type")
		}
	case *types.Chan, *types.Interface, *types.Map, *types.Pointer, *types.Signature, *types.Slice:
		return ast.NewIdent("nil")
	case *types.Struct:
		texpr := typeExpr(fset, f, pkg, typ) // typ because we want the name here.
		if texpr == nil {
			return nil
		}
		return &ast.CompositeLit{
			Type: texpr,
		}
	case *types.Array:
		texpr := typeExpr(fset, f, pkg, u.Elem())
		if texpr == nil {
			return nil
		}
		return &ast.CompositeLit{
			Type: &ast.ArrayType{
				Elt: texpr,
				Len: &ast.BasicLit{Kind: token.INT, Value: fmt.Sprintf("%v", u.Len())},
			},
		}
	}
	return nil
}

func typeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Type) ast.Expr {
	switch t := typ.(type) {
	case *types.Basic:
		switch t.Kind() {
		case types.UnsafePointer:
			return &ast.SelectorExpr{X: ast.NewIdent("unsafe"), Sel: ast.NewIdent("Pointer")}
		default:
			return ast.NewIdent(t.Name())
		}
	case *types.Named:
		if t.Obj().Pkg() == pkg {
			return ast.NewIdent(t.Obj().Name())
		}
		pkgName := t.Obj().Pkg().Name()
		// If the file already imports the package under another name, use that.
		for _, group := range astutil.Imports(fset, f) {
			for _, cand := range group {
				if strings.Trim(cand.Path.Value, `"`) == t.Obj().Pkg().Path() {
					if cand.Name != nil && cand.Name.Name != "" {
						pkgName = cand.Name.Name
					}
				}
			}
		}
		if pkgName == "." {
			return ast.NewIdent(t.Obj().Name())
		}
		return &ast.SelectorExpr{
			X:   ast.NewIdent(pkgName),
			Sel: ast.NewIdent(t.Obj().Name()),
		}
	default:
		return nil // TODO: anonymous structs, but who does that
	}
}