match.go

Documentation: golang.org/x/tools/refactor/eg

     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
View as plain text