1
2
3
4
5 package syntax
6
7 import (
8 "fmt"
9 "strings"
10 "testing"
11 "unicode"
12 )
13
14 type parseTest struct {
15 Regexp string
16 Dump string
17 }
18
19 var parseTests = []parseTest{
20
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
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{}`},
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
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
97
98
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
116 {`[\012-\234]\141`, `cat{cc{0xa-0x9c}lit{a}}`},
117 {`[\x{41}-\x7a]\x61`, `cat{cc{0x41-0x7a}lit{a}}`},
118
119
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}`},
125 {`a*{`, `cat{star{lit{a}}lit{{}}`},
126
127
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
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
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
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
162 {`(?P<name>a)`, `cap{name:lit{a}}`},
163
164
165 {`[Aa]`, `litfold{A}`},
166 {`[\x{100}\x{101}]`, `litfold{Ā}`},
167 {`[Δδ]`, `litfold{Δ}`},
168
169
170 {`abcde`, `str{abcde}`},
171 {`[Aa][Bb]cd`, `cat{strfold{AB}str{cd}}`},
172
173
174 {`abc|abd|aef|bcx|bcy`, `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}cat{str{bc}cc{0x78-0x79}}}`},
175 {`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}}}}`},
176
177
178 {`(?:.)`, `dot{}`},
179 {`(?:x|(?:xa))`, `cat{lit{x}alt{emp{}lit{a}}}`},
180 {`(?:.|(?:.a))`, `cat{dot{}alt{emp{}lit{a}}}`},
181 {`(?:A(?:A|a))`, `cat{lit{A}litfold{A}}`},
182 {`(?:A|a)`, `litfold{A}`},
183 {`A|(?:A|a)`, `litfold{A}`},
184 {`(?s).`, `dot{}`},
185 {`(?-s).`, `dnl{}`},
186 {`(?:(?:^).)`, `cat{bol{}dot{}}`},
187 {`(?-s)(?:(?:^).)`, `cat{bol{}dnl{}}`},
188 {`[\s\S]a`, `cat{cc{0x0-0x10ffff}lit{a}}`},
189
190
191 {`abc|abd`, `cat{str{ab}cc{0x63-0x64}}`},
192 {`a(?:b)c|abd`, `cat{str{ab}cc{0x63-0x64}}`},
193 {`abc|abd|aef|bcx|bcy`,
194 `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}` +
195 `cat{str{bc}cc{0x78-0x79}}}`},
196 {`abc|x|abd`, `alt{str{abc}lit{x}str{abd}}`},
197 {`(?i)abc|ABD`, `cat{strfold{AB}cc{0x43-0x44 0x63-0x64}}`},
198 {`[ab]c|[ab]d`, `cat{cc{0x61-0x62}cc{0x63-0x64}}`},
199 {`.c|.d`, `cat{dot{}cc{0x63-0x64}}`},
200 {`x{2}|x{2}[0-9]`,
201 `cat{rep{2,2 lit{x}}alt{emp{}cc{0x30-0x39}}}`},
202 {`x{2}y|x{2}[0-9]y`,
203 `cat{rep{2,2 lit{x}}alt{lit{y}cat{cc{0x30-0x39}lit{y}}}}`},
204 {`a.*?c|a.*?b`,
205 `cat{lit{a}alt{cat{nstar{dot{}}lit{c}}cat{nstar{dot{}}lit{b}}}}`},
206
207
208 {`((((((((((x{2}){2}){2}){2}){2}){2}){2}){2}){2}))`, ``},
209 {`((((((((((x{1}){2}){2}){2}){2}){2}){2}){2}){2}){2})`, ``},
210 }
211
212 const testFlags = MatchNL | PerlX | UnicodeGroups
213
214 func TestParseSimple(t *testing.T) {
215 testParseDump(t, parseTests, testFlags)
216 }
217
218 var foldcaseTests = []parseTest{
219 {`AbCdE`, `strfold{ABCDE}`},
220 {`[Aa]`, `litfold{A}`},
221 {`a`, `litfold{A}`},
222
223
224
225 {`A[F-g]`, `cat{litfold{A}cc{0x41-0x7a 0x17f 0x212a}}`},
226 {`[[:upper:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
227 {`[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
228 }
229
230 func TestParseFoldCase(t *testing.T) {
231 testParseDump(t, foldcaseTests, FoldCase)
232 }
233
234 var literalTests = []parseTest{
235 {"(|)^$.[*+?]{5,10},\\", "str{(|)^$.[*+?]{5,10},\\}"},
236 }
237
238 func TestParseLiteral(t *testing.T) {
239 testParseDump(t, literalTests, Literal)
240 }
241
242 var matchnlTests = []parseTest{
243 {`.`, `dot{}`},
244 {"\n", "lit{\n}"},
245 {`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
246 {`[a\n]`, `cc{0xa 0x61}`},
247 }
248
249 func TestParseMatchNL(t *testing.T) {
250 testParseDump(t, matchnlTests, MatchNL)
251 }
252
253 var nomatchnlTests = []parseTest{
254 {`.`, `dnl{}`},
255 {"\n", "lit{\n}"},
256 {`[^a]`, `cc{0x0-0x9 0xb-0x60 0x62-0x10ffff}`},
257 {`[a\n]`, `cc{0xa 0x61}`},
258 }
259
260 func TestParseNoMatchNL(t *testing.T) {
261 testParseDump(t, nomatchnlTests, 0)
262 }
263
264
265 func testParseDump(t *testing.T, tests []parseTest, flags Flags) {
266 for _, tt := range tests {
267 re, err := Parse(tt.Regexp, flags)
268 if err != nil {
269 t.Errorf("Parse(%#q): %v", tt.Regexp, err)
270 continue
271 }
272 if tt.Dump == "" {
273
274 continue
275 }
276 d := dump(re)
277 if d != tt.Dump {
278 t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
279 }
280 }
281 }
282
283
284
285 func dump(re *Regexp) string {
286 var b strings.Builder
287 dumpRegexp(&b, re)
288 return b.String()
289 }
290
291 var opNames = []string{
292 OpNoMatch: "no",
293 OpEmptyMatch: "emp",
294 OpLiteral: "lit",
295 OpCharClass: "cc",
296 OpAnyCharNotNL: "dnl",
297 OpAnyChar: "dot",
298 OpBeginLine: "bol",
299 OpEndLine: "eol",
300 OpBeginText: "bot",
301 OpEndText: "eot",
302 OpWordBoundary: "wb",
303 OpNoWordBoundary: "nwb",
304 OpCapture: "cap",
305 OpStar: "star",
306 OpPlus: "plus",
307 OpQuest: "que",
308 OpRepeat: "rep",
309 OpConcat: "cat",
310 OpAlternate: "alt",
311 }
312
313
314
315
316 func dumpRegexp(b *strings.Builder, re *Regexp) {
317 if int(re.Op) >= len(opNames) || opNames[re.Op] == "" {
318 fmt.Fprintf(b, "op%d", re.Op)
319 } else {
320 switch re.Op {
321 default:
322 b.WriteString(opNames[re.Op])
323 case OpStar, OpPlus, OpQuest, OpRepeat:
324 if re.Flags&NonGreedy != 0 {
325 b.WriteByte('n')
326 }
327 b.WriteString(opNames[re.Op])
328 case OpLiteral:
329 if len(re.Rune) > 1 {
330 b.WriteString("str")
331 } else {
332 b.WriteString("lit")
333 }
334 if re.Flags&FoldCase != 0 {
335 for _, r := range re.Rune {
336 if unicode.SimpleFold(r) != r {
337 b.WriteString("fold")
338 break
339 }
340 }
341 }
342 }
343 }
344 b.WriteByte('{')
345 switch re.Op {
346 case OpEndText:
347 if re.Flags&WasDollar == 0 {
348 b.WriteString(`\z`)
349 }
350 case OpLiteral:
351 for _, r := range re.Rune {
352 b.WriteRune(r)
353 }
354 case OpConcat, OpAlternate:
355 for _, sub := range re.Sub {
356 dumpRegexp(b, sub)
357 }
358 case OpStar, OpPlus, OpQuest:
359 dumpRegexp(b, re.Sub[0])
360 case OpRepeat:
361 fmt.Fprintf(b, "%d,%d ", re.Min, re.Max)
362 dumpRegexp(b, re.Sub[0])
363 case OpCapture:
364 if re.Name != "" {
365 b.WriteString(re.Name)
366 b.WriteByte(':')
367 }
368 dumpRegexp(b, re.Sub[0])
369 case OpCharClass:
370 sep := ""
371 for i := 0; i < len(re.Rune); i += 2 {
372 b.WriteString(sep)
373 sep = " "
374 lo, hi := re.Rune[i], re.Rune[i+1]
375 if lo == hi {
376 fmt.Fprintf(b, "%#x", lo)
377 } else {
378 fmt.Fprintf(b, "%#x-%#x", lo, hi)
379 }
380 }
381 }
382 b.WriteByte('}')
383 }
384
385 func mkCharClass(f func(rune) bool) string {
386 re := &Regexp{Op: OpCharClass}
387 lo := rune(-1)
388 for i := rune(0); i <= unicode.MaxRune; i++ {
389 if f(i) {
390 if lo < 0 {
391 lo = i
392 }
393 } else {
394 if lo >= 0 {
395 re.Rune = append(re.Rune, lo, i-1)
396 lo = -1
397 }
398 }
399 }
400 if lo >= 0 {
401 re.Rune = append(re.Rune, lo, unicode.MaxRune)
402 }
403 return dump(re)
404 }
405
406 func isUpperFold(r rune) bool {
407 if unicode.IsUpper(r) {
408 return true
409 }
410 c := unicode.SimpleFold(r)
411 for c != r {
412 if unicode.IsUpper(c) {
413 return true
414 }
415 c = unicode.SimpleFold(c)
416 }
417 return false
418 }
419
420 func TestFoldConstants(t *testing.T) {
421 last := rune(-1)
422 for i := rune(0); i <= unicode.MaxRune; i++ {
423 if unicode.SimpleFold(i) == i {
424 continue
425 }
426 if last == -1 && minFold != i {
427 t.Errorf("minFold=%#U should be %#U", minFold, i)
428 }
429 last = i
430 }
431 if maxFold != last {
432 t.Errorf("maxFold=%#U should be %#U", maxFold, last)
433 }
434 }
435
436 func TestAppendRangeCollapse(t *testing.T) {
437
438
439
440
441 var r []rune
442 for i := rune('A'); i <= 'Z'; i++ {
443 r = appendRange(r, i, i)
444 r = appendRange(r, i+'a'-'A', i+'a'-'A')
445 }
446 if string(r) != "AZaz" {
447 t.Errorf("appendRange interlaced A-Z a-z = %s, want AZaz", string(r))
448 }
449 }
450
451 var invalidRegexps = []string{
452 `(`,
453 `)`,
454 `(a`,
455 `a)`,
456 `(a))`,
457 `(a|b|`,
458 `a|b|)`,
459 `(a|b|))`,
460 `(a|b`,
461 `a|b)`,
462 `(a|b))`,
463 `[a-z`,
464 `([a-z)`,
465 `[a-z)`,
466 `([a-z]))`,
467 `x{1001}`,
468 `x{9876543210}`,
469 `x{2,1}`,
470 `x{1,9876543210}`,
471 "\xff",
472 "[\xff]",
473 "[\\\xff]",
474 "\\\xff",
475 `(?P<name>a`,
476 `(?P<name>`,
477 `(?P<name`,
478 `(?P<x y>a)`,
479 `(?P<>a)`,
480 `[a-Z]`,
481 `(?i)[a-Z]`,
482 `a{100000}`,
483 `a{100000,}`,
484 "((((((((((x{2}){2}){2}){2}){2}){2}){2}){2}){2}){2})",
485 `\Q\E*`,
486 }
487
488 var onlyPerl = []string{
489 `[a-b-c]`,
490 `\Qabc\E`,
491 `\Q*+?{[\E`,
492 `\Q\\E`,
493 `\Q\\\E`,
494 `\Q\\\\E`,
495 `\Q\\\\\E`,
496 `(?:a)`,
497 `(?P<name>a)`,
498 }
499
500 var onlyPOSIX = []string{
501 "a++",
502 "a**",
503 "a?*",
504 "a+*",
505 "a{1}*",
506 ".{1}{2}.{3}",
507 }
508
509 func TestParseInvalidRegexps(t *testing.T) {
510 for _, regexp := range invalidRegexps {
511 if re, err := Parse(regexp, Perl); err == nil {
512 t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
513 }
514 if re, err := Parse(regexp, POSIX); err == nil {
515 t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
516 }
517 }
518 for _, regexp := range onlyPerl {
519 if _, err := Parse(regexp, Perl); err != nil {
520 t.Errorf("Parse(%#q, Perl): %v", regexp, err)
521 }
522 if re, err := Parse(regexp, POSIX); err == nil {
523 t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
524 }
525 }
526 for _, regexp := range onlyPOSIX {
527 if re, err := Parse(regexp, Perl); err == nil {
528 t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
529 }
530 if _, err := Parse(regexp, POSIX); err != nil {
531 t.Errorf("Parse(%#q, POSIX): %v", regexp, err)
532 }
533 }
534 }
535
536 func TestToStringEquivalentParse(t *testing.T) {
537 for _, tt := range parseTests {
538 re, err := Parse(tt.Regexp, testFlags)
539 if err != nil {
540 t.Errorf("Parse(%#q): %v", tt.Regexp, err)
541 continue
542 }
543 if tt.Dump == "" {
544
545 continue
546 }
547 d := dump(re)
548 if d != tt.Dump {
549 t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
550 continue
551 }
552
553 s := re.String()
554 if s != tt.Regexp {
555
556
557
558
559
560 nre, err := Parse(s, testFlags)
561 if err != nil {
562 t.Errorf("Parse(%#q.String() = %#q): %v", tt.Regexp, s, err)
563 continue
564 }
565 nd := dump(nre)
566 if d != nd {
567 t.Errorf("Parse(%#q) -> %#q; %#q vs %#q", tt.Regexp, s, d, nd)
568 }
569
570 ns := nre.String()
571 if s != ns {
572 t.Errorf("Parse(%#q) -> %#q -> %#q", tt.Regexp, s, ns)
573 }
574 }
575 }
576 }
577
View as plain text