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