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

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