lookup.go

     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
View as plain text