fork of https://github.com/sourcegraph/zoekt
1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package syntaxutil
6
7import (
8 "fmt"
9 "strings"
10 "testing"
11 "unicode"
12)
13
14type parseTest struct {
15 Regexp string
16 Dump string
17}
18
19var parseTests = []parseTest{
20 // Base cases
21 {`a`, `lit{a}`},
22 {`a.`, `cat{lit{a}dot{}}`},
23 {`a.b`, `cat{lit{a}dot{}lit{b}}`},
24 {`ab`, `str{ab}`},
25 {`a.b.c`, `cat{lit{a}dot{}lit{b}dot{}lit{c}}`},
26 {`abc`, `str{abc}`},
27 {`a|^`, `alt{lit{a}bol{}}`},
28 {`a|b`, `cc{0x61-0x62}`},
29 {`(a)`, `cap{lit{a}}`},
30 {`(a)|b`, `alt{cap{lit{a}}lit{b}}`},
31 {`a*`, `star{lit{a}}`},
32 {`a+`, `plus{lit{a}}`},
33 {`a?`, `que{lit{a}}`},
34 {`a{2}`, `rep{2,2 lit{a}}`},
35 {`a{2,3}`, `rep{2,3 lit{a}}`},
36 {`a{2,}`, `rep{2,-1 lit{a}}`},
37 {`a*?`, `nstar{lit{a}}`},
38 {`a+?`, `nplus{lit{a}}`},
39 {`a??`, `nque{lit{a}}`},
40 {`a{2}?`, `nrep{2,2 lit{a}}`},
41 {`a{2,3}?`, `nrep{2,3 lit{a}}`},
42 {`a{2,}?`, `nrep{2,-1 lit{a}}`},
43 // Malformed { } are treated as literals.
44 {`x{1001`, `str{x{1001}`},
45 {`x{9876543210`, `str{x{9876543210}`},
46 {`x{9876543210,`, `str{x{9876543210,}`},
47 {`x{2,1`, `str{x{2,1}`},
48 {`x{1,9876543210`, `str{x{1,9876543210}`},
49 {``, `emp{}`},
50 {`|`, `emp{}`}, // alt{emp{}emp{}} but got factored
51 {`|x|`, `alt{emp{}lit{x}emp{}}`},
52 {`.`, `dot{}`},
53 {`^`, `bol{}`},
54 {`$`, `eol{}`},
55 {`\|`, `lit{|}`},
56 {`\(`, `lit{(}`},
57 {`\)`, `lit{)}`},
58 {`\*`, `lit{*}`},
59 {`\+`, `lit{+}`},
60 {`\?`, `lit{?}`},
61 {`{`, `lit{{}`},
62 {`}`, `lit{}}`},
63 {`\.`, `lit{.}`},
64 {`\^`, `lit{^}`},
65 {`\$`, `lit{$}`},
66 {`\\`, `lit{\}`},
67 {`[ace]`, `cc{0x61 0x63 0x65}`},
68 {`[abc]`, `cc{0x61-0x63}`},
69 {`[a-z]`, `cc{0x61-0x7a}`},
70 {`[a]`, `lit{a}`},
71 {`\-`, `lit{-}`},
72 {`-`, `lit{-}`},
73 {`\_`, `lit{_}`},
74 {`abc`, `str{abc}`},
75 {`abc|def`, `alt{str{abc}str{def}}`},
76 {`abc|def|ghi`, `alt{str{abc}str{def}str{ghi}}`},
77
78 // Posix and Perl extensions
79 {`[[:lower:]]`, `cc{0x61-0x7a}`},
80 {`[a-z]`, `cc{0x61-0x7a}`},
81 {`[^[:lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
82 {`[[:^lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
83 {`(?i)[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
84 {`(?i)[a-z]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
85 {`(?i)[^[:lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
86 {`(?i)[[:^lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
87 {`\d`, `cc{0x30-0x39}`},
88 {`\D`, `cc{0x0-0x2f 0x3a-0x10ffff}`},
89 {`\s`, `cc{0x9-0xa 0xc-0xd 0x20}`},
90 {`\S`, `cc{0x0-0x8 0xb 0xe-0x1f 0x21-0x10ffff}`},
91 {`\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a}`},
92 {`\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x10ffff}`},
93 {`(?i)\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a 0x17f 0x212a}`},
94 {`(?i)\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
95 {`[^\\]`, `cc{0x0-0x5b 0x5d-0x10ffff}`},
96 // { `\C`, `byte{}` }, // probably never
97
98 // Unicode, negatives, and a double negative.
99 {`\p{Braille}`, `cc{0x2800-0x28ff}`},
100 {`\P{Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
101 {`\p{^Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
102 {`\P{^Braille}`, `cc{0x2800-0x28ff}`},
103 {`\pZ`, `cc{0x20 0xa0 0x1680 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
104 {`[\p{Braille}]`, `cc{0x2800-0x28ff}`},
105 {`[\P{Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
106 {`[\p{^Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
107 {`[\P{^Braille}]`, `cc{0x2800-0x28ff}`},
108 {`[\pZ]`, `cc{0x20 0xa0 0x1680 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
109 {`\p{Lu}`, mkCharClass(unicode.IsUpper)},
110 {`[\p{Lu}]`, mkCharClass(unicode.IsUpper)},
111 {`(?i)[\p{Lu}]`, mkCharClass(isUpperFold)},
112 {`\p{Any}`, `dot{}`},
113 {`\p{^Any}`, `cc{}`},
114
115 // Hex, octal.
116 {`[\012-\234]\141`, `cat{cc{0xa-0x9c}lit{a}}`},
117 {`[\x{41}-\x7a]\x61`, `cat{cc{0x41-0x7a}lit{a}}`},
118
119 // More interesting regular expressions.
120 {`a{,2}`, `str{a{,2}}`},
121 {`\.\^\$\\`, `str{.^$\}`},
122 {`[a-zABC]`, `cc{0x41-0x43 0x61-0x7a}`},
123 {`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
124 {`[α-ε☺]`, `cc{0x3b1-0x3b5 0x263a}`}, // utf-8
125 {`a*{`, `cat{star{lit{a}}lit{{}}`},
126
127 // Test precedences
128 {`(?:ab)*`, `star{str{ab}}`},
129 {`(ab)*`, `star{cap{str{ab}}}`},
130 {`ab|cd`, `alt{str{ab}str{cd}}`},
131 {`a(b|c)d`, `cat{lit{a}cap{cc{0x62-0x63}}lit{d}}`},
132
133 // Test flattening.
134 {`(?:a)`, `lit{a}`},
135 {`(?:ab)(?:cd)`, `str{abcd}`},
136 {`(?:a+b+)(?:c+d+)`, `cat{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
137 {`(?:a+|b+)|(?:c+|d+)`, `alt{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
138 {`(?:a|b)|(?:c|d)`, `cc{0x61-0x64}`},
139 {`a|.`, `dot{}`},
140 {`.|a`, `dot{}`},
141 {`(?:[abc]|A|Z|hello|world)`, `alt{cc{0x41 0x5a 0x61-0x63}str{hello}str{world}}`},
142 {`(?:[abc]|A|Z)`, `cc{0x41 0x5a 0x61-0x63}`},
143
144 // Test Perl quoted literals
145 {`\Q+|*?{[\E`, `str{+|*?{[}`},
146 {`\Q+\E+`, `plus{lit{+}}`},
147 {`\Qab\E+`, `cat{lit{a}plus{lit{b}}}`},
148 {`\Q\\E`, `lit{\}`},
149 {`\Q\\\E`, `str{\\}`},
150
151 // Test Perl \A and \z
152 {`(?m)^`, `bol{}`},
153 {`(?m)$`, `eol{}`},
154 {`(?-m)^`, `bot{}`},
155 {`(?-m)$`, `eot{}`},
156 {`(?m)\A`, `bot{}`},
157 {`(?m)\z`, `eot{\z}`},
158 {`(?-m)\A`, `bot{}`},
159 {`(?-m)\z`, `eot{\z}`},
160
161 // Test named captures
162 {`(?P<name>a)`, `cap{name:lit{a}}`},
163 {`(?<name>a)`, `cap{name:lit{a}}`},
164
165 // Case-folded literals
166 {`[Aa]`, `litfold{A}`},
167 {`[\x{100}\x{101}]`, `litfold{Ā}`},
168 {`[Δδ]`, `litfold{Δ}`},
169
170 // Strings
171 {`abcde`, `str{abcde}`},
172 {`[Aa][Bb]cd`, `cat{strfold{AB}str{cd}}`},
173
174 // Factoring.
175 {`abc|abd|aef|bcx|bcy`, `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}cat{str{bc}cc{0x78-0x79}}}`},
176 {`ax+y|ax+z|ay+w`, `cat{lit{a}alt{cat{plus{lit{x}}lit{y}}cat{plus{lit{x}}lit{z}}cat{plus{lit{y}}lit{w}}}}`},
177
178 // Bug fixes.
179 {`(?:.)`, `dot{}`},
180 {`(?:x|(?:xa))`, `cat{lit{x}alt{emp{}lit{a}}}`},
181 {`(?:.|(?:.a))`, `cat{dot{}alt{emp{}lit{a}}}`},
182 {`(?:A(?:A|a))`, `cat{lit{A}litfold{A}}`},
183 {`(?:A|a)`, `litfold{A}`},
184 {`A|(?:A|a)`, `litfold{A}`},
185 {`(?s).`, `dot{}`},
186 {`(?-s).`, `dnl{}`},
187 {`(?:(?:^).)`, `cat{bol{}dot{}}`},
188 {`(?-s)(?:(?:^).)`, `cat{bol{}dnl{}}`},
189 {`[\s\S]a`, `cat{cc{0x0-0x10ffff}lit{a}}`},
190
191 // RE2 prefix_tests
192 {`abc|abd`, `cat{str{ab}cc{0x63-0x64}}`},
193 {`a(?:b)c|abd`, `cat{str{ab}cc{0x63-0x64}}`},
194 {`abc|abd|aef|bcx|bcy`,
195 `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}` +
196 `cat{str{bc}cc{0x78-0x79}}}`},
197 {`abc|x|abd`, `alt{str{abc}lit{x}str{abd}}`},
198 {`(?i)abc|ABD`, `cat{strfold{AB}cc{0x43-0x44 0x63-0x64}}`},
199 {`[ab]c|[ab]d`, `cat{cc{0x61-0x62}cc{0x63-0x64}}`},
200 {`.c|.d`, `cat{dot{}cc{0x63-0x64}}`},
201 {`x{2}|x{2}[0-9]`,
202 `cat{rep{2,2 lit{x}}alt{emp{}cc{0x30-0x39}}}`},
203 {`x{2}y|x{2}[0-9]y`,
204 `cat{rep{2,2 lit{x}}alt{lit{y}cat{cc{0x30-0x39}lit{y}}}}`},
205 {`a.*?c|a.*?b`,
206 `cat{lit{a}alt{cat{nstar{dot{}}lit{c}}cat{nstar{dot{}}lit{b}}}}`},
207
208 // Valid repetitions.
209 {`((((((((((x{2}){2}){2}){2}){2}){2}){2}){2}){2}))`, ``},
210 {`((((((((((x{1}){2}){2}){2}){2}){2}){2}){2}){2}){2})`, ``},
211
212 // Valid nesting.
213 {strings.Repeat("(", 999) + strings.Repeat(")", 999), ``},
214 {strings.Repeat("(?:", 999) + strings.Repeat(")*", 999), ``},
215 {"(" + strings.Repeat("|", 12345) + ")", ``}, // not nested at all
216}
217
218const testFlags = MatchNL | PerlX | UnicodeGroups
219
220// dump prints a string representation of the regexp showing
221// the structure explicitly.
222func dump(re *Regexp) string {
223 var b strings.Builder
224 dumpRegexp(&b, re)
225 return b.String()
226}
227
228var opNames = []string{
229 OpNoMatch: "no",
230 OpEmptyMatch: "emp",
231 OpLiteral: "lit",
232 OpCharClass: "cc",
233 OpAnyCharNotNL: "dnl",
234 OpAnyChar: "dot",
235 OpBeginLine: "bol",
236 OpEndLine: "eol",
237 OpBeginText: "bot",
238 OpEndText: "eot",
239 OpWordBoundary: "wb",
240 OpNoWordBoundary: "nwb",
241 OpCapture: "cap",
242 OpStar: "star",
243 OpPlus: "plus",
244 OpQuest: "que",
245 OpRepeat: "rep",
246 OpConcat: "cat",
247 OpAlternate: "alt",
248}
249
250// dumpRegexp writes an encoding of the syntax tree for the regexp re to b.
251// It is used during testing to distinguish between parses that might print
252// the same using re's String method.
253func dumpRegexp(b *strings.Builder, re *Regexp) {
254 if int(re.Op) >= len(opNames) || opNames[re.Op] == "" {
255 fmt.Fprintf(b, "op%d", re.Op)
256 } else {
257 switch re.Op {
258 default:
259 b.WriteString(opNames[re.Op])
260 case OpStar, OpPlus, OpQuest, OpRepeat:
261 if re.Flags&NonGreedy != 0 {
262 b.WriteByte('n')
263 }
264 b.WriteString(opNames[re.Op])
265 case OpLiteral:
266 if len(re.Rune) > 1 {
267 b.WriteString("str")
268 } else {
269 b.WriteString("lit")
270 }
271 if re.Flags&FoldCase != 0 {
272 for _, r := range re.Rune {
273 if unicode.SimpleFold(r) != r {
274 b.WriteString("fold")
275 break
276 }
277 }
278 }
279 }
280 }
281 b.WriteByte('{')
282 switch re.Op {
283 case OpEndText:
284 if re.Flags&WasDollar == 0 {
285 b.WriteString(`\z`)
286 }
287 case OpLiteral:
288 for _, r := range re.Rune {
289 b.WriteRune(r)
290 }
291 case OpConcat, OpAlternate:
292 for _, sub := range re.Sub {
293 dumpRegexp(b, sub)
294 }
295 case OpStar, OpPlus, OpQuest:
296 dumpRegexp(b, re.Sub[0])
297 case OpRepeat:
298 fmt.Fprintf(b, "%d,%d ", re.Min, re.Max)
299 dumpRegexp(b, re.Sub[0])
300 case OpCapture:
301 if re.Name != "" {
302 b.WriteString(re.Name)
303 b.WriteByte(':')
304 }
305 dumpRegexp(b, re.Sub[0])
306 case OpCharClass:
307 sep := ""
308 for i := 0; i < len(re.Rune); i += 2 {
309 b.WriteString(sep)
310 sep = " "
311 lo, hi := re.Rune[i], re.Rune[i+1]
312 if lo == hi {
313 fmt.Fprintf(b, "%#x", lo)
314 } else {
315 fmt.Fprintf(b, "%#x-%#x", lo, hi)
316 }
317 }
318 }
319 b.WriteByte('}')
320}
321
322func mkCharClass(f func(rune) bool) string {
323 re := &Regexp{Op: OpCharClass}
324 lo := rune(-1)
325 for i := rune(0); i <= unicode.MaxRune; i++ {
326 if f(i) {
327 if lo < 0 {
328 lo = i
329 }
330 } else {
331 if lo >= 0 {
332 re.Rune = append(re.Rune, lo, i-1)
333 lo = -1
334 }
335 }
336 }
337 if lo >= 0 {
338 re.Rune = append(re.Rune, lo, unicode.MaxRune)
339 }
340 return dump(re)
341}
342
343func isUpperFold(r rune) bool {
344 if unicode.IsUpper(r) {
345 return true
346 }
347 c := unicode.SimpleFold(r)
348 for c != r {
349 if unicode.IsUpper(c) {
350 return true
351 }
352 c = unicode.SimpleFold(c)
353 }
354 return false
355}
356
357func TestToStringEquivalentParse(t *testing.T) {
358 for _, tt := range parseTests {
359 re, err := Parse(tt.Regexp, testFlags)
360 if err != nil {
361 t.Errorf("Parse(%#q): %v", tt.Regexp, err)
362 continue
363 }
364 if tt.Dump == "" {
365 // It parsed. That's all we care about.
366 continue
367 }
368 d := dump(re)
369 if d != tt.Dump {
370 t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
371 continue
372 }
373
374 s := re.String()
375 if s != tt.Regexp {
376 // If ToString didn't return the original regexp,
377 // it must have found one with fewer parens.
378 // Unfortunately we can't check the length here, because
379 // ToString produces "\\{" for a literal brace,
380 // but "{" is a shorter equivalent in some contexts.
381 nre, err := Parse(s, testFlags)
382 if err != nil {
383 t.Errorf("Parse(%#q.String() = %#q): %v", tt.Regexp, s, err)
384 continue
385 }
386 nd := dump(nre)
387 if d != nd {
388 t.Errorf("Parse(%#q) -> %#q; %#q vs %#q", tt.Regexp, s, d, nd)
389 }
390
391 ns := nre.String()
392 if s != ns {
393 t.Errorf("Parse(%#q) -> %#q -> %#q", tt.Regexp, s, ns)
394 }
395 }
396 }
397}