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	"testing"
11)
12
13var runeMergeTests = []struct {
14	left, right, merged []rune
15	next                []uint32
16	leftPC, rightPC     uint32
17}{
18	{
19		// empty rhs
20		[]rune{69, 69},
21		[]rune{},
22		[]rune{69, 69},
23		[]uint32{1},
24		1, 2,
25	},
26	{
27		// identical runes, identical targets
28		[]rune{69, 69},
29		[]rune{69, 69},
30		[]rune{},
31		[]uint32{mergeFailed},
32		1, 1,
33	},
34	{
35		// identical runes, different targets
36		[]rune{69, 69},
37		[]rune{69, 69},
38		[]rune{},
39		[]uint32{mergeFailed},
40		1, 2,
41	},
42	{
43		// append right-first
44		[]rune{69, 69},
45		[]rune{71, 71},
46		[]rune{69, 69, 71, 71},
47		[]uint32{1, 2},
48		1, 2,
49	},
50	{
51		// append, left-first
52		[]rune{71, 71},
53		[]rune{69, 69},
54		[]rune{69, 69, 71, 71},
55		[]uint32{2, 1},
56		1, 2,
57	},
58	{
59		// successful interleave
60		[]rune{60, 60, 71, 71, 101, 101},
61		[]rune{69, 69, 88, 88},
62		[]rune{60, 60, 69, 69, 71, 71, 88, 88, 101, 101},
63		[]uint32{1, 2, 1, 2, 1},
64		1, 2,
65	},
66	{
67		// left surrounds right
68		[]rune{69, 74},
69		[]rune{71, 71},
70		[]rune{},
71		[]uint32{mergeFailed},
72		1, 2,
73	},
74	{
75		// right surrounds left
76		[]rune{69, 74},
77		[]rune{68, 75},
78		[]rune{},
79		[]uint32{mergeFailed},
80		1, 2,
81	},
82	{
83		// overlap at interval begin
84		[]rune{69, 74},
85		[]rune{74, 75},
86		[]rune{},
87		[]uint32{mergeFailed},
88		1, 2,
89	},
90	{
91		// overlap ar interval end
92		[]rune{69, 74},
93		[]rune{65, 69},
94		[]rune{},
95		[]uint32{mergeFailed},
96		1, 2,
97	},
98	{
99		// overlap from above
100		[]rune{69, 74},
101		[]rune{71, 74},
102		[]rune{},
103		[]uint32{mergeFailed},
104		1, 2,
105	},
106	{
107		// overlap from below
108		[]rune{69, 74},
109		[]rune{65, 71},
110		[]rune{},
111		[]uint32{mergeFailed},
112		1, 2,
113	},
114	{
115		// out of order []rune
116		[]rune{69, 74, 60, 65},
117		[]rune{66, 67},
118		[]rune{},
119		[]uint32{mergeFailed},
120		1, 2,
121	},
122}
123
124func TestMergeRuneSet(t *testing.T) {
125	for ix, test := range runeMergeTests {
126		merged, next := mergeRuneSets(&test.left, &test.right, test.leftPC, test.rightPC)
127		if !reflect.DeepEqual(merged, test.merged) {
128			t.Errorf("mergeRuneSet :%d (%v, %v) merged\n have\n%v\nwant\n%v", ix, test.left, test.right, merged, test.merged)
129		}
130		if !reflect.DeepEqual(next, test.next) {
131			t.Errorf("mergeRuneSet :%d(%v, %v) next\n have\n%v\nwant\n%v", ix, test.left, test.right, next, test.next)
132		}
133	}
134}
135
136const noStr = `!`
137
138var onePass = &onePassProg{}
139
140var onePassTests = []struct {
141	re      string
142	onePass *onePassProg
143}{
144	{`^(?:a|(?:a*))$`, notOnePass},
145	{`^(?:(a)|(?:a*))$`, notOnePass},
146	{`^(?:(?:(?:.(?:$))?))$`, onePass},
147	{`^abcd$`, onePass},
148	{`^(?:(?:a{0,})*?)$`, onePass},
149	{`^(?:(?:a+)*)$`, onePass},
150	{`^(?:(?:a|(?:aa)))$`, onePass},
151	{`^(?:[^\s\S])$`, onePass},
152	{`^(?:(?:a{3,4}){0,})$`, notOnePass},
153	{`^(?:(?:(?:a*)+))$`, onePass},
154	{`^[a-c]+$`, onePass},
155	{`^[a-c]*$`, onePass},
156	{`^(?:a*)$`, onePass},
157	{`^(?:(?:aa)|a)$`, onePass},
158	{`^[a-c]*`, notOnePass},
159	{`^...$`, onePass},
160	{`^(?:a|(?:aa))$`, onePass},
161	{`^a((b))c$`, onePass},
162	{`^a.[l-nA-Cg-j]?e$`, onePass},
163	{`^a((b))$`, onePass},
164	{`^a(?:(b)|(c))c$`, onePass},
165	{`^a(?:(b*)|(c))c$`, notOnePass},
166	{`^a(?:b|c)$`, onePass},
167	{`^a(?:b?|c)$`, onePass},
168	{`^a(?:b?|c?)$`, notOnePass},
169	{`^a(?:b?|c+)$`, onePass},
170	{`^a(?:b+|(bc))d$`, notOnePass},
171	{`^a(?:bc)+$`, onePass},
172	{`^a(?:[bcd])+$`, onePass},
173	{`^a((?:[bcd])+)$`, onePass},
174	{`^a(:?b|c)*d$`, onePass},
175	{`^.bc(d|e)*$`, onePass},
176	{`^(?:(?:aa)|.)$`, notOnePass},
177	{`^(?:(?:a{1,2}){1,2})$`, notOnePass},
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