1// SPDX-License-Identifier: MIT
2
3package expr
4
5import (
6 "context"
7 "regexp"
8 "strings"
9 "testing"
10 "unicode/utf8"
11)
12
13// Seeds for the fuzz targets: the corpus of the table tests and a few shapes
14// that stress the lexer and the parser.
15var fuzzSeeds = []string{
16 "", " ", "true", "github.event_name == 'push'", "1 == '1'", "'it''s'", "'unterminated", "a-b", "NaN", "-Infinity", "0x1F", "1e3", ".5", "5.",
17 "github.event.commits.*.id", "github['x'][0].*", "contains(github.ref, 'main') && !failure()", "format('{0} {{}} {1}', 1, null)",
18 "fromJSON('[1,{\"a\":null}]')[1].a", "toJSON(fromJSON('{\"b\":1,\"1\":2}'))", "join(matrix.node.*, ', ')", "case(true, 1, 2)", "case(false, 1, true, 2, 3)",
19 "((((((((((1))))))))))", "!!!!!!true", "1 || 2 && 3 == 4 < 5", "hashFiles('**/*.go', '!vendor/**')", "success() && always()", "\n\t \r", "\u00a0", "'😀' == '\U00010000'",
20 "=", "&", "|", "!=", "<=", ">=", "()", "(1", "1)", "a.", ".a", "a..b", "a[", "a[]", "a[*]", "*", "a.*.*", "1.2.3", "--1", "1_000", "'\xed\xa0\x80'",
21 "fromJSON('\"\\ud800\"') == fromJSON('\"\\udc00\"')", "format('{0}{1}', fromJSON('\"\\ud83d\"'), fromJSON('\"\\ude00\"'))", "contains(fromJSON('\"\\ud83d\\ude00\"'), fromJSON('\"\\ude00\"'))", "format('{0}{0}', format('{0}{0}', 'xxxxxxxx'))", "github.event.commits.*.*.*", "format('{0:x}{', 1)", "format('}}{{', 1)", "contains(1,2,3)", "ß == 'SS'", "İ", "'ı' == 'I'", "'\u03a3' < 'z'",
22}
23
24func addSeeds(f *testing.F) {
25 for _, s := range fuzzSeeds {
26 f.Add(s)
27 }
28}
29
30// FuzzLex checks that lexing never panics, that it is deterministic, and
31// that successful lexing yields ordered tokens ending with exactly one EOF.
32func FuzzLex(f *testing.F) {
33 addSeeds(f)
34 f.Fuzz(func(t *testing.T, s string) {
35 toks, err := Lex(s)
36 toks2, err2 := Lex(s)
37 if (err == nil) != (err2 == nil) || len(toks) != len(toks2) {
38 t.Fatal("lexing is not deterministic")
39 }
40 if err != nil {
41 if _, ok := err.(*Error); !ok {
42 t.Fatalf("error is %T, not *Error", err)
43 }
44 return
45 }
46 if len(toks) == 0 || toks[len(toks)-1].Type != TokenEOF {
47 t.Fatal("token stream does not end with EOF")
48 }
49 for i, tk := range toks {
50 if tk.Type == TokenEOF && i != len(toks)-1 {
51 t.Fatal("EOF in the middle of the token stream")
52 }
53 if tk.Type != TokenEOF && tk.Lexeme == "" {
54 t.Fatalf("empty lexeme for token %v", tk.Type)
55 }
56 if !utf8.ValidString(tk.Lexeme) && utf8.ValidString(s) {
57 t.Fatalf("invalid UTF-8 lexeme %q from valid input", tk.Lexeme)
58 }
59 // The EOF token of the reference starts at a stale offset, so after
60 // a trailing newline its start column is -1; every other token
61 // has a column of at least 0.
62 if tk.Range.Start.Line < 0 || (tk.Type != TokenEOF && tk.Range.Start.Column < 0) || tk.Range.End.Line < tk.Range.Start.Line {
63 t.Fatalf("bad range %+v", tk.Range)
64 }
65 }
66 })
67}
68
69// FuzzParse checks that parsing never panics, that errors are *Error and
70// that the depth limit holds: no accepted expression nests deeper than the
71// parser allows.
72func FuzzParse(f *testing.F) {
73 addSeeds(f)
74 f.Fuzz(func(t *testing.T, s string) {
75 node, err := Parse(s, []string{"github", "matrix", "env"}, []FuncInfo{{Name: "hashFiles", MinArgs: 1, MaxArgs: -1}, {Name: "success"}})
76 if err != nil {
77 if _, ok := err.(*Error); !ok {
78 t.Fatalf("error is %T, not *Error", err)
79 }
80 if node != nil {
81 t.Fatal("node returned with an error")
82 }
83 return
84 }
85 if node == nil && strings.TrimFunc(s, isNetSpace) != "" {
86 t.Fatalf("empty tree for non-blank input %q", s)
87 }
88 if d := nodeDepth(node); d > 2*MaxParserDepth+2 {
89 t.Fatalf("tree depth %d exceeds the parser limit", d)
90 }
91 })
92}
93
94func nodeDepth(n Node) int {
95 switch n := n.(type) {
96 case *Unary:
97 return 1 + nodeDepth(n.Expr)
98 case *Binary:
99 return 1 + max(nodeDepth(n.Left), nodeDepth(n.Right))
100 case *Logical:
101 d := 0
102 for _, a := range n.Args {
103 d = max(d, nodeDepth(a))
104 }
105 return 1 + d
106 case *Grouping:
107 return 1 + nodeDepth(n.Group)
108 case *IndexAccess:
109 return 1 + max(nodeDepth(n.Expr), nodeDepth(n.Index))
110 case *FunctionCall:
111 d := 0
112 for _, a := range n.Args {
113 d = max(d, nodeDepth(a))
114 }
115 return 1 + d
116 }
117 return 1
118}
119
120// FuzzEvaluate checks that evaluating an arbitrary parsed expression never
121// panics, always returns a usable value or an *EvalError, and leaves the
122// context untouched.
123func FuzzEvaluate(f *testing.F) {
124 addSeeds(f)
125 ctx := EvalContext{
126 Contexts: map[string]Value{
127 "github": mustJSON(f, `{"event_name":"push","ref":"refs/heads/main","event":{"commits":[{"id":"1","added":["a"]},{"id":"2"},{"x":[[1],[2,3]]}],"n":12,"nested":[[1,2],[3]]}}`),
128 "matrix": mustJSON(f, `{"node":[14,16],"os":"linux","o":{"k":null}}`),
129 "env": mustJSON(f, `{"A":"","B":"1","C":"x","J":"{\"a\":[1,2]}"}`),
130 },
131 Funcs: map[string]Func{
132 "hashfiles": func(_ context.Context, args []Value) (Value, error) { return String("h"), nil },
133 "success": func(context.Context, []Value) (Value, error) { return Boolean(true), nil },
134 },
135 }
136 before := map[string]string{}
137 for k, v := range ctx.Contexts {
138 before[k] = ToJSON(v)
139 }
140 f.Fuzz(func(t *testing.T, s string) {
141 node, err := Parse(s, []string{"github", "matrix", "env"}, []FuncInfo{{Name: "hashFiles", MinArgs: 1, MaxArgs: -1}, {Name: "success"}})
142 if err != nil || node == nil {
143 return
144 }
145 v, err := Evaluate(context.Background(), node, ctx)
146 if err != nil {
147 if _, ok := err.(*EvalError); !ok {
148 t.Fatalf("error is %T, not *EvalError", err)
149 }
150 return
151 }
152 if v == nil {
153 t.Fatal("nil value without error")
154 }
155 _ = CoerceString(v)
156 _ = Truthy(v)
157 j := ToJSON(v)
158 if !utf8.ValidString(j) {
159 t.Fatalf("toJSON produced invalid UTF-8: %q", j)
160 }
161 if _, err := FromJSON([]byte(j)); err != nil && !hasNonFinite(j) {
162 t.Fatalf("toJSON output does not parse: %v\n%s", err, j)
163 }
164 for k, c := range ctx.Contexts {
165 if ToJSON(c) != before[k] {
166 t.Fatalf("context %s was modified", k)
167 }
168 }
169 })
170}
171
172// FuzzFromJSON checks that FromJSON never panics and that whatever it
173// accepts prints as JSON that parses back to the same text.
174func FuzzFromJSON(f *testing.F) {
175 for _, s := range []string{`null`, `{"a":[1,2,{"b":null}]}`, `"\ud83d\ude00"`, `{"1":1,"a":2,"01":3}`, `[1e999]`, `-0`, `"\ud800"`, `{"a":1,"A":2}`, `[`, `{"a"`, "\"\x01\""} {
176 f.Add(s)
177 }
178 // The corpus recorded from the runner: every input it was asked about
179 // (leading zeros, slashes, commas, literals, mutations of those).
180 for _, c := range loadFromJSONCases(f) {
181 f.Add(c.In)
182 }
183 f.Fuzz(func(t *testing.T, s string) {
184 v, err := FromJSON([]byte(s))
185 if err != nil {
186 return
187 }
188 j := ToJSON(v)
189 v2, err := FromJSON([]byte(j))
190 if err != nil && hasNonFinite(j) {
191 return
192 }
193 if err != nil {
194 t.Fatalf("round trip failed: %v\n%s", err, j)
195 }
196 // A negative zero is written "-0" and read back as the integer 0.
197 if j2 := ToJSON(v2); j2 != j && negZeroLine.ReplaceAllString(j, "${1}0${2}") != j2 {
198 t.Fatalf("round trip changed output:\n%s\n%s", j, j2)
199 }
200 })
201}
202
203// hasNonFinite reports whether toJSON output holds NaN or an infinity, which
204// the runner writes as bare words (not JSON).
205func hasNonFinite(j string) bool {
206 return strings.Contains(j, "NaN") || strings.Contains(j, "Infinity")
207}
208
209// negZeroLine matches a written negative zero: "-0" alone on its value.
210var negZeroLine = regexp.MustCompile(`(^|[\s\[:,])-0($|[\s,\]}])`)