libgo/go/regexp/all_test.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package regexp
   6
   7 import (
   8         "os"
   9         "strings"
  10         "testing"
  11 )
  12
  13 var good_re = []string{
  14         ``,
  15         `.`,
  16         `^.$`,
  17         `a`,
  18         `a*`,
  19         `a+`,
  20         `a?`,
  21         `a|b`,
  22         `a*|b*`,
  23         `(a*|b)(c*|d)`,
  24         `[a-z]`,
  25         `[a-abc-c\-\]\[]`,
  26         `[a-z]+`,
  27         `[]`,
  28         `[abc]`,
  29         `[^1234]`,
  30         `[^\n]`,
  31         `\!\\`,
  32 }
  33
  34 type stringError struct {
  35         re  string
  36         err os.Error
  37 }
  38
  39 var bad_re = []stringError{
  40         {`*`, ErrBareClosure},
  41         {`+`, ErrBareClosure},
  42         {`?`, ErrBareClosure},
  43         {`(abc`, ErrUnmatchedLpar},
  44         {`abc)`, ErrUnmatchedRpar},
  45         {`x[a-z`, ErrUnmatchedLbkt},
  46         {`abc]`, ErrUnmatchedRbkt},
  47         {`[z-a]`, ErrBadRange},
  48         {`abc\`, ErrExtraneousBackslash},
  49         {`a**`, ErrBadClosure},
  50         {`a*+`, ErrBadClosure},
  51         {`a??`, ErrBadClosure},
  52         {`\x`, ErrBadBackslash},
  53 }
  54
  55 func compileTest(t *testing.T, expr string, error os.Error) *Regexp {
  56         re, err := Compile(expr)
  57         if err != error {
  58                 t.Error("compiling `", expr, "`; unexpected error: ", err.String())
  59         }
  60         return re
  61 }
  62
  63 func TestGoodCompile(t *testing.T) {
  64         for i := 0; i < len(good_re); i++ {
  65                 compileTest(t, good_re[i], nil)
  66         }
  67 }
  68
  69 func TestBadCompile(t *testing.T) {
  70         for i := 0; i < len(bad_re); i++ {
  71                 compileTest(t, bad_re[i].re, bad_re[i].err)
  72         }
  73 }
  74
  75 func matchTest(t *testing.T, test *FindTest) {
  76         re := compileTest(t, test.pat, nil)
  77         if re == nil {
  78                 return
  79         }
  80         m := re.MatchString(test.text)
  81         if m != (len(test.matches) > 0) {
  82                 t.Errorf("MatchString failure on %s: %t should be %t", test, m, len(test.matches) > 0)
  83         }
  84         // now try bytes
  85         m = re.Match([]byte(test.text))
  86         if m != (len(test.matches) > 0) {
  87                 t.Errorf("Match failure on %s: %t should be %t", test, m, len(test.matches) > 0)
  88         }
  89 }
  90
  91 func TestMatch(t *testing.T) {
  92         for _, test := range findTests {
  93                 matchTest(t, &test)
  94         }
  95 }
  96
  97 func matchFunctionTest(t *testing.T, test *FindTest) {
  98         m, err := MatchString(test.pat, test.text)
  99         if err == nil {
 100                 return
 101         }
 102         if m != (len(test.matches) > 0) {
 103                 t.Errorf("Match failure on %s: %t should be %t", test, m, len(test.matches) > 0)
 104         }
 105 }
 106
 107 func TestMatchFunction(t *testing.T) {
 108         for _, test := range findTests {
 109                 matchFunctionTest(t, &test)
 110         }
 111 }
 112
 113 type ReplaceTest struct {
 114         pattern, replacement, input, output string
 115 }
 116
 117 var replaceTests = []ReplaceTest{
 118         // Test empty input and/or replacement, with pattern that matches the empty string.
 119         {"", "", "", ""},
 120         {"", "x", "", "x"},
 121         {"", "", "abc", "abc"},
 122         {"", "x", "abc", "xaxbxcx"},
 123
 124         // Test empty input and/or replacement, with pattern that does not match the empty string.
 125         {"b", "", "", ""},
 126         {"b", "x", "", ""},
 127         {"b", "", "abc", "ac"},
 128         {"b", "x", "abc", "axc"},
 129         {"y", "", "", ""},
 130         {"y", "x", "", ""},
 131         {"y", "", "abc", "abc"},
 132         {"y", "x", "abc", "abc"},
 133
 134         // Multibyte characters -- verify that we don't try to match in the middle
 135         // of a character.
 136         {"[a-c]*", "x", "\u65e5", "x\u65e5x"},
 137         {"[^\u65e5]", "x", "abc\u65e5def", "xxx\u65e5xxx"},
 138
 139         // Start and end of a string.
 140         {"^[a-c]*", "x", "abcdabc", "xdabc"},
 141         {"[a-c]*$", "x", "abcdabc", "abcdx"},
 142         {"^[a-c]*$", "x", "abcdabc", "abcdabc"},
 143         {"^[a-c]*", "x", "abc", "x"},
 144         {"[a-c]*$", "x", "abc", "x"},
 145         {"^[a-c]*$", "x", "abc", "x"},
 146         {"^[a-c]*", "x", "dabce", "xdabce"},
 147         {"[a-c]*$", "x", "dabce", "dabcex"},
 148         {"^[a-c]*$", "x", "dabce", "dabce"},
 149         {"^[a-c]*", "x", "", "x"},
 150         {"[a-c]*$", "x", "", "x"},
 151         {"^[a-c]*$", "x", "", "x"},
 152
 153         {"^[a-c]+", "x", "abcdabc", "xdabc"},
 154         {"[a-c]+$", "x", "abcdabc", "abcdx"},
 155         {"^[a-c]+$", "x", "abcdabc", "abcdabc"},
 156         {"^[a-c]+", "x", "abc", "x"},
 157         {"[a-c]+$", "x", "abc", "x"},
 158         {"^[a-c]+$", "x", "abc", "x"},
 159         {"^[a-c]+", "x", "dabce", "dabce"},
 160         {"[a-c]+$", "x", "dabce", "dabce"},
 161         {"^[a-c]+$", "x", "dabce", "dabce"},
 162         {"^[a-c]+", "x", "", ""},
 163         {"[a-c]+$", "x", "", ""},
 164         {"^[a-c]+$", "x", "", ""},
 165
 166         // Other cases.
 167         {"abc", "def", "abcdefg", "defdefg"},
 168         {"bc", "BC", "abcbcdcdedef", "aBCBCdcdedef"},
 169         {"abc", "", "abcdabc", "d"},
 170         {"x", "xXx", "xxxXxxx", "xXxxXxxXxXxXxxXxxXx"},
 171         {"abc", "d", "", ""},
 172         {"abc", "d", "abc", "d"},
 173         {".+", "x", "abc", "x"},
 174         {"[a-c]*", "x", "def", "xdxexfx"},
 175         {"[a-c]+", "x", "abcbcdcdedef", "xdxdedef"},
 176         {"[a-c]*", "x", "abcbcdcdedef", "xdxdxexdxexfx"},
 177 }
 178
 179 type ReplaceFuncTest struct {
 180         pattern       string
 181         replacement   func(string) string
 182         input, output string
 183 }
 184
 185 var replaceFuncTests = []ReplaceFuncTest{
 186         {"[a-c]", func(s string) string { return "x" + s + "y" }, "defabcdef", "defxayxbyxcydef"},
 187         {"[a-c]+", func(s string) string { return "x" + s + "y" }, "defabcdef", "defxabcydef"},
 188         {"[a-c]*", func(s string) string { return "x" + s + "y" }, "defabcdef", "xydxyexyfxabcydxyexyfxy"},
 189 }
 190
 191 func TestReplaceAll(t *testing.T) {
 192         for _, tc := range replaceTests {
 193                 re, err := Compile(tc.pattern)
 194                 if err != nil {
 195                         t.Errorf("Unexpected error compiling %q: %v", tc.pattern, err)
 196                         continue
 197                 }
 198                 actual := re.ReplaceAllString(tc.input, tc.replacement)
 199                 if actual != tc.output {
 200                         t.Errorf("%q.Replace(%q,%q) = %q; want %q",
 201                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 202                 }
 203                 // now try bytes
 204                 actual = string(re.ReplaceAll([]byte(tc.input), []byte(tc.replacement)))
 205                 if actual != tc.output {
 206                         t.Errorf("%q.Replace(%q,%q) = %q; want %q",
 207                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 208                 }
 209         }
 210 }
 211
 212 func TestReplaceAllFunc(t *testing.T) {
 213         for _, tc := range replaceFuncTests {
 214                 re, err := Compile(tc.pattern)
 215                 if err != nil {
 216                         t.Errorf("Unexpected error compiling %q: %v", tc.pattern, err)
 217                         continue
 218                 }
 219                 actual := re.ReplaceAllStringFunc(tc.input, tc.replacement)
 220                 if actual != tc.output {
 221                         t.Errorf("%q.ReplaceFunc(%q,%q) = %q; want %q",
 222                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 223                 }
 224                 // now try bytes
 225                 actual = string(re.ReplaceAllFunc([]byte(tc.input), func(s []byte) []byte { return []byte(tc.replacement(string(s))) }))
 226                 if actual != tc.output {
 227                         t.Errorf("%q.ReplaceFunc(%q,%q) = %q; want %q",
 228                                 tc.pattern, tc.input, tc.replacement, actual, tc.output)
 229                 }
 230         }
 231 }
 232
 233 type MetaTest struct {
 234         pattern, output, literal string
 235         isLiteral                bool
 236 }
 237
 238 var metaTests = []MetaTest{
 239         {``, ``, ``, true},
 240         {`foo`, `foo`, `foo`, true},
 241         {`foo\.\$`, `foo\\\.\\\$`, `foo.$`, true}, // has meta but no operator
 242         {`foo.\$`, `foo\.\\\$`, `foo`, false},     // has escaped operators and real operators
 243         {`!@#$%^&*()_+-=[{]}\|,<.>/?~`, `!@#\$%\^&\*\(\)_\+-=\[{\]}\\\|,<\.>/\?~`, `!@#`, false},
 244 }
 245
 246 func TestQuoteMeta(t *testing.T) {
 247         for _, tc := range metaTests {
 248                 // Verify that QuoteMeta returns the expected string.
 249                 quoted := QuoteMeta(tc.pattern)
 250                 if quoted != tc.output {
 251                         t.Errorf("QuoteMeta(`%s`) = `%s`; want `%s`",
 252                                 tc.pattern, quoted, tc.output)
 253                         continue
 254                 }
 255
 256                 // Verify that the quoted string is in fact treated as expected
 257                 // by Compile -- i.e. that it matches the original, unquoted string.
 258                 if tc.pattern != "" {
 259                         re, err := Compile(quoted)
 260                         if err != nil {
 261                                 t.Errorf("Unexpected error compiling QuoteMeta(`%s`): %v", tc.pattern, err)
 262                                 continue
 263                         }
 264                         src := "abc" + tc.pattern + "def"
 265                         repl := "xyz"
 266                         replaced := re.ReplaceAllString(src, repl)
 267                         expected := "abcxyzdef"
 268                         if replaced != expected {
 269                                 t.Errorf("QuoteMeta(`%s`).Replace(`%s`,`%s`) = `%s`; want `%s`",
 270                                         tc.pattern, src, repl, replaced, expected)
 271                         }
 272                 }
 273         }
 274 }
 275
 276 func TestLiteralPrefix(t *testing.T) {
 277         for _, tc := range metaTests {
 278                 // Literal method needs to scan the pattern.
 279                 re := MustCompile(tc.pattern)
 280                 str, complete := re.LiteralPrefix()
 281                 if complete != tc.isLiteral {
 282                         t.Errorf("LiteralPrefix(`%s`) = %t; want %t", tc.pattern, complete, tc.isLiteral)
 283                 }
 284                 if str != tc.literal {
 285                         t.Errorf("LiteralPrefix(`%s`) = `%s`; want `%s`", tc.pattern, str, tc.literal)
 286                 }
 287         }
 288 }
 289
 290 type numSubexpCase struct {
 291         input    string
 292         expected int
 293 }
 294
 295 var numSubexpCases = []numSubexpCase{
 296         {``, 0},
 297         {`.*`, 0},
 298         {`abba`, 0},
 299         {`ab(b)a`, 1},
 300         {`ab(.*)a`, 1},
 301         {`(.*)ab(.*)a`, 2},
 302         {`(.*)(ab)(.*)a`, 3},
 303         {`(.*)((a)b)(.*)a`, 4},
 304         {`(.*)(\(ab)(.*)a`, 3},
 305         {`(.*)(\(a\)b)(.*)a`, 3},
 306 }
 307
 308 func TestNumSubexp(t *testing.T) {
 309         for _, c := range numSubexpCases {
 310                 re := MustCompile(c.input)
 311                 n := re.NumSubexp()
 312                 if n != c.expected {
 313                         t.Errorf("NumSubexp for %q returned %d, expected %d", c.input, n, c.expected)
 314                 }
 315         }
 316 }
 317
 318 func BenchmarkLiteral(b *testing.B) {
 319         x := strings.Repeat("x", 50) + "y"
 320         b.StopTimer()
 321         re := MustCompile("y")
 322         b.StartTimer()
 323         for i := 0; i < b.N; i++ {
 324                 if !re.MatchString(x) {
 325                         println("no match!")
 326                         break
 327                 }
 328         }
 329 }
 330
 331 func BenchmarkNotLiteral(b *testing.B) {
 332         x := strings.Repeat("x", 50) + "y"
 333         b.StopTimer()
 334         re := MustCompile(".y")
 335         b.StartTimer()
 336         for i := 0; i < b.N; i++ {
 337                 if !re.MatchString(x) {
 338                         println("no match!")
 339                         break
 340                 }
 341         }
 342 }
 343
 344 func BenchmarkMatchClass(b *testing.B) {
 345         b.StopTimer()
 346         x := strings.Repeat("xxxx", 20) + "w"
 347         re := MustCompile("[abcdw]")
 348         b.StartTimer()
 349         for i := 0; i < b.N; i++ {
 350                 if !re.MatchString(x) {
 351                         println("no match!")
 352                         break
 353                 }
 354         }
 355 }
 356
 357 func BenchmarkMatchClass_InRange(b *testing.B) {
 358         b.StopTimer()
 359         // 'b' is between 'a' and 'c', so the charclass
 360         // range checking is no help here.
 361         x := strings.Repeat("bbbb", 20) + "c"
 362         re := MustCompile("[ac]")
 363         b.StartTimer()
 364         for i := 0; i < b.N; i++ {
 365                 if !re.MatchString(x) {
 366                         println("no match!")
 367                         break
 368                 }
 369         }
 370 }
 371
 372 func BenchmarkReplaceAll(b *testing.B) {
 373         x := "abcdefghijklmnopqrstuvwxyz"
 374         b.StopTimer()
 375         re := MustCompile("[cjrw]")
 376         b.StartTimer()
 377         for i := 0; i < b.N; i++ {
 378                 re.ReplaceAllString(x, "")
 379         }
 380 }
 381
 382 func BenchmarkAnchoredLiteralShortNonMatch(b *testing.B) {
 383         b.StopTimer()
 384         x := []byte("abcdefghijklmnopqrstuvwxyz")
 385         re := MustCompile("^zbc(d|e)")
 386         b.StartTimer()
 387         for i := 0; i < b.N; i++ {
 388                 re.Match(x)
 389         }
 390 }
 391
 392 func BenchmarkAnchoredLiteralLongNonMatch(b *testing.B) {
 393         b.StopTimer()
 394         x := []byte("abcdefghijklmnopqrstuvwxyz")
 395         for i := 0; i < 15; i++ {
 396                 x = append(x, x...)
 397         }
 398         re := MustCompile("^zbc(d|e)")
 399         b.StartTimer()
 400         for i := 0; i < b.N; i++ {
 401                 re.Match(x)
 402         }
 403 }
 404
 405 func BenchmarkAnchoredShortMatch(b *testing.B) {
 406         b.StopTimer()
 407         x := []byte("abcdefghijklmnopqrstuvwxyz")
 408         re := MustCompile("^.bc(d|e)")
 409         b.StartTimer()
 410         for i := 0; i < b.N; i++ {
 411                 re.Match(x)
 412         }
 413 }
 414
 415 func BenchmarkAnchoredLongMatch(b *testing.B) {
 416         b.StopTimer()
 417         x := []byte("abcdefghijklmnopqrstuvwxyz")
 418         for i := 0; i < 15; i++ {
 419                 x = append(x, x...)
 420         }
 421         re := MustCompile("^.bc(d|e)")
 422         b.StartTimer()
 423         for i := 0; i < b.N; i++ {
 424                 re.Match(x)
 425         }
 426 }