// Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
// Source: ../../cmd/compile/internal/types2/subst.go

// 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 makeSubstMap( []*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 makeRenameMap(,  []*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 doesn't modify the
// incoming type. If a substitution took place, the result type is different
// from the incoming type.
//
// If expanding is non-nil, it is the instance type currently being expanded.
// One of expanding or ctxt must be non-nil.
func ( *Checker) ( token.Pos,  Type,  substMap,  *Named,  *Context) Type {
	assert( != nil ||  != nil)

	if .empty() {
		return 
	}

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

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

type subster struct {
	pos       token.Pos
	smap      substMap
	check     *Checker // nil if called via Instantiate
	expanding *Named   // if non-nil, the instance that is being expanded
	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 *Alias:
		// This code follows the code for *Named types closely.
		// TODO(gri) try to factor better
		 := .Origin()
		 := .TypeParams().Len()
		if  == 0 {
			return  // type is not parameterized
		}

		// TODO(gri) do we need this for Alias types?
		if .TypeArgs().Len() !=  {
			return Typ[Invalid] // error reported elsewhere
		}

		// already instantiated
		// For each (existing) type argument determine if it needs
		// to be substituted; i.e., if it is or contains a type parameter
		// that has a type argument for it.
		if  := substList(.TypeArgs().list(), .);  != nil {
			return .check.newAliasInstance(.pos, .orig, , .expanding, .ctxt)
		}

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

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

	case *Struct:
		if  := substList(.fields, .var_);  != nil {
			 := &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(gri) 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:
		if  := substList(.terms, .term);  != nil {
			// 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:
		 := substList(.methods, .func_)
		 := substList(.embeddeds, .)
		if  != nil ||  != nil {
			if  == nil {
				 = .methods
			}
			if  == nil {
				 = .embeddeds
			}
			 := .check.newInterface()
			.embeddeds = 
			.embedPos = .embedPos
			.implicit = .implicit
			assert(.complete) // otherwise we are copying incomplete data
			.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 Named.expandUnderlying.
			.methods, _ = replaceRecvType(, , )

			// If check != nil, check.newInterface will have saved the interface for later completion.
			if .check == nil { // golang/go#61561: all newly created interfaces must be completed
				.typeSet()
			}
			return 
		}

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

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

	case *Named:
		// subst is called during expansion, 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.Origin().TypeParams() rather than t.TypeParams().
		 := .Origin()
		 := .TypeParams().Len()
		if  == 0 {
			return  // type is not parameterized
		}

		if .TypeArgs().Len() !=  {
			return Typ[Invalid] // error reported elsewhere
		}

		// already instantiated
		// For each (existing) type argument determine if it needs
		// to be substituted; i.e., if it is or contains a type parameter
		// that has a type argument for it.
		if  := substList(.TypeArgs().list(), .);  != nil {
			// 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.
			return .check.instance(.pos, , , .expanding, .ctxt)
		}

	case *TypeParam:
		return .smap.lookup()

	default:
		panic("unreachable")
	}

	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 cloneVar(, )
		}
	}
	return 
}

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

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

// substList applies subst to each element of the incoming slice.
// If at least one element changes, the result is a new slice with
// all the (possibly updated) elements of the incoming slice;
// otherwise the result it nil. The incoming slice is unchanged.
func substList[ comparable]( [],  func() ) ( []) {
	for ,  := range  {
		if  := ();  !=  {
			if  == nil {
				// lazily allocate a new slice on first substitution
				 = make([], len())
				copy(, )
			}
			[] = 
		}
	}
	return
}

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

func cloneFunc( *Func,  Type) *Func {
	 := *
	.typ = 
	.origin = .Origin()
	return &
}

func ( *subster) ( *Term) *Term {
	if  := .typ(.typ);  != .typ {
		return 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 replaceRecvType( []*Func, ,  Type) ( []*Func,  bool) {
	 = 
	for ,  := range  {
		 := .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 = cloneVar(.recv, )
			[] = cloneFunc(, &)
		}
	}
	return
}