1 // Copyright 2017 The Go Authors. All rights reserved. 2 // Use of this src code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package types 6 7 import ( 8 "bytes" 9 "fmt" 10 "go/ast" 11 "go/token" 12 ) 13 14 // This file implements the collection of an interface's methods 15 // without relying on partially computed types of methods or interfaces 16 // for interface types declared at the package level. 17 // 18 // Because interfaces must not embed themselves, directly or indirectly, 19 // the method set of a valid interface can always be computed independent 20 // of any cycles that might exist via method signatures (see also issue #18395). 21 // 22 // Except for blank method name and interface cycle errors, no errors 23 // are reported. Affected methods or embedded interfaces are silently 24 // dropped. Subsequent type-checking of the interface will check 25 // signatures and embedded interfaces and report errors at that time. 26 // 27 // Only infoFromTypeLit should be called directly from code outside this file 28 // to compute an ifaceInfo. 29 30 // ifaceInfo describes the method set for an interface. 31 // The zero value for an ifaceInfo is a ready-to-use ifaceInfo representing 32 // the empty interface. 33 type ifaceInfo struct { 34 explicits int // number of explicitly declared methods 35 methods []*methodInfo // all methods, starting with explicitly declared ones in source order 36 } 37 38 // emptyIfaceInfo represents the ifaceInfo for the empty interface. 39 var emptyIfaceInfo ifaceInfo 40 41 func (info *ifaceInfo) String() string { 42 var buf bytes.Buffer 43 fmt.Fprintf(&buf, "interface{") 44 for i, m := range info.methods { 45 if i > 0 { 46 fmt.Fprint(&buf, " ") 47 } 48 fmt.Fprint(&buf, m) 49 } 50 fmt.Fprintf(&buf, "}") 51 return buf.String() 52 } 53 54 // methodInfo represents an interface method. 55 // At least one of src or fun must be non-nil. 56 // (Methods declared in the current package have a non-nil scope 57 // and src, and eventually a non-nil fun field; imported and pre- 58 // declared methods have a nil scope and src, and only a non-nil 59 // fun field.) 60 type methodInfo struct { 61 scope *Scope // scope of interface method; or nil 62 src *ast.Field // syntax tree representation of interface method; or nil 63 fun *Func // corresponding fully type-checked method type; or nil 64 } 65 66 func (info *methodInfo) String() string { 67 if info.fun != nil { 68 return info.fun.name 69 } 70 return info.src.Names[0].Name 71 } 72 73 func (info *methodInfo) Pos() token.Pos { 74 if info.fun != nil { 75 return info.fun.Pos() 76 } 77 return info.src.Pos() 78 } 79 80 func (info *methodInfo) id(pkg *Package) string { 81 if info.fun != nil { 82 return info.fun.Id() 83 } 84 return Id(pkg, info.src.Names[0].Name) 85 } 86 87 // A methodInfoSet maps method ids to methodInfos. 88 // It is used to determine duplicate declarations. 89 // (A methodInfo set is the equivalent of an objset 90 // but for methodInfos rather than Objects.) 91 type methodInfoSet map[string]*methodInfo 92 93 // insert attempts to insert an method m into the method set s. 94 // If s already contains an alternative method alt with 95 // the same name, insert leaves s unchanged and returns alt. 96 // Otherwise it inserts m and returns nil. 97 func (s *methodInfoSet) insert(pkg *Package, m *methodInfo) *methodInfo { 98 id := m.id(pkg) 99 if alt := (*s)[id]; alt != nil { 100 return alt 101 } 102 if *s == nil { 103 *s = make(methodInfoSet) 104 } 105 (*s)[id] = m 106 return nil 107 } 108 109 // like Checker.declareInSet but for method infos. 110 func (check *Checker) declareInMethodSet(mset *methodInfoSet, pos token.Pos, m *methodInfo) bool { 111 if alt := mset.insert(check.pkg, m); alt != nil { 112 check.errorf(pos, "%s redeclared", m) 113 check.reportAltMethod(alt) 114 return false 115 } 116 return true 117 } 118 119 // like Checker.reportAltDecl but for method infos. 120 func (check *Checker) reportAltMethod(m *methodInfo) { 121 if pos := m.Pos(); pos.IsValid() { 122 // We use "other" rather than "previous" here because 123 // the first declaration seen may not be textually 124 // earlier in the source. 125 check.errorf(pos, "\tother declaration of %s", m) // secondary error, \t indented 126 } 127 } 128 129 // infoFromTypeLit computes the method set for the given interface iface 130 // declared in scope. 131 // If a corresponding type name exists (tname != nil), it is used for 132 // cycle detection and to cache the method set. 133 // The result is the method set, or nil if there is a cycle via embedded 134 // interfaces. A non-nil result doesn't mean that there were no errors, 135 // but they were either reported (e.g., blank methods), or will be found 136 // (again) when computing the interface's type. 137 // If tname is not nil it must be the last element in path. 138 func (check *Checker) infoFromTypeLit(scope *Scope, iface *ast.InterfaceType, tname *TypeName, path []*TypeName) (info *ifaceInfo) { 139 assert(iface != nil) 140 141 // lazy-allocate interfaces map 142 if check.interfaces == nil { 143 check.interfaces = make(map[*TypeName]*ifaceInfo) 144 } 145 146 if trace { 147 check.trace(iface.Pos(), "-- collect methods for %v (path = %s, objPath = %s)", iface, pathString(path), objPathString(check.objPath)) 148 check.indent++ 149 defer func() { 150 check.indent-- 151 check.trace(iface.Pos(), "=> %s", info) 152 }() 153 } 154 155 // If the interface is named, check if we computed info already. 156 // 157 // This is not simply an optimization; we may run into stack 158 // overflow with recursive interface declarations. Example: 159 // 160 // type T interface { 161 // m() interface { T } 162 // } 163 // 164 // (Since recursive definitions can only be expressed via names, 165 // it is sufficient to track named interfaces here.) 166 // 167 // While at it, use the same mechanism to detect cycles. (We still 168 // have the path-based cycle check because we want to report the 169 // entire cycle if present.) 170 if tname != nil { 171 assert(path[len(path)-1] == tname) // tname must be last path element 172 var found bool 173 if info, found = check.interfaces[tname]; found { 174 if info == nil { 175 // We have a cycle and use check.cycle to report it. 176 // We are guaranteed that check.cycle also finds the 177 // cycle because when infoFromTypeLit is called, any 178 // tname that's already in check.interfaces was also 179 // added to the path. (But the converse is not true: 180 // A non-nil tname is always the last element in path.) 181 ok := check.cycle(tname, path, true) 182 assert(ok) 183 } 184 return 185 } 186 check.interfaces[tname] = nil // computation started but not complete 187 } 188 189 if iface.Methods.List == nil { 190 // fast track for empty interface 191 info = &emptyIfaceInfo 192 } else { 193 // (syntactically) non-empty interface 194 info = new(ifaceInfo) 195 196 // collect explicitly declared methods and embedded interfaces 197 var mset methodInfoSet 198 var embeddeds []*ifaceInfo 199 var positions []token.Pos // entries correspond to positions of embeddeds; used for error reporting 200 for _, f := range iface.Methods.List { 201 if len(f.Names) > 0 { 202 // We have a method with name f.Names[0]. 203 // (The parser ensures that there's only one method 204 // and we don't care if a constructed AST has more.) 205 206 // spec: "As with all method sets, in an interface type, 207 // each method must have a unique non-blank name." 208 if name := f.Names[0]; name.Name == "_" { 209 check.errorf(name.Pos(), "invalid method name _") 210 continue // ignore 211 } 212 213 m := &methodInfo{scope: scope, src: f} 214 if check.declareInMethodSet(&mset, f.Pos(), m) { 215 info.methods = append(info.methods, m) 216 } 217 } else { 218 // We have an embedded interface and f.Type is its 219 // (possibly qualified) embedded type name. Collect 220 // it if it's a valid interface. 221 var e *ifaceInfo 222 switch ename := f.Type.(type) { 223 case *ast.Ident: 224 e = check.infoFromTypeName(scope, ename, path) 225 case *ast.SelectorExpr: 226 e = check.infoFromQualifiedTypeName(scope, ename) 227 default: 228 // The parser makes sure we only see one of the above. 229 // Constructed ASTs may contain other (invalid) nodes; 230 // we simply ignore them. The full type-checking pass 231 // will report those as errors later. 232 } 233 if e != nil { 234 embeddeds = append(embeddeds, e) 235 positions = append(positions, f.Type.Pos()) 236 } 237 } 238 } 239 info.explicits = len(info.methods) 240 241 // collect methods of embedded interfaces 242 for i, e := range embeddeds { 243 pos := positions[i] // position of type name of embedded interface 244 for _, m := range e.methods { 245 if check.declareInMethodSet(&mset, pos, m) { 246 info.methods = append(info.methods, m) 247 } 248 } 249 } 250 } 251 252 // mark check.interfaces as complete 253 assert(info != nil) 254 if tname != nil { 255 check.interfaces[tname] = info 256 } 257 258 return 259 } 260 261 // infoFromTypeName computes the method set for the given type name 262 // which must denote a type whose underlying type is an interface. 263 // The same result qualifications apply as for infoFromTypeLit. 264 // infoFromTypeName should only be called from infoFromTypeLit. 265 func (check *Checker) infoFromTypeName(scope *Scope, name *ast.Ident, path []*TypeName) *ifaceInfo { 266 // A single call of infoFromTypeName handles a sequence of (possibly 267 // recursive) type declarations connected via unqualified type names. 268 // Each type declaration leading to another typename causes a "tail call" 269 // (goto) of this function. The general scenario looks like this: 270 // 271 // ... 272 // type Pn T // previous declarations leading to T, path = [..., Pn] 273 // type T interface { T0; ... } // T0 leads to call of infoFromTypeName 274 // 275 // // infoFromTypeName(name = T0, path = [..., Pn, T]) 276 // type T0 T1 // path = [..., Pn, T, T0] 277 // type T1 T2 <-+ // path = [..., Pn, T, T0, T1] 278 // type T2 ... | // path = [..., Pn, T, T0, T1, T2] 279 // type Tn T1 --+ // path = [..., Pn, T, T0, T1, T2, Tn] and T1 is in path => cycle 280 // 281 // infoFromTypeName returns nil when such a cycle is detected. But in 282 // contrast to cycles involving interfaces, we must not report the 283 // error for "type name only" cycles because they will be found again 284 // during type-checking of embedded interfaces. Reporting those cycles 285 // here would lead to double reporting. Cycles involving embedding are 286 // not reported again later because type-checking of interfaces relies 287 // on the ifaceInfos computed here which are cycle-free by design. 288 // 289 // Remember the path length to detect "type name only" cycles. 290 start := len(path) 291 292 typenameLoop: 293 // name must be a type name denoting a type whose underlying type is an interface 294 _, obj := scope.LookupParent(name.Name, check.pos) 295 if obj == nil { 296 return nil 297 } 298 tname, _ := obj.(*TypeName) 299 if tname == nil { 300 return nil 301 } 302 303 // We have a type name. It may be predeclared (error type), 304 // imported (dot import), or declared by a type declaration. 305 // It may not be an interface (e.g., predeclared type int). 306 // Resolve it by analyzing each possible case. 307 308 // Abort but don't report an error if we have a "type name only" 309 // cycle (see big function comment). 310 if check.cycle(tname, path[start:], false) { 311 return nil 312 } 313 314 // Abort and report an error if we have a general cycle. 315 if check.cycle(tname, path, true) { 316 return nil 317 } 318 319 path = append(path, tname) 320 321 // If tname is a package-level type declaration, it must be 322 // in the objMap. Follow the RHS of that declaration if so. 323 // The RHS may be a literal type (likely case), or another 324 // (possibly parenthesized and/or qualified) type name. 325 // (The declaration may be an alias declaration, but it 326 // doesn't matter for the purpose of determining the under- 327 // lying interface.) 328 if decl := check.objMap[tname]; decl != nil { 329 switch typ := unparen(decl.typ).(type) { 330 case *ast.Ident: 331 // type tname T 332 name = typ 333 goto typenameLoop 334 case *ast.SelectorExpr: 335 // type tname p.T 336 return check.infoFromQualifiedTypeName(decl.file, typ) 337 case *ast.InterfaceType: 338 // type tname interface{...} 339 // If tname is fully type-checked at this point (tname.color() == black) 340 // we could use infoFromType here. But in this case, the interface must 341 // be in the check.interfaces cache as well, which will be hit when we 342 // call infoFromTypeLit below, and which will be faster. It is important 343 // that we use that previously computed interface because its methods 344 // have the correct receiver type (for go/types clients). Thus, the 345 // check.interfaces cache must be up-to-date across even across multiple 346 // check.Files calls (was bug - see issue #29029). 347 return check.infoFromTypeLit(decl.file, typ, tname, path) 348 } 349 // type tname X // and X is not an interface type 350 return nil 351 } 352 353 // If tname is not a package-level declaration, in a well-typed 354 // program it should be a predeclared (error type), imported (dot 355 // import), or function local declaration. Either way, it should 356 // have been fully declared before use, except if there is a direct 357 // cycle, and direct cycles will be caught above. Also, the denoted 358 // type should be an interface (e.g., int is not an interface). 359 if typ := tname.typ; typ != nil { 360 // typ should be an interface 361 if ityp, _ := typ.Underlying().(*Interface); ityp != nil { 362 return infoFromType(ityp) 363 } 364 } 365 366 // In all other cases we have some error. 367 return nil 368 } 369 370 // infoFromQualifiedTypeName computes the method set for the given qualified type name, or nil. 371 func (check *Checker) infoFromQualifiedTypeName(scope *Scope, qname *ast.SelectorExpr) *ifaceInfo { 372 // see also Checker.selector 373 name, _ := qname.X.(*ast.Ident) 374 if name == nil { 375 return nil 376 } 377 _, obj1 := scope.LookupParent(name.Name, check.pos) 378 if obj1 == nil { 379 return nil 380 } 381 pname, _ := obj1.(*PkgName) 382 if pname == nil { 383 return nil 384 } 385 assert(pname.pkg == check.pkg) 386 obj2 := pname.imported.scope.Lookup(qname.Sel.Name) 387 if obj2 == nil || !obj2.Exported() { 388 return nil 389 } 390 tname, _ := obj2.(*TypeName) 391 if tname == nil { 392 return nil 393 } 394 ityp, _ := tname.typ.Underlying().(*Interface) 395 if ityp == nil { 396 return nil 397 } 398 return infoFromType(ityp) 399 } 400 401 // infoFromType computes the method set for the given interface type. 402 // The result is never nil. 403 func infoFromType(typ *Interface) *ifaceInfo { 404 assert(typ.allMethods != nil) // typ must be completely set up 405 406 // fast track for empty interface 407 n := len(typ.allMethods) 408 if n == 0 { 409 return &emptyIfaceInfo 410 } 411 412 info := new(ifaceInfo) 413 info.explicits = len(typ.methods) 414 info.methods = make([]*methodInfo, n) 415 416 // If there are no embedded interfaces, simply collect the 417 // explicitly declared methods (optimization of common case). 418 if len(typ.methods) == n { 419 for i, m := range typ.methods { 420 info.methods[i] = &methodInfo{fun: m} 421 } 422 return info 423 } 424 425 // Interface types have a separate list for explicitly declared methods 426 // which shares its methods with the list of all (explicitly declared or 427 // embedded) methods. Collect all methods in a set so we can separate 428 // the embedded methods from the explicitly declared ones. 429 all := make(map[*Func]bool, n) 430 for _, m := range typ.allMethods { 431 all[m] = true 432 } 433 assert(len(all) == n) // methods must be unique 434 435 // collect explicitly declared methods 436 info.methods = make([]*methodInfo, n) 437 for i, m := range typ.methods { 438 info.methods[i] = &methodInfo{fun: m} 439 delete(all, m) 440 } 441 442 // collect remaining (embedded) methods 443 i := len(typ.methods) 444 for m := range all { 445 info.methods[i] = &methodInfo{fun: m} 446 i++ 447 } 448 assert(i == n) 449 450 return info 451 } 452