libgo/go/regexp/syntax/parse_test.go

   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         "bytes"
   9         "fmt"
  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{Lu}]`, mkCharClass(unicode.IsUpper)},
 111         {`(?i)[\p{Lu}]`, mkCharClass(isUpperFold)},
 112         {`\p{Any}`, `dot{}`},
 113         {`\p{^Any}`, `cc{}`},
 114
 115         // Hex, octal.
 116         {`[\012-\234]\141`, `cat{cc{0xa-0x9c}lit{a}}`},
 117         {`[\x{41}-\x7a]\x61`, `cat{cc{0x41-0x7a}lit{a}}`},
 118
 119         // More interesting regular expressions.
 120         {`a{,2}`, `str{a{,2}}`},
 121         {`\.\^\$\\`, `str{.^$\}`},
 122         {`[a-zABC]`, `cc{0x41-0x43 0x61-0x7a}`},
 123         {`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
 124         {`[α-ε☺]`, `cc{0x3b1-0x3b5 0x263a}`}, // utf-8
 125         {`a*{`, `cat{star{lit{a}}lit{{}}`},
 126
 127         // Test precedences
 128         {`(?:ab)*`, `star{str{ab}}`},
 129         {`(ab)*`, `star{cap{str{ab}}}`},
 130         {`ab|cd`, `alt{str{ab}str{cd}}`},
 131         {`a(b|c)d`, `cat{lit{a}cap{cc{0x62-0x63}}lit{d}}`},
 132
 133         // Test flattening.
 134         {`(?:a)`, `lit{a}`},
 135         {`(?:ab)(?:cd)`, `str{abcd}`},
 136         {`(?:a+b+)(?:c+d+)`, `cat{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
 137         {`(?:a+|b+)|(?:c+|d+)`, `alt{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
 138         {`(?:a|b)|(?:c|d)`, `cc{0x61-0x64}`},
 139         {`a|.`, `dot{}`},
 140         {`.|a`, `dot{}`},
 141         {`(?:[abc]|A|Z|hello|world)`, `alt{cc{0x41 0x5a 0x61-0x63}str{hello}str{world}}`},
 142         {`(?:[abc]|A|Z)`, `cc{0x41 0x5a 0x61-0x63}`},
 143
 144         // Test Perl quoted literals
 145         {`\Q+|*?{[\E`, `str{+|*?{[}`},
 146         {`\Q+\E+`, `plus{lit{+}}`},
 147         {`\Q\\E`, `lit{\}`},
 148         {`\Q\\\E`, `str{\\}`},
 149
 150         // Test Perl \A and \z
 151         {`(?m)^`, `bol{}`},
 152         {`(?m)$`, `eol{}`},
 153         {`(?-m)^`, `bot{}`},
 154         {`(?-m)$`, `eot{}`},
 155         {`(?m)\A`, `bot{}`},
 156         {`(?m)\z`, `eot{\z}`},
 157         {`(?-m)\A`, `bot{}`},
 158         {`(?-m)\z`, `eot{\z}`},
 159
 160         // Test named captures
 161         {`(?P<name>a)`, `cap{name:lit{a}}`},
 162
 163         // Case-folded literals
 164         {`[Aa]`, `litfold{A}`},
 165         {`[\x{100}\x{101}]`, `litfold{Ā}`},
 166         {`[Δδ]`, `litfold{Δ}`},
 167
 168         // Strings
 169         {`abcde`, `str{abcde}`},
 170         {`[Aa][Bb]cd`, `cat{strfold{AB}str{cd}}`},
 171
 172         // Factoring.
 173         {`abc|abd|aef|bcx|bcy`, `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}cat{str{bc}cc{0x78-0x79}}}`},
 174         {`ax+y|ax+z|ay+w`, `cat{lit{a}alt{cat{plus{lit{x}}cc{0x79-0x7a}}cat{plus{lit{y}}lit{w}}}}`},
 175
 176         // Bug fixes.
 177         {`(?:.)`, `dot{}`},
 178         {`(?:x|(?:xa))`, `cat{lit{x}alt{emp{}lit{a}}}`},
 179         {`(?:.|(?:.a))`, `cat{dot{}alt{emp{}lit{a}}}`},
 180         {`(?:A(?:A|a))`, `cat{lit{A}litfold{A}}`},
 181         {`(?:A|a)`, `litfold{A}`},
 182         {`A|(?:A|a)`, `litfold{A}`},
 183         {`(?s).`, `dot{}`},
 184         {`(?-s).`, `dnl{}`},
 185         {`(?:(?:^).)`, `cat{bol{}dot{}}`},
 186         {`(?-s)(?:(?:^).)`, `cat{bol{}dnl{}}`},
 187
 188         // RE2 prefix_tests
 189         {`abc|abd`, `cat{str{ab}cc{0x63-0x64}}`},
 190         {`a(?:b)c|abd`, `cat{str{ab}cc{0x63-0x64}}`},
 191         {`abc|abd|aef|bcx|bcy`,
 192                 `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}` +
 193                         `cat{str{bc}cc{0x78-0x79}}}`},
 194         {`abc|x|abd`, `alt{str{abc}lit{x}str{abd}}`},
 195         {`(?i)abc|ABD`, `cat{strfold{AB}cc{0x43-0x44 0x63-0x64}}`},
 196         {`[ab]c|[ab]d`, `cat{cc{0x61-0x62}cc{0x63-0x64}}`},
 197         {`(?:xx|yy)c|(?:xx|yy)d`,
 198                 `cat{alt{str{xx}str{yy}}cc{0x63-0x64}}`},
 199         {`x{2}|x{2}[0-9]`,
 200                 `cat{rep{2,2 lit{x}}alt{emp{}cc{0x30-0x39}}}`},
 201         {`x{2}y|x{2}[0-9]y`,
 202                 `cat{rep{2,2 lit{x}}alt{lit{y}cat{cc{0x30-0x39}lit{y}}}}`},
 203 }
 204
 205 const testFlags = MatchNL | PerlX | UnicodeGroups
 206
 207 func TestParseSimple(t *testing.T) {
 208         testParseDump(t, parseTests, testFlags)
 209 }
 210
 211 var foldcaseTests = []parseTest{
 212         {`AbCdE`, `strfold{ABCDE}`},
 213         {`[Aa]`, `litfold{A}`},
 214         {`a`, `litfold{A}`},
 215
 216         // 0x17F is an old English long s (looks like an f) and folds to s.
 217         // 0x212A is the Kelvin symbol and folds to k.
 218         {`A[F-g]`, `cat{litfold{A}cc{0x41-0x7a 0x17f 0x212a}}`}, // [Aa][A-z...]
 219         {`[[:upper:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
 220         {`[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
 221 }
 222
 223 func TestParseFoldCase(t *testing.T) {
 224         testParseDump(t, foldcaseTests, FoldCase)
 225 }
 226
 227 var literalTests = []parseTest{
 228         {"(|)^$.[*+?]{5,10},\\", "str{(|)^$.[*+?]{5,10},\\}"},
 229 }
 230
 231 func TestParseLiteral(t *testing.T) {
 232         testParseDump(t, literalTests, Literal)
 233 }
 234
 235 var matchnlTests = []parseTest{
 236         {`.`, `dot{}`},
 237         {"\n", "lit{\n}"},
 238         {`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
 239         {`[a\n]`, `cc{0xa 0x61}`},
 240 }
 241
 242 func TestParseMatchNL(t *testing.T) {
 243         testParseDump(t, matchnlTests, MatchNL)
 244 }
 245
 246 var nomatchnlTests = []parseTest{
 247         {`.`, `dnl{}`},
 248         {"\n", "lit{\n}"},
 249         {`[^a]`, `cc{0x0-0x9 0xb-0x60 0x62-0x10ffff}`},
 250         {`[a\n]`, `cc{0xa 0x61}`},
 251 }
 252
 253 func TestParseNoMatchNL(t *testing.T) {
 254         testParseDump(t, nomatchnlTests, 0)
 255 }
 256
 257 // Test Parse -> Dump.
 258 func testParseDump(t *testing.T, tests []parseTest, flags Flags) {
 259         for _, tt := range tests {
 260                 re, err := Parse(tt.Regexp, flags)
 261                 if err != nil {
 262                         t.Errorf("Parse(%#q): %v", tt.Regexp, err)
 263                         continue
 264                 }
 265                 d := dump(re)
 266                 if d != tt.Dump {
 267                         t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
 268                 }
 269         }
 270 }
 271
 272 // dump prints a string representation of the regexp showing
 273 // the structure explicitly.
 274 func dump(re *Regexp) string {
 275         var b bytes.Buffer
 276         dumpRegexp(&b, re)
 277         return b.String()
 278 }
 279
 280 var opNames = []string{
 281         OpNoMatch:        "no",
 282         OpEmptyMatch:     "emp",
 283         OpLiteral:        "lit",
 284         OpCharClass:      "cc",
 285         OpAnyCharNotNL:   "dnl",
 286         OpAnyChar:        "dot",
 287         OpBeginLine:      "bol",
 288         OpEndLine:        "eol",
 289         OpBeginText:      "bot",
 290         OpEndText:        "eot",
 291         OpWordBoundary:   "wb",
 292         OpNoWordBoundary: "nwb",
 293         OpCapture:        "cap",
 294         OpStar:           "star",
 295         OpPlus:           "plus",
 296         OpQuest:          "que",
 297         OpRepeat:         "rep",
 298         OpConcat:         "cat",
 299         OpAlternate:      "alt",
 300 }
 301
 302 // dumpRegexp writes an encoding of the syntax tree for the regexp re to b.
 303 // It is used during testing to distinguish between parses that might print
 304 // the same using re's String method.
 305 func dumpRegexp(b *bytes.Buffer, re *Regexp) {
 306         if int(re.Op) >= len(opNames) || opNames[re.Op] == "" {
 307                 fmt.Fprintf(b, "op%d", re.Op)
 308         } else {
 309                 switch re.Op {
 310                 default:
 311                         b.WriteString(opNames[re.Op])
 312                 case OpStar, OpPlus, OpQuest, OpRepeat:
 313                         if re.Flags&NonGreedy != 0 {
 314                                 b.WriteByte('n')
 315                         }
 316                         b.WriteString(opNames[re.Op])
 317                 case OpLiteral:
 318                         if len(re.Rune) > 1 {
 319                                 b.WriteString("str")
 320                         } else {
 321                                 b.WriteString("lit")
 322                         }
 323                         if re.Flags&FoldCase != 0 {
 324                                 for _, r := range re.Rune {
 325                                         if unicode.SimpleFold(r) != r {
 326                                                 b.WriteString("fold")
 327                                                 break
 328                                         }
 329                                 }
 330                         }
 331                 }
 332         }
 333         b.WriteByte('{')
 334         switch re.Op {
 335         case OpEndText:
 336                 if re.Flags&WasDollar == 0 {
 337                         b.WriteString(`\z`)
 338                 }
 339         case OpLiteral:
 340                 for _, r := range re.Rune {
 341                         b.WriteRune(r)
 342                 }
 343         case OpConcat, OpAlternate:
 344                 for _, sub := range re.Sub {
 345                         dumpRegexp(b, sub)
 346                 }
 347         case OpStar, OpPlus, OpQuest:
 348                 dumpRegexp(b, re.Sub[0])
 349         case OpRepeat:
 350                 fmt.Fprintf(b, "%d,%d ", re.Min, re.Max)
 351                 dumpRegexp(b, re.Sub[0])
 352         case OpCapture:
 353                 if re.Name != "" {
 354                         b.WriteString(re.Name)
 355                         b.WriteByte(':')
 356                 }
 357                 dumpRegexp(b, re.Sub[0])
 358         case OpCharClass:
 359                 sep := ""
 360                 for i := 0; i < len(re.Rune); i += 2 {
 361                         b.WriteString(sep)
 362                         sep = " "
 363                         lo, hi := re.Rune[i], re.Rune[i+1]
 364                         if lo == hi {
 365                                 fmt.Fprintf(b, "%#x", lo)
 366                         } else {
 367                                 fmt.Fprintf(b, "%#x-%#x", lo, hi)
 368                         }
 369                 }
 370         }
 371         b.WriteByte('}')
 372 }
 373
 374 func mkCharClass(f func(rune) bool) string {
 375         re := &Regexp{Op: OpCharClass}
 376         lo := rune(-1)
 377         for i := rune(0); i <= unicode.MaxRune; i++ {
 378                 if f(i) {
 379                         if lo < 0 {
 380                                 lo = i
 381                         }
 382                 } else {
 383                         if lo >= 0 {
 384                                 re.Rune = append(re.Rune, lo, i-1)
 385                                 lo = -1
 386                         }
 387                 }
 388         }
 389         if lo >= 0 {
 390                 re.Rune = append(re.Rune, lo, unicode.MaxRune)
 391         }
 392         return dump(re)
 393 }
 394
 395 func isUpperFold(r rune) bool {
 396         if unicode.IsUpper(r) {
 397                 return true
 398         }
 399         c := unicode.SimpleFold(r)
 400         for c != r {
 401                 if unicode.IsUpper(c) {
 402                         return true
 403                 }
 404                 c = unicode.SimpleFold(c)
 405         }
 406         return false
 407 }
 408
 409 func TestFoldConstants(t *testing.T) {
 410         last := rune(-1)
 411         for i := rune(0); i <= unicode.MaxRune; i++ {
 412                 if unicode.SimpleFold(i) == i {
 413                         continue
 414                 }
 415                 if last == -1 && minFold != i {
 416                         t.Errorf("minFold=%#U should be %#U", minFold, i)
 417                 }
 418                 last = i
 419         }
 420         if maxFold != last {
 421                 t.Errorf("maxFold=%#U should be %#U", maxFold, last)
 422         }
 423 }
 424
 425 func TestAppendRangeCollapse(t *testing.T) {
 426         // AppendRange should collapse each of the new ranges
 427         // into the earlier ones (it looks back two ranges), so that
 428         // the slice never grows very large.
 429         // Note that we are not calling cleanClass.
 430         var r []rune
 431         for i := rune('A'); i <= 'Z'; i++ {
 432                 r = appendRange(r, i, i)
 433                 r = appendRange(r, i+'a'-'A', i+'a'-'A')
 434         }
 435         if string(r) != "AZaz" {
 436                 t.Errorf("appendRange interlaced A-Z a-z = %s, want AZaz", string(r))
 437         }
 438 }
 439
 440 var invalidRegexps = []string{
 441         `(`,
 442         `)`,
 443         `(a`,
 444         `a)`,
 445         `(a))`,
 446         `(a|b|`,
 447         `a|b|)`,
 448         `(a|b|))`,
 449         `(a|b`,
 450         `a|b)`,
 451         `(a|b))`,
 452         `[a-z`,
 453         `([a-z)`,
 454         `[a-z)`,
 455         `([a-z]))`,
 456         `x{1001}`,
 457         `x{9876543210}`,
 458         `x{2,1}`,
 459         `x{1,9876543210}`,
 460         "\xff", // Invalid UTF-8
 461         "[\xff]",
 462         "[\\\xff]",
 463         "\\\xff",
 464         `(?P<name>a`,
 465         `(?P<name>`,
 466         `(?P<name`,
 467         `(?P<x y>a)`,
 468         `(?P<>a)`,
 469         `[a-Z]`,
 470         `(?i)[a-Z]`,
 471         `a{100000}`,
 472         `a{100000,}`,
 473 }
 474
 475 var onlyPerl = []string{
 476         `[a-b-c]`,
 477         `\Qabc\E`,
 478         `\Q*+?{[\E`,
 479         `\Q\\E`,
 480         `\Q\\\E`,
 481         `\Q\\\\E`,
 482         `\Q\\\\\E`,
 483         `(?:a)`,
 484         `(?P<name>a)`,
 485 }
 486
 487 var onlyPOSIX = []string{
 488         "a++",
 489         "a**",
 490         "a?*",
 491         "a+*",
 492         "a{1}*",
 493         ".{1}{2}.{3}",
 494 }
 495
 496 func TestParseInvalidRegexps(t *testing.T) {
 497         for _, regexp := range invalidRegexps {
 498                 if re, err := Parse(regexp, Perl); err == nil {
 499                         t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
 500                 }
 501                 if re, err := Parse(regexp, POSIX); err == nil {
 502                         t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
 503                 }
 504         }
 505         for _, regexp := range onlyPerl {
 506                 if _, err := Parse(regexp, Perl); err != nil {
 507                         t.Errorf("Parse(%#q, Perl): %v", regexp, err)
 508                 }
 509                 if re, err := Parse(regexp, POSIX); err == nil {
 510                         t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
 511                 }
 512         }
 513         for _, regexp := range onlyPOSIX {
 514                 if re, err := Parse(regexp, Perl); err == nil {
 515                         t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
 516                 }
 517                 if _, err := Parse(regexp, POSIX); err != nil {
 518                         t.Errorf("Parse(%#q, POSIX): %v", regexp, err)
 519                 }
 520         }
 521 }
 522
 523 func TestToStringEquivalentParse(t *testing.T) {
 524         for _, tt := range parseTests {
 525                 re, err := Parse(tt.Regexp, testFlags)
 526                 if err != nil {
 527                         t.Errorf("Parse(%#q): %v", tt.Regexp, err)
 528                         continue
 529                 }
 530                 d := dump(re)
 531                 if d != tt.Dump {
 532                         t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
 533                         continue
 534                 }
 535
 536                 s := re.String()
 537                 if s != tt.Regexp {
 538                         // If ToString didn't return the original regexp,
 539                         // it must have found one with fewer parens.
 540                         // Unfortunately we can't check the length here, because
 541                         // ToString produces "\\{" for a literal brace,
 542                         // but "{" is a shorter equivalent in some contexts.
 543                         nre, err := Parse(s, testFlags)
 544                         if err != nil {
 545                                 t.Errorf("Parse(%#q.String() = %#q): %v", tt.Regexp, s, err)
 546                                 continue
 547                         }
 548                         nd := dump(nre)
 549                         if d != nd {
 550                                 t.Errorf("Parse(%#q) -> %#q; %#q vs %#q", tt.Regexp, s, d, nd)
 551                         }
 552
 553                         ns := nre.String()
 554                         if s != ns {
 555                                 t.Errorf("Parse(%#q) -> %#q -> %#q", tt.Regexp, s, ns)
 556                         }
 557                 }
 558         }
 559 }