1package regexp2
2
3import (
4	"strings"
5	"testing"
6)
7
8func BenchmarkLiteral(b *testing.B) {
9	x := strings.Repeat("x", 50) + "y"
10	b.StopTimer()
11	re := MustCompile("y", 0)
12	b.StartTimer()
13	for i := 0; i < b.N; i++ {
14		if m, err := re.MatchString(x); !m || err != nil {
15			b.Fatalf("no match or error! %v", err)
16		}
17	}
18}
19
20func BenchmarkNotLiteral(b *testing.B) {
21	x := strings.Repeat("x", 50) + "y"
22	b.StopTimer()
23	re := MustCompile(".y", 0)
24	b.StartTimer()
25	for i := 0; i < b.N; i++ {
26		if m, err := re.MatchString(x); !m || err != nil {
27			b.Fatalf("no match or error! %v", err)
28		}
29	}
30}
31
32func BenchmarkMatchClass(b *testing.B) {
33	b.StopTimer()
34	x := strings.Repeat("xxxx", 20) + "w"
35	re := MustCompile("[abcdw]", 0)
36	b.StartTimer()
37	for i := 0; i < b.N; i++ {
38		if m, err := re.MatchString(x); !m || err != nil {
39			b.Fatalf("no match or error! %v", err)
40		}
41
42	}
43}
44
45func BenchmarkMatchClass_InRange(b *testing.B) {
46	b.StopTimer()
47	// 'b' is between 'a' and 'c', so the charclass
48	// range checking is no help here.
49	x := strings.Repeat("bbbb", 20) + "c"
50	re := MustCompile("[ac]", 0)
51	b.StartTimer()
52	for i := 0; i < b.N; i++ {
53		if m, err := re.MatchString(x); !m || err != nil {
54			b.Fatalf("no match or error! %v", err)
55		}
56	}
57}
58
59/*
60func BenchmarkReplaceAll(b *testing.B) {
61	x := "abcdefghijklmnopqrstuvwxyz"
62	b.StopTimer()
63	re := MustCompile("[cjrw]", 0)
64	b.StartTimer()
65	for i := 0; i < b.N; i++ {
66		re.ReplaceAllString(x, "")
67	}
68}
69*/
70func BenchmarkAnchoredLiteralShortNonMatch(b *testing.B) {
71	b.StopTimer()
72	x := "abcdefghijklmnopqrstuvwxyz"
73	re := MustCompile("^zbc(d|e)", 0)
74	b.StartTimer()
75	for i := 0; i < b.N; i++ {
76		if m, err := re.MatchString(x); m || err != nil {
77			b.Fatalf("unexpected match or error! %v", err)
78		}
79	}
80}
81
82func BenchmarkAnchoredLiteralLongNonMatch(b *testing.B) {
83	b.StopTimer()
84
85	data := "abcdefghijklmnopqrstuvwxyz"
86	x := make([]rune, 32768*len(data))
87	for i := 0; i < 32768; /*(2^15)*/ i++ {
88		for j := 0; j < len(data); j++ {
89			x[i*len(data)+j] = rune(data[j])
90		}
91	}
92
93	re := MustCompile("^zbc(d|e)", 0)
94	b.StartTimer()
95	for i := 0; i < b.N; i++ {
96		if m, err := re.MatchRunes(x); m || err != nil {
97			b.Fatalf("unexpected match or error! %v", err)
98		}
99	}
100}
101
102func BenchmarkAnchoredShortMatch(b *testing.B) {
103	b.StopTimer()
104	x := "abcdefghijklmnopqrstuvwxyz"
105	re := MustCompile("^.bc(d|e)", 0)
106	b.StartTimer()
107	for i := 0; i < b.N; i++ {
108		if m, err := re.MatchString(x); !m || err != nil {
109			b.Fatalf("no match or error! %v", err)
110		}
111	}
112}
113
114func BenchmarkAnchoredLongMatch(b *testing.B) {
115	b.StopTimer()
116	data := "abcdefghijklmnopqrstuvwxyz"
117	x := make([]rune, 32768*len(data))
118	for i := 0; i < 32768; /*(2^15)*/ i++ {
119		for j := 0; j < len(data); j++ {
120			x[i*len(data)+j] = rune(data[j])
121		}
122	}
123
124	re := MustCompile("^.bc(d|e)", 0)
125	b.StartTimer()
126	for i := 0; i < b.N; i++ {
127		if m, err := re.MatchRunes(x); !m || err != nil {
128			b.Fatalf("no match or error! %v", err)
129		}
130	}
131}
132
133func BenchmarkOnePassShortA(b *testing.B) {
134	b.StopTimer()
135	x := "abcddddddeeeededd"
136	re := MustCompile("^.bc(d|e)*$", 0)
137	b.StartTimer()
138	for i := 0; i < b.N; i++ {
139		if m, err := re.MatchString(x); !m || err != nil {
140			b.Fatalf("no match or error! %v", err)
141		}
142	}
143}
144
145func BenchmarkNotOnePassShortA(b *testing.B) {
146	b.StopTimer()
147	x := "abcddddddeeeededd"
148	re := MustCompile(".bc(d|e)*$", 0)
149	b.StartTimer()
150	for i := 0; i < b.N; i++ {
151		if m, err := re.MatchString(x); !m || err != nil {
152			b.Fatalf("no match or error! %v", err)
153		}
154	}
155}
156
157func BenchmarkOnePassShortB(b *testing.B) {
158	b.StopTimer()
159	x := "abcddddddeeeededd"
160	re := MustCompile("^.bc(?:d|e)*$", 0)
161	b.StartTimer()
162	for i := 0; i < b.N; i++ {
163		if m, err := re.MatchString(x); !m || err != nil {
164			b.Fatalf("no match or error! %v", err)
165		}
166	}
167}
168
169func BenchmarkNotOnePassShortB(b *testing.B) {
170	b.StopTimer()
171	x := "abcddddddeeeededd"
172	re := MustCompile(".bc(?:d|e)*$", 0)
173	b.StartTimer()
174	for i := 0; i < b.N; i++ {
175		if m, err := re.MatchString(x); !m || err != nil {
176			b.Fatalf("no match or error! %v", err)
177		}
178	}
179}
180
181func BenchmarkOnePassLongPrefix(b *testing.B) {
182	b.StopTimer()
183	x := "abcdefghijklmnopqrstuvwxyz"
184	re := MustCompile("^abcdefghijklmnopqrstuvwxyz.*$", 0)
185	b.StartTimer()
186	for i := 0; i < b.N; i++ {
187		if m, err := re.MatchString(x); !m || err != nil {
188			b.Fatalf("no match or error! %v", err)
189		}
190	}
191}
192
193func BenchmarkOnePassLongNotPrefix(b *testing.B) {
194	b.StopTimer()
195	x := "abcdefghijklmnopqrstuvwxyz"
196	re := MustCompile("^.bcdefghijklmnopqrstuvwxyz.*$", 0)
197	b.StartTimer()
198	for i := 0; i < b.N; i++ {
199		if m, err := re.MatchString(x); !m || err != nil {
200			b.Fatalf("no match or error! %v", err)
201		}
202	}
203}
204
205var text []rune
206
207func makeText(n int) []rune {
208	if len(text) >= n {
209		return text[:n]
210	}
211	text = make([]rune, n)
212	x := ^uint32(0)
213	for i := range text {
214		x += x
215		x ^= 1
216		if int32(x) < 0 {
217			x ^= 0x88888eef
218		}
219		if x%31 == 0 {
220			text[i] = '\n'
221		} else {
222			text[i] = rune(x%(0x7E+1-0x20) + 0x20)
223		}
224	}
225	return text
226}
227
228func benchmark(b *testing.B, re string, n int) {
229	r := MustCompile(re, 0)
230	t := makeText(n)
231	b.ResetTimer()
232	b.SetBytes(int64(n))
233	for i := 0; i < b.N; i++ {
234		if m, err := r.MatchRunes(t); m {
235			b.Fatal("match!")
236		} else if err != nil {
237			b.Fatalf("Err %v", err)
238		}
239	}
240}
241
242const (
243	easy0  = "ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
244	easy1  = "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$"
245	medium = "[XYZ]ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
246	hard   = "[ -~]*ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
247	parens = "([ -~])*(A)(B)(C)(D)(E)(F)(G)(H)(I)(J)(K)(L)(M)" +
248		"(N)(O)(P)(Q)(R)(S)(T)(U)(V)(W)(X)(Y)(Z)$"
249)
250
251func BenchmarkMatchEasy0_32(b *testing.B)   { benchmark(b, easy0, 32<<0) }
252func BenchmarkMatchEasy0_1K(b *testing.B)   { benchmark(b, easy0, 1<<10) }
253func BenchmarkMatchEasy0_32K(b *testing.B)  { benchmark(b, easy0, 32<<10) }
254func BenchmarkMatchEasy0_1M(b *testing.B)   { benchmark(b, easy0, 1<<20) }
255func BenchmarkMatchEasy0_32M(b *testing.B)  { benchmark(b, easy0, 32<<20) }
256func BenchmarkMatchEasy1_32(b *testing.B)   { benchmark(b, easy1, 32<<0) }
257func BenchmarkMatchEasy1_1K(b *testing.B)   { benchmark(b, easy1, 1<<10) }
258func BenchmarkMatchEasy1_32K(b *testing.B)  { benchmark(b, easy1, 32<<10) }
259func BenchmarkMatchEasy1_1M(b *testing.B)   { benchmark(b, easy1, 1<<20) }
260func BenchmarkMatchEasy1_32M(b *testing.B)  { benchmark(b, easy1, 32<<20) }
261func BenchmarkMatchMedium_32(b *testing.B)  { benchmark(b, medium, 32<<0) }
262func BenchmarkMatchMedium_1K(b *testing.B)  { benchmark(b, medium, 1<<10) }
263func BenchmarkMatchMedium_32K(b *testing.B) { benchmark(b, medium, 32<<10) }
264func BenchmarkMatchMedium_1M(b *testing.B)  { benchmark(b, medium, 1<<20) }
265func BenchmarkMatchMedium_32M(b *testing.B) { benchmark(b, medium, 32<<20) }
266func BenchmarkMatchHard_32(b *testing.B)    { benchmark(b, hard, 32<<0) }
267func BenchmarkMatchHard_1K(b *testing.B)    { benchmark(b, hard, 1<<10) }
268func BenchmarkMatchHard_32K(b *testing.B)   { benchmark(b, hard, 32<<10) }
269func BenchmarkMatchHard_1M(b *testing.B)    { benchmark(b, hard, 1<<20) }
270func BenchmarkMatchHard_32M(b *testing.B)   { benchmark(b, hard, 32<<20) }
271
272// TestProgramTooLongForBacktrack tests that a regex which is too long
273// for the backtracker still executes properly.
274func TestProgramTooLongForBacktrack(t *testing.T) {
275	longRegex := MustCompile(`(one|two|three|four|five|six|seven|eight|nine|ten|eleven|twelve|thirteen|fourteen|fifteen|sixteen|seventeen|eighteen|nineteen|twenty|twentyone|twentytwo|twentythree|twentyfour|twentyfive|twentysix|twentyseven|twentyeight|twentynine|thirty|thirtyone|thirtytwo|thirtythree|thirtyfour|thirtyfive|thirtysix|thirtyseven|thirtyeight|thirtynine|forty|fortyone|fortytwo|fortythree|fortyfour|fortyfive|fortysix|fortyseven|fortyeight|fortynine|fifty|fiftyone|fiftytwo|fiftythree|fiftyfour|fiftyfive|fiftysix|fiftyseven|fiftyeight|fiftynine|sixty|sixtyone|sixtytwo|sixtythree|sixtyfour|sixtyfive|sixtysix|sixtyseven|sixtyeight|sixtynine|seventy|seventyone|seventytwo|seventythree|seventyfour|seventyfive|seventysix|seventyseven|seventyeight|seventynine|eighty|eightyone|eightytwo|eightythree|eightyfour|eightyfive|eightysix|eightyseven|eightyeight|eightynine|ninety|ninetyone|ninetytwo|ninetythree|ninetyfour|ninetyfive|ninetysix|ninetyseven|ninetyeight|ninetynine|onehundred)`, 0)
276
277	if m, err := longRegex.MatchString("two"); !m {
278		t.Errorf("longRegex.MatchString(\"two\") was false, want true")
279	} else if err != nil {
280		t.Errorf("Error: %v", err)
281	}
282	if m, err := longRegex.MatchString("xxx"); m {
283		t.Errorf("longRegex.MatchString(\"xxx\") was true, want false")
284	} else if err != nil {
285		t.Errorf("Error: %v", err)
286	}
287}
288
289func BenchmarkLeading(b *testing.B) {
290	b.StopTimer()
291	r := MustCompile("[a-q][^u-z]{13}x", 0)
292	inp := makeText(1000000)
293	b.StartTimer()
294	for i := 0; i < b.N; i++ {
295		if m, err := r.MatchRunes(inp); !m {
296			b.Errorf("Expected match")
297		} else if err != nil {
298			b.Errorf("Error: %v", err)
299		}
300	}
301}
302