-
Notifications
You must be signed in to change notification settings - Fork 0
/
parser.go
388 lines (312 loc) · 8.99 KB
/
parser.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
package rule
import (
"context"
"fmt"
"go/scanner"
"go/token"
"strings"
"github.com/sado0823/go-kitx/kit/log"
)
var (
logger = log.NewHelper(log.WithFields(log.GetGlobal(), "pkg", "rule"))
)
type (
Parser struct {
ctx context.Context
sc scanner.Scanner
fSet *token.FileSet
file *token.File
expr string
streamV *stream
stageV *stage
option *option
}
option struct {
customFns map[string]CustomFn
}
WithOption func(*option)
)
func WithCustomFn(name string, fn CustomFn) WithOption {
return func(o *option) {
o.customFns[name] = fn
}
}
func doOptions(options ...WithOption) *option {
option := &option{
customFns: make(map[string]CustomFn),
}
for _, withOption := range options {
withOption(option)
}
return option
}
func Check(ctx context.Context, expr string, options ...WithOption) (err error) {
src := []byte(expr)
var s scanner.Scanner
fSet := token.NewFileSet()
file := fSet.AddFile("", fSet.Base(), len(src))
s.Init(file, src, nil /* no error handler */, scanner.ScanComments)
p := &Parser{ctx: ctx, sc: s, fSet: fSet, file: file, expr: expr, option: doOptions(options...)}
p.streamV, err = p.stream()
return err
}
func Do(ctx context.Context, expr string, params interface{}, options ...WithOption) (interface{}, error) {
parser, err := New(ctx, expr, options...)
if err != nil {
return nil, err
}
return parser.Eval(params)
}
func New(ctx context.Context, expr string, options ...WithOption) (parser *Parser, err error) {
src := []byte(expr)
var s scanner.Scanner
fSet := token.NewFileSet()
file := fSet.AddFile("", fSet.Base(), len(src))
s.Init(file, src, nil /* no error handler */, scanner.ScanComments)
p := &Parser{ctx: ctx, sc: s, fSet: fSet, file: file, expr: expr, option: doOptions(options...)}
p.streamV, err = p.stream()
if err != nil {
return nil, err
}
p.stageV, err = buildStage(p.streamV)
return p, err
}
func (p *Parser) Eval(params interface{}) (interface{}, error) {
return doStage(p.stageV, params)
}
func (p *Parser) stream() (ret *stream, err error) {
ret = new(stream)
ret.tokens, err = p.read()
ret.len = len(ret.tokens)
return ret, err
}
func (p *Parser) read() ([]Token, error) {
tokens := make([]Token, 0)
var (
beforeToken Token = new(tokenNull)
lParenCount = 0
rParenCount = 0
)
for {
pos, tok, lit := p.sc.Scan()
logger.Debugf("pos_o=%d pos=%s\t token=%#v\t token_str=%q\t lit=%q\n", pos, p.fSet.Position(pos), tok, tok.String(), lit)
if tok == token.EOF {
if !beforeToken.CanEOF() {
return nil, fmt.Errorf("%s can NOT be last", beforeToken.String())
}
break
}
if tok == token.COMMENT || tok == token.SEMICOLON {
continue
}
if tok == token.LPAREN {
lParenCount++
}
if tok == token.RPAREN {
rParenCount++
}
var (
symbol = UNKNOWN
parseToken Token
supported bool
parseTokenFn func(pos token.Pos, tok token.Token, lit string) (Token, error)
err error
)
if tok == token.IDENT {
if beforeToken.Symbol() == FUNC {
inputCustomFn, okInput := p.option.customFns[lit]
buildInCustomFn, okBuildIn := _buildInCustomFn[lit]
if !okInput && !okBuildIn {
return nil, fmt.Errorf("unknown func, name=%s, pos=%v", lit, pos)
}
tokenFn := beforeToken.(*tokenFunc)
tokenFn.lit = lit
if okInput {
tokenFn.value = inputCustomFn
continue
}
if okBuildIn {
tokenFn.value = buildInCustomFn
continue
}
}
// like `foo.`, `foo.bar.` , must be accessor
if beforeToken.Symbol() == PERIOD {
before := beforeToken.(*tokenIdent)
withPeriodStr := fmt.Sprintf("%s%s", before.lit, lit)
before.lit = withPeriodStr
before.value = withPeriodStr
continue
}
// parse bool
if strings.ToUpper(lit) == "TRUE" || strings.ToUpper(lit) == "FALSE" {
symbol = BOOL
goto symbolStep
}
}
// like `foo`, `bar` + `.`, must be accessor
if tok == token.PERIOD {
if beforeToken.Symbol() == IDENT {
before := beforeToken.(*tokenIdent)
withPeriodStr := fmt.Sprintf("%s.", before.lit)
before.lit = withPeriodStr
before.value = withPeriodStr
continue
}
}
// like `.1`, `.2` ... must be accessor and try to get data from array with array index (foo.bar.1)
if tok == token.FLOAT && strings.LastIndex(lit, ".") == 0 {
if beforeToken.Symbol() == IDENT {
before := beforeToken.(*tokenIdent)
withPeriodStr := fmt.Sprintf("%s%s", before.lit, lit)
before.lit = withPeriodStr
before.value = withPeriodStr
continue
}
}
if beforeToken.CanNext(&tokenNEGATE{}) == nil && tok == token.SUB {
symbol = NEGATE
goto symbolStep
}
symbol, supported = token2Symbol[tok]
if !supported {
return nil, fmt.Errorf("token2Symbol unsupported expr, token=%s\t lit=%s\t pos:%v", tok.String(), lit, p.fSet.Position(pos))
}
symbolStep:
parseTokenFn, supported = symbol2Token[symbol]
if !supported {
return nil, fmt.Errorf("symbol2Token unsupported expr, token=%s\t lit=%s\t pos:%v", tok.String(), lit, p.fSet.Position(pos))
}
parseToken, err = parseTokenFn(pos, tok, lit)
if err != nil {
return nil, err
}
// check if current is valid
err = beforeToken.CanNext(parseToken)
if err != nil {
return nil, err
}
tokens = append(tokens, parseToken)
beforeToken = parseToken
}
if lParenCount != rParenCount {
return nil, fmt.Errorf("check got %d left paren but %d right paren, should be equal", lParenCount, rParenCount)
}
return tokens, nil
}
func buildStage(stream *stream) (*stage, error) {
if !stream.hasNext() {
return nil, nil
}
stage, err := planSeparator(stream)
if err != nil {
return nil, err
}
reorderStages(stage)
return stage, nil
}
// During stage planning, stages of equal precedence are parsed such that they'll be evaluated in reverse order.
//
// For commutative operators like "+" or "-", it's no big deal.
// But for order-specific operators, it ruins the expected result.
func reorderStages(rootStage *stage) {
if rootStage == nil {
return
}
// traverse every rightStage until we find multiples in a row of the same precedence.
var identicalPrecedences []*stage
var currentStage, nextStage *stage
var precedence, currentPrecedence int
nextStage = rootStage
precedence = symbolPrecedence(rootStage.symbol.Symbol())
for nextStage != nil {
currentStage = nextStage
nextStage = currentStage.right
// left depth first, since this entire method only looks for precedences down the right side of the tree
if currentStage.left != nil {
reorderStages(currentStage.left)
}
currentPrecedence = symbolPrecedence(currentStage.symbol.Symbol())
if currentPrecedence == precedence {
identicalPrecedences = append(identicalPrecedences, currentStage)
continue
}
// precedence break.
// See how many in a row we had, and reorder if there's more than one.
if len(identicalPrecedences) > 1 {
mirrorStageSubtree(identicalPrecedences)
}
identicalPrecedences = []*stage{currentStage}
precedence = currentPrecedence
}
if len(identicalPrecedences) > 1 {
mirrorStageSubtree(identicalPrecedences)
}
}
// Performs a "mirror" on a subtree of stages.
//
// This mirror functionally inverts the order of execution for all members of the [stages] list.
// That list is assumed to be a root-to-leaf (ordered) list of evaluation stages,
// where each is a right-hand stage of the last.
func mirrorStageSubtree(stages []*stage) {
var rootStage, inverseStage, carryStage, frontStage *stage
stagesLength := len(stages)
// reverse all right/left
for _, frontStage = range stages {
carryStage = frontStage.right
frontStage.right = frontStage.left
frontStage.left = carryStage
}
// end left swaps with root right
rootStage = stages[0]
frontStage = stages[stagesLength-1]
carryStage = frontStage.left
frontStage.left = rootStage.right
rootStage.right = carryStage
// for all non-root non-end stages, right is swapped with inverse stage right in list
for i := 0; i < (stagesLength-2)/2+1; i++ {
frontStage = stages[i+1]
inverseStage = stages[stagesLength-i-1]
carryStage = frontStage.right
frontStage.right = inverseStage.right
inverseStage.right = carryStage
}
// swap all other information with inverse stages
for i := 0; i < stagesLength/2; i++ {
frontStage = stages[i]
inverseStage = stages[stagesLength-i-1]
frontStage.swapWith(inverseStage)
}
}
func doStage(stage *stage, parameters interface{}) (interface{}, error) {
if stage == nil {
return nil, nil
}
var left, right interface{}
var err error
if stage.left != nil {
left, err = doStage(stage.left, parameters)
if err != nil {
return nil, err
}
}
if stage.right != nil {
right, err = doStage(stage.right, parameters)
if err != nil {
return nil, err
}
}
if stage.symbol.LeftCheckFn() != nil {
err = stage.symbol.LeftCheckFn()(left, right, parameters)
if err != nil {
return nil, err
}
}
if stage.symbol.RightCheckFn() != nil {
err = stage.symbol.RightCheckFn()(left, right, parameters)
if err != nil {
return nil, err
}
}
return stage.symbol.SymbolFn()(left, right, parameters)
}