shuntingyard.gno
14.30 Kb · 541 lines
1// Package shuntingyard turns an infix arithmetic expression into reverse
2// Polish notation and evaluates it over int64, with Dijkstra's shunting-yard
3// algorithm (1961).
4//
5// A realm that wants to take a formula from a caller has two bad options and
6// this one. Hard-coding the arithmetic means a new package path for every new
7// formula, and a public path can never be redeployed. Accepting a pre-built
8// RPN string pushes the parsing onto whoever is sending the transaction, who
9// then has to be trusted to have parsed it the same way. Parsing infix on
10// chain keeps the formula a piece of data and the meaning a piece of code.
11//
12// Three properties make it usable for that rather than only interesting:
13//
14// - Every arithmetic result is checked. An expression that would wrap int64
15// returns [ErrOverflow] instead of a plausible wrong number, which matters
16// because the usual reason to evaluate a caller's formula is to compute an
17// amount.
18// - Nothing panics. Every refusal is an error value, so a Render that
19// evaluates a stored expression cannot be made permanently unreadable by
20// one bad input.
21// - Parsing and evaluation are separate. [ToRPN] answers whether an
22// expression is well formed, and the RPN it returns is a bounded program a
23// realm can store and re-run without parsing it again.
24//
25// Integers only, deliberately: see the package README.
26//
27// A live demo of this package is at
28// [r/moul/x/daily/shuntingyarddemo](/r/moul/x/daily/shuntingyarddemo/v0).
29package shuntingyard
30
31import (
32 "errors"
33 "math"
34 "strconv"
35 "strings"
36)
37
38// MaxTokens bounds how long an expression may be, so a caller cannot size the
39// two stacks from unbounded input and make the allocation itself the attack.
40// It is a token count, not a byte count: whitespace and long literals are free.
41const MaxTokens = 1024
42
43// Operator spellings, as they appear in a [Token]. The two unary forms are
44// separate operators rather than a flag, because a prefix minus and a binary
45// minus have different arities and different precedence, and conflating them
46// is the classic way a shunting-yard implementation evaluates -3^2 as 9.
47const (
48 OpAdd = "+"
49 OpSub = "-"
50 OpMul = "*"
51 OpDiv = "/"
52 OpMod = "%"
53 OpPow = "^"
54 OpNeg = "u-"
55 OpPos = "u+"
56)
57
58// Evaluation failures. Each one is a value rather than a panic: see the
59// package doc.
60var (
61 ErrDivByZero = errors.New("shuntingyard: division by zero")
62 ErrOverflow = errors.New("shuntingyard: int64 overflow")
63 ErrNegExponent = errors.New("shuntingyard: negative exponent")
64 ErrTooLong = errors.New("shuntingyard: too many tokens")
65 ErrMalformedRPN = errors.New("shuntingyard: malformed RPN")
66)
67
68// SyntaxError is returned by [Tokenize] and [ToRPN]. Pos is the byte offset in
69// the source where the problem was noticed, so a caller can point at it.
70type SyntaxError struct {
71 Pos int
72 Msg string
73}
74
75// Error implements the error interface.
76func (e *SyntaxError) Error() string {
77 return "shuntingyard: " + e.Msg + " at offset " + strconv.Itoa(e.Pos)
78}
79
80// Kind tells a [Token] apart.
81type Kind uint8
82
83// The four token kinds.
84const (
85 KindNumber Kind = iota
86 KindOperator
87 KindLParen
88 KindRParen
89)
90
91// Token is one lexical unit of an expression. Num is meaningful only for
92// [KindNumber] and Op only for [KindOperator]. Pos is the byte offset the
93// token started at, kept so an error can name a place rather than a symbol.
94type Token struct {
95 Kind Kind
96 Num int64
97 Op string
98 Pos int
99}
100
101// String renders a token the way it is written in an expression, which is also
102// how [FormatRPN] prints it.
103func (t Token) String() string {
104 switch t.Kind {
105 case KindNumber:
106 return strconv.FormatInt(t.Num, 10)
107 case KindOperator:
108 return t.Op
109 case KindLParen:
110 return "("
111 case KindRParen:
112 return ")"
113 }
114 return "?"
115}
116
117// OpInfo describes one operator: its precedence, whether it associates to the
118// right, and whether it is the prefix unary form.
119type OpInfo struct {
120 Op string
121 Prec int
122 Right bool
123 Unary bool
124}
125
126// operators is the whole precedence table. Everything about how an expression
127// groups is in these eight rows, which is the point of the algorithm: the
128// grouping is data, not control flow, so adding an operator is a row.
129//
130// The unary forms sit between the multiplicative operators and the power on
131// purpose. Below the power is what makes -3^2 read as -(3^2), which is how
132// every language that has both spells it; above multiplication is what makes
133// -2*3 read as (-2)*3 rather than -(2*3). The two happen to agree here, but
134// they would not for an operator that is not distributive.
135var operators = []OpInfo{
136 {Op: OpAdd, Prec: 1},
137 {Op: OpSub, Prec: 1},
138 {Op: OpMul, Prec: 2},
139 {Op: OpDiv, Prec: 2},
140 {Op: OpMod, Prec: 2},
141 {Op: OpNeg, Prec: 3, Right: true, Unary: true},
142 {Op: OpPos, Prec: 3, Right: true, Unary: true},
143 {Op: OpPow, Prec: 4, Right: true},
144}
145
146// Operators returns the precedence table, lowest precedence first. The slice
147// is a copy: a caller rendering it must not be able to reorder the parser.
148func Operators() []OpInfo {
149 out := make([]OpInfo, len(operators))
150 copy(out, operators)
151 return out
152}
153
154// lookup returns the table row for an operator spelling.
155func lookup(op string) (OpInfo, bool) {
156 for _, info := range operators {
157 if info.Op == op {
158 return info, true
159 }
160 }
161 return OpInfo{}, false
162}
163
164// Tokenize splits an infix expression into tokens, resolving a leading '+' or
165// '-' to its unary form ([OpPos], [OpNeg]) from what came before it.
166//
167// It validates characters and literals only. Whether the tokens form an
168// expression is [ToRPN]'s question, because that is the pass that knows what
169// may follow what.
170func Tokenize(src string) ([]Token, error) {
171 var out []Token
172 for i := 0; i < len(src); {
173 c := src[i]
174
175 if c == ' ' || c == '\t' || c == '\n' || c == '\r' {
176 i++
177 continue
178 }
179
180 switch {
181 case c >= '0' && c <= '9':
182 j := i
183 for j < len(src) && src[j] >= '0' && src[j] <= '9' {
184 j++
185 }
186 n, err := strconv.ParseInt(src[i:j], 10, 64)
187 if err != nil {
188 return nil, &SyntaxError{Pos: i, Msg: "integer literal out of range"}
189 }
190 out = append(out, Token{Kind: KindNumber, Num: n, Pos: i})
191 i = j
192 case c == '(':
193 out = append(out, Token{Kind: KindLParen, Pos: i})
194 i++
195 case c == ')':
196 out = append(out, Token{Kind: KindRParen, Pos: i})
197 i++
198 default:
199 op := binaryOp(c)
200 if op == "" {
201 return nil, &SyntaxError{Pos: i, Msg: "unexpected character " + quote(src[i:i+1])}
202 }
203 if prefixPosition(out) {
204 switch op {
205 case OpAdd:
206 op = OpPos
207 case OpSub:
208 op = OpNeg
209 }
210 }
211 out = append(out, Token{Kind: KindOperator, Op: op, Pos: i})
212 i++
213 }
214
215 if len(out) > MaxTokens {
216 return nil, ErrTooLong
217 }
218 }
219 return out, nil
220}
221
222// binaryOp maps a byte to the operator it spells, or "" if it spells none.
223func binaryOp(c byte) string {
224 switch c {
225 case '+':
226 return OpAdd
227 case '-':
228 return OpSub
229 case '*':
230 return OpMul
231 case '/':
232 return OpDiv
233 case '%':
234 return OpMod
235 case '^':
236 return OpPow
237 }
238 return ""
239}
240
241// prefixPosition reports whether the next operator would be a prefix one:
242// nothing before it, or an operator or an opening parenthesis before it. A
243// closing parenthesis and a number both end an operand, so what follows them
244// is binary.
245func prefixPosition(out []Token) bool {
246 if len(out) == 0 {
247 return true
248 }
249 prev := out[len(out)-1]
250 return prev.Kind == KindOperator || prev.Kind == KindLParen
251}
252
253// ToRPN converts an infix token stream to reverse Polish notation, rejecting
254// anything that is not a well-formed expression.
255//
256// The validity check is one bit of state: whether an operand or an operator is
257// expected next. That single bit is what rejects "1 2", "1+" and "()", and it
258// costs nothing on top of the conversion the function is doing anyway.
259func ToRPN(in []Token) ([]Token, error) {
260 if len(in) > MaxTokens {
261 return nil, ErrTooLong
262 }
263
264 var out, stack []Token
265 expectOperand := true
266 end := 0
267
268 for _, tok := range in {
269 end = tok.Pos + 1
270
271 switch tok.Kind {
272 case KindNumber:
273 if !expectOperand {
274 return nil, &SyntaxError{Pos: tok.Pos, Msg: "unexpected number"}
275 }
276 out = append(out, tok)
277 expectOperand = false
278
279 case KindLParen:
280 if !expectOperand {
281 return nil, &SyntaxError{Pos: tok.Pos, Msg: "unexpected " + quote("(")}
282 }
283 stack = append(stack, tok)
284
285 case KindRParen:
286 if expectOperand {
287 return nil, &SyntaxError{Pos: tok.Pos, Msg: "unexpected " + quote(")")}
288 }
289 for len(stack) > 0 && stack[len(stack)-1].Kind != KindLParen {
290 out = append(out, stack[len(stack)-1])
291 stack = stack[:len(stack)-1]
292 }
293 if len(stack) == 0 {
294 return nil, &SyntaxError{Pos: tok.Pos, Msg: "unbalanced " + quote(")")}
295 }
296 stack = stack[:len(stack)-1]
297 expectOperand = false
298
299 case KindOperator:
300 info, ok := lookup(tok.Op)
301 if !ok {
302 return nil, &SyntaxError{Pos: tok.Pos, Msg: "unknown operator " + quote(tok.Op)}
303 }
304 // A unary operator is only ever an operand's prefix, a binary one
305 // only ever an operand's successor. One comparison covers both.
306 if info.Unary != expectOperand {
307 return nil, &SyntaxError{Pos: tok.Pos, Msg: "unexpected operator " + quote(tok.Op)}
308 }
309 // A prefix operator pops nothing: whatever is on the stack is
310 // waiting for a right operand that this operator is about to
311 // build, so popping it here would apply it to nothing.
312 if !info.Unary {
313 for len(stack) > 0 {
314 top := stack[len(stack)-1]
315 if top.Kind != KindOperator {
316 break
317 }
318 ti, _ := lookup(top.Op)
319 if ti.Prec > info.Prec || (ti.Prec == info.Prec && !info.Right) {
320 out = append(out, top)
321 stack = stack[:len(stack)-1]
322 continue
323 }
324 break
325 }
326 }
327 stack = append(stack, tok)
328 expectOperand = true
329
330 default:
331 return nil, &SyntaxError{Pos: tok.Pos, Msg: "unknown token"}
332 }
333 }
334
335 if expectOperand {
336 return nil, &SyntaxError{Pos: end, Msg: "unexpected end of expression"}
337 }
338
339 for len(stack) > 0 {
340 top := stack[len(stack)-1]
341 stack = stack[:len(stack)-1]
342 if top.Kind == KindLParen {
343 return nil, &SyntaxError{Pos: top.Pos, Msg: "unbalanced " + quote("(")}
344 }
345 out = append(out, top)
346 }
347 return out, nil
348}
349
350// EvalRPN evaluates a reverse Polish token stream over int64.
351//
352// It re-checks everything [ToRPN] guarantees, because the RPN is the part a
353// realm would store and re-run, and a stored program is an input like any
354// other by the time it is read back.
355func EvalRPN(rpn []Token) (int64, error) {
356 if len(rpn) > MaxTokens {
357 return 0, ErrTooLong
358 }
359
360 var stack []int64
361 for _, tok := range rpn {
362 if tok.Kind == KindNumber {
363 stack = append(stack, tok.Num)
364 continue
365 }
366 if tok.Kind != KindOperator {
367 return 0, ErrMalformedRPN
368 }
369
370 info, ok := lookup(tok.Op)
371 if !ok {
372 return 0, ErrMalformedRPN
373 }
374
375 if info.Unary {
376 if len(stack) < 1 {
377 return 0, ErrMalformedRPN
378 }
379 v, err := applyUnary(tok.Op, stack[len(stack)-1])
380 if err != nil {
381 return 0, err
382 }
383 stack[len(stack)-1] = v
384 continue
385 }
386
387 if len(stack) < 2 {
388 return 0, ErrMalformedRPN
389 }
390 a, b := stack[len(stack)-2], stack[len(stack)-1]
391 stack = stack[:len(stack)-2]
392 v, err := applyBinary(tok.Op, a, b)
393 if err != nil {
394 return 0, err
395 }
396 stack = append(stack, v)
397 }
398
399 if len(stack) != 1 {
400 return 0, ErrMalformedRPN
401 }
402 return stack[0], nil
403}
404
405// Eval tokenizes, converts and evaluates an infix expression in one call.
406func Eval(src string) (int64, error) {
407 toks, err := Tokenize(src)
408 if err != nil {
409 return 0, err
410 }
411 rpn, err := ToRPN(toks)
412 if err != nil {
413 return 0, err
414 }
415 return EvalRPN(rpn)
416}
417
418// FormatRPN renders a token stream space-separated, the usual way RPN is
419// written down.
420func FormatRPN(toks []Token) string {
421 var b strings.Builder
422 for i, t := range toks {
423 if i > 0 {
424 b.WriteString(" ")
425 }
426 b.WriteString(t.String())
427 }
428 return b.String()
429}
430
431// applyUnary applies a prefix operator.
432func applyUnary(op string, a int64) (int64, error) {
433 switch op {
434 case OpNeg:
435 // The one asymmetry of two's complement: there is no positive
436 // counterpart to the smallest int64, so negating it wraps to itself.
437 if a == math.MinInt64 {
438 return 0, ErrOverflow
439 }
440 return -a, nil
441 case OpPos:
442 return a, nil
443 }
444 return 0, ErrMalformedRPN
445}
446
447// applyBinary applies an infix operator, refusing anything it cannot compute
448// exactly.
449func applyBinary(op string, a, b int64) (int64, error) {
450 switch op {
451 case OpAdd:
452 if (b > 0 && a > math.MaxInt64-b) || (b < 0 && a < math.MinInt64-b) {
453 return 0, ErrOverflow
454 }
455 return a + b, nil
456 case OpSub:
457 if (b < 0 && a > math.MaxInt64+b) || (b > 0 && a < math.MinInt64+b) {
458 return 0, ErrOverflow
459 }
460 return a - b, nil
461 case OpMul:
462 return mulChecked(a, b)
463 case OpDiv:
464 if b == 0 {
465 return 0, ErrDivByZero
466 }
467 if a == math.MinInt64 && b == -1 {
468 return 0, ErrOverflow
469 }
470 return a / b, nil
471 case OpMod:
472 if b == 0 {
473 return 0, ErrDivByZero
474 }
475 // MinInt64 % -1 is 0 mathematically, but the hardware instruction
476 // behind it is the same one that overflows on the division.
477 if a == math.MinInt64 && b == -1 {
478 return 0, nil
479 }
480 return a % b, nil
481 case OpPow:
482 return powChecked(a, b)
483 }
484 return 0, ErrMalformedRPN
485}
486
487// mulChecked multiplies, reporting [ErrOverflow] rather than wrapping.
488func mulChecked(a, b int64) (int64, error) {
489 if a == 0 || b == 0 {
490 return 0, nil
491 }
492 if (a == -1 && b == math.MinInt64) || (b == -1 && a == math.MinInt64) {
493 return 0, ErrOverflow
494 }
495 p := a * b
496 // The division is the check: it recovers a exactly unless the product
497 // wrapped. Comparing against a precomputed limit instead needs a different
498 // limit per sign combination, and that is where these get written wrong.
499 if p/b != a {
500 return 0, ErrOverflow
501 }
502 return p, nil
503}
504
505// powChecked raises base to exp by squaring, in O(log exp) checked
506// multiplications.
507func powChecked(base, exp int64) (int64, error) {
508 if exp < 0 {
509 return 0, ErrNegExponent
510 }
511
512 result := int64(1)
513 b, e := base, exp
514 for e > 0 {
515 if e&1 == 1 {
516 v, err := mulChecked(result, b)
517 if err != nil {
518 return 0, err
519 }
520 result = v
521 }
522 e >>= 1
523 // Squaring the base one last time after the final bit is consumed
524 // would overflow on exponents that are perfectly representable, so
525 // the loop stops before the squaring it does not need.
526 if e == 0 {
527 break
528 }
529 v, err := mulChecked(b, b)
530 if err != nil {
531 return 0, err
532 }
533 b = v
534 }
535 return result, nil
536}
537
538// quote wraps a spelling in double quotes for an error message.
539func quote(s string) string {
540 return "\"" + s + "\""
541}
