ast.go raw
1 //
2 // Copyright 2024 CloudWeGo Authors
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16
17 package expr
18
19 import (
20 "fmt"
21 )
22
23 // Type is tyep expression type.
24 type Type int
25
26 const (
27 // CONST indicates that the expression is a constant.
28 CONST Type = iota
29
30 // TERM indicates that the expression is a Term reference.
31 TERM
32
33 // EXPR indicates that the expression is a unary or binary expression.
34 EXPR
35 )
36
37 var typeNames = map[Type]string{
38 EXPR: "Expr",
39 TERM: "Term",
40 CONST: "Const",
41 }
42
43 // String returns the string representation of a Type.
44 func (self Type) String() string {
45 if v, ok := typeNames[self]; ok {
46 return v
47 } else {
48 return fmt.Sprintf("expr.Type(%d)", self)
49 }
50 }
51
52 // Operator represents an operation to perform when Type is EXPR.
53 type Operator uint8
54
55 const (
56 // ADD performs "Add Expr.Left and Expr.Right".
57 ADD Operator = iota
58
59 // SUB performs "Subtract Expr.Left by Expr.Right".
60 SUB
61
62 // MUL performs "Multiply Expr.Left by Expr.Right".
63 MUL
64
65 // DIV performs "Divide Expr.Left by Expr.Right".
66 DIV
67
68 // MOD performs "Modulo Expr.Left by Expr.Right".
69 MOD
70
71 // AND performs "Bitwise AND Expr.Left and Expr.Right".
72 AND
73
74 // OR performs "Bitwise OR Expr.Left and Expr.Right".
75 OR
76
77 // XOR performs "Bitwise XOR Expr.Left and Expr.Right".
78 XOR
79
80 // SHL performs "Bitwise Shift Expr.Left to the Left by Expr.Right Bits".
81 SHL
82
83 // SHR performs "Bitwise Shift Expr.Left to the Right by Expr.Right Bits".
84 SHR
85
86 // POW performs "Raise Expr.Left to the power of Expr.Right"
87 POW
88
89 // NOT performs "Bitwise Invert Expr.Left".
90 NOT
91
92 // NEG performs "Negate Expr.Left".
93 NEG
94 )
95
96 var operatorNames = map[Operator]string{
97 ADD: "Add",
98 SUB: "Subtract",
99 MUL: "Multiply",
100 DIV: "Divide",
101 MOD: "Modulo",
102 AND: "And",
103 OR: "Or",
104 XOR: "ExclusiveOr",
105 SHL: "ShiftLeft",
106 SHR: "ShiftRight",
107 POW: "Power",
108 NOT: "Invert",
109 NEG: "Negate",
110 }
111
112 // String returns the string representation of a Type.
113 func (self Operator) String() string {
114 if v, ok := operatorNames[self]; ok {
115 return v
116 } else {
117 return fmt.Sprintf("expr.Operator(%d)", self)
118 }
119 }
120
121 // Expr represents an expression node.
122 type Expr struct {
123 Type Type
124 Term Term
125 Op Operator
126 Left *Expr
127 Right *Expr
128 Const int64
129 }
130
131 // Ref creates an expression from a Term.
132 func Ref(t Term) (p *Expr) {
133 p = newExpression()
134 p.Term = t
135 p.Type = TERM
136 return
137 }
138
139 // Int creates an expression from an integer.
140 func Int(v int64) (p *Expr) {
141 p = newExpression()
142 p.Type = CONST
143 p.Const = v
144 return
145 }
146
147 func (self *Expr) clear() {
148 if self.Term != nil {
149 self.Term.Free()
150 }
151 if self.Left != nil {
152 self.Left.Free()
153 }
154 if self.Right != nil {
155 self.Right.Free()
156 }
157 }
158
159 // Free returns the Expr into pool.
160 // Any operation performed after Free is undefined behavior.
161 func (self *Expr) Free() {
162 self.clear()
163 freeExpression(self)
164 }
165
166 // Evaluate evaluates the expression into an integer.
167 // It also implements the Term interface.
168 func (self *Expr) Evaluate() (int64, error) {
169 switch self.Type {
170 case EXPR:
171 return self.eval()
172 case TERM:
173 return self.Term.Evaluate()
174 case CONST:
175 return self.Const, nil
176 default:
177 panic("invalid expression type: " + self.Type.String())
178 }
179 }
180
181 /** Expression Combinator **/
182
183 func combine(a *Expr, op Operator, b *Expr) (r *Expr) {
184 r = newExpression()
185 r.Op = op
186 r.Type = EXPR
187 r.Left = a
188 r.Right = b
189 return
190 }
191
192 func (self *Expr) Add(v *Expr) *Expr { return combine(self, ADD, v) }
193 func (self *Expr) Sub(v *Expr) *Expr { return combine(self, SUB, v) }
194 func (self *Expr) Mul(v *Expr) *Expr { return combine(self, MUL, v) }
195 func (self *Expr) Div(v *Expr) *Expr { return combine(self, DIV, v) }
196 func (self *Expr) Mod(v *Expr) *Expr { return combine(self, MOD, v) }
197 func (self *Expr) And(v *Expr) *Expr { return combine(self, AND, v) }
198 func (self *Expr) Or(v *Expr) *Expr { return combine(self, OR, v) }
199 func (self *Expr) Xor(v *Expr) *Expr { return combine(self, XOR, v) }
200 func (self *Expr) Shl(v *Expr) *Expr { return combine(self, SHL, v) }
201 func (self *Expr) Shr(v *Expr) *Expr { return combine(self, SHR, v) }
202 func (self *Expr) Pow(v *Expr) *Expr { return combine(self, POW, v) }
203 func (self *Expr) Not() *Expr { return combine(self, NOT, nil) }
204 func (self *Expr) Neg() *Expr { return combine(self, NEG, nil) }
205
206 /** Expression Evaluator **/
207
208 var binaryEvaluators = [256]func(int64, int64) (int64, error){
209 ADD: func(a, b int64) (int64, error) { return a + b, nil },
210 SUB: func(a, b int64) (int64, error) { return a - b, nil },
211 MUL: func(a, b int64) (int64, error) { return a * b, nil },
212 DIV: idiv,
213 MOD: imod,
214 AND: func(a, b int64) (int64, error) { return a & b, nil },
215 OR: func(a, b int64) (int64, error) { return a | b, nil },
216 XOR: func(a, b int64) (int64, error) { return a ^ b, nil },
217 SHL: func(a, b int64) (int64, error) { return a << b, nil },
218 SHR: func(a, b int64) (int64, error) { return a >> b, nil },
219 POW: ipow,
220 }
221
222 func (self *Expr) eval() (int64, error) {
223 var lhs int64
224 var rhs int64
225 var err error
226 var vfn func(int64, int64) (int64, error)
227
228 /* evaluate LHS */
229 if lhs, err = self.Left.Evaluate(); err != nil {
230 return 0, err
231 }
232
233 /* check for unary operators */
234 switch self.Op {
235 case NOT:
236 return self.unaryNot(lhs)
237 case NEG:
238 return self.unaryNeg(lhs)
239 }
240
241 /* check for operators */
242 if vfn = binaryEvaluators[self.Op]; vfn == nil {
243 panic("invalid operator: " + self.Op.String())
244 }
245
246 /* must be a binary expression */
247 if self.Right == nil {
248 panic("operator " + self.Op.String() + " is a binary operator")
249 }
250
251 /* evaluate RHS, and call the operator */
252 if rhs, err = self.Right.Evaluate(); err != nil {
253 return 0, err
254 } else {
255 return vfn(lhs, rhs)
256 }
257 }
258
259 func (self *Expr) unaryNot(v int64) (int64, error) {
260 if self.Right == nil {
261 return ^v, nil
262 } else {
263 panic("operator Invert is an unary operator")
264 }
265 }
266
267 func (self *Expr) unaryNeg(v int64) (int64, error) {
268 if self.Right == nil {
269 return -v, nil
270 } else {
271 panic("operator Negate is an unary operator")
272 }
273 }
274