1// SPDX-License-Identifier: MIT
2
3package expr
4
5import (
6 "context"
7 "errors"
8 "fmt"
9 "strings"
10 "testing"
11 "unicode"
12)
13
14func mustParse(t testing.TB, src string, ctxNames []string, funcs []FuncInfo) Node {
15 t.Helper()
16 n, err := Parse(src, ctxNames, funcs)
17 if err != nil {
18 t.Fatalf("Parse(%.60q): %v", src, err)
19 }
20 return n
21}
22
23func evalWith(t testing.TB, src string, ec EvalContext) (Value, error) {
24 t.Helper()
25 return Evaluate(context.Background(), mustParse(t, src, []string{"big", "github"}, nil), ec)
26}
27
28func asEvalError(t testing.TB, err error) *EvalError {
29 t.Helper()
30 var ee *EvalError
31 if !errors.As(err, &ee) {
32 t.Fatalf("error %v (%T) is not an *EvalError", err, err)
33 }
34 return ee
35}
36
37// An expression of a few hundred bytes that would build a gigabyte string
38// without a budget: each level of format doubles the text.
39func doublingExpr(levels int) string {
40 e := "'x'"
41 for i := 0; i < levels; i++ {
42 e = "format('{0}{0}', " + e + ")"
43 }
44 return e
45}
46
47func TestOutputBudgetFormat(t *testing.T) {
48 // The doubling chain charges every intermediate string: 19 levels cost
49 // 2^20-2 bytes in total, which just fits the default budget of 1 MiB;
50 // 20 levels do not.
51 if _, err := evalWith(t, doublingExpr(19), EvalContext{}); err != nil {
52 t.Fatalf("19 doublings: %v", err)
53 }
54 _, err := evalWith(t, doublingExpr(20), EvalContext{})
55 if err == nil {
56 t.Fatal("a chain of 20 doublings fits the budget?")
57 }
58 if ee := asEvalError(t, err); !strings.Contains(ee.Message, "exceeds the limit of 1048576 bytes") {
59 t.Errorf("message = %q", ee.Message)
60 }
61 if v, err := evalWith(t, doublingExpr(10), EvalContext{}); err != nil || len(CoerceString(v)) != 1024 {
62 t.Errorf("10 doublings: %v, %v", v, err)
63 }
64 // Absurd depth is cut off long before memory is.
65 if _, err := evalWith(t, doublingExpr(40), EvalContext{}); err == nil {
66 t.Error("40 doublings succeeded")
67 }
68 // The limit can be raised, lowered or removed.
69 if _, err := evalWith(t, doublingExpr(12), EvalContext{MaxResultBytes: 4096}); err == nil {
70 t.Error("small limit not applied")
71 }
72 if v, err := evalWith(t, doublingExpr(20), EvalContext{MaxResultBytes: -1}); err != nil || len(CoerceString(v)) != 1<<20 {
73 t.Errorf("unlimited: %v", err)
74 }
75 if v, err := evalWith(t, doublingExpr(12), EvalContext{MaxResultBytes: 1 << 20}); err != nil || len(CoerceString(v)) != 4096 {
76 t.Errorf("explicit limit: %v", err)
77 }
78 // A single oversized argument.
79 big := String(strings.Repeat("y", 100))
80 _, err = evalWith(t, "format('{0}{0}', big)", EvalContext{Contexts: map[string]Value{"big": big}, MaxResultBytes: 150})
81 if err == nil {
82 t.Error("format over the limit succeeded")
83 }
84 if _, err = evalWith(t, "format('{0}{0}', big)", EvalContext{Contexts: map[string]Value{"big": big}, MaxResultBytes: 200}); err != nil {
85 t.Errorf("format at the limit failed: %v", err)
86 }
87}
88
89func bigArray(n int) *Array {
90 a := NewArray()
91 for i := 0; i < n; i++ {
92 a.Append(String("item"))
93 }
94 return a
95}
96
97func TestOutputBudgetJoin(t *testing.T) {
98 ec := EvalContext{Contexts: map[string]Value{"big": bigArray(1000)}}
99 // 1000 items of 4 bytes and 999 separators of 2: about 6 KB.
100 if _, err := evalWith(t, "join(big, ', ')", ec); err != nil {
101 t.Fatal(err)
102 }
103 ec.MaxResultBytes = 5000
104 if _, err := evalWith(t, "join(big, ', ')", ec); err == nil {
105 t.Error("join over the limit succeeded")
106 }
107 // A huge separator is charged too.
108 ec = EvalContext{Contexts: map[string]Value{"big": bigArray(1000), "github": String(strings.Repeat("s", 2000))}, MaxResultBytes: 1 << 20}
109 if _, err := evalWith(t, "join(big, github)", ec); err == nil { // 999 * 2000 bytes of separators
110 t.Error("a 2 MB join fits a 1 MiB budget?")
111 }
112}
113
114func TestOutputBudgetToJSON(t *testing.T) {
115 ec := EvalContext{Contexts: map[string]Value{"big": bigArray(1000)}}
116 if _, err := evalWith(t, "toJSON(big)", ec); err != nil {
117 t.Fatal(err)
118 }
119 ec.MaxResultBytes = 1000
120 _, err := evalWith(t, "toJSON(big)", ec)
121 if err == nil {
122 t.Fatal("toJSON over the limit succeeded")
123 }
124 if ee := asEvalError(t, err); !strings.Contains(ee.Message, "exceeds the limit of 1000 bytes") {
125 t.Errorf("message = %q", ee.Message)
126 }
127 // The budget is shared: two toJSON of 400 bytes each exceed 700.
128 ec.Contexts = map[string]Value{"big": bigArray(40)}
129 ec.MaxResultBytes = 700
130 if _, err := evalWith(t, "toJSON(big)", ec); err != nil {
131 t.Fatalf("one toJSON: %v", err)
132 }
133 if _, err := evalWith(t, "toJSON(big) && toJSON(big)", ec); err == nil {
134 t.Error("budget is not shared between calls")
135 }
136}
137
138func TestOutputBudgetFilter(t *testing.T) {
139 // A filter over 100 arrays of 100 items, then a second flattening: the
140 // elements built are charged.
141 outer := NewArray()
142 for i := 0; i < 100; i++ {
143 outer.Append(bigArray(100))
144 }
145 ec := EvalContext{Contexts: map[string]Value{"big": outer}}
146 if _, err := evalWith(t, "big.*.*", ec); err != nil {
147 t.Fatalf("filter within budget: %v", err)
148 }
149 ec.MaxResultBytes = 100 * 16 // the first .* costs 1600, the second 160000
150 if _, err := evalWith(t, "big.*.*", ec); err == nil {
151 t.Error("filter over the budget succeeded")
152 }
153 // A fan-out through shared arrays: an array of 1000 references to one
154 // array of 1000 items yields a million elements after two stars.
155 shared := bigArray(1000)
156 fan := NewArray()
157 for i := 0; i < 1000; i++ {
158 fan.Append(shared)
159 }
160 ec = EvalContext{Contexts: map[string]Value{"big": fan}}
161 _, err := evalWith(t, "big.*.*.*", ec)
162 if err == nil {
163 t.Fatal("fan-out filter succeeded")
164 }
165 _ = asEvalError(t, err)
166 // Lookups that do not build arrays are free.
167 if _, err := evalWith(t, "big[0][0]", EvalContext{Contexts: map[string]Value{"big": fan}, MaxResultBytes: 1}); err != nil {
168 t.Errorf("indexing charged the budget: %v", err)
169 }
170}
171
172func TestEvaluateContextCancellation(t *testing.T) {
173 ctx, cancel := context.WithCancel(context.Background())
174 cancel()
175 n := mustParse(t, "1 == 1", nil, nil)
176 _, err := Evaluate(ctx, n, EvalContext{})
177 ee := asEvalError(t, err)
178 if !errors.Is(err, context.Canceled) || ee.Unwrap() != context.Canceled {
179 t.Errorf("err = %v, want context.Canceled", err)
180 }
181
182 // Cancelled from inside a function while a big filter and contains loop run.
183 arr := bigArray(1 << 16)
184 ctx, cancel = context.WithCancel(context.Background())
185 defer cancel()
186 ec := EvalContext{
187 Contexts: map[string]Value{"big": arr, "github": String("g")},
188 Funcs: map[string]Func{"stop": func(context.Context, []Value) (Value, error) {
189 cancel()
190 return Null{}, nil
191 }},
192 MaxResultBytes: -1,
193 }
194 node := mustParse(t, "stop() || contains(big, 'nope') || join(big, ',')", []string{"big", "github"}, []FuncInfo{{Name: "stop"}})
195 _, err = Evaluate(ctx, node, ec)
196 if !errors.Is(err, context.Canceled) {
197 t.Errorf("cancel inside evaluation: err = %v", err)
198 }
199
200 // A deadline during a long loop.
201 ctx, cancel2 := context.WithTimeout(context.Background(), 0)
202 defer cancel2()
203 <-ctx.Done()
204 if _, err = Evaluate(ctx, mustParse(t, "contains(big, 'nope')", []string{"big"}, nil), EvalContext{Contexts: map[string]Value{"big": arr}}); !errors.Is(err, context.DeadlineExceeded) {
205 t.Errorf("deadline: err = %v", err)
206 }
207 // A nil context behaves as Background. (Through a variable: passing a nil
208 // literal is what staticcheck SA1012 flags.)
209 var nilCtx context.Context
210 if v, err := Evaluate(nilCtx, n, EvalContext{}); err != nil || v != Boolean(true) {
211 t.Errorf("nil context: %v, %v", v, err)
212 }
213}
214
215func TestFuncReceivesContext(t *testing.T) {
216 type key struct{}
217 ctx := context.WithValue(context.Background(), key{}, "marker")
218 var got any
219 ec := EvalContext{Funcs: map[string]Func{"probe": func(c context.Context, _ []Value) (Value, error) {
220 got = c.Value(key{})
221 return Null{}, nil
222 }}}
223 if _, err := Evaluate(ctx, mustParse(t, "probe()", nil, []FuncInfo{{Name: "probe"}}), ec); err != nil {
224 t.Fatal(err)
225 }
226 if got != "marker" {
227 t.Errorf("function did not receive the evaluation context: %v", got)
228 }
229}
230
231func TestHandBuiltASTArity(t *testing.T) {
232 call := func(name string, n int) Node {
233 args := make([]Node, n)
234 for i := range args {
235 args[i] = &Literal{Value: String("x")}
236 }
237 return &FunctionCall{Name: Token{Type: TokenIdentifier, Lexeme: name}, Args: args}
238 }
239 for _, tc := range []struct {
240 name string
241 n int
242 want string
243 }{
244 {"contains", 0, "Too few parameters supplied: 'contains'"},
245 {"contains", 1, "Too few parameters supplied: 'contains'"},
246 {"contains", 3, "Too many parameters supplied: 'contains'"},
247 {"startsWith", 1, "Too few parameters supplied: 'startsWith'"},
248 {"endsWith", 0, "Too few parameters supplied: 'endsWith'"},
249 {"join", 0, "Too few parameters supplied: 'join'"},
250 {"join", 3, "Too many parameters supplied: 'join'"},
251 {"toJSON", 0, "Too few parameters supplied: 'toJSON'"},
252 {"fromJSON", 2, "Too many parameters supplied: 'fromJSON'"},
253 {"format", 0, "Too few parameters supplied: 'format'"},
254 {"format", 256, "Too many parameters supplied: 'format'"},
255 {"case", 0, "Too few parameters supplied: 'case'"},
256 {"case", 2, "Too few parameters supplied: 'case'"},
257 {"case", 4, "Even number of parameters supplied, requires an odd number of parameters: 'case'"},
258 {"nosuch", 1, "function nosuch is not implemented"},
259 } {
260 var err error
261 func() {
262 defer func() {
263 if r := recover(); r != nil {
264 t.Errorf("%s(%d args) panicked: %v", tc.name, tc.n, r)
265 }
266 }()
267 _, err = Evaluate(context.Background(), call(tc.name, tc.n), EvalContext{})
268 }()
269 if ee := (&EvalError{}); !errors.As(err, &ee) || ee.Message != tc.want {
270 t.Errorf("%s(%d args): err = %v, want %q", tc.name, tc.n, err, tc.want)
271 }
272 }
273 // Other malformed trees must not panic either.
274 for _, n := range []Node{&Star{}, &Logical{}, &Binary{Left: &Literal{}, Right: &Literal{}}, &IndexAccess{Expr: &Literal{}, Index: &Literal{}}, &Literal{Value: nil}, &Unary{Expr: &Literal{}}} {
275 if _, err := Evaluate(context.Background(), n, EvalContext{}); err != nil {
276 _ = asEvalError(t, err)
277 }
278 }
279}
280
281func TestEvalDepthCap(t *testing.T) {
282 var n Node = &Literal{Value: Boolean(true)}
283 for i := 0; i < maxEvalDepth+10; i++ {
284 n = &Grouping{Group: n}
285 }
286 _, err := Evaluate(context.Background(), n, EvalContext{})
287 if ee := asEvalError(t, err); !strings.Contains(ee.Message, "deeper than") {
288 t.Errorf("message = %q", ee.Message)
289 }
290}
291
292func TestExtensionErrorsAreWrapped(t *testing.T) {
293 sentinel := errors.New("kaput")
294 ec := EvalContext{Funcs: map[string]Func{
295 "boom": func(context.Context, []Value) (Value, error) { return nil, sentinel },
296 "wrapped": func(context.Context, []Value) (Value, error) { return nil, fmt.Errorf("while hashing: %w", sentinel) },
297 "already": func(context.Context, []Value) (Value, error) { return nil, &EvalError{Message: "mine"} },
298 }}
299 infos := []FuncInfo{{Name: "boom"}, {Name: "wrapped"}, {Name: "already"}}
300 for src, msg := range map[string]string{"boom()": "kaput", "wrapped()": "while hashing: kaput", "already()": "mine"} {
301 _, err := Evaluate(context.Background(), mustParse(t, src, nil, infos), ec)
302 ee := asEvalError(t, err)
303 if ee.Message != msg {
304 t.Errorf("%s: message %q, want %q", src, ee.Message, msg)
305 }
306 if src != "already()" && (!errors.Is(err, sentinel) || ee.Unwrap() == nil) {
307 t.Errorf("%s: sentinel not reachable with errors.Is", src)
308 }
309 }
310}
311
312func cyclic() *Array {
313 a := NewArray()
314 a.Append(a)
315 return a
316}
317
318func TestToJSONCycle(t *testing.T) {
319 a := cyclic()
320 if got := ToJSON(a); got != "null" {
321 t.Errorf("ToJSON(cycle) = %.40q, want null", got)
322 }
323 if _, err := EncodeJSON(a, -1); err == nil || !strings.Contains(err.Error(), "nested too deeply") {
324 t.Errorf("EncodeJSON(cycle) err = %v", err)
325 }
326 d := NewDictionary()
327 d.Add("self", d)
328 if _, err := EncodeJSON(d, -1); err == nil {
329 t.Error("dictionary cycle encoded")
330 }
331 // Evaluated: toJSON(cycle) is an *EvalError, not a stack overflow.
332 _, err := evalWith(t, "toJSON(big)", EvalContext{Contexts: map[string]Value{"big": a}})
333 _ = asEvalError(t, err)
334 // Everything within MaxJSONDepth still works, and the cut is exact.
335 deep := Value(Number(1))
336 for i := 0; i < MaxJSONDepth; i++ {
337 deep = NewArray(deep)
338 }
339 if _, err := EncodeJSON(deep, -1); err != nil {
340 t.Errorf("depth %d: %v", MaxJSONDepth, err)
341 }
342 if _, err := EncodeJSON(NewArray(deep), -1); err == nil {
343 t.Errorf("depth %d accepted", MaxJSONDepth+1)
344 }
345}
346
347func TestEncodeJSONLimit(t *testing.T) {
348 a := bigArray(100)
349 full, err := EncodeJSON(a, -1)
350 if err != nil {
351 t.Fatal(err)
352 }
353 if got, err := EncodeJSON(a, len(full)); err != nil || got != full {
354 t.Errorf("exact limit: %v", err)
355 }
356 if _, err := EncodeJSON(a, len(full)-1); err == nil {
357 t.Error("one byte over the limit accepted")
358 }
359 if _, err := EncodeJSON(String(strings.Repeat("a", 100)), 50); err == nil {
360 t.Error("long string over the limit accepted")
361 }
362 if got, err := EncodeJSON(Null{}, 0); err == nil {
363 t.Errorf("limit 0: got %q", got)
364 }
365}
366
367func TestOverLongInputIsRejectedCheaply(t *testing.T) {
368 huge := strings.Repeat("a", 64<<20)
369 allocs := testing.AllocsPerRun(3, func() {
370 if _, err := Lex(huge); err == nil {
371 t.Fatal("64 MiB expression accepted")
372 }
373 })
374 if allocs > 3 {
375 t.Errorf("rejecting a 64 MiB expression allocated %v times", allocs)
376 }
377 if exceedsUTF16Len("😀", 1) != true || exceedsUTF16Len("😀", 2) || exceedsUTF16Len("ab", 2) || !exceedsUTF16Len("abc", 2) || exceedsUTF16Len("", 0) {
378 t.Error("exceedsUTF16Len")
379 }
380 if exceedsUTF16Len("\xff\xff", 2) || !exceedsUTF16Len("\xff\xff\xff", 2) {
381 t.Error("invalid bytes count as one unit each")
382 }
383}
384
385// The case tables are generated relative to the Unicode version of the Go
386// toolchain: another toolchain needs them regenerated.
387func TestCasingTablesMatchGoUnicodeVersion(t *testing.T) {
388 if unicode.Version != casingGoUnicodeVersion {
389 t.Errorf("casing_tables.go was generated with Go's Unicode %s but this toolchain has %s: regenerate with `go generate ./expr` (needs node) and commit the result",
390 casingGoUnicodeVersion, unicode.Version)
391 }
392}
393
394func TestWTF8Helpers(t *testing.T) {
395 hi := "\xed\xa0\x80" // U+D800
396 lo := "\xed\xb0\x80" // U+DC00
397 if !hasWTF8(hi) || hasWTF8("abc") || hasWTF8("é\xed") {
398 t.Error("hasWTF8")
399 }
400 if r, w := decodeRune(hi); r != 0xD800 || w != 3 {
401 t.Errorf("decodeRune = %U, %d", r, w)
402 }
403 for _, f := range []func(string) string{jsToUpper, toUpperSpecial, jsToLower, normalizeWTF8} {
404 if got := f("a" + hi + "b"); !strings.Contains(got, hi) || strings.Contains(got, "\ufffd") {
405 t.Errorf("lone surrogate not preserved: %q", got)
406 }
407 }
408 if got := normalizeWTF8("\xed\xa0\xbd\xed\xb8\x80"); got != "😀" {
409 t.Errorf("surrogate pair not joined: %q", got)
410 }
411 if got := normalizeWTF8(lo + hi); got != lo+hi {
412 t.Errorf("reversed pair joined: %q", got)
413 }
414 if foldKey(hi) != hi || foldKey("a"+hi) != "A"+hi {
415 t.Error("foldKey")
416 }
417 if compareUTF16(hi, "\ue000") >= 0 || compareUTF16(lo, "\ue000") >= 0 || compareUTF16(hi, "\U00010000") >= 0 {
418 t.Error("lone surrogates sort before U+E000 and before supplementary characters starting with the same unit")
419 }
420 if !jsIncludes("\U0001F600", "\xed\xa0\xbd") || !jsHasPrefix("\U0001F600", "\xed\xa0\xbd") || !jsHasSuffix("\U0001F600", "\xed\xb8\x80") {
421 t.Error("search by lone surrogate inside a supplementary character")
422 }
423}
424
425func TestLoneSurrogateExpressions(t *testing.T) {
426 // Json.NET turns an unpaired surrogate escape into U+FFFD, so the
427 // runner has no lone surrogates (JavaScript strings do: see PORTING.md).
428 runEvalCases(t, []evalCase{
429 {`fromJSON('"\ud800"') == fromJSON('"\udc00"')`, "Boolean:true"},
430 {"fromJSON('\"\\ud800\"') == '\ufffd'", "Boolean:true"},
431 {`fromJSON('"\ud800"') < fromJSON('"\udc00"')`, "Boolean:false"},
432 {`contains(fromJSON('"\ud83d\ude00"'), fromJSON('"\ud83d"'))`, "Boolean:false"},
433 {`fromJSON('"\ud83d\ude00"') == '😀'`, "Boolean:true"},
434 {`format('{0}{1}', fromJSON('"\ud83d"'), fromJSON('"\ude00"')) == '😀'`, "Boolean:false"},
435 {`toJSON(fromJSON('"\ud800"'))`, "String:\"\ufffd\""},
436 })
437}