libgo/go/regexp/all_test.go

   1 // Copyright 2009 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
   5 package regexp
   6
   7 import (
   8         "reflect"
   9         "regexp/syntax"
  10         "strings"
  11         "testing"
  12 )
  13
  14 var goodRe = []string{
  15         ``,
  16         `.`,
  17         `^.$`,
  18         `a`,
  19         `a*`,
  20         `a+`,
  21         `a?`,
  22         `a|b`,
  23         `a*|b*`,
  24         `(a*|b)(c*|d)`,
  25         `[a-z]`,
  26         `[a-abc-c\-\]\[]`,
  27         `[a-z]+`,
  28         `[abc]`,
  29         `[^1234]`,
  30         `[^\n]`,
  31         `\!\\`,
  32 }
  33
  34 type stringError struct {
  35         re  string
  36         err string
  37 }
  38
  39 var badRe = []stringError{
  40         {`*`, "missing argument to repetition operator: `*`"},
  41         {`+`, "missing argument to repetition operator: `+`"},
  42         {`?`, "missing argument to repetition operator: `?`"},
  43         {`(abc`, "missing closing ): `(abc`"},
  44         {`abc)`, "unexpected ): `abc)`"},
  45         {`x[a-z`, "missing closing ]: `[a-z`"},
  46         {`[z-a]`, "invalid character class range: `z-a`"},
  47         {`abc\`, "trailing backslash at end of expression"},
  48         {`a**`, "invalid nested repetition operator: `**`"},
  49         {`a*+`, "invalid nested repetition operator: `*+`"},
  50         {`\x`, "invalid escape sequence: `\\x`"},
  51 }
  52
  53 func compileTest(t *testing.T, expr string, error string) *Regexp {
  54         re, err := Compile(expr)
  55         if error == "" && err != nil {
  56                 t.Error("compiling `", expr, "`; unexpected error: ", err.Error())
  57         }
  58         if error != "" && err == nil {
  59                 t.Error("compiling `", expr, "`; missing error")
  60         } else if error != "" && !strings.Contains(err.Error(), error) {
  61                 t.Error("compiling `", expr, "`; wrong error: ", err.Error(), "; want ", error)
  62         }
  63         return re
  64 }
  65
  66 func TestGoodCompile(t *testing.T) {
  67         for i := 0; i < len(goodRe); i++ {
  68                 compileTest(t, goodRe[i], "")
  69         }
  70 }
  71
  72 func TestBadCompile(t *testing.T) {
  73         for i := 0; i < len(badRe); i++ {
  74                 compileTest(t, badRe[i].re, badRe[i].err)
  75         }
  76 }
  77
  78 func matchTest(t *testing.T, test *FindTest) {
  79         re := compileTest(t, test.pat, "")
  80         if re == nil {
  81                 return
  82         }
  83         m := re.MatchString(test.text)
  84         if m != (len(test.matches) > 0) {
  85                 t.Errorf("MatchString failure on %s: %t should be %t", test, m, len(test.matches) > 0)
  86         }
  87         // now try bytes
  88         m = re.Match([]byte(test.text))
  89         if m != (len(test.matches) > 0) {
  90                 t.Errorf("Match failure on %s: %t should be %t", test, m, len(test.matches) > 0)
  91         }
  92 }
  93
  94 func TestMatch(t *testing.T) {
  95         for _, test := range findTests {
  96                 matchTest(t, &test)
  97         }
  98 }
  99
 100 func matchFunctionTest(t *testing.T, test *FindTest) {
 101         m, err := MatchString(test.pat, test.text)
 102         if err == nil {
 103                 return
 104         }
 105         if m != (len(test.matches) > 0) {
 106                 t.Errorf("Match failure on %s: %t should be %t", test, m, len(test.matches) > 0)
 107         }
 108 }
 109
 110 func TestMatchFunction(t *testing.T) {
 111         for _, test := range findTests {
 112                 matchFunctionTest(t, &test)
 113         }
 114 }
 115
 116 func copyMatchTest(t *testing.T, test *FindTest) {
 117         re := compileTest(t, test.pat, "")
 118         if re == nil {
 119                 return
 120         }
 121         m1 := re.MatchString(test.text)
 122         m2 := re.Copy().MatchString(test.text)
 123         if m1 != m2 {
 124                 t.Errorf("Copied Regexp match failure on %s: original gave %t; copy gave %t; should be %t",
 125                         test, m1, m2, len(test.matches) > 0)
 126         }
 127 }
 128
 129 func TestCopyMatch(t *testing.T) {
 130         for _, test := range findTests {
 131                 copyMatchTest(t, &test)
 132         }
 133 }
 134
 135 type ReplaceTest struct {
 136         pattern, replacement, input, output string
 137 }
 138
 139 var replaceTests = []ReplaceTest{
 140         // Test empty input and/or replacement, with pattern that matches the empty string.
 141         {"", "", "", ""},
 142         {"", "x", "", "x"},
 143         {"", "", "abc", "abc"},
 144         {"", "x", "abc", "xaxbxcx"},
 145
 146         // Test empty input and/or replacement, with pattern that does not match the empty string.
 147         {"b", "", "", ""},
 148         {"b", "x", "", ""},
 149         {"b", "", "abc", "ac"},
 150         {"b", "x", "abc", "axc"},
 151         {"y", "", "", ""},
 152         {"y", "x", "", ""},
 153         {"y", "", "abc", "abc"},
 154         {"y", "x", "abc", "abc"},
 155
 156         // Multibyte characters -- verify that we don't try to match in the middle
 157         // of a character.
 158         {"[a-c]*", "x", "\u65e5", "x\u65e5x"},
 159         {"[^\u65e5]", "x", "abc\u65e5def", "xxx\u65e5xxx"},
 160
 161         // Start and end of a string.
 162         {"^[a-c]*", "x", "abcdabc", "xdabc"},
 163         {"[a-c]*$", "x", "abcdabc", "abcdx"},
 164         {"^[a-c]*$", "x", "abcdabc", "abcdabc"},
 165         {"^[a-c]*", "x", "abc", "x"},
 166         {"[a-c]*$", "x", "abc", "x"},
 167         {"^[a-c]*$", "x", "abc", "x"},
 168         {"^[a-c]*", "x", "dabce", "xdabce"},
 169         {"[a-c]*$", "x", "dabce", "dabcex"},
 170         {"^[a-c]*$", "x", "dabce", "dabce"},
 171         {"^[a-c]*", "x", "", "x"},
 172         {"[a-c]*$", "x", "", "x"},
 173         {"^[a-c]*$", "x", "", "x"},
 174
 175         {"^[a-c]+", "x", "abcdabc", "xdabc"},
 176         {"[a-c]+$", "x", "abcdabc", "abcdx"},
 177         {"^[a-c]+$", "x", "abcdabc", "abcdabc"},
 178         {"^[a-c]+", "x", "abc", "x"},
 179         {"[a-c]+$", "x", "abc", "x"},
 180         {"^[a-c]+$", "x", "abc", "x"},
 181         {"^[a-c]+", "x", "dabce", "dabce"},
 182         {"[a-c]+$", "x", "dabce", "dabce"},
 183         {"^[a-c]+$", "x", "dabce", "dabce"},
 184         {"^[a-c]+", "x", "", ""},
 185         {"[a-c]+$", "x", "", ""},
 186         {"^[a-c]+$", "x", "", ""},
 187
 188         // Other cases.
 189         {"abc", "def", "abcdefg", "defdefg"},
 190         {"bc", "BC", "abcbcdcdedef", "aBCBCdcdedef"},
 191         {"abc", "", "abcdabc", "d"},
 192         {"x", "xXx", "xxxXxxx", "xXxxXxxXxXxXxxXxxXx"},
 193         {"abc", "d", "", ""},
 194         {"abc", "d", "abc", "d"},
 195         {".+", "x", "abc", "x"},
 196         {"[a-c]*", "x", "def", "xdxexfx"},
 197         {"[a-c]+", "x", "abcbcdcdedef", "xdxdedef"},
 198         {"[a-c]*", "x", "abcbcdcdedef", "xdxdxexdxexfx"},
 199
 200         // Substitutions
 201         {"a+", "($0)", "banana", "b(a)n(a)n(a)"},
 202         {"a+", "(${0})", "banana", "b(a)n(a)n(a)"},
 203         {"a+", "(${0})$0", "banana", "b(a)an(a)an(a)a"},
 204         {"a+", "(${0})$0", "banana", "b(a)an(a)an(a)a"},
 205         {"hello, (.+)", "goodbye, ${1}", "hello, world", "goodbye, world"},
 206         {"hello, (.+)", "goodbye, $1x", "hello, world", "goodbye, "},
 207         {"hello, (.+)", "goodbye, ${1}x", "hello, world", "goodbye, worldx"},
 208         {"hello, (.+)", "<$0><$1><$2><$3>", "hello, world", "<hello, world><world><><>"},
 209         {"hello, (?P<noun>.+)", "goodbye, $noun!", "hello, world", "goodbye, world!"},
 210         {"hello, (?P<noun>.+)", "goodbye, ${noun}", "hello, world", "goodbye, world"},
 211         {"(?P<x>hi)|(?P<x>bye)", "$x$x$x", "hi", "hihihi"},
 212         {"(?P<x>hi)|(?P<x>bye)", "$x$x$x", "bye", "byebyebye"},
 213         {"(?P<x>hi)|(?P<x>bye)", "$xyz", "hi", ""},
 214         {"(?P<x>hi)|(?P<x>bye)", "${x}yz", "hi", "hiyz"},
 215         {"(?P<x>hi)|(?P<x>bye)", "hello $$x", "hi", "hello $x"},
 216         {"a+", "${oops", "aaa", "${oops"},
 217         {"a+", "$$", "aaa", "$"},
 218         {"a+", "$", "aaa", "$"},
 219
 220         // Substitution when subexpression isn't found
 221         {"(x)?", "$1", "123", "123"},
 222         {"abc", "$1", "123", "123"},
 223
 224         // Substitutions involving a (x){0}
 225         {"(a)(b){0}(c)", ".$1|$3.", "xacxacx", "x.a|c.x.a|c.x"},
 226         {"(a)(((b))){0}c", ".$1.", "xacxacx", "x.a.x.a.x"},
 227         {"((a(b){0}){3}){5}(h)", "y caramb$2", "say aaaaaaaaaaaaaaaah", "say ay caramba"},
 228         {"((a(b){0}){3}){5}h", "y caramb$2", "say aaaaaaaaaaaaaaaah", "say ay caramba"},
 229 }
 230
 231 var replaceLiteralTests = []ReplaceTest{
 232         // Substitutions
 233         {"a+", "($0)", "banana", "b($0)n($0)n($0)"},
 234         {"a+", "(${0})", "banana", "b(${0})n(${0})n(${0})"},
 235         {"a+", "(${0})$0", "banana", "b(${0})$0n(${0})$0n(${0})$0"},
 236         {"a+", "(${0})$0", "banana", "b(${0})$0n(${0})$0n(${0})$0"},
 237         {"hello, (.+)", "goodbye, ${1}", "hello, world", "goodbye, ${1}"},
 238         {"hello, (?P<noun>.+)", "goodbye, $noun!", "hello, world", "goodbye, $noun!"},
 239         {"hello, (?P<noun>.+)", "goodbye, ${noun}", "hello, world", "goodbye, ${noun}"},
 240         {"(?P<x>hi)|(?P<x>bye)", "$x$x$x", "hi", "$x$x$x"},
 241         {"(?P<x>hi)|(?P<x>bye)", "$x$x$x", "bye", "$x$x$x"},
 242         {"(?P<x>hi)|(?P<x>bye)", "$xyz", "hi", "$xyz"},
 243         {"(?P<x>hi)|(?P<x>bye)", "${x}yz", "hi", "${x}yz"},
 244         {"(?P<x>hi)|(?P<x>bye)", "hello $$x", "hi", "hello $$x"},
 245         {"a+", "${oops", "aaa", "${oops"},
 246         {"a+", "$$", "aaa", "$$"},
 247         {"a+", "$", "aaa", "$"},
 248 }
 249
 250 type ReplaceFuncTest struct {
 251         pattern       string
 252         replacement   func(string) string
 253         input, output string
 254 }
 255
 256 var replaceFuncTests = []ReplaceFuncTest{
 257         {"[a-c]", func(s string) string { return "x" + s + "y" }, "defabcdef", "defxayxbyxcydef"},
 258         {"[a-c]+", func(s string) string { return "x" + s + "y" }, "defabcdef", "defxabcydef"},
 259         {"[a-c]*", func(s string) string { return "x" + s + "y" }, "defabcdef", "xydxyexyfxabcydxyexyfxy"},
 260 }
 261
 262 func TestReplaceAll(t *testing.T) {
 263         for _, tc := range replaceTests {
 264                 re, err := Compile(tc.pattern)
 265                 if err != nil {
 266                         t.Errorf("Unexpected error compiling %q: %v", tc.pattern, err)
 267                         continue
 268                 }
 269                 actual := re.ReplaceAllString(tc.input, tc.replacement)
 270                 if actual != tc.output {
 271                         t.Errorf("%q.ReplaceAllString(%q,%q) = %q; want %q",
 272                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 273                 }
 274                 // now try bytes
 275                 actual = string(re.ReplaceAll([]byte(tc.input), []byte(tc.replacement)))
 276                 if actual != tc.output {
 277                         t.Errorf("%q.ReplaceAll(%q,%q) = %q; want %q",
 278                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 279                 }
 280         }
 281 }
 282
 283 func TestReplaceAllLiteral(t *testing.T) {
 284         // Run ReplaceAll tests that do not have $ expansions.
 285         for _, tc := range replaceTests {
 286                 if strings.Contains(tc.replacement, "$") {
 287                         continue
 288                 }
 289                 re, err := Compile(tc.pattern)
 290                 if err != nil {
 291                         t.Errorf("Unexpected error compiling %q: %v", tc.pattern, err)
 292                         continue
 293                 }
 294                 actual := re.ReplaceAllLiteralString(tc.input, tc.replacement)
 295                 if actual != tc.output {
 296                         t.Errorf("%q.ReplaceAllLiteralString(%q,%q) = %q; want %q",
 297                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 298                 }
 299                 // now try bytes
 300                 actual = string(re.ReplaceAllLiteral([]byte(tc.input), []byte(tc.replacement)))
 301                 if actual != tc.output {
 302                         t.Errorf("%q.ReplaceAllLiteral(%q,%q) = %q; want %q",
 303                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 304                 }
 305         }
 306
 307         // Run literal-specific tests.
 308         for _, tc := range replaceLiteralTests {
 309                 re, err := Compile(tc.pattern)
 310                 if err != nil {
 311                         t.Errorf("Unexpected error compiling %q: %v", tc.pattern, err)
 312                         continue
 313                 }
 314                 actual := re.ReplaceAllLiteralString(tc.input, tc.replacement)
 315                 if actual != tc.output {
 316                         t.Errorf("%q.ReplaceAllLiteralString(%q,%q) = %q; want %q",
 317                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 318                 }
 319                 // now try bytes
 320                 actual = string(re.ReplaceAllLiteral([]byte(tc.input), []byte(tc.replacement)))
 321                 if actual != tc.output {
 322                         t.Errorf("%q.ReplaceAllLiteral(%q,%q) = %q; want %q",
 323                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 324                 }
 325         }
 326 }
 327
 328 func TestReplaceAllFunc(t *testing.T) {
 329         for _, tc := range replaceFuncTests {
 330                 re, err := Compile(tc.pattern)
 331                 if err != nil {
 332                         t.Errorf("Unexpected error compiling %q: %v", tc.pattern, err)
 333                         continue
 334                 }
 335                 actual := re.ReplaceAllStringFunc(tc.input, tc.replacement)
 336                 if actual != tc.output {
 337                         t.Errorf("%q.ReplaceFunc(%q,fn) = %q; want %q",
 338                                 tc.pattern, tc.input, actual, tc.output)
 339                 }
 340                 // now try bytes
 341                 actual = string(re.ReplaceAllFunc([]byte(tc.input), func(s []byte) []byte { return []byte(tc.replacement(string(s))) }))
 342                 if actual != tc.output {
 343                         t.Errorf("%q.ReplaceFunc(%q,fn) = %q; want %q",
 344                                 tc.pattern, tc.input, actual, tc.output)
 345                 }
 346         }
 347 }
 348
 349 type MetaTest struct {
 350         pattern, output, literal string
 351         isLiteral                bool
 352 }
 353
 354 var metaTests = []MetaTest{
 355         {``, ``, ``, true},
 356         {`foo`, `foo`, `foo`, true},
 357         {`foo\.\$`, `foo\\\.\\\$`, `foo.$`, true}, // has meta but no operator
 358         {`foo.\$`, `foo\.\\\$`, `foo`, false},     // has escaped operators and real operators
 359         {`!@#$%^&*()_+-=[{]}\|,<.>/?~`, `!@#\$%\^&\*\(\)_\+-=\[\{\]\}\\\|,<\.>/\?~`, `!@#`, false},
 360 }
 361
 362 var literalPrefixTests = []MetaTest{
 363         // See golang.org/issue/11175.
 364         // output is unused.
 365         {`^0^0$`, ``, `0`, false},
 366         {`^0^`, ``, ``, false},
 367         {`^0$`, ``, `0`, true},
 368         {`$0^`, ``, ``, false},
 369         {`$0$`, ``, ``, false},
 370         {`^^0$$`, ``, ``, false},
 371         {`^$^$`, ``, ``, false},
 372         {`$$0^^`, ``, ``, false},
 373 }
 374
 375 func TestQuoteMeta(t *testing.T) {
 376         for _, tc := range metaTests {
 377                 // Verify that QuoteMeta returns the expected string.
 378                 quoted := QuoteMeta(tc.pattern)
 379                 if quoted != tc.output {
 380                         t.Errorf("QuoteMeta(`%s`) = `%s`; want `%s`",
 381                                 tc.pattern, quoted, tc.output)
 382                         continue
 383                 }
 384
 385                 // Verify that the quoted string is in fact treated as expected
 386                 // by Compile -- i.e. that it matches the original, unquoted string.
 387                 if tc.pattern != "" {
 388                         re, err := Compile(quoted)
 389                         if err != nil {
 390                                 t.Errorf("Unexpected error compiling QuoteMeta(`%s`): %v", tc.pattern, err)
 391                                 continue
 392                         }
 393                         src := "abc" + tc.pattern + "def"
 394                         repl := "xyz"
 395                         replaced := re.ReplaceAllString(src, repl)
 396                         expected := "abcxyzdef"
 397                         if replaced != expected {
 398                                 t.Errorf("QuoteMeta(`%s`).Replace(`%s`,`%s`) = `%s`; want `%s`",
 399                                         tc.pattern, src, repl, replaced, expected)
 400                         }
 401                 }
 402         }
 403 }
 404
 405 func TestLiteralPrefix(t *testing.T) {
 406         for _, tc := range append(metaTests, literalPrefixTests...) {
 407                 // Literal method needs to scan the pattern.
 408                 re := MustCompile(tc.pattern)
 409                 str, complete := re.LiteralPrefix()
 410                 if complete != tc.isLiteral {
 411                         t.Errorf("LiteralPrefix(`%s`) = %t; want %t", tc.pattern, complete, tc.isLiteral)
 412                 }
 413                 if str != tc.literal {
 414                         t.Errorf("LiteralPrefix(`%s`) = `%s`; want `%s`", tc.pattern, str, tc.literal)
 415                 }
 416         }
 417 }
 418
 419 type subexpCase struct {
 420         input string
 421         num   int
 422         names []string
 423 }
 424
 425 var subexpCases = []subexpCase{
 426         {``, 0, nil},
 427         {`.*`, 0, nil},
 428         {`abba`, 0, nil},
 429         {`ab(b)a`, 1, []string{"", ""}},
 430         {`ab(.*)a`, 1, []string{"", ""}},
 431         {`(.*)ab(.*)a`, 2, []string{"", "", ""}},
 432         {`(.*)(ab)(.*)a`, 3, []string{"", "", "", ""}},
 433         {`(.*)((a)b)(.*)a`, 4, []string{"", "", "", "", ""}},
 434         {`(.*)(\(ab)(.*)a`, 3, []string{"", "", "", ""}},
 435         {`(.*)(\(a\)b)(.*)a`, 3, []string{"", "", "", ""}},
 436         {`(?P<foo>.*)(?P<bar>(a)b)(?P<foo>.*)a`, 4, []string{"", "foo", "bar", "", "foo"}},
 437 }
 438
 439 func TestSubexp(t *testing.T) {
 440         for _, c := range subexpCases {
 441                 re := MustCompile(c.input)
 442                 n := re.NumSubexp()
 443                 if n != c.num {
 444                         t.Errorf("%q: NumSubexp = %d, want %d", c.input, n, c.num)
 445                         continue
 446                 }
 447                 names := re.SubexpNames()
 448                 if len(names) != 1+n {
 449                         t.Errorf("%q: len(SubexpNames) = %d, want %d", c.input, len(names), n)
 450                         continue
 451                 }
 452                 if c.names != nil {
 453                         for i := 0; i < 1+n; i++ {
 454                                 if names[i] != c.names[i] {
 455                                         t.Errorf("%q: SubexpNames[%d] = %q, want %q", c.input, i, names[i], c.names[i])
 456                                 }
 457                         }
 458                 }
 459         }
 460 }
 461
 462 var splitTests = []struct {
 463         s   string
 464         r   string
 465         n   int
 466         out []string
 467 }{
 468         {"foo:and:bar", ":", -1, []string{"foo", "and", "bar"}},
 469         {"foo:and:bar", ":", 1, []string{"foo:and:bar"}},
 470         {"foo:and:bar", ":", 2, []string{"foo", "and:bar"}},
 471         {"foo:and:bar", "foo", -1, []string{"", ":and:bar"}},
 472         {"foo:and:bar", "bar", -1, []string{"foo:and:", ""}},
 473         {"foo:and:bar", "baz", -1, []string{"foo:and:bar"}},
 474         {"baabaab", "a", -1, []string{"b", "", "b", "", "b"}},
 475         {"baabaab", "a*", -1, []string{"b", "b", "b"}},
 476         {"baabaab", "ba*", -1, []string{"", "", "", ""}},
 477         {"foobar", "f*b*", -1, []string{"", "o", "o", "a", "r"}},
 478         {"foobar", "f+.*b+", -1, []string{"", "ar"}},
 479         {"foobooboar", "o{2}", -1, []string{"f", "b", "boar"}},
 480         {"a,b,c,d,e,f", ",", 3, []string{"a", "b", "c,d,e,f"}},
 481         {"a,b,c,d,e,f", ",", 0, nil},
 482         {",", ",", -1, []string{"", ""}},
 483         {",,,", ",", -1, []string{"", "", "", ""}},
 484         {"", ",", -1, []string{""}},
 485         {"", ".*", -1, []string{""}},
 486         {"", ".+", -1, []string{""}},
 487         {"", "", -1, []string{}},
 488         {"foobar", "", -1, []string{"f", "o", "o", "b", "a", "r"}},
 489         {"abaabaccadaaae", "a*", 5, []string{"", "b", "b", "c", "cadaaae"}},
 490         {":x:y:z:", ":", -1, []string{"", "x", "y", "z", ""}},
 491 }
 492
 493 func TestSplit(t *testing.T) {
 494         for i, test := range splitTests {
 495                 re, err := Compile(test.r)
 496                 if err != nil {
 497                         t.Errorf("#%d: %q: compile error: %s", i, test.r, err.Error())
 498                         continue
 499                 }
 500
 501                 split := re.Split(test.s, test.n)
 502                 if !reflect.DeepEqual(split, test.out) {
 503                         t.Errorf("#%d: %q: got %q; want %q", i, test.r, split, test.out)
 504                 }
 505
 506                 if QuoteMeta(test.r) == test.r {
 507                         strsplit := strings.SplitN(test.s, test.r, test.n)
 508                         if !reflect.DeepEqual(split, strsplit) {
 509                                 t.Errorf("#%d: Split(%q, %q, %d): regexp vs strings mismatch\nregexp=%q\nstrings=%q", i, test.s, test.r, test.n, split, strsplit)
 510                         }
 511                 }
 512         }
 513 }
 514
 515 // The following sequence of Match calls used to panic. See issue #12980.
 516 func TestParseAndCompile(t *testing.T) {
 517         expr := "a$"
 518         s := "a\nb"
 519
 520         for i, tc := range []struct {
 521                 reFlags  syntax.Flags
 522                 expMatch bool
 523         }{
 524                 {syntax.Perl | syntax.OneLine, false},
 525                 {syntax.Perl &^ syntax.OneLine, true},
 526         } {
 527                 parsed, err := syntax.Parse(expr, tc.reFlags)
 528                 if err != nil {
 529                         t.Fatalf("%d: parse: %v", i, err)
 530                 }
 531                 re, err := Compile(parsed.String())
 532                 if err != nil {
 533                         t.Fatalf("%d: compile: %v", i, err)
 534                 }
 535                 if match := re.MatchString(s); match != tc.expMatch {
 536                         t.Errorf("%d: %q.MatchString(%q)=%t; expected=%t", i, re, s, match, tc.expMatch)
 537                 }
 538         }
 539 }
 540
 541 // Check that one-pass cutoff does trigger.
 542 func TestOnePassCutoff(t *testing.T) {
 543         re, err := syntax.Parse(`^x{1,1000}y{1,1000}$`, syntax.Perl)
 544         if err != nil {
 545                 t.Fatalf("parse: %v", err)
 546         }
 547         p, err := syntax.Compile(re.Simplify())
 548         if err != nil {
 549                 t.Fatalf("compile: %v", err)
 550         }
 551         if compileOnePass(p) != notOnePass {
 552                 t.Fatalf("makeOnePass succeeded; wanted notOnePass")
 553         }
 554 }
 555
 556 // Check that the same machine can be used with the standard matcher
 557 // and then the backtracker when there are no captures.
 558 func TestSwitchBacktrack(t *testing.T) {
 559         re := MustCompile(`a|b`)
 560         long := make([]byte, maxBacktrackVector+1)
 561
 562         // The following sequence of Match calls used to panic. See issue #10319.
 563         re.Match(long)     // triggers standard matcher
 564         re.Match(long[:1]) // triggers backtracker
 565 }
 566
 567 func BenchmarkFind(b *testing.B) {
 568         b.StopTimer()
 569         re := MustCompile("a+b+")
 570         wantSubs := "aaabb"
 571         s := []byte("acbb" + wantSubs + "dd")
 572         b.StartTimer()
 573         b.ReportAllocs()
 574         for i := 0; i < b.N; i++ {
 575                 subs := re.Find(s)
 576                 if string(subs) != wantSubs {
 577                         b.Fatalf("Find(%q) = %q; want %q", s, subs, wantSubs)
 578                 }
 579         }
 580 }
 581
 582 func BenchmarkFindString(b *testing.B) {
 583         b.StopTimer()
 584         re := MustCompile("a+b+")
 585         wantSubs := "aaabb"
 586         s := "acbb" + wantSubs + "dd"
 587         b.StartTimer()
 588         b.ReportAllocs()
 589         for i := 0; i < b.N; i++ {
 590                 subs := re.FindString(s)
 591                 if subs != wantSubs {
 592                         b.Fatalf("FindString(%q) = %q; want %q", s, subs, wantSubs)
 593                 }
 594         }
 595 }
 596
 597 func BenchmarkFindSubmatch(b *testing.B) {
 598         b.StopTimer()
 599         re := MustCompile("a(a+b+)b")
 600         wantSubs := "aaabb"
 601         s := []byte("acbb" + wantSubs + "dd")
 602         b.StartTimer()
 603         b.ReportAllocs()
 604         for i := 0; i < b.N; i++ {
 605                 subs := re.FindSubmatch(s)
 606                 if string(subs[0]) != wantSubs {
 607                         b.Fatalf("FindSubmatch(%q)[0] = %q; want %q", s, subs[0], wantSubs)
 608                 }
 609                 if string(subs[1]) != "aab" {
 610                         b.Fatalf("FindSubmatch(%q)[1] = %q; want %q", s, subs[1], "aab")
 611                 }
 612         }
 613 }
 614
 615 func BenchmarkFindStringSubmatch(b *testing.B) {
 616         b.StopTimer()
 617         re := MustCompile("a(a+b+)b")
 618         wantSubs := "aaabb"
 619         s := "acbb" + wantSubs + "dd"
 620         b.StartTimer()
 621         b.ReportAllocs()
 622         for i := 0; i < b.N; i++ {
 623                 subs := re.FindStringSubmatch(s)
 624                 if subs[0] != wantSubs {
 625                         b.Fatalf("FindStringSubmatch(%q)[0] = %q; want %q", s, subs[0], wantSubs)
 626                 }
 627                 if subs[1] != "aab" {
 628                         b.Fatalf("FindStringSubmatch(%q)[1] = %q; want %q", s, subs[1], "aab")
 629                 }
 630         }
 631 }
 632
 633 func BenchmarkLiteral(b *testing.B) {
 634         x := strings.Repeat("x", 50) + "y"
 635         b.StopTimer()
 636         re := MustCompile("y")
 637         b.StartTimer()
 638         for i := 0; i < b.N; i++ {
 639                 if !re.MatchString(x) {
 640                         b.Fatalf("no match!")
 641                 }
 642         }
 643 }
 644
 645 func BenchmarkNotLiteral(b *testing.B) {
 646         x := strings.Repeat("x", 50) + "y"
 647         b.StopTimer()
 648         re := MustCompile(".y")
 649         b.StartTimer()
 650         for i := 0; i < b.N; i++ {
 651                 if !re.MatchString(x) {
 652                         b.Fatalf("no match!")
 653                 }
 654         }
 655 }
 656
 657 func BenchmarkMatchClass(b *testing.B) {
 658         b.StopTimer()
 659         x := strings.Repeat("xxxx", 20) + "w"
 660         re := MustCompile("[abcdw]")
 661         b.StartTimer()
 662         for i := 0; i < b.N; i++ {
 663                 if !re.MatchString(x) {
 664                         b.Fatalf("no match!")
 665                 }
 666         }
 667 }
 668
 669 func BenchmarkMatchClass_InRange(b *testing.B) {
 670         b.StopTimer()
 671         // 'b' is between 'a' and 'c', so the charclass
 672         // range checking is no help here.
 673         x := strings.Repeat("bbbb", 20) + "c"
 674         re := MustCompile("[ac]")
 675         b.StartTimer()
 676         for i := 0; i < b.N; i++ {
 677                 if !re.MatchString(x) {
 678                         b.Fatalf("no match!")
 679                 }
 680         }
 681 }
 682
 683 func BenchmarkReplaceAll(b *testing.B) {
 684         x := "abcdefghijklmnopqrstuvwxyz"
 685         b.StopTimer()
 686         re := MustCompile("[cjrw]")
 687         b.StartTimer()
 688         for i := 0; i < b.N; i++ {
 689                 re.ReplaceAllString(x, "")
 690         }
 691 }
 692
 693 func BenchmarkAnchoredLiteralShortNonMatch(b *testing.B) {
 694         b.StopTimer()
 695         x := []byte("abcdefghijklmnopqrstuvwxyz")
 696         re := MustCompile("^zbc(d|e)")
 697         b.StartTimer()
 698         for i := 0; i < b.N; i++ {
 699                 re.Match(x)
 700         }
 701 }
 702
 703 func BenchmarkAnchoredLiteralLongNonMatch(b *testing.B) {
 704         b.StopTimer()
 705         x := []byte("abcdefghijklmnopqrstuvwxyz")
 706         for i := 0; i < 15; i++ {
 707                 x = append(x, x...)
 708         }
 709         re := MustCompile("^zbc(d|e)")
 710         b.StartTimer()
 711         for i := 0; i < b.N; i++ {
 712                 re.Match(x)
 713         }
 714 }
 715
 716 func BenchmarkAnchoredShortMatch(b *testing.B) {
 717         b.StopTimer()
 718         x := []byte("abcdefghijklmnopqrstuvwxyz")
 719         re := MustCompile("^.bc(d|e)")
 720         b.StartTimer()
 721         for i := 0; i < b.N; i++ {
 722                 re.Match(x)
 723         }
 724 }
 725
 726 func BenchmarkAnchoredLongMatch(b *testing.B) {
 727         b.StopTimer()
 728         x := []byte("abcdefghijklmnopqrstuvwxyz")
 729         for i := 0; i < 15; i++ {
 730                 x = append(x, x...)
 731         }
 732         re := MustCompile("^.bc(d|e)")
 733         b.StartTimer()
 734         for i := 0; i < b.N; i++ {
 735                 re.Match(x)
 736         }
 737 }
 738
 739 func BenchmarkOnePassShortA(b *testing.B) {
 740         b.StopTimer()
 741         x := []byte("abcddddddeeeededd")
 742         re := MustCompile("^.bc(d|e)*$")
 743         b.StartTimer()
 744         for i := 0; i < b.N; i++ {
 745                 re.Match(x)
 746         }
 747 }
 748
 749 func BenchmarkNotOnePassShortA(b *testing.B) {
 750         b.StopTimer()
 751         x := []byte("abcddddddeeeededd")
 752         re := MustCompile(".bc(d|e)*$")
 753         b.StartTimer()
 754         for i := 0; i < b.N; i++ {
 755                 re.Match(x)
 756         }
 757 }
 758
 759 func BenchmarkOnePassShortB(b *testing.B) {
 760         b.StopTimer()
 761         x := []byte("abcddddddeeeededd")
 762         re := MustCompile("^.bc(?:d|e)*$")
 763         b.StartTimer()
 764         for i := 0; i < b.N; i++ {
 765                 re.Match(x)
 766         }
 767 }
 768
 769 func BenchmarkNotOnePassShortB(b *testing.B) {
 770         b.StopTimer()
 771         x := []byte("abcddddddeeeededd")
 772         re := MustCompile(".bc(?:d|e)*$")
 773         b.StartTimer()
 774         for i := 0; i < b.N; i++ {
 775                 re.Match(x)
 776         }
 777 }
 778
 779 func BenchmarkOnePassLongPrefix(b *testing.B) {
 780         b.StopTimer()
 781         x := []byte("abcdefghijklmnopqrstuvwxyz")
 782         re := MustCompile("^abcdefghijklmnopqrstuvwxyz.*$")
 783         b.StartTimer()
 784         for i := 0; i < b.N; i++ {
 785                 re.Match(x)
 786         }
 787 }
 788
 789 func BenchmarkOnePassLongNotPrefix(b *testing.B) {
 790         b.StopTimer()
 791         x := []byte("abcdefghijklmnopqrstuvwxyz")
 792         re := MustCompile("^.bcdefghijklmnopqrstuvwxyz.*$")
 793         b.StartTimer()
 794         for i := 0; i < b.N; i++ {
 795                 re.Match(x)
 796         }
 797 }
 798
 799 func BenchmarkMatchParallelShared(b *testing.B) {
 800         x := []byte("this is a long line that contains foo bar baz")
 801         re := MustCompile("foo (ba+r)? baz")
 802         b.ResetTimer()
 803         b.RunParallel(func(pb *testing.PB) {
 804                 for pb.Next() {
 805                         re.Match(x)
 806                 }
 807         })
 808 }
 809
 810 func BenchmarkMatchParallelCopied(b *testing.B) {
 811         x := []byte("this is a long line that contains foo bar baz")
 812         re := MustCompile("foo (ba+r)? baz")
 813         b.ResetTimer()
 814         b.RunParallel(func(pb *testing.PB) {
 815                 re := re.Copy()
 816                 for pb.Next() {
 817                         re.Match(x)
 818                 }
 819         })
 820 }
 821
 822 var sink string
 823
 824 func BenchmarkQuoteMetaAll(b *testing.B) {
 825         s := string(specialBytes)
 826         b.SetBytes(int64(len(s)))
 827         b.ResetTimer()
 828         for i := 0; i < b.N; i++ {
 829                 sink = QuoteMeta(s)
 830         }
 831 }
 832
 833 func BenchmarkQuoteMetaNone(b *testing.B) {
 834         s := "abcdefghijklmnopqrstuvwxyz"
 835         b.SetBytes(int64(len(s)))
 836         b.ResetTimer()
 837         for i := 0; i < b.N; i++ {
 838                 sink = QuoteMeta(s)
 839         }
 840 }