Source file src/go/types/lookup.go

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

View as plain text