shuntingyard_test.gno
9.69 Kb · 307 lines
1package shuntingyard
2
3import (
4 "strings"
5 "testing"
6
7 "gno.land/p/nt/uassert/v0"
8)
9
10// TestEval pins the grouping rules. Every want below was computed by hand:
11// a parser checked against another parser only proves the two agree.
12func TestEval(t *testing.T) {
13 cases := []struct {
14 name string
15 src string
16 want int64
17 }{
18 {"a single number", "42", 42},
19 {"multiplication binds tighter", "2+3*4", 14},
20 {"parentheses beat precedence", "(2+3)*4", 20},
21 {"subtraction is left associative", "10-3-2", 5},
22 {"division is left associative", "100/5/2", 10},
23 {"power is right associative", "2^3^2", 512},
24 {"unary minus binds looser than power", "-3^2", -9},
25 {"unary minus over a group", "-(3+4)", -7},
26 {"two unary minuses cancel", "--5", 5},
27 {"unary after a binary operator", "3*-2", -6},
28 {"unary plus is a no-op", "+7-+2", 5},
29 {"a plus directly after a plus is unary", "1++2", 3},
30 {"modulo", "17%5", 2},
31 {"division truncates toward zero", "-7/2", -3},
32 {"modulo takes the sign of the dividend", "-7%2", -1},
33 {"whitespace is insignificant", " 1 +\t2 ", 3},
34 {"zero to the zero is one", "0^0", 1},
35 {"redundant nesting", "((((1+2))))*3", 9},
36 {"a long chain", "1+2*3-4/2+5%3", 7},
37 }
38
39 for _, tc := range cases {
40 t.Run(tc.name, func(t *testing.T) {
41 got, err := Eval(tc.src)
42 if err != nil {
43 t.Errorf("Eval(%q) returned error %v", tc.src, err)
44 return
45 }
46 if got != tc.want {
47 t.Errorf("Eval(%q) = %d, want %d", tc.src, got, tc.want)
48 }
49 })
50 }
51}
52
53// TestToRPN pins the conversion itself rather than the number that falls out
54// of it. Eval would pass on a shape that happened to evaluate the same way.
55func TestToRPN(t *testing.T) {
56 cases := []struct {
57 src string
58 want string
59 }{
60 {"2+3*4", "2 3 4 * +"},
61 {"(2+3)*4", "2 3 + 4 *"},
62 {"2^3^2", "2 3 2 ^ ^"},
63 {"-3^2", "3 2 ^ u-"},
64 {"3*-2", "3 2 u- *"},
65 {"10-3-2", "10 3 - 2 -"},
66 {"-(3+4)", "3 4 + u-"},
67 {"1+2*3-4/2", "1 2 3 * + 4 2 / -"},
68 }
69
70 for _, tc := range cases {
71 t.Run(tc.src, func(t *testing.T) {
72 toks, err := Tokenize(tc.src)
73 if err != nil {
74 t.Errorf("Tokenize(%q) returned error %v", tc.src, err)
75 return
76 }
77 rpn, err := ToRPN(toks)
78 if err != nil {
79 t.Errorf("ToRPN(%q) returned error %v", tc.src, err)
80 return
81 }
82 if got := FormatRPN(rpn); got != tc.want {
83 t.Errorf("ToRPN(%q) = %q, want %q", tc.src, got, tc.want)
84 }
85 })
86 }
87}
88
89// TestTokenizeResolvesUnary is the one decision Tokenize makes on its own, and
90// it is the decision a hand-rolled parser gets wrong: the same byte is two
91// different operators depending on what precedes it.
92func TestTokenizeResolvesUnary(t *testing.T) {
93 cases := []struct {
94 src string
95 at int // index of the token under test
96 wantOp string
97 }{
98 {"1-2", 1, OpSub},
99 {"-1", 0, OpNeg},
100 {"(-1)", 1, OpNeg},
101 {"2*-1", 2, OpNeg},
102 {"2^-1", 2, OpNeg},
103 {"+1", 0, OpPos},
104 {"1+2", 1, OpAdd},
105 }
106
107 for _, tc := range cases {
108 t.Run(tc.src, func(t *testing.T) {
109 toks, err := Tokenize(tc.src)
110 if err != nil {
111 t.Errorf("Tokenize(%q) returned error %v", tc.src, err)
112 return
113 }
114 if tc.at >= len(toks) {
115 t.Errorf("Tokenize(%q) produced %d tokens, want more than %d", tc.src, len(toks), tc.at)
116 return
117 }
118 tok := toks[tc.at]
119 if tok.Kind != KindOperator || tok.Op != tc.wantOp {
120 t.Errorf("Tokenize(%q)[%d] = %v, want operator %q", tc.src, tc.at, tok, tc.wantOp)
121 }
122 })
123 }
124}
125
126// TestTokenPositions pins the offsets, which are the only thing making a
127// syntax error actionable to whoever typed the expression.
128func TestTokenPositions(t *testing.T) {
129 toks, err := Tokenize(" 12 + (3)")
130 uassert.NoError(t, err)
131 if len(toks) != 5 {
132 t.Errorf("got %d tokens, want 5", len(toks))
133 return
134 }
135 wantPos := []int{1, 4, 6, 7, 8}
136 for i, want := range wantPos {
137 if toks[i].Pos != want {
138 t.Errorf("token %d (%v) at offset %d, want %d", i, toks[i], toks[i].Pos, want)
139 }
140 }
141}
142
143// TestSyntaxErrors covers every way an expression can be rejected before any
144// arithmetic happens. The message is pinned whole, offset included.
145func TestSyntaxErrors(t *testing.T) {
146 cases := []struct {
147 name string
148 src string
149 want string
150 }{
151 {"empty", "", "shuntingyard: unexpected end of expression at offset 0"},
152 {"trailing operator", "1+", "shuntingyard: unexpected end of expression at offset 2"},
153 {"two numbers", "1 2", "shuntingyard: unexpected number at offset 2"},
154 {"leading binary operator", "*2", "shuntingyard: unexpected operator \"*\" at offset 0"},
155 {"unclosed group", "(1", "shuntingyard: unbalanced \"(\" at offset 0"},
156 {"unopened group", "1)", "shuntingyard: unbalanced \")\" at offset 1"},
157 {"empty group", "()", "shuntingyard: unexpected \")\" at offset 1"},
158 {"number before group", "2(3)", "shuntingyard: unexpected \"(\" at offset 1"},
159 {"stray character", "1$2", "shuntingyard: unexpected character \"$\" at offset 1"},
160 {"literal out of range", "99999999999999999999", "shuntingyard: integer literal out of range at offset 0"},
161 }
162
163 for _, tc := range cases {
164 t.Run(tc.name, func(t *testing.T) {
165 _, err := Eval(tc.src)
166 if err == nil {
167 t.Errorf("Eval(%q) returned no error, want %q", tc.src, tc.want)
168 return
169 }
170 if got := err.Error(); got != tc.want {
171 t.Errorf("Eval(%q) error = %q, want %q", tc.src, got, tc.want)
172 }
173 })
174 }
175}
176
177// TestEvalErrors is the half that makes the package usable for money: an
178// expression that cannot be evaluated exactly says so instead of wrapping.
179func TestEvalErrors(t *testing.T) {
180 // minInt64 is only reachable through arithmetic: the literal itself is
181 // out of range for the tokenizer, because a number token carries no sign.
182 const mkMin = "((0-9223372036854775807)-1)"
183
184 cases := []struct {
185 name string
186 src string
187 want error
188 }{
189 {"division by zero", "1/0", ErrDivByZero},
190 {"modulo by zero", "1%0", ErrDivByZero},
191 {"addition overflows", "9223372036854775807+1", ErrOverflow},
192 {"multiplication overflows", "9223372036854775807*2", ErrOverflow},
193 {"subtraction overflows", "(0-9223372036854775807)-2", ErrOverflow},
194 {"power overflows", "2^64", ErrOverflow},
195 {"negating the smallest int64 overflows", "-" + mkMin, ErrOverflow},
196 {"dividing the smallest int64 by -1 overflows", mkMin + "/(0-1)", ErrOverflow},
197 {"negative exponent", "2^-1", ErrNegExponent},
198 }
199
200 for _, tc := range cases {
201 t.Run(tc.name, func(t *testing.T) {
202 got, err := Eval(tc.src)
203 if err != tc.want {
204 t.Errorf("Eval(%q) = %d, %v, want error %v", tc.src, got, err, tc.want)
205 }
206 })
207 }
208}
209
210// TestEvalNearTheLimit is the other side of TestEvalErrors: the checks must
211// not reject an expression that fits exactly.
212func TestEvalNearTheLimit(t *testing.T) {
213 cases := []struct {
214 src string
215 want int64
216 }{
217 {"9223372036854775806+1", 9223372036854775807},
218 {"4611686018427387903*2", 9223372036854775806},
219 {"2^62", 4611686018427387904},
220 {"(0-9223372036854775807)-0", -9223372036854775807},
221 }
222
223 for _, tc := range cases {
224 t.Run(tc.src, func(t *testing.T) {
225 got, err := Eval(tc.src)
226 if err != nil {
227 t.Errorf("Eval(%q) returned error %v", tc.src, err)
228 return
229 }
230 if got != tc.want {
231 t.Errorf("Eval(%q) = %d, want %d", tc.src, got, tc.want)
232 }
233 })
234 }
235}
236
237// TestEvalRPNRejectsMalformed matters because EvalRPN is exported: a realm may
238// store the RPN and re-run it later, so it has to defend itself rather than
239// trust that ToRPN produced what it is given.
240func TestEvalRPNRejectsMalformed(t *testing.T) {
241 cases := []struct {
242 name string
243 rpn []Token
244 }{
245 {"empty", nil},
246 {"operator with no operands", []Token{{Kind: KindOperator, Op: OpAdd}}},
247 {"operator with one operand", []Token{{Kind: KindNumber, Num: 2}, {Kind: KindOperator, Op: OpAdd}}},
248 {"two values left over", []Token{{Kind: KindNumber, Num: 2}, {Kind: KindNumber, Num: 3}}},
249 {"unary with no operand", []Token{{Kind: KindOperator, Op: OpNeg}}},
250 {"unknown operator", []Token{{Kind: KindNumber, Num: 2}, {Kind: KindNumber, Num: 3}, {Kind: KindOperator, Op: "&"}}},
251 {"a parenthesis survived the conversion", []Token{{Kind: KindLParen}}},
252 }
253
254 for _, tc := range cases {
255 t.Run(tc.name, func(t *testing.T) {
256 got, err := EvalRPN(tc.rpn)
257 if err != ErrMalformedRPN {
258 t.Errorf("EvalRPN(%v) = %d, %v, want %v", tc.rpn, got, err, ErrMalformedRPN)
259 }
260 })
261 }
262}
263
264// TestTooLong pins the bound. Without it the two stacks are sized by whoever
265// sends the transaction.
266func TestTooLong(t *testing.T) {
267 src := strings.Repeat("1+", MaxTokens) + "1"
268 if _, err := Eval(src); err != ErrTooLong {
269 t.Errorf("Eval of %d tokens returned %v, want %v", 2*MaxTokens+1, err, ErrTooLong)
270 }
271
272 // Just under the bound still parses, so the check is a bound and not an
273 // off-by-one that rejects a long but legal expression.
274 pairs := (MaxTokens - 1) / 2
275 ok := strings.Repeat("1+", pairs) + "1"
276 if _, err := Eval(ok); err != nil {
277 t.Errorf("Eval of %d tokens returned %v, want it to parse", 2*pairs+1, err)
278 }
279}
280
281// TestOperatorsIsACopy: the table is the parser's behaviour, so handing out
282// the backing array would let a caller rendering it change how it parses.
283func TestOperatorsIsACopy(t *testing.T) {
284 got := Operators()
285 if len(got) != len(operators) {
286 t.Errorf("Operators() returned %d rows, want %d", len(got), len(operators))
287 return
288 }
289 got[0].Prec = 99
290 if operators[0].Prec == 99 {
291 t.Errorf("Operators() handed out the table itself")
292 }
293}
294
295// TestFormatRPNEmpty pins the only edge case the formatter has.
296func TestFormatRPNEmpty(t *testing.T) {
297 uassert.Equal(t, "", FormatRPN(nil))
298}
299
300// TestTokenString covers the four kinds, since FormatRPN and the demo both
301// render through it.
302func TestTokenString(t *testing.T) {
303 uassert.Equal(t, "-7", Token{Kind: KindNumber, Num: -7}.String())
304 uassert.Equal(t, "u-", Token{Kind: KindOperator, Op: OpNeg}.String())
305 uassert.Equal(t, "(", Token{Kind: KindLParen}.String())
306 uassert.Equal(t, ")", Token{Kind: KindRParen}.String())
307}
