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