// Copyright 2017 The Go Authors. All rights reserved.
// Use of this src code is governed by a BSD-style
// license that can be found in the LICENSE file.

package types

import (
	"bytes"
	"fmt"
	"go/ast"
	"go/token"
)

// This file implements the collection of an interface's methods
// without relying on partially computed types of methods or interfaces
// for interface types declared at the package level.
//
// Because interfaces must not embed themselves, directly or indirectly,
// the method set of a valid interface can always be computed independent
// of any cycles that might exist via method signatures (see also issue #18395).
//
// Except for blank method name and interface cycle errors, no errors
// are reported. Affected methods or embedded interfaces are silently
// dropped. Subsequent type-checking of the interface will check
// signatures and embedded interfaces and report errors at that time.
//
// Only infoFromTypeLit should be called directly from code outside this file
// to compute an ifaceInfo.

// ifaceInfo describes the method set for an interface.
// The zero value for an ifaceInfo is a ready-to-use ifaceInfo representing
// the empty interface.
type ifaceInfo struct {
	explicits int           // number of explicitly declared methods
	methods   []*methodInfo // all methods, starting with explicitly declared ones in source order
}

// emptyIfaceInfo represents the ifaceInfo for the empty interface.
var emptyIfaceInfo ifaceInfo

func (info *ifaceInfo) String() string {
	var buf bytes.Buffer
	fmt.Fprintf(&buf, "interface{")
	for i, m := range info.methods {
		if i > 0 {
			fmt.Fprint(&buf, " ")
		}
		fmt.Fprint(&buf, m)
	}
	fmt.Fprintf(&buf, "}")
	return buf.String()
}

// methodInfo represents an interface method.
// At least one of src or fun must be non-nil.
// (Methods declared in the current package have a non-nil scope
// and src, and eventually a non-nil fun field; imported and pre-
// declared methods have a nil scope and src, and only a non-nil
// fun field.)
type methodInfo struct {
	scope *Scope     // scope of interface method; or nil
	src   *ast.Field // syntax tree representation of interface method; or nil
	fun   *Func      // corresponding fully type-checked method type; or nil
}

func (info *methodInfo) String() string {
	if info.fun != nil {
		return info.fun.name
	}
	return info.src.Names[0].Name
}

func (info *methodInfo) Pos() token.Pos {
	if info.fun != nil {
		return info.fun.Pos()
	}
	return info.src.Pos()
}

func (info *methodInfo) id(pkg *Package) string {
	if info.fun != nil {
		return info.fun.Id()
	}
	return Id(pkg, info.src.Names[0].Name)
}

// A methodInfoSet maps method ids to methodInfos.
// It is used to determine duplicate declarations.
// (A methodInfo set is the equivalent of an objset
// but for methodInfos rather than Objects.)
type methodInfoSet map[string]*methodInfo

// insert attempts to insert an method m into the method set s.
// If s already contains an alternative method alt with
// the same name, insert leaves s unchanged and returns alt.
// Otherwise it inserts m and returns nil.
func (s *methodInfoSet) insert(pkg *Package, m *methodInfo) *methodInfo {
	id := m.id(pkg)
	if alt := (*s)[id]; alt != nil {
		return alt
	}
	if *s == nil {
		*s = make(methodInfoSet)
	}
	(*s)[id] = m
	return nil
}

// like Checker.declareInSet but for method infos.
func (check *Checker) declareInMethodSet(mset *methodInfoSet, pos token.Pos, m *methodInfo) bool {
	if alt := mset.insert(check.pkg, m); alt != nil {
		check.errorf(pos, "%s redeclared", m)
		check.reportAltMethod(alt)
		return false
	}
	return true
}

// like Checker.reportAltDecl but for method infos.
func (check *Checker) reportAltMethod(m *methodInfo) {
	if pos := m.Pos(); pos.IsValid() {
		// We use "other" rather than "previous" here because
		// the first declaration seen may not be textually
		// earlier in the source.
		check.errorf(pos, "\tother declaration of %s", m) // secondary error, \t indented
	}
}

