// Copyright 2021 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 types

import (
	
	
	. 
)

// This file implements a check to validate that a Go package doesn't
// have unbounded recursive instantiation, which is not compatible
// with compilers using static instantiation (such as
// monomorphization).
//
// It implements a sort of "type flow" analysis by detecting which
// type parameters are instantiated with other type parameters (or
// types derived thereof). A package cannot be statically instantiated
// if the graph has any cycles involving at least one derived type.
//
// Concretely, we construct a directed, weighted graph. Vertices are
// used to represent type parameters as well as some defined
// types. Edges are used to represent how types depend on each other:
//
// * Everywhere a type-parameterized function or type is instantiated,
//   we add edges to each type parameter from the vertices (if any)
//   representing each type parameter or defined type referenced by
//   the type argument. If the type argument is just the referenced
//   type itself, then the edge has weight 0, otherwise 1.
//
// * For every defined type declared within a type-parameterized
//   function or method, we add an edge of weight 1 to the defined
//   type from each ambient type parameter.
//
// For example, given:
//
//	func f[A, B any]() {
//		type T int
//		f[T, map[A]B]()
//	}
//
// we construct vertices representing types A, B, and T. Because of
// declaration "type T int", we construct edges T<-A and T<-B with
// weight 1; and because of instantiation "f[T, map[A]B]" we construct
// edges A<-T with weight 0, and B<-A and B<-B with weight 1.
//
// Finally, we look for any positive-weight cycles. Zero-weight cycles
// are allowed because static instantiation will reach a fixed point.

type monoGraph struct {
	vertices []monoVertex
	edges    []monoEdge

	// canon maps method receiver type parameters to their respective
	// receiver type's type parameters.
	canon map[*TypeParam]*TypeParam

	// nameIdx maps a defined type or (canonical) type parameter to its
	// vertex index.
	nameIdx map[*TypeName]int
}

type monoVertex struct {
	weight int // weight of heaviest known path to this vertex
	pre    int // previous edge (if any) in the above path
	len    int // length of the above path

	// obj is the defined type or type parameter represented by this
	// vertex.
	obj *TypeName
}

type monoEdge struct {
	dst, src int
	weight   int

	pos token.Pos
	typ Type
}

func ( *Checker) () {
	// We detect unbounded instantiation cycles using a variant of
	// Bellman-Ford's algorithm. Namely, instead of always running |V|
	// iterations, we run until we either reach a fixed point or we've
	// found a path of length |V|. This allows us to terminate earlier
	// when there are no cycles, which should be the common case.

	 := true
	for  {
		 = false

		for ,  := range .mono.edges {
			 := &.mono.vertices[.src]
			 := &.mono.vertices[.dst]

			// N.B., we're looking for the greatest weight paths, unlike
			// typical Bellman-Ford.
			 := .weight + .weight
			if  <= .weight {
				continue
			}

			.pre = 
			.len = .len + 1
			if .len == len(.mono.vertices) {
				.reportInstanceLoop(.dst)
				return
			}

			.weight = 
			 = true
		}
	}
}

func ( *Checker) ( int) {
	var  []int
	 := make([]bool, len(.mono.vertices))

	// We have a path that contains a cycle and ends at v, but v may
	// only be reachable from the cycle, not on the cycle itself. We
	// start by walking backwards along the path until we find a vertex
	// that appears twice.
	for ![] {
		 = append(, )
		[] = true
		 = .mono.edges[.mono.vertices[].pre].src
	}

	// Trim any vertices we visited before visiting v the first
	// time. Since v is the first vertex we found within the cycle, any
	// vertices we visited earlier cannot be part of the cycle.
	for [0] !=  {
		 = [1:]
	}

	// TODO(mdempsky): Pivot stack so we report the cycle from the top?

	 := .mono.vertices[].obj
	.error(, InvalidInstanceCycle, "instantiation cycle:")

	 := RelativeTo(.pkg)
	for ,  := range  {
		 := .mono.edges[.mono.vertices[].pre]
		 := .mono.vertices[.dst].obj

		switch .Type().(type) {
		default:
			panic("unexpected type")
		case *Named:
			.errorf(atPos(.pos), InvalidInstanceCycle, "\t%s implicitly parameterized by %s", .Name(), TypeString(.typ, )) // secondary error, \t indented
		case *TypeParam:
			.errorf(atPos(.pos), InvalidInstanceCycle, "\t%s instantiated as %s", .Name(), TypeString(.typ, )) // secondary error, \t indented
		}
	}
}

