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.
 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         *u.handles[x] = t
 171 }
 172
 173 // unknowns returns the number of type parameters for which no type has been set yet.
 174 func (u *unifier) unknowns() int {
 175         n := 0
 176         for _, h := range u.handles {
 177                 if *h == nil {
 178                         n++
 179                 }
 180         }
 181         return n
 182 }
 183
 184 // inferred returns the list of inferred types (via unification) for the type parameters
 185 // recorded with u, and an index. If all types were inferred, the returned index is < 0.
 186 // Otherwise, it is the index of the first type parameter which couldn't be inferred;
 187 // i.e., for which list[index] is nil.
 188 func (u *unifier) inferred() (list []Type, index int) {
 189         list = make([]Type, len(u.tparams))
 190         index = -1
 191         for i, x := range u.tparams {
 192                 t := u.at(x)
 193                 list[i] = t
 194                 if index < 0 && t == nil {
 195                         index = i
 196                 }
 197         }
 198         return
 199 }
 200
 201 func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
 202         return x == y || u.nify(x, y, p)
 203 }
 204
 205 // nify implements the core unification algorithm which is an
 206 // adapted version of Checker.identical. For changes to that
 207 // code the corresponding changes should be made here.
 208 // Must not be called directly from outside the unifier.
 209 func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) {
 210         u.depth++
 211         if traceInference {
 212                 u.tracef("%s ≡ %s", x, y)
 213         }
 214         defer func() {
 215                 if traceInference && !result {
 216                         u.tracef("%s ≢ %s", x, y)
 217                 }
 218                 u.depth--
 219         }()
 220
 221         // Stop gap for cases where unification fails.
 222         if u.depth > unificationDepthLimit {
 223                 if traceInference {
 224                         u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
 225                 }
 226                 if panicAtUnificationDepthLimit {
 227                         panic("unification reached recursion depth limit")
 228                 }
 229                 return false
 230         }
 231
 232         // Unification is symmetric, so we can swap the operands.
 233         // Ensure that if we have at least one
 234         // - defined type, make sure sure one is in y
 235         // - type parameter recorded with u, make sure one is in x
 236         if _, ok := x.(*Named); ok || u.asTypeParam(y) != nil {
 237                 if traceInference {
 238                         u.tracef("%s ≡ %s (swap)", y, x)
 239                 }
 240                 x, y = y, x
 241         }
 242
 243         // If exact unification is known to fail because we attempt to
 244         // match a defined type against an unnamed type literal, consider
 245         // the underlying type of the defined type.
 246         // If we have at least one defined type, there is one in y.
 247         // (We use !hasName to exclude any type with a name, including
 248         // basic types and type parameters; the rest are unamed types.)
 249         if ny, _ := y.(*Named); ny != nil && !hasName(x) {
 250                 if traceInference {
 251                         u.tracef("%s ≡ under %s", x, ny)
 252                 }
 253                 y = ny.under()
 254                 // Per the spec, a defined type cannot have an underlying type
 255                 // that is a type parameter.
 256                 assert(!isTypeParam(y))
 257         }
 258
 259         // Cases where at least one of x or y is a type parameter recorded with u.
 260         // If we have at least one type parameter, there is one in x.
 261         switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
 262         case px != nil && py != nil:
 263                 // both x and y are type parameters
 264                 if u.join(px, py) {
 265                         return true
 266                 }
 267                 // both x and y have an inferred type - they must match
 268                 return u.nifyEq(u.at(px), u.at(py), p)
 269
 270         case px != nil:
 271                 // x is a type parameter, y is not
 272                 if x := u.at(px); x != nil {
 273                         // x has an inferred type which must match y
 274                         if u.nifyEq(x, y, p) {
 275                                 // If we have a match, possibly through underlying types,
 276                                 // and y is a defined type, make sure we record that type
 277                                 // for type parameter x, which may have until now only
 278                                 // recorded an underlying type (go.dev/issue/43056).
 279                                 if _, ok := y.(*Named); ok {
 280                                         u.set(px, y)
 281                                 }
 282                                 return true
 283                         }
 284                         return false
 285                 }
 286                 // otherwise, infer type from y
 287                 u.set(px, y)
 288                 return true
 289         }
 290
 291         // If we get here and x or y is a type parameter, they are type parameters
 292         // from outside our declaration list. Try to unify their core types, if any
 293         // (see go.dev/issue/50755 for a test case).
 294         if enableCoreTypeUnification {
 295                 // swap x and y as needed
 296                 // (the earlier swap checks for _recorded_ type parameters only)
 297                 if isTypeParam(y) {
 298                         if traceInference {
 299                                 u.tracef("%s ≡ %s (swap)", y, x)
 300                         }
 301                         x, y = y, x
 302                 }
 303                 if isTypeParam(x) && !hasName(y) {
 304                         // When considering the type parameter for unification
 305                         // we look at the adjusted core term (adjusted core type
 306                         // with tilde information).
 307                         // If the adjusted core type is a named type N; the
 308                         // corresponding core type is under(N).
 309                         // Since y doesn't have a name, unification will end up
 310                         // comparing under(N) to y, so we can just use the core
 311                         // type instead. And we can ignore the tilde because we
 312                         // already look at the underlying types on both sides
 313                         // and we have known types on both sides.
 314                         // Optimization.
 315                         if cx := coreType(x); cx != nil {
 316                                 if traceInference {
 317                                         u.tracef("core %s ≡ %s", x, y)
 318                                 }
 319                                 return u.nify(cx, y, p)
 320                         }
 321                 }
 322         }
 323
 324         // For type unification, do not shortcut (x == y) for identical
 325         // types. Instead keep comparing them element-wise to unify the
 326         // matching (and equal type parameter types). A simple test case
 327         // where this matters is: func f[P any](a P) { f(a) } .
 328
 329         switch x := x.(type) {
 330         case *Basic:
 331                 // Basic types are singletons except for the rune and byte
 332                 // aliases, thus we cannot solely rely on the x == y check
 333                 // above. See also comment in TypeName.IsAlias.
 334                 if y, ok := y.(*Basic); ok {
 335                         return x.kind == y.kind
 336                 }
 337
 338         case *Array:
 339                 // Two array types are identical if they have identical element types
 340                 // and the same array length.
 341                 if y, ok := y.(*Array); ok {
 342                         // If one or both array lengths are unknown (< 0) due to some error,
 343                         // assume they are the same to avoid spurious follow-on errors.
 344                         return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p)
 345                 }
 346
 347         case *Slice:
 348                 // Two slice types are identical if they have identical element types.
 349                 if y, ok := y.(*Slice); ok {
 350                         return u.nify(x.elem, y.elem, p)
 351                 }
 352
 353         case *Struct:
 354                 // Two struct types are identical if they have the same sequence of fields,
 355                 // and if corresponding fields have the same names, and identical types,
 356                 // and identical tags. Two embedded fields are considered to have the same
 357                 // name. Lower-case field names from different packages are always different.
 358                 if y, ok := y.(*Struct); ok {
 359                         if x.NumFields() == y.NumFields() {
 360                                 for i, f := range x.fields {
 361                                         g := y.fields[i]
 362                                         if f.embedded != g.embedded ||
 363                                                 x.Tag(i) != y.Tag(i) ||
 364                                                 !f.sameId(g.pkg, g.name) ||
 365                                                 !u.nify(f.typ, g.typ, p) {
 366                                                 return false
 367                                         }
 368                                 }
 369                                 return true
 370                         }
 371                 }
 372
 373         case *Pointer:
 374                 // Two pointer types are identical if they have identical base types.
 375                 if y, ok := y.(*Pointer); ok {
 376                         return u.nify(x.base, y.base, p)
 377                 }
 378
 379         case *Tuple:
 380                 // Two tuples types are identical if they have the same number of elements
 381                 // and corresponding elements have identical types.
 382                 if y, ok := y.(*Tuple); ok {
 383                         if x.Len() == y.Len() {
 384                                 if x != nil {
 385                                         for i, v := range x.vars {
 386                                                 w := y.vars[i]
 387                                                 if !u.nify(v.typ, w.typ, p) {
 388                                                         return false
 389                                                 }
 390                                         }
 391                                 }
 392                                 return true
 393                         }
 394                 }
 395
 396         case *Signature:
 397                 // Two function types are identical if they have the same number of parameters
 398                 // and result values, corresponding parameter and result types are identical,
 399                 // and either both functions are variadic or neither is. Parameter and result
 400                 // names are not required to match.
 401                 // TODO(gri) handle type parameters or document why we can ignore them.
 402                 if y, ok := y.(*Signature); ok {
 403                         return x.variadic == y.variadic &&
 404                                 u.nify(x.params, y.params, p) &&
 405                                 u.nify(x.results, y.results, p)
 406                 }
 407
 408         case *Interface:
 409                 // Two interface types are identical if they have the same set of methods with
 410                 // the same names and identical function types. Lower-case method names from
 411                 // different packages are always different. The order of the methods is irrelevant.
 412                 if y, ok := y.(*Interface); ok {
 413                         xset := x.typeSet()
 414                         yset := y.typeSet()
 415                         if xset.comparable != yset.comparable {
 416                                 return false
 417                         }
 418                         if !xset.terms.equal(yset.terms) {
 419                                 return false
 420                         }
 421                         a := xset.methods
 422                         b := yset.methods
 423                         if len(a) == len(b) {
 424                                 // Interface types are the only types where cycles can occur
 425                                 // that are not "terminated" via named types; and such cycles
 426                                 // can only be created via method parameter types that are
 427                                 // anonymous interfaces (directly or indirectly) embedding
 428                                 // the current interface. Example:
 429                                 //
 430                                 //    type T interface {
 431                                 //        m() interface{T}
 432                                 //    }
 433                                 //
 434                                 // If two such (differently named) interfaces are compared,
 435                                 // endless recursion occurs if the cycle is not detected.
 436                                 //
 437                                 // If x and y were compared before, they must be equal
 438                                 // (if they were not, the recursion would have stopped);
 439                                 // search the ifacePair stack for the same pair.
 440                                 //
 441                                 // This is a quadratic algorithm, but in practice these stacks
 442                                 // are extremely short (bounded by the nesting depth of interface
 443                                 // type declarations that recur via parameter types, an extremely
 444                                 // rare occurrence). An alternative implementation might use a
 445                                 // "visited" map, but that is probably less efficient overall.
 446                                 q := &ifacePair{x, y, p}
 447                                 for p != nil {
 448                                         if p.identical(q) {
 449                                                 return true // same pair was compared before
 450                                         }
 451                                         p = p.prev
 452                                 }
 453                                 if debug {
 454                                         assertSortedMethods(a)
 455                                         assertSortedMethods(b)
 456                                 }
 457                                 for i, f := range a {
 458                                         g := b[i]
 459                                         if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
 460                                                 return false
 461                                         }
 462                                 }
 463                                 return true
 464                         }
 465                 }
 466
 467         case *Map:
 468                 // Two map types are identical if they have identical key and value types.
 469                 if y, ok := y.(*Map); ok {
 470                         return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p)
 471                 }
 472
 473         case *Chan:
 474                 // Two channel types are identical if they have identical value types.
 475                 if y, ok := y.(*Chan); ok {
 476                         return u.nify(x.elem, y.elem, p)
 477                 }
 478
 479         case *Named:
 480                 // TODO(gri) This code differs now from the parallel code in Checker.identical. Investigate.
 481                 if y, ok := y.(*Named); ok {
 482                         xargs := x.TypeArgs().list()
 483                         yargs := y.TypeArgs().list()
 484
 485                         if len(xargs) != len(yargs) {
 486                                 return false
 487                         }
 488
 489                         // TODO(gri) This is not always correct: two types may have the same names
 490                         //           in the same package if one of them is nested in a function.
 491                         //           Extremely unlikely but we need an always correct solution.
 492                         if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
 493                                 for i, x := range xargs {
 494                                         if !u.nify(x, yargs[i], p) {
 495                                                 return false
 496                                         }
 497                                 }
 498                                 return true
 499                         }
 500                 }
 501
 502         case *TypeParam:
 503                 // Two type parameters (which are not part of the type parameters of the
 504                 // enclosing type as those are handled in the beginning of this function)
 505                 // are identical if they originate in the same declaration.
 506                 return x == y
 507
 508         case nil:
 509                 // avoid a crash in case of nil type
 510
 511         default:
 512                 panic(sprintf(nil, true, "u.nify(%s, %s), u.tparams = %s", x, y, u.tparams))
 513         }
 514
 515         return false
 516 }