1 // Copyright 2013 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 various field and method lookup functions. 6 7 package types2 8 9 import ( 10 "bytes" 11 "cmd/compile/internal/syntax" 12 ) 13 14 // Internal use of LookupFieldOrMethod: If the obj result is a method 15 // associated with a concrete (non-interface) type, the method's signature 16 // may not be fully set up. Call Checker.objDecl(obj, nil) before accessing 17 // the method's type. 18 19 // LookupFieldOrMethod looks up a field or method with given package and name 20 // in T and returns the corresponding *Var or *Func, an index sequence, and a 21 // bool indicating if there were any pointer indirections on the path to the 22 // field or method. If addressable is set, T is the type of an addressable 23 // variable (only matters for method lookups). T must not be nil. 24 // 25 // The last index entry is the field or method index in the (possibly embedded) 26 // type where the entry was found, either: 27 // 28 // 1. the list of declared methods of a named type; or 29 // 2. the list of all methods (method set) of an interface type; or 30 // 3. the list of fields of a struct type. 31 // 32 // The earlier index entries are the indices of the embedded struct fields 33 // traversed to get to the found entry, starting at depth 0. 34 // 35 // If no entry is found, a nil object is returned. In this case, the returned 36 // index and indirect values have the following meaning: 37 // 38 // - If index != nil, the index sequence points to an ambiguous entry 39 // (the same name appeared more than once at the same embedding level). 40 // 41 // - If indirect is set, a method with a pointer receiver type was found 42 // but there was no pointer on the path from the actual receiver type to 43 // the method's formal receiver base type, nor was the receiver addressable. 44 func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) { 45 if T == nil { 46 panic("LookupFieldOrMethod on nil type") 47 } 48 return lookupFieldOrMethod(T, addressable, pkg, name, false) 49 } 50 51 // lookupFieldOrMethod is like LookupFieldOrMethod but with the additional foldCase parameter 52 // (see Object.sameId for the meaning of foldCase). 53 func lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string, foldCase bool) (obj Object, index []int, indirect bool) { 54 // Methods cannot be associated to a named pointer type. 55 // (spec: "The type denoted by T is called the receiver base type; 56 // it must not be a pointer or interface type and it must be declared 57 // in the same package as the method."). 58 // Thus, if we have a named pointer type, proceed with the underlying 59 // pointer type but discard the result if it is a method since we would 60 // not have found it for T (see also go.dev/issue/8590). 61 if t := asNamed(T); t != nil { 62 if p, _ := t.Underlying().(*Pointer); p != nil { 63 obj, index, indirect = lookupFieldOrMethodImpl(p, false, pkg, name, foldCase) 64 if _, ok := obj.(*Func); ok { 65 return nil, nil, false 66 } 67 return 68 } 69 } 70 71 obj, index, indirect = lookupFieldOrMethodImpl(T, addressable, pkg, name, foldCase) 72 73 // If we didn't find anything and if we have a type parameter with a core type, 74 // see if there is a matching field (but not a method, those need to be declared 75 // explicitly in the constraint). If the constraint is a named pointer type (see 76 // above), we are ok here because only fields are accepted as results. 77 const enableTParamFieldLookup = false // see go.dev/issue/51576 78 if enableTParamFieldLookup && obj == nil && isTypeParam(T) { 79 if t := coreType(T); t != nil { 80 obj, index, indirect = lookupFieldOrMethodImpl(t, addressable, pkg, name, foldCase) 81 if _, ok := obj.(*Var); !ok { 82 obj, index, indirect = nil, nil, false // accept fields (variables) only 83 } 84 } 85 } 86 return 87 } 88 89 // lookupFieldOrMethodImpl is the implementation of lookupFieldOrMethod. 90 // Notably, in contrast to lookupFieldOrMethod, it won't find struct fields 91 // in base types of defined (*Named) pointer types T. For instance, given 92 // the declaration: 93 // 94 // type T *struct{f int} 95 // 96 // lookupFieldOrMethodImpl won't find the field f in the defined (*Named) type T 97 // (methods on T are not permitted in the first place). 98 // 99 // Thus, lookupFieldOrMethodImpl should only be called by lookupFieldOrMethod 100 // and missingMethod (the latter doesn't care about struct fields). 101 // 102 // The resulting object may not be fully type-checked. 103 func lookupFieldOrMethodImpl(T Type, addressable bool, pkg *Package, name string, foldCase bool) (obj Object, index []int, indirect bool) { 104 // WARNING: The code in this function is extremely subtle - do not modify casually! 105 106 if name == "_" { 107 return // blank fields/methods are never found 108 } 109 110 // Importantly, we must not call under before the call to deref below (nor 111 // does deref call under), as doing so could incorrectly result in finding 112 // methods of the pointer base type when T is a (*Named) pointer type. 113 typ, isPtr := deref(T) 114 115 // *typ where typ is an interface (incl. a type parameter) has no methods. 116 if isPtr { 117 if _, ok := under(typ).(*Interface); ok { 118 return 119 } 120 } 121 122 // Start with typ as single entry at shallowest depth. 123 current := []embeddedType{{typ, nil, isPtr, false}} 124 125 // seen tracks named types that we have seen already, allocated lazily. 126 // Used to avoid endless searches in case of recursive types. 127 // 128 // We must use a lookup on identity rather than a simple map[*Named]bool as 129 // instantiated types may be identical but not equal. 130 var seen instanceLookup 131 132 // search current depth 133 for len(current) > 0 { 134 var next []embeddedType // embedded types found at current depth 135 136 // look for (pkg, name) in all types at current depth 137 for _, e := range current { 138 typ := e.typ 139 140 // If we have a named type, we may have associated methods. 141 // Look for those first. 142 if named := asNamed(typ); named != nil { 143 if alt := seen.lookup(named); alt != nil { 144 // We have seen this type before, at a more shallow depth 145 // (note that multiples of this type at the current depth 146 // were consolidated before). The type at that depth shadows 147 // this same type at the current depth, so we can ignore 148 // this one. 149 continue 150 } 151 seen.add(named) 152 153 // look for a matching attached method 154 if i, m := named.lookupMethod(pkg, name, foldCase); m != nil { 155 // potential match 156 // caution: method may not have a proper signature yet 157 index = concat(e.index, i) 158 if obj != nil || e.multiples { 159 return nil, index, false // collision 160 } 161 obj = m 162 indirect = e.indirect 163 continue // we can't have a matching field or interface method 164 } 165 } 166 167 switch t := under(typ).(type) { 168 case *Struct: 169 // look for a matching field and collect embedded types 170 for i, f := range t.fields { 171 if f.sameId(pkg, name, foldCase) { 172 assert(f.typ != nil) 173 index = concat(e.index, i) 174 if obj != nil || e.multiples { 175 return nil, index, false // collision 176 } 177 obj = f 178 indirect = e.indirect 179 continue // we can't have a matching interface method 180 } 181 // Collect embedded struct fields for searching the next 182 // lower depth, but only if we have not seen a match yet 183 // (if we have a match it is either the desired field or 184 // we have a name collision on the same depth; in either 185 // case we don't need to look further). 186 // Embedded fields are always of the form T or *T where 187 // T is a type name. If e.typ appeared multiple times at 188 // this depth, f.typ appears multiple times at the next 189 // depth. 190 if obj == nil && f.embedded { 191 typ, isPtr := deref(f.typ) 192 // TODO(gri) optimization: ignore types that can't 193 // have fields or methods (only Named, Struct, and 194 // Interface types need to be considered). 195 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples}) 196 } 197 } 198 199 case *Interface: 200 // look for a matching method (interface may be a type parameter) 201 if i, m := t.typeSet().LookupMethod(pkg, name, foldCase); m != nil { 202 assert(m.typ != nil) 203 index = concat(e.index, i) 204 if obj != nil || e.multiples { 205 return nil, index, false // collision 206 } 207 obj = m 208 indirect = e.indirect 209 } 210 } 211 } 212 213 if obj != nil { 214 // found a potential match 215 // spec: "A method call x.m() is valid if the method set of (the type of) x 216 // contains m and the argument list can be assigned to the parameter 217 // list of m. If x is addressable and &x's method set contains m, x.m() 218 // is shorthand for (&x).m()". 219 if f, _ := obj.(*Func); f != nil { 220 // determine if method has a pointer receiver 221 if f.hasPtrRecv() && !indirect && !addressable { 222 return nil, nil, true // pointer/addressable receiver required 223 } 224 } 225 return 226 } 227 228 current = consolidateMultiples(next) 229 } 230 231 return nil, nil, false // not found 232 } 233 234 // embeddedType represents an embedded type 235 type embeddedType struct { 236 typ Type 237 index []int // embedded field indices, starting with index at depth 0 238 indirect bool // if set, there was a pointer indirection on the path to this field 239 multiples bool // if set, typ appears multiple times at this depth 240 } 241 242 // consolidateMultiples collects multiple list entries with the same type 243 // into a single entry marked as containing multiples. The result is the 244 // consolidated list. 245 func consolidateMultiples(list []embeddedType) []embeddedType { 246 if len(list) <= 1 { 247 return list // at most one entry - nothing to do 248 } 249 250 n := 0 // number of entries w/ unique type 251 prev := make(map[Type]int) // index at which type was previously seen 252 for _, e := range list { 253 if i, found := lookupType(prev, e.typ); found { 254 list[i].multiples = true 255 // ignore this entry 256 } else { 257 prev[e.typ] = n 258 list[n] = e 259 n++ 260 } 261 } 262 return list[:n] 263 } 264 265 func lookupType(m map[Type]int, typ Type) (int, bool) { 266 // fast path: maybe the types are equal 267 if i, found := m[typ]; found { 268 return i, true 269 } 270 271 for t, i := range m { 272 if Identical(t, typ) { 273 return i, true 274 } 275 } 276 277 return 0, false 278 } 279 280 type instanceLookup struct { 281 // buf is used to avoid allocating the map m in the common case of a small 282 // number of instances. 283 buf [3]*Named 284 m map[*Named][]*Named 285 } 286 287 func (l *instanceLookup) lookup(inst *Named) *Named { 288 for _, t := range l.buf { 289 if t != nil && Identical(inst, t) { 290 return t 291 } 292 } 293 for _, t := range l.m[inst.Origin()] { 294 if Identical(inst, t) { 295 return t 296 } 297 } 298 return nil 299 } 300 301 func (l *instanceLookup) add(inst *Named) { 302 for i, t := range l.buf { 303 if t == nil { 304 l.buf[i] = inst 305 return 306 } 307 } 308 if l.m == nil { 309 l.m = make(map[*Named][]*Named) 310 } 311 insts := l.m[inst.Origin()] 312 l.m[inst.Origin()] = append(insts, inst) 313 } 314 315 // MissingMethod returns (nil, false) if V implements T, otherwise it 316 // returns a missing method required by T and whether it is missing or 317 // just has the wrong type: either a pointer receiver or wrong signature. 318 // 319 // For non-interface types V, or if static is set, V implements T if all 320 // methods of T are present in V. Otherwise (V is an interface and static 321 // is not set), MissingMethod only checks that methods of T which are also 322 // present in V have matching types (e.g., for a type assertion x.(T) where 323 // x is of interface type V). 324 func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) { 325 return (*Checker)(nil).missingMethod(V, T, static, Identical, nil) 326 } 327 328 // missingMethod is like MissingMethod but accepts a *Checker as receiver, 329 // a comparator equivalent for type comparison, and a *string for error causes. 330 // The receiver may be nil if missingMethod is invoked through an exported 331 // API call (such as MissingMethod), i.e., when all methods have been type- 332 // checked. 333 // The underlying type of T must be an interface; T (rather than its under- 334 // lying type) is used for better error messages (reported through *cause). 335 // The comparator is used to compare signatures. 336 // If a method is missing and cause is not nil, *cause describes the error. 337 func (check *Checker) missingMethod(V, T Type, static bool, equivalent func(x, y Type) bool, cause *string) (method *Func, wrongType bool) { 338 methods := under(T).(*Interface).typeSet().methods // T must be an interface 339 if len(methods) == 0 { 340 return nil, false 341 } 342 343 const ( 344 ok = iota 345 notFound 346 wrongName 347 unexported 348 wrongSig 349 ambigSel 350 ptrRecv 351 field 352 ) 353 354 state := ok 355 var m *Func // method on T we're trying to implement 356 var f *Func // method on V, if found (state is one of ok, wrongName, wrongSig) 357 358 if u, _ := under(V).(*Interface); u != nil { 359 tset := u.typeSet() 360 for _, m = range methods { 361 _, f = tset.LookupMethod(m.pkg, m.name, false) 362 363 if f == nil { 364 if !static { 365 continue 366 } 367 state = notFound 368 break 369 } 370 371 if !equivalent(f.typ, m.typ) { 372 state = wrongSig 373 break 374 } 375 } 376 } else { 377 for _, m = range methods { 378 obj, index, indirect := lookupFieldOrMethodImpl(V, false, m.pkg, m.name, false) 379 380 // check if m is ambiguous, on *V, or on V with case-folding 381 if obj == nil { 382 switch { 383 case index != nil: 384 state = ambigSel 385 case indirect: 386 state = ptrRecv 387 default: 388 state = notFound 389 obj, _, _ = lookupFieldOrMethodImpl(V, false, m.pkg, m.name, true /* fold case */) 390 f, _ = obj.(*Func) 391 if f != nil { 392 state = wrongName 393 if f.name == m.name { 394 // If the names are equal, f must be unexported 395 // (otherwise the package wouldn't matter). 396 state = unexported 397 } 398 } 399 } 400 break 401 } 402 403 // we must have a method (not a struct field) 404 f, _ = obj.(*Func) 405 if f == nil { 406 state = field 407 break 408 } 409 410 // methods may not have a fully set up signature yet 411 if check != nil { 412 check.objDecl(f, nil) 413 } 414 415 if !equivalent(f.typ, m.typ) { 416 state = wrongSig 417 break 418 } 419 } 420 } 421 422 if state == ok { 423 return nil, false 424 } 425 426 if cause != nil { 427 if f != nil { 428 // This method may be formatted in funcString below, so must have a fully 429 // set up signature. 430 if check != nil { 431 check.objDecl(f, nil) 432 } 433 } 434 switch state { 435 case notFound: 436 switch { 437 case isInterfacePtr(V): 438 *cause = "(" + check.interfacePtrError(V) + ")" 439 case isInterfacePtr(T): 440 *cause = "(" + check.interfacePtrError(T) + ")" 441 default: 442 *cause = check.sprintf("(missing method %s)", m.Name()) 443 } 444 case wrongName: 445 fs, ms := check.funcString(f, false), check.funcString(m, false) 446 *cause = check.sprintf("(missing method %s)\n\t\thave %s\n\t\twant %s", m.Name(), fs, ms) 447 case unexported: 448 *cause = check.sprintf("(unexported method %s)", m.Name()) 449 case wrongSig: 450 fs, ms := check.funcString(f, false), check.funcString(m, false) 451 if fs == ms { 452 // Don't report "want Foo, have Foo". 453 // Add package information to disambiguate (go.dev/issue/54258). 454 fs, ms = check.funcString(f, true), check.funcString(m, true) 455 } 456 if fs == ms { 457 // We still have "want Foo, have Foo". 458 // This is most likely due to different type parameters with 459 // the same name appearing in the instantiated signatures 460 // (go.dev/issue/61685). 461 // Rather than reporting this misleading error cause, for now 462 // just point out that the method signature is incorrect. 463 // TODO(gri) should find a good way to report the root cause 464 *cause = check.sprintf("(wrong type for method %s)", m.Name()) 465 break 466 } 467 *cause = check.sprintf("(wrong type for method %s)\n\t\thave %s\n\t\twant %s", m.Name(), fs, ms) 468 case ambigSel: 469 *cause = check.sprintf("(ambiguous selector %s.%s)", V, m.Name()) 470 case ptrRecv: 471 *cause = check.sprintf("(method %s has pointer receiver)", m.Name()) 472 case field: 473 *cause = check.sprintf("(%s.%s is a field, not a method)", V, m.Name()) 474 default: 475 panic("unreachable") 476 } 477 } 478 479 return m, state == wrongSig || state == ptrRecv 480 } 481 482 func isInterfacePtr(T Type) bool { 483 p, _ := under(T).(*Pointer) 484 return p != nil && IsInterface(p.base) 485 } 486 487 // check may be nil. 488 func (check *Checker) interfacePtrError(T Type) string { 489 assert(isInterfacePtr(T)) 490 if p, _ := under(T).(*Pointer); isTypeParam(p.base) { 491 return check.sprintf("type %s is pointer to type parameter, not type parameter", T) 492 } 493 return check.sprintf("type %s is pointer to interface, not interface", T) 494 } 495 496 // funcString returns a string of the form name + signature for f. 497 // check may be nil. 498 func (check *Checker) funcString(f *Func, pkgInfo bool) string { 499 buf := bytes.NewBufferString(f.name) 500 var qf Qualifier 501 if check != nil && !pkgInfo { 502 qf = check.qualifier 503 } 504 w := newTypeWriter(buf, qf) 505 w.pkgInfo = pkgInfo 506 w.paramNames = false 507 w.signature(f.typ.(*Signature)) 508 return buf.String() 509 } 510 511 // assertableTo reports whether a value of type V can be asserted to have type T. 512 // The receiver may be nil if assertableTo is invoked through an exported API call 513 // (such as AssertableTo), i.e., when all methods have been type-checked. 514 // The underlying type of V must be an interface. 515 // If the result is false and cause is not nil, *cause describes the error. 516 // TODO(gri) replace calls to this function with calls to newAssertableTo. 517 func (check *Checker) assertableTo(V, T Type, cause *string) bool { 518 // no static check is required if T is an interface 519 // spec: "If T is an interface type, x.(T) asserts that the 520 // dynamic type of x implements the interface T." 521 if IsInterface(T) { 522 return true 523 } 524 // TODO(gri) fix this for generalized interfaces 525 m, _ := check.missingMethod(T, V, false, Identical, cause) 526 return m == nil 527 } 528 529 // newAssertableTo reports whether a value of type V can be asserted to have type T. 530 // It also implements behavior for interfaces that currently are only permitted 531 // in constraint position (we have not yet defined that behavior in the spec). 532 // The underlying type of V must be an interface. 533 // If the result is false and cause is not nil, *cause is set to the error cause. 534 func (check *Checker) newAssertableTo(pos syntax.Pos, V, T Type, cause *string) bool { 535 // no static check is required if T is an interface 536 // spec: "If T is an interface type, x.(T) asserts that the 537 // dynamic type of x implements the interface T." 538 if IsInterface(T) { 539 return true 540 } 541 return check.implements(pos, T, V, false, cause) 542 } 543 544 // deref dereferences typ if it is a *Pointer (but not a *Named type 545 // with an underlying pointer type!) and returns its base and true. 546 // Otherwise it returns (typ, false). 547 func deref(typ Type) (Type, bool) { 548 if p, _ := Unalias(typ).(*Pointer); p != nil { 549 // p.base should never be nil, but be conservative 550 if p.base == nil { 551 if debug { 552 panic("pointer with nil base type (possibly due to an invalid cyclic declaration)") 553 } 554 return Typ[Invalid], true 555 } 556 return p.base, true 557 } 558 return typ, false 559 } 560 561 // derefStructPtr dereferences typ if it is a (named or unnamed) pointer to a 562 // (named or unnamed) struct and returns its base. Otherwise it returns typ. 563 func derefStructPtr(typ Type) Type { 564 if p, _ := under(typ).(*Pointer); p != nil { 565 if _, ok := under(p.base).(*Struct); ok { 566 return p.base 567 } 568 } 569 return typ 570 } 571 572 // concat returns the result of concatenating list and i. 573 // The result does not share its underlying array with list. 574 func concat(list []int, i int) []int { 575 var t []int 576 t = append(t, list...) 577 return append(t, i) 578 } 579 580 // fieldIndex returns the index for the field with matching package and name, or a value < 0. 581 // See Object.sameId for the meaning of foldCase. 582 func fieldIndex(fields []*Var, pkg *Package, name string, foldCase bool) int { 583 if name != "_" { 584 for i, f := range fields { 585 if f.sameId(pkg, name, foldCase) { 586 return i 587 } 588 } 589 } 590 return -1 591 } 592 593 // methodIndex returns the index of and method with matching package and name, or (-1, nil). 594 // See Object.sameId for the meaning of foldCase. 595 func methodIndex(methods []*Func, pkg *Package, name string, foldCase bool) (int, *Func) { 596 if name != "_" { 597 for i, m := range methods { 598 if m.sameId(pkg, name, foldCase) { 599 return i, m 600 } 601 } 602 } 603 return -1, nil 604 } 605