// infoFromTypeLit computes the method set for the given interface iface
// declared in scope.
// If a corresponding type name exists (tname != nil), it is used for
// cycle detection and to cache the method set.
// The result is the method set, or nil if there is a cycle via embedded
// interfaces. A non-nil result doesn't mean that there were no errors,
// but they were either reported (e.g., blank methods), or will be found
// (again) when computing the interface's type.
// If tname is not nil it must be the last element in path.
func (check *Checker) infoFromTypeLit(scope *Scope, iface *ast.InterfaceType, tname *TypeName, path []*TypeName) (info *ifaceInfo) {
	assert(iface != nil)

	// lazy-allocate interfaces map
	if check.interfaces == nil {
		check.interfaces = make(map[*TypeName]*ifaceInfo)
	}

	if trace {
		check.trace(iface.Pos(), "-- collect methods for %v (path = %s, objPath = %s)", iface, pathString(path), objPathString(check.objPath))
		check.indent++
		defer func() {
			check.indent--
			check.trace(iface.Pos(), "=> %s", info)
		}()
	}

	// If the interface is named, check if we computed info already.
	//
	// This is not simply an optimization; we may run into stack
	// overflow with recursive interface declarations. Example:
	//
	//      type T interface {
	//              m() interface { T }
	//      }
	//
	// (Since recursive definitions can only be expressed via names,
	// it is sufficient to track named interfaces here.)
	//
	// While at it, use the same mechanism to detect cycles. (We still
	// have the path-based cycle check because we want to report the
	// entire cycle if present.)
	if tname != nil {
		assert(path[len(path)-1] == tname) // tname must be last path element
		var found bool
		if info, found = check.interfaces[tname]; found {
			if info == nil {
				// We have a cycle and use check.cycle to report it.
				// We are guaranteed that check.cycle also finds the
				// cycle because when infoFromTypeLit is called, any
				// tname that's already in check.interfaces was also
				// added to the path. (But the converse is not true:
				// A non-nil tname is always the last element in path.)
				ok := check.cycle(tname, path, true)
				assert(ok)
			}
			return
		}
		check.interfaces[tname] = nil // computation started but not complete
	}

	if iface.Methods.List == nil {
		// fast track for empty interface
		info = &emptyIfaceInfo
	} else {
		// (syntactically) non-empty interface
		info = new(ifaceInfo)

		// collect explicitly declared methods and embedded interfaces
		var mset methodInfoSet
		var embeddeds []*ifaceInfo
		var positions []token.Pos // entries correspond to positions of embeddeds; used for error reporting
		for _, f := range iface.Methods.List {
			if len(f.Names) > 0 {
				// We have a method with name f.Names[0].
				// (The parser ensures that there's only one method
				// and we don't care if a constructed AST has more.)

				// spec: "As with all method sets, in an interface type,
				// each method must have a unique non-blank name."
				if name := f.Names[0]; name.Name == "_" {
					check.errorf(name.Pos(), "invalid method name _")
					continue // ignore
				}

				m := &methodInfo{scope: scope, src: f}
				if check.declareInMethodSet(&mset, f.Pos(), m) {
					info.methods = append(info.methods, m)
				}
			} else {
				// We have an embedded interface and f.Type is its
				// (possibly qualified) embedded type name. Collect
				// it if it's a valid interface.
				var e *ifaceInfo
				switch ename := f.Type.(type) {
				case *ast.Ident:
					e = check.infoFromTypeName(scope, ename, path)
				case *ast.SelectorExpr:
					e = check.infoFromQualifiedTypeName(scope, ename)
				default:
					// The parser makes sure we only see one of the above.
					// Constructed ASTs may contain other (invalid) nodes;
					// we simply ignore them. The full type-checking pass
					// will report those as errors later.
				}
				if e != nil {
					embeddeds = append(embeddeds, e)
					positions = append(positions, f.Type.Pos())
				}
			}
		}
		info.explicits = len(info.methods)

		// collect methods of embedded interfaces
		for i, e := range embeddeds {
			pos := positions[i] // position of type name of embedded interface
			for _, m := range e.methods {
				if check.declareInMethodSet(&mset, pos, m) {
					info.methods = append(info.methods, m)
				}
			}
		}
	}

	// mark check.interfaces as complete
	assert(info != nil)
	if tname != nil {
		check.interfaces[tname] = info
	}

	return
}

