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