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. 4 5package eg 6 7import ( 8 "fmt" 9 "go/ast" 10 "go/constant" 11 "go/token" 12 "go/types" 13 "log" 14 "os" 15 "reflect" 16 17 "golang.org/x/tools/go/ast/astutil" 18) 19 20// matchExpr reports whether pattern x matches y. 21// 22// If tr.allowWildcards, Idents in x that refer to parameters are 23// treated as wildcards, and match any y that is assignable to the 24// parameter type; matchExpr records this correspondence in tr.env. 25// Otherwise, matchExpr simply reports whether the two trees are 26// equivalent. 27// 28// A wildcard appearing more than once in the pattern must 29// consistently match the same tree. 30// 31func (tr *Transformer) matchExpr(x, y ast.Expr) bool { 32 if x == nil && y == nil { 33 return true 34 } 35 if x == nil || y == nil { 36 return false 37 } 38 x = unparen(x) 39 y = unparen(y) 40 41 // Is x a wildcard? (a reference to a 'before' parameter) 42 if xobj, ok := tr.wildcardObj(x); ok { 43 return tr.matchWildcard(xobj, y) 44 } 45 46 // Object identifiers (including pkg-qualified ones) 47 // are handled semantically, not syntactically. 48 xobj := isRef(x, tr.info) 49 yobj := isRef(y, tr.info) 50 if xobj != nil { 51 return xobj == yobj 52 } 53 if yobj != nil { 54 return false 55 } 56 57 // TODO(adonovan): audit: we cannot assume these ast.Exprs 58 // contain non-nil pointers. e.g. ImportSpec.Name may be a 59 // nil *ast.Ident. 60 61 if reflect.TypeOf(x) != reflect.TypeOf(y) { 62 return false 63 } 64 switch x := x.(type) { 65 case *ast.Ident: 66 log.Fatalf("unexpected Ident: %s", astString(tr.fset, x)) 67 68 case *ast.BasicLit: 69 y := y.(*ast.BasicLit) 70 xval := constant.MakeFromLiteral(x.Value, x.Kind, 0) 71 yval := constant.MakeFromLiteral(y.Value, y.Kind, 0) 72 return constant.Compare(xval, token.EQL, yval) 73 74 case *ast.FuncLit: 75 // func literals (and thus statement syntax) never match. 76 return false 77 78 case *ast.CompositeLit: 79 y := y.(*ast.CompositeLit) 80 return (x.Type == nil) == (y.Type == nil) && 81 (x.Type == nil || tr.matchType(x.Type, y.Type)) && 82 tr.matchExprs(x.Elts, y.Elts) 83 84 case *ast.SelectorExpr: 85 y := y.(*ast.SelectorExpr) 86 return tr.matchSelectorExpr(x, y) && 87 tr.info.Selections[x].Obj() == tr.info.Selections[y].Obj() 88 89 case *ast.IndexExpr: 90 y := y.(*ast.IndexExpr) 91 return tr.matchExpr(x.X, y.X) && 92 tr.matchExpr(x.Index, y.Index) 93 94 case *ast.SliceExpr: 95 y := y.(*ast.SliceExpr) 96 return tr.matchExpr(x.X, y.X) && 97 tr.matchExpr(x.Low, y.Low) && 98 tr.matchExpr(x.High, y.High) && 99 tr.matchExpr(x.Max, y.Max) && 100 x.Slice3 == y.Slice3 101 102 case *ast.TypeAssertExpr: 103 y := y.(*ast.TypeAssertExpr) 104 return tr.matchExpr(x.X, y.X) && 105 tr.matchType(x.Type, y.Type) 106 107 case *ast.CallExpr: 108 y := y.(*ast.CallExpr) 109 match := tr.matchExpr // function call 110 if tr.info.Types[x.Fun].IsType() { 111 match = tr.matchType // type conversion 112 } 113 return x.Ellipsis.IsValid() == y.Ellipsis.IsValid() && 114 match(x.Fun, y.Fun) && 115 tr.matchExprs(x.Args, y.Args) 116 117 case *ast.StarExpr: 118 y := y.(*ast.StarExpr) 119 return tr.matchExpr(x.X, y.X) 120 121 case *ast.UnaryExpr: 122 y := y.(*ast.UnaryExpr) 123 return x.Op == y.Op && 124 tr.matchExpr(x.X, y.X) 125 126 case *ast.BinaryExpr: 127 y := y.(*ast.BinaryExpr) 128 return x.Op == y.Op && 129 tr.matchExpr(x.X, y.X) && 130 tr.matchExpr(x.Y, y.Y) 131 132 case *ast.KeyValueExpr: 133 y := y.(*ast.KeyValueExpr) 134 return tr.matchExpr(x.Key, y.Key) && 135 tr.matchExpr(x.Value, y.Value) 136 } 137 138 panic(fmt.Sprintf("unhandled AST node type: %T", x)) 139} 140 141func (tr *Transformer) matchExprs(xx, yy []ast.Expr) bool { 142 if len(xx) != len(yy) { 143 return false 144 } 145 for i := range xx { 146 if !tr.matchExpr(xx[i], yy[i]) { 147 return false 148 } 149 } 150 return true 151} 152 153// matchType reports whether the two type ASTs denote identical types. 154func (tr *Transformer) matchType(x, y ast.Expr) bool { 155 tx := tr.info.Types[x].Type 156 ty := tr.info.Types[y].Type 157 return types.Identical(tx, ty) 158} 159 160func (tr *Transformer) wildcardObj(x ast.Expr) (*types.Var, bool) { 161 if x, ok := x.(*ast.Ident); ok && x != nil && tr.allowWildcards { 162 if xobj, ok := tr.info.Uses[x].(*types.Var); ok && tr.wildcards[xobj] { 163 return xobj, true 164 } 165 } 166 return nil, false 167} 168 169func (tr *Transformer) matchSelectorExpr(x, y *ast.SelectorExpr) bool { 170 if xobj, ok := tr.wildcardObj(x.X); ok { 171 field := x.Sel.Name 172 yt := tr.info.TypeOf(y.X) 173 o, _, _ := types.LookupFieldOrMethod(yt, true, tr.currentPkg, field) 174 if o != nil { 175 tr.env[xobj.Name()] = y.X // record binding 176 return true 177 } 178 } 179 return tr.matchExpr(x.X, y.X) 180} 181 182func (tr *Transformer) matchWildcard(xobj *types.Var, y ast.Expr) bool { 183 name := xobj.Name() 184 185 if tr.verbose { 186 fmt.Fprintf(os.Stderr, "%s: wildcard %s -> %s?: ", 187 tr.fset.Position(y.Pos()), name, astString(tr.fset, y)) 188 } 189 190 // Check that y is assignable to the declared type of the param. 191 yt := tr.info.TypeOf(y) 192 if yt == nil { 193 // y has no type. 194 // Perhaps it is an *ast.Ellipsis in [...]T{}, or 195 // an *ast.KeyValueExpr in T{k: v}. 196 // Clearly these pseudo-expressions cannot match a 197 // wildcard, but it would nice if we had a way to ignore 198 // the difference between T{v} and T{k:v} for structs. 199 return false 200 } 201 if !types.AssignableTo(yt, xobj.Type()) { 202 if tr.verbose { 203 fmt.Fprintf(os.Stderr, "%s not assignable to %s\n", yt, xobj.Type()) 204 } 205 return false 206 } 207 208 // A wildcard matches any expression. 209 // If it appears multiple times in the pattern, it must match 210 // the same expression each time. 211 if old, ok := tr.env[name]; ok { 212 // found existing binding 213 tr.allowWildcards = false 214 r := tr.matchExpr(old, y) 215 if tr.verbose { 216 fmt.Fprintf(os.Stderr, "%t secondary match, primary was %s\n", 217 r, astString(tr.fset, old)) 218 } 219 tr.allowWildcards = true 220 return r 221 } 222 223 if tr.verbose { 224 fmt.Fprintf(os.Stderr, "primary match\n") 225 } 226 227 tr.env[name] = y // record binding 228 return true 229} 230 231// -- utilities -------------------------------------------------------- 232 233func unparen(e ast.Expr) ast.Expr { return astutil.Unparen(e) } 234 235// isRef returns the object referred to by this (possibly qualified) 236// identifier, or nil if the node is not a referring identifier. 237func isRef(n ast.Node, info *types.Info) types.Object { 238 switch n := n.(type) { 239 case *ast.Ident: 240 return info.Uses[n] 241 242 case *ast.SelectorExpr: 243 if _, ok := info.Selections[n]; !ok { 244 // qualified ident 245 return info.Uses[n.Sel] 246 } 247 } 248 return nil 249} 250