libgo/go/regexp/find_test.go

   1 // Copyright 2010 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_test
   6
   7 import (
   8         . "regexp"
   9
  10         "fmt"
  11         "strings"
  12         "testing"
  13 )
  14
  15 // For each pattern/text pair, what is the expected output of each function?
  16 // We can derive the textual results from the indexed results, the non-submatch
  17 // results from the submatched results, the single results from the 'all' results,
  18 // and the byte results from the string results. Therefore the table includes
  19 // only the FindAllStringSubmatchIndex result.
  20 type FindTest struct {
  21         pat     string
  22         text    string
  23         matches [][]int
  24 }
  25
  26 func (t FindTest) String() string {
  27         return fmt.Sprintf("pat: %#q text: %#q", t.pat, t.text)
  28 }
  29
  30 var findTests = []FindTest{
  31         {``, ``, build(1, 0, 0)},
  32         {`^abcdefg`, "abcdefg", build(1, 0, 7)},
  33         {`a+`, "baaab", build(1, 1, 4)},
  34         {"abcd..", "abcdef", build(1, 0, 6)},
  35         {`a`, "a", build(1, 0, 1)},
  36         {`x`, "y", nil},
  37         {`b`, "abc", build(1, 1, 2)},
  38         {`.`, "a", build(1, 0, 1)},
  39         {`.*`, "abcdef", build(1, 0, 6)},
  40         {`^`, "abcde", build(1, 0, 0)},
  41         {`$`, "abcde", build(1, 5, 5)},
  42         {`^abcd$`, "abcd", build(1, 0, 4)},
  43         {`^bcd'`, "abcdef", nil},
  44         {`^abcd$`, "abcde", nil},
  45         {`a+`, "baaab", build(1, 1, 4)},
  46         {`a*`, "baaab", build(3, 0, 0, 1, 4, 5, 5)},
  47         {`[a-z]+`, "abcd", build(1, 0, 4)},
  48         {`[^a-z]+`, "ab1234cd", build(1, 2, 6)},
  49         {`[a\-\]z]+`, "az]-bcz", build(2, 0, 4, 6, 7)},
  50         {`[^\n]+`, "abcd\n", build(1, 0, 4)},
  51         {`[日本語]+`, "日本語日本語", build(1, 0, 18)},
  52         {`日本語+`, "日本語", build(1, 0, 9)},
  53         {`日本語+`, "日本語語語語", build(1, 0, 18)},
  54         {`()`, "", build(1, 0, 0, 0, 0)},
  55         {`(a)`, "a", build(1, 0, 1, 0, 1)},
  56         {`(.)(.)`, "日a", build(1, 0, 4, 0, 3, 3, 4)},
  57         {`(.*)`, "", build(1, 0, 0, 0, 0)},
  58         {`(.*)`, "abcd", build(1, 0, 4, 0, 4)},
  59         {`(..)(..)`, "abcd", build(1, 0, 4, 0, 2, 2, 4)},
  60         {`(([^xyz]*)(d))`, "abcd", build(1, 0, 4, 0, 4, 0, 3, 3, 4)},
  61         {`((a|b|c)*(d))`, "abcd", build(1, 0, 4, 0, 4, 2, 3, 3, 4)},
  62         {`(((a|b|c)*)(d))`, "abcd", build(1, 0, 4, 0, 4, 0, 3, 2, 3, 3, 4)},
  63         {`\a\f\n\r\t\v`, "\a\f\n\r\t\v", build(1, 0, 6)},
  64         {`[\a\f\n\r\t\v]+`, "\a\f\n\r\t\v", build(1, 0, 6)},
  65
  66         {`a*(|(b))c*`, "aacc", build(1, 0, 4, 2, 2, -1, -1)},
  67         {`(.*).*`, "ab", build(1, 0, 2, 0, 2)},
  68         {`[.]`, ".", build(1, 0, 1)},
  69         {`/$`, "/abc/", build(1, 4, 5)},
  70         {`/$`, "/abc", nil},
  71
  72         // multiple matches
  73         {`.`, "abc", build(3, 0, 1, 1, 2, 2, 3)},
  74         {`(.)`, "abc", build(3, 0, 1, 0, 1, 1, 2, 1, 2, 2, 3, 2, 3)},
  75         {`.(.)`, "abcd", build(2, 0, 2, 1, 2, 2, 4, 3, 4)},
  76         {`ab*`, "abbaab", build(3, 0, 3, 3, 4, 4, 6)},
  77         {`a(b*)`, "abbaab", build(3, 0, 3, 1, 3, 3, 4, 4, 4, 4, 6, 5, 6)},
  78
  79         // fixed bugs
  80         {`ab$`, "cab", build(1, 1, 3)},
  81         {`axxb$`, "axxcb", nil},
  82         {`data`, "daXY data", build(1, 5, 9)},
  83         {`da(.)a$`, "daXY data", build(1, 5, 9, 7, 8)},
  84         {`zx+`, "zzx", build(1, 1, 3)},
  85         {`ab$`, "abcab", build(1, 3, 5)},
  86         {`(aa)*$`, "a", build(1, 1, 1, -1, -1)},
  87         {`(?:.|(?:.a))`, "", nil},
  88         {`(?:A(?:A|a))`, "Aa", build(1, 0, 2)},
  89         {`(?:A|(?:A|a))`, "a", build(1, 0, 1)},
  90         {`(a){0}`, "", build(1, 0, 0, -1, -1)},
  91         {`(?-s)(?:(?:^).)`, "\n", nil},
  92         {`(?s)(?:(?:^).)`, "\n", build(1, 0, 1)},
  93         {`(?:(?:^).)`, "\n", nil},
  94         {`\b`, "x", build(2, 0, 0, 1, 1)},
  95         {`\b`, "xx", build(2, 0, 0, 2, 2)},
  96         {`\b`, "x y", build(4, 0, 0, 1, 1, 2, 2, 3, 3)},
  97         {`\b`, "xx yy", build(4, 0, 0, 2, 2, 3, 3, 5, 5)},
  98         {`\B`, "x", nil},
  99         {`\B`, "xx", build(1, 1, 1)},
 100         {`\B`, "x y", nil},
 101         {`\B`, "xx yy", build(2, 1, 1, 4, 4)},
 102
 103         // RE2 tests
 104         {`[^\S\s]`, "abcd", nil},
 105         {`[^\S[:space:]]`, "abcd", nil},
 106         {`[^\D\d]`, "abcd", nil},
 107         {`[^\D[:digit:]]`, "abcd", nil},
 108         {`(?i)\W`, "x", nil},
 109         {`(?i)\W`, "k", nil},
 110         {`(?i)\W`, "s", nil},
 111
 112         // can backslash-escape any punctuation
 113         {`\!\"\#\$\%\&\'\(\)\*\+\,\-\.\/\:\;\<\=\>\?\@\[\\\]\^\_\{\|\}\~`,
 114                 `!"#$%&'()*+,-./:;<=>?@[\]^_{|}~`, build(1, 0, 31)},
 115         {`[\!\"\#\$\%\&\'\(\)\*\+\,\-\.\/\:\;\<\=\>\?\@\[\\\]\^\_\{\|\}\~]+`,
 116                 `!"#$%&'()*+,-./:;<=>?@[\]^_{|}~`, build(1, 0, 31)},
 117         {"\\`", "`", build(1, 0, 1)},
 118         {"[\\`]+", "`", build(1, 0, 1)},
 119
 120         // long set of matches (longer than startSize)
 121         {
 122                 ".",
 123                 "qwertyuiopasdfghjklzxcvbnm1234567890",
 124                 build(36, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
 125                         10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20,
 126                         20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30,
 127                         30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36),
 128         },
 129 }
 130
 131 // build is a helper to construct a [][]int by extracting n sequences from x.
 132 // This represents n matches with len(x)/n submatches each.
 133 func build(n int, x ...int) [][]int {
 134         ret := make([][]int, n)
 135         runLength := len(x) / n
 136         j := 0
 137         for i := range ret {
 138                 ret[i] = make([]int, runLength)
 139                 copy(ret[i], x[j:])
 140                 j += runLength
 141                 if j > len(x) {
 142                         panic("invalid build entry")
 143                 }
 144         }
 145         return ret
 146 }
 147
 148 // First the simple cases.
 149
 150 func TestFind(t *testing.T) {
 151         for _, test := range findTests {
 152                 re := MustCompile(test.pat)
 153                 if re.String() != test.pat {
 154                         t.Errorf("String() = `%s`; should be `%s`", re.String(), test.pat)
 155                 }
 156                 result := re.Find([]byte(test.text))
 157                 switch {
 158                 case len(test.matches) == 0 && len(result) == 0:
 159                         // ok
 160                 case test.matches == nil && result != nil:
 161                         t.Errorf("expected no match; got one: %s", test)
 162                 case test.matches != nil && result == nil:
 163                         t.Errorf("expected match; got none: %s", test)
 164                 case test.matches != nil && result != nil:
 165                         expect := test.text[test.matches[0][0]:test.matches[0][1]]
 166                         if expect != string(result) {
 167                                 t.Errorf("expected %q got %q: %s", expect, result, test)
 168                         }
 169                 }
 170         }
 171 }
 172
 173 func TestFindString(t *testing.T) {
 174         for _, test := range findTests {
 175                 result := MustCompile(test.pat).FindString(test.text)
 176                 switch {
 177                 case len(test.matches) == 0 && len(result) == 0:
 178                         // ok
 179                 case test.matches == nil && result != "":
 180                         t.Errorf("expected no match; got one: %s", test)
 181                 case test.matches != nil && result == "":
 182                         // Tricky because an empty result has two meanings: no match or empty match.
 183                         if test.matches[0][0] != test.matches[0][1] {
 184                                 t.Errorf("expected match; got none: %s", test)
 185                         }
 186                 case test.matches != nil && result != "":
 187                         expect := test.text[test.matches[0][0]:test.matches[0][1]]
 188                         if expect != result {
 189                                 t.Errorf("expected %q got %q: %s", expect, result, test)
 190                         }
 191                 }
 192         }
 193 }
 194
 195 func testFindIndex(test *FindTest, result []int, t *testing.T) {
 196         switch {
 197         case len(test.matches) == 0 && len(result) == 0:
 198                 // ok
 199         case test.matches == nil && result != nil:
 200                 t.Errorf("expected no match; got one: %s", test)
 201         case test.matches != nil && result == nil:
 202                 t.Errorf("expected match; got none: %s", test)
 203         case test.matches != nil && result != nil:
 204                 expect := test.matches[0]
 205                 if expect[0] != result[0] || expect[1] != result[1] {
 206                         t.Errorf("expected %v got %v: %s", expect, result, test)
 207                 }
 208         }
 209 }
 210
 211 func TestFindIndex(t *testing.T) {
 212         for _, test := range findTests {
 213                 testFindIndex(&test, MustCompile(test.pat).FindIndex([]byte(test.text)), t)
 214         }
 215 }
 216
 217 func TestFindStringIndex(t *testing.T) {
 218         for _, test := range findTests {
 219                 testFindIndex(&test, MustCompile(test.pat).FindStringIndex(test.text), t)
 220         }
 221 }
 222
 223 func TestFindReaderIndex(t *testing.T) {
 224         for _, test := range findTests {
 225                 testFindIndex(&test, MustCompile(test.pat).FindReaderIndex(strings.NewReader(test.text)), t)
 226         }
 227 }
 228
 229 // Now come the simple All cases.
 230
 231 func TestFindAll(t *testing.T) {
 232         for _, test := range findTests {
 233                 result := MustCompile(test.pat).FindAll([]byte(test.text), -1)
 234                 switch {
 235                 case test.matches == nil && result == nil:
 236                         // ok
 237                 case test.matches == nil && result != nil:
 238                         t.Errorf("expected no match; got one: %s", test)
 239                 case test.matches != nil && result == nil:
 240                         t.Fatalf("expected match; got none: %s", test)
 241                 case test.matches != nil && result != nil:
 242                         if len(test.matches) != len(result) {
 243                                 t.Errorf("expected %d matches; got %d: %s", len(test.matches), len(result), test)
 244                                 continue
 245                         }
 246                         for k, e := range test.matches {
 247                                 expect := test.text[e[0]:e[1]]
 248                                 if expect != string(result[k]) {
 249                                         t.Errorf("match %d: expected %q got %q: %s", k, expect, result[k], test)
 250                                 }
 251                         }
 252                 }
 253         }
 254 }
 255
 256 func TestFindAllString(t *testing.T) {
 257         for _, test := range findTests {
 258                 result := MustCompile(test.pat).FindAllString(test.text, -1)
 259                 switch {
 260                 case test.matches == nil && result == nil:
 261                         // ok
 262                 case test.matches == nil && result != nil:
 263                         t.Errorf("expected no match; got one: %s", test)
 264                 case test.matches != nil && result == nil:
 265                         t.Errorf("expected match; got none: %s", test)
 266                 case test.matches != nil && result != nil:
 267                         if len(test.matches) != len(result) {
 268                                 t.Errorf("expected %d matches; got %d: %s", len(test.matches), len(result), test)
 269                                 continue
 270                         }
 271                         for k, e := range test.matches {
 272                                 expect := test.text[e[0]:e[1]]
 273                                 if expect != result[k] {
 274                                         t.Errorf("expected %q got %q: %s", expect, result, test)
 275                                 }
 276                         }
 277                 }
 278         }
 279 }
 280
 281 func testFindAllIndex(test *FindTest, result [][]int, t *testing.T) {
 282         switch {
 283         case test.matches == nil && result == nil:
 284                 // ok
 285         case test.matches == nil && result != nil:
 286                 t.Errorf("expected no match; got one: %s", test)
 287         case test.matches != nil && result == nil:
 288                 t.Errorf("expected match; got none: %s", test)
 289         case test.matches != nil && result != nil:
 290                 if len(test.matches) != len(result) {
 291                         t.Errorf("expected %d matches; got %d: %s", len(test.matches), len(result), test)
 292                         return
 293                 }
 294                 for k, e := range test.matches {
 295                         if e[0] != result[k][0] || e[1] != result[k][1] {
 296                                 t.Errorf("match %d: expected %v got %v: %s", k, e, result[k], test)
 297                         }
 298                 }
 299         }
 300 }
 301
 302 func TestFindAllIndex(t *testing.T) {
 303         for _, test := range findTests {
 304                 testFindAllIndex(&test, MustCompile(test.pat).FindAllIndex([]byte(test.text), -1), t)
 305         }
 306 }
 307
 308 func TestFindAllStringIndex(t *testing.T) {
 309         for _, test := range findTests {
 310                 testFindAllIndex(&test, MustCompile(test.pat).FindAllStringIndex(test.text, -1), t)
 311         }
 312 }
 313
 314 // Now come the Submatch cases.
 315
 316 func testSubmatchBytes(test *FindTest, n int, submatches []int, result [][]byte, t *testing.T) {
 317         if len(submatches) != len(result)*2 {
 318                 t.Errorf("match %d: expected %d submatches; got %d: %s", n, len(submatches)/2, len(result), test)
 319                 return
 320         }
 321         for k := 0; k < len(submatches); k += 2 {
 322                 if submatches[k] == -1 {
 323                         if result[k/2] != nil {
 324                                 t.Errorf("match %d: expected nil got %q: %s", n, result, test)
 325                         }
 326                         continue
 327                 }
 328                 expect := test.text[submatches[k]:submatches[k+1]]
 329                 if expect != string(result[k/2]) {
 330                         t.Errorf("match %d: expected %q got %q: %s", n, expect, result, test)
 331                         return
 332                 }
 333         }
 334 }
 335
 336 func TestFindSubmatch(t *testing.T) {
 337         for _, test := range findTests {
 338                 result := MustCompile(test.pat).FindSubmatch([]byte(test.text))
 339                 switch {
 340                 case test.matches == nil && result == nil:
 341                         // ok
 342                 case test.matches == nil && result != nil:
 343                         t.Errorf("expected no match; got one: %s", test)
 344                 case test.matches != nil && result == nil:
 345                         t.Errorf("expected match; got none: %s", test)
 346                 case test.matches != nil && result != nil:
 347                         testSubmatchBytes(&test, 0, test.matches[0], result, t)
 348                 }
 349         }
 350 }
 351
 352 func testSubmatchString(test *FindTest, n int, submatches []int, result []string, t *testing.T) {
 353         if len(submatches) != len(result)*2 {
 354                 t.Errorf("match %d: expected %d submatches; got %d: %s", n, len(submatches)/2, len(result), test)
 355                 return
 356         }
 357         for k := 0; k < len(submatches); k += 2 {
 358                 if submatches[k] == -1 {
 359                         if result[k/2] != "" {
 360                                 t.Errorf("match %d: expected nil got %q: %s", n, result, test)
 361                         }
 362                         continue
 363                 }
 364                 expect := test.text[submatches[k]:submatches[k+1]]
 365                 if expect != result[k/2] {
 366                         t.Errorf("match %d: expected %q got %q: %s", n, expect, result, test)
 367                         return
 368                 }
 369         }
 370 }
 371
 372 func TestFindStringSubmatch(t *testing.T) {
 373         for _, test := range findTests {
 374                 result := MustCompile(test.pat).FindStringSubmatch(test.text)
 375                 switch {
 376                 case test.matches == nil && result == nil:
 377                         // ok
 378                 case test.matches == nil && result != nil:
 379                         t.Errorf("expected no match; got one: %s", test)
 380                 case test.matches != nil && result == nil:
 381                         t.Errorf("expected match; got none: %s", test)
 382                 case test.matches != nil && result != nil:
 383                         testSubmatchString(&test, 0, test.matches[0], result, t)
 384                 }
 385         }
 386 }
 387
 388 func testSubmatchIndices(test *FindTest, n int, expect, result []int, t *testing.T) {
 389         if len(expect) != len(result) {
 390                 t.Errorf("match %d: expected %d matches; got %d: %s", n, len(expect)/2, len(result)/2, test)
 391                 return
 392         }
 393         for k, e := range expect {
 394                 if e != result[k] {
 395                         t.Errorf("match %d: submatch error: expected %v got %v: %s", n, expect, result, test)
 396                 }
 397         }
 398 }
 399
 400 func testFindSubmatchIndex(test *FindTest, result []int, t *testing.T) {
 401         switch {
 402         case test.matches == nil && result == nil:
 403                 // ok
 404         case test.matches == nil && result != nil:
 405                 t.Errorf("expected no match; got one: %s", test)
 406         case test.matches != nil && result == nil:
 407                 t.Errorf("expected match; got none: %s", test)
 408         case test.matches != nil && result != nil:
 409                 testSubmatchIndices(test, 0, test.matches[0], result, t)
 410         }
 411 }
 412
 413 func TestFindSubmatchIndex(t *testing.T) {
 414         for _, test := range findTests {
 415                 testFindSubmatchIndex(&test, MustCompile(test.pat).FindSubmatchIndex([]byte(test.text)), t)
 416         }
 417 }
 418
 419 func TestFindStringSubmatchIndex(t *testing.T) {
 420         for _, test := range findTests {
 421                 testFindSubmatchIndex(&test, MustCompile(test.pat).FindStringSubmatchIndex(test.text), t)
 422         }
 423 }
 424
 425 func TestFindReaderSubmatchIndex(t *testing.T) {
 426         for _, test := range findTests {
 427                 testFindSubmatchIndex(&test, MustCompile(test.pat).FindReaderSubmatchIndex(strings.NewReader(test.text)), t)
 428         }
 429 }
 430
 431 // Now come the monster AllSubmatch cases.
 432
 433 func TestFindAllSubmatch(t *testing.T) {
 434         for _, test := range findTests {
 435                 result := MustCompile(test.pat).FindAllSubmatch([]byte(test.text), -1)
 436                 switch {
 437                 case test.matches == nil && result == nil:
 438                         // ok
 439                 case test.matches == nil && result != nil:
 440                         t.Errorf("expected no match; got one: %s", test)
 441                 case test.matches != nil && result == nil:
 442                         t.Errorf("expected match; got none: %s", test)
 443                 case len(test.matches) != len(result):
 444                         t.Errorf("expected %d matches; got %d: %s", len(test.matches), len(result), test)
 445                 case test.matches != nil && result != nil:
 446                         for k, match := range test.matches {
 447                                 testSubmatchBytes(&test, k, match, result[k], t)
 448                         }
 449                 }
 450         }
 451 }
 452
 453 func TestFindAllStringSubmatch(t *testing.T) {
 454         for _, test := range findTests {
 455                 result := MustCompile(test.pat).FindAllStringSubmatch(test.text, -1)
 456                 switch {
 457                 case test.matches == nil && result == nil:
 458                         // ok
 459                 case test.matches == nil && result != nil:
 460                         t.Errorf("expected no match; got one: %s", test)
 461                 case test.matches != nil && result == nil:
 462                         t.Errorf("expected match; got none: %s", test)
 463                 case len(test.matches) != len(result):
 464                         t.Errorf("expected %d matches; got %d: %s", len(test.matches), len(result), test)
 465                 case test.matches != nil && result != nil:
 466                         for k, match := range test.matches {
 467                                 testSubmatchString(&test, k, match, result[k], t)
 468                         }
 469                 }
 470         }
 471 }
 472
 473 func testFindAllSubmatchIndex(test *FindTest, result [][]int, t *testing.T) {
 474         switch {
 475         case test.matches == nil && result == nil:
 476                 // ok
 477         case test.matches == nil && result != nil:
 478                 t.Errorf("expected no match; got one: %s", test)
 479         case test.matches != nil && result == nil:
 480                 t.Errorf("expected match; got none: %s", test)
 481         case len(test.matches) != len(result):
 482                 t.Errorf("expected %d matches; got %d: %s", len(test.matches), len(result), test)
 483         case test.matches != nil && result != nil:
 484                 for k, match := range test.matches {
 485                         testSubmatchIndices(test, k, match, result[k], t)
 486                 }
 487         }
 488 }
 489
 490 func TestFindAllSubmatchIndex(t *testing.T) {
 491         for _, test := range findTests {
 492                 testFindAllSubmatchIndex(&test, MustCompile(test.pat).FindAllSubmatchIndex([]byte(test.text), -1), t)
 493         }
 494 }
 495
 496 func TestFindAllStringSubmatchIndex(t *testing.T) {
 497         for _, test := range findTests {
 498                 testFindAllSubmatchIndex(&test, MustCompile(test.pat).FindAllStringSubmatchIndex(test.text, -1), t)
 499         }
 500 }