int32.gno
9.37 Kb ยท 494 lines
1// eval/int32 is a evaluator for int32 expressions.
2// This code is heavily forked from https://github.com/dengsgo/math-engine
3// which is licensed under Apache 2.0:
4// https://raw.githubusercontent.com/dengsgo/math-engine/298e2b57b7e7350d0f67bd036916efd5709abe25/LICENSE
5package int32
6
7import (
8 "errors"
9 "strconv"
10 "strings"
11
12 "gno.land/p/demo/ufmt"
13)
14
15const (
16 Identifier = iota
17 Number // numbers
18 Operator // +, -, *, /, etc.
19 Variable // x, y, z, etc. (one-letter only)
20)
21
22type expression interface {
23 String() string
24}
25
26type expressionRaw struct {
27 expression string
28 Type int
29 Flag int
30 Offset int
31}
32
33type parser struct {
34 Input string
35 ch byte
36 offset int
37 err error
38}
39
40type expressionNumber struct {
41 Val int
42 Str string
43}
44
45type expressionVariable struct {
46 Val int
47 Str string
48}
49
50type expressionOperation struct {
51 Op string
52 Lhs,
53 Rhs expression
54}
55
56type ast struct {
57 rawexpressions []*expressionRaw
58 source string
59 currentexpression *expressionRaw
60 currentIndex int
61 depth int
62 err error
63}
64
65// Parse takes an expression string, e.g. "1+2" and returns
66// a parsed expression. If there is an error it will return.
67func Parse(s string) (ar expression, err error) {
68 toks, err := lexer(s)
69 if err != nil {
70 return
71 }
72 ast, err := newAST(toks, s)
73 if err != nil {
74 return
75 }
76 ar, err = ast.parseExpression()
77 return
78}
79
80// Eval takes a parsed expression and a map of variables (or nil). The parsed
81// expression is evaluated using any variables and returns the
82// resulting int and/or error.
83func Eval(expr expression, variables map[string]int) (res int, err error) {
84 if err != nil {
85 return
86 }
87 var l, r int
88 switch expr.(type) {
89 case expressionVariable:
90 ast := expr.(expressionVariable)
91 ok := false
92 if variables != nil {
93 res, ok = variables[ast.Str]
94 }
95 if !ok {
96 err = ufmt.Errorf("variable '%s' not found", ast.Str)
97 }
98 return
99 case expressionOperation:
100 ast := expr.(expressionOperation)
101 l, err = Eval(ast.Lhs, variables)
102 if err != nil {
103 return
104 }
105 r, err = Eval(ast.Rhs, variables)
106 if err != nil {
107 return
108 }
109 switch ast.Op {
110 case "+":
111 res = l + r
112 case "-":
113 res = l - r
114 case "*":
115 res = l * r
116 case "/":
117 if r == 0 {
118 err = ufmt.Errorf("violation of arithmetic specification: a division by zero in Eval: [%d/%d]", l, r)
119 return
120 }
121 res = l / r
122 case "%":
123 if r == 0 {
124 res = 0
125 } else {
126 res = l % r
127 }
128 case "^":
129 res = l ^ r
130 case ">>":
131 res = l >> r
132 case "<<":
133 res = l << r
134 case ">":
135 if l > r {
136 res = 1
137 } else {
138 res = 0
139 }
140 case "<":
141 if l < r {
142 res = 1
143 } else {
144 res = 0
145 }
146 case "&":
147 res = l & r
148 case "|":
149 res = l | r
150 default:
151
152 }
153 case expressionNumber:
154 res = expr.(expressionNumber).Val
155 }
156
157 return
158}
159
160func expressionError(s string, pos int) string {
161 r := strings.Repeat("-", len(s)) + "\n"
162 s += "\n"
163 for i := 0; i < pos; i++ {
164 s += " "
165 }
166 s += "^\n"
167 return r + s + r
168}
169
170func (n expressionVariable) String() string {
171 return ufmt.Sprintf(
172 "expressionVariable: %s",
173 n.Str,
174 )
175}
176
177func (n expressionNumber) String() string {
178 return ufmt.Sprintf(
179 "expressionNumber: %s",
180 n.Str,
181 )
182}
183
184func (b expressionOperation) String() string {
185 return ufmt.Sprintf(
186 "expressionOperation: (%s %s %s)",
187 b.Op,
188 b.Lhs.String(),
189 b.Rhs.String(),
190 )
191}
192
193func newAST(toks []*expressionRaw, s string) (*ast, error) {
194 a := &ast{
195 rawexpressions: toks,
196 source: s,
197 }
198 if a.rawexpressions == nil || len(a.rawexpressions) == 0 {
199 return a, errors.New("empty token")
200 } else {
201 a.currentIndex = 0
202 a.currentexpression = a.rawexpressions[0]
203 }
204 return a, nil
205}
206
207func (a *ast) parseExpression() (expression, error) {
208 a.depth++ // called depth
209 lhs := a.parsePrimary()
210 r := a.parseBinOpRHS(0, lhs)
211 a.depth--
212 if a.depth == 0 && a.currentIndex != len(a.rawexpressions) && a.err == nil {
213 return r, ufmt.Errorf("bad expression, reaching the end or missing the operator\n%s",
214 expressionError(a.source, a.currentexpression.Offset))
215 }
216 return r, nil
217}
218
219func (a *ast) getNextexpressionRaw() *expressionRaw {
220 a.currentIndex++
221 if a.currentIndex < len(a.rawexpressions) {
222 a.currentexpression = a.rawexpressions[a.currentIndex]
223 return a.currentexpression
224 }
225 return nil
226}
227
228func (a *ast) getTokPrecedence() int {
229 switch a.currentexpression.expression {
230 case "/", "%", "*":
231 return 100
232 case "<<", ">>":
233 return 80
234 case "+", "-":
235 return 75
236 case "<", ">":
237 return 70
238 case "&":
239 return 60
240 case "^":
241 return 50
242 case "|":
243 return 40
244 }
245 return -1
246}
247
248func (a *ast) parseNumber() expressionNumber {
249 f64, err := strconv.Atoi(a.currentexpression.expression)
250 if err != nil {
251 a.err = ufmt.Errorf("%v\nwant '(' or '0-9' but get '%s'\n%s",
252 err.Error(),
253 a.currentexpression.expression,
254 expressionError(a.source, a.currentexpression.Offset))
255 return expressionNumber{}
256 }
257 n := expressionNumber{
258 Val: f64,
259 Str: a.currentexpression.expression,
260 }
261 a.getNextexpressionRaw()
262 return n
263}
264
265func (a *ast) parseVariable() expressionVariable {
266 n := expressionVariable{
267 Val: 0,
268 Str: a.currentexpression.expression,
269 }
270 a.getNextexpressionRaw()
271 return n
272}
273
274func (a *ast) parsePrimary() expression {
275 switch a.currentexpression.Type {
276 case Variable:
277 return a.parseVariable()
278 case Number:
279 return a.parseNumber()
280 case Operator:
281 if a.currentexpression.expression == "(" {
282 t := a.getNextexpressionRaw()
283 if t == nil {
284 a.err = ufmt.Errorf("want '(' or '0-9' but get EOF\n%s",
285 expressionError(a.source, a.currentexpression.Offset))
286 return nil
287 }
288 e, _ := a.parseExpression()
289 if e == nil {
290 return nil
291 }
292 if a.currentexpression.expression != ")" {
293 a.err = ufmt.Errorf("want ')' but get %s\n%s",
294 a.currentexpression.expression,
295 expressionError(a.source, a.currentexpression.Offset))
296 return nil
297 }
298 a.getNextexpressionRaw()
299 return e
300 } else if a.currentexpression.expression == "-" {
301 if a.getNextexpressionRaw() == nil {
302 a.err = ufmt.Errorf("want '0-9' but get '-'\n%s",
303 expressionError(a.source, a.currentexpression.Offset))
304 return nil
305 }
306 bin := expressionOperation{
307 Op: "-",
308 Lhs: expressionNumber{},
309 Rhs: a.parsePrimary(),
310 }
311 return bin
312 } else {
313 return a.parseNumber()
314 }
315 default:
316 return nil
317 }
318}
319
320func (a *ast) parseBinOpRHS(execPrec int, lhs expression) expression {
321 for {
322 tokPrec := a.getTokPrecedence()
323 if tokPrec < execPrec {
324 return lhs
325 }
326 binOp := a.currentexpression.expression
327 if a.getNextexpressionRaw() == nil {
328 a.err = ufmt.Errorf("want '(' or '0-9' but get EOF\n%s",
329 expressionError(a.source, a.currentexpression.Offset))
330 return nil
331 }
332 rhs := a.parsePrimary()
333 if rhs == nil {
334 return nil
335 }
336 nextPrec := a.getTokPrecedence()
337 if tokPrec < nextPrec {
338 rhs = a.parseBinOpRHS(tokPrec+1, rhs)
339 if rhs == nil {
340 return nil
341 }
342 }
343 lhs = expressionOperation{
344 Op: binOp,
345 Lhs: lhs,
346 Rhs: rhs,
347 }
348 }
349}
350
351func lexer(s string) ([]*expressionRaw, error) {
352 p := &parser{
353 Input: s,
354 err: nil,
355 ch: s[0],
356 }
357 toks := p.parse()
358 if p.err != nil {
359 return nil, p.err
360 }
361 return toks, nil
362}
363
364func (p *parser) parse() []*expressionRaw {
365 toks := make([]*expressionRaw, 0)
366 for {
367 tok := p.nextTok()
368 if tok == nil {
369 break
370 }
371 toks = append(toks, tok)
372 }
373 return toks
374}
375
376func (p *parser) nextTok() *expressionRaw {
377 if p.offset >= len(p.Input) || p.err != nil {
378 return nil
379 }
380 var err error
381 for p.isWhitespace(p.ch) && err == nil {
382 err = p.nextCh()
383 }
384 start := p.offset
385 var tok *expressionRaw
386 switch p.ch {
387 case
388 '(',
389 ')',
390 '+',
391 '-',
392 '*',
393 '/',
394 '^',
395 '&',
396 '|',
397 '%':
398 tok = &expressionRaw{
399 expression: string(p.ch),
400 Type: Operator,
401 }
402 tok.Offset = start
403 err = p.nextCh()
404 case '>', '<':
405 tokS := string(p.ch)
406 bb, be := p.nextChPeek()
407 if be == nil && string(bb) == tokS {
408 tokS += string(p.ch)
409 }
410 tok = &expressionRaw{
411 expression: tokS,
412 Type: Operator,
413 }
414 tok.Offset = start
415 if len(tokS) > 1 {
416 p.nextCh()
417 }
418 err = p.nextCh()
419 case
420 '0',
421 '1',
422 '2',
423 '3',
424 '4',
425 '5',
426 '6',
427 '7',
428 '8',
429 '9':
430 for p.isDigitNum(p.ch) && p.nextCh() == nil {
431 if (p.ch == '-' || p.ch == '+') && p.Input[p.offset-1] != 'e' {
432 break
433 }
434 }
435 tok = &expressionRaw{
436 expression: strings.ReplaceAll(p.Input[start:p.offset], "_", ""),
437 Type: Number,
438 }
439 tok.Offset = start
440 default:
441 if p.isChar(p.ch) {
442 tok = &expressionRaw{
443 expression: string(p.ch),
444 Type: Variable,
445 }
446 tok.Offset = start
447 err = p.nextCh()
448 } else if p.ch != ' ' {
449 p.err = ufmt.Errorf("symbol error: unknown '%v', pos [%v:]\n%s",
450 string(p.ch),
451 start,
452 expressionError(p.Input, start))
453 }
454 }
455 return tok
456}
457
458func (p *parser) nextChPeek() (byte, error) {
459 offset := p.offset + 1
460 if offset < len(p.Input) {
461 return p.Input[offset], nil
462 }
463 return byte(0), errors.New("no byte")
464}
465
466func (p *parser) nextCh() error {
467 p.offset++
468 if p.offset < len(p.Input) {
469 p.ch = p.Input[p.offset]
470 return nil
471 }
472 return errors.New("EOF")
473}
474
475func (p *parser) isWhitespace(c byte) bool {
476 return c == ' ' ||
477 c == '\t' ||
478 c == '\n' ||
479 c == '\v' ||
480 c == '\f' ||
481 c == '\r'
482}
483
484func (p *parser) isDigitNum(c byte) bool {
485 return '0' <= c && c <= '9' || c == '.' || c == '_' || c == 'e' || c == '-' || c == '+'
486}
487
488func (p *parser) isChar(c byte) bool {
489 return 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z'
490}
491
492func (p *parser) isWordChar(c byte) bool {
493 return p.isChar(c) || '0' <= c && c <= '9'
494}
