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

View as plain text