mono.go

     1  // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
     2  // Source: ../../cmd/compile/internal/types2/mono.go
     3  
     4  // Copyright 2021 The Go Authors. All rights reserved.
     5  // Use of this source code is governed by a BSD-style
     6  // license that can be found in the LICENSE file.
     7  
     8  package types
     9  
    10  import (
    11  	"go/ast"
    12  	"go/token"
    13  	. "internal/types/errors"
    14  )
    15  
    16  // This file implements a check to validate that a Go package doesn't
    17  // have unbounded recursive instantiation, which is not compatible
    18  // with compilers using static instantiation (such as
    19  // monomorphization).
    20  //
    21  // It implements a sort of "type flow" analysis by detecting which
    22  // type parameters are instantiated with other type parameters (or
    23  // types derived thereof). A package cannot be statically instantiated
    24  // if the graph has any cycles involving at least one derived type.
    25  //
    26  // Concretely, we construct a directed, weighted graph. Vertices are
    27  // used to represent type parameters as well as some defined
    28  // types. Edges are used to represent how types depend on each other:
    29  //
    30  // * Everywhere a type-parameterized function or type is instantiated,
    31  //   we add edges to each type parameter from the vertices (if any)
    32  //   representing each type parameter or defined type referenced by
    33  //   the type argument. If the type argument is just the referenced
    34  //   type itself, then the edge has weight 0, otherwise 1.
    35  //
    36  // * For every defined type declared within a type-parameterized
    37  //   function or method, we add an edge of weight 1 to the defined
    38  //   type from each ambient type parameter.
    39  //
    40  // For example, given:
    41  //
    42  //	func f[A, B any]() {
    43  //		type T int
    44  //		f[T, map[A]B]()
    45  //	}
    46  //
    47  // we construct vertices representing types A, B, and T. Because of
    48  // declaration "type T int", we construct edges T<-A and T<-B with
    49  // weight 1; and because of instantiation "f[T, map[A]B]" we construct
    50  // edges A<-T with weight 0, and B<-A and B<-B with weight 1.
    51  //
    52  // Finally, we look for any positive-weight cycles. Zero-weight cycles
    53  // are allowed because static instantiation will reach a fixed point.
    54  
    55  type monoGraph struct {
    56  	vertices []monoVertex
    57  	edges    []monoEdge
    58  
    59  	// canon maps method receiver type parameters to their respective
    60  	// receiver type's type parameters.
    61  	canon map[*TypeParam]*TypeParam
    62  
    63  	// nameIdx maps a defined type or (canonical) type parameter to its
    64  	// vertex index.
    65  	nameIdx map[*TypeName]int
    66  }
    67  
    68  type monoVertex struct {
    69  	weight int // weight of heaviest known path to this vertex
    70  	pre    int // previous edge (if any) in the above path
    71  	len    int // length of the above path
    72  
    73  	// obj is the defined type or type parameter represented by this
    74  	// vertex.
    75  	obj *TypeName
    76  }
    77  
    78  type monoEdge struct {
    79  	dst, src int
    80  	weight   int
    81  
    82  	pos token.Pos
    83  	typ Type
    84  }
    85  
    86  func (check *Checker) monomorph() {
    87  	// We detect unbounded instantiation cycles using a variant of
    88  	// Bellman-Ford's algorithm. Namely, instead of always running |V|
    89  	// iterations, we run until we either reach a fixed point or we've
    90  	// found a path of length |V|. This allows us to terminate earlier
    91  	// when there are no cycles, which should be the common case.
    92  
    93  	again := true
    94  	for again {
    95  		again = false
    96  
    97  		for i, edge := range check.mono.edges {
    98  			src := &check.mono.vertices[edge.src]
    99  			dst := &check.mono.vertices[edge.dst]
   100  
   101  			// N.B., we're looking for the greatest weight paths, unlike
   102  			// typical Bellman-Ford.
   103  			w := src.weight + edge.weight
   104  			if w <= dst.weight {
   105  				continue
   106  			}
   107  
   108  			dst.pre = i
   109  			dst.len = src.len + 1
   110  			if dst.len == len(check.mono.vertices) {
   111  				check.reportInstanceLoop(edge.dst)
   112  				return
   113  			}
   114  
   115  			dst.weight = w
   116  			again = true
   117  		}
   118  	}
   119  }
   120  
   121  func (check *Checker) reportInstanceLoop(v int) {
   122  	var stack []int
   123  	seen := make([]bool, len(check.mono.vertices))
   124  
   125  	// We have a path that contains a cycle and ends at v, but v may
   126  	// only be reachable from the cycle, not on the cycle itself. We
   127  	// start by walking backwards along the path until we find a vertex
   128  	// that appears twice.
   129  	for !seen[v] {
   130  		stack = append(stack, v)
   131  		seen[v] = true
   132  		v = check.mono.edges[check.mono.vertices[v].pre].src
   133  	}
   134  
   135  	// Trim any vertices we visited before visiting v the first
   136  	// time. Since v is the first vertex we found within the cycle, any
   137  	// vertices we visited earlier cannot be part of the cycle.
   138  	for stack[0] != v {
   139  		stack = stack[1:]
   140  	}
   141  
   142  	// TODO(mdempsky): Pivot stack so we report the cycle from the top?
   143  
   144  	err := check.newError(InvalidInstanceCycle)
   145  	obj0 := check.mono.vertices[v].obj
   146  	err.addf(obj0, "instantiation cycle:")
   147  
   148  	qf := RelativeTo(check.pkg)
   149  	for _, v := range stack {
   150  		edge := check.mono.edges[check.mono.vertices[v].pre]
   151  		obj := check.mono.vertices[edge.dst].obj
   152  
   153  		switch obj.Type().(type) {
   154  		default:
   155  			panic("unexpected type")
   156  		case *Named:
   157  			err.addf(atPos(edge.pos), "%s implicitly parameterized by %s", obj.Name(), TypeString(edge.typ, qf)) // secondary error, \t indented
   158  		case *TypeParam:
   159  			err.addf(atPos(edge.pos), "%s instantiated as %s", obj.Name(), TypeString(edge.typ, qf)) // secondary error, \t indented
   160  		}
   161  	}
   162  	err.report()
   163  }
   164  
   165  // recordCanon records that tpar is the canonical type parameter
   166  // corresponding to method type parameter mpar.
   167  func (w *monoGraph) recordCanon(mpar, tpar *TypeParam) {
   168  	if w.canon == nil {
   169  		w.canon = make(map[*TypeParam]*TypeParam)
   170  	}
   171  	w.canon[mpar] = tpar
   172  }
   173  
   174  // recordInstance records that the given type parameters were
   175  // instantiated with the corresponding type arguments.
   176  func (w *monoGraph) recordInstance(pkg *Package, pos token.Pos, tparams []*TypeParam, targs []Type, xlist []ast.Expr) {
   177  	for i, tpar := range tparams {
   178  		pos := pos
   179  		if i < len(xlist) {
   180  			pos = startPos(xlist[i])
   181  		}
   182  		w.assign(pkg, pos, tpar, targs[i])
   183  	}
   184  }
   185  
   186  // assign records that tpar was instantiated as targ at pos.
   187  func (w *monoGraph) assign(pkg *Package, pos token.Pos, tpar *TypeParam, targ Type) {
   188  	// Go generics do not have an analog to C++`s template-templates,
   189  	// where a template parameter can itself be an instantiable
   190  	// template. So any instantiation cycles must occur within a single
   191  	// package. Accordingly, we can ignore instantiations of imported
   192  	// type parameters.
   193  	//
   194  	// TODO(mdempsky): Push this check up into recordInstance? All type
   195  	// parameters in a list will appear in the same package.
   196  	if tpar.Obj().Pkg() != pkg {
   197  		return
   198  	}
   199  
   200  	// flow adds an edge from vertex src representing that typ flows to tpar.
   201  	flow := func(src int, typ Type) {
   202  		weight := 1
   203  		if typ == targ {
   204  			weight = 0
   205  		}
   206  
   207  		w.addEdge(w.typeParamVertex(tpar), src, weight, pos, targ)
   208  	}
   209  
   210  	// Recursively walk the type argument to find any defined types or
   211  	// type parameters.
   212  	var do func(typ Type)
   213  	do = func(typ Type) {
   214  		switch typ := Unalias(typ).(type) {
   215  		default:
   216  			panic("unexpected type")
   217  
   218  		case *TypeParam:
   219  			assert(typ.Obj().Pkg() == pkg)
   220  			flow(w.typeParamVertex(typ), typ)
   221  
   222  		case *Named:
   223  			if src := w.localNamedVertex(pkg, typ.Origin()); src >= 0 {
   224  				flow(src, typ)
   225  			}
   226  
   227  			targs := typ.TypeArgs()
   228  			for i := 0; i < targs.Len(); i++ {
   229  				do(targs.At(i))
   230  			}
   231  
   232  		case *Array:
   233  			do(typ.Elem())
   234  		case *Basic:
   235  			// ok
   236  		case *Chan:
   237  			do(typ.Elem())
   238  		case *Map:
   239  			do(typ.Key())
   240  			do(typ.Elem())
   241  		case *Pointer:
   242  			do(typ.Elem())
   243  		case *Slice:
   244  			do(typ.Elem())
   245  
   246  		case *Interface:
   247  			for i := 0; i < typ.NumMethods(); i++ {
   248  				do(typ.Method(i).Type())
   249  			}
   250  		case *Signature:
   251  			tuple := func(tup *Tuple) {
   252  				for i := 0; i < tup.Len(); i++ {
   253  					do(tup.At(i).Type())
   254  				}
   255  			}
   256  			tuple(typ.Params())
   257  			tuple(typ.Results())
   258  		case *Struct:
   259  			for i := 0; i < typ.NumFields(); i++ {
   260  				do(typ.Field(i).Type())
   261  			}
   262  		}
   263  	}
   264  	do(targ)
   265  }
   266  
   267  // localNamedVertex returns the index of the vertex representing
   268  // named, or -1 if named doesn't need representation.
   269  func (w *monoGraph) localNamedVertex(pkg *Package, named *Named) int {
   270  	obj := named.Obj()
   271  	if obj.Pkg() != pkg {
   272  		return -1 // imported type
   273  	}
   274  
   275  	root := pkg.Scope()
   276  	if obj.Parent() == root {
   277  		return -1 // package scope, no ambient type parameters
   278  	}
   279  
   280  	if idx, ok := w.nameIdx[obj]; ok {
   281  		return idx
   282  	}
   283  
   284  	idx := -1
   285  
   286  	// Walk the type definition's scope to find any ambient type
   287  	// parameters that it's implicitly parameterized by.
   288  	for scope := obj.Parent(); scope != root; scope = scope.Parent() {
   289  		for _, elem := range scope.elems {
   290  			if elem, ok := elem.(*TypeName); ok && !elem.IsAlias() && cmpPos(elem.Pos(), obj.Pos()) < 0 {
   291  				if tpar, ok := elem.Type().(*TypeParam); ok {
   292  					if idx < 0 {
   293  						idx = len(w.vertices)
   294  						w.vertices = append(w.vertices, monoVertex{obj: obj})
   295  					}
   296  
   297  					w.addEdge(idx, w.typeParamVertex(tpar), 1, obj.Pos(), tpar)
   298  				}
   299  			}
   300  		}
   301  	}
   302  
   303  	if w.nameIdx == nil {
   304  		w.nameIdx = make(map[*TypeName]int)
   305  	}
   306  	w.nameIdx[obj] = idx
   307  	return idx
   308  }
   309  
   310  // typeParamVertex returns the index of the vertex representing tpar.
   311  func (w *monoGraph) typeParamVertex(tpar *TypeParam) int {
   312  	if x, ok := w.canon[tpar]; ok {
   313  		tpar = x
   314  	}
   315  
   316  	obj := tpar.Obj()
   317  
   318  	if idx, ok := w.nameIdx[obj]; ok {
   319  		return idx
   320  	}
   321  
   322  	if w.nameIdx == nil {
   323  		w.nameIdx = make(map[*TypeName]int)
   324  	}
   325  
   326  	idx := len(w.vertices)
   327  	w.vertices = append(w.vertices, monoVertex{obj: obj})
   328  	w.nameIdx[obj] = idx
   329  	return idx
   330  }
   331  
   332  func (w *monoGraph) addEdge(dst, src, weight int, pos token.Pos, typ Type) {
   333  	// TODO(mdempsky): Deduplicate redundant edges?
   334  	w.edges = append(w.edges, monoEdge{
   335  		dst:    dst,
   336  		src:    src,
   337  		weight: weight,
   338  
   339  		pos: pos,
   340  		typ: typ,
   341  	})
   342  }
   343
View as plain text