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 9// LookupFieldOrMethod looks up a field or method with given package and name 10// in T and returns the corresponding *Var or *Func, an index sequence, and a 11// bool indicating if there were any pointer indirections on the path to the 12// field or method. If addressable is set, T is the type of an addressable 13// variable (only matters for method lookups). 14// 15// The last index entry is the field or method index in the (possibly embedded) 16// type where the entry was found, either: 17// 18// 1) the list of declared methods of a named type; or 19// 2) the list of all methods (method set) of an interface type; or 20// 3) the list of fields of a struct type. 21// 22// The earlier index entries are the indices of the embedded struct fields 23// traversed to get to the found entry, starting at depth 0. 24// 25// If no entry is found, a nil object is returned. In this case, the returned 26// index and indirect values have the following meaning: 27// 28// - If index != nil, the index sequence points to an ambiguous entry 29// (the same name appeared more than once at the same embedding level). 30// 31// - If indirect is set, a method with a pointer receiver type was found 32// but there was no pointer on the path from the actual receiver type to 33// the method's formal receiver base type, nor was the receiver addressable. 34// 35func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) { 36 return (*Checker)(nil).lookupFieldOrMethod(T, addressable, pkg, name) 37} 38 39// Internal use of Checker.lookupFieldOrMethod: If the obj result is a method 40// associated with a concrete (non-interface) type, the method's signature 41// may not be fully set up. Call Checker.objDecl(obj, nil) before accessing 42// the method's type. 43// TODO(gri) Now that we provide the *Checker, we can probably remove this 44// caveat by calling Checker.objDecl from lookupFieldOrMethod. Investigate. 45 46// lookupFieldOrMethod is like the external version but completes interfaces 47// as necessary. 48func (check *Checker) lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) { 49 // Methods cannot be associated to a named pointer type 50 // (spec: "The type denoted by T is called the receiver base type; 51 // it must not be a pointer or interface type and it must be declared 52 // in the same package as the method."). 53 // Thus, if we have a named pointer type, proceed with the underlying 54 // pointer type but discard the result if it is a method since we would 55 // not have found it for T (see also issue 8590). 56 if t, _ := T.(*Named); t != nil { 57 if p, _ := t.underlying.(*Pointer); p != nil { 58 obj, index, indirect = check.rawLookupFieldOrMethod(p, false, pkg, name) 59 if _, ok := obj.(*Func); ok { 60 return nil, nil, false 61 } 62 return 63 } 64 } 65 66 return check.rawLookupFieldOrMethod(T, addressable, pkg, name) 67} 68 69// TODO(gri) The named type consolidation and seen maps below must be 70// indexed by unique keys for a given type. Verify that named 71// types always have only one representation (even when imported 72// indirectly via different packages.) 73 74// rawLookupFieldOrMethod should only be called by lookupFieldOrMethod and missingMethod. 75func (check *Checker) rawLookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) { 76 // WARNING: The code in this function is extremely subtle - do not modify casually! 77 // This function and NewMethodSet should be kept in sync. 78 79 if name == "_" { 80 return // blank fields/methods are never found 81 } 82 83 typ, isPtr := deref(T) 84 85 // *typ where typ is an interface has no methods. 86 if isPtr && IsInterface(typ) { 87 return 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 for _, e := range current { 108 typ := e.typ 109 110 // If we have a named type, we may have associated methods. 111 // Look for those first. 112 if named, _ := typ.(*Named); named != nil { 113 if seen[named] { 114 // We have seen this type before, at a more shallow depth 115 // (note that multiples of this type at the current depth 116 // were consolidated before). The type at that depth shadows 117 // this same type at the current depth, so we can ignore 118 // this one. 119 continue 120 } 121 if seen == nil { 122 seen = make(map[*Named]bool) 123 } 124 seen[named] = true 125 126 // look for a matching attached method 127 if i, m := lookupMethod(named.methods, pkg, name); m != nil { 128 // potential match 129 // caution: method may not have a proper signature yet 130 index = concat(e.index, i) 131 if obj != nil || e.multiples { 132 return nil, index, false // collision 133 } 134 obj = m 135 indirect = e.indirect 136 continue // we can't have a matching field or interface method 137 } 138 139 // continue with underlying type 140 typ = named.underlying 141 } 142 143 switch t := typ.(type) { 144 case *Struct: 145 // look for a matching field and collect embedded types 146 for i, f := range t.fields { 147 if f.sameId(pkg, name) { 148 assert(f.typ != nil) 149 index = concat(e.index, i) 150 if obj != nil || e.multiples { 151 return nil, index, false // collision 152 } 153 obj = f 154 indirect = e.indirect 155 continue // we can't have a matching interface method 156 } 157 // Collect embedded struct fields for searching the next 158 // lower depth, but only if we have not seen a match yet 159 // (if we have a match it is either the desired field or 160 // we have a name collision on the same depth; in either 161 // case we don't need to look further). 162 // Embedded fields are always of the form T or *T where 163 // T is a type name. If e.typ appeared multiple times at 164 // this depth, f.typ appears multiple times at the next 165 // depth. 166 if obj == nil && f.embedded { 167 typ, isPtr := deref(f.typ) 168 // TODO(gri) optimization: ignore types that can't 169 // have fields or methods (only Named, Struct, and 170 // Interface types need to be considered). 171 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples}) 172 } 173 } 174 175 case *Interface: 176 // look for a matching method 177 // TODO(gri) t.allMethods is sorted - use binary search 178 check.completeInterface(t) 179 if i, m := lookupMethod(t.allMethods, pkg, name); m != nil { 180 assert(m.typ != nil) 181 index = concat(e.index, i) 182 if obj != nil || e.multiples { 183 return nil, index, false // collision 184 } 185 obj = m 186 indirect = e.indirect 187 } 188 } 189 } 190 191 if obj != nil { 192 // found a potential match 193 // spec: "A method call x.m() is valid if the method set of (the type of) x 194 // contains m and the argument list can be assigned to the parameter 195 // list of m. If x is addressable and &x's method set contains m, x.m() 196 // is shorthand for (&x).m()". 197 if f, _ := obj.(*Func); f != nil && ptrRecv(f) && !indirect && !addressable { 198 return nil, nil, true // pointer/addressable receiver required 199 } 200 return 201 } 202 203 current = check.consolidateMultiples(next) 204 } 205 206 return nil, nil, false // not found 207} 208 209// embeddedType represents an embedded type 210type embeddedType struct { 211 typ Type 212 index []int // embedded field indices, starting with index at depth 0 213 indirect bool // if set, there was a pointer indirection on the path to this field 214 multiples bool // if set, typ appears multiple times at this depth 215} 216 217// consolidateMultiples collects multiple list entries with the same type 218// into a single entry marked as containing multiples. The result is the 219// consolidated list. 220func (check *Checker) consolidateMultiples(list []embeddedType) []embeddedType { 221 if len(list) <= 1 { 222 return list // at most one entry - nothing to do 223 } 224 225 n := 0 // number of entries w/ unique type 226 prev := make(map[Type]int) // index at which type was previously seen 227 for _, e := range list { 228 if i, found := check.lookupType(prev, e.typ); found { 229 list[i].multiples = true 230 // ignore this entry 231 } else { 232 prev[e.typ] = n 233 list[n] = e 234 n++ 235 } 236 } 237 return list[:n] 238} 239 240func (check *Checker) lookupType(m map[Type]int, typ Type) (int, bool) { 241 // fast path: maybe the types are equal 242 if i, found := m[typ]; found { 243 return i, true 244 } 245 246 for t, i := range m { 247 if check.identical(t, typ) { 248 return i, true 249 } 250 } 251 252 return 0, false 253} 254 255// MissingMethod returns (nil, false) if V implements T, otherwise it 256// returns a missing method required by T and whether it is missing or 257// just has the wrong type. 258// 259// For non-interface types V, or if static is set, V implements T if all 260// methods of T are present in V. Otherwise (V is an interface and static 261// is not set), MissingMethod only checks that methods of T which are also 262// present in V have matching types (e.g., for a type assertion x.(T) where 263// x is of interface type V). 264// 265func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) { 266 m, typ := (*Checker)(nil).missingMethod(V, T, static) 267 return m, typ != nil 268} 269 270// missingMethod is like MissingMethod but accepts a receiver. 271// The receiver may be nil if missingMethod is invoked through 272// an exported API call (such as MissingMethod), i.e., when all 273// methods have been type-checked. 274// If the type has the correctly named method, but with the wrong 275// signature, the existing method is returned as well. 276// To improve error messages, also report the wrong signature 277// when the method exists on *V instead of V. 278func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method, wrongType *Func) { 279 check.completeInterface(T) 280 281 // fast path for common case 282 if T.Empty() { 283 return 284 } 285 286 if ityp, _ := V.Underlying().(*Interface); ityp != nil { 287 check.completeInterface(ityp) 288 // TODO(gri) allMethods is sorted - can do this more efficiently 289 for _, m := range T.allMethods { 290 _, obj := lookupMethod(ityp.allMethods, m.pkg, m.name) 291 switch { 292 case obj == nil: 293 if static { 294 return m, nil 295 } 296 case !check.identical(obj.Type(), m.typ): 297 return m, obj 298 } 299 } 300 return 301 } 302 303 // A concrete type implements T if it implements all methods of T. 304 for _, m := range T.allMethods { 305 obj, _, _ := check.rawLookupFieldOrMethod(V, false, m.pkg, m.name) 306 307 // Check if *V implements this method of T. 308 if obj == nil { 309 ptr := NewPointer(V) 310 obj, _, _ = check.rawLookupFieldOrMethod(ptr, false, m.pkg, m.name) 311 if obj != nil { 312 return m, obj.(*Func) 313 } 314 } 315 316 // we must have a method (not a field of matching function type) 317 f, _ := obj.(*Func) 318 if f == nil { 319 return m, nil 320 } 321 322 // methods may not have a fully set up signature yet 323 if check != nil { 324 check.objDecl(f, nil) 325 } 326 327 if !check.identical(f.typ, m.typ) { 328 return m, f 329 } 330 } 331 332 return 333} 334 335// assertableTo reports whether a value of type V can be asserted to have type T. 336// It returns (nil, false) as affirmative answer. Otherwise it returns a missing 337// method required by V and whether it is missing or just has the wrong type. 338// The receiver may be nil if assertableTo is invoked through an exported API call 339// (such as AssertableTo), i.e., when all methods have been type-checked. 340func (check *Checker) assertableTo(V *Interface, T Type) (method, wrongType *Func) { 341 // no static check is required if T is an interface 342 // spec: "If T is an interface type, x.(T) asserts that the 343 // dynamic type of x implements the interface T." 344 if _, ok := T.Underlying().(*Interface); ok && !strict { 345 return 346 } 347 return check.missingMethod(T, V, false) 348} 349 350// deref dereferences typ if it is a *Pointer and returns its base and true. 351// Otherwise it returns (typ, false). 352func deref(typ Type) (Type, bool) { 353 if p, _ := typ.(*Pointer); p != nil { 354 return p.base, true 355 } 356 return typ, false 357} 358 359// derefStructPtr dereferences typ if it is a (named or unnamed) pointer to a 360// (named or unnamed) struct and returns its base. Otherwise it returns typ. 361func derefStructPtr(typ Type) Type { 362 if p, _ := typ.Underlying().(*Pointer); p != nil { 363 if _, ok := p.base.Underlying().(*Struct); ok { 364 return p.base 365 } 366 } 367 return typ 368} 369 370// concat returns the result of concatenating list and i. 371// The result does not share its underlying array with list. 372func concat(list []int, i int) []int { 373 var t []int 374 t = append(t, list...) 375 return append(t, i) 376} 377 378// fieldIndex returns the index for the field with matching package and name, or a value < 0. 379func fieldIndex(fields []*Var, pkg *Package, name string) int { 380 if name != "_" { 381 for i, f := range fields { 382 if f.sameId(pkg, name) { 383 return i 384 } 385 } 386 } 387 return -1 388} 389 390// lookupMethod returns the index of and method with matching package and name, or (-1, nil). 391func lookupMethod(methods []*Func, pkg *Package, name string) (int, *Func) { 392 if name != "_" { 393 for i, m := range methods { 394 if m.sameId(pkg, name) { 395 return i, m 396 } 397 } 398 } 399 return -1, nil 400} 401