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