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

// This file implements type parameter substitution.

package types

import 

type substMap map[*TypeParam]Type

// makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
// If targs[i] is nil, tpars[i] is not substituted.
func ( []*TypeParam,  []Type) substMap {
	assert(len() == len())
	 := make(substMap, len())
	for ,  := range  {
		[] = []
	}
	return 
}

// makeRenameMap is like makeSubstMap, but creates a map used to rename type
// parameters in from with the type parameters in to.
func (,  []*TypeParam) substMap {
	assert(len() == len())
	 := make(substMap, len())
	for ,  := range  {
		[] = []
	}
	return 
}

func ( substMap) () bool {
	return len() == 0
}

func ( substMap) ( *TypeParam) Type {
	if  := [];  != nil {
		return 
	}
	return 
}

// subst returns the type typ with its type parameters tpars replaced by the
// corresponding type arguments targs, recursively. subst is pure in the sense
// that it doesn't modify the incoming type. If a substitution took place, the
// result type is different from the incoming type.
//
// If the given context is non-nil, it is used in lieu of check.Config.Context
func ( *Checker) ( token.Pos,  Type,  substMap,  *Context) Type {
	if .empty() {
		return 
	}

	// common cases
	switch t := .(type) {
	case *Basic:
		return  // nothing to do
	case *TypeParam:
		return .lookup()
	}

	// general case
	 := subster{
		pos:   ,
		smap:  ,
		check: ,
		ctxt:  .bestContext(),
	}
	return .typ()
}

type subster struct {
	pos   token.Pos
	smap  substMap
	check *Checker // nil if called via Instantiate
	ctxt  *Context
}

func ( *subster) ( Type) Type {
	switch t := .(type) {
	case nil:
		// Call typOrNil if it's possible that typ is nil.
		panic("nil typ")

	case *Basic:
		// nothing to do

	case *Array:
		 := .typOrNil(.elem)
		if  != .elem {
			return &Array{len: .len, elem: }
		}

	case *Slice:
		 := .typOrNil(.elem)
		if  != .elem {
			return &Slice{elem: }
		}

	case *Struct:
		if ,  := .varList(.fields);  {
			 := &Struct{fields: , tags: .tags}
			.markComplete()
			return 
		}

	case *Pointer:
		 := .(.base)
		if  != .base {
			return &Pointer{base: }
		}

	case *Tuple:
		return .tuple()

	case *Signature:
		// Preserve the receiver: it is handled during *Interface and *Named type
		// substitution.
		//
		// Naively doing the substitution here can lead to an infinite recursion in
		// the case where the receiver is an interface. For example, consider the
		// following declaration:
		//
		//  type T[A any] struct { f interface{ m() } }
		//
		// In this case, the type of f is an interface that is itself the receiver
		// type of all of its methods. Because we have no type name to break
		// cycles, substituting in the recv results in an infinite loop of
		// recv->interface->recv->interface->...
		 := .recv

		 := .tuple(.params)
		 := .tuple(.results)
		if  != .params ||  != .results {
			return &Signature{
				rparams: .rparams,
				// TODO(rFindley) why can't we nil out tparams here, rather than in instantiate?
				tparams: .tparams,
				// instantiated signatures have a nil scope
				recv:     ,
				params:   ,
				results:  ,
				variadic: .variadic,
			}
		}

	case *Union:
		,  := .termlist(.terms)
		if  {
			// term list substitution may introduce duplicate terms (unlikely but possible).
			// This is ok; lazy type set computation will determine the actual type set
			// in normal form.
			return &Union{}
		}

	case *Interface:
		,  := .funcList(.methods)
		,  := .typeList(.embeddeds)
		if  ||  {
			 := .check.newInterface()
			.embeddeds = 
			.implicit = .implicit
			.complete = .complete
			// If we've changed the interface type, we may need to replace its
			// receiver if the receiver type is the original interface. Receivers of
			// *Named type are replaced during named type expansion.
			//
			// Notably, it's possible to reach here and not create a new *Interface,
			// even though the receiver type may be parameterized. For example:
			//
			//  type T[P any] interface{ m() }
			//
			// In this case the interface will not be substituted here, because its
			// method signatures do not depend on the type parameter P, but we still
			// need to create new interface methods to hold the instantiated
			// receiver. This is handled by expandNamed.
			.methods, _ = replaceRecvType(, , )
			return 
		}

	case *Map:
		 := .(.key)
		 := .(.elem)
		if  != .key ||  != .elem {
			return &Map{key: , elem: }
		}

	case *Chan:
		 := .(.elem)
		if  != .elem {
			return &Chan{dir: .dir, elem: }
		}

	case *Named:
		// dump is for debugging
		 := func(string, ...any) {}
		if .check != nil && trace {
			.check.indent++
			defer func() {
				.check.indent--
			}()
			 = func( string,  ...any) {
				.check.trace(.pos, , ...)
			}
		}

		// subst is called by expandNamed, so in this function we need to be
		// careful not to call any methods that would cause t to be expanded: doing
		// so would result in deadlock.
		//
		// So we call t.orig.TypeParams() rather than t.TypeParams() here and
		// below.
		if .orig.TypeParams().Len() == 0 {
			(">>> %s is not parameterized", )
			return  // type is not parameterized
		}

		var  []Type
		if .targs.Len() != .orig.TypeParams().Len() {
			return Typ[Invalid] // error reported elsewhere
		}

		// already instantiated
		(">>> %s already instantiated", )
		// For each (existing) type argument targ, determine if it needs
		// to be substituted; i.e., if it is or contains a type parameter
		// that has a type argument for it.
		for ,  := range .targs.list() {
			(">>> %d targ = %s", , )
			 := .()
			if  !=  {
				(">>> substituted %d targ %s => %s", , , )
				if  == nil {
					 = make([]Type, .orig.TypeParams().Len())
					copy(, .targs.list())
				}
				[] = 
			}
		}

		if  == nil {
			(">>> nothing to substitute in %s", )
			return  // nothing to substitute
		}

		// before creating a new named type, check if we have this one already
		 := .ctxt.instanceHash(.orig, )
		(">>> new type hash: %s", )
		if  := .ctxt.lookup(, .orig, );  != nil {
			(">>> found %s", )
			return 
		}

		// Create a new instance and populate the context to avoid endless
		// recursion. The position used here is irrelevant because validation only
		// occurs on t (we don't call validType on named), but we use subst.pos to
		// help with debugging.
		.orig.resolve(.ctxt)
		return .check.instance(.pos, .orig, , .ctxt)

		// Note that if we were to expose substitution more generally (not just in
		// the context of a declaration), we'd have to substitute in
		// named.underlying as well.
		//
		// But this is unnecessary for now.

	case *TypeParam:
		return .smap.lookup()

	default:
		panic("unimplemented")
	}

	return 
}

// typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
// A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
// where an array/slice element is accessed before it is set up.
func ( *subster) ( Type) Type {
	if  == nil {
		return Typ[Invalid]
	}
	return .typ()
}

func ( *subster) ( *Var) *Var {
	if  != nil {
		if  := .typ(.typ);  != .typ {
			return substVar(, )
		}
	}
	return 
}

func ( *Var,  Type) *Var {
	 := *
	.typ = 
	return &
}

func ( *subster) ( *Tuple) *Tuple {
	if  != nil {
		if ,  := .varList(.vars);  {
			return &Tuple{vars: }
		}
	}
	return 
}

func ( *subster) ( []*Var) ( []*Var,  bool) {
	 = 
	for ,  := range  {
		if  := .var_();  !=  {
			if ! {
				// first variable that got substituted => allocate new out slice
				// and copy all variables
				 := make([]*Var, len())
				copy(, )
				 = 
				 = true
			}
			[] = 
		}
	}
	return
}

func ( *subster) ( *Func) *Func {
	if  != nil {
		if  := .typ(.typ);  != .typ {
			 := *
			.typ = 
			return &
		}
	}
	return 
}

func ( *subster) ( []*Func) ( []*Func,  bool) {
	 = 
	for ,  := range  {
		if  := .func_();  !=  {
			if ! {
				// first function that got substituted => allocate new out slice
				// and copy all functions
				 := make([]*Func, len())
				copy(, )
				 = 
				 = true
			}
			[] = 
		}
	}
	return
}

func ( *subster) ( []Type) ( []Type,  bool) {
	 = 
	for ,  := range  {
		if  := .typ();  !=  {
			if ! {
				// first function that got substituted => allocate new out slice
				// and copy all functions
				 := make([]Type, len())
				copy(, )
				 = 
				 = true
			}
			[] = 
		}
	}
	return
}

func ( *subster) ( []*Term) ( []*Term,  bool) {
	 = 
	for ,  := range  {
		if  := .typ(.typ);  != .typ {
			if ! {
				// first function that got substituted => allocate new out slice
				// and copy all functions
				 := make([]*Term, len())
				copy(, )
				 = 
				 = true
			}
			[] = NewTerm(.tilde, )
		}
	}
	return
}

// replaceRecvType updates any function receivers that have type old to have
// type new. It does not modify the input slice; if modifications are required,
// the input slice and any affected signatures will be copied before mutating.
//
// The resulting out slice contains the updated functions, and copied reports
// if anything was modified.
func ( []*Func, ,  Type) ( []*Func,  bool) {
	 = 
	for ,  := range  {
		 := .Type().(*Signature)
		if .recv != nil && .recv.Type() ==  {
			if ! {
				// Allocate a new methods slice before mutating for the first time.
				// This is defensive, as we may share methods across instantiations of
				// a given interface type if they do not get substituted.
				 = make([]*Func, len())
				copy(, )
				 = true
			}
			 := *
			.recv = substVar(.recv, )
			[] = NewFunc(.pos, .pkg, .name, &)
		}
	}
	return
}