src/cmd/compile/internal/types2/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 // Internal use of LookupFieldOrMethod: If the obj result is a method
  10 // associated with a concrete (non-interface) type, the method's signature
  11 // may not be fully set up. Call Checker.objDecl(obj, nil) before accessing
  12 // the method's type.
  13
  14 // LookupFieldOrMethod looks up a field or method with given package and name
  15 // in T and returns the corresponding *Var or *Func, an index sequence, and a
  16 // bool indicating if there were any pointer indirections on the path to the
  17 // field or method. If addressable is set, T is the type of an addressable
  18 // variable (only matters for method lookups).
  19 //
  20 // The last index entry is the field or method index in the (possibly embedded)
  21 // type where the entry was found, either:
  22 //
  23 //      1) the list of declared methods of a named type; or
  24 //      2) the list of all methods (method set) of an interface type; or
  25 //      3) the list of fields of a struct type.
  26 //
  27 // The earlier index entries are the indices of the embedded struct fields
  28 // traversed to get to the found entry, starting at depth 0.
  29 //
  30 // If no entry is found, a nil object is returned. In this case, the returned
  31 // index and indirect values have the following meaning:
  32 //
  33 //      - If index != nil, the index sequence points to an ambiguous entry
  34 //      (the same name appeared more than once at the same embedding level).
  35 //
  36 //      - If indirect is set, a method with a pointer receiver type was found
  37 //      but there was no pointer on the path from the actual receiver type to
  38 //      the method's formal receiver base type, nor was the receiver addressable.
  39 //
  40 func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) {
  41         // Methods cannot be associated to a named pointer type
  42         // (spec: "The type denoted by T is called the receiver base type;
  43         // it must not be a pointer or interface type and it must be declared
  44         // in the same package as the method.").
  45         // Thus, if we have a named pointer type, proceed with the underlying
  46         // pointer type but discard the result if it is a method since we would
  47         // not have found it for T (see also issue 8590).
  48         if t := asNamed(T); t != nil {
  49                 if p, _ := t.Underlying().(*Pointer); p != nil {
  50                         obj, index, indirect = lookupFieldOrMethod(p, false, pkg, name)
  51                         if _, ok := obj.(*Func); ok {
  52                                 return nil, nil, false
  53                         }
  54                         return
  55                 }
  56         }
  57
  58         return lookupFieldOrMethod(T, addressable, pkg, name)
  59 }
  60
  61 // TODO(gri) The named type consolidation and seen maps below must be
  62 //           indexed by unique keys for a given type. Verify that named
  63 //           types always have only one representation (even when imported
  64 //           indirectly via different packages.)
  65
  66 // lookupFieldOrMethod should only be called by LookupFieldOrMethod and missingMethod.
  67 func lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) {
  68         // WARNING: The code in this function is extremely subtle - do not modify casually!
  69
  70         if name == "_" {
  71                 return // blank fields/methods are never found
  72         }
  73
  74         typ, isPtr := deref(T)
  75
  76         // *typ where typ is an interface has no methods.
  77         // Be cautious: typ may be nil (issue 39634, crash #3).
  78         if typ == nil || isPtr && IsInterface(typ) {
  79                 return
  80         }
  81
  82         // Start with typ as single entry at shallowest depth.
  83         current := []embeddedType{{typ, nil, isPtr, false}}
  84
  85         // Named types that we have seen already, allocated lazily.
  86         // Used to avoid endless searches in case of recursive types.
  87         // Since only Named types can be used for recursive types, we
  88         // only need to track those.
  89         // (If we ever allow type aliases to construct recursive types,
  90         // we must use type identity rather than pointer equality for
  91         // the map key comparison, as we do in consolidateMultiples.)
  92         var seen map[*Named]bool
  93
  94         // search current depth
  95         for len(current) > 0 {
  96                 var next []embeddedType // embedded types found at current depth
  97
  98                 // look for (pkg, name) in all types at current depth
  99                 var tpar *TypeParam // set if obj receiver is a type parameter
 100                 for _, e := range current {
 101                         typ := e.typ
 102
 103                         // If we have a named type, we may have associated methods.
 104                         // Look for those first.
 105                         if named := asNamed(typ); named != nil {
 106                                 if seen[named] {
 107                                         // We have seen this type before, at a more shallow depth
 108                                         // (note that multiples of this type at the current depth
 109                                         // were consolidated before). The type at that depth shadows
 110                                         // this same type at the current depth, so we can ignore
 111                                         // this one.
 112                                         continue
 113                                 }
 114                                 if seen == nil {
 115                                         seen = make(map[*Named]bool)
 116                                 }
 117                                 seen[named] = true
 118
 119                                 // look for a matching attached method
 120                                 named.expand()
 121                                 if i, m := lookupMethod(named.methods, pkg, name); m != nil {
 122                                         // potential match
 123                                         // caution: method may not have a proper signature yet
 124                                         index = concat(e.index, i)
 125                                         if obj != nil || e.multiples {
 126                                                 return nil, index, false // collision
 127                                         }
 128                                         obj = m
 129                                         indirect = e.indirect
 130                                         continue // we can't have a matching field or interface method
 131                                 }
 132
 133                                 // continue with underlying type, but only if it's not a type parameter
 134                                 // TODO(gri) is this what we want to do for type parameters? (spec question)
 135                                 typ = named.under()
 136                                 if asTypeParam(typ) != nil {
 137                                         continue
 138                                 }
 139                         }
 140
 141                         tpar = nil
 142                         switch t := typ.(type) {
 143                         case *Struct:
 144                                 // look for a matching field and collect embedded types
 145                                 for i, f := range t.fields {
 146                                         if f.sameId(pkg, name) {
 147                                                 assert(f.typ != nil)
 148                                                 index = concat(e.index, i)
 149                                                 if obj != nil || e.multiples {
 150                                                         return nil, index, false // collision
 151                                                 }
 152                                                 obj = f
 153                                                 indirect = e.indirect
 154                                                 continue // we can't have a matching interface method
 155                                         }
 156                                         // Collect embedded struct fields for searching the next
 157                                         // lower depth, but only if we have not seen a match yet
 158                                         // (if we have a match it is either the desired field or
 159                                         // we have a name collision on the same depth; in either
 160                                         // case we don't need to look further).
 161                                         // Embedded fields are always of the form T or *T where
 162                                         // T is a type name. If e.typ appeared multiple times at
 163                                         // this depth, f.typ appears multiple times at the next
 164                                         // depth.
 165                                         if obj == nil && f.embedded {
 166                                                 typ, isPtr := deref(f.typ)
 167                                                 // TODO(gri) optimization: ignore types that can't
 168                                                 // have fields or methods (only Named, Struct, and
 169                                                 // Interface types need to be considered).
 170                                                 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples})
 171                                         }
 172                                 }
 173
 174                         case *Interface:
 175                                 // look for a matching method
 176                                 if i, m := t.typeSet().LookupMethod(pkg, name); m != nil {
 177                                         assert(m.typ != nil)
 178                                         index = concat(e.index, i)
 179                                         if obj != nil || e.multiples {
 180                                                 return nil, index, false // collision
 181                                         }
 182                                         obj = m
 183                                         indirect = e.indirect
 184                                 }
 185
 186                         case *TypeParam:
 187                                 if i, m := t.Bound().typeSet().LookupMethod(pkg, name); m != nil {
 188                                         assert(m.typ != nil)
 189                                         index = concat(e.index, i)
 190                                         if obj != nil || e.multiples {
 191                                                 return nil, index, false // collision
 192                                         }
 193                                         tpar = t
 194                                         obj = m
 195                                         indirect = e.indirect
 196                                 }
 197                                 if obj == nil {
 198                                         // At this point we're not (yet) looking into methods
 199                                         // that any underlying type of the types in the type list
 200                                         // might have.
 201                                         // TODO(gri) Do we want to specify the language that way?
 202                                 }
 203                         }
 204                 }
 205
 206                 if obj != nil {
 207                         // found a potential match
 208                         // spec: "A method call x.m() is valid if the method set of (the type of) x
 209                         //        contains m and the argument list can be assigned to the parameter
 210                         //        list of m. If x is addressable and &x's method set contains m, x.m()
 211                         //        is shorthand for (&x).m()".
 212                         if f, _ := obj.(*Func); f != nil {
 213                                 // determine if method has a pointer receiver
 214                                 hasPtrRecv := tpar == nil && ptrRecv(f)
 215                                 if hasPtrRecv && !indirect && !addressable {
 216                                         return nil, nil, true // pointer/addressable receiver required
 217                                 }
 218                         }
 219                         return
 220                 }
 221
 222                 current = consolidateMultiples(next)
 223         }
 224
 225         return nil, nil, false // not found
 226 }
 227
 228 // embeddedType represents an embedded type
 229 type embeddedType struct {
 230         typ       Type
 231         index     []int // embedded field indices, starting with index at depth 0
 232         indirect  bool  // if set, there was a pointer indirection on the path to this field
 233         multiples bool  // if set, typ appears multiple times at this depth
 234 }
 235
 236 // consolidateMultiples collects multiple list entries with the same type
 237 // into a single entry marked as containing multiples. The result is the
 238 // consolidated list.
 239 func consolidateMultiples(list []embeddedType) []embeddedType {
 240         if len(list) <= 1 {
 241                 return list // at most one entry - nothing to do
 242         }
 243
 244         n := 0                     // number of entries w/ unique type
 245         prev := make(map[Type]int) // index at which type was previously seen
 246         for _, e := range list {
 247                 if i, found := lookupType(prev, e.typ); found {
 248                         list[i].multiples = true
 249                         // ignore this entry
 250                 } else {
 251                         prev[e.typ] = n
 252                         list[n] = e
 253                         n++
 254                 }
 255         }
 256         return list[:n]
 257 }
 258
 259 func lookupType(m map[Type]int, typ Type) (int, bool) {
 260         // fast path: maybe the types are equal
 261         if i, found := m[typ]; found {
 262                 return i, true
 263         }
 264
 265         for t, i := range m {
 266                 if Identical(t, typ) {
 267                         return i, true
 268                 }
 269         }
 270
 271         return 0, false
 272 }
 273
 274 // MissingMethod returns (nil, false) if V implements T, otherwise it
 275 // returns a missing method required by T and whether it is missing or
 276 // just has the wrong type.
 277 //
 278 // For non-interface types V, or if static is set, V implements T if all
 279 // methods of T are present in V. Otherwise (V is an interface and static
 280 // is not set), MissingMethod only checks that methods of T which are also
 281 // present in V have matching types (e.g., for a type assertion x.(T) where
 282 // x is of interface type V).
 283 //
 284 func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) {
 285         m, typ := (*Checker)(nil).missingMethod(V, T, static)
 286         return m, typ != nil
 287 }
 288
 289 // missingMethod is like MissingMethod but accepts a *Checker as
 290 // receiver and an addressable flag.
 291 // The receiver may be nil if missingMethod is invoked through
 292 // an exported API call (such as MissingMethod), i.e., when all
 293 // methods have been type-checked.
 294 // If the type has the correctly named method, but with the wrong
 295 // signature, the existing method is returned as well.
 296 // To improve error messages, also report the wrong signature
 297 // when the method exists on *V instead of V.
 298 func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method, wrongType *Func) {
 299         // fast path for common case
 300         if T.Empty() {
 301                 return
 302         }
 303
 304         if ityp := asInterface(V); ityp != nil {
 305                 // TODO(gri) the methods are sorted - could do this more efficiently
 306                 for _, m := range T.typeSet().methods {
 307                         _, f := ityp.typeSet().LookupMethod(m.pkg, m.name)
 308
 309                         if f == nil {
 310                                 // if m is the magic method == we're ok (interfaces are comparable)
 311                                 if m.name == "==" || !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 len(ftyp.tparams) != len(mtyp.tparams) {
 321                                 return m, f
 322                         }
 323                         if !acceptMethodTypeParams && len(ftyp.tparams) > 0 {
 324                                 panic("internal error: 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.tparams)
 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         Vd, _ := deref(V)
 344         Vn := asNamed(Vd)
 345         for _, m := range T.typeSet().methods {
 346                 // TODO(gri) should this be calling lookupFieldOrMethod instead (and why not)?
 347                 obj, _, _ := lookupFieldOrMethod(V, false, m.pkg, m.name)
 348
 349                 // Check if *V implements this method of T.
 350                 if obj == nil {
 351                         ptr := NewPointer(V)
 352                         obj, _, _ = lookupFieldOrMethod(ptr, false, m.pkg, m.name)
 353                         if obj != nil {
 354                                 return m, obj.(*Func)
 355                         }
 356                 }
 357
 358                 // we must have a method (not a field of matching function type)
 359                 f, _ := obj.(*Func)
 360                 if f == nil {
 361                         // if m is the magic method == and V is comparable, we're ok
 362                         if m.name == "==" && Comparable(V) {
 363                                 continue
 364                         }
 365                         return m, nil
 366                 }
 367
 368                 // methods may not have a fully set up signature yet
 369                 if check != nil {
 370                         check.objDecl(f, nil)
 371                 }
 372
 373                 // both methods must have the same number of type parameters
 374                 ftyp := f.typ.(*Signature)
 375                 mtyp := m.typ.(*Signature)
 376                 if len(ftyp.tparams) != len(mtyp.tparams) {
 377                         return m, f
 378                 }
 379                 if !acceptMethodTypeParams && len(ftyp.tparams) > 0 {
 380                         panic("internal error: method with type parameters")
 381                 }
 382
 383                 // If V is a (instantiated) generic type, its methods are still
 384                 // parameterized using the original (declaration) receiver type
 385                 // parameters (subst simply copies the existing method list, it
 386                 // does not instantiate the methods).
 387                 // In order to compare the signatures, substitute the receiver
 388                 // type parameters of ftyp with V's instantiation type arguments.
 389                 // This lazily instantiates the signature of method f.
 390                 if Vn != nil && len(Vn.TParams()) > 0 {
 391                         // Be careful: The number of type arguments may not match
 392                         // the number of receiver parameters. If so, an error was
 393                         // reported earlier but the length discrepancy is still
 394                         // here. Exit early in this case to prevent an assertion
 395                         // failure in makeSubstMap.
 396                         // TODO(gri) Can we avoid this check by fixing the lengths?
 397                         if len(ftyp.rparams) != len(Vn.targs) {
 398                                 return
 399                         }
 400                         ftyp = check.subst(nopos, ftyp, makeSubstMap(ftyp.rparams, Vn.targs)).(*Signature)
 401                 }
 402
 403                 // If the methods have type parameters we don't care whether they
 404                 // are the same or not, as long as they match up. Use unification
 405                 // to see if they can be made to match.
 406                 // TODO(gri) is this always correct? what about type bounds?
 407                 // (Alternative is to rename/subst type parameters and compare.)
 408                 u := newUnifier(true)
 409                 if len(ftyp.tparams) > 0 {
 410                         // We reach here only if we accept method type parameters.
 411                         // In this case, unification must consider any receiver
 412                         // and method type parameters as "free" type parameters.
 413                         assert(acceptMethodTypeParams)
 414                         // We don't have a test case for this at the moment since
 415                         // we can't parse method type parameters. Keeping the
 416                         // unimplemented call so that we test this code if we
 417                         // enable method type parameters.
 418                         unimplemented()
 419                         u.x.init(append(ftyp.rparams, ftyp.tparams...))
 420                 } else {
 421                         u.x.init(ftyp.rparams)
 422                 }
 423                 if !u.unify(ftyp, mtyp) {
 424                         return m, f
 425                 }
 426         }
 427
 428         return
 429 }
 430
 431 // assertableTo reports whether a value of type V can be asserted to have type T.
 432 // It returns (nil, false) as affirmative answer. Otherwise it returns a missing
 433 // method required by V and whether it is missing or just has the wrong type.
 434 // The receiver may be nil if assertableTo is invoked through an exported API call
 435 // (such as AssertableTo), i.e., when all methods have been type-checked.
 436 // If the global constant forceStrict is set, assertions that are known to fail
 437 // are not permitted.
 438 func (check *Checker) assertableTo(V *Interface, T Type) (method, wrongType *Func) {
 439         // no static check is required if T is an interface
 440         // spec: "If T is an interface type, x.(T) asserts that the
 441         //        dynamic type of x implements the interface T."
 442         if asInterface(T) != nil && !forceStrict {
 443                 return
 444         }
 445         return check.missingMethod(T, V, false)
 446 }
 447
 448 // deref dereferences typ if it is a *Pointer and returns its base and true.
 449 // Otherwise it returns (typ, false).
 450 func deref(typ Type) (Type, bool) {
 451         if p, _ := typ.(*Pointer); p != nil {
 452                 return p.base, true
 453         }
 454         return typ, false
 455 }
 456
 457 // derefStructPtr dereferences typ if it is a (named or unnamed) pointer to a
 458 // (named or unnamed) struct and returns its base. Otherwise it returns typ.
 459 func derefStructPtr(typ Type) Type {
 460         if p := asPointer(typ); p != nil {
 461                 if asStruct(p.base) != nil {
 462                         return p.base
 463                 }
 464         }
 465         return typ
 466 }
 467
 468 // concat returns the result of concatenating list and i.
 469 // The result does not share its underlying array with list.
 470 func concat(list []int, i int) []int {
 471         var t []int
 472         t = append(t, list...)
 473         return append(t, i)
 474 }
 475
 476 // fieldIndex returns the index for the field with matching package and name, or a value < 0.
 477 func fieldIndex(fields []*Var, pkg *Package, name string) int {
 478         if name != "_" {
 479                 for i, f := range fields {
 480                         if f.sameId(pkg, name) {
 481                                 return i
 482                         }
 483                 }
 484         }
 485         return -1
 486 }
 487
 488 // lookupMethod returns the index of and method with matching package and name, or (-1, nil).
 489 func lookupMethod(methods []*Func, pkg *Package, name string) (int, *Func) {
 490         if name != "_" {
 491                 for i, m := range methods {
 492                         if m.sameId(pkg, name) {
 493                                 return i, m
 494                         }
 495                 }
 496         }
 497         return -1, nil
 498 }
 499
 500 // ptrRecv reports whether the receiver is of the form *T.
 501 func ptrRecv(f *Func) bool {
 502         // If a method's receiver type is set, use that as the source of truth for the receiver.
 503         // Caution: Checker.funcDecl (decl.go) marks a function by setting its type to an empty
 504         // signature. We may reach here before the signature is fully set up: we must explicitly
 505         // check if the receiver is set (we cannot just look for non-nil f.typ).
 506         if sig, _ := f.typ.(*Signature); sig != nil && sig.recv != nil {
 507                 _, isPtr := deref(sig.recv.typ)
 508                 return isPtr
 509         }
 510
 511         // If a method's type is not set it may be a method/function that is:
 512         // 1) client-supplied (via NewFunc with no signature), or
 513         // 2) internally created but not yet type-checked.
 514         // For case 1) we can't do anything; the client must know what they are doing.
 515         // For case 2) we can use the information gathered by the resolver.
 516         return f.hasPtrRecv
 517 }