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  // asBoundTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u.
   209  // Otherwise, the result is nil.
   210  func (u *unifier) asBoundTypeParam(x Type) *TypeParam {
   211  	if x, _ := Unalias(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 := Unalias(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  	// nothing to do if x == y
   295  	if x == y || Unalias(x) == Unalias(y) {
   296  		return true
   297  	}
   298  
   299  	// Stop gap for cases where unification fails.
   300  	if u.depth > unificationDepthLimit {
   301  		if traceInference {
   302  			u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
   303  		}
   304  		if panicAtUnificationDepthLimit {
   305  			panic("unification reached recursion depth limit")
   306  		}
   307  		return false
   308  	}
   309  
   310  	// Unification is symmetric, so we can swap the operands.
   311  	// Ensure that if we have at least one
   312  	// - defined type, make sure one is in y
   313  	// - type parameter recorded with u, make sure one is in x
   314  	if asNamed(x) != nil || u.asBoundTypeParam(y) != nil {
   315  		if traceInference {
   316  			u.tracef("%s ≡ %s\t// swap", y, x)
   317  		}
   318  		x, y = y, x
   319  	}
   320  
   321  	// Unification will fail if we match a defined type against a type literal.
   322  	// If we are matching types in an assignment, at the top-level, types with
   323  	// the same type structure are permitted as long as at least one of them
   324  	// is not a defined type. To accommodate for that possibility, we continue
   325  	// unification with the underlying type of a defined type if the other type
   326  	// is a type literal. This is controlled by the exact unification mode.
   327  	// We also continue if the other type is a basic type because basic types
   328  	// are valid underlying types and may appear as core types of type constraints.
   329  	// If we exclude them, inferred defined types for type parameters may not
   330  	// match against the core types of their constraints (even though they might
   331  	// correctly match against some of the types in the constraint's type set).
   332  	// Finally, if unification (incorrectly) succeeds by matching the underlying
   333  	// type of a defined type against a basic type (because we include basic types
   334  	// as type literals here), and if that leads to an incorrectly inferred type,
   335  	// we will fail at function instantiation or argument assignment time.
   336  	//
   337  	// If we have at least one defined type, there is one in y.
   338  	if ny := asNamed(y); mode&exact == 0 && ny != nil && isTypeLit(x) && !(u.enableInterfaceInference && IsInterface(x)) {
   339  		if traceInference {
   340  			u.tracef("%s ≡ under %s", x, ny)
   341  		}
   342  		y = ny.under()
   343  		// Per the spec, a defined type cannot have an underlying type
   344  		// that is a type parameter.
   345  		assert(!isTypeParam(y))
   346  		// x and y may be identical now
   347  		if x == y || Unalias(x) == Unalias(y) {
   348  			return true
   349  		}
   350  	}
   351  
   352  	// Cases where at least one of x or y is a type parameter recorded with u.
   353  	// If we have at least one type parameter, there is one in x.
   354  	// If we have exactly one type parameter, because it is in x,
   355  	// isTypeLit(x) is false and y was not changed above. In other
   356  	// words, if y was a defined type, it is still a defined type
   357  	// (relevant for the logic below).
   358  	switch px, py := u.asBoundTypeParam(x), u.asBoundTypeParam(y); {
   359  	case px != nil && py != nil:
   360  		// both x and y are type parameters
   361  		if u.join(px, py) {
   362  			return true
   363  		}
   364  		// both x and y have an inferred type - they must match
   365  		return u.nify(u.at(px), u.at(py), mode, p)
   366  
   367  	case px != nil:
   368  		// x is a type parameter, y is not
   369  		if x := u.at(px); x != nil {
   370  			// x has an inferred type which must match y
   371  			if u.nify(x, y, mode, p) {
   372  				// We have a match, possibly through underlying types.
   373  				xi := asInterface(x)
   374  				yi := asInterface(y)
   375  				xn := asNamed(x) != nil
   376  				yn := asNamed(y) != nil
   377  				// If we have two interfaces, what to do depends on
   378  				// whether they are named and their method sets.
   379  				if xi != nil && yi != nil {
   380  					// Both types are interfaces.
   381  					// If both types are defined types, they must be identical
   382  					// because unification doesn't know which type has the "right" name.
   383  					if xn && yn {
   384  						return Identical(x, y)
   385  					}
   386  					// In all other cases, the method sets must match.
   387  					// The types unified so we know that corresponding methods
   388  					// match and we can simply compare the number of methods.
   389  					// TODO(gri) We may be able to relax this rule and select
   390  					// the more general interface. But if one of them is a defined
   391  					// type, it's not clear how to choose and whether we introduce
   392  					// an order dependency or not. Requiring the same method set
   393  					// is conservative.
   394  					if len(xi.typeSet().methods) != len(yi.typeSet().methods) {
   395  						return false
   396  					}
   397  				} else if xi != nil || yi != nil {
   398  					// One but not both of them are interfaces.
   399  					// In this case, either x or y could be viable matches for the corresponding
   400  					// type parameter, which means choosing either introduces an order dependence.
   401  					// Therefore, we must fail unification (go.dev/issue/60933).
   402  					return false
   403  				}
   404  				// If we have inexact unification and one of x or y is a defined type, select the
   405  				// defined type. This ensures that in a series of types, all matching against the
   406  				// same type parameter, we infer a defined type if there is one, independent of
   407  				// order. Type inference or assignment may fail, which is ok.
   408  				// Selecting a defined type, if any, ensures that we don't lose the type name;
   409  				// and since we have inexact unification, a value of equally named or matching
   410  				// undefined type remains assignable (go.dev/issue/43056).
   411  				//
   412  				// Similarly, if we have inexact unification and there are no defined types but
   413  				// channel types, select a directed channel, if any. This ensures that in a series
   414  				// of unnamed types, all matching against the same type parameter, we infer the
   415  				// directed channel if there is one, independent of order.
   416  				// Selecting a directional channel, if any, ensures that a value of another
   417  				// inexactly unifying channel type remains assignable (go.dev/issue/62157).
   418  				//
   419  				// If we have multiple defined channel types, they are either identical or we
   420  				// have assignment conflicts, so we can ignore directionality in this case.
   421  				//
   422  				// If we have defined and literal channel types, a defined type wins to avoid
   423  				// order dependencies.
   424  				if mode&exact == 0 {
   425  					switch {
   426  					case xn:
   427  						// x is a defined type: nothing to do.
   428  					case yn:
   429  						// x is not a defined type and y is a defined type: select y.
   430  						u.set(px, y)
   431  					default:
   432  						// Neither x nor y are defined types.
   433  						if yc, _ := under(y).(*Chan); yc != nil && yc.dir != SendRecv {
   434  							// y is a directed channel type: select y.
   435  							u.set(px, y)
   436  						}
   437  					}
   438  				}
   439  				return true
   440  			}
   441  			return false
   442  		}
   443  		// otherwise, infer type from y
   444  		u.set(px, y)
   445  		return true
   446  	}
   447  
   448  	// x != y if we get here
   449  	assert(x != y && Unalias(x) != Unalias(y))
   450  
   451  	// If u.EnableInterfaceInference is set and we don't require exact unification,
   452  	// if both types are interfaces, one interface must have a subset of the
   453  	// methods of the other and corresponding method signatures must unify.
   454  	// If only one type is an interface, all its methods must be present in the
   455  	// other type and corresponding method signatures must unify.
   456  	if u.enableInterfaceInference && mode&exact == 0 {
   457  		// One or both interfaces may be defined types.
   458  		// Look under the name, but not under type parameters (go.dev/issue/60564).
   459  		xi := asInterface(x)
   460  		yi := asInterface(y)
   461  		// If we have two interfaces, check the type terms for equivalence,
   462  		// and unify common methods if possible.
   463  		if xi != nil && yi != nil {
   464  			xset := xi.typeSet()
   465  			yset := yi.typeSet()
   466  			if xset.comparable != yset.comparable {
   467  				return false
   468  			}
   469  			// For now we require terms to be equal.
   470  			// We should be able to relax this as well, eventually.
   471  			if !xset.terms.equal(yset.terms) {
   472  				return false
   473  			}
   474  			// Interface types are the only types where cycles can occur
   475  			// that are not "terminated" via named types; and such cycles
   476  			// can only be created via method parameter types that are
   477  			// anonymous interfaces (directly or indirectly) embedding
   478  			// the current interface. Example:
   479  			//
   480  			//    type T interface {
   481  			//        m() interface{T}
   482  			//    }
   483  			//
   484  			// If two such (differently named) interfaces are compared,
   485  			// endless recursion occurs if the cycle is not detected.
   486  			//
   487  			// If x and y were compared before, they must be equal
   488  			// (if they were not, the recursion would have stopped);
   489  			// search the ifacePair stack for the same pair.
   490  			//
   491  			// This is a quadratic algorithm, but in practice these stacks
   492  			// are extremely short (bounded by the nesting depth of interface
   493  			// type declarations that recur via parameter types, an extremely
   494  			// rare occurrence). An alternative implementation might use a
   495  			// "visited" map, but that is probably less efficient overall.
   496  			q := &ifacePair{xi, yi, p}
   497  			for p != nil {
   498  				if p.identical(q) {
   499  					return true // same pair was compared before
   500  				}
   501  				p = p.prev
   502  			}
   503  			// The method set of x must be a subset of the method set
   504  			// of y or vice versa, and the common methods must unify.
   505  			xmethods := xset.methods
   506  			ymethods := yset.methods
   507  			// The smaller method set must be the subset, if it exists.
   508  			if len(xmethods) > len(ymethods) {
   509  				xmethods, ymethods = ymethods, xmethods
   510  			}
   511  			// len(xmethods) <= len(ymethods)
   512  			// Collect the ymethods in a map for quick lookup.
   513  			ymap := make(map[string]*Func, len(ymethods))
   514  			for _, ym := range ymethods {
   515  				ymap[ym.Id()] = ym
   516  			}
   517  			// All xmethods must exist in ymethods and corresponding signatures must unify.
   518  			for _, xm := range xmethods {
   519  				if ym := ymap[xm.Id()]; ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
   520  					return false
   521  				}
   522  			}
   523  			return true
   524  		}
   525  
   526  		// We don't have two interfaces. If we have one, make sure it's in xi.
   527  		if yi != nil {
   528  			xi = yi
   529  			y = x
   530  		}
   531  
   532  		// If we have one interface, at a minimum each of the interface methods
   533  		// must be implemented and thus unify with a corresponding method from
   534  		// the non-interface type, otherwise unification fails.
   535  		if xi != nil {
   536  			// All xi methods must exist in y and corresponding signatures must unify.
   537  			xmethods := xi.typeSet().methods
   538  			for _, xm := range xmethods {
   539  				obj, _, _ := LookupFieldOrMethod(y, false, xm.pkg, xm.name)
   540  				if ym, _ := obj.(*Func); ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
   541  					return false
   542  				}
   543  			}
   544  			return true
   545  		}
   546  	}
   547  
   548  	// Unless we have exact unification, neither x nor y are interfaces now.
   549  	// Except for unbound type parameters (see below), x and y must be structurally
   550  	// equivalent to unify.
   551  
   552  	// If we get here and x or y is a type parameter, they are unbound
   553  	// (not recorded with the unifier).
   554  	// Ensure that if we have at least one type parameter, it is in x
   555  	// (the earlier swap checks for _recorded_ type parameters only).
   556  	// This ensures that the switch switches on the type parameter.
   557  	//
   558  	// TODO(gri) Factor out type parameter handling from the switch.
   559  	if isTypeParam(y) {
   560  		if traceInference {
   561  			u.tracef("%s ≡ %s\t// swap", y, x)
   562  		}
   563  		x, y = y, x
   564  	}
   565  
   566  	// Type elements (array, slice, etc. elements) use emode for unification.
   567  	// Element types must match exactly if the types are used in an assignment.
   568  	emode := mode
   569  	if mode&assign != 0 {
   570  		emode |= exact
   571  	}
   572  
   573  	// Continue with unaliased types but don't lose original alias names, if any (go.dev/issue/67628).
   574  	xorig, x := x, Unalias(x)
   575  	yorig, y := y, Unalias(y)
   576  
   577  	switch x := x.(type) {
   578  	case *Basic:
   579  		// Basic types are singletons except for the rune and byte
   580  		// aliases, thus we cannot solely rely on the x == y check
   581  		// above. See also comment in TypeName.IsAlias.
   582  		if y, ok := y.(*Basic); ok {
   583  			return x.kind == y.kind
   584  		}
   585  
   586  	case *Array:
   587  		// Two array types unify if they have the same array length
   588  		// and their element types unify.
   589  		if y, ok := y.(*Array); ok {
   590  			// If one or both array lengths are unknown (< 0) due to some error,
   591  			// assume they are the same to avoid spurious follow-on errors.
   592  			return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, emode, p)
   593  		}
   594  
   595  	case *Slice:
   596  		// Two slice types unify if their element types unify.
   597  		if y, ok := y.(*Slice); ok {
   598  			return u.nify(x.elem, y.elem, emode, p)
   599  		}
   600  
   601  	case *Struct:
   602  		// Two struct types unify if they have the same sequence of fields,
   603  		// and if corresponding fields have the same names, their (field) types unify,
   604  		// and they have identical tags. Two embedded fields are considered to have the same
   605  		// name. Lower-case field names from different packages are always different.
   606  		if y, ok := y.(*Struct); ok {
   607  			if x.NumFields() == y.NumFields() {
   608  				for i, f := range x.fields {
   609  					g := y.fields[i]
   610  					if f.embedded != g.embedded ||
   611  						x.Tag(i) != y.Tag(i) ||
   612  						!f.sameId(g.pkg, g.name, false) ||
   613  						!u.nify(f.typ, g.typ, emode, p) {
   614  						return false
   615  					}
   616  				}
   617  				return true
   618  			}
   619  		}
   620  
   621  	case *Pointer:
   622  		// Two pointer types unify if their base types unify.
   623  		if y, ok := y.(*Pointer); ok {
   624  			return u.nify(x.base, y.base, emode, p)
   625  		}
   626  
   627  	case *Tuple:
   628  		// Two tuples types unify if they have the same number of elements
   629  		// and the types of corresponding elements unify.
   630  		if y, ok := y.(*Tuple); ok {
   631  			if x.Len() == y.Len() {
   632  				if x != nil {
   633  					for i, v := range x.vars {
   634  						w := y.vars[i]
   635  						if !u.nify(v.typ, w.typ, mode, p) {
   636  							return false
   637  						}
   638  					}
   639  				}
   640  				return true
   641  			}
   642  		}
   643  
   644  	case *Signature:
   645  		// Two function types unify if they have the same number of parameters
   646  		// and result values, corresponding parameter and result types unify,
   647  		// and either both functions are variadic or neither is.
   648  		// Parameter and result names are not required to match.
   649  		// TODO(gri) handle type parameters or document why we can ignore them.
   650  		if y, ok := y.(*Signature); ok {
   651  			return x.variadic == y.variadic &&
   652  				u.nify(x.params, y.params, emode, p) &&
   653  				u.nify(x.results, y.results, emode, p)
   654  		}
   655  
   656  	case *Interface:
   657  		assert(!u.enableInterfaceInference || mode&exact != 0) // handled before this switch
   658  
   659  		// Two interface types unify if they have the same set of methods with
   660  		// the same names, and corresponding function types unify.
   661  		// Lower-case method names from different packages are always different.
   662  		// The order of the methods is irrelevant.
   663  		if y, ok := y.(*Interface); ok {
   664  			xset := x.typeSet()
   665  			yset := y.typeSet()
   666  			if xset.comparable != yset.comparable {
   667  				return false
   668  			}
   669  			if !xset.terms.equal(yset.terms) {
   670  				return false
   671  			}
   672  			a := xset.methods
   673  			b := yset.methods
   674  			if len(a) == len(b) {
   675  				// Interface types are the only types where cycles can occur
   676  				// that are not "terminated" via named types; and such cycles
   677  				// can only be created via method parameter types that are
   678  				// anonymous interfaces (directly or indirectly) embedding
   679  				// the current interface. Example:
   680  				//
   681  				//    type T interface {
   682  				//        m() interface{T}
   683  				//    }
   684  				//
   685  				// If two such (differently named) interfaces are compared,
   686  				// endless recursion occurs if the cycle is not detected.
   687  				//
   688  				// If x and y were compared before, they must be equal
   689  				// (if they were not, the recursion would have stopped);
   690  				// search the ifacePair stack for the same pair.
   691  				//
   692  				// This is a quadratic algorithm, but in practice these stacks
   693  				// are extremely short (bounded by the nesting depth of interface
   694  				// type declarations that recur via parameter types, an extremely
   695  				// rare occurrence). An alternative implementation might use a
   696  				// "visited" map, but that is probably less efficient overall.
   697  				q := &ifacePair{x, y, p}
   698  				for p != nil {
   699  					if p.identical(q) {
   700  						return true // same pair was compared before
   701  					}
   702  					p = p.prev
   703  				}
   704  				if debug {
   705  					assertSortedMethods(a)
   706  					assertSortedMethods(b)
   707  				}
   708  				for i, f := range a {
   709  					g := b[i]
   710  					if f.Id() != g.Id() || !u.nify(f.typ, g.typ, exact, q) {
   711  						return false
   712  					}
   713  				}
   714  				return true
   715  			}
   716  		}
   717  
   718  	case *Map:
   719  		// Two map types unify if their key and value types unify.
   720  		if y, ok := y.(*Map); ok {
   721  			return u.nify(x.key, y.key, emode, p) && u.nify(x.elem, y.elem, emode, p)
   722  		}
   723  
   724  	case *Chan:
   725  		// Two channel types unify if their value types unify
   726  		// and if they have the same direction.
   727  		// The channel direction is ignored for inexact unification.
   728  		if y, ok := y.(*Chan); ok {
   729  			return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p)
   730  		}
   731  
   732  	case *Named:
   733  		// Two named types unify if their type names originate in the same type declaration.
   734  		// If they are instantiated, their type argument lists must unify.
   735  		if y := asNamed(y); y != nil {
   736  			// Check type arguments before origins so they unify
   737  			// even if the origins don't match; for better error
   738  			// messages (see go.dev/issue/53692).
   739  			xargs := x.TypeArgs().list()
   740  			yargs := y.TypeArgs().list()
   741  			if len(xargs) != len(yargs) {
   742  				return false
   743  			}
   744  			for i, xarg := range xargs {
   745  				if !u.nify(xarg, yargs[i], mode, p) {
   746  					return false
   747  				}
   748  			}
   749  			return identicalOrigin(x, y)
   750  		}
   751  
   752  	case *TypeParam:
   753  		// x must be an unbound type parameter (see comment above).
   754  		if debug {
   755  			assert(u.asBoundTypeParam(x) == nil)
   756  		}
   757  		// By definition, a valid type argument must be in the type set of
   758  		// the respective type constraint. Therefore, the type argument's
   759  		// underlying type must be in the set of underlying types of that
   760  		// constraint. If there is a single such underlying type, it's the
   761  		// constraint's core type. It must match the type argument's under-
   762  		// lying type, irrespective of whether the actual type argument,
   763  		// which may be a defined type, is actually in the type set (that
   764  		// will be determined at instantiation time).
   765  		// Thus, if we have the core type of an unbound type parameter,
   766  		// we know the structure of the possible types satisfying such
   767  		// parameters. Use that core type for further unification
   768  		// (see go.dev/issue/50755 for a test case).
   769  		if enableCoreTypeUnification {
   770  			// Because the core type is always an underlying type,
   771  			// unification will take care of matching against a
   772  			// defined or literal type automatically.
   773  			// If y is also an unbound type parameter, we will end
   774  			// up here again with x and y swapped, so we don't
   775  			// need to take care of that case separately.
   776  			if cx := coreType(x); cx != nil {
   777  				if traceInference {
   778  					u.tracef("core %s ≡ %s", xorig, yorig)
   779  				}
   780  				// If y is a defined type, it may not match against cx which
   781  				// is an underlying type (incl. int, string, etc.). Use assign
   782  				// mode here so that the unifier automatically takes under(y)
   783  				// if necessary.
   784  				return u.nify(cx, yorig, assign, p)
   785  			}
   786  		}
   787  		// x != y and there's nothing to do
   788  
   789  	case nil:
   790  		// avoid a crash in case of nil type
   791  
   792  	default:
   793  		panic(sprintf(nil, true, "u.nify(%s, %s, %d)", xorig, yorig, mode))
   794  	}
   795  
   796  	return false
   797  }
   798
View as plain text