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