// recordCanon records that tpar is the canonical type parameter
// corresponding to method type parameter mpar.
func ( *monoGraph) (,  *TypeParam) {
	if .canon == nil {
		.canon = make(map[*TypeParam]*TypeParam)
	}
	.canon[] = 
}

// recordInstance records that the given type parameters were
// instantiated with the corresponding type arguments.
func ( *monoGraph) ( *Package,  token.Pos,  []*TypeParam,  []Type,  []ast.Expr) {
	for ,  := range  {
		 := 
		if  < len() {
			 = [].Pos()
		}
		.assign(, , , [])
	}
}

// assign records that tpar was instantiated as targ at pos.
func ( *monoGraph) ( *Package,  token.Pos,  *TypeParam,  Type) {
	// Go generics do not have an analog to C++`s template-templates,
	// where a template parameter can itself be an instantiable
	// template. So any instantiation cycles must occur within a single
	// package. Accordingly, we can ignore instantiations of imported
	// type parameters.
	//
	// TODO(mdempsky): Push this check up into recordInstance? All type
	// parameters in a list will appear in the same package.
	if .Obj().Pkg() !=  {
		return
	}

	// flow adds an edge from vertex src representing that typ flows to tpar.
	 := func( int,  Type) {
		 := 1
		if  ==  {
			 = 0
		}

		.addEdge(.typeParamVertex(), , , , )
	}

	// Recursively walk the type argument to find any defined types or
	// type parameters.
	var  func( Type)
	 = func( Type) {
		switch typ := .(type) {
		default:
			panic("unexpected type")

		case *TypeParam:
			assert(.Obj().Pkg() == )
			(.typeParamVertex(), )

		case *Named:
			if  := .localNamedVertex(, .Origin());  >= 0 {
				(, )
			}

			 := .TypeArgs()
			for  := 0;  < .Len(); ++ {
				(.At())
			}

		case *Array:
			(.Elem())
		case *Basic:
			// ok
		case *Chan:
			(.Elem())
		case *Map:
			(.Key())
			(.Elem())
		case *Pointer:
			(.Elem())
		case *Slice:
			(.Elem())

		case *Interface:
			for  := 0;  < .NumMethods(); ++ {
				(.Method().Type())
			}
		case *Signature:
			 := func( *Tuple) {
				for  := 0;  < .Len(); ++ {
					(.At().Type())
				}
			}
			(.Params())
			(.Results())
		case *Struct:
			for  := 0;  < .NumFields(); ++ {
				(.Field().Type())
			}
		}
	}
	()
}

// localNamedVertex returns the index of the vertex representing
// named, or -1 if named doesn't need representation.
func ( *monoGraph) ( *Package,  *Named) int {
	 := .Obj()
	if .Pkg() !=  {
		return -1 // imported type
	}

	 := .Scope()
	if .Parent() ==  {
		return -1 // package scope, no ambient type parameters
	}

	if ,  := .nameIdx[];  {
		return 
	}

	 := -1

	// Walk the type definition's scope to find any ambient type
	// parameters that it's implicitly parameterized by.
	for  := .Parent();  != ;  = .Parent() {
		for ,  := range .elems {
			if ,  := .(*TypeName);  && !.IsAlias() && .Pos() < .Pos() {
				if ,  := .Type().(*TypeParam);  {
					if  < 0 {
						 = len(.vertices)
						.vertices = append(.vertices, monoVertex{obj: })
					}

					.addEdge(, .typeParamVertex(), 1, .Pos(), )
				}
			}
		}
	}

	if .nameIdx == nil {
		.nameIdx = make(map[*TypeName]int)
	}
	.nameIdx[] = 
	return 
}

// typeParamVertex returns the index of the vertex representing tpar.
func ( *monoGraph) ( *TypeParam) int {
	if ,  := .canon[];  {
		 = 
	}

	 := .Obj()

	if ,  := .nameIdx[];  {
		return 
	}

	if .nameIdx == nil {
		.nameIdx = make(map[*TypeName]int)
	}

	 := len(.vertices)
	.vertices = append(.vertices, monoVertex{obj: })
	.nameIdx[] = 
	return 
}

func ( *monoGraph) (, ,  int,  token.Pos,  Type) {
	// TODO(mdempsky): Deduplicate redundant edges?
	.edges = append(.edges, monoEdge{
		dst:    ,
		src:    ,
		weight: ,

		pos: ,
		typ: ,
	})
}