-
Notifications
You must be signed in to change notification settings - Fork 153
/
pattern.go
104 lines (87 loc) · 2.44 KB
/
pattern.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package plan
const AnyKind = "*** any procedure kind ***"
// Pattern represents an operator tree pattern
// It can match itself against a query plan
type Pattern interface {
Root() ProcedureKind
Match(Node) bool
}
// Pat returns a pattern that can match a plan node with the given ProcedureKind
// and whose predecessors match the given predecessor patterns.
//
// For example, to construct a pattern that matches a join followed by a sum:
//
// sum
// |
// |X| <=> join(A, B) |> sum() <=> Pat(SumKind, Pat(JoinKind, Any(), Any()))
// / \
// A B
func Pat(kind ProcedureKind, predecessors ...Pattern) Pattern {
return &OneKindPattern{
kind: kind,
predecessors: predecessors,
}
}
// PhysPat returns a pattern that matches a physical plan node with the given
// ProcedureKind and whose predecessors match the given predecessor patterns.
func PhysPat(kind ProcedureKind, predecessors ...Pattern) Pattern {
return PhysicalOneKindPattern{
pattern: Pat(kind, predecessors...),
}
}
// PhysicalOneKindPattern matches a physical operator pattern
type PhysicalOneKindPattern struct {
pattern Pattern
}
func (p PhysicalOneKindPattern) Root() ProcedureKind {
return p.pattern.Root()
}
func (p PhysicalOneKindPattern) Match(node Node) bool {
_, ok := node.(*PhysicalPlanNode)
return ok && p.pattern.Match(node)
}
// Any returns a pattern that matches anything.
func Any() Pattern {
return &AnyPattern{}
}
// OneKindPattern matches a specified procedure with a predecessor pattern
//
// ProcedureKind
// / | ... \
// pattern1 pattern2 ... patternK
type OneKindPattern struct {
kind ProcedureKind
predecessors []Pattern
}
func (okp OneKindPattern) Root() ProcedureKind {
return okp.kind
}
func (okp OneKindPattern) Match(node Node) bool {
if node.Kind() != okp.kind {
return false
}
if len(okp.predecessors) != len(node.Predecessors()) {
return false
}
// Check that each predecessor does not have other successors
for _, pred := range node.Predecessors() {
if len(pred.Successors()) != 1 {
return false
}
}
// Recursively match each predecessor
for i, pattern := range okp.predecessors {
if !pattern.Match(node.Predecessors()[i]) {
return false
}
}
return true
}
// AnyPattern describes (and matches) any plan node
type AnyPattern struct{}
func (AnyPattern) Root() ProcedureKind {
return AnyKind
}
func (AnyPattern) Match(node Node) bool {
return true
}