| // Copyright 2014 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // Package satisfy inspects the type-checked ASTs of Go packages and |
| // reports the set of discovered type constraints of the form (lhs, rhs |
| // Type) where lhs is a non-trivial interface, rhs satisfies this |
| // interface, and this fact is necessary for the package to be |
| // well-typed. |
| // |
| // THIS PACKAGE IS EXPERIMENTAL AND MAY CHANGE AT ANY TIME. |
| // |
| // It is provided only for the gopls tool. It requires well-typed inputs. |
| package satisfy // import "golang.org/x/tools/refactor/satisfy" |
| |
| // NOTES: |
| // |
| // We don't care about numeric conversions, so we don't descend into |
| // types or constant expressions. This is unsound because |
| // constant expressions can contain arbitrary statements, e.g. |
| // const x = len([1]func(){func() { |
| // ... |
| // }}) |
| // |
| // Assignability conversions are possible in the following places: |
| // - in assignments y = x, y := x, var y = x. |
| // - from call argument types to formal parameter types |
| // - in append and delete calls |
| // - from return operands to result parameter types |
| // - in composite literal T{k:v}, from k and v to T's field/element/key type |
| // - in map[key] from key to the map's key type |
| // - in comparisons x==y and switch x { case y: }. |
| // - in explicit conversions T(x) |
| // - in sends ch <- x, from x to the channel element type |
| // - in type assertions x.(T) and switch x.(type) { case T: } |
| // |
| // The results of this pass provide information equivalent to the |
| // ssa.MakeInterface and ssa.ChangeInterface instructions. |
| |
| import ( |
| "fmt" |
| "go/ast" |
| "go/token" |
| "go/types" |
| |
| "golang.org/x/tools/go/ast/astutil" |
| "golang.org/x/tools/go/types/typeutil" |
| "golang.org/x/tools/internal/typeparams" |
| ) |
| |
| // A Constraint records the fact that the RHS type does and must |
| // satisfy the LHS type, which is an interface. |
| // The names are suggestive of an assignment statement LHS = RHS. |
| // |
| // The constraint is implicitly universally quantified over any type |
| // parameters appearing within the two types. |
| type Constraint struct { |
| LHS, RHS types.Type |
| } |
| |
| // A Finder inspects the type-checked ASTs of Go packages and |
| // accumulates the set of type constraints (x, y) such that x is |
| // assignable to y, y is an interface, and both x and y have methods. |
| // |
| // In other words, it returns the subset of the "implements" relation |
| // that is checked during compilation of a package. Refactoring tools |
| // will need to preserve at least this part of the relation to ensure |
| // continued compilation. |
| type Finder struct { |
| Result map[Constraint]bool |
| msetcache typeutil.MethodSetCache |
| |
| // per-Find state |
| info *types.Info |
| sig *types.Signature |
| } |
| |
| // Find inspects a single package, populating Result with its pairs of |
| // constrained types. |
| // |
| // The result is non-canonical and thus may contain duplicates (but this |
| // tends to preserves names of interface types better). |
| // |
| // The package must be free of type errors, and |
| // info.{Defs,Uses,Selections,Types} must have been populated by the |
| // type-checker. |
| func (f *Finder) Find(info *types.Info, files []*ast.File) { |
| if f.Result == nil { |
| f.Result = make(map[Constraint]bool) |
| } |
| |
| f.info = info |
| for _, file := range files { |
| for _, d := range file.Decls { |
| switch d := d.(type) { |
| case *ast.GenDecl: |
| if d.Tok == token.VAR { // ignore consts |
| for _, spec := range d.Specs { |
| f.valueSpec(spec.(*ast.ValueSpec)) |
| } |
| } |
| |
| case *ast.FuncDecl: |
| if d.Body != nil { |
| f.sig = f.info.Defs[d.Name].Type().(*types.Signature) |
| f.stmt(d.Body) |
| f.sig = nil |
| } |
| } |
| } |
| } |
| f.info = nil |
| } |
| |
| var ( |
| tInvalid = types.Typ[types.Invalid] |
| tUntypedBool = types.Typ[types.UntypedBool] |
| tUntypedNil = types.Typ[types.UntypedNil] |
| ) |
| |
| // exprN visits an expression in a multi-value context. |
| func (f *Finder) exprN(e ast.Expr) types.Type { |
| typ := f.info.Types[e].Type.(*types.Tuple) |
| switch e := e.(type) { |
| case *ast.ParenExpr: |
| return f.exprN(e.X) |
| |
| case *ast.CallExpr: |
| // x, err := f(args) |
| sig := coreType(f.expr(e.Fun)).(*types.Signature) |
| f.call(sig, e.Args) |
| |
| case *ast.IndexExpr: |
| // y, ok := x[i] |
| x := f.expr(e.X) |
| f.assign(f.expr(e.Index), coreType(x).(*types.Map).Key()) |
| |
| case *ast.TypeAssertExpr: |
| // y, ok := x.(T) |
| f.typeAssert(f.expr(e.X), typ.At(0).Type()) |
| |
| case *ast.UnaryExpr: // must be receive <- |
| // y, ok := <-x |
| f.expr(e.X) |
| |
| default: |
| panic(e) |
| } |
| return typ |
| } |
| |
| func (f *Finder) call(sig *types.Signature, args []ast.Expr) { |
| if len(args) == 0 { |
| return |
| } |
| |
| // Ellipsis call? e.g. f(x, y, z...) |
| if _, ok := args[len(args)-1].(*ast.Ellipsis); ok { |
| for i, arg := range args { |
| // The final arg is a slice, and so is the final param. |
| f.assign(sig.Params().At(i).Type(), f.expr(arg)) |
| } |
| return |
| } |
| |
| var argtypes []types.Type |
| |
| // Gather the effective actual parameter types. |
| if tuple, ok := f.info.Types[args[0]].Type.(*types.Tuple); ok { |
| // f(g()) call where g has multiple results? |
| f.expr(args[0]) |
| // unpack the tuple |
| for i := 0; i < tuple.Len(); i++ { |
| argtypes = append(argtypes, tuple.At(i).Type()) |
| } |
| } else { |
| for _, arg := range args { |
| argtypes = append(argtypes, f.expr(arg)) |
| } |
| } |
| |
| // Assign the actuals to the formals. |
| if !sig.Variadic() { |
| for i, argtype := range argtypes { |
| f.assign(sig.Params().At(i).Type(), argtype) |
| } |
| } else { |
| // The first n-1 parameters are assigned normally. |
| nnormals := sig.Params().Len() - 1 |
| for i, argtype := range argtypes[:nnormals] { |
| f.assign(sig.Params().At(i).Type(), argtype) |
| } |
| // Remaining args are assigned to elements of varargs slice. |
| tElem := sig.Params().At(nnormals).Type().(*types.Slice).Elem() |
| for i := nnormals; i < len(argtypes); i++ { |
| f.assign(tElem, argtypes[i]) |
| } |
| } |
| } |
| |
| // builtin visits the arguments of a builtin type with signature sig. |
| func (f *Finder) builtin(obj *types.Builtin, sig *types.Signature, args []ast.Expr) { |
| switch obj.Name() { |
| case "make", "new": |
| // skip the type operand |
| for _, arg := range args[1:] { |
| f.expr(arg) |
| } |
| |
| case "append": |
| s := f.expr(args[0]) |
| if _, ok := args[len(args)-1].(*ast.Ellipsis); ok && len(args) == 2 { |
| // append(x, y...) including append([]byte, "foo"...) |
| f.expr(args[1]) |
| } else { |
| // append(x, y, z) |
| tElem := coreType(s).(*types.Slice).Elem() |
| for _, arg := range args[1:] { |
| f.assign(tElem, f.expr(arg)) |
| } |
| } |
| |
| case "delete": |
| m := f.expr(args[0]) |
| k := f.expr(args[1]) |
| f.assign(coreType(m).(*types.Map).Key(), k) |
| |
| default: |
| // ordinary call |
| f.call(sig, args) |
| } |
| } |
| |
| func (f *Finder) extract(tuple types.Type, i int) types.Type { |
| if tuple, ok := tuple.(*types.Tuple); ok && i < tuple.Len() { |
| return tuple.At(i).Type() |
| } |
| return tInvalid |
| } |
| |
| func (f *Finder) valueSpec(spec *ast.ValueSpec) { |
| var T types.Type |
| if spec.Type != nil { |
| T = f.info.Types[spec.Type].Type |
| } |
| switch len(spec.Values) { |
| case len(spec.Names): // e.g. var x, y = f(), g() |
| for _, value := range spec.Values { |
| v := f.expr(value) |
| if T != nil { |
| f.assign(T, v) |
| } |
| } |
| |
| case 1: // e.g. var x, y = f() |
| tuple := f.exprN(spec.Values[0]) |
| for i := range spec.Names { |
| if T != nil { |
| f.assign(T, f.extract(tuple, i)) |
| } |
| } |
| } |
| } |
| |
| // assign records pairs of distinct types that are related by |
| // assignability, where the left-hand side is an interface and both |
| // sides have methods. |
| // |
| // It should be called for all assignability checks, type assertions, |
| // explicit conversions and comparisons between two types, unless the |
| // types are uninteresting (e.g. lhs is a concrete type, or the empty |
| // interface; rhs has no methods). |
| func (f *Finder) assign(lhs, rhs types.Type) { |
| if types.Identical(lhs, rhs) { |
| return |
| } |
| if !isInterface(lhs) { |
| return |
| } |
| |
| if f.msetcache.MethodSet(lhs).Len() == 0 { |
| return |
| } |
| if f.msetcache.MethodSet(rhs).Len() == 0 { |
| return |
| } |
| // record the pair |
| f.Result[Constraint{lhs, rhs}] = true |
| } |
| |
| // typeAssert must be called for each type assertion x.(T) where x has |
| // interface type I. |
| func (f *Finder) typeAssert(I, T types.Type) { |
| // Type assertions are slightly subtle, because they are allowed |
| // to be "impossible", e.g. |
| // |
| // var x interface{f()} |
| // _ = x.(interface{f()int}) // legal |
| // |
| // (In hindsight, the language spec should probably not have |
| // allowed this, but it's too late to fix now.) |
| // |
| // This means that a type assert from I to T isn't exactly a |
| // constraint that T is assignable to I, but for a refactoring |
| // tool it is a conditional constraint that, if T is assignable |
| // to I before a refactoring, it should remain so after. |
| |
| if types.AssignableTo(T, I) { |
| f.assign(I, T) |
| } |
| } |
| |
| // compare must be called for each comparison x==y. |
| func (f *Finder) compare(x, y types.Type) { |
| if types.AssignableTo(x, y) { |
| f.assign(y, x) |
| } else if types.AssignableTo(y, x) { |
| f.assign(x, y) |
| } |
| } |
| |
| // expr visits a true expression (not a type or defining ident) |
| // and returns its type. |
| func (f *Finder) expr(e ast.Expr) types.Type { |
| tv := f.info.Types[e] |
| if tv.Value != nil { |
| return tv.Type // prune the descent for constants |
| } |
| |
| // tv.Type may be nil for an ast.Ident. |
| |
| switch e := e.(type) { |
| case *ast.BadExpr, *ast.BasicLit: |
| // no-op |
| |
| case *ast.Ident: |
| // (referring idents only) |
| if obj, ok := f.info.Uses[e]; ok { |
| return obj.Type() |
| } |
| if e.Name == "_" { // e.g. "for _ = range x" |
| return tInvalid |
| } |
| panic("undefined ident: " + e.Name) |
| |
| case *ast.Ellipsis: |
| if e.Elt != nil { |
| f.expr(e.Elt) |
| } |
| |
| case *ast.FuncLit: |
| saved := f.sig |
| f.sig = tv.Type.(*types.Signature) |
| f.stmt(e.Body) |
| f.sig = saved |
| |
| case *ast.CompositeLit: |
| switch T := coreType(deref(tv.Type)).(type) { |
| case *types.Struct: |
| for i, elem := range e.Elts { |
| if kv, ok := elem.(*ast.KeyValueExpr); ok { |
| f.assign(f.info.Uses[kv.Key.(*ast.Ident)].Type(), f.expr(kv.Value)) |
| } else { |
| f.assign(T.Field(i).Type(), f.expr(elem)) |
| } |
| } |
| |
| case *types.Map: |
| for _, elem := range e.Elts { |
| elem := elem.(*ast.KeyValueExpr) |
| f.assign(T.Key(), f.expr(elem.Key)) |
| f.assign(T.Elem(), f.expr(elem.Value)) |
| } |
| |
| case *types.Array, *types.Slice: |
| tElem := T.(interface { |
| Elem() types.Type |
| }).Elem() |
| for _, elem := range e.Elts { |
| if kv, ok := elem.(*ast.KeyValueExpr); ok { |
| // ignore the key |
| f.assign(tElem, f.expr(kv.Value)) |
| } else { |
| f.assign(tElem, f.expr(elem)) |
| } |
| } |
| |
| default: |
| panic(fmt.Sprintf("unexpected composite literal type %T: %v", tv.Type, tv.Type.String())) |
| } |
| |
| case *ast.ParenExpr: |
| f.expr(e.X) |
| |
| case *ast.SelectorExpr: |
| if _, ok := f.info.Selections[e]; ok { |
| f.expr(e.X) // selection |
| } else { |
| return f.info.Uses[e.Sel].Type() // qualified identifier |
| } |
| |
| case *ast.IndexExpr: |
| if instance(f.info, e.X) { |
| // f[T] or C[T] -- generic instantiation |
| } else { |
| // x[i] or m[k] -- index or lookup operation |
| x := f.expr(e.X) |
| i := f.expr(e.Index) |
| if ux, ok := coreType(x).(*types.Map); ok { |
| f.assign(ux.Key(), i) |
| } |
| } |
| |
| case *ast.IndexListExpr: |
| // f[X, Y] -- generic instantiation |
| |
| case *ast.SliceExpr: |
| f.expr(e.X) |
| if e.Low != nil { |
| f.expr(e.Low) |
| } |
| if e.High != nil { |
| f.expr(e.High) |
| } |
| if e.Max != nil { |
| f.expr(e.Max) |
| } |
| |
| case *ast.TypeAssertExpr: |
| x := f.expr(e.X) |
| f.typeAssert(x, f.info.Types[e.Type].Type) |
| |
| case *ast.CallExpr: |
| if tvFun := f.info.Types[e.Fun]; tvFun.IsType() { |
| // conversion |
| arg0 := f.expr(e.Args[0]) |
| f.assign(tvFun.Type, arg0) |
| } else { |
| // function call |
| |
| // unsafe call. Treat calls to functions in unsafe like ordinary calls, |
| // except that their signature cannot be determined by their func obj. |
| // Without this special handling, f.expr(e.Fun) would fail below. |
| if s, ok := unparen(e.Fun).(*ast.SelectorExpr); ok { |
| if obj, ok := f.info.Uses[s.Sel].(*types.Builtin); ok && obj.Pkg().Path() == "unsafe" { |
| sig := f.info.Types[e.Fun].Type.(*types.Signature) |
| f.call(sig, e.Args) |
| return tv.Type |
| } |
| } |
| |
| // builtin call |
| if id, ok := unparen(e.Fun).(*ast.Ident); ok { |
| if obj, ok := f.info.Uses[id].(*types.Builtin); ok { |
| sig := f.info.Types[id].Type.(*types.Signature) |
| f.builtin(obj, sig, e.Args) |
| return tv.Type |
| } |
| } |
| |
| // ordinary call |
| f.call(coreType(f.expr(e.Fun)).(*types.Signature), e.Args) |
| } |
| |
| case *ast.StarExpr: |
| f.expr(e.X) |
| |
| case *ast.UnaryExpr: |
| f.expr(e.X) |
| |
| case *ast.BinaryExpr: |
| x := f.expr(e.X) |
| y := f.expr(e.Y) |
| if e.Op == token.EQL || e.Op == token.NEQ { |
| f.compare(x, y) |
| } |
| |
| case *ast.KeyValueExpr: |
| f.expr(e.Key) |
| f.expr(e.Value) |
| |
| case *ast.ArrayType, |
| *ast.StructType, |
| *ast.FuncType, |
| *ast.InterfaceType, |
| *ast.MapType, |
| *ast.ChanType: |
| panic(e) |
| } |
| |
| if tv.Type == nil { |
| panic(fmt.Sprintf("no type for %T", e)) |
| } |
| |
| return tv.Type |
| } |
| |
| func (f *Finder) stmt(s ast.Stmt) { |
| switch s := s.(type) { |
| case *ast.BadStmt, |
| *ast.EmptyStmt, |
| *ast.BranchStmt: |
| // no-op |
| |
| case *ast.DeclStmt: |
| d := s.Decl.(*ast.GenDecl) |
| if d.Tok == token.VAR { // ignore consts |
| for _, spec := range d.Specs { |
| f.valueSpec(spec.(*ast.ValueSpec)) |
| } |
| } |
| |
| case *ast.LabeledStmt: |
| f.stmt(s.Stmt) |
| |
| case *ast.ExprStmt: |
| f.expr(s.X) |
| |
| case *ast.SendStmt: |
| ch := f.expr(s.Chan) |
| val := f.expr(s.Value) |
| f.assign(coreType(ch).(*types.Chan).Elem(), val) |
| |
| case *ast.IncDecStmt: |
| f.expr(s.X) |
| |
| case *ast.AssignStmt: |
| switch s.Tok { |
| case token.ASSIGN, token.DEFINE: |
| // y := x or y = x |
| var rhsTuple types.Type |
| if len(s.Lhs) != len(s.Rhs) { |
| rhsTuple = f.exprN(s.Rhs[0]) |
| } |
| for i := range s.Lhs { |
| var lhs, rhs types.Type |
| if rhsTuple == nil { |
| rhs = f.expr(s.Rhs[i]) // 1:1 assignment |
| } else { |
| rhs = f.extract(rhsTuple, i) // n:1 assignment |
| } |
| |
| if id, ok := s.Lhs[i].(*ast.Ident); ok { |
| if id.Name != "_" { |
| if obj, ok := f.info.Defs[id]; ok { |
| lhs = obj.Type() // definition |
| } |
| } |
| } |
| if lhs == nil { |
| lhs = f.expr(s.Lhs[i]) // assignment |
| } |
| f.assign(lhs, rhs) |
| } |
| |
| default: |
| // y op= x |
| f.expr(s.Lhs[0]) |
| f.expr(s.Rhs[0]) |
| } |
| |
| case *ast.GoStmt: |
| f.expr(s.Call) |
| |
| case *ast.DeferStmt: |
| f.expr(s.Call) |
| |
| case *ast.ReturnStmt: |
| formals := f.sig.Results() |
| switch len(s.Results) { |
| case formals.Len(): // 1:1 |
| for i, result := range s.Results { |
| f.assign(formals.At(i).Type(), f.expr(result)) |
| } |
| |
| case 1: // n:1 |
| tuple := f.exprN(s.Results[0]) |
| for i := 0; i < formals.Len(); i++ { |
| f.assign(formals.At(i).Type(), f.extract(tuple, i)) |
| } |
| } |
| |
| case *ast.SelectStmt: |
| f.stmt(s.Body) |
| |
| case *ast.BlockStmt: |
| for _, s := range s.List { |
| f.stmt(s) |
| } |
| |
| case *ast.IfStmt: |
| if s.Init != nil { |
| f.stmt(s.Init) |
| } |
| f.expr(s.Cond) |
| f.stmt(s.Body) |
| if s.Else != nil { |
| f.stmt(s.Else) |
| } |
| |
| case *ast.SwitchStmt: |
| if s.Init != nil { |
| f.stmt(s.Init) |
| } |
| var tag types.Type = tUntypedBool |
| if s.Tag != nil { |
| tag = f.expr(s.Tag) |
| } |
| for _, cc := range s.Body.List { |
| cc := cc.(*ast.CaseClause) |
| for _, cond := range cc.List { |
| f.compare(tag, f.info.Types[cond].Type) |
| } |
| for _, s := range cc.Body { |
| f.stmt(s) |
| } |
| } |
| |
| case *ast.TypeSwitchStmt: |
| if s.Init != nil { |
| f.stmt(s.Init) |
| } |
| var I types.Type |
| switch ass := s.Assign.(type) { |
| case *ast.ExprStmt: // x.(type) |
| I = f.expr(unparen(ass.X).(*ast.TypeAssertExpr).X) |
| case *ast.AssignStmt: // y := x.(type) |
| I = f.expr(unparen(ass.Rhs[0]).(*ast.TypeAssertExpr).X) |
| } |
| for _, cc := range s.Body.List { |
| cc := cc.(*ast.CaseClause) |
| for _, cond := range cc.List { |
| tCase := f.info.Types[cond].Type |
| if tCase != tUntypedNil { |
| f.typeAssert(I, tCase) |
| } |
| } |
| for _, s := range cc.Body { |
| f.stmt(s) |
| } |
| } |
| |
| case *ast.CommClause: |
| if s.Comm != nil { |
| f.stmt(s.Comm) |
| } |
| for _, s := range s.Body { |
| f.stmt(s) |
| } |
| |
| case *ast.ForStmt: |
| if s.Init != nil { |
| f.stmt(s.Init) |
| } |
| if s.Cond != nil { |
| f.expr(s.Cond) |
| } |
| if s.Post != nil { |
| f.stmt(s.Post) |
| } |
| f.stmt(s.Body) |
| |
| case *ast.RangeStmt: |
| x := f.expr(s.X) |
| // No conversions are involved when Tok==DEFINE. |
| if s.Tok == token.ASSIGN { |
| if s.Key != nil { |
| k := f.expr(s.Key) |
| var xelem types.Type |
| // Keys of array, *array, slice, string aren't interesting |
| // since the RHS key type is just an int. |
| switch ux := coreType(x).(type) { |
| case *types.Chan: |
| xelem = ux.Elem() |
| case *types.Map: |
| xelem = ux.Key() |
| } |
| if xelem != nil { |
| f.assign(k, xelem) |
| } |
| } |
| if s.Value != nil { |
| val := f.expr(s.Value) |
| var xelem types.Type |
| // Values of type strings aren't interesting because |
| // the RHS value type is just a rune. |
| switch ux := coreType(x).(type) { |
| case *types.Array: |
| xelem = ux.Elem() |
| case *types.Map: |
| xelem = ux.Elem() |
| case *types.Pointer: // *array |
| xelem = coreType(deref(ux)).(*types.Array).Elem() |
| case *types.Slice: |
| xelem = ux.Elem() |
| } |
| if xelem != nil { |
| f.assign(val, xelem) |
| } |
| } |
| } |
| f.stmt(s.Body) |
| |
| default: |
| panic(s) |
| } |
| } |
| |
| // -- Plundered from golang.org/x/tools/go/ssa ----------------- |
| |
| // deref returns a pointer's element type; otherwise it returns typ. |
| func deref(typ types.Type) types.Type { |
| if p, ok := coreType(typ).(*types.Pointer); ok { |
| return p.Elem() |
| } |
| return typ |
| } |
| |
| func unparen(e ast.Expr) ast.Expr { return astutil.Unparen(e) } |
| |
| func isInterface(T types.Type) bool { return types.IsInterface(T) } |
| |
| func coreType(T types.Type) types.Type { return typeparams.CoreType(T) } |
| |
| func instance(info *types.Info, expr ast.Expr) bool { |
| var id *ast.Ident |
| switch x := expr.(type) { |
| case *ast.Ident: |
| id = x |
| case *ast.SelectorExpr: |
| id = x.Sel |
| default: |
| return false |
| } |
| _, ok := info.Instances[id] |
| return ok |
| } |