parse_test.go

Documentation: regexp/syntax

     1  // Copyright 2011 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 syntax
     6  
     7  import (
     8  	"fmt"
     9  	"strings"
    10  	"testing"
    11  	"unicode"
    12  )
    13  
    14  type parseTest struct {
    15  	Regexp string
    16  	Dump   string
    17  }
    18  
    19  var parseTests = []parseTest{
    20  	// Base cases
    21  	{`a`, `lit{a}`},
    22  	{`a.`, `cat{lit{a}dot{}}`},
    23  	{`a.b`, `cat{lit{a}dot{}lit{b}}`},
    24  	{`ab`, `str{ab}`},
    25  	{`a.b.c`, `cat{lit{a}dot{}lit{b}dot{}lit{c}}`},
    26  	{`abc`, `str{abc}`},
    27  	{`a|^`, `alt{lit{a}bol{}}`},
    28  	{`a|b`, `cc{0x61-0x62}`},
    29  	{`(a)`, `cap{lit{a}}`},
    30  	{`(a)|b`, `alt{cap{lit{a}}lit{b}}`},
    31  	{`a*`, `star{lit{a}}`},
    32  	{`a+`, `plus{lit{a}}`},
    33  	{`a?`, `que{lit{a}}`},
    34  	{`a{2}`, `rep{2,2 lit{a}}`},
    35  	{`a{2,3}`, `rep{2,3 lit{a}}`},
    36  	{`a{2,}`, `rep{2,-1 lit{a}}`},
    37  	{`a*?`, `nstar{lit{a}}`},
    38  	{`a+?`, `nplus{lit{a}}`},
    39  	{`a??`, `nque{lit{a}}`},
    40  	{`a{2}?`, `nrep{2,2 lit{a}}`},
    41  	{`a{2,3}?`, `nrep{2,3 lit{a}}`},
    42  	{`a{2,}?`, `nrep{2,-1 lit{a}}`},
    43  	// Malformed { } are treated as literals.
    44  	{`x{1001`, `str{x{1001}`},
    45  	{`x{9876543210`, `str{x{9876543210}`},
    46  	{`x{9876543210,`, `str{x{9876543210,}`},
    47  	{`x{2,1`, `str{x{2,1}`},
    48  	{`x{1,9876543210`, `str{x{1,9876543210}`},
    49  	{``, `emp{}`},
    50  	{`|`, `emp{}`}, // alt{emp{}emp{}} but got factored
    51  	{`|x|`, `alt{emp{}lit{x}emp{}}`},
    52  	{`.`, `dot{}`},
    53  	{`^`, `bol{}`},
    54  	{`$`, `eol{}`},
    55  	{`\|`, `lit{|}`},
    56  	{`\(`, `lit{(}`},
    57  	{`\)`, `lit{)}`},
    58  	{`\*`, `lit{*}`},
    59  	{`\+`, `lit{+}`},
    60  	{`\?`, `lit{?}`},
    61  	{`{`, `lit{{}`},
    62  	{`}`, `lit{}}`},
    63  	{`\.`, `lit{.}`},
    64  	{`\^`, `lit{^}`},
    65  	{`\$`, `lit{$}`},
    66  	{`\\`, `lit{\}`},
    67  	{`[ace]`, `cc{0x61 0x63 0x65}`},
    68  	{`[abc]`, `cc{0x61-0x63}`},
    69  	{`[a-z]`, `cc{0x61-0x7a}`},
    70  	{`[a]`, `lit{a}`},
    71  	{`\-`, `lit{-}`},
    72  	{`-`, `lit{-}`},
    73  	{`\_`, `lit{_}`},
    74  	{`abc`, `str{abc}`},
    75  	{`abc|def`, `alt{str{abc}str{def}}`},
    76  	{`abc|def|ghi`, `alt{str{abc}str{def}str{ghi}}`},
    77  
    78  	// Posix and Perl extensions
    79  	{`[[:lower:]]`, `cc{0x61-0x7a}`},
    80  	{`[a-z]`, `cc{0x61-0x7a}`},
    81  	{`[^[:lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
    82  	{`[[:^lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
    83  	{`(?i)[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
    84  	{`(?i)[a-z]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
    85  	{`(?i)[^[:lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
    86  	{`(?i)[[:^lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
    87  	{`\d`, `cc{0x30-0x39}`},
    88  	{`\D`, `cc{0x0-0x2f 0x3a-0x10ffff}`},
    89  	{`\s`, `cc{0x9-0xa 0xc-0xd 0x20}`},
    90  	{`\S`, `cc{0x0-0x8 0xb 0xe-0x1f 0x21-0x10ffff}`},
    91  	{`\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a}`},
    92  	{`\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x10ffff}`},
    93  	{`(?i)\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a 0x17f 0x212a}`},
    94  	{`(?i)\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
    95  	{`[^\\]`, `cc{0x0-0x5b 0x5d-0x10ffff}`},
    96  	//	{ `\C`, `byte{}` },  // probably never
    97  
    98  	// Unicode, negatives, and a double negative.
    99  	{`\p{Braille}`, `cc{0x2800-0x28ff}`},
   100  	{`\P{Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
   101  	{`\p{^Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
   102  	{`\P{^Braille}`, `cc{0x2800-0x28ff}`},
   103  	{`\pZ`, `cc{0x20 0xa0 0x1680 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
   104  	{`[\p{Braille}]`, `cc{0x2800-0x28ff}`},
   105  	{`[\P{Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
   106  	{`[\p{^Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
   107  	{`[\P{^Braille}]`, `cc{0x2800-0x28ff}`},
   108  	{`[\pZ]`, `cc{0x20 0xa0 0x1680 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
   109  	{`\p{Lu}`, mkCharClass(unicode.IsUpper)},
   110  	{`\p{Uppercase_Letter}`, mkCharClass(unicode.IsUpper)},
   111  	{`\p{upper case-let ter}`, mkCharClass(unicode.IsUpper)},
   112  	{`\p{__upper case-let ter}`, mkCharClass(unicode.IsUpper)},
   113  	{`\p{Canadian_Aboriginal}`, mkCharClass(func(r rune) bool { return unicode.In(r, unicode.Canadian_Aboriginal) })},
   114  	{`[\p{Lu}]`, mkCharClass(unicode.IsUpper)},
   115  	{`(?i)[\p{Lu}]`, mkCharClass(isUpperFold)},
   116  	{`\p{Any}`, `dot{}`},
   117  	{`\p{^Any}`, `cc{}`},
   118  	{`(?i)\p{ascii}`, `cc{0x0-0x7f 0x17f 0x212a}`},
   119  	{`\p{Assigned}`, mkCharClass(func(r rune) bool { return !unicode.In(r, unicode.Cn) })},
   120  	{`\p{^Assigned}`, mkCharClass(func(r rune) bool { return unicode.In(r, unicode.Cn) })},
   121  
   122  	// Hex, octal.
   123  	{`[\012-\234]\141`, `cat{cc{0xa-0x9c}lit{a}}`},
   124  	{`[\x{41}-\x7a]\x61`, `cat{cc{0x41-0x7a}lit{a}}`},
   125  
   126  	// More interesting regular expressions.
   127  	{`a{,2}`, `str{a{,2}}`},
   128  	{`\.\^\$\\`, `str{.^$\}`},
   129  	{`[a-zABC]`, `cc{0x41-0x43 0x61-0x7a}`},
   130  	{`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
   131  	{`[α-ε☺]`, `cc{0x3b1-0x3b5 0x263a}`}, // utf-8
   132  	{`a*{`, `cat{star{lit{a}}lit{{}}`},
   133  
   134  	// Test precedences
   135  	{`(?:ab)*`, `star{str{ab}}`},
   136  	{`(ab)*`, `star{cap{str{ab}}}`},
   137  	{`ab|cd`, `alt{str{ab}str{cd}}`},
   138  	{`a(b|c)d`, `cat{lit{a}cap{cc{0x62-0x63}}lit{d}}`},
   139  
   140  	// Test flattening.
   141  	{`(?:a)`, `lit{a}`},
   142  	{`(?:ab)(?:cd)`, `str{abcd}`},
   143  	{`(?:a+b+)(?:c+d+)`, `cat{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
   144  	{`(?:a+|b+)|(?:c+|d+)`, `alt{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
   145  	{`(?:a|b)|(?:c|d)`, `cc{0x61-0x64}`},
   146  	{`a|.`, `dot{}`},
   147  	{`.|a`, `dot{}`},
   148  	{`(?:[abc]|A|Z|hello|world)`, `alt{cc{0x41 0x5a 0x61-0x63}str{hello}str{world}}`},
   149  	{`(?:[abc]|A|Z)`, `cc{0x41 0x5a 0x61-0x63}`},
   150  
   151  	// Test Perl quoted literals
   152  	{`\Q+|*?{[\E`, `str{+|*?{[}`},
   153  	{`\Q+\E+`, `plus{lit{+}}`},
   154  	{`\Qab\E+`, `cat{lit{a}plus{lit{b}}}`},
   155  	{`\Q\\E`, `lit{\}`},
   156  	{`\Q\\\E`, `str{\\}`},
   157  
   158  	// Test Perl \A and \z
   159  	{`(?m)^`, `bol{}`},
   160  	{`(?m)$`, `eol{}`},
   161  	{`(?-m)^`, `bot{}`},
   162  	{`(?-m)$`, `eot{}`},
   163  	{`(?m)\A`, `bot{}`},
   164  	{`(?m)\z`, `eot{\z}`},
   165  	{`(?-m)\A`, `bot{}`},
   166  	{`(?-m)\z`, `eot{\z}`},
   167  
   168  	// Test named captures
   169  	{`(?P<name>a)`, `cap{name:lit{a}}`},
   170  	{`(?<name>a)`, `cap{name:lit{a}}`},
   171  
   172  	// Case-folded literals
   173  	{`[Aa]`, `litfold{A}`},
   174  	{`[\x{100}\x{101}]`, `litfold{Ā}`},
   175  	{`[Δδ]`, `litfold{Δ}`},
   176  
   177  	// Strings
   178  	{`abcde`, `str{abcde}`},
   179  	{`[Aa][Bb]cd`, `cat{strfold{AB}str{cd}}`},
   180  
   181  	// Factoring.
   182  	{`abc|abd|aef|bcx|bcy`, `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}cat{str{bc}cc{0x78-0x79}}}`},
   183  	{`ax+y|ax+z|ay+w`, `cat{lit{a}alt{cat{plus{lit{x}}lit{y}}cat{plus{lit{x}}lit{z}}cat{plus{lit{y}}lit{w}}}}`},
   184  
   185  	// Bug fixes.
   186  	{`(?:.)`, `dot{}`},
   187  	{`(?:x|(?:xa))`, `cat{lit{x}alt{emp{}lit{a}}}`},
   188  	{`(?:.|(?:.a))`, `cat{dot{}alt{emp{}lit{a}}}`},
   189  	{`(?:A(?:A|a))`, `cat{lit{A}litfold{A}}`},
   190  	{`(?:A|a)`, `litfold{A}`},
   191  	{`A|(?:A|a)`, `litfold{A}`},
   192  	{`(?s).`, `dot{}`},
   193  	{`(?-s).`, `dnl{}`},
   194  	{`(?:(?:^).)`, `cat{bol{}dot{}}`},
   195  	{`(?-s)(?:(?:^).)`, `cat{bol{}dnl{}}`},
   196  	{`[\s\S]a`, `cat{cc{0x0-0x10ffff}lit{a}}`},
   197  
   198  	// RE2 prefix_tests
   199  	{`abc|abd`, `cat{str{ab}cc{0x63-0x64}}`},
   200  	{`a(?:b)c|abd`, `cat{str{ab}cc{0x63-0x64}}`},
   201  	{`abc|abd|aef|bcx|bcy`,
   202  		`alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}` +
   203  			`cat{str{bc}cc{0x78-0x79}}}`},
   204  	{`abc|x|abd`, `alt{str{abc}lit{x}str{abd}}`},
   205  	{`(?i)abc|ABD`, `cat{strfold{AB}cc{0x43-0x44 0x63-0x64}}`},
   206  	{`[ab]c|[ab]d`, `cat{cc{0x61-0x62}cc{0x63-0x64}}`},
   207  	{`.c|.d`, `cat{dot{}cc{0x63-0x64}}`},
   208  	{`x{2}|x{2}[0-9]`,
   209  		`cat{rep{2,2 lit{x}}alt{emp{}cc{0x30-0x39}}}`},
   210  	{`x{2}y|x{2}[0-9]y`,
   211  		`cat{rep{2,2 lit{x}}alt{lit{y}cat{cc{0x30-0x39}lit{y}}}}`},
   212  	{`a.*?c|a.*?b`,
   213  		`cat{lit{a}alt{cat{nstar{dot{}}lit{c}}cat{nstar{dot{}}lit{b}}}}`},
   214  
   215  	// Valid repetitions.
   216  	{`((((((((((x{2}){2}){2}){2}){2}){2}){2}){2}){2}))`, ``},
   217  	{`((((((((((x{1}){2}){2}){2}){2}){2}){2}){2}){2}){2})`, ``},
   218  
   219  	// Valid nesting.
   220  	{strings.Repeat("(", 999) + strings.Repeat(")", 999), ``},
   221  	{strings.Repeat("(?:", 999) + strings.Repeat(")*", 999), ``},
   222  	{"(" + strings.Repeat("|", 12345) + ")", ``}, // not nested at all
   223  }
   224  
   225  const testFlags = MatchNL | PerlX | UnicodeGroups
   226  
   227  func TestParseSimple(t *testing.T) {
   228  	testParseDump(t, parseTests, testFlags)
   229  }
   230  
   231  var foldcaseTests = []parseTest{
   232  	{`AbCdE`, `strfold{ABCDE}`},
   233  	{`[Aa]`, `litfold{A}`},
   234  	{`a`, `litfold{A}`},
   235  
   236  	// 0x17F is an old English long s (looks like an f) and folds to s.
   237  	// 0x212A is the Kelvin symbol and folds to k.
   238  	{`A[F-g]`, `cat{litfold{A}cc{0x41-0x7a 0x17f 0x212a}}`}, // [Aa][A-z...]
   239  	{`[[:upper:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
   240  	{`[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
   241  }
   242  
   243  func TestParseFoldCase(t *testing.T) {
   244  	testParseDump(t, foldcaseTests, FoldCase)
   245  }
   246  
   247  var literalTests = []parseTest{
   248  	{"(|)^$.[*+?]{5,10},\\", "str{(|)^$.[*+?]{5,10},\\}"},
   249  }
   250  
   251  func TestParseLiteral(t *testing.T) {
   252  	testParseDump(t, literalTests, Literal)
   253  }
   254  
   255  var matchnlTests = []parseTest{
   256  	{`.`, `dot{}`},
   257  	{"\n", "lit{\n}"},
   258  	{`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
   259  	{`[a\n]`, `cc{0xa 0x61}`},
   260  }
   261  
   262  func TestParseMatchNL(t *testing.T) {
   263  	testParseDump(t, matchnlTests, MatchNL)
   264  }
   265  
   266  var nomatchnlTests = []parseTest{
   267  	{`.`, `dnl{}`},
   268  	{"\n", "lit{\n}"},
   269  	{`[^a]`, `cc{0x0-0x9 0xb-0x60 0x62-0x10ffff}`},
   270  	{`[a\n]`, `cc{0xa 0x61}`},
   271  }
   272  
   273  func TestParseNoMatchNL(t *testing.T) {
   274  	testParseDump(t, nomatchnlTests, 0)
   275  }
   276  
   277  // Test Parse -> Dump.
   278  func testParseDump(t *testing.T, tests []parseTest, flags Flags) {
   279  	for _, tt := range tests {
   280  		re, err := Parse(tt.Regexp, flags)
   281  		if err != nil {
   282  			t.Errorf("Parse(%#q): %v", tt.Regexp, err)
   283  			continue
   284  		}
   285  		if tt.Dump == "" {
   286  			// It parsed. That's all we care about.
   287  			continue
   288  		}
   289  		d := dump(re)
   290  		if d != tt.Dump {
   291  			t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
   292  		}
   293  	}
   294  }
   295  
   296  // dump prints a string representation of the regexp showing
   297  // the structure explicitly.
   298  func dump(re *Regexp) string {
   299  	var b strings.Builder
   300  	dumpRegexp(&b, re)
   301  	return b.String()
   302  }
   303  
   304  var opNames = []string{
   305  	OpNoMatch:        "no",
   306  	OpEmptyMatch:     "emp",
   307  	OpLiteral:        "lit",
   308  	OpCharClass:      "cc",
   309  	OpAnyCharNotNL:   "dnl",
   310  	OpAnyChar:        "dot",
   311  	OpBeginLine:      "bol",
   312  	OpEndLine:        "eol",
   313  	OpBeginText:      "bot",
   314  	OpEndText:        "eot",
   315  	OpWordBoundary:   "wb",
   316  	OpNoWordBoundary: "nwb",
   317  	OpCapture:        "cap",
   318  	OpStar:           "star",
   319  	OpPlus:           "plus",
   320  	OpQuest:          "que",
   321  	OpRepeat:         "rep",
   322  	OpConcat:         "cat",
   323  	OpAlternate:      "alt",
   324  }
   325  
   326  // dumpRegexp writes an encoding of the syntax tree for the regexp re to b.
   327  // It is used during testing to distinguish between parses that might print
   328  // the same using re's String method.
   329  func dumpRegexp(b *strings.Builder, re *Regexp) {
   330  	if int(re.Op) >= len(opNames) || opNames[re.Op] == "" {
   331  		fmt.Fprintf(b, "op%d", re.Op)
   332  	} else {
   333  		switch re.Op {
   334  		default:
   335  			b.WriteString(opNames[re.Op])
   336  		case OpStar, OpPlus, OpQuest, OpRepeat:
   337  			if re.Flags&NonGreedy != 0 {
   338  				b.WriteByte('n')
   339  			}
   340  			b.WriteString(opNames[re.Op])
   341  		case OpLiteral:
   342  			if len(re.Rune) > 1 {
   343  				b.WriteString("str")
   344  			} else {
   345  				b.WriteString("lit")
   346  			}
   347  			if re.Flags&FoldCase != 0 {
   348  				for _, r := range re.Rune {
   349  					if unicode.SimpleFold(r) != r {
   350  						b.WriteString("fold")
   351  						break
   352  					}
   353  				}
   354  			}
   355  		}
   356  	}
   357  	b.WriteByte('{')
   358  	switch re.Op {
   359  	case OpEndText:
   360  		if re.Flags&WasDollar == 0 {
   361  			b.WriteString(`\z`)
   362  		}
   363  	case OpLiteral:
   364  		for _, r := range re.Rune {
   365  			b.WriteRune(r)
   366  		}
   367  	case OpConcat, OpAlternate:
   368  		for _, sub := range re.Sub {
   369  			dumpRegexp(b, sub)
   370  		}
   371  	case OpStar, OpPlus, OpQuest:
   372  		dumpRegexp(b, re.Sub[0])
   373  	case OpRepeat:
   374  		fmt.Fprintf(b, "%d,%d ", re.Min, re.Max)
   375  		dumpRegexp(b, re.Sub[0])
   376  	case OpCapture:
   377  		if re.Name != "" {
   378  			b.WriteString(re.Name)
   379  			b.WriteByte(':')
   380  		}
   381  		dumpRegexp(b, re.Sub[0])
   382  	case OpCharClass:
   383  		sep := ""
   384  		for i := 0; i < len(re.Rune); i += 2 {
   385  			b.WriteString(sep)
   386  			sep = " "
   387  			lo, hi := re.Rune[i], re.Rune[i+1]
   388  			if lo == hi {
   389  				fmt.Fprintf(b, "%#x", lo)
   390  			} else {
   391  				fmt.Fprintf(b, "%#x-%#x", lo, hi)
   392  			}
   393  		}
   394  	}
   395  	b.WriteByte('}')
   396  }
   397  
   398  func mkCharClass(f func(rune) bool) string {
   399  	re := &Regexp{Op: OpCharClass}
   400  	lo := rune(-1)
   401  	for i := rune(0); i <= unicode.MaxRune; i++ {
   402  		if f(i) {
   403  			if lo < 0 {
   404  				lo = i
   405  			}
   406  		} else {
   407  			if lo >= 0 {
   408  				re.Rune = append(re.Rune, lo, i-1)
   409  				lo = -1
   410  			}
   411  		}
   412  	}
   413  	if lo >= 0 {
   414  		re.Rune = append(re.Rune, lo, unicode.MaxRune)
   415  	}
   416  	return dump(re)
   417  }
   418  
   419  func isUpperFold(r rune) bool {
   420  	if unicode.IsUpper(r) {
   421  		return true
   422  	}
   423  	c := unicode.SimpleFold(r)
   424  	for c != r {
   425  		if unicode.IsUpper(c) {
   426  			return true
   427  		}
   428  		c = unicode.SimpleFold(c)
   429  	}
   430  	return false
   431  }
   432  
   433  func TestFoldConstants(t *testing.T) {
   434  	last := rune(-1)
   435  	for i := rune(0); i <= unicode.MaxRune; i++ {
   436  		if unicode.SimpleFold(i) == i {
   437  			continue
   438  		}
   439  		if last == -1 && minFold != i {
   440  			t.Errorf("minFold=%#U should be %#U", minFold, i)
   441  		}
   442  		last = i
   443  	}
   444  	if maxFold != last {
   445  		t.Errorf("maxFold=%#U should be %#U", maxFold, last)
   446  	}
   447  }
   448  
   449  func TestAppendRangeCollapse(t *testing.T) {
   450  	// AppendRange should collapse each of the new ranges
   451  	// into the earlier ones (it looks back two ranges), so that
   452  	// the slice never grows very large.
   453  	// Note that we are not calling cleanClass.
   454  	var r []rune
   455  	for i := rune('A'); i <= 'Z'; i++ {
   456  		r = appendRange(r, i, i)
   457  		r = appendRange(r, i+'a'-'A', i+'a'-'A')
   458  	}
   459  	if string(r) != "AZaz" {
   460  		t.Errorf("appendRange interlaced A-Z a-z = %s, want AZaz", string(r))
   461  	}
   462  }
   463  
   464  var invalidRegexps = []string{
   465  	`(`,
   466  	`)`,
   467  	`(a`,
   468  	`a)`,
   469  	`(a))`,
   470  	`(a|b|`,
   471  	`a|b|)`,
   472  	`(a|b|))`,
   473  	`(a|b`,
   474  	`a|b)`,
   475  	`(a|b))`,
   476  	`[a-z`,
   477  	`([a-z)`,
   478  	`[a-z)`,
   479  	`([a-z]))`,
   480  	`x{1001}`,
   481  	`x{9876543210}`,
   482  	`x{2,1}`,
   483  	`x{1,9876543210}`,
   484  	"\xff", // Invalid UTF-8
   485  	"[\xff]",
   486  	"[\\\xff]",
   487  	"\\\xff",
   488  	`(?P<name>a`,
   489  	`(?P<name>`,
   490  	`(?P<name`,
   491  	`(?P<x y>a)`,
   492  	`(?P<>a)`,
   493  	`(?<name>a`,
   494  	`(?<name>`,
   495  	`(?<name`,
   496  	`(?<x y>a)`,
   497  	`(?<>a)`,
   498  	`[a-Z]`,
   499  	`(?i)[a-Z]`,
   500  	`\Q\E*`,
   501  	`a{100000}`,  // too much repetition
   502  	`a{100000,}`, // too much repetition
   503  	"((((((((((x{2}){2}){2}){2}){2}){2}){2}){2}){2}){2})",    // too much repetition
   504  	strings.Repeat("(", 1000) + strings.Repeat(")", 1000),    // too deep
   505  	strings.Repeat("(?:", 1000) + strings.Repeat(")*", 1000), // too deep
   506  	"(" + strings.Repeat("(xx?)", 1000) + "){1000}",          // too long
   507  	strings.Repeat("(xx?){1000}", 1000),                      // too long
   508  	strings.Repeat(`\pL`, 27000),                             // too many runes
   509  }
   510  
   511  var onlyPerl = []string{
   512  	`[a-b-c]`,
   513  	`\Qabc\E`,
   514  	`\Q*+?{[\E`,
   515  	`\Q\\E`,
   516  	`\Q\\\E`,
   517  	`\Q\\\\E`,
   518  	`\Q\\\\\E`,
   519  	`(?:a)`,
   520  	`(?P<name>a)`,
   521  }
   522  
   523  var onlyPOSIX = []string{
   524  	"a++",
   525  	"a**",
   526  	"a?*",
   527  	"a+*",
   528  	"a{1}*",
   529  	".{1}{2}.{3}",
   530  }
   531  
   532  func TestParseInvalidRegexps(t *testing.T) {
   533  	for _, regexp := range invalidRegexps {
   534  		if re, err := Parse(regexp, Perl); err == nil {
   535  			t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
   536  		}
   537  		if re, err := Parse(regexp, POSIX); err == nil {
   538  			t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
   539  		}
   540  	}
   541  	for _, regexp := range onlyPerl {
   542  		if _, err := Parse(regexp, Perl); err != nil {
   543  			t.Errorf("Parse(%#q, Perl): %v", regexp, err)
   544  		}
   545  		if re, err := Parse(regexp, POSIX); err == nil {
   546  			t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
   547  		}
   548  	}
   549  	for _, regexp := range onlyPOSIX {
   550  		if re, err := Parse(regexp, Perl); err == nil {
   551  			t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
   552  		}
   553  		if _, err := Parse(regexp, POSIX); err != nil {
   554  			t.Errorf("Parse(%#q, POSIX): %v", regexp, err)
   555  		}
   556  	}
   557  }
   558  
   559  func TestToStringEquivalentParse(t *testing.T) {
   560  	for _, tt := range parseTests {
   561  		re, err := Parse(tt.Regexp, testFlags)
   562  		if err != nil {
   563  			t.Errorf("Parse(%#q): %v", tt.Regexp, err)
   564  			continue
   565  		}
   566  		if tt.Dump == "" {
   567  			// It parsed. That's all we care about.
   568  			continue
   569  		}
   570  		d := dump(re)
   571  		if d != tt.Dump {
   572  			t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
   573  			continue
   574  		}
   575  
   576  		s := re.String()
   577  		if s != tt.Regexp {
   578  			// If ToString didn't return the original regexp,
   579  			// it must have found one with fewer parens.
   580  			// Unfortunately we can't check the length here, because
   581  			// ToString produces "\\{" for a literal brace,
   582  			// but "{" is a shorter equivalent in some contexts.
   583  			nre, err := Parse(s, testFlags)
   584  			if err != nil {
   585  				t.Errorf("Parse(%#q.String() = %#q): %v", tt.Regexp, s, err)
   586  				continue
   587  			}
   588  			nd := dump(nre)
   589  			if d != nd {
   590  				t.Errorf("Parse(%#q) -> %#q; %#q vs %#q", tt.Regexp, s, d, nd)
   591  			}
   592  
   593  			ns := nre.String()
   594  			if s != ns {
   595  				t.Errorf("Parse(%#q) -> %#q -> %#q", tt.Regexp, s, ns)
   596  			}
   597  		}
   598  	}
   599  }
   600  
   601  var stringTests = []struct {
   602  	re  string
   603  	out string
   604  }{
   605  	{`x(?i:ab*c|d?e)1`, `x(?i:AB*C|D?E)1`},
   606  	{`x(?i:ab*cd?e)1`, `x(?i:AB*CD?E)1`},
   607  	{`0(?i:ab*c|d?e)1`, `(?i:0(?:AB*C|D?E)1)`},
   608  	{`0(?i:ab*cd?e)1`, `(?i:0AB*CD?E1)`},
   609  	{`x(?i:ab*c|d?e)`, `x(?i:AB*C|D?E)`},
   610  	{`x(?i:ab*cd?e)`, `x(?i:AB*CD?E)`},
   611  	{`0(?i:ab*c|d?e)`, `(?i:0(?:AB*C|D?E))`},
   612  	{`0(?i:ab*cd?e)`, `(?i:0AB*CD?E)`},
   613  	{`(?i:ab*c|d?e)1`, `(?i:(?:AB*C|D?E)1)`},
   614  	{`(?i:ab*cd?e)1`, `(?i:AB*CD?E1)`},
   615  	{`(?i:ab)[123](?i:cd)`, `(?i:AB[1-3]CD)`},
   616  	{`(?i:ab*c|d?e)`, `(?i:AB*C|D?E)`},
   617  	{`[Aa][Bb]`, `(?i:AB)`},
   618  	{`[Aa][Bb]*[Cc]`, `(?i:AB*C)`},
   619  	{`A(?:[Bb][Cc]|[Dd])[Zz]`, `A(?i:(?:BC|D)Z)`},
   620  	{`[Aa](?:[Bb][Cc]|[Dd])Z`, `(?i:A(?:BC|D))Z`},
   621  }
   622  
   623  func TestString(t *testing.T) {
   624  	for _, tt := range stringTests {
   625  		re, err := Parse(tt.re, Perl)
   626  		if err != nil {
   627  			t.Errorf("Parse(%#q): %v", tt.re, err)
   628  			continue
   629  		}
   630  		out := re.String()
   631  		if out != tt.out {
   632  			t.Errorf("Parse(%#q).String() = %#q, want %#q", tt.re, out, tt.out)
   633  		}
   634  	}
   635  }
   636
View as plain text