Source file src/go/types/infer.go
1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT. 2 // Source: ../../cmd/compile/internal/types2/infer.go 3 4 // Copyright 2018 The Go Authors. All rights reserved. 5 // Use of this source code is governed by a BSD-style 6 // license that can be found in the LICENSE file. 7 8 // This file implements type parameter inference. 9 10 package types 11 12 import ( 13 "fmt" 14 "go/token" 15 "strings" 16 ) 17 18 // If enableReverseTypeInference is set, uninstantiated and 19 // partially instantiated generic functions may be assigned 20 // (incl. returned) to variables of function type and type 21 // inference will attempt to infer the missing type arguments. 22 // Available with go1.21. 23 const enableReverseTypeInference = true // disable for debugging 24 25 // infer attempts to infer the complete set of type arguments for generic function instantiation/call 26 // based on the given type parameters tparams, type arguments targs, function parameters params, and 27 // function arguments args, if any. There must be at least one type parameter, no more type arguments 28 // than type parameters, and params and args must match in number (incl. zero). 29 // If reverse is set, an error message's contents are reversed for a better error message for some 30 // errors related to reverse type inference (where the function call is synthetic). 31 // If successful, infer returns the complete list of given and inferred type arguments, one for each 32 // type parameter. Otherwise the result is nil. Errors are reported through the err parameter. 33 // Note: infer may fail (return nil) due to invalid args operands without reporting additional errors. 34 func (check *Checker) infer(posn positioner, tparams []*TypeParam, targs []Type, params *Tuple, args []*operand, reverse bool, err *error_) (inferred []Type) { 35 // Don't verify result conditions if there's no error handler installed: 36 // in that case, an error leads to an exit panic and the result value may 37 // be incorrect. But in that case it doesn't matter because callers won't 38 // be able to use it either. 39 if check.conf.Error != nil { 40 defer func() { 41 assert(inferred == nil || len(inferred) == len(tparams) && !containsNil(inferred)) 42 }() 43 } 44 45 if traceInference { 46 check.dump("== infer : %s%s ➞ %s", tparams, params, targs) // aligned with rename print below 47 defer func() { 48 check.dump("=> %s ➞ %s\n", tparams, inferred) 49 }() 50 } 51 52 // There must be at least one type parameter, and no more type arguments than type parameters. 53 n := len(tparams) 54 assert(n > 0 && len(targs) <= n) 55 56 // Parameters and arguments must match in number. 57 assert(params.Len() == len(args)) 58 59 // If we already have all type arguments, we're done. 60 if len(targs) == n && !containsNil(targs) { 61 return targs 62 } 63 64 // If we have invalid (ordinary) arguments, an error was reported before. 65 // Avoid additional inference errors and exit early (go.dev/issue/60434). 66 for _, arg := range args { 67 if arg.mode == invalid { 68 return nil 69 } 70 } 71 72 // Make sure we have a "full" list of type arguments, some of which may 73 // be nil (unknown). Make a copy so as to not clobber the incoming slice. 74 if len(targs) < n { 75 targs2 := make([]Type, n) 76 copy(targs2, targs) 77 targs = targs2 78 } 79 // len(targs) == n 80 81 // Continue with the type arguments we have. Avoid matching generic 82 // parameters that already have type arguments against function arguments: 83 // It may fail because matching uses type identity while parameter passing 84 // uses assignment rules. Instantiate the parameter list with the type 85 // arguments we have, and continue with that parameter list. 86 87 // Substitute type arguments for their respective type parameters in params, 88 // if any. Note that nil targs entries are ignored by check.subst. 89 // We do this for better error messages; it's not needed for correctness. 90 // For instance, given: 91 // 92 // func f[P, Q any](P, Q) {} 93 // 94 // func _(s string) { 95 // f[int](s, s) // ERROR 96 // } 97 // 98 // With substitution, we get the error: 99 // "cannot use s (variable of type string) as int value in argument to f[int]" 100 // 101 // Without substitution we get the (worse) error: 102 // "type string of s does not match inferred type int for P" 103 // even though the type int was provided (not inferred) for P. 104 // 105 // TODO(gri) We might be able to finesse this in the error message reporting 106 // (which only happens in case of an error) and then avoid doing 107 // the substitution (which always happens). 108 if params.Len() > 0 { 109 smap := makeSubstMap(tparams, targs) 110 params = check.subst(nopos, params, smap, nil, check.context()).(*Tuple) 111 } 112 113 // Unify parameter and argument types for generic parameters with typed arguments 114 // and collect the indices of generic parameters with untyped arguments. 115 // Terminology: generic parameter = function parameter with a type-parameterized type 116 u := newUnifier(tparams, targs, check.allowVersion(posn, go1_21)) 117 118 errorf := func(tpar, targ Type, arg *operand) { 119 // provide a better error message if we can 120 targs := u.inferred(tparams) 121 if targs[0] == nil { 122 // The first type parameter couldn't be inferred. 123 // If none of them could be inferred, don't try 124 // to provide the inferred type in the error msg. 125 allFailed := true 126 for _, targ := range targs { 127 if targ != nil { 128 allFailed = false 129 break 130 } 131 } 132 if allFailed { 133 err.addf(arg, "type %s of %s does not match %s (cannot infer %s)", targ, arg.expr, tpar, typeParamsString(tparams)) 134 return 135 } 136 } 137 smap := makeSubstMap(tparams, targs) 138 // TODO(gri): pass a poser here, rather than arg.Pos(). 139 inferred := check.subst(arg.Pos(), tpar, smap, nil, check.context()) 140 // CannotInferTypeArgs indicates a failure of inference, though the actual 141 // error may be better attributed to a user-provided type argument (hence 142 // InvalidTypeArg). We can't differentiate these cases, so fall back on 143 // the more general CannotInferTypeArgs. 144 if inferred != tpar { 145 if reverse { 146 err.addf(arg, "inferred type %s for %s does not match type %s of %s", inferred, tpar, targ, arg.expr) 147 } else { 148 err.addf(arg, "type %s of %s does not match inferred type %s for %s", targ, arg.expr, inferred, tpar) 149 } 150 } else { 151 err.addf(arg, "type %s of %s does not match %s", targ, arg.expr, tpar) 152 } 153 } 154 155 // indices of generic parameters with untyped arguments, for later use 156 var untyped []int 157 158 // --- 1 --- 159 // use information from function arguments 160 161 if traceInference { 162 u.tracef("== function parameters: %s", params) 163 u.tracef("-- function arguments : %s", args) 164 } 165 166 for i, arg := range args { 167 if arg.mode == invalid { 168 // An error was reported earlier. Ignore this arg 169 // and continue, we may still be able to infer all 170 // targs resulting in fewer follow-on errors. 171 // TODO(gri) determine if we still need this check 172 continue 173 } 174 par := params.At(i) 175 if isParameterized(tparams, par.typ) || isParameterized(tparams, arg.typ) { 176 // Function parameters are always typed. Arguments may be untyped. 177 // Collect the indices of untyped arguments and handle them later. 178 if isTyped(arg.typ) { 179 if !u.unify(par.typ, arg.typ, assign) { 180 errorf(par.typ, arg.typ, arg) 181 return nil 182 } 183 } else if _, ok := par.typ.(*TypeParam); ok && !arg.isNil() { 184 // Since default types are all basic (i.e., non-composite) types, an 185 // untyped argument will never match a composite parameter type; the 186 // only parameter type it can possibly match against is a *TypeParam. 187 // Thus, for untyped arguments we only need to look at parameter types 188 // that are single type parameters. 189 // Also, untyped nils don't have a default type and can be ignored. 190 // Finally, it's not possible to have an alias type denoting a type 191 // parameter declared by the current function and use it in the same 192 // function signature; hence we don't need to Unalias before the 193 // .(*TypeParam) type assertion above. 194 untyped = append(untyped, i) 195 } 196 } 197 } 198 199 if traceInference { 200 inferred := u.inferred(tparams) 201 u.tracef("=> %s ➞ %s\n", tparams, inferred) 202 } 203 204 // --- 2 --- 205 // use information from type parameter constraints 206 207 if traceInference { 208 u.tracef("== type parameters: %s", tparams) 209 } 210 211 // Unify type parameters with their constraints as long 212 // as progress is being made. 213 // 214 // This is an O(n^2) algorithm where n is the number of 215 // type parameters: if there is progress, at least one 216 // type argument is inferred per iteration, and we have 217 // a doubly nested loop. 218 // 219 // In practice this is not a problem because the number 220 // of type parameters tends to be very small (< 5 or so). 221 // (It should be possible for unification to efficiently 222 // signal newly inferred type arguments; then the loops 223 // here could handle the respective type parameters only, 224 // but that will come at a cost of extra complexity which 225 // may not be worth it.) 226 for i := 0; ; i++ { 227 nn := u.unknowns() 228 if traceInference { 229 if i > 0 { 230 fmt.Println() 231 } 232 u.tracef("-- iteration %d", i) 233 } 234 235 for _, tpar := range tparams { 236 tx := u.at(tpar) 237 core, single := coreTerm(tpar) 238 if traceInference { 239 u.tracef("-- type parameter %s = %s: core(%s) = %s, single = %v", tpar, tx, tpar, core, single) 240 } 241 242 // If there is a core term (i.e., a core type with tilde information) 243 // unify the type parameter with the core type. 244 if core != nil { 245 // A type parameter can be unified with its core type in two cases. 246 switch { 247 case tx != nil: 248 // The corresponding type argument tx is known. There are 2 cases: 249 // 1) If the core type has a tilde, per spec requirement for tilde 250 // elements, the core type is an underlying (literal) type. 251 // And because of the tilde, the underlying type of tx must match 252 // against the core type. 253 // But because unify automatically matches a defined type against 254 // an underlying literal type, we can simply unify tx with the 255 // core type. 256 // 2) If the core type doesn't have a tilde, we also must unify tx 257 // with the core type. 258 if !u.unify(tx, core.typ, 0) { 259 // TODO(gri) Type parameters that appear in the constraint and 260 // for which we have type arguments inferred should 261 // use those type arguments for a better error message. 262 err.addf(posn, "%s (type %s) does not satisfy %s", tpar, tx, tpar.Constraint()) 263 return nil 264 } 265 case single && !core.tilde: 266 // The corresponding type argument tx is unknown and there's a single 267 // specific type and no tilde. 268 // In this case the type argument must be that single type; set it. 269 u.set(tpar, core.typ) 270 } 271 } else { 272 if tx != nil { 273 // We don't have a core type, but the type argument tx is known. 274 // It must have (at least) all the methods of the type constraint, 275 // and the method signatures must unify; otherwise tx cannot satisfy 276 // the constraint. 277 // TODO(gri) Now that unification handles interfaces, this code can 278 // be reduced to calling u.unify(tx, tpar.iface(), assign) 279 // (which will compare signatures exactly as we do below). 280 // We leave it as is for now because missingMethod provides 281 // a failure cause which allows for a better error message. 282 // Eventually, unify should return an error with cause. 283 var cause string 284 constraint := tpar.iface() 285 if m, _ := check.missingMethod(tx, constraint, true, func(x, y Type) bool { return u.unify(x, y, exact) }, &cause); m != nil { 286 // TODO(gri) better error message (see TODO above) 287 err.addf(posn, "%s (type %s) does not satisfy %s %s", tpar, tx, tpar.Constraint(), cause) 288 return nil 289 } 290 } 291 } 292 } 293 294 if u.unknowns() == nn { 295 break // no progress 296 } 297 } 298 299 if traceInference { 300 inferred := u.inferred(tparams) 301 u.tracef("=> %s ➞ %s\n", tparams, inferred) 302 } 303 304 // --- 3 --- 305 // use information from untyped constants 306 307 if traceInference { 308 u.tracef("== untyped arguments: %v", untyped) 309 } 310 311 // Some generic parameters with untyped arguments may have been given a type by now. 312 // Collect all remaining parameters that don't have a type yet and determine the 313 // maximum untyped type for each of those parameters, if possible. 314 var maxUntyped map[*TypeParam]Type // lazily allocated (we may not need it) 315 for _, index := range untyped { 316 tpar := params.At(index).typ.(*TypeParam) // is type parameter (no alias) by construction of untyped 317 if u.at(tpar) == nil { 318 arg := args[index] // arg corresponding to tpar 319 if maxUntyped == nil { 320 maxUntyped = make(map[*TypeParam]Type) 321 } 322 max := maxUntyped[tpar] 323 if max == nil { 324 max = arg.typ 325 } else { 326 m := maxType(max, arg.typ) 327 if m == nil { 328 err.addf(arg, "mismatched types %s and %s (cannot infer %s)", max, arg.typ, tpar) 329 return nil 330 } 331 max = m 332 } 333 maxUntyped[tpar] = max 334 } 335 } 336 // maxUntyped contains the maximum untyped type for each type parameter 337 // which doesn't have a type yet. Set the respective default types. 338 for tpar, typ := range maxUntyped { 339 d := Default(typ) 340 assert(isTyped(d)) 341 u.set(tpar, d) 342 } 343 344 // --- simplify --- 345 346 // u.inferred(tparams) now contains the incoming type arguments plus any additional type 347 // arguments which were inferred. The inferred non-nil entries may still contain 348 // references to other type parameters found in constraints. 349 // For instance, for [A any, B interface{ []C }, C interface{ *A }], if A == int 350 // was given, unification produced the type list [int, []C, *A]. We eliminate the 351 // remaining type parameters by substituting the type parameters in this type list 352 // until nothing changes anymore. 353 inferred = u.inferred(tparams) 354 if debug { 355 for i, targ := range targs { 356 assert(targ == nil || inferred[i] == targ) 357 } 358 } 359 360 // The data structure of each (provided or inferred) type represents a graph, where 361 // each node corresponds to a type and each (directed) vertex points to a component 362 // type. The substitution process described above repeatedly replaces type parameter 363 // nodes in these graphs with the graphs of the types the type parameters stand for, 364 // which creates a new (possibly bigger) graph for each type. 365 // The substitution process will not stop if the replacement graph for a type parameter 366 // also contains that type parameter. 367 // For instance, for [A interface{ *A }], without any type argument provided for A, 368 // unification produces the type list [*A]. Substituting A in *A with the value for 369 // A will lead to infinite expansion by producing [**A], [****A], [********A], etc., 370 // because the graph A -> *A has a cycle through A. 371 // Generally, cycles may occur across multiple type parameters and inferred types 372 // (for instance, consider [P interface{ *Q }, Q interface{ func(P) }]). 373 // We eliminate cycles by walking the graphs for all type parameters. If a cycle 374 // through a type parameter is detected, killCycles nils out the respective type 375 // (in the inferred list) which kills the cycle, and marks the corresponding type 376 // parameter as not inferred. 377 // 378 // TODO(gri) If useful, we could report the respective cycle as an error. We don't 379 // do this now because type inference will fail anyway, and furthermore, 380 // constraints with cycles of this kind cannot currently be satisfied by 381 // any user-supplied type. But should that change, reporting an error 382 // would be wrong. 383 killCycles(tparams, inferred) 384 385 // dirty tracks the indices of all types that may still contain type parameters. 386 // We know that nil type entries and entries corresponding to provided (non-nil) 387 // type arguments are clean, so exclude them from the start. 388 var dirty []int 389 for i, typ := range inferred { 390 if typ != nil && (i >= len(targs) || targs[i] == nil) { 391 dirty = append(dirty, i) 392 } 393 } 394 395 for len(dirty) > 0 { 396 if traceInference { 397 u.tracef("-- simplify %s ➞ %s", tparams, inferred) 398 } 399 // TODO(gri) Instead of creating a new substMap for each iteration, 400 // provide an update operation for substMaps and only change when 401 // needed. Optimization. 402 smap := makeSubstMap(tparams, inferred) 403 n := 0 404 for _, index := range dirty { 405 t0 := inferred[index] 406 if t1 := check.subst(nopos, t0, smap, nil, check.context()); t1 != t0 { 407 // t0 was simplified to t1. 408 // If t0 was a generic function, but the simplified signature t1 does 409 // not contain any type parameters anymore, the function is not generic 410 // anymore. Remove it's type parameters. (go.dev/issue/59953) 411 // Note that if t0 was a signature, t1 must be a signature, and t1 412 // can only be a generic signature if it originated from a generic 413 // function argument. Those signatures are never defined types and 414 // thus there is no need to call under below. 415 // TODO(gri) Consider doing this in Checker.subst. 416 // Then this would fall out automatically here and also 417 // in instantiation (where we also explicitly nil out 418 // type parameters). See the *Signature TODO in subst. 419 if sig, _ := t1.(*Signature); sig != nil && sig.TypeParams().Len() > 0 && !isParameterized(tparams, sig) { 420 sig.tparams = nil 421 } 422 inferred[index] = t1 423 dirty[n] = index 424 n++ 425 } 426 } 427 dirty = dirty[:n] 428 } 429 430 // Once nothing changes anymore, we may still have type parameters left; 431 // e.g., a constraint with core type *P may match a type parameter Q but 432 // we don't have any type arguments to fill in for *P or Q (go.dev/issue/45548). 433 // Don't let such inferences escape; instead treat them as unresolved. 434 for i, typ := range inferred { 435 if typ == nil || isParameterized(tparams, typ) { 436 obj := tparams[i].obj 437 err.addf(posn, "cannot infer %s (%v)", obj.name, obj.pos) 438 return nil 439 } 440 } 441 442 return 443 } 444 445 // containsNil reports whether list contains a nil entry. 446 func containsNil(list []Type) bool { 447 for _, t := range list { 448 if t == nil { 449 return true 450 } 451 } 452 return false 453 } 454 455 // renameTParams renames the type parameters in the given type such that each type 456 // parameter is given a new identity. renameTParams returns the new type parameters 457 // and updated type. If the result type is unchanged from the argument type, none 458 // of the type parameters in tparams occurred in the type. 459 // If typ is a generic function, type parameters held with typ are not changed and 460 // must be updated separately if desired. 461 // The positions is only used for debug traces. 462 func (check *Checker) renameTParams(pos token.Pos, tparams []*TypeParam, typ Type) ([]*TypeParam, Type) { 463 // For the purpose of type inference we must differentiate type parameters 464 // occurring in explicit type or value function arguments from the type 465 // parameters we are solving for via unification because they may be the 466 // same in self-recursive calls: 467 // 468 // func f[P constraint](x P) { 469 // f(x) 470 // } 471 // 472 // In this example, without type parameter renaming, the P used in the 473 // instantiation f[P] has the same pointer identity as the P we are trying 474 // to solve for through type inference. This causes problems for type 475 // unification. Because any such self-recursive call is equivalent to 476 // a mutually recursive call, type parameter renaming can be used to 477 // create separate, disentangled type parameters. The above example 478 // can be rewritten into the following equivalent code: 479 // 480 // func f[P constraint](x P) { 481 // f2(x) 482 // } 483 // 484 // func f2[P2 constraint](x P2) { 485 // f(x) 486 // } 487 // 488 // Type parameter renaming turns the first example into the second 489 // example by renaming the type parameter P into P2. 490 if len(tparams) == 0 { 491 return nil, typ // nothing to do 492 } 493 494 tparams2 := make([]*TypeParam, len(tparams)) 495 for i, tparam := range tparams { 496 tname := NewTypeName(tparam.Obj().Pos(), tparam.Obj().Pkg(), tparam.Obj().Name(), nil) 497 tparams2[i] = NewTypeParam(tname, nil) 498 tparams2[i].index = tparam.index // == i 499 } 500 501 renameMap := makeRenameMap(tparams, tparams2) 502 for i, tparam := range tparams { 503 tparams2[i].bound = check.subst(pos, tparam.bound, renameMap, nil, check.context()) 504 } 505 506 return tparams2, check.subst(pos, typ, renameMap, nil, check.context()) 507 } 508 509 // typeParamsString produces a string containing all the type parameter names 510 // in list suitable for human consumption. 511 func typeParamsString(list []*TypeParam) string { 512 // common cases 513 n := len(list) 514 switch n { 515 case 0: 516 return "" 517 case 1: 518 return list[0].obj.name 519 case 2: 520 return list[0].obj.name + " and " + list[1].obj.name 521 } 522 523 // general case (n > 2) 524 var buf strings.Builder 525 for i, tname := range list[:n-1] { 526 if i > 0 { 527 buf.WriteString(", ") 528 } 529 buf.WriteString(tname.obj.name) 530 } 531 buf.WriteString(", and ") 532 buf.WriteString(list[n-1].obj.name) 533 return buf.String() 534 } 535 536 // isParameterized reports whether typ contains any of the type parameters of tparams. 537 // If typ is a generic function, isParameterized ignores the type parameter declarations; 538 // it only considers the signature proper (incoming and result parameters). 539 func isParameterized(tparams []*TypeParam, typ Type) bool { 540 w := tpWalker{ 541 tparams: tparams, 542 seen: make(map[Type]bool), 543 } 544 return w.isParameterized(typ) 545 } 546 547 type tpWalker struct { 548 tparams []*TypeParam 549 seen map[Type]bool 550 } 551 552 func (w *tpWalker) isParameterized(typ Type) (res bool) { 553 // detect cycles 554 if x, ok := w.seen[typ]; ok { 555 return x 556 } 557 w.seen[typ] = false 558 defer func() { 559 w.seen[typ] = res 560 }() 561 562 switch t := typ.(type) { 563 case *Basic: 564 // nothing to do 565 566 case *Alias: 567 return w.isParameterized(Unalias(t)) 568 569 case *Array: 570 return w.isParameterized(t.elem) 571 572 case *Slice: 573 return w.isParameterized(t.elem) 574 575 case *Struct: 576 return w.varList(t.fields) 577 578 case *Pointer: 579 return w.isParameterized(t.base) 580 581 case *Tuple: 582 // This case does not occur from within isParameterized 583 // because tuples only appear in signatures where they 584 // are handled explicitly. But isParameterized is also 585 // called by Checker.callExpr with a function result tuple 586 // if instantiation failed (go.dev/issue/59890). 587 return t != nil && w.varList(t.vars) 588 589 case *Signature: 590 // t.tparams may not be nil if we are looking at a signature 591 // of a generic function type (or an interface method) that is 592 // part of the type we're testing. We don't care about these type 593 // parameters. 594 // Similarly, the receiver of a method may declare (rather than 595 // use) type parameters, we don't care about those either. 596 // Thus, we only need to look at the input and result parameters. 597 return t.params != nil && w.varList(t.params.vars) || t.results != nil && w.varList(t.results.vars) 598 599 case *Interface: 600 tset := t.typeSet() 601 for _, m := range tset.methods { 602 if w.isParameterized(m.typ) { 603 return true 604 } 605 } 606 return tset.is(func(t *term) bool { 607 return t != nil && w.isParameterized(t.typ) 608 }) 609 610 case *Map: 611 return w.isParameterized(t.key) || w.isParameterized(t.elem) 612 613 case *Chan: 614 return w.isParameterized(t.elem) 615 616 case *Named: 617 for _, t := range t.TypeArgs().list() { 618 if w.isParameterized(t) { 619 return true 620 } 621 } 622 623 case *TypeParam: 624 return tparamIndex(w.tparams, t) >= 0 625 626 default: 627 panic(fmt.Sprintf("unexpected %T", typ)) 628 } 629 630 return false 631 } 632 633 func (w *tpWalker) varList(list []*Var) bool { 634 for _, v := range list { 635 if w.isParameterized(v.typ) { 636 return true 637 } 638 } 639 return false 640 } 641 642 // If the type parameter has a single specific type S, coreTerm returns (S, true). 643 // Otherwise, if tpar has a core type T, it returns a term corresponding to that 644 // core type and false. In that case, if any term of tpar has a tilde, the core 645 // term has a tilde. In all other cases coreTerm returns (nil, false). 646 func coreTerm(tpar *TypeParam) (*term, bool) { 647 n := 0 648 var single *term // valid if n == 1 649 var tilde bool 650 tpar.is(func(t *term) bool { 651 if t == nil { 652 assert(n == 0) 653 return false // no terms 654 } 655 n++ 656 single = t 657 if t.tilde { 658 tilde = true 659 } 660 return true 661 }) 662 if n == 1 { 663 if debug { 664 assert(debug && under(single.typ) == coreType(tpar)) 665 } 666 return single, true 667 } 668 if typ := coreType(tpar); typ != nil { 669 // A core type is always an underlying type. 670 // If any term of tpar has a tilde, we don't 671 // have a precise core type and we must return 672 // a tilde as well. 673 return &term{tilde, typ}, false 674 } 675 return nil, false 676 } 677 678 // killCycles walks through the given type parameters and looks for cycles 679 // created by type parameters whose inferred types refer back to that type 680 // parameter, either directly or indirectly. If such a cycle is detected, 681 // it is killed by setting the corresponding inferred type to nil. 682 // 683 // TODO(gri) Determine if we can simply abort inference as soon as we have 684 // found a single cycle. 685 func killCycles(tparams []*TypeParam, inferred []Type) { 686 w := cycleFinder{tparams, inferred, make(map[Type]bool)} 687 for _, t := range tparams { 688 w.typ(t) // t != nil 689 } 690 } 691 692 type cycleFinder struct { 693 tparams []*TypeParam 694 inferred []Type 695 seen map[Type]bool 696 } 697 698 func (w *cycleFinder) typ(typ Type) { 699 typ = Unalias(typ) 700 if w.seen[typ] { 701 // We have seen typ before. If it is one of the type parameters 702 // in w.tparams, iterative substitution will lead to infinite expansion. 703 // Nil out the corresponding type which effectively kills the cycle. 704 if tpar, _ := typ.(*TypeParam); tpar != nil { 705 if i := tparamIndex(w.tparams, tpar); i >= 0 { 706 // cycle through tpar 707 w.inferred[i] = nil 708 } 709 } 710 // If we don't have one of our type parameters, the cycle is due 711 // to an ordinary recursive type and we can just stop walking it. 712 return 713 } 714 w.seen[typ] = true 715 defer delete(w.seen, typ) 716 717 switch t := typ.(type) { 718 case *Basic: 719 // nothing to do 720 721 // *Alias: 722 // This case should not occur because of Unalias(typ) at the top. 723 724 case *Array: 725 w.typ(t.elem) 726 727 case *Slice: 728 w.typ(t.elem) 729 730 case *Struct: 731 w.varList(t.fields) 732 733 case *Pointer: 734 w.typ(t.base) 735 736 // case *Tuple: 737 // This case should not occur because tuples only appear 738 // in signatures where they are handled explicitly. 739 740 case *Signature: 741 if t.params != nil { 742 w.varList(t.params.vars) 743 } 744 if t.results != nil { 745 w.varList(t.results.vars) 746 } 747 748 case *Union: 749 for _, t := range t.terms { 750 w.typ(t.typ) 751 } 752 753 case *Interface: 754 for _, m := range t.methods { 755 w.typ(m.typ) 756 } 757 for _, t := range t.embeddeds { 758 w.typ(t) 759 } 760 761 case *Map: 762 w.typ(t.key) 763 w.typ(t.elem) 764 765 case *Chan: 766 w.typ(t.elem) 767 768 case *Named: 769 for _, tpar := range t.TypeArgs().list() { 770 w.typ(tpar) 771 } 772 773 case *TypeParam: 774 if i := tparamIndex(w.tparams, t); i >= 0 && w.inferred[i] != nil { 775 w.typ(w.inferred[i]) 776 } 777 778 default: 779 panic(fmt.Sprintf("unexpected %T", typ)) 780 } 781 } 782 783 func (w *cycleFinder) varList(list []*Var) { 784 for _, v := range list { 785 w.typ(v.typ) 786 } 787 } 788 789 // If tpar is a type parameter in list, tparamIndex returns the index 790 // of the type parameter in list. Otherwise the result is < 0. 791 func tparamIndex(list []*TypeParam, tpar *TypeParam) int { 792 for i, p := range list { 793 if p == tpar { 794 return i 795 } 796 } 797 return -1 798 } 799