1// Copyright 2014 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 regexp
6
7import (
8	"reflect"
9	"regexp/syntax"
10	"strings"
11	"testing"
12)
13
14var runeMergeTests = []struct {
15	left, right, merged []rune
16	next                []uint32
17	leftPC, rightPC     uint32
18}{
19	{
20		// empty rhs
21		[]rune{69, 69},
22		[]rune{},
23		[]rune{69, 69},
24		[]uint32{1},
25		1, 2,
26	},
27	{
28		// identical runes, identical targets
29		[]rune{69, 69},
30		[]rune{69, 69},
31		[]rune{},
32		[]uint32{mergeFailed},
33		1, 1,
34	},
35	{
36		// identical runes, different targets
37		[]rune{69, 69},
38		[]rune{69, 69},
39		[]rune{},
40		[]uint32{mergeFailed},
41		1, 2,
42	},
43	{
44		// append right-first
45		[]rune{69, 69},
46		[]rune{71, 71},
47		[]rune{69, 69, 71, 71},
48		[]uint32{1, 2},
49		1, 2,
50	},
51	{
52		// append, left-first
53		[]rune{71, 71},
54		[]rune{69, 69},
55		[]rune{69, 69, 71, 71},
56		[]uint32{2, 1},
57		1, 2,
58	},
59	{
60		// successful interleave
61		[]rune{60, 60, 71, 71, 101, 101},
62		[]rune{69, 69, 88, 88},
63		[]rune{60, 60, 69, 69, 71, 71, 88, 88, 101, 101},
64		[]uint32{1, 2, 1, 2, 1},
65		1, 2,
66	},
67	{
68		// left surrounds right
69		[]rune{69, 74},
70		[]rune{71, 71},
71		[]rune{},
72		[]uint32{mergeFailed},
73		1, 2,
74	},
75	{
76		// right surrounds left
77		[]rune{69, 74},
78		[]rune{68, 75},
79		[]rune{},
80		[]uint32{mergeFailed},
81		1, 2,
82	},
83	{
84		// overlap at interval begin
85		[]rune{69, 74},
86		[]rune{74, 75},
87		[]rune{},
88		[]uint32{mergeFailed},
89		1, 2,
90	},
91	{
92		// overlap ar interval end
93		[]rune{69, 74},
94		[]rune{65, 69},
95		[]rune{},
96		[]uint32{mergeFailed},
97		1, 2,
98	},
99	{
100		// overlap from above
101		[]rune{69, 74},
102		[]rune{71, 74},
103		[]rune{},
104		[]uint32{mergeFailed},
105		1, 2,
106	},
107	{
108		// overlap from below
109		[]rune{69, 74},
110		[]rune{65, 71},
111		[]rune{},
112		[]uint32{mergeFailed},
113		1, 2,
114	},
115	{
116		// out of order []rune
117		[]rune{69, 74, 60, 65},
118		[]rune{66, 67},
119		[]rune{},
120		[]uint32{mergeFailed},
121		1, 2,
122	},
123}
124
125func TestMergeRuneSet(t *testing.T) {
126	for ix, test := range runeMergeTests {
127		merged, next := mergeRuneSets(&test.left, &test.right, test.leftPC, test.rightPC)
128		if !reflect.DeepEqual(merged, test.merged) {
129			t.Errorf("mergeRuneSet :%d (%v, %v) merged\n have\n%v\nwant\n%v", ix, test.left, test.right, merged, test.merged)
130		}
131		if !reflect.DeepEqual(next, test.next) {
132			t.Errorf("mergeRuneSet :%d(%v, %v) next\n have\n%v\nwant\n%v", ix, test.left, test.right, next, test.next)
133		}
134	}
135}
136
137var onePass = &onePassProg{}
138
139var onePassTests = []struct {
140	re      string
141	onePass *onePassProg
142}{
143	{`^(?:a|(?:a*))$`, notOnePass},
144	{`^(?:(a)|(?:a*))$`, notOnePass},
145	{`^(?:(?:(?:.(?:$))?))$`, onePass},
146	{`^abcd$`, onePass},
147	{`^(?:(?:a{0,})*?)$`, onePass},
148	{`^(?:(?:a+)*)$`, onePass},
149	{`^(?:(?:a|(?:aa)))$`, onePass},
150	{`^(?:[^\s\S])$`, onePass},
151	{`^(?:(?:a{3,4}){0,})$`, notOnePass},
152	{`^(?:(?:(?:a*)+))$`, onePass},
153	{`^[a-c]+$`, onePass},
154	{`^[a-c]*$`, onePass},
155	{`^(?:a*)$`, onePass},
156	{`^(?:(?:aa)|a)$`, onePass},
157	{`^[a-c]*`, notOnePass},
158	{`^...$`, onePass},
159	{`^(?:a|(?:aa))$`, onePass},
160	{`^a((b))c$`, onePass},
161	{`^a.[l-nA-Cg-j]?e$`, onePass},
162	{`^a((b))$`, onePass},
163	{`^a(?:(b)|(c))c$`, onePass},
164	{`^a(?:(b*)|(c))c$`, notOnePass},
165	{`^a(?:b|c)$`, onePass},
166	{`^a(?:b?|c)$`, onePass},
167	{`^a(?:b?|c?)$`, notOnePass},
168	{`^a(?:b?|c+)$`, onePass},
169	{`^a(?:b+|(bc))d$`, notOnePass},
170	{`^a(?:bc)+$`, onePass},
171	{`^a(?:[bcd])+$`, onePass},
172	{`^a((?:[bcd])+)$`, onePass},
173	{`^a(:?b|c)*d$`, onePass},
174	{`^.bc(d|e)*$`, onePass},
175	{`^(?:(?:aa)|.)$`, notOnePass},
176	{`^(?:(?:a{1,2}){1,2})$`, notOnePass},
177	{`^l` + strings.Repeat("o", 2<<8) + `ng$`, onePass},
178}
179
180func TestCompileOnePass(t *testing.T) {
181	var (
182		p   *syntax.Prog
183		re  *syntax.Regexp
184		err error
185	)
186	for _, test := range onePassTests {
187		if re, err = syntax.Parse(test.re, syntax.Perl); err != nil {
188			t.Errorf("Parse(%q) got err:%s, want success", test.re, err)
189			continue
190		}
191		// needs to be done before compile...
192		re = re.Simplify()
193		if p, err = syntax.Compile(re); err != nil {
194			t.Errorf("Compile(%q) got err:%s, want success", test.re, err)
195			continue
196		}
197		onePass = compileOnePass(p)
198		if (onePass == notOnePass) != (test.onePass == notOnePass) {
199			t.Errorf("CompileOnePass(%q) got %v, expected %v", test.re, onePass, test.onePass)
200		}
201	}
202}
203
204// TODO(cespare): Unify with onePassTests and rationalize one-pass test cases.
205var onePassTests1 = []struct {
206	re    string
207	match string
208}{
209	{`^a(/b+(#c+)*)*$`, "a/b#c"}, // golang.org/issue/11905
210}
211
212func TestRunOnePass(t *testing.T) {
213	for _, test := range onePassTests1 {
214		re, err := Compile(test.re)
215		if err != nil {
216			t.Errorf("Compile(%q): got err: %s", test.re, err)
217			continue
218		}
219		if re.onepass == notOnePass {
220			t.Errorf("Compile(%q): got notOnePass, want one-pass", test.re)
221			continue
222		}
223		if !re.MatchString(test.match) {
224			t.Errorf("onepass %q did not match %q", test.re, test.match)
225		}
226	}
227}
228
229func BenchmarkCompileOnepass(b *testing.B) {
230	for _, test := range onePassTests {
231		if test.onePass == notOnePass {
232			continue
233		}
234		name := test.re
235		if len(name) > 20 {
236			name = name[:20] + "..."
237		}
238		b.Run(name, func(b *testing.B) {
239			b.ReportAllocs()
240			for i := 0; i < b.N; i++ {
241				if _, err := Compile(test.re); err != nil {
242					b.Fatal(err)
243				}
244			}
245		})
246	}
247}
248