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

View as plain text