Debian Codegraph @

pattern/match.go

raw
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 "BREAK": Token(token.BREAK),
59 "CONTINUE": Token(token.CONTINUE),
60 "GOTO": Token(token.GOTO),
61 "FALLTHROUGH": Token(token.FALLTHROUGH),
62 }
63
64 func maybeToken(node Node) (Node, bool) {
65 if node, ok := node.(String); ok {
66 if tok, ok := tokensByString[string(node)]; ok {
67 return tok, true
68 }
69 return node, false
70 }
71 return node, false
72 }
73
74 func isNil(v any) bool {
75 if v == nil {
76 return true
77 }
78 if _, ok := v.(Nil); ok {
79 return true
80 }
81 return false
82 }
83
84 type matcher interface {
85 Match(*Matcher, any) (any, bool)
86 }
87
88 type State = map[string]any
89
90 type Matcher struct {
91 TypesInfo *types.Info
92 State State
93
94 bindingsMapping []string
95
96 setBindings []uint64
97 }
98
99 func (m *Matcher) set(b Binding, value any) {
100 m.State[b.Name] = value
101 m.setBindings[len(m.setBindings)-1] |= 1 << b.idx
102 }
103
104 func (m *Matcher) push() {
105 m.setBindings = append(m.setBindings, 0)
106 }
107
108 func (m *Matcher) pop() {
109 set := m.setBindings[len(m.setBindings)-1]
110 if set != 0 {
111 for i := 0; i < len(m.bindingsMapping); i++ {
112 if (set & (1 << i)) != 0 {
113 key := m.bindingsMapping[i]
114 delete(m.State, key)
115 }
116 }
117 }
118 m.setBindings = m.setBindings[:len(m.setBindings)-1]
119 }
120
121 func (m *Matcher) merge() {
122 m.setBindings = m.setBindings[:len(m.setBindings)-1]
123 }
124
125 func (m *Matcher) Match(a Pattern, b ast.Node) bool {
126 m.bindingsMapping = a.Bindings
127 m.State = State{}
128 m.push()
129 _, ok := match(m, a.Root, b)
130 m.merge()
131 if len(m.setBindings) != 0 {
132 panic(fmt.Sprintf("%d entries left on the stack, expected none", len(m.setBindings)))
133 }
134 return ok
135 }
136
137 func Match(a Pattern, b ast.Node) (*Matcher, bool) {
138 m := &Matcher{}
139 ret := m.Match(a, b)
140 return m, ret
141 }
142
143 // Match two items, which may be (Node, AST) or (AST, AST)
144 func match(m *Matcher, l, r any) (any, bool) {
145 if _, ok := r.(Node); ok {
146 panic("Node mustn't be on right side of match")
147 }
148
149 switch l := l.(type) {
150 case *ast.ParenExpr:
151 return match(m, l.X, r)
152 case *ast.ExprStmt:
153 return match(m, l.X, r)
154 case *ast.DeclStmt:
155 return match(m, l.Decl, r)
156 case *ast.LabeledStmt:
157 return match(m, l.Stmt, r)
158 case *ast.BlockStmt:
159 return match(m, l.List, r)
160 case *ast.FieldList:
161 if l == nil {
162 return match(m, nil, r)
163 } else {
164 return match(m, l.List, r)
165 }
166 }
167
168 switch r := r.(type) {
169 case *ast.ParenExpr:
170 return match(m, l, r.X)
171 case *ast.ExprStmt:
172 return match(m, l, r.X)
173 case *ast.DeclStmt:
174 return match(m, l, r.Decl)
175 case *ast.LabeledStmt:
176 return match(m, l, r.Stmt)
177 case *ast.BlockStmt:
178 if r == nil {
179 return match(m, l, nil)
180 }
181 return match(m, l, r.List)
182 case *ast.FieldList:
183 if r == nil {
184 return match(m, l, nil)
185 }
186 return match(m, l, r.List)
187 case *ast.BasicLit:
188 if r == nil {
189 return match(m, l, nil)
190 }
191 }
192
193 if l, ok := l.(matcher); ok {
194 return l.Match(m, r)
195 }
196
197 if l, ok := l.(Node); ok {
198 // Matching of pattern with concrete value
199 return matchNodeAST(m, l, r)
200 }
201
202 if l == nil || r == nil {
203 return nil, l == r
204 }
205
206 {
207 ln, ok1 := l.(ast.Node)
208 rn, ok2 := r.(ast.Node)
209 if ok1 && ok2 {
210 return matchAST(m, ln, rn)
211 }
212 }
213
214 {
215 obj, ok := l.(types.Object)
216 if ok {
217 switch r := r.(type) {
218 case *ast.Ident:
219 return obj, obj == m.TypesInfo.ObjectOf(r)
220 case *ast.SelectorExpr:
221 return obj, obj == m.TypesInfo.ObjectOf(r.Sel)
222 default:
223 return obj, false
224 }
225 }
226 }
227
228 // TODO(dh): the three blocks handling slices can be combined into a single block if we use reflection
229
230 {
231 ln, ok1 := l.([]ast.Expr)
232 rn, ok2 := r.([]ast.Expr)
233 if ok1 || ok2 {
234 if ok1 && !ok2 {
235 cast, ok := r.(ast.Expr)
236 if !ok {
237 return nil, false
238 }
239 rn = []ast.Expr{cast}
240 } else if !ok1 && ok2 {
241 cast, ok := l.(ast.Expr)
242 if !ok {
243 return nil, false
244 }
245 ln = []ast.Expr{cast}
246 }
247
248 if len(ln) != len(rn) {
249 return nil, false
250 }
251 for i, ll := range ln {
252 if _, ok := match(m, ll, rn[i]); !ok {
253 return nil, false
254 }
255 }
256 return r, true
257 }
258 }
259
260 {
261 ln, ok1 := l.([]ast.Stmt)
262 rn, ok2 := r.([]ast.Stmt)
263 if ok1 || ok2 {
264 if ok1 && !ok2 {
265 cast, ok := r.(ast.Stmt)
266 if !ok {
267 return nil, false
268 }
269 rn = []ast.Stmt{cast}
270 } else if !ok1 && ok2 {
271 cast, ok := l.(ast.Stmt)
272 if !ok {
273 return nil, false
274 }
275 ln = []ast.Stmt{cast}
276 }
277
278 if len(ln) != len(rn) {
279 return nil, false
280 }
281 for i, ll := range ln {
282 if _, ok := match(m, ll, rn[i]); !ok {
283 return nil, false
284 }
285 }
286 return r, true
287 }
288 }
289
290 {
291 ln, ok1 := l.([]*ast.Field)
292 rn, ok2 := r.([]*ast.Field)
293 if ok1 || ok2 {
294 if ok1 && !ok2 {
295 cast, ok := r.(*ast.Field)
296 if !ok {
297 return nil, false
298 }
299 rn = []*ast.Field{cast}
300 } else if !ok1 && ok2 {
301 cast, ok := l.(*ast.Field)
302 if !ok {
303 return nil, false
304 }
305 ln = []*ast.Field{cast}
306 }
307
308 if len(ln) != len(rn) {
309 return nil, false
310 }
311 for i, ll := range ln {
312 if _, ok := match(m, ll, rn[i]); !ok {
313 return nil, false
314 }
315 }
316 return r, true
317 }
318 }
319
320 return nil, false
321 }
322
323 // Match a Node with an AST node
324 func matchNodeAST(m *Matcher, a Node, b any) (any, bool) {
325 switch b := b.(type) {
326 case []ast.Stmt:
327 // 'a' is not a List or we'd be using its Match
328 // implementation.
329
330 if len(b) != 1 {
331 return nil, false
332 }
333 return match(m, a, b[0])
334 case []ast.Expr:
335 // 'a' is not a List or we'd be using its Match
336 // implementation.
337
338 if len(b) != 1 {
339 return nil, false
340 }
341 return match(m, a, b[0])
342 case []*ast.Field:
343 // 'a' is not a List or we'd be using its Match
344 // implementation
345 if len(b) != 1 {
346 return nil, false
347 }
348 return match(m, a, b[0])
349 case ast.Node:
350 ra := reflect.ValueOf(a)
351 rb := reflect.ValueOf(b).Elem()
352
353 if ra.Type().Name() != rb.Type().Name() {
354 return nil, false
355 }
356
357 for i := 0; i < ra.NumField(); i++ {
358 af := ra.Field(i)
359 fieldName := ra.Type().Field(i).Name
360 bf := rb.FieldByName(fieldName)
361 if (bf == reflect.Value{}) {
362 panic(fmt.Sprintf("internal error: could not find field %s in type %t when comparing with %T", fieldName, b, a))
363 }
364 ai := af.Interface()
365 bi := bf.Interface()
366 if ai == nil {
367 return b, bi == nil
368 }
369 if _, ok := match(m, ai.(Node), bi); !ok {
370 return b, false
371 }
372 }
373 return b, true
374 case nil:
375 return nil, a == Nil{}
376 case string, token.Token:
377 // 'a' can't be a String, Token, or Binding or we'd be using their Match implementations.
378 return nil, false
379 default:
380 panic(fmt.Sprintf("unhandled type %T", b))
381 }
382 }
383
384 // Match two AST nodes
385 func matchAST(m *Matcher, a, b ast.Node) (any, bool) {
386 ra := reflect.ValueOf(a)
387 rb := reflect.ValueOf(b)
388
389 if ra.Type() != rb.Type() {
390 return nil, false
391 }
392 if ra.IsNil() || rb.IsNil() {
393 return rb, ra.IsNil() == rb.IsNil()
394 }
395
396 ra = ra.Elem()
397 rb = rb.Elem()
398 for i := 0; i < ra.NumField(); i++ {
399 af := ra.Field(i)
400 bf := rb.Field(i)
401 if af.Type() == rtTokPos || af.Type() == rtObject || af.Type() == rtCommentGroup {
402 continue
403 }
404
405 switch af.Kind() {
406 case reflect.Slice:
407 if af.Len() != bf.Len() {
408 return nil, false
409 }
410 for j := 0; j < af.Len(); j++ {
411 if _, ok := match(m, af.Index(j).Interface().(ast.Node), bf.Index(j).Interface().(ast.Node)); !ok {
412 return nil, false
413 }
414 }
415 case reflect.String:
416 if af.String() != bf.String() {
417 return nil, false
418 }
419 case reflect.Int:
420 if af.Int() != bf.Int() {
421 return nil, false
422 }
423 case reflect.Bool:
424 if af.Bool() != bf.Bool() {
425 return nil, false
426 }
427 case reflect.Pointer, reflect.Interface:
428 if _, ok := match(m, af.Interface(), bf.Interface()); !ok {
429 return nil, false
430 }
431 default:
432 panic(fmt.Sprintf("internal error: unhandled kind %s (%T)", af.Kind(), af.Interface()))
433 }
434 }
435 return b, true
436 }
437
438 func (b Binding) Match(m *Matcher, node any) (any, bool) {
439 if isNil(b.Node) {
440 v, ok := m.State[b.Name]
441 if ok {
442 // Recall value
443 return match(m, v, node)
444 }
445 // Matching anything
446 b.Node = Any{}
447 }
448
449 // Store value
450 if _, ok := m.State[b.Name]; ok {
451 panic(fmt.Sprintf("binding already created: %s", b.Name))
452 }
453 new, ret := match(m, b.Node, node)
454 if ret {
455 m.set(b, new)
456 }
457 return new, ret
458 }
459
460 func (Any) Match(m *Matcher, node any) (any, bool) {
461 return node, true
462 }
463
464 func (l List) Match(m *Matcher, node any) (any, bool) {
465 v := reflect.ValueOf(node)
466 if v.Kind() == reflect.Slice {
467 if isNil(l.Head) {
468 return node, v.Len() == 0
469 }
470 if v.Len() == 0 {
471 return nil, false
472 }
473 // OPT(dh): don't check the entire tail if head didn't match
474 _, ok1 := match(m, l.Head, v.Index(0).Interface())
475 _, ok2 := match(m, l.Tail, v.Slice(1, v.Len()).Interface())
476 return node, ok1 && ok2
477 }
478 // Our empty list does not equal an untyped Go nil. This way, we can
479 // tell apart an if with no else and an if with an empty else.
480 return nil, false
481 }
482
483 func (s String) Match(m *Matcher, node any) (any, bool) {
484 switch o := node.(type) {
485 case token.Token:
486 if tok, ok := maybeToken(s); ok {
487 return match(m, tok, node)
488 }
489 return nil, false
490 case string:
491 return o, string(s) == o
492 case types.TypeAndValue:
493 return o, o.Value != nil && o.Value.String() == string(s)
494 default:
495 return nil, false
496 }
497 }
498
499 func (tok Token) Match(m *Matcher, node any) (any, bool) {
500 o, ok := node.(token.Token)
501 if !ok {
502 return nil, false
503 }
504 return o, token.Token(tok) == o
505 }
506
507 func (Nil) Match(m *Matcher, node any) (any, bool) {
508 if isNil(node) {
509 return nil, true
510 }
511 v := reflect.ValueOf(node)
512 switch v.Kind() {
513 case reflect.Chan, reflect.Func, reflect.Interface, reflect.Map, reflect.Pointer, reflect.Slice:
514 return nil, v.IsNil()
515 default:
516 return nil, false
517 }
518 }
519
520 func (builtin Builtin) Match(m *Matcher, node any) (any, bool) {
521 r, ok := match(m, Ident(builtin), node)
522 if !ok {
523 return nil, false
524 }
525 ident := r.(*ast.Ident)
526 obj := m.TypesInfo.ObjectOf(ident)
527 if obj != types.Universe.Lookup(ident.Name) {
528 return nil, false
529 }
530 return ident, true
531 }
532
533 func (obj Object) Match(m *Matcher, node any) (any, bool) {
534 r, ok := match(m, Ident(obj), node)
535 if !ok {
536 return nil, false
537 }
538 ident := r.(*ast.Ident)
539
540 id := m.TypesInfo.ObjectOf(ident)
541 _, ok = match(m, obj.Name, ident.Name)
542 return id, ok
543 }
544
545 func (fn Symbol) Match(m *Matcher, node any) (any, bool) {
546 var name string
547 var obj types.Object
548
549 base := []Node{
550 Ident{Any{}},
551 SelectorExpr{Any{}, Any{}},
552 }
553 p := Or{
554 Nodes: append(base,
555 IndexExpr{Or{Nodes: base}, Any{}},
556 IndexListExpr{Or{Nodes: base}, Any{}})}
557
558 r, ok := match(m, p, node)
559 if !ok {
560 return nil, false
561 }
562
563 fun := r.(ast.Expr)
564 switch idx := fun.(type) {
565 case *ast.IndexExpr:
566 fun = idx.X
567 case *ast.IndexListExpr:
568 fun = idx.X
569 }
570
571 switch fun := ast.Unparen(fun).(type) {
572 case *ast.Ident:
573 obj = m.TypesInfo.ObjectOf(fun)
574 case *ast.SelectorExpr:
575 obj = m.TypesInfo.ObjectOf(fun.Sel)
576 default:
577 panic("unreachable")
578 }
579 switch obj := obj.(type) {
580 case *types.Func:
581 // OPT(dh): optimize this similar to code.FuncName
582 name = obj.FullName()
583 case *types.Builtin:
584 name = obj.Name()
585 case *types.TypeName:
586 origObj := obj
587 for {
588 if obj.Parent() != obj.Pkg().Scope() {
589 return nil, false
590 }
591 name = types.TypeString(obj.Type(), nil)
592 _, ok = match(m, fn.Name, name)
593 if ok || !obj.IsAlias() {
594 return origObj, ok
595 } else {
596 // FIXME(dh): we should peel away one layer of alias at a time; this is blocked on
597 // github.com/golang/go/issues/66559
598 switch typ := types.Unalias(obj.Type()).(type) {
599 case interface{ Obj() *types.TypeName }:
600 obj = typ.Obj()
601 case *types.Basic:
602 return match(m, fn.Name, typ.Name())
603 default:
604 return nil, false
605 }
606 }
607 }
608 case *types.Const, *types.Var:
609 if obj.Pkg() == nil {
610 return nil, false
611 }
612 if obj.Parent() != obj.Pkg().Scope() {
613 return nil, false
614 }
615 name = fmt.Sprintf("%s.%s", obj.Pkg().Path(), obj.Name())
616 default:
617 return nil, false
618 }
619
620 _, ok = match(m, fn.Name, name)
621 return obj, ok
622 }
623
624 func (or Or) Match(m *Matcher, node any) (any, bool) {
625 for _, opt := range or.Nodes {
626 m.push()
627 if ret, ok := match(m, opt, node); ok {
628 m.merge()
629 return ret, true
630 } else {
631 m.pop()
632 }
633 }
634 return nil, false
635 }
636
637 func (not Not) Match(m *Matcher, node any) (any, bool) {
638 _, ok := match(m, not.Node, node)
639 if ok {
640 return nil, false
641 }
642 return node, true
643 }
644
645 var integerLiteralQ = MustParse(`(Or (BasicLit "INT" _) (UnaryExpr (Or "+" "-") (IntegerLiteral _)))`)
646
647 func (lit IntegerLiteral) Match(m *Matcher, node any) (any, bool) {
648 matched, ok := match(m, integerLiteralQ.Root, node)
649 if !ok {
650 return nil, false
651 }
652 tv, ok := m.TypesInfo.Types[matched.(ast.Expr)]
653 if !ok {
654 return nil, false
655 }
656 if tv.Value == nil {
657 return nil, false
658 }
659 _, ok = match(m, lit.Value, tv)
660 return matched, ok
661 }
662
663 func (texpr TrulyConstantExpression) Match(m *Matcher, node any) (any, bool) {
664 expr, ok := node.(ast.Expr)
665 if !ok {
666 return nil, false
667 }
668 tv, ok := m.TypesInfo.Types[expr]
669 if !ok {
670 return nil, false
671 }
672 if tv.Value == nil {
673 return nil, false
674 }
675 truly := true
676 ast.Inspect(expr, func(node ast.Node) bool {
677 if _, ok := node.(*ast.Ident); ok {
678 truly = false
679 return false
680 }
681 return true
682 })
683 if !truly {
684 return nil, false
685 }
686 _, ok = match(m, texpr.Value, tv)
687 return expr, ok
688 }
689
690 var (
691 // Types of fields in go/ast structs that we want to skip
692 rtTokPos = reflect.TypeFor[token.Pos]()
693 //lint:ignore SA1019 It's deprecated, but we still want to skip the field.
694 rtObject = reflect.TypeFor[*ast.Object]()
695 rtCommentGroup = reflect.TypeFor[*ast.CommentGroup]()
696 )
697
698 var (
699 _ matcher = Binding{}
700 _ matcher = Any{}
701 _ matcher = List{}
702 _ matcher = String("")
703 _ matcher = Token(0)
704 _ matcher = Nil{}
705 _ matcher = Builtin{}
706 _ matcher = Object{}
707 _ matcher = Symbol{}
708 _ matcher = Or{}
709 _ matcher = Not{}
710 _ matcher = IntegerLiteral{}
711 _ matcher = TrulyConstantExpression{}
712 )