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.
208 //nolint:staticcheck // deliberately passing nil
209 if v, err := Evaluate(nil, n, EvalContext{}); err != nil || v != Boolean(true) {
210 t.Errorf("nil context: %v, %v", v, err)
211 }
212}
213
214func TestFuncReceivesContext(t *testing.T) {
215 type key struct{}
216 ctx := context.WithValue(context.Background(), key{}, "marker")
217 var got any
218 ec := EvalContext{Funcs: map[string]Func{"probe": func(c context.Context, _ []Value) (Value, error) {
219 got = c.Value(key{})
220 return Null{}, nil
221 }}}
222 if _, err := Evaluate(ctx, mustParse(t, "probe()", nil, []FuncInfo{{Name: "probe"}}), ec); err != nil {
223 t.Fatal(err)
224 }
225 if got != "marker" {
226 t.Errorf("function did not receive the evaluation context: %v", got)
227 }
228}
229
230func TestHandBuiltASTArity(t *testing.T) {
231 call := func(name string, n int) Node {
232 args := make([]Node, n)
233 for i := range args {
234 args[i] = &Literal{Value: String("x")}
235 }
236 return &FunctionCall{Name: Token{Type: TokenIdentifier, Lexeme: name}, Args: args}
237 }
238 for _, tc := range []struct {
239 name string
240 n int
241 want string
242 }{
243 {"contains", 0, "Too few parameters supplied: 'contains'"},
244 {"contains", 1, "Too few parameters supplied: 'contains'"},
245 {"contains", 3, "Too many parameters supplied: 'contains'"},
246 {"startsWith", 1, "Too few parameters supplied: 'startsWith'"},
247 {"endsWith", 0, "Too few parameters supplied: 'endsWith'"},
248 {"join", 0, "Too few parameters supplied: 'join'"},
249 {"join", 3, "Too many parameters supplied: 'join'"},
250 {"toJSON", 0, "Too few parameters supplied: 'toJSON'"},
251 {"fromJSON", 2, "Too many parameters supplied: 'fromJSON'"},
252 {"format", 0, "Too few parameters supplied: 'format'"},
253 {"format", 256, "Too many parameters supplied: 'format'"},
254 {"case", 0, "Too few parameters supplied: 'case'"},
255 {"case", 2, "Too few parameters supplied: 'case'"},
256 {"case", 4, "Even number of parameters supplied, requires an odd number of parameters: 'case'"},
257 {"nosuch", 1, "function nosuch is not implemented"},
258 } {
259 var err error
260 func() {
261 defer func() {
262 if r := recover(); r != nil {
263 t.Errorf("%s(%d args) panicked: %v", tc.name, tc.n, r)
264 }
265 }()
266 _, err = Evaluate(context.Background(), call(tc.name, tc.n), EvalContext{})
267 }()
268 if ee := (&EvalError{}); !errors.As(err, &ee) || ee.Message != tc.want {
269 t.Errorf("%s(%d args): err = %v, want %q", tc.name, tc.n, err, tc.want)
270 }
271 }
272 // Other malformed trees must not panic either.
273 for _, n := range []Node{&Star{}, &Logical{}, &Binary{Left: &Literal{}, Right: &Literal{}}, &IndexAccess{Expr: &Literal{}, Index: &Literal{}}, &Literal{Value: nil}, &Unary{Expr: &Literal{}}} {
274 if _, err := Evaluate(context.Background(), n, EvalContext{}); err != nil {
275 _ = asEvalError(t, err)
276 }
277 }
278}
279
280func TestEvalDepthCap(t *testing.T) {
281 var n Node = &Literal{Value: Boolean(true)}
282 for i := 0; i < maxEvalDepth+10; i++ {
283 n = &Grouping{Group: n}
284 }
285 _, err := Evaluate(context.Background(), n, EvalContext{})
286 if ee := asEvalError(t, err); !strings.Contains(ee.Message, "deeper than") {
287 t.Errorf("message = %q", ee.Message)
288 }
289}
290
291func TestExtensionErrorsAreWrapped(t *testing.T) {
292 sentinel := errors.New("kaput")
293 ec := EvalContext{Funcs: map[string]Func{
294 "boom": func(context.Context, []Value) (Value, error) { return nil, sentinel },
295 "wrapped": func(context.Context, []Value) (Value, error) { return nil, fmt.Errorf("while hashing: %w", sentinel) },
296 "already": func(context.Context, []Value) (Value, error) { return nil, &EvalError{Message: "mine"} },
297 }}
298 infos := []FuncInfo{{Name: "boom"}, {Name: "wrapped"}, {Name: "already"}}
299 for src, msg := range map[string]string{"boom()": "kaput", "wrapped()": "while hashing: kaput", "already()": "mine"} {
300 _, err := Evaluate(context.Background(), mustParse(t, src, nil, infos), ec)
301 ee := asEvalError(t, err)
302 if ee.Message != msg {
303 t.Errorf("%s: message %q, want %q", src, ee.Message, msg)
304 }
305 if src != "already()" && (!errors.Is(err, sentinel) || ee.Unwrap() == nil) {
306 t.Errorf("%s: sentinel not reachable with errors.Is", src)
307 }
308 }
309}
310
311func cyclic() *Array {
312 a := NewArray()
313 a.Append(a)
314 return a
315}
316
317func TestToJSONCycle(t *testing.T) {
318 a := cyclic()
319 if got := ToJSON(a); got != "null" {
320 t.Errorf("ToJSON(cycle) = %.40q, want null", got)
321 }
322 if _, err := EncodeJSON(a, -1); err == nil || !strings.Contains(err.Error(), "nested too deeply") {
323 t.Errorf("EncodeJSON(cycle) err = %v", err)
324 }
325 d := NewDictionary()
326 d.Add("self", d)
327 if _, err := EncodeJSON(d, -1); err == nil {
328 t.Error("dictionary cycle encoded")
329 }
330 // Evaluated: toJSON(cycle) is an *EvalError, not a stack overflow.
331 _, err := evalWith(t, "toJSON(big)", EvalContext{Contexts: map[string]Value{"big": a}})
332 _ = asEvalError(t, err)
333 // Everything within MaxJSONDepth still works, and the cut is exact.
334 deep := Value(Number(1))
335 for i := 0; i < MaxJSONDepth; i++ {
336 deep = NewArray(deep)
337 }
338 if _, err := EncodeJSON(deep, -1); err != nil {
339 t.Errorf("depth %d: %v", MaxJSONDepth, err)
340 }
341 if _, err := EncodeJSON(NewArray(deep), -1); err == nil {
342 t.Errorf("depth %d accepted", MaxJSONDepth+1)
343 }
344}
345
346func TestEncodeJSONLimit(t *testing.T) {
347 a := bigArray(100)
348 full, err := EncodeJSON(a, -1)
349 if err != nil {
350 t.Fatal(err)
351 }
352 if got, err := EncodeJSON(a, len(full)); err != nil || got != full {
353 t.Errorf("exact limit: %v", err)
354 }
355 if _, err := EncodeJSON(a, len(full)-1); err == nil {
356 t.Error("one byte over the limit accepted")
357 }
358 if _, err := EncodeJSON(String(strings.Repeat("a", 100)), 50); err == nil {
359 t.Error("long string over the limit accepted")
360 }
361 if got, err := EncodeJSON(Null{}, 0); err == nil {
362 t.Errorf("limit 0: got %q", got)
363 }
364}
365
366func TestOverLongInputIsRejectedCheaply(t *testing.T) {
367 huge := strings.Repeat("a", 64<<20)
368 allocs := testing.AllocsPerRun(3, func() {
369 if _, err := Lex(huge); err == nil {
370 t.Fatal("64 MiB expression accepted")
371 }
372 })
373 if allocs > 3 {
374 t.Errorf("rejecting a 64 MiB expression allocated %v times", allocs)
375 }
376 if exceedsUTF16Len("😀", 1) != true || exceedsUTF16Len("😀", 2) || exceedsUTF16Len("ab", 2) || !exceedsUTF16Len("abc", 2) || exceedsUTF16Len("", 0) {
377 t.Error("exceedsUTF16Len")
378 }
379 if exceedsUTF16Len("\xff\xff", 2) || !exceedsUTF16Len("\xff\xff\xff", 2) {
380 t.Error("invalid bytes count as one unit each")
381 }
382}
383
384// The case tables are generated relative to the Unicode version of the Go
385// toolchain: another toolchain needs them regenerated.
386func TestCasingTablesMatchGoUnicodeVersion(t *testing.T) {
387 if unicode.Version != casingGoUnicodeVersion {
388 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",
389 casingGoUnicodeVersion, unicode.Version)
390 }
391}
392
393func TestWTF8Helpers(t *testing.T) {
394 hi := "\xed\xa0\x80" // U+D800
395 lo := "\xed\xb0\x80" // U+DC00
396 if !hasWTF8(hi) || hasWTF8("abc") || hasWTF8("é\xed") {
397 t.Error("hasWTF8")
398 }
399 if r, w := decodeRune(hi); r != 0xD800 || w != 3 {
400 t.Errorf("decodeRune = %U, %d", r, w)
401 }
402 for _, f := range []func(string) string{jsToUpper, toUpperSpecial, jsToLower, normalizeWTF8} {
403 if got := f("a" + hi + "b"); !strings.Contains(got, hi) || strings.Contains(got, "\ufffd") {
404 t.Errorf("lone surrogate not preserved: %q", got)
405 }
406 }
407 if got := normalizeWTF8("\xed\xa0\xbd\xed\xb8\x80"); got != "😀" {
408 t.Errorf("surrogate pair not joined: %q", got)
409 }
410 if got := normalizeWTF8(lo + hi); got != lo+hi {
411 t.Errorf("reversed pair joined: %q", got)
412 }
413 if foldKey(hi) != hi || foldKey("a"+hi) != "A"+hi {
414 t.Error("foldKey")
415 }
416 if compareUTF16(hi, "\ue000") >= 0 || compareUTF16(lo, "\ue000") >= 0 || compareUTF16(hi, "\U00010000") >= 0 {
417 t.Error("lone surrogates sort before U+E000 and before supplementary characters starting with the same unit")
418 }
419 if !jsIncludes("\U0001F600", "\xed\xa0\xbd") || !jsHasPrefix("\U0001F600", "\xed\xa0\xbd") || !jsHasSuffix("\U0001F600", "\xed\xb8\x80") {
420 t.Error("search by lone surrogate inside a supplementary character")
421 }
422}
423
424func TestLoneSurrogateExpressions(t *testing.T) {
425 // Json.NET turns an unpaired surrogate escape into U+FFFD, so the
426 // runner has no lone surrogates (JavaScript strings do: see PORTING.md).
427 runEvalCases(t, []evalCase{
428 {`fromJSON('"\ud800"') == fromJSON('"\udc00"')`, "Boolean:true"},
429 {"fromJSON('\"\\ud800\"') == '\ufffd'", "Boolean:true"},
430 {`fromJSON('"\ud800"') < fromJSON('"\udc00"')`, "Boolean:false"},
431 {`contains(fromJSON('"\ud83d\ude00"'), fromJSON('"\ud83d"'))`, "Boolean:false"},
432 {`fromJSON('"\ud83d\ude00"') == '😀'`, "Boolean:true"},
433 {`format('{0}{1}', fromJSON('"\ud83d"'), fromJSON('"\ude00"')) == '😀'`, "Boolean:false"},
434 {`toJSON(fromJSON('"\ud800"'))`, "String:\"\ufffd\""},
435 })
436}