unify.go

     1  // Copyright 2020 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  // This file implements type unification.
     6  //
     7  // Type unification attempts to make two types x and y structurally
     8  // equivalent by determining the types for a given list of (bound)
     9  // type parameters which may occur within x and y. If x and y are
    10  // structurally different (say []T vs chan T), or conflicting
    11  // types are determined for type parameters, unification fails.
    12  // If unification succeeds, as a side-effect, the types of the
    13  // bound type parameters may be determined.
    14  //
    15  // Unification typically requires multiple calls u.unify(x, y) to
    16  // a given unifier u, with various combinations of types x and y.
    17  // In each call, additional type parameter types may be determined
    18  // as a side effect and recorded in u.
    19  // If a call fails (returns false), unification fails.
    20  //
    21  // In the unification context, structural equivalence of two types
    22  // ignores the difference between a defined type and its underlying
    23  // type if one type is a defined type and the other one is not.
    24  // It also ignores the difference between an (external, unbound)
    25  // type parameter and its core type.
    26  // If two types are not structurally equivalent, they cannot be Go
    27  // identical types. On the other hand, if they are structurally
    28  // equivalent, they may be Go identical or at least assignable, or
    29  // they may be in the type set of a constraint.
    30  // Whether they indeed are identical or assignable is determined
    31  // upon instantiation and function argument passing.
    32  
    33  package types2
    34  
    35  import (
    36  	"bytes"
    37  	"fmt"
    38  	"sort"
    39  	"strings"
    40  )
    41  
    42  const (
    43  	// Upper limit for recursion depth. Used to catch infinite recursions
    44  	// due to implementation issues (e.g., see issues go.dev/issue/48619, go.dev/issue/48656).
    45  	unificationDepthLimit = 50
    46  
    47  	// Whether to panic when unificationDepthLimit is reached.
    48  	// If disabled, a recursion depth overflow results in a (quiet)
    49  	// unification failure.
    50  	panicAtUnificationDepthLimit = true
    51  
    52  	// If enableCoreTypeUnification is set, unification will consider
    53  	// the core types, if any, of non-local (unbound) type parameters.
    54  	enableCoreTypeUnification = true
    55  
    56  	// If traceInference is set, unification will print a trace of its operation.
    57  	// Interpretation of trace:
    58  	//   x ≡ y    attempt to unify types x and y
    59  	//   p ➞ y    type parameter p is set to type y (p is inferred to be y)
    60  	//   p ⇄ q    type parameters p and q match (p is inferred to be q and vice versa)
    61  	//   x ≢ y    types x and y cannot be unified
    62  	//   [p, q, ...] ➞ [x, y, ...]    mapping from type parameters to types
    63  	traceInference = false
    64  )
    65  
    66  // A unifier maintains a list of type parameters and
    67  // corresponding types inferred for each type parameter.
    68  // A unifier is created by calling newUnifier.
    69  type unifier struct {
    70  	// handles maps each type parameter to its inferred type through
    71  	// an indirection *Type called (inferred type) "handle".
    72  	// Initially, each type parameter has its own, separate handle,
    73  	// with a nil (i.e., not yet inferred) type.
    74  	// After a type parameter P is unified with a type parameter Q,
    75  	// P and Q share the same handle (and thus type). This ensures
    76  	// that inferring the type for a given type parameter P will
    77  	// automatically infer the same type for all other parameters
    78  	// unified (joined) with P.
    79  	handles                  map[*TypeParam]*Type
    80  	depth                    int  // recursion depth during unification
    81  	enableInterfaceInference bool // use shared methods for better inference
    82  }
    83  
    84  // newUnifier returns a new unifier initialized with the given type parameter
    85  // and corresponding type argument lists. The type argument list may be shorter
    86  // than the type parameter list, and it may contain nil types. Matching type
    87  // parameters and arguments must have the same index.
    88  func newUnifier(tparams []*TypeParam, targs []Type, enableInterfaceInference bool) *unifier {
    89  	assert(len(tparams) >= len(targs))
    90  	handles := make(map[*TypeParam]*Type, len(tparams))
    91  	// Allocate all handles up-front: in a correct program, all type parameters
    92  	// must be resolved and thus eventually will get a handle.
    93  	// Also, sharing of handles caused by unified type parameters is rare and
    94  	// so it's ok to not optimize for that case (and delay handle allocation).
    95  	for i, x := range tparams {
    96  		var t Type
    97  		if i < len(targs) {
    98  			t = targs[i]
    99  		}
   100  		handles[x] = &t
   101  	}
   102  	return &unifier{handles, 0, enableInterfaceInference}
   103  }
   104  
   105  // unifyMode controls the behavior of the unifier.
   106  type unifyMode uint
   107  
   108  const (
   109  	// If assign is set, we are unifying types involved in an assignment:
   110  	// they may match inexactly at the top, but element types must match
   111  	// exactly.
   112  	assign unifyMode = 1 << iota
   113  
   114  	// If exact is set, types unify if they are identical (or can be
   115  	// made identical with suitable arguments for type parameters).
   116  	// Otherwise, a named type and a type literal unify if their
   117  	// underlying types unify, channel directions are ignored, and
   118  	// if there is an interface, the other type must implement the
   119  	// interface.
   120  	exact
   121  )
   122  
   123  func (m unifyMode) String() string {
   124  	switch m {
   125  	case 0:
   126  		return "inexact"
   127  	case assign:
   128  		return "assign"
   129  	case exact:
   130  		return "exact"
   131  	case assign | exact:
   132  		return "assign, exact"
   133  	}
   134  	return fmt.Sprintf("mode %d", m)
   135  }
   136  
   137  // unify attempts to unify x and y and reports whether it succeeded.
   138  // As a side-effect, types may be inferred for type parameters.
   139  // The mode parameter controls how types are compared.
   140  func (u *unifier) unify(x, y Type, mode unifyMode) bool {
   141  	return u.nify(x, y, mode, nil)
   142  }
   143  
   144  func (u *unifier) tracef(format string, args ...interface{}) {
   145  	fmt.Println(strings.Repeat(".  ", u.depth) + sprintf(nil, true, format, args...))
   146  }
   147  
   148  // String returns a string representation of the current mapping
   149  // from type parameters to types.
   150  func (u *unifier) String() string {
   151  	// sort type parameters for reproducible strings
   152  	tparams := make(typeParamsById, len(u.handles))
   153  	i := 0
   154  	for tpar := range u.handles {
   155  		tparams[i] = tpar
   156  		i++
   157  	}
   158  	sort.Sort(tparams)
   159  
   160  	var buf bytes.Buffer
   161  	w := newTypeWriter(&buf, nil)
   162  	w.byte('[')
   163  	for i, x := range tparams {
   164  		if i > 0 {
   165  			w.string(", ")
   166  		}
   167  		w.typ(x)
   168  		w.string(": ")
   169  		w.typ(u.at(x))
   170  	}
   171  	w.byte(']')
   172  	return buf.String()
   173  }
   174  
   175  type typeParamsById []*TypeParam
   176  
   177  func (s typeParamsById) Len() int           { return len(s) }
   178  func (s typeParamsById) Less(i, j int) bool { return s[i].id < s[j].id }
   179  func (s typeParamsById) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   180  
   181  // join unifies the given type parameters x and y.
   182  // If both type parameters already have a type associated with them
   183  // and they are not joined, join fails and returns false.
   184  func (u *unifier) join(x, y *TypeParam) bool {
   185  	if traceInference {
   186  		u.tracef("%s ⇄ %s", x, y)
   187  	}
   188  	switch hx, hy := u.handles[x], u.handles[y]; {
   189  	case hx == hy:
   190  		// Both type parameters already share the same handle. Nothing to do.
   191  	case *hx != nil && *hy != nil:
   192  		// Both type parameters have (possibly different) inferred types. Cannot join.
   193  		return false
   194  	case *hx != nil:
   195  		// Only type parameter x has an inferred type. Use handle of x.
   196  		u.setHandle(y, hx)
   197  	// This case is treated like the default case.
   198  	// case *hy != nil:
   199  	// 	// Only type parameter y has an inferred type. Use handle of y.
   200  	//	u.setHandle(x, hy)
   201  	default:
   202  		// Neither type parameter has an inferred type. Use handle of y.
   203  		u.setHandle(x, hy)
   204  	}
   205  	return true
   206  }
   207  
   208  // asTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u.
   209  // Otherwise, the result is nil.
   210  func (u *unifier) asTypeParam(x Type) *TypeParam {
   211  	if x, _ := x.(*TypeParam); x != nil {
   212  		if _, found := u.handles[x]; found {
   213  			return x
   214  		}
   215  	}
   216  	return nil
   217  }
   218  
   219  // setHandle sets the handle for type parameter x
   220  // (and all its joined type parameters) to h.
   221  func (u *unifier) setHandle(x *TypeParam, h *Type) {
   222  	hx := u.handles[x]
   223  	assert(hx != nil)
   224  	for y, hy := range u.handles {
   225  		if hy == hx {
   226  			u.handles[y] = h
   227  		}
   228  	}
   229  }
   230  
   231  // at returns the (possibly nil) type for type parameter x.
   232  func (u *unifier) at(x *TypeParam) Type {
   233  	return *u.handles[x]
   234  }
   235  
   236  // set sets the type t for type parameter x;
   237  // t must not be nil.
   238  func (u *unifier) set(x *TypeParam, t Type) {
   239  	assert(t != nil)
   240  	if traceInference {
   241  		u.tracef("%s ➞ %s", x, t)
   242  	}
   243  	*u.handles[x] = t
   244  }
   245  
   246  // unknowns returns the number of type parameters for which no type has been set yet.
   247  func (u *unifier) unknowns() int {
   248  	n := 0
   249  	for _, h := range u.handles {
   250  		if *h == nil {
   251  			n++
   252  		}
   253  	}
   254  	return n
   255  }
   256  
   257  // inferred returns the list of inferred types for the given type parameter list.
   258  // The result is never nil and has the same length as tparams; result types that
   259  // could not be inferred are nil. Corresponding type parameters and result types
   260  // have identical indices.
   261  func (u *unifier) inferred(tparams []*TypeParam) []Type {
   262  	list := make([]Type, len(tparams))
   263  	for i, x := range tparams {
   264  		list[i] = u.at(x)
   265  	}
   266  	return list
   267  }
   268  
   269  // asInterface returns the underlying type of x as an interface if
   270  // it is a non-type parameter interface. Otherwise it returns nil.
   271  func asInterface(x Type) (i *Interface) {
   272  	if _, ok := x.(*TypeParam); !ok {
   273  		i, _ = under(x).(*Interface)
   274  	}
   275  	return i
   276  }
   277  
   278  // nify implements the core unification algorithm which is an
   279  // adapted version of Checker.identical. For changes to that
   280  // code the corresponding changes should be made here.
   281  // Must not be called directly from outside the unifier.
   282  func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
   283  	u.depth++
   284  	if traceInference {
   285  		u.tracef("%s ≡ %s\t// %s", x, y, mode)
   286  	}
   287  	defer func() {
   288  		if traceInference && !result {
   289  			u.tracef("%s ≢ %s", x, y)
   290  		}
   291  		u.depth--
   292  	}()
   293  
   294  	x = Unalias(x)
   295  	y = Unalias(y)
   296  
   297  	// nothing to do if x == y
   298  	if x == y {
   299  		return true
   300  	}
   301  
   302  	// Stop gap for cases where unification fails.
   303  	if u.depth > unificationDepthLimit {
   304  		if traceInference {
   305  			u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
   306  		}
   307  		if panicAtUnificationDepthLimit {
   308  			panic("unification reached recursion depth limit")
   309  		}
   310  		return false
   311  	}
   312  
   313  	// Unification is symmetric, so we can swap the operands.
   314  	// Ensure that if we have at least one
   315  	// - defined type, make sure one is in y
   316  	// - type parameter recorded with u, make sure one is in x
   317  	if asNamed(x) != nil || u.asTypeParam(y) != nil {
   318  		if traceInference {
   319  			u.tracef("%s ≡ %s\t// swap", y, x)
   320  		}
   321  		x, y = y, x
   322  	}
   323  
   324  	// Unification will fail if we match a defined type against a type literal.
   325  	// If we are matching types in an assignment, at the top-level, types with
   326  	// the same type structure are permitted as long as at least one of them
   327  	// is not a defined type. To accommodate for that possibility, we continue
   328  	// unification with the underlying type of a defined type if the other type
   329  	// is a type literal. This is controlled by the exact unification mode.
   330  	// We also continue if the other type is a basic type because basic types
   331  	// are valid underlying types and may appear as core types of type constraints.
   332  	// If we exclude them, inferred defined types for type parameters may not
   333  	// match against the core types of their constraints (even though they might
   334  	// correctly match against some of the types in the constraint's type set).
   335  	// Finally, if unification (incorrectly) succeeds by matching the underlying
   336  	// type of a defined type against a basic type (because we include basic types
   337  	// as type literals here), and if that leads to an incorrectly inferred type,
   338  	// we will fail at function instantiation or argument assignment time.
   339  	//
   340  	// If we have at least one defined type, there is one in y.
   341  	if ny := asNamed(y); mode&exact == 0 && ny != nil && isTypeLit(x) && !(u.enableInterfaceInference && IsInterface(x)) {
   342  		if traceInference {
   343  			u.tracef("%s ≡ under %s", x, ny)
   344  		}
   345  		y = ny.under()
   346  		// Per the spec, a defined type cannot have an underlying type
   347  		// that is a type parameter.
   348  		assert(!isTypeParam(y))
   349  		// x and y may be identical now
   350  		if x == y {
   351  			return true
   352  		}
   353  	}
   354  
   355  	// Cases where at least one of x or y is a type parameter recorded with u.
   356  	// If we have at least one type parameter, there is one in x.
   357  	// If we have exactly one type parameter, because it is in x,
   358  	// isTypeLit(x) is false and y was not changed above. In other
   359  	// words, if y was a defined type, it is still a defined type
   360  	// (relevant for the logic below).
   361  	switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
   362  	case px != nil && py != nil:
   363  		// both x and y are type parameters
   364  		if u.join(px, py) {
   365  			return true
   366  		}
   367  		// both x and y have an inferred type - they must match
   368  		return u.nify(u.at(px), u.at(py), mode, p)
   369  
   370  	case px != nil:
   371  		// x is a type parameter, y is not
   372  		if x := u.at(px); x != nil {
   373  			// x has an inferred type which must match y
   374  			if u.nify(x, y, mode, p) {
   375  				// We have a match, possibly through underlying types.
   376  				xi := asInterface(x)
   377  				yi := asInterface(y)
   378  				xn := asNamed(x) != nil
   379  				yn := asNamed(y) != nil
   380  				// If we have two interfaces, what to do depends on
   381  				// whether they are named and their method sets.
   382  				if xi != nil && yi != nil {
   383  					// Both types are interfaces.
   384  					// If both types are defined types, they must be identical
   385  					// because unification doesn't know which type has the "right" name.
   386  					if xn && yn {
   387  						return Identical(x, y)
   388  					}
   389  					// In all other cases, the method sets must match.
   390  					// The types unified so we know that corresponding methods
   391  					// match and we can simply compare the number of methods.
   392  					// TODO(gri) We may be able to relax this rule and select
   393  					// the more general interface. But if one of them is a defined
   394  					// type, it's not clear how to choose and whether we introduce
   395  					// an order dependency or not. Requiring the same method set
   396  					// is conservative.
   397  					if len(xi.typeSet().methods) != len(yi.typeSet().methods) {
   398  						return false
   399  					}
   400  				} else if xi != nil || yi != nil {
   401  					// One but not both of them are interfaces.
   402  					// In this case, either x or y could be viable matches for the corresponding
   403  					// type parameter, which means choosing either introduces an order dependence.
   404  					// Therefore, we must fail unification (go.dev/issue/60933).
   405  					return false
   406  				}
   407  				// If we have inexact unification and one of x or y is a defined type, select the
   408  				// defined type. This ensures that in a series of types, all matching against the
   409  				// same type parameter, we infer a defined type if there is one, independent of
   410  				// order. Type inference or assignment may fail, which is ok.
   411  				// Selecting a defined type, if any, ensures that we don't lose the type name;
   412  				// and since we have inexact unification, a value of equally named or matching
   413  				// undefined type remains assignable (go.dev/issue/43056).
   414  				//
   415  				// Similarly, if we have inexact unification and there are no defined types but
   416  				// channel types, select a directed channel, if any. This ensures that in a series
   417  				// of unnamed types, all matching against the same type parameter, we infer the
   418  				// directed channel if there is one, independent of order.
   419  				// Selecting a directional channel, if any, ensures that a value of another
   420  				// inexactly unifying channel type remains assignable (go.dev/issue/62157).
   421  				//
   422  				// If we have multiple defined channel types, they are either identical or we
   423  				// have assignment conflicts, so we can ignore directionality in this case.
   424  				//
   425  				// If we have defined and literal channel types, a defined type wins to avoid
   426  				// order dependencies.
   427  				if mode&exact == 0 {
   428  					switch {
   429  					case xn:
   430  						// x is a defined type: nothing to do.
   431  					case yn:
   432  						// x is not a defined type and y is a defined type: select y.
   433  						u.set(px, y)
   434  					default:
   435  						// Neither x nor y are defined types.
   436  						if yc, _ := under(y).(*Chan); yc != nil && yc.dir != SendRecv {
   437  							// y is a directed channel type: select y.
   438  							u.set(px, y)
   439  						}
   440  					}
   441  				}
   442  				return true
   443  			}
   444  			return false
   445  		}
   446  		// otherwise, infer type from y
   447  		u.set(px, y)
   448  		return true
   449  	}
   450  
   451  	// x != y if we get here
   452  	assert(x != y)
   453  
   454  	// If u.EnableInterfaceInference is set and we don't require exact unification,
   455  	// if both types are interfaces, one interface must have a subset of the
   456  	// methods of the other and corresponding method signatures must unify.
   457  	// If only one type is an interface, all its methods must be present in the
   458  	// other type and corresponding method signatures must unify.
   459  	if u.enableInterfaceInference && mode&exact == 0 {
   460  		// One or both interfaces may be defined types.
   461  		// Look under the name, but not under type parameters (go.dev/issue/60564).
   462  		xi := asInterface(x)
   463  		yi := asInterface(y)
   464  		// If we have two interfaces, check the type terms for equivalence,
   465  		// and unify common methods if possible.
   466  		if xi != nil && yi != nil {
   467  			xset := xi.typeSet()
   468  			yset := yi.typeSet()
   469  			if xset.comparable != yset.comparable {
   470  				return false
   471  			}
   472  			// For now we require terms to be equal.
   473  			// We should be able to relax this as well, eventually.
   474  			if !xset.terms.equal(yset.terms) {
   475  				return false
   476  			}
   477  			// Interface types are the only types where cycles can occur
   478  			// that are not "terminated" via named types; and such cycles
   479  			// can only be created via method parameter types that are
   480  			// anonymous interfaces (directly or indirectly) embedding
   481  			// the current interface. Example:
   482  			//
   483  			//    type T interface {
   484  			//        m() interface{T}
   485  			//    }
   486  			//
   487  			// If two such (differently named) interfaces are compared,
   488  			// endless recursion occurs if the cycle is not detected.
   489  			//
   490  			// If x and y were compared before, they must be equal
   491  			// (if they were not, the recursion would have stopped);
   492  			// search the ifacePair stack for the same pair.
   493  			//
   494  			// This is a quadratic algorithm, but in practice these stacks
   495  			// are extremely short (bounded by the nesting depth of interface
   496  			// type declarations that recur via parameter types, an extremely
   497  			// rare occurrence). An alternative implementation might use a
   498  			// "visited" map, but that is probably less efficient overall.
   499  			q := &ifacePair{xi, yi, p}
   500  			for p != nil {
   501  				if p.identical(q) {
   502  					return true // same pair was compared before
   503  				}
   504  				p = p.prev
   505  			}
   506  			// The method set of x must be a subset of the method set
   507  			// of y or vice versa, and the common methods must unify.
   508  			xmethods := xset.methods
   509  			ymethods := yset.methods
   510  			// The smaller method set must be the subset, if it exists.
   511  			if len(xmethods) > len(ymethods) {
   512  				xmethods, ymethods = ymethods, xmethods
   513  			}
   514  			// len(xmethods) <= len(ymethods)
   515  			// Collect the ymethods in a map for quick lookup.
   516  			ymap := make(map[string]*Func, len(ymethods))
   517  			for _, ym := range ymethods {
   518  				ymap[ym.Id()] = ym
   519  			}
   520  			// All xmethods must exist in ymethods and corresponding signatures must unify.
   521  			for _, xm := range xmethods {
   522  				if ym := ymap[xm.Id()]; ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
   523  					return false
   524  				}
   525  			}
   526  			return true
   527  		}
   528  
   529  		// We don't have two interfaces. If we have one, make sure it's in xi.
   530  		if yi != nil {
   531  			xi = yi
   532  			y = x
   533  		}
   534  
   535  		// If we have one interface, at a minimum each of the interface methods
   536  		// must be implemented and thus unify with a corresponding method from
   537  		// the non-interface type, otherwise unification fails.
   538  		if xi != nil {
   539  			// All xi methods must exist in y and corresponding signatures must unify.
   540  			xmethods := xi.typeSet().methods
   541  			for _, xm := range xmethods {
   542  				obj, _, _ := LookupFieldOrMethod(y, false, xm.pkg, xm.name)
   543  				if ym, _ := obj.(*Func); ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
   544  					return false
   545  				}
   546  			}
   547  			return true
   548  		}
   549  	}
   550  
   551  	// Unless we have exact unification, neither x nor y are interfaces now.
   552  	// Except for unbound type parameters (see below), x and y must be structurally
   553  	// equivalent to unify.
   554  
   555  	// If we get here and x or y is a type parameter, they are unbound
   556  	// (not recorded with the unifier).
   557  	// Ensure that if we have at least one type parameter, it is in x
   558  	// (the earlier swap checks for _recorded_ type parameters only).
   559  	// This ensures that the switch switches on the type parameter.
   560  	//
   561  	// TODO(gri) Factor out type parameter handling from the switch.
   562  	if isTypeParam(y) {
   563  		if traceInference {
   564  			u.tracef("%s ≡ %s\t// swap", y, x)
   565  		}
   566  		x, y = y, x
   567  	}
   568  
   569  	// Type elements (array, slice, etc. elements) use emode for unification.
   570  	// Element types must match exactly if the types are used in an assignment.
   571  	emode := mode
   572  	if mode&assign != 0 {
   573  		emode |= exact
   574  	}
   575  
   576  	switch x := x.(type) {
   577  	case *Basic:
   578  		// Basic types are singletons except for the rune and byte
   579  		// aliases, thus we cannot solely rely on the x == y check
   580  		// above. See also comment in TypeName.IsAlias.
   581  		if y, ok := y.(*Basic); ok {
   582  			return x.kind == y.kind
   583  		}
   584  
   585  	case *Array:
   586  		// Two array types unify if they have the same array length
   587  		// and their element types unify.
   588  		if y, ok := y.(*Array); ok {
   589  			// If one or both array lengths are unknown (< 0) due to some error,
   590  			// assume they are the same to avoid spurious follow-on errors.
   591  			return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, emode, p)
   592  		}
   593  
   594  	case *Slice:
   595  		// Two slice types unify if their element types unify.
   596  		if y, ok := y.(*Slice); ok {
   597  			return u.nify(x.elem, y.elem, emode, p)
   598  		}
   599  
   600  	case *Struct:
   601  		// Two struct types unify if they have the same sequence of fields,
   602  		// and if corresponding fields have the same names, their (field) types unify,
   603  		// and they have identical tags. Two embedded fields are considered to have the same
   604  		// name. Lower-case field names from different packages are always different.
   605  		if y, ok := y.(*Struct); ok {
   606  			if x.NumFields() == y.NumFields() {
   607  				for i, f := range x.fields {
   608  					g := y.fields[i]
   609  					if f.embedded != g.embedded ||
   610  						x.Tag(i) != y.Tag(i) ||
   611  						!f.sameId(g.pkg, g.name) ||
   612  						!u.nify(f.typ, g.typ, emode, p) {
   613  						return false
   614  					}
   615  				}
   616  				return true
   617  			}
   618  		}
   619  
   620  	case *Pointer:
   621  		// Two pointer types unify if their base types unify.
   622  		if y, ok := y.(*Pointer); ok {
   623  			return u.nify(x.base, y.base, emode, p)
   624  		}
   625  
   626  	case *Tuple:
   627  		// Two tuples types unify if they have the same number of elements
   628  		// and the types of corresponding elements unify.
   629  		if y, ok := y.(*Tuple); ok {
   630  			if x.Len() == y.Len() {
   631  				if x != nil {
   632  					for i, v := range x.vars {
   633  						w := y.vars[i]
   634  						if !u.nify(v.typ, w.typ, mode, p) {
   635  							return false
   636  						}
   637  					}
   638  				}
   639  				return true
   640  			}
   641  		}
   642  
   643  	case *Signature:
   644  		// Two function types unify if they have the same number of parameters
   645  		// and result values, corresponding parameter and result types unify,
   646  		// and either both functions are variadic or neither is.
   647  		// Parameter and result names are not required to match.
   648  		// TODO(gri) handle type parameters or document why we can ignore them.
   649  		if y, ok := y.(*Signature); ok {
   650  			return x.variadic == y.variadic &&
   651  				u.nify(x.params, y.params, emode, p) &&
   652  				u.nify(x.results, y.results, emode, p)
   653  		}
   654  
   655  	case *Interface:
   656  		assert(!u.enableInterfaceInference || mode&exact != 0) // handled before this switch
   657  
   658  		// Two interface types unify if they have the same set of methods with
   659  		// the same names, and corresponding function types unify.
   660  		// Lower-case method names from different packages are always different.
   661  		// The order of the methods is irrelevant.
   662  		if y, ok := y.(*Interface); ok {
   663  			xset := x.typeSet()
   664  			yset := y.typeSet()
   665  			if xset.comparable != yset.comparable {
   666  				return false
   667  			}
   668  			if !xset.terms.equal(yset.terms) {
   669  				return false
   670  			}
   671  			a := xset.methods
   672  			b := yset.methods
   673  			if len(a) == len(b) {
   674  				// Interface types are the only types where cycles can occur
   675  				// that are not "terminated" via named types; and such cycles
   676  				// can only be created via method parameter types that are
   677  				// anonymous interfaces (directly or indirectly) embedding
   678  				// the current interface. Example:
   679  				//
   680  				//    type T interface {
   681  				//        m() interface{T}
   682  				//    }
   683  				//
   684  				// If two such (differently named) interfaces are compared,
   685  				// endless recursion occurs if the cycle is not detected.
   686  				//
   687  				// If x and y were compared before, they must be equal
   688  				// (if they were not, the recursion would have stopped);
   689  				// search the ifacePair stack for the same pair.
   690  				//
   691  				// This is a quadratic algorithm, but in practice these stacks
   692  				// are extremely short (bounded by the nesting depth of interface
   693  				// type declarations that recur via parameter types, an extremely
   694  				// rare occurrence). An alternative implementation might use a
   695  				// "visited" map, but that is probably less efficient overall.
   696  				q := &ifacePair{x, y, p}
   697  				for p != nil {
   698  					if p.identical(q) {
   699  						return true // same pair was compared before
   700  					}
   701  					p = p.prev
   702  				}
   703  				if debug {
   704  					assertSortedMethods(a)
   705  					assertSortedMethods(b)
   706  				}
   707  				for i, f := range a {
   708  					g := b[i]
   709  					if f.Id() != g.Id() || !u.nify(f.typ, g.typ, exact, q) {
   710  						return false
   711  					}
   712  				}
   713  				return true
   714  			}
   715  		}
   716  
   717  	case *Map:
   718  		// Two map types unify if their key and value types unify.
   719  		if y, ok := y.(*Map); ok {
   720  			return u.nify(x.key, y.key, emode, p) && u.nify(x.elem, y.elem, emode, p)
   721  		}
   722  
   723  	case *Chan:
   724  		// Two channel types unify if their value types unify
   725  		// and if they have the same direction.
   726  		// The channel direction is ignored for inexact unification.
   727  		if y, ok := y.(*Chan); ok {
   728  			return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p)
   729  		}
   730  
   731  	case *Named:
   732  		// Two named types unify if their type names originate in the same type declaration.
   733  		// If they are instantiated, their type argument lists must unify.
   734  		if y := asNamed(y); y != nil {
   735  			// Check type arguments before origins so they unify
   736  			// even if the origins don't match; for better error
   737  			// messages (see go.dev/issue/53692).
   738  			xargs := x.TypeArgs().list()
   739  			yargs := y.TypeArgs().list()
   740  			if len(xargs) != len(yargs) {
   741  				return false
   742  			}
   743  			for i, xarg := range xargs {
   744  				if !u.nify(xarg, yargs[i], mode, p) {
   745  					return false
   746  				}
   747  			}
   748  			return identicalOrigin(x, y)
   749  		}
   750  
   751  	case *TypeParam:
   752  		// x must be an unbound type parameter (see comment above).
   753  		if debug {
   754  			assert(u.asTypeParam(x) == nil)
   755  		}
   756  		// By definition, a valid type argument must be in the type set of
   757  		// the respective type constraint. Therefore, the type argument's
   758  		// underlying type must be in the set of underlying types of that
   759  		// constraint. If there is a single such underlying type, it's the
   760  		// constraint's core type. It must match the type argument's under-
   761  		// lying type, irrespective of whether the actual type argument,
   762  		// which may be a defined type, is actually in the type set (that
   763  		// will be determined at instantiation time).
   764  		// Thus, if we have the core type of an unbound type parameter,
   765  		// we know the structure of the possible types satisfying such
   766  		// parameters. Use that core type for further unification
   767  		// (see go.dev/issue/50755 for a test case).
   768  		if enableCoreTypeUnification {
   769  			// Because the core type is always an underlying type,
   770  			// unification will take care of matching against a
   771  			// defined or literal type automatically.
   772  			// If y is also an unbound type parameter, we will end
   773  			// up here again with x and y swapped, so we don't
   774  			// need to take care of that case separately.
   775  			if cx := coreType(x); cx != nil {
   776  				if traceInference {
   777  					u.tracef("core %s ≡ %s", x, y)
   778  				}
   779  				// If y is a defined type, it may not match against cx which
   780  				// is an underlying type (incl. int, string, etc.). Use assign
   781  				// mode here so that the unifier automatically takes under(y)
   782  				// if necessary.
   783  				return u.nify(cx, y, assign, p)
   784  			}
   785  		}
   786  		// x != y and there's nothing to do
   787  
   788  	case nil:
   789  		// avoid a crash in case of nil type
   790  
   791  	default:
   792  		panic(sprintf(nil, true, "u.nify(%s, %s, %d)", x, y, mode))
   793  	}
   794  
   795  	return false
   796  }
   797
View as plain text