mono.go

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