1 // Copyright 2014 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.
5 // Package satisfy inspects the type-checked ASTs of Go packages and
6 // reports the set of discovered type constraints of the form (lhs, rhs
7 // Type) where lhs is a non-trivial interface, rhs satisfies this
8 // interface, and this fact is necessary for the package to be
11 // THIS PACKAGE IS EXPERIMENTAL AND MAY CHANGE AT ANY TIME.
13 // It is provided only for the gorename tool. Ideally this
14 // functionality will become part of the type-checker in due course,
15 // since it is computing it anyway, and it is robust for ill-typed
16 // inputs, which this package is not.
18 package satisfy // import "golang.org/x/tools/refactor/satisfy"
22 // We don't care about numeric conversions, so we don't descend into
23 // types or constant expressions. This is unsound because
24 // constant expressions can contain arbitrary statements, e.g.
25 // const x = len([1]func(){func() {
29 // TODO(adonovan): make this robust against ill-typed input.
30 // Or move it into the type-checker.
32 // Assignability conversions are possible in the following places:
33 // - in assignments y = x, y := x, var y = x.
34 // - from call argument types to formal parameter types
35 // - in append and delete calls
36 // - from return operands to result parameter types
37 // - in composite literal T{k:v}, from k and v to T's field/element/key type
38 // - in map[key] from key to the map's key type
39 // - in comparisons x==y and switch x { case y: }.
40 // - in explicit conversions T(x)
41 // - in sends ch <- x, from x to the channel element type
42 // - in type assertions x.(T) and switch x.(type) { case T: }
44 // The results of this pass provide information equivalent to the
45 // ssa.MakeInterface and ssa.ChangeInterface instructions.
53 "golang.org/x/tools/go/ast/astutil"
54 "golang.org/x/tools/go/types/typeutil"
57 // A Constraint records the fact that the RHS type does and must
58 // satisfy the LHS type, which is an interface.
59 // The names are suggestive of an assignment statement LHS = RHS.
60 type Constraint struct {
64 // A Finder inspects the type-checked ASTs of Go packages and
65 // accumulates the set of type constraints (x, y) such that x is
66 // assignable to y, y is an interface, and both x and y have methods.
68 // In other words, it returns the subset of the "implements" relation
69 // that is checked during compilation of a package. Refactoring tools
70 // will need to preserve at least this part of the relation to ensure
71 // continued compilation.
74 Result map[Constraint]bool
75 msetcache typeutil.MethodSetCache
82 // Find inspects a single package, populating Result with its pairs of
85 // The result is non-canonical and thus may contain duplicates (but this
86 // tends to preserves names of interface types better).
88 // The package must be free of type errors, and
89 // info.{Defs,Uses,Selections,Types} must have been populated by the
92 func (f *Finder) Find(info *types.Info, files []*ast.File) {
94 f.Result = make(map[Constraint]bool)
98 for _, file := range files {
99 for _, d := range file.Decls {
100 switch d := d.(type) {
102 if d.Tok == token.VAR { // ignore consts
103 for _, spec := range d.Specs {
104 f.valueSpec(spec.(*ast.ValueSpec))
110 f.sig = f.info.Defs[d.Name].Type().(*types.Signature)
121 tInvalid = types.Typ[types.Invalid]
122 tUntypedBool = types.Typ[types.UntypedBool]
123 tUntypedNil = types.Typ[types.UntypedNil]
126 // exprN visits an expression in a multi-value context.
127 func (f *Finder) exprN(e ast.Expr) types.Type {
128 typ := f.info.Types[e].Type.(*types.Tuple)
129 switch e := e.(type) {
135 sig := f.expr(e.Fun).Underlying().(*types.Signature)
141 f.assign(f.expr(e.Index), x.Underlying().(*types.Map).Key())
143 case *ast.TypeAssertExpr:
145 f.typeAssert(f.expr(e.X), typ.At(0).Type())
147 case *ast.UnaryExpr: // must be receive <-
157 func (f *Finder) call(sig *types.Signature, args []ast.Expr) {
162 // Ellipsis call? e.g. f(x, y, z...)
163 if _, ok := args[len(args)-1].(*ast.Ellipsis); ok {
164 for i, arg := range args {
165 // The final arg is a slice, and so is the final param.
166 f.assign(sig.Params().At(i).Type(), f.expr(arg))
171 var argtypes []types.Type
173 // Gather the effective actual parameter types.
174 if tuple, ok := f.info.Types[args[0]].Type.(*types.Tuple); ok {
175 // f(g()) call where g has multiple results?
178 for i := 0; i < tuple.Len(); i++ {
179 argtypes = append(argtypes, tuple.At(i).Type())
182 for _, arg := range args {
183 argtypes = append(argtypes, f.expr(arg))
187 // Assign the actuals to the formals.
189 for i, argtype := range argtypes {
190 f.assign(sig.Params().At(i).Type(), argtype)
193 // The first n-1 parameters are assigned normally.
194 nnormals := sig.Params().Len() - 1
195 for i, argtype := range argtypes[:nnormals] {
196 f.assign(sig.Params().At(i).Type(), argtype)
198 // Remaining args are assigned to elements of varargs slice.
199 tElem := sig.Params().At(nnormals).Type().(*types.Slice).Elem()
200 for i := nnormals; i < len(argtypes); i++ {
201 f.assign(tElem, argtypes[i])
206 func (f *Finder) builtin(obj *types.Builtin, sig *types.Signature, args []ast.Expr, T types.Type) types.Type {
209 // skip the type operand
210 for _, arg := range args[1:] {
216 if _, ok := args[len(args)-1].(*ast.Ellipsis); ok && len(args) == 2 {
217 // append(x, y...) including append([]byte, "foo"...)
221 tElem := s.Underlying().(*types.Slice).Elem()
222 for _, arg := range args[1:] {
223 f.assign(tElem, f.expr(arg))
230 f.assign(m.Underlying().(*types.Map).Key(), k)
240 func (f *Finder) extract(tuple types.Type, i int) types.Type {
241 if tuple, ok := tuple.(*types.Tuple); ok && i < tuple.Len() {
242 return tuple.At(i).Type()
247 func (f *Finder) valueSpec(spec *ast.ValueSpec) {
249 if spec.Type != nil {
250 T = f.info.Types[spec.Type].Type
252 switch len(spec.Values) {
253 case len(spec.Names): // e.g. var x, y = f(), g()
254 for _, value := range spec.Values {
261 case 1: // e.g. var x, y = f()
262 tuple := f.exprN(spec.Values[0])
263 for i := range spec.Names {
265 f.assign(T, f.extract(tuple, i))
271 // assign records pairs of distinct types that are related by
272 // assignability, where the left-hand side is an interface and both
273 // sides have methods.
275 // It should be called for all assignability checks, type assertions,
276 // explicit conversions and comparisons between two types, unless the
277 // types are uninteresting (e.g. lhs is a concrete type, or the empty
278 // interface; rhs has no methods).
280 func (f *Finder) assign(lhs, rhs types.Type) {
281 if types.Identical(lhs, rhs) {
284 if !isInterface(lhs) {
288 if f.msetcache.MethodSet(lhs).Len() == 0 {
291 if f.msetcache.MethodSet(rhs).Len() == 0 {
295 f.Result[Constraint{lhs, rhs}] = true
298 // typeAssert must be called for each type assertion x.(T) where x has
300 func (f *Finder) typeAssert(I, T types.Type) {
301 // Type assertions are slightly subtle, because they are allowed
302 // to be "impossible", e.g.
304 // var x interface{f()}
305 // _ = x.(interface{f()int}) // legal
307 // (In hindsight, the language spec should probably not have
308 // allowed this, but it's too late to fix now.)
310 // This means that a type assert from I to T isn't exactly a
311 // constraint that T is assignable to I, but for a refactoring
312 // tool it is a conditional constraint that, if T is assignable
313 // to I before a refactoring, it should remain so after.
315 if types.AssignableTo(T, I) {
320 // compare must be called for each comparison x==y.
321 func (f *Finder) compare(x, y types.Type) {
322 if types.AssignableTo(x, y) {
324 } else if types.AssignableTo(y, x) {
329 // expr visits a true expression (not a type or defining ident)
330 // and returns its type.
331 func (f *Finder) expr(e ast.Expr) types.Type {
332 tv := f.info.Types[e]
334 return tv.Type // prune the descent for constants
337 // tv.Type may be nil for an ast.Ident.
339 switch e := e.(type) {
340 case *ast.BadExpr, *ast.BasicLit:
344 // (referring idents only)
345 if obj, ok := f.info.Uses[e]; ok {
348 if e.Name == "_" { // e.g. "for _ = range x"
351 panic("undefined ident: " + e.Name)
360 f.sig = tv.Type.(*types.Signature)
364 case *ast.CompositeLit:
365 switch T := deref(tv.Type).Underlying().(type) {
367 for i, elem := range e.Elts {
368 if kv, ok := elem.(*ast.KeyValueExpr); ok {
369 f.assign(f.info.Uses[kv.Key.(*ast.Ident)].Type(), f.expr(kv.Value))
371 f.assign(T.Field(i).Type(), f.expr(elem))
376 for _, elem := range e.Elts {
377 elem := elem.(*ast.KeyValueExpr)
378 f.assign(T.Key(), f.expr(elem.Key))
379 f.assign(T.Elem(), f.expr(elem.Value))
382 case *types.Array, *types.Slice:
383 tElem := T.(interface {
386 for _, elem := range e.Elts {
387 if kv, ok := elem.(*ast.KeyValueExpr); ok {
389 f.assign(tElem, f.expr(kv.Value))
391 f.assign(tElem, f.expr(elem))
396 panic("unexpected composite literal type: " + tv.Type.String())
402 case *ast.SelectorExpr:
403 if _, ok := f.info.Selections[e]; ok {
404 f.expr(e.X) // selection
406 return f.info.Uses[e.Sel].Type() // qualified identifier
412 if ux, ok := x.Underlying().(*types.Map); ok {
413 f.assign(ux.Key(), i)
428 case *ast.TypeAssertExpr:
430 f.typeAssert(x, f.info.Types[e.Type].Type)
433 if tvFun := f.info.Types[e.Fun]; tvFun.IsType() {
435 arg0 := f.expr(e.Args[0])
436 f.assign(tvFun.Type, arg0)
439 if id, ok := unparen(e.Fun).(*ast.Ident); ok {
440 if obj, ok := f.info.Uses[id].(*types.Builtin); ok {
441 sig := f.info.Types[id].Type.(*types.Signature)
442 return f.builtin(obj, sig, e.Args, tv.Type)
446 f.call(f.expr(e.Fun).Underlying().(*types.Signature), e.Args)
455 case *ast.BinaryExpr:
458 if e.Op == token.EQL || e.Op == token.NEQ {
462 case *ast.KeyValueExpr:
476 panic(fmt.Sprintf("no type for %T", e))
482 func (f *Finder) stmt(s ast.Stmt) {
483 switch s := s.(type) {
490 d := s.Decl.(*ast.GenDecl)
491 if d.Tok == token.VAR { // ignore consts
492 for _, spec := range d.Specs {
493 f.valueSpec(spec.(*ast.ValueSpec))
497 case *ast.LabeledStmt:
505 val := f.expr(s.Value)
506 f.assign(ch.Underlying().(*types.Chan).Elem(), val)
508 case *ast.IncDecStmt:
511 case *ast.AssignStmt:
513 case token.ASSIGN, token.DEFINE:
515 var rhsTuple types.Type
516 if len(s.Lhs) != len(s.Rhs) {
517 rhsTuple = f.exprN(s.Rhs[0])
519 for i := range s.Lhs {
520 var lhs, rhs types.Type
522 rhs = f.expr(s.Rhs[i]) // 1:1 assignment
524 rhs = f.extract(rhsTuple, i) // n:1 assignment
527 if id, ok := s.Lhs[i].(*ast.Ident); ok {
529 if obj, ok := f.info.Defs[id]; ok {
530 lhs = obj.Type() // definition
535 lhs = f.expr(s.Lhs[i]) // assignment
552 case *ast.ReturnStmt:
553 formals := f.sig.Results()
554 switch len(s.Results) {
555 case formals.Len(): // 1:1
556 for i, result := range s.Results {
557 f.assign(formals.At(i).Type(), f.expr(result))
561 tuple := f.exprN(s.Results[0])
562 for i := 0; i < formals.Len(); i++ {
563 f.assign(formals.At(i).Type(), f.extract(tuple, i))
567 case *ast.SelectStmt:
571 for _, s := range s.List {
585 case *ast.SwitchStmt:
589 var tag types.Type = tUntypedBool
593 for _, cc := range s.Body.List {
594 cc := cc.(*ast.CaseClause)
595 for _, cond := range cc.List {
596 f.compare(tag, f.info.Types[cond].Type)
598 for _, s := range cc.Body {
603 case *ast.TypeSwitchStmt:
608 switch ass := s.Assign.(type) {
609 case *ast.ExprStmt: // x.(type)
610 I = f.expr(unparen(ass.X).(*ast.TypeAssertExpr).X)
611 case *ast.AssignStmt: // y := x.(type)
612 I = f.expr(unparen(ass.Rhs[0]).(*ast.TypeAssertExpr).X)
614 for _, cc := range s.Body.List {
615 cc := cc.(*ast.CaseClause)
616 for _, cond := range cc.List {
617 tCase := f.info.Types[cond].Type
618 if tCase != tUntypedNil {
619 f.typeAssert(I, tCase)
622 for _, s := range cc.Body {
627 case *ast.CommClause:
631 for _, s := range s.Body {
649 // No conversions are involved when Tok==DEFINE.
650 if s.Tok == token.ASSIGN {
654 // keys of array, *array, slice, string aren't interesting
655 switch ux := x.Underlying().(type) {
666 val := f.expr(s.Value)
668 // values of strings aren't interesting
669 switch ux := x.Underlying().(type) {
676 case *types.Pointer: // *array
677 xelem = deref(ux).(*types.Array).Elem()
693 // -- Plundered from golang.org/x/tools/go/ssa -----------------
695 // deref returns a pointer's element type; otherwise it returns typ.
696 func deref(typ types.Type) types.Type {
697 if p, ok := typ.Underlying().(*types.Pointer); ok {
703 func unparen(e ast.Expr) ast.Expr { return astutil.Unparen(e) }
705 func isInterface(T types.Type) bool { return types.IsInterface(T) }