src/go/types/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 types
   8
   9 import (
  10         "fmt"
  11         "strings"
  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).
  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 //
  45 func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) {
  46         // Methods cannot be associated to a named pointer type
  47         // (spec: "The type denoted by T is called the receiver base type;
  48         // it must not be a pointer or interface type and it must be declared
  49         // in the same package as the method.").
  50         // Thus, if we have a named pointer type, proceed with the underlying
  51         // pointer type but discard the result if it is a method since we would
  52         // not have found it for T (see also issue 8590).
  53         if t := asNamed(T); t != nil {
  54                 if p, _ := safeUnderlying(t).(*Pointer); p != nil {
  55                         obj, index, indirect = lookupFieldOrMethod(p, false, pkg, name)
  56                         if _, ok := obj.(*Func); ok {
  57                                 return nil, nil, false
  58                         }
  59                         return
  60                 }
  61         }
  62
  63         return lookupFieldOrMethod(T, addressable, pkg, name)
  64 }
  65
  66 // TODO(gri) The named type consolidation and seen maps below must be
  67 //           indexed by unique keys for a given type. Verify that named
  68 //           types always have only one representation (even when imported
  69 //           indirectly via different packages.)
  70
  71 // lookupFieldOrMethod should only be called by LookupFieldOrMethod and missingMethod.
  72 //
  73 // The resulting object may not be fully type-checked.
  74 func lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) {
  75         // WARNING: The code in this function is extremely subtle - do not modify casually!
  76
  77         if name == "_" {
  78                 return // blank fields/methods are never found
  79         }
  80
  81         typ, isPtr := deref(T)
  82
  83         // *typ where typ is an interface or type parameter has no methods.
  84         if isPtr {
  85                 // don't look at under(typ) here - was bug (issue #47747)
  86                 if _, ok := typ.(*TypeParam); ok {
  87                         return
  88                 }
  89                 if _, ok := under(typ).(*Interface); ok {
  90                         return
  91                 }
  92         }
  93
  94         // Start with typ as single entry at shallowest depth.
  95         current := []embeddedType{{typ, nil, isPtr, false}}
  96
  97         // Named types that we have seen already, allocated lazily.
  98         // Used to avoid endless searches in case of recursive types.
  99         // Since only Named types can be used for recursive types, we
 100         // only need to track those.
 101         // (If we ever allow type aliases to construct recursive types,
 102         // we must use type identity rather than pointer equality for
 103         // the map key comparison, as we do in consolidateMultiples.)
 104         var seen map[*Named]bool
 105
 106         // search current depth
 107         for len(current) > 0 {
 108                 var next []embeddedType // embedded types found at current depth
 109
 110                 // look for (pkg, name) in all types at current depth
 111                 var tpar *TypeParam // set if obj receiver is a type parameter
 112                 for _, e := range current {
 113                         typ := e.typ
 114
 115                         // If we have a named type, we may have associated methods.
 116                         // Look for those first.
 117                         if named := asNamed(typ); named != nil {
 118                                 if seen[named] {
 119                                         // We have seen this type before, at a more shallow depth
 120                                         // (note that multiples of this type at the current depth
 121                                         // were consolidated before). The type at that depth shadows
 122                                         // this same type at the current depth, so we can ignore
 123                                         // this one.
 124                                         continue
 125                                 }
 126                                 if seen == nil {
 127                                         seen = make(map[*Named]bool)
 128                                 }
 129                                 seen[named] = true
 130
 131                                 // look for a matching attached method
 132                                 if i, m := lookupMethod(named.methods, pkg, name); m != nil {
 133                                         // potential match
 134                                         // caution: method may not have a proper signature yet
 135                                         index = concat(e.index, i)
 136                                         if obj != nil || e.multiples {
 137                                                 return nil, index, false // collision
 138                                         }
 139                                         obj = m
 140                                         indirect = e.indirect
 141                                         continue // we can't have a matching field or interface method
 142                                 }
 143
 144                                 // continue with underlying type
 145                                 typ = named.under()
 146                         }
 147
 148                         tpar = nil
 149                         switch t := typ.(type) {
 150                         case *Struct:
 151                                 // look for a matching field and collect embedded types
 152                                 for i, f := range t.fields {
 153                                         if f.sameId(pkg, name) {
 154                                                 assert(f.typ != nil)
 155                                                 index = concat(e.index, i)
 156                                                 if obj != nil || e.multiples {
 157                                                         return nil, index, false // collision
 158                                                 }
 159                                                 obj = f
 160                                                 indirect = e.indirect
 161                                                 continue // we can't have a matching interface method
 162                                         }
 163                                         // Collect embedded struct fields for searching the next
 164                                         // lower depth, but only if we have not seen a match yet
 165                                         // (if we have a match it is either the desired field or
 166                                         // we have a name collision on the same depth; in either
 167                                         // case we don't need to look further).
 168                                         // Embedded fields are always of the form T or *T where
 169                                         // T is a type name. If e.typ appeared multiple times at
 170                                         // this depth, f.typ appears multiple times at the next
 171                                         // depth.
 172                                         if obj == nil && f.embedded {
 173                                                 typ, isPtr := deref(f.typ)
 174                                                 // TODO(gri) optimization: ignore types that can't
 175                                                 // have fields or methods (only Named, Struct, and
 176                                                 // Interface types need to be considered).
 177                                                 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples})
 178                                         }
 179                                 }
 180
 181                         case *Interface:
 182                                 // look for a matching method
 183                                 if i, m := t.typeSet().LookupMethod(pkg, name); m != nil {
 184                                         assert(m.typ != nil)
 185                                         index = concat(e.index, i)
 186                                         if obj != nil || e.multiples {
 187                                                 return nil, index, false // collision
 188                                         }
 189                                         obj = m
 190                                         indirect = e.indirect
 191                                 }
 192
 193                         case *TypeParam:
 194                                 if i, m := t.iface().typeSet().LookupMethod(pkg, name); m != nil {
 195                                         assert(m.typ != nil)
 196                                         index = concat(e.index, i)
 197                                         if obj != nil || e.multiples {
 198                                                 return nil, index, false // collision
 199                                         }
 200                                         tpar = t
 201                                         obj = m
 202                                         indirect = e.indirect
 203                                 }
 204                         }
 205                 }
 206
 207                 if obj != nil {
 208                         // found a potential match
 209                         // spec: "A method call x.m() is valid if the method set of (the type of) x
 210                         //        contains m and the argument list can be assigned to the parameter
 211                         //        list of m. If x is addressable and &x's method set contains m, x.m()
 212                         //        is shorthand for (&x).m()".
 213                         if f, _ := obj.(*Func); f != nil {
 214                                 // determine if method has a pointer receiver
 215                                 hasPtrRecv := tpar == nil && f.hasPtrRecv()
 216                                 if hasPtrRecv && !indirect && !addressable {
 217                                         return nil, nil, true // pointer/addressable receiver required
 218                                 }
 219                         }
 220                         return
 221                 }
 222
 223                 current = consolidateMultiples(next)
 224         }
 225
 226         return nil, nil, false // not found
 227 }
 228
 229 // embeddedType represents an embedded type
 230 type embeddedType struct {
 231         typ       Type
 232         index     []int // embedded field indices, starting with index at depth 0
 233         indirect  bool  // if set, there was a pointer indirection on the path to this field
 234         multiples bool  // if set, typ appears multiple times at this depth
 235 }
 236
 237 // consolidateMultiples collects multiple list entries with the same type
 238 // into a single entry marked as containing multiples. The result is the
 239 // consolidated list.
 240 func consolidateMultiples(list []embeddedType) []embeddedType {
 241         if len(list) <= 1 {
 242                 return list // at most one entry - nothing to do
 243         }
 244
 245         n := 0                     // number of entries w/ unique type
 246         prev := make(map[Type]int) // index at which type was previously seen
 247         for _, e := range list {
 248                 if i, found := lookupType(prev, e.typ); found {
 249                         list[i].multiples = true
 250                         // ignore this entry
 251                 } else {
 252                         prev[e.typ] = n
 253                         list[n] = e
 254                         n++
 255                 }
 256         }
 257         return list[:n]
 258 }
 259
 260 func lookupType(m map[Type]int, typ Type) (int, bool) {
 261         // fast path: maybe the types are equal
 262         if i, found := m[typ]; found {
 263                 return i, true
 264         }
 265
 266         for t, i := range m {
 267                 if Identical(t, typ) {
 268                         return i, true
 269                 }
 270         }
 271
 272         return 0, false
 273 }
 274
 275 // MissingMethod returns (nil, false) if V implements T, otherwise it
 276 // returns a missing method required by T and whether it is missing or
 277 // just has the wrong type.
 278 //
 279 // For non-interface types V, or if static is set, V implements T if all
 280 // methods of T are present in V. Otherwise (V is an interface and static
 281 // is not set), MissingMethod only checks that methods of T which are also
 282 // present in V have matching types (e.g., for a type assertion x.(T) where
 283 // x is of interface type V).
 284 //
 285 func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) {
 286         m, typ := (*Checker)(nil).missingMethod(V, T, static)
 287         return m, typ != nil
 288 }
 289
 290 // missingMethod is like MissingMethod but accepts a *Checker as
 291 // receiver and an addressable flag.
 292 // The receiver may be nil if missingMethod is invoked through
 293 // an exported API call (such as MissingMethod), i.e., when all
 294 // methods have been type-checked.
 295 // If the type has the correctly named method, but with the wrong
 296 // signature, the existing method is returned as well.
 297 // To improve error messages, also report the wrong signature
 298 // when the method exists on *V instead of V.
 299 func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method, wrongType *Func) {
 300         // fast path for common case
 301         if T.Empty() {
 302                 return
 303         }
 304
 305         if ityp, _ := under(V).(*Interface); ityp != nil {
 306                 // TODO(gri) the methods are sorted - could do this more efficiently
 307                 for _, m := range T.typeSet().methods {
 308                         _, f := ityp.typeSet().LookupMethod(m.pkg, m.name)
 309
 310                         if f == nil {
 311                                 if !static {
 312                                         continue
 313                                 }
 314                                 return m, f
 315                         }
 316
 317                         // both methods must have the same number of type parameters
 318                         ftyp := f.typ.(*Signature)
 319                         mtyp := m.typ.(*Signature)
 320                         if ftyp.TypeParams().Len() != mtyp.TypeParams().Len() {
 321                                 return m, f
 322                         }
 323                         if ftyp.TypeParams().Len() > 0 {
 324                                 panic("method with type parameters")
 325                         }
 326
 327                         // If the methods have type parameters we don't care whether they
 328                         // are the same or not, as long as they match up. Use unification
 329                         // to see if they can be made to match.
 330                         // TODO(gri) is this always correct? what about type bounds?
 331                         // (Alternative is to rename/subst type parameters and compare.)
 332                         u := newUnifier(true)
 333                         u.x.init(ftyp.TypeParams().list())
 334                         if !u.unify(ftyp, mtyp) {
 335                                 return m, f
 336                         }
 337                 }
 338
 339                 return
 340         }
 341
 342         // A concrete type implements T if it implements all methods of T.
 343         for _, m := range T.typeSet().methods {
 344                 // TODO(gri) should this be calling lookupFieldOrMethod instead (and why not)?
 345                 obj, _, _ := lookupFieldOrMethod(V, false, m.pkg, m.name)
 346
 347                 // Check if *V implements this method of T.
 348                 if obj == nil {
 349                         ptr := NewPointer(V)
 350                         obj, _, _ = lookupFieldOrMethod(ptr, false, m.pkg, m.name)
 351
 352                         if obj != nil {
 353                                 // methods may not have a fully set up signature yet
 354                                 if check != nil {
 355                                         check.objDecl(obj, nil)
 356                                 }
 357                                 return m, obj.(*Func)
 358                         }
 359                 }
 360
 361                 // we must have a method (not a field of matching function type)
 362                 f, _ := obj.(*Func)
 363                 if f == nil {
 364                         return m, nil
 365                 }
 366
 367                 // methods may not have a fully set up signature yet
 368                 if check != nil {
 369                         check.objDecl(f, nil)
 370                 }
 371
 372                 // both methods must have the same number of type parameters
 373                 ftyp := f.typ.(*Signature)
 374                 mtyp := m.typ.(*Signature)
 375                 if ftyp.TypeParams().Len() != mtyp.TypeParams().Len() {
 376                         return m, f
 377                 }
 378                 if ftyp.TypeParams().Len() > 0 {
 379                         panic("method with type parameters")
 380                 }
 381
 382                 // If the methods have type parameters we don't care whether they
 383                 // are the same or not, as long as they match up. Use unification
 384                 // to see if they can be made to match.
 385                 // TODO(gri) is this always correct? what about type bounds?
 386                 // (Alternative is to rename/subst type parameters and compare.)
 387                 u := newUnifier(true)
 388                 u.x.init(ftyp.RecvTypeParams().list())
 389                 if !u.unify(ftyp, mtyp) {
 390                         return m, f
 391                 }
 392         }
 393
 394         return
 395 }
 396
 397 // missingMethodReason returns a string giving the detailed reason for a missing method m,
 398 // where m is missing from V, but required by T. It puts the reason in parentheses,
 399 // and may include more have/want info after that. If non-nil, wrongType is a relevant
 400 // method that matches in some way. It may have the correct name, but wrong type, or
 401 // it may have a pointer receiver.
 402 func (check *Checker) missingMethodReason(V, T Type, m, wrongType *Func) string {
 403         var r string
 404         var mname string
 405         if compilerErrorMessages {
 406                 mname = m.Name() + " method"
 407         } else {
 408                 mname = "method " + m.Name()
 409         }
 410         if wrongType != nil {
 411                 if Identical(m.typ, wrongType.typ) {
 412                         if m.Name() == wrongType.Name() {
 413                                 r = fmt.Sprintf("(%s has pointer receiver)", mname)
 414                         } else {
 415                                 r = fmt.Sprintf("(missing %s)\n\t\thave %s^^%s\n\t\twant %s^^%s",
 416                                         mname, wrongType.Name(), wrongType.typ, m.Name(), m.typ)
 417                         }
 418                 } else {
 419                         if compilerErrorMessages {
 420                                 r = fmt.Sprintf("(wrong type for %s)\n\t\thave %s^^%s\n\t\twant %s^^%s",
 421                                         mname, wrongType.Name(), wrongType.typ, m.Name(), m.typ)
 422                         } else {
 423                                 r = fmt.Sprintf("(wrong type for %s: have %s, want %s)",
 424                                         mname, wrongType.typ, m.typ)
 425                         }
 426                 }
 427                 // This is a hack to print the function type without the leading
 428                 // 'func' keyword in the have/want printouts. We could change to have
 429                 // an extra formatting option for types2.Type that doesn't print out
 430                 // 'func'.
 431                 r = strings.Replace(r, "^^func", "", -1)
 432         } else if IsInterface(T) {
 433                 if isInterfacePtr(V) {
 434                         r = fmt.Sprintf("(%s is pointer to interface, not interface)", V)
 435                 }
 436         } else if isInterfacePtr(T) {
 437                 r = fmt.Sprintf("(%s is pointer to interface, not interface)", T)
 438         }
 439         if r == "" {
 440                 r = fmt.Sprintf("(missing %s)", mname)
 441         }
 442         return r
 443 }
 444
 445 func isInterfacePtr(T Type) bool {
 446         p, _ := under(T).(*Pointer)
 447         return p != nil && IsInterface(p.base)
 448 }
 449
 450 // assertableTo reports whether a value of type V can be asserted to have type T.
 451 // It returns (nil, false) as affirmative answer. Otherwise it returns a missing
 452 // method required by V and whether it is missing or just has the wrong type.
 453 // The receiver may be nil if assertableTo is invoked through an exported API call
 454 // (such as AssertableTo), i.e., when all methods have been type-checked.
 455 // If the global constant forceStrict is set, assertions that are known to fail
 456 // are not permitted.
 457 func (check *Checker) assertableTo(V *Interface, T Type) (method, wrongType *Func) {
 458         // no static check is required if T is an interface
 459         // spec: "If T is an interface type, x.(T) asserts that the
 460         //        dynamic type of x implements the interface T."
 461         if IsInterface(T) && !forceStrict {
 462                 return
 463         }
 464         return check.missingMethod(T, V, false)
 465 }
 466
 467 // deref dereferences typ if it is a *Pointer and returns its base and true.
 468 // Otherwise it returns (typ, false).
 469 func deref(typ Type) (Type, bool) {
 470         if p, _ := typ.(*Pointer); p != nil {
 471                 return p.base, true
 472         }
 473         return typ, false
 474 }
 475
 476 // derefStructPtr dereferences typ if it is a (named or unnamed) pointer to a
 477 // (named or unnamed) struct and returns its base. Otherwise it returns typ.
 478 func derefStructPtr(typ Type) Type {
 479         if p, _ := under(typ).(*Pointer); p != nil {
 480                 if _, ok := under(p.base).(*Struct); ok {
 481                         return p.base
 482                 }
 483         }
 484         return typ
 485 }
 486
 487 // concat returns the result of concatenating list and i.
 488 // The result does not share its underlying array with list.
 489 func concat(list []int, i int) []int {
 490         var t []int
 491         t = append(t, list...)
 492         return append(t, i)
 493 }
 494
 495 // fieldIndex returns the index for the field with matching package and name, or a value < 0.
 496 func fieldIndex(fields []*Var, pkg *Package, name string) int {
 497         if name != "_" {
 498                 for i, f := range fields {
 499                         if f.sameId(pkg, name) {
 500                                 return i
 501                         }
 502                 }
 503         }
 504         return -1
 505 }
 506
 507 // lookupMethod returns the index of and method with matching package and name, or (-1, nil).
 508 func lookupMethod(methods []*Func, pkg *Package, name string) (int, *Func) {
 509         if name != "_" {
 510                 for i, m := range methods {
 511                         if m.sameId(pkg, name) {
 512                                 return i, m
 513                         }
 514                 }
 515         }
 516         return -1, nil
 517 }