.config/coc/extensions/coc-go-data/tools/pkg/mod/honnef.co/go/tools@v0.0.1-2020.1.5/pattern/match.go

   1 package pattern
   2
   3 import (
   4         "fmt"
   5         "go/ast"
   6         "go/token"
   7         "go/types"
   8         "reflect"
   9
  10         "honnef.co/go/tools/lint"
  11 )
  12
  13 var tokensByString = map[string]Token{
  14         "INT":    Token(token.INT),
  15         "FLOAT":  Token(token.FLOAT),
  16         "IMAG":   Token(token.IMAG),
  17         "CHAR":   Token(token.CHAR),
  18         "STRING": Token(token.STRING),
  19         "+":      Token(token.ADD),
  20         "-":      Token(token.SUB),
  21         "*":      Token(token.MUL),
  22         "/":      Token(token.QUO),
  23         "%":      Token(token.REM),
  24         "&":      Token(token.AND),
  25         "|":      Token(token.OR),
  26         "^":      Token(token.XOR),
  27         "<<":     Token(token.SHL),
  28         ">>":     Token(token.SHR),
  29         "&^":     Token(token.AND_NOT),
  30         "+=":     Token(token.ADD_ASSIGN),
  31         "-=":     Token(token.SUB_ASSIGN),
  32         "*=":     Token(token.MUL_ASSIGN),
  33         "/=":     Token(token.QUO_ASSIGN),
  34         "%=":     Token(token.REM_ASSIGN),
  35         "&=":     Token(token.AND_ASSIGN),
  36         "|=":     Token(token.OR_ASSIGN),
  37         "^=":     Token(token.XOR_ASSIGN),
  38         "<<=":    Token(token.SHL_ASSIGN),
  39         ">>=":    Token(token.SHR_ASSIGN),
  40         "&^=":    Token(token.AND_NOT_ASSIGN),
  41         "&&":     Token(token.LAND),
  42         "||":     Token(token.LOR),
  43         "<-":     Token(token.ARROW),
  44         "++":     Token(token.INC),
  45         "--":     Token(token.DEC),
  46         "==":     Token(token.EQL),
  47         "<":      Token(token.LSS),
  48         ">":      Token(token.GTR),
  49         "=":      Token(token.ASSIGN),
  50         "!":      Token(token.NOT),
  51         "!=":     Token(token.NEQ),
  52         "<=":     Token(token.LEQ),
  53         ">=":     Token(token.GEQ),
  54         ":=":     Token(token.DEFINE),
  55         "...":    Token(token.ELLIPSIS),
  56         "IMPORT": Token(token.IMPORT),
  57         "VAR":    Token(token.VAR),
  58         "TYPE":   Token(token.TYPE),
  59         "CONST":  Token(token.CONST),
  60 }
  61
  62 func maybeToken(node Node) (Node, bool) {
  63         if node, ok := node.(String); ok {
  64                 if tok, ok := tokensByString[string(node)]; ok {
  65                         return tok, true
  66                 }
  67                 return node, false
  68         }
  69         return node, false
  70 }
  71
  72 func isNil(v interface{}) bool {
  73         if v == nil {
  74                 return true
  75         }
  76         if _, ok := v.(Nil); ok {
  77                 return true
  78         }
  79         return false
  80 }
  81
  82 type matcher interface {
  83         Match(*Matcher, interface{}) (interface{}, bool)
  84 }
  85
  86 type State = map[string]interface{}
  87
  88 type Matcher struct {
  89         TypesInfo *types.Info
  90         State     State
  91 }
  92
  93 func (m *Matcher) fork() *Matcher {
  94         state := make(State, len(m.State))
  95         for k, v := range m.State {
  96                 state[k] = v
  97         }
  98         return &Matcher{
  99                 TypesInfo: m.TypesInfo,
 100                 State:     state,
 101         }
 102 }
 103
 104 func (m *Matcher) merge(mc *Matcher) {
 105         m.State = mc.State
 106 }
 107
 108 func (m *Matcher) Match(a Node, b ast.Node) bool {
 109         m.State = State{}
 110         _, ok := match(m, a, b)
 111         return ok
 112 }
 113
 114 func Match(a Node, b ast.Node) (*Matcher, bool) {
 115         m := &Matcher{}
 116         ret := m.Match(a, b)
 117         return m, ret
 118 }
 119
 120 // Match two items, which may be (Node, AST) or (AST, AST)
 121 func match(m *Matcher, l, r interface{}) (interface{}, bool) {
 122         if _, ok := r.(Node); ok {
 123                 panic("Node mustn't be on right side of match")
 124         }
 125
 126         switch l := l.(type) {
 127         case *ast.ParenExpr:
 128                 return match(m, l.X, r)
 129         case *ast.ExprStmt:
 130                 return match(m, l.X, r)
 131         case *ast.DeclStmt:
 132                 return match(m, l.Decl, r)
 133         case *ast.LabeledStmt:
 134                 return match(m, l.Stmt, r)
 135         case *ast.BlockStmt:
 136                 return match(m, l.List, r)
 137         case *ast.FieldList:
 138                 return match(m, l.List, r)
 139         }
 140
 141         switch r := r.(type) {
 142         case *ast.ParenExpr:
 143                 return match(m, l, r.X)
 144         case *ast.ExprStmt:
 145                 return match(m, l, r.X)
 146         case *ast.DeclStmt:
 147                 return match(m, l, r.Decl)
 148         case *ast.LabeledStmt:
 149                 return match(m, l, r.Stmt)
 150         case *ast.BlockStmt:
 151                 if r == nil {
 152                         return match(m, l, nil)
 153                 }
 154                 return match(m, l, r.List)
 155         case *ast.FieldList:
 156                 if r == nil {
 157                         return match(m, l, nil)
 158                 }
 159                 return match(m, l, r.List)
 160         case *ast.BasicLit:
 161                 if r == nil {
 162                         return match(m, l, nil)
 163                 }
 164         }
 165
 166         if l, ok := l.(matcher); ok {
 167                 return l.Match(m, r)
 168         }
 169
 170         if l, ok := l.(Node); ok {
 171                 // Matching of pattern with concrete value
 172                 return matchNodeAST(m, l, r)
 173         }
 174
 175         if l == nil || r == nil {
 176                 return nil, l == r
 177         }
 178
 179         {
 180                 ln, ok1 := l.(ast.Node)
 181                 rn, ok2 := r.(ast.Node)
 182                 if ok1 && ok2 {
 183                         return matchAST(m, ln, rn)
 184                 }
 185         }
 186
 187         {
 188                 obj, ok := l.(types.Object)
 189                 if ok {
 190                         switch r := r.(type) {
 191                         case *ast.Ident:
 192                                 return obj, obj == m.TypesInfo.ObjectOf(r)
 193                         case *ast.SelectorExpr:
 194                                 return obj, obj == m.TypesInfo.ObjectOf(r.Sel)
 195                         default:
 196                                 return obj, false
 197                         }
 198                 }
 199         }
 200
 201         {
 202                 ln, ok1 := l.([]ast.Expr)
 203                 rn, ok2 := r.([]ast.Expr)
 204                 if ok1 || ok2 {
 205                         if ok1 && !ok2 {
 206                                 rn = []ast.Expr{r.(ast.Expr)}
 207                         } else if !ok1 && ok2 {
 208                                 ln = []ast.Expr{l.(ast.Expr)}
 209                         }
 210
 211                         if len(ln) != len(rn) {
 212                                 return nil, false
 213                         }
 214                         for i, ll := range ln {
 215                                 if _, ok := match(m, ll, rn[i]); !ok {
 216                                         return nil, false
 217                                 }
 218                         }
 219                         return r, true
 220                 }
 221         }
 222
 223         {
 224                 ln, ok1 := l.([]ast.Stmt)
 225                 rn, ok2 := r.([]ast.Stmt)
 226                 if ok1 || ok2 {
 227                         if ok1 && !ok2 {
 228                                 rn = []ast.Stmt{r.(ast.Stmt)}
 229                         } else if !ok1 && ok2 {
 230                                 ln = []ast.Stmt{l.(ast.Stmt)}
 231                         }
 232
 233                         if len(ln) != len(rn) {
 234                                 return nil, false
 235                         }
 236                         for i, ll := range ln {
 237                                 if _, ok := match(m, ll, rn[i]); !ok {
 238                                         return nil, false
 239                                 }
 240                         }
 241                         return r, true
 242                 }
 243         }
 244
 245         {
 246                 ln, ok1 := l.([]*ast.Field)
 247                 rn, ok2 := r.([]*ast.Field)
 248                 if ok1 || ok2 {
 249                         if ok1 && !ok2 {
 250                                 rn = []*ast.Field{r.(*ast.Field)}
 251                         } else if !ok1 && ok2 {
 252                                 ln = []*ast.Field{l.(*ast.Field)}
 253                         }
 254
 255                         if len(ln) != len(rn) {
 256                                 return nil, false
 257                         }
 258                         for i, ll := range ln {
 259                                 if _, ok := match(m, ll, rn[i]); !ok {
 260                                         return nil, false
 261                                 }
 262                         }
 263                         return r, true
 264                 }
 265         }
 266
 267         panic(fmt.Sprintf("unsupported comparison: %T and %T", l, r))
 268 }
 269
 270 // Match a Node with an AST node
 271 func matchNodeAST(m *Matcher, a Node, b interface{}) (interface{}, bool) {
 272         switch b := b.(type) {
 273         case []ast.Stmt:
 274                 // 'a' is not a List or we'd be using its Match
 275                 // implementation.
 276
 277                 if len(b) != 1 {
 278                         return nil, false
 279                 }
 280                 return match(m, a, b[0])
 281         case []ast.Expr:
 282                 // 'a' is not a List or we'd be using its Match
 283                 // implementation.
 284
 285                 if len(b) != 1 {
 286                         return nil, false
 287                 }
 288                 return match(m, a, b[0])
 289         case ast.Node:
 290                 ra := reflect.ValueOf(a)
 291                 rb := reflect.ValueOf(b).Elem()
 292
 293                 if ra.Type().Name() != rb.Type().Name() {
 294                         return nil, false
 295                 }
 296
 297                 for i := 0; i < ra.NumField(); i++ {
 298                         af := ra.Field(i)
 299                         fieldName := ra.Type().Field(i).Name
 300                         bf := rb.FieldByName(fieldName)
 301                         if (bf == reflect.Value{}) {
 302                                 panic(fmt.Sprintf("internal error: could not find field %s in type %t when comparing with %T", fieldName, b, a))
 303                         }
 304                         ai := af.Interface()
 305                         bi := bf.Interface()
 306                         if ai == nil {
 307                                 return b, bi == nil
 308                         }
 309                         if _, ok := match(m, ai.(Node), bi); !ok {
 310                                 return b, false
 311                         }
 312                 }
 313                 return b, true
 314         case nil:
 315                 return nil, a == Nil{}
 316         default:
 317                 panic(fmt.Sprintf("unhandled type %T", b))
 318         }
 319 }
 320
 321 // Match two AST nodes
 322 func matchAST(m *Matcher, a, b ast.Node) (interface{}, bool) {
 323         ra := reflect.ValueOf(a)
 324         rb := reflect.ValueOf(b)
 325
 326         if ra.Type() != rb.Type() {
 327                 return nil, false
 328         }
 329         if ra.IsNil() || rb.IsNil() {
 330                 return rb, ra.IsNil() == rb.IsNil()
 331         }
 332
 333         ra = ra.Elem()
 334         rb = rb.Elem()
 335         for i := 0; i < ra.NumField(); i++ {
 336                 af := ra.Field(i)
 337                 bf := rb.Field(i)
 338                 if af.Type() == rtTokPos || af.Type() == rtObject || af.Type() == rtCommentGroup {
 339                         continue
 340                 }
 341
 342                 switch af.Kind() {
 343                 case reflect.Slice:
 344                         if af.Len() != bf.Len() {
 345                                 return nil, false
 346                         }
 347                         for j := 0; j < af.Len(); j++ {
 348                                 if _, ok := match(m, af.Index(j).Interface().(ast.Node), bf.Index(j).Interface().(ast.Node)); !ok {
 349                                         return nil, false
 350                                 }
 351                         }
 352                 case reflect.String:
 353                         if af.String() != bf.String() {
 354                                 return nil, false
 355                         }
 356                 case reflect.Int:
 357                         if af.Int() != bf.Int() {
 358                                 return nil, false
 359                         }
 360                 case reflect.Bool:
 361                         if af.Bool() != bf.Bool() {
 362                                 return nil, false
 363                         }
 364                 case reflect.Ptr, reflect.Interface:
 365                         if _, ok := match(m, af.Interface(), bf.Interface()); !ok {
 366                                 return nil, false
 367                         }
 368                 default:
 369                         panic(fmt.Sprintf("internal error: unhandled kind %s (%T)", af.Kind(), af.Interface()))
 370                 }
 371         }
 372         return b, true
 373 }
 374
 375 func (b Binding) Match(m *Matcher, node interface{}) (interface{}, bool) {
 376         if isNil(b.Node) {
 377                 v, ok := m.State[b.Name]
 378                 if ok {
 379                         // Recall value
 380                         return match(m, v, node)
 381                 }
 382                 // Matching anything
 383                 b.Node = Any{}
 384         }
 385
 386         // Store value
 387         if _, ok := m.State[b.Name]; ok {
 388                 panic(fmt.Sprintf("binding already created: %s", b.Name))
 389         }
 390         new, ret := match(m, b.Node, node)
 391         if ret {
 392                 m.State[b.Name] = new
 393         }
 394         return new, ret
 395 }
 396
 397 func (Any) Match(m *Matcher, node interface{}) (interface{}, bool) {
 398         return node, true
 399 }
 400
 401 func (l List) Match(m *Matcher, node interface{}) (interface{}, bool) {
 402         v := reflect.ValueOf(node)
 403         if v.Kind() == reflect.Slice {
 404                 if isNil(l.Head) {
 405                         return node, v.Len() == 0
 406                 }
 407                 if v.Len() == 0 {
 408                         return nil, false
 409                 }
 410                 // OPT(dh): don't check the entire tail if head didn't match
 411                 _, ok1 := match(m, l.Head, v.Index(0).Interface())
 412                 _, ok2 := match(m, l.Tail, v.Slice(1, v.Len()).Interface())
 413                 return node, ok1 && ok2
 414         }
 415         // Our empty list does not equal an untyped Go nil. This way, we can
 416         // tell apart an if with no else and an if with an empty else.
 417         return nil, false
 418 }
 419
 420 func (s String) Match(m *Matcher, node interface{}) (interface{}, bool) {
 421         switch o := node.(type) {
 422         case token.Token:
 423                 if tok, ok := maybeToken(s); ok {
 424                         return match(m, tok, node)
 425                 }
 426                 return nil, false
 427         case string:
 428                 return o, string(s) == o
 429         default:
 430                 return nil, false
 431         }
 432 }
 433
 434 func (tok Token) Match(m *Matcher, node interface{}) (interface{}, bool) {
 435         o, ok := node.(token.Token)
 436         if !ok {
 437                 return nil, false
 438         }
 439         return o, token.Token(tok) == o
 440 }
 441
 442 func (Nil) Match(m *Matcher, node interface{}) (interface{}, bool) {
 443         return nil, isNil(node)
 444 }
 445
 446 func (builtin Builtin) Match(m *Matcher, node interface{}) (interface{}, bool) {
 447         ident, ok := node.(*ast.Ident)
 448         if !ok {
 449                 return nil, false
 450         }
 451         obj := m.TypesInfo.ObjectOf(ident)
 452         if obj != types.Universe.Lookup(ident.Name) {
 453                 return nil, false
 454         }
 455         return match(m, builtin.Name, ident.Name)
 456 }
 457
 458 func (obj Object) Match(m *Matcher, node interface{}) (interface{}, bool) {
 459         ident, ok := node.(*ast.Ident)
 460         if !ok {
 461                 return nil, false
 462         }
 463
 464         id := m.TypesInfo.ObjectOf(ident)
 465         _, ok = match(m, obj.Name, ident.Name)
 466         return id, ok
 467 }
 468
 469 func (fn Function) Match(m *Matcher, node interface{}) (interface{}, bool) {
 470         var name string
 471         var obj types.Object
 472         switch node := node.(type) {
 473         case *ast.Ident:
 474                 obj = m.TypesInfo.ObjectOf(node)
 475                 switch obj := obj.(type) {
 476                 case *types.Func:
 477                         name = lint.FuncName(obj)
 478                 case *types.Builtin:
 479                         name = obj.Name()
 480                 default:
 481                         return nil, false
 482                 }
 483         case *ast.SelectorExpr:
 484                 var ok bool
 485                 obj, ok = m.TypesInfo.ObjectOf(node.Sel).(*types.Func)
 486                 if !ok {
 487                         return nil, false
 488                 }
 489                 name = lint.FuncName(obj.(*types.Func))
 490         default:
 491                 return nil, false
 492         }
 493         _, ok := match(m, fn.Name, name)
 494         return obj, ok
 495 }
 496
 497 func (or Or) Match(m *Matcher, node interface{}) (interface{}, bool) {
 498         for _, opt := range or.Nodes {
 499                 mc := m.fork()
 500                 if ret, ok := match(mc, opt, node); ok {
 501                         m.merge(mc)
 502                         return ret, true
 503                 }
 504         }
 505         return nil, false
 506 }
 507
 508 func (not Not) Match(m *Matcher, node interface{}) (interface{}, bool) {
 509         _, ok := match(m, not.Node, node)
 510         if ok {
 511                 return nil, false
 512         }
 513         return node, true
 514 }
 515
 516 var (
 517         // Types of fields in go/ast structs that we want to skip
 518         rtTokPos       = reflect.TypeOf(token.Pos(0))
 519         rtObject       = reflect.TypeOf((*ast.Object)(nil))
 520         rtCommentGroup = reflect.TypeOf((*ast.CommentGroup)(nil))
 521 )
 522
 523 var (
 524         _ matcher = Binding{}
 525         _ matcher = Any{}
 526         _ matcher = List{}
 527         _ matcher = String("")
 528         _ matcher = Token(0)
 529         _ matcher = Nil{}
 530         _ matcher = Builtin{}
 531         _ matcher = Object{}
 532         _ matcher = Function{}
 533         _ matcher = Or{}
 534         _ matcher = Not{}
 535 )