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