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 // 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, _ := T.(*Named); 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 func lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) { 67 // WARNING: The code in this function is extremely subtle - do not modify casually! 68 // This function and NewMethodSet should be kept in sync. 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 if isPtr && IsInterface(typ) { 78 return 79 } 80 81 // Start with typ as single entry at shallowest depth. 82 current := []embeddedType{{typ, nil, isPtr, false}} 83 84 // Named types that we have seen already, allocated lazily. 85 // Used to avoid endless searches in case of recursive types. 86 // Since only Named types can be used for recursive types, we 87 // only need to track those. 88 // (If we ever allow type aliases to construct recursive types, 89 // we must use type identity rather than pointer equality for 90 // the map key comparison, as we do in consolidateMultiples.) 91 var seen map[*Named]bool 92 93 // search current depth 94 for len(current) > 0 { 95 var next []embeddedType // embedded types found at current depth 96 97 // look for (pkg, name) in all types at current depth 98 for _, e := range current { 99 typ := e.typ 100 101 // If we have a named type, we may have associated methods. 102 // Look for those first. 103 if named, _ := typ.(*Named); named != nil { 104 if seen[named] { 105 // We have seen this type before, at a more shallow depth 106 // (note that multiples of this type at the current depth 107 // were consolidated before). The type at that depth shadows 108 // this same type at the current depth, so we can ignore 109 // this one. 110 continue 111 } 112 if seen == nil { 113 seen = make(map[*Named]bool) 114 } 115 seen[named] = true 116 117 // look for a matching attached method 118 if i, m := lookupMethod(named.methods, pkg, name); m != nil { 119 // potential match 120 // caution: method may not have a proper signature yet 121 index = concat(e.index, i) 122 if obj != nil || e.multiples { 123 return nil, index, false // collision 124 } 125 obj = m 126 indirect = e.indirect 127 continue // we can't have a matching field or interface method 128 } 129 130 // continue with underlying type 131 typ = named.underlying 132 } 133 134 switch t := typ.(type) { 135 case *Struct: 136 // look for a matching field and collect embedded types 137 for i, f := range t.fields { 138 if f.sameId(pkg, name) { 139 assert(f.typ != nil) 140 index = concat(e.index, i) 141 if obj != nil || e.multiples { 142 return nil, index, false // collision 143 } 144 obj = f 145 indirect = e.indirect 146 continue // we can't have a matching interface method 147 } 148 // Collect embedded struct fields for searching the next 149 // lower depth, but only if we have not seen a match yet 150 // (if we have a match it is either the desired field or 151 // we have a name collision on the same depth; in either 152 // case we don't need to look further). 153 // Embedded fields are always of the form T or *T where 154 // T is a type name. If e.typ appeared multiple times at 155 // this depth, f.typ appears multiple times at the next 156 // depth. 157 if obj == nil && f.embedded { 158 typ, isPtr := deref(f.typ) 159 // TODO(gri) optimization: ignore types that can't 160 // have fields or methods (only Named, Struct, and 161 // Interface types need to be considered). 162 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples}) 163 } 164 } 165 166 case *Interface: 167 // look for a matching method 168 // TODO(gri) t.allMethods is sorted - use binary search 169 if i, m := lookupMethod(t.allMethods, pkg, name); m != nil { 170 assert(m.typ != nil) 171 index = concat(e.index, i) 172 if obj != nil || e.multiples { 173 return nil, index, false // collision 174 } 175 obj = m 176 indirect = e.indirect 177 } 178 } 179 } 180 181 if obj != nil { 182 // found a potential match 183 // spec: "A method call x.m() is valid if the method set of (the type of) x 184 // contains m and the argument list can be assigned to the parameter 185 // list of m. If x is addressable and &x's method set contains m, x.m() 186 // is shorthand for (&x).m()". 187 if f, _ := obj.(*Func); f != nil && ptrRecv(f) && !indirect && !addressable { 188 return nil, nil, true // pointer/addressable receiver required 189 } 190 return 191 } 192 193 current = consolidateMultiples(next) 194 } 195 196 return nil, nil, false // not found 197 } 198 199 // embeddedType represents an embedded type 200 type embeddedType struct { 201 typ Type 202 index []int // embedded field indices, starting with index at depth 0 203 indirect bool // if set, there was a pointer indirection on the path to this field 204 multiples bool // if set, typ appears multiple times at this depth 205 } 206 207 // consolidateMultiples collects multiple list entries with the same type 208 // into a single entry marked as containing multiples. The result is the 209 // consolidated list. 210 func consolidateMultiples(list []embeddedType) []embeddedType { 211 if len(list) <= 1 { 212 return list // at most one entry - nothing to do 213 } 214 215 n := 0 // number of entries w/ unique type 216 prev := make(map[Type]int) // index at which type was previously seen 217 for _, e := range list { 218 if i, found := lookupType(prev, e.typ); found { 219 list[i].multiples = true 220 // ignore this entry 221 } else { 222 prev[e.typ] = n 223 list[n] = e 224 n++ 225 } 226 } 227 return list[:n] 228 } 229 230 func lookupType(m map[Type]int, typ Type) (int, bool) { 231 // fast path: maybe the types are equal 232 if i, found := m[typ]; found { 233 return i, true 234 } 235 236 for t, i := range m { 237 if Identical(t, typ) { 238 return i, true 239 } 240 } 241 242 return 0, false 243 } 244 245 // MissingMethod returns (nil, false) if V implements T, otherwise it 246 // returns a missing method required by T and whether it is missing or 247 // just has the wrong type. 248 // 249 // For non-interface types V, or if static is set, V implements T if all 250 // methods of T are present in V. Otherwise (V is an interface and static 251 // is not set), MissingMethod only checks that methods of T which are also 252 // present in V have matching types (e.g., for a type assertion x.(T) where 253 // x is of interface type V). 254 // 255 func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) { 256 return (*Checker)(nil).missingMethod(V, T, static) 257 } 258 259 // missingMethod is like MissingMethod but accepts a receiver. 260 // The receiver may be nil if missingMethod is invoked through 261 // an exported API call (such as MissingMethod), i.e., when all 262 // methods have been type-checked. 263 func (check *Checker) missingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) { 264 // fast path for common case 265 if T.Empty() { 266 return 267 } 268 269 // TODO(gri) Consider using method sets here. Might be more efficient. 270 271 if ityp, _ := V.Underlying().(*Interface); ityp != nil { 272 // TODO(gri) allMethods is sorted - can do this more efficiently 273 for _, m := range T.allMethods { 274 _, obj := lookupMethod(ityp.allMethods, m.pkg, m.name) 275 switch { 276 case obj == nil: 277 if static { 278 return m, false 279 } 280 case !Identical(obj.Type(), m.typ): 281 return m, true 282 } 283 } 284 return 285 } 286 287 // A concrete type implements T if it implements all methods of T. 288 for _, m := range T.allMethods { 289 obj, _, _ := lookupFieldOrMethod(V, false, m.pkg, m.name) 290 291 // we must have a method (not a field of matching function type) 292 f, _ := obj.(*Func) 293 if f == nil { 294 return m, false 295 } 296 297 // methods may not have a fully set up signature yet 298 if check != nil { 299 check.objDecl(f, nil) 300 } 301 302 if !Identical(f.typ, m.typ) { 303 return m, true 304 } 305 } 306 307 return 308 } 309 310 // assertableTo reports whether a value of type V can be asserted to have type T. 311 // It returns (nil, false) as affirmative answer. Otherwise it returns a missing 312 // method required by V and whether it is missing or just has the wrong type. 313 // The receiver may be nil if assertableTo is invoked through an exported API call 314 // (such as AssertableTo), i.e., when all methods have been type-checked. 315 func (check *Checker) assertableTo(V *Interface, T Type) (method *Func, wrongType bool) { 316 // no static check is required if T is an interface 317 // spec: "If T is an interface type, x.(T) asserts that the 318 // dynamic type of x implements the interface T." 319 if _, ok := T.Underlying().(*Interface); ok && !strict { 320 return 321 } 322 return check.missingMethod(T, V, false) 323 } 324 325 // deref dereferences typ if it is a *Pointer and returns its base and true. 326 // Otherwise it returns (typ, false). 327 func deref(typ Type) (Type, bool) { 328 if p, _ := typ.(*Pointer); p != nil { 329 return p.base, true 330 } 331 return typ, false 332 } 333 334 // derefStructPtr dereferences typ if it is a (named or unnamed) pointer to a 335 // (named or unnamed) struct and returns its base. Otherwise it returns typ. 336 func derefStructPtr(typ Type) Type { 337 if p, _ := typ.Underlying().(*Pointer); p != nil { 338 if _, ok := p.base.Underlying().(*Struct); ok { 339 return p.base 340 } 341 } 342 return typ 343 } 344 345 // concat returns the result of concatenating list and i. 346 // The result does not share its underlying array with list. 347 func concat(list []int, i int) []int { 348 var t []int 349 t = append(t, list...) 350 return append(t, i) 351 } 352 353 // fieldIndex returns the index for the field with matching package and name, or a value < 0. 354 func fieldIndex(fields []*Var, pkg *Package, name string) int { 355 if name != "_" { 356 for i, f := range fields { 357 if f.sameId(pkg, name) { 358 return i 359 } 360 } 361 } 362 return -1 363 } 364 365 // lookupMethod returns the index of and method with matching package and name, or (-1, nil). 366 func lookupMethod(methods []*Func, pkg *Package, name string) (int, *Func) { 367 if name != "_" { 368 for i, m := range methods { 369 if m.sameId(pkg, name) { 370 return i, m 371 } 372 } 373 } 374 return -1, nil 375 } 376