// infoFromTypeName computes the method set for the given type name
// which must denote a type whose underlying type is an interface.
// The same result qualifications apply as for infoFromTypeLit.
// infoFromTypeName should only be called from infoFromTypeLit.
func (check *Checker) infoFromTypeName(scope *Scope, name *ast.Ident, path []*TypeName) *ifaceInfo {
	// A single call of infoFromTypeName handles a sequence of (possibly
	// recursive) type declarations connected via unqualified type names.
	// Each type declaration leading to another typename causes a "tail call"
	// (goto) of this function. The general scenario looks like this:
	//
	//      ...
	//      type Pn T        // previous declarations leading to T, path = [..., Pn]
	//      type T interface { T0; ... }  // T0 leads to call of infoFromTypeName
	//
	//      // infoFromTypeName(name = T0, path = [..., Pn, T])
	//      type T0 T1       // path = [..., Pn, T, T0]
	//      type T1 T2  <-+  // path = [..., Pn, T, T0, T1]
	//      type T2 ...   |  // path = [..., Pn, T, T0, T1, T2]
	//      type Tn T1  --+  // path = [..., Pn, T, T0, T1, T2, Tn] and T1 is in path => cycle
	//
	// infoFromTypeName returns nil when such a cycle is detected. But in
	// contrast to cycles involving interfaces, we must not report the
	// error for "type name only" cycles because they will be found again
	// during type-checking of embedded interfaces. Reporting those cycles
	// here would lead to double reporting. Cycles involving embedding are
	// not reported again later because type-checking of interfaces relies
	// on the ifaceInfos computed here which are cycle-free by design.
	//
	// Remember the path length to detect "type name only" cycles.
	start := len(path)

typenameLoop:
	// name must be a type name denoting a type whose underlying type is an interface
	_, obj := scope.LookupParent(name.Name, check.pos)
	if obj == nil {
		return nil
	}
	tname, _ := obj.(*TypeName)
	if tname == nil {
		return nil
	}

	// We have a type name. It may be predeclared (error type),
	// imported (dot import), or declared by a type declaration.
	// It may not be an interface (e.g., predeclared type int).
	// Resolve it by analyzing each possible case.

	// Abort but don't report an error if we have a "type name only"
	// cycle (see big function comment).
	if check.cycle(tname, path[start:], false) {
		return nil
	}

	// Abort and report an error if we have a general cycle.
	if check.cycle(tname, path, true) {
		return nil
	}

	path = append(path, tname)

	// If tname is a package-level type declaration, it must be
	// in the objMap. Follow the RHS of that declaration if so.
	// The RHS may be a literal type (likely case), or another
	// (possibly parenthesized and/or qualified) type name.
	// (The declaration may be an alias declaration, but it
	// doesn't matter for the purpose of determining the under-
	// lying interface.)
	if decl := check.objMap[tname]; decl != nil {
		switch typ := unparen(decl.typ).(type) {
		case *ast.Ident:
			// type tname T
			name = typ
			goto typenameLoop
		case *ast.SelectorExpr:
			// type tname p.T
			return check.infoFromQualifiedTypeName(decl.file, typ)
		case *ast.InterfaceType:
			// type tname interface{...}
			// If tname is fully type-checked at this point (tname.color() == black)
			// we could use infoFromType here. But in this case, the interface must
			// be in the check.interfaces cache as well, which will be hit when we
			// call infoFromTypeLit below, and which will be faster. It is important
			// that we use that previously computed interface because its methods
			// have the correct receiver type (for go/types clients). Thus, the
			// check.interfaces cache must be up-to-date across even across multiple
			// check.Files calls (was bug - see issue #29029).
			return check.infoFromTypeLit(decl.file, typ, tname, path)
		}
		// type tname X // and X is not an interface type
		return nil
	}

	// If tname is not a package-level declaration, in a well-typed
	// program it should be a predeclared (error type), imported (dot
	// import), or function local declaration. Either way, it should
	// have been fully declared before use, except if there is a direct
	// cycle, and direct cycles will be caught above. Also, the denoted
	// type should be an interface (e.g., int is not an interface).
	if typ := tname.typ; typ != nil {
		// typ should be an interface
		if ityp, _ := typ.Underlying().(*Interface); ityp != nil {
			return infoFromType(ityp)
		}
	}

	// In all other cases we have some error.
	return nil
}

// infoFromQualifiedTypeName computes the method set for the given qualified type name, or nil.
func (check *Checker) infoFromQualifiedTypeName(scope *Scope, qname *ast.SelectorExpr) *ifaceInfo {
	// see also Checker.selector
	name, _ := qname.X.(*ast.Ident)
	if name == nil {
		return nil
	}
	_, obj1 := scope.LookupParent(name.Name, check.pos)
	if obj1 == nil {
		return nil
	}
	pname, _ := obj1.(*PkgName)
	if pname == nil {
		return nil
	}
	assert(pname.pkg == check.pkg)
	obj2 := pname.imported.scope.Lookup(qname.Sel.Name)
	if obj2 == nil || !obj2.Exported() {
		return nil
	}
	tname, _ := obj2.(*TypeName)
	if tname == nil {
		return nil
	}
	ityp, _ := tname.typ.Underlying().(*Interface)
	if ityp == nil {
		return nil
	}
	return infoFromType(ityp)
}

// infoFromType computes the method set for the given interface type.
// The result is never nil.
func infoFromType(typ *Interface) *ifaceInfo {
	assert(typ.allMethods != nil) // typ must be completely set up

	// fast track for empty interface
	n := len(typ.allMethods)
	if n == 0 {
		return &emptyIfaceInfo
	}

	info := new(ifaceInfo)
	info.explicits = len(typ.methods)
	info.methods = make([]*methodInfo, n)

	// If there are no embedded interfaces, simply collect the
	// explicitly declared methods (optimization of common case).
	if len(typ.methods) == n {
		for i, m := range typ.methods {
			info.methods[i] = &methodInfo{fun: m}
		}
		return info
	}

	// Interface types have a separate list for explicitly declared methods
	// which shares its methods with the list of all (explicitly declared or
	// embedded) methods. Collect all methods in a set so we can separate
	// the embedded methods from the explicitly declared ones.
	all := make(map[*Func]bool, n)
	for _, m := range typ.allMethods {
		all[m] = true
	}
	assert(len(all) == n) // methods must be unique

	// collect explicitly declared methods
	info.methods = make([]*methodInfo, n)
	for i, m := range typ.methods {
		info.methods[i] = &methodInfo{fun: m}
		delete(all, m)
	}

	// collect remaining (embedded) methods
	i := len(typ.methods)
	for m := range all {
		info.methods[i] = &methodInfo{fun: m}
		i++
	}
	assert(i == n)

	return info
}