src/cmd/compile/internal/types2/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 package types2
   8
   9 import (
  10         "bytes"
  11         "fmt"
  12         "strings"
  13 )
  14
  15 const (
  16         // Upper limit for recursion depth. Used to catch infinite recursions
  17         // due to implementation issues (e.g., see issues go.dev/issue/48619, go.dev/issue/48656).
  18         unificationDepthLimit = 50
  19
  20         // Whether to panic when unificationDepthLimit is reached.
  21         // If disabled, a recursion depth overflow results in a (quiet)
  22         // unification failure.
  23         panicAtUnificationDepthLimit = true
  24
  25         // If enableCoreTypeUnification is set, unification will consider
  26         // the core types, if any, of non-local (unbound) type parameters.
  27         enableCoreTypeUnification = true
  28
  29         // If traceInference is set, unification will print a trace of its operation.
  30         // Interpretation of trace:
  31         //   x ≡ y    attempt to unify types x and y
  32         //   p ➞ y    type parameter p is set to type y (p is inferred to be y)
  33         //   p ⇄ q    type parameters p and q match (p is inferred to be q and vice versa)
  34         //   x ≢ y    types x and y cannot be unified
  35         //   [p, q, ...] ➞ [x, y, ...]    mapping from type parameters to types
  36         traceInference = false
  37 )
  38
  39 // A unifier maintains a list of type parameters and
  40 // corresponding types inferred for each type parameter.
  41 // A unifier is created by calling newUnifier.
  42 type unifier struct {
  43         // tparams is the initial list of type parameters provided.
  44         // Only used to print/return types in reproducible order.
  45         tparams []*TypeParam
  46         // handles maps each type parameter to its inferred type through
  47         // an indirection *Type called (inferred type) "handle".
  48         // Initially, each type parameter has its own, separate handle,
  49         // with a nil (i.e., not yet inferred) type.
  50         // After a type parameter P is unified with a type parameter Q,
  51         // P and Q share the same handle (and thus type). This ensures
  52         // that inferring the type for a given type parameter P will
  53         // automatically infer the same type for all other parameters
  54         // unified (joined) with P.
  55         handles map[*TypeParam]*Type
  56         depth   int // recursion depth during unification
  57 }
  58
  59 // newUnifier returns a new unifier initialized with the given type parameter
  60 // and corresponding type argument lists. The type argument list may be shorter
  61 // than the type parameter list, and it may contain nil types. Matching type
  62 // parameters and arguments must have the same index.
  63 func newUnifier(tparams []*TypeParam, targs []Type) *unifier {
  64         assert(len(tparams) >= len(targs))
  65         handles := make(map[*TypeParam]*Type, len(tparams))
  66         // Allocate all handles up-front: in a correct program, all type parameters
  67         // must be resolved and thus eventually will get a handle.
  68         // Also, sharing of handles caused by unified type parameters is rare and
  69         // so it's ok to not optimize for that case (and delay handle allocation).
  70         for i, x := range tparams {
  71                 var t Type
  72                 if i < len(targs) {
  73                         t = targs[i]
  74                 }
  75                 handles[x] = &t
  76         }
  77         return &unifier{tparams, handles, 0}
  78 }
  79
  80 // unify attempts to unify x and y and reports whether it succeeded.
  81 // As a side-effect, types may be inferred for type parameters.
  82 func (u *unifier) unify(x, y Type) bool {
  83         return u.nify(x, y, nil)
  84 }
  85
  86 func (u *unifier) tracef(format string, args ...interface{}) {
  87         fmt.Println(strings.Repeat(".  ", u.depth) + sprintf(nil, true, format, args...))
  88 }
  89
  90 // String returns a string representation of the current mapping
  91 // from type parameters to types.
  92 func (u *unifier) String() string {
  93         var buf bytes.Buffer
  94         w := newTypeWriter(&buf, nil)
  95         w.byte('[')
  96         for i, x := range u.tparams {
  97                 if i > 0 {
  98                         w.string(", ")
  99                 }
 100                 w.typ(x)
 101                 w.string(": ")
 102                 w.typ(u.at(x))
 103         }
 104         w.byte(']')
 105         return buf.String()
 106 }
 107
 108 // join unifies the given type parameters x and y.
 109 // If both type parameters already have a type associated with them
 110 // and they are not joined, join fails and returns false.
 111 func (u *unifier) join(x, y *TypeParam) bool {
 112         if traceInference {
 113                 u.tracef("%s ⇄ %s", x, y)
 114         }
 115         switch hx, hy := u.handles[x], u.handles[y]; {
 116         case hx == hy:
 117                 // Both type parameters already share the same handle. Nothing to do.
 118         case *hx != nil && *hy != nil:
 119                 // Both type parameters have (possibly different) inferred types. Cannot join.
 120                 return false
 121         case *hx != nil:
 122                 // Only type parameter x has an inferred type. Use handle of x.
 123                 u.setHandle(y, hx)
 124         // This case is treated like the default case.
 125         // case *hy != nil:
 126         //      // Only type parameter y has an inferred type. Use handle of y.
 127         //      u.setHandle(x, hy)
 128         default:
 129                 // Neither type parameter has an inferred type. Use handle of y.
 130                 u.setHandle(x, hy)
 131         }
 132         return true
 133 }
 134
 135 // asTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u.
 136 // Otherwise, the result is nil.
 137 func (u *unifier) asTypeParam(x Type) *TypeParam {
 138         if x, _ := x.(*TypeParam); x != nil {
 139                 if _, found := u.handles[x]; found {
 140                         return x
 141                 }
 142         }
 143         return nil
 144 }
 145
 146 // setHandle sets the handle for type parameter x
 147 // (and all its joined type parameters) to h.
 148 func (u *unifier) setHandle(x *TypeParam, h *Type) {
 149         hx := u.handles[x]
 150         assert(hx != nil)
 151         for y, hy := range u.handles {
 152                 if hy == hx {
 153                         u.handles[y] = h
 154                 }
 155         }
 156 }
 157
 158 // at returns the (possibly nil) type for type parameter x.
 159 func (u *unifier) at(x *TypeParam) Type {
 160         return *u.handles[x]
 161 }
 162
 163 // set sets the type t for type parameter x;
 164 // t must not be nil and it must not have been set before.
 165 func (u *unifier) set(x *TypeParam, t Type) {
 166         assert(t != nil)
 167         if traceInference {
 168                 u.tracef("%s ➞ %s", x, t)
 169         }
 170         h := u.handles[x]
 171         assert(*h == nil)
 172         *h = t
 173 }
 174
 175 // unknowns returns the number of type parameters for which no type has been set yet.
 176 func (u *unifier) unknowns() int {
 177         n := 0
 178         for _, h := range u.handles {
 179                 if *h == nil {
 180                         n++
 181                 }
 182         }
 183         return n
 184 }
 185
 186 // inferred returns the list of inferred types (via unification) for the type parameters
 187 // recorded with u, and an index. If all types were inferred, the returned index is < 0.
 188 // Otherwise, it is the index of the first type parameter which couldn't be inferred;
 189 // i.e., for which list[index] is nil.
 190 func (u *unifier) inferred() (list []Type, index int) {
 191         list = make([]Type, len(u.tparams))
 192         index = -1
 193         for i, x := range u.tparams {
 194                 t := u.at(x)
 195                 list[i] = t
 196                 if index < 0 && t == nil {
 197                         index = i
 198                 }
 199         }
 200         return
 201 }
 202
 203 func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
 204         return x == y || u.nify(x, y, p)
 205 }
 206
 207 // nify implements the core unification algorithm which is an
 208 // adapted version of Checker.identical. For changes to that
 209 // code the corresponding changes should be made here.
 210 // Must not be called directly from outside the unifier.
 211 func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) {
 212         if traceInference {
 213                 u.tracef("%s ≡ %s", x, y)
 214         }
 215
 216         // Stop gap for cases where unification fails.
 217         if u.depth >= unificationDepthLimit {
 218                 if traceInference {
 219                         u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
 220                 }
 221                 if panicAtUnificationDepthLimit {
 222                         panic("unification reached recursion depth limit")
 223                 }
 224                 return false
 225         }
 226         u.depth++
 227         defer func() {
 228                 u.depth--
 229                 if traceInference && !result {
 230                         u.tracef("%s ≢ %s", x, y)
 231                 }
 232         }()
 233
 234         // If exact unification is known to fail because we attempt to
 235         // match a type name against an unnamed type literal, consider
 236         // the underlying type of the named type.
 237         // (We use !hasName to exclude any type with a name, including
 238         // basic types and type parameters; the rest are unamed types.)
 239         if nx, _ := x.(*Named); nx != nil && !hasName(y) {
 240                 if traceInference {
 241                         u.tracef("under %s ≡ %s", nx, y)
 242                 }
 243                 return u.nify(nx.under(), y, p)
 244         } else if ny, _ := y.(*Named); ny != nil && !hasName(x) {
 245                 if traceInference {
 246                         u.tracef("%s ≡ under %s", x, ny)
 247                 }
 248                 return u.nify(x, ny.under(), p)
 249         }
 250
 251         // Cases where at least one of x or y is a type parameter recorded with u.
 252         switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
 253         case px != nil && py != nil:
 254                 // both x and y are type parameters
 255                 if u.join(px, py) {
 256                         return true
 257                 }
 258                 // both x and y have an inferred type - they must match
 259                 return u.nifyEq(u.at(px), u.at(py), p)
 260
 261         case px != nil:
 262                 // x is a type parameter, y is not
 263                 if tx := u.at(px); tx != nil {
 264                         return u.nifyEq(tx, y, p)
 265                 }
 266                 // otherwise, infer type from y
 267                 u.set(px, y)
 268                 return true
 269
 270         case py != nil:
 271                 // y is a type parameter, x is not
 272                 if ty := u.at(py); ty != nil {
 273                         return u.nifyEq(x, ty, p)
 274                 }
 275                 // otherwise, infer type from x
 276                 u.set(py, x)
 277                 return true
 278         }
 279
 280         // If we get here and x or y is a type parameter, they are type parameters
 281         // from outside our declaration list. Try to unify their core types, if any
 282         // (see go.dev/issue/50755 for a test case).
 283         if enableCoreTypeUnification {
 284                 if isTypeParam(x) && !hasName(y) {
 285                         // When considering the type parameter for unification
 286                         // we look at the adjusted core term (adjusted core type
 287                         // with tilde information).
 288                         // If the adjusted core type is a named type N; the
 289                         // corresponding core type is under(N).
 290                         // Since y doesn't have a name, unification will end up
 291                         // comparing under(N) to y, so we can just use the core
 292                         // type instead. And we can ignore the tilde because we
 293                         // already look at the underlying types on both sides
 294                         // and we have known types on both sides.
 295                         // Optimization.
 296                         if cx := coreType(x); cx != nil {
 297                                 if traceInference {
 298                                         u.tracef("core %s ≡ %s", x, y)
 299                                 }
 300                                 return u.nify(cx, y, p)
 301                         }
 302                 } else if isTypeParam(y) && !hasName(x) {
 303                         // see comment above
 304                         if cy := coreType(y); cy != nil {
 305                                 if traceInference {
 306                                         u.tracef("%s ≡ core %s", x, y)
 307                                 }
 308                                 return u.nify(x, cy, p)
 309                         }
 310                 }
 311         }
 312
 313         // For type unification, do not shortcut (x == y) for identical
 314         // types. Instead keep comparing them element-wise to unify the
 315         // matching (and equal type parameter types). A simple test case
 316         // where this matters is: func f[P any](a P) { f(a) } .
 317
 318         switch x := x.(type) {
 319         case *Basic:
 320                 // Basic types are singletons except for the rune and byte
 321                 // aliases, thus we cannot solely rely on the x == y check
 322                 // above. See also comment in TypeName.IsAlias.
 323                 if y, ok := y.(*Basic); ok {
 324                         return x.kind == y.kind
 325                 }
 326
 327         case *Array:
 328                 // Two array types are identical if they have identical element types
 329                 // and the same array length.
 330                 if y, ok := y.(*Array); ok {
 331                         // If one or both array lengths are unknown (< 0) due to some error,
 332                         // assume they are the same to avoid spurious follow-on errors.
 333                         return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p)
 334                 }
 335
 336         case *Slice:
 337                 // Two slice types are identical if they have identical element types.
 338                 if y, ok := y.(*Slice); ok {
 339                         return u.nify(x.elem, y.elem, p)
 340                 }
 341
 342         case *Struct:
 343                 // Two struct types are identical if they have the same sequence of fields,
 344                 // and if corresponding fields have the same names, and identical types,
 345                 // and identical tags. Two embedded fields are considered to have the same
 346                 // name. Lower-case field names from different packages are always different.
 347                 if y, ok := y.(*Struct); ok {
 348                         if x.NumFields() == y.NumFields() {
 349                                 for i, f := range x.fields {
 350                                         g := y.fields[i]
 351                                         if f.embedded != g.embedded ||
 352                                                 x.Tag(i) != y.Tag(i) ||
 353                                                 !f.sameId(g.pkg, g.name) ||
 354                                                 !u.nify(f.typ, g.typ, p) {
 355                                                 return false
 356                                         }
 357                                 }
 358                                 return true
 359                         }
 360                 }
 361
 362         case *Pointer:
 363                 // Two pointer types are identical if they have identical base types.
 364                 if y, ok := y.(*Pointer); ok {
 365                         return u.nify(x.base, y.base, p)
 366                 }
 367
 368         case *Tuple:
 369                 // Two tuples types are identical if they have the same number of elements
 370                 // and corresponding elements have identical types.
 371                 if y, ok := y.(*Tuple); ok {
 372                         if x.Len() == y.Len() {
 373                                 if x != nil {
 374                                         for i, v := range x.vars {
 375                                                 w := y.vars[i]
 376                                                 if !u.nify(v.typ, w.typ, p) {
 377                                                         return false
 378                                                 }
 379                                         }
 380                                 }
 381                                 return true
 382                         }
 383                 }
 384
 385         case *Signature:
 386                 // Two function types are identical if they have the same number of parameters
 387                 // and result values, corresponding parameter and result types are identical,
 388                 // and either both functions are variadic or neither is. Parameter and result
 389                 // names are not required to match.
 390                 // TODO(gri) handle type parameters or document why we can ignore them.
 391                 if y, ok := y.(*Signature); ok {
 392                         return x.variadic == y.variadic &&
 393                                 u.nify(x.params, y.params, p) &&
 394                                 u.nify(x.results, y.results, p)
 395                 }
 396
 397         case *Interface:
 398                 // Two interface types are identical if they have the same set of methods with
 399                 // the same names and identical function types. Lower-case method names from
 400                 // different packages are always different. The order of the methods is irrelevant.
 401                 if y, ok := y.(*Interface); ok {
 402                         xset := x.typeSet()
 403                         yset := y.typeSet()
 404                         if xset.comparable != yset.comparable {
 405                                 return false
 406                         }
 407                         if !xset.terms.equal(yset.terms) {
 408                                 return false
 409                         }
 410                         a := xset.methods
 411                         b := yset.methods
 412                         if len(a) == len(b) {
 413                                 // Interface types are the only types where cycles can occur
 414                                 // that are not "terminated" via named types; and such cycles
 415                                 // can only be created via method parameter types that are
 416                                 // anonymous interfaces (directly or indirectly) embedding
 417                                 // the current interface. Example:
 418                                 //
 419                                 //    type T interface {
 420                                 //        m() interface{T}
 421                                 //    }
 422                                 //
 423                                 // If two such (differently named) interfaces are compared,
 424                                 // endless recursion occurs if the cycle is not detected.
 425                                 //
 426                                 // If x and y were compared before, they must be equal
 427                                 // (if they were not, the recursion would have stopped);
 428                                 // search the ifacePair stack for the same pair.
 429                                 //
 430                                 // This is a quadratic algorithm, but in practice these stacks
 431                                 // are extremely short (bounded by the nesting depth of interface
 432                                 // type declarations that recur via parameter types, an extremely
 433                                 // rare occurrence). An alternative implementation might use a
 434                                 // "visited" map, but that is probably less efficient overall.
 435                                 q := &ifacePair{x, y, p}
 436                                 for p != nil {
 437                                         if p.identical(q) {
 438                                                 return true // same pair was compared before
 439                                         }
 440                                         p = p.prev
 441                                 }
 442                                 if debug {
 443                                         assertSortedMethods(a)
 444                                         assertSortedMethods(b)
 445                                 }
 446                                 for i, f := range a {
 447                                         g := b[i]
 448                                         if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
 449                                                 return false
 450                                         }
 451                                 }
 452                                 return true
 453                         }
 454                 }
 455
 456         case *Map:
 457                 // Two map types are identical if they have identical key and value types.
 458                 if y, ok := y.(*Map); ok {
 459                         return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p)
 460                 }
 461
 462         case *Chan:
 463                 // Two channel types are identical if they have identical value types.
 464                 if y, ok := y.(*Chan); ok {
 465                         return u.nify(x.elem, y.elem, p)
 466                 }
 467
 468         case *Named:
 469                 // TODO(gri) This code differs now from the parallel code in Checker.identical. Investigate.
 470                 if y, ok := y.(*Named); ok {
 471                         xargs := x.TypeArgs().list()
 472                         yargs := y.TypeArgs().list()
 473
 474                         if len(xargs) != len(yargs) {
 475                                 return false
 476                         }
 477
 478                         // TODO(gri) This is not always correct: two types may have the same names
 479                         //           in the same package if one of them is nested in a function.
 480                         //           Extremely unlikely but we need an always correct solution.
 481                         if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
 482                                 for i, x := range xargs {
 483                                         if !u.nify(x, yargs[i], p) {
 484                                                 return false
 485                                         }
 486                                 }
 487                                 return true
 488                         }
 489                 }
 490
 491         case *TypeParam:
 492                 // Two type parameters (which are not part of the type parameters of the
 493                 // enclosing type as those are handled in the beginning of this function)
 494                 // are identical if they originate in the same declaration.
 495                 return x == y
 496
 497         case nil:
 498                 // avoid a crash in case of nil type
 499
 500         default:
 501                 panic(sprintf(nil, true, "u.nify(%s, %s), u.tparams = %s", x, y, u.tparams))
 502         }
 503
 504         return false
 505 }