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