Source file src/regexp/exec_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
     6  
     7  import (
     8  	"bufio"
     9  	"compress/bzip2"
    10  	"fmt"
    11  	"internal/testenv"
    12  	"io"
    13  	"os"
    14  	"path/filepath"
    15  	"regexp/syntax"
    16  	"slices"
    17  	"strconv"
    18  	"strings"
    19  	"testing"
    20  	"unicode/utf8"
    21  )
    22  
    23  // TestRE2 tests this package's regexp API against test cases
    24  // considered during RE2's exhaustive tests, which run all possible
    25  // regexps over a given set of atoms and operators, up to a given
    26  // complexity, over all possible strings over a given alphabet,
    27  // up to a given size. Rather than try to link with RE2, we read a
    28  // log file containing the test cases and the expected matches.
    29  // The log file, re2-exhaustive.txt, is generated by running 'make log'
    30  // in the open source RE2 distribution https://github.com/google/re2/.
    31  //
    32  // The test file format is a sequence of stanzas like:
    33  //
    34  //	strings
    35  //	"abc"
    36  //	"123x"
    37  //	regexps
    38  //	"[a-z]+"
    39  //	0-3;0-3
    40  //	-;-
    41  //	"([0-9])([0-9])([0-9])"
    42  //	-;-
    43  //	-;0-3 0-1 1-2 2-3
    44  //
    45  // The stanza begins by defining a set of strings, quoted
    46  // using Go double-quote syntax, one per line. Then the
    47  // regexps section gives a sequence of regexps to run on
    48  // the strings. In the block that follows a regexp, each line
    49  // gives the semicolon-separated match results of running
    50  // the regexp on the corresponding string.
    51  // Each match result is either a single -, meaning no match, or a
    52  // space-separated sequence of pairs giving the match and
    53  // submatch indices. An unmatched subexpression formats
    54  // its pair as a single - (not illustrated above).  For now
    55  // each regexp run produces two match results, one for a
    56  // “full match” that restricts the regexp to matching the entire
    57  // string or nothing, and one for a “partial match” that gives
    58  // the leftmost first match found in the string.
    59  //
    60  // Lines beginning with # are comments. Lines beginning with
    61  // a capital letter are test names printed during RE2's test suite
    62  // and are echoed into t but otherwise ignored.
    63  //
    64  // At time of writing, re2-exhaustive.txt is 59 MB but compresses to 385 kB,
    65  // so we store re2-exhaustive.txt.bz2 in the repository and decompress it on the fly.
    66  func TestRE2Search(t *testing.T) {
    67  	testRE2(t, "testdata/re2-search.txt")
    68  }
    69  
    70  func testRE2(t *testing.T, file string) {
    71  	f, err := os.Open(file)
    72  	if err != nil {
    73  		t.Fatal(err)
    74  	}
    75  	defer f.Close()
    76  	var txt io.Reader
    77  	if strings.HasSuffix(file, ".bz2") {
    78  		z := bzip2.NewReader(f)
    79  		txt = z
    80  		file = file[:len(file)-len(".bz2")] // for error messages
    81  	} else {
    82  		txt = f
    83  	}
    84  	lineno := 0
    85  	scanner := bufio.NewScanner(txt)
    86  	var (
    87  		str       []string
    88  		input     []string
    89  		inStrings bool
    90  		re        *Regexp
    91  		refull    *Regexp
    92  		nfail     int
    93  		ncase     int
    94  	)
    95  	for lineno := 1; scanner.Scan(); lineno++ {
    96  		line := scanner.Text()
    97  		switch {
    98  		case line == "":
    99  			t.Fatalf("%s:%d: unexpected blank line", file, lineno)
   100  		case line[0] == '#':
   101  			continue
   102  		case 'A' <= line[0] && line[0] <= 'Z':
   103  			// Test name.
   104  			t.Logf("%s\n", line)
   105  			continue
   106  		case line == "strings":
   107  			str = str[:0]
   108  			inStrings = true
   109  		case line == "regexps":
   110  			inStrings = false
   111  		case line[0] == '"':
   112  			q, err := strconv.Unquote(line)
   113  			if err != nil {
   114  				// Fatal because we'll get out of sync.
   115  				t.Fatalf("%s:%d: unquote %s: %v", file, lineno, line, err)
   116  			}
   117  			if inStrings {
   118  				str = append(str, q)
   119  				continue
   120  			}
   121  			// Is a regexp.
   122  			if len(input) != 0 {
   123  				t.Fatalf("%s:%d: out of sync: have %d strings left before %#q", file, lineno, len(input), q)
   124  			}
   125  			re, err = tryCompile(q)
   126  			if err != nil {
   127  				if err.Error() == "error parsing regexp: invalid escape sequence: `\\C`" {
   128  					// We don't and likely never will support \C; keep going.
   129  					continue
   130  				}
   131  				t.Errorf("%s:%d: compile %#q: %v", file, lineno, q, err)
   132  				if nfail++; nfail >= 100 {
   133  					t.Fatalf("stopping after %d errors", nfail)
   134  				}
   135  				continue
   136  			}
   137  			full := `\A(?:` + q + `)\z`
   138  			refull, err = tryCompile(full)
   139  			if err != nil {
   140  				// Fatal because q worked, so this should always work.
   141  				t.Fatalf("%s:%d: compile full %#q: %v", file, lineno, full, err)
   142  			}
   143  			input = str
   144  		case line[0] == '-' || '0' <= line[0] && line[0] <= '9':
   145  			// A sequence of match results.
   146  			ncase++
   147  			if re == nil {
   148  				// Failed to compile: skip results.
   149  				continue
   150  			}
   151  			if len(input) == 0 {
   152  				t.Fatalf("%s:%d: out of sync: no input remaining", file, lineno)
   153  			}
   154  			var text string
   155  			text, input = input[0], input[1:]
   156  			if !isSingleBytes(text) && strings.Contains(re.String(), `\B`) {
   157  				// RE2's \B considers every byte position,
   158  				// so it sees 'not word boundary' in the
   159  				// middle of UTF-8 sequences. This package
   160  				// only considers the positions between runes,
   161  				// so it disagrees. Skip those cases.
   162  				continue
   163  			}
   164  			res := strings.Split(line, ";")
   165  			if len(res) != len(run) {
   166  				t.Fatalf("%s:%d: have %d test results, want %d", file, lineno, len(res), len(run))
   167  			}
   168  			for i := range res {
   169  				have, suffix := run[i](re, refull, text)
   170  				want := parseResult(t, file, lineno, res[i])
   171  				if !slices.Equal(have, want) {
   172  					t.Errorf("%s:%d: %#q%s.FindSubmatchIndex(%#q) = %v, want %v", file, lineno, re, suffix, text, have, want)
   173  					if nfail++; nfail >= 100 {
   174  						t.Fatalf("stopping after %d errors", nfail)
   175  					}
   176  					continue
   177  				}
   178  				b, suffix := match[i](re, refull, text)
   179  				if b != (want != nil) {
   180  					t.Errorf("%s:%d: %#q%s.MatchString(%#q) = %v, want %v", file, lineno, re, suffix, text, b, !b)
   181  					if nfail++; nfail >= 100 {
   182  						t.Fatalf("stopping after %d errors", nfail)
   183  					}
   184  					continue
   185  				}
   186  			}
   187  
   188  		default:
   189  			t.Fatalf("%s:%d: out of sync: %s\n", file, lineno, line)
   190  		}
   191  	}
   192  	if err := scanner.Err(); err != nil {
   193  		t.Fatalf("%s:%d: %v", file, lineno, err)
   194  	}
   195  	if len(input) != 0 {
   196  		t.Fatalf("%s:%d: out of sync: have %d strings left at EOF", file, lineno, len(input))
   197  	}
   198  	t.Logf("%d cases tested", ncase)
   199  }
   200  
   201  var run = []func(*Regexp, *Regexp, string) ([]int, string){
   202  	runFull,
   203  	runPartial,
   204  	runFullLongest,
   205  	runPartialLongest,
   206  }
   207  
   208  func runFull(re, refull *Regexp, text string) ([]int, string) {
   209  	refull.longest = false
   210  	return refull.FindStringSubmatchIndex(text), "[full]"
   211  }
   212  
   213  func runPartial(re, refull *Regexp, text string) ([]int, string) {
   214  	re.longest = false
   215  	return re.FindStringSubmatchIndex(text), ""
   216  }
   217  
   218  func runFullLongest(re, refull *Regexp, text string) ([]int, string) {
   219  	refull.longest = true
   220  	return refull.FindStringSubmatchIndex(text), "[full,longest]"
   221  }
   222  
   223  func runPartialLongest(re, refull *Regexp, text string) ([]int, string) {
   224  	re.longest = true
   225  	return re.FindStringSubmatchIndex(text), "[longest]"
   226  }
   227  
   228  var match = []func(*Regexp, *Regexp, string) (bool, string){
   229  	matchFull,
   230  	matchPartial,
   231  	matchFullLongest,
   232  	matchPartialLongest,
   233  }
   234  
   235  func matchFull(re, refull *Regexp, text string) (bool, string) {
   236  	refull.longest = false
   237  	return refull.MatchString(text), "[full]"
   238  }
   239  
   240  func matchPartial(re, refull *Regexp, text string) (bool, string) {
   241  	re.longest = false
   242  	return re.MatchString(text), ""
   243  }
   244  
   245  func matchFullLongest(re, refull *Regexp, text string) (bool, string) {
   246  	refull.longest = true
   247  	return refull.MatchString(text), "[full,longest]"
   248  }
   249  
   250  func matchPartialLongest(re, refull *Regexp, text string) (bool, string) {
   251  	re.longest = true
   252  	return re.MatchString(text), "[longest]"
   253  }
   254  
   255  func isSingleBytes(s string) bool {
   256  	for _, c := range s {
   257  		if c >= utf8.RuneSelf {
   258  			return false
   259  		}
   260  	}
   261  	return true
   262  }
   263  
   264  func tryCompile(s string) (re *Regexp, err error) {
   265  	// Protect against panic during Compile.
   266  	defer func() {
   267  		if r := recover(); r != nil {
   268  			err = fmt.Errorf("panic: %v", r)
   269  		}
   270  	}()
   271  	return Compile(s)
   272  }
   273  
   274  func parseResult(t *testing.T, file string, lineno int, res string) []int {
   275  	// A single - indicates no match.
   276  	if res == "-" {
   277  		return nil
   278  	}
   279  	// Otherwise, a space-separated list of pairs.
   280  	n := 1
   281  	for j := 0; j < len(res); j++ {
   282  		if res[j] == ' ' {
   283  			n++
   284  		}
   285  	}
   286  	out := make([]int, 2*n)
   287  	i := 0
   288  	n = 0
   289  	for j := 0; j <= len(res); j++ {
   290  		if j == len(res) || res[j] == ' ' {
   291  			// Process a single pair.  - means no submatch.
   292  			pair := res[i:j]
   293  			if pair == "-" {
   294  				out[n] = -1
   295  				out[n+1] = -1
   296  			} else {
   297  				loStr, hiStr, _ := strings.Cut(pair, "-")
   298  				lo, err1 := strconv.Atoi(loStr)
   299  				hi, err2 := strconv.Atoi(hiStr)
   300  				if err1 != nil || err2 != nil || lo > hi {
   301  					t.Fatalf("%s:%d: invalid pair %s", file, lineno, pair)
   302  				}
   303  				out[n] = lo
   304  				out[n+1] = hi
   305  			}
   306  			n += 2
   307  			i = j + 1
   308  		}
   309  	}
   310  	return out
   311  }
   312  
   313  // TestFowler runs this package's regexp API against the
   314  // POSIX regular expression tests collected by Glenn Fowler
   315  // at http://www2.research.att.com/~astopen/testregex/testregex.html.
   316  func TestFowler(t *testing.T) {
   317  	files, err := filepath.Glob("testdata/*.dat")
   318  	if err != nil {
   319  		t.Fatal(err)
   320  	}
   321  	for _, file := range files {
   322  		t.Log(file)
   323  		testFowler(t, file)
   324  	}
   325  }
   326  
   327  var notab = MustCompilePOSIX(`[^\t]+`)
   328  
   329  func testFowler(t *testing.T, file string) {
   330  	f, err := os.Open(file)
   331  	if err != nil {
   332  		t.Error(err)
   333  		return
   334  	}
   335  	defer f.Close()
   336  	b := bufio.NewReader(f)
   337  	lineno := 0
   338  	lastRegexp := ""
   339  Reading:
   340  	for {
   341  		lineno++
   342  		line, err := b.ReadString('\n')
   343  		if err != nil {
   344  			if err != io.EOF {
   345  				t.Errorf("%s:%d: %v", file, lineno, err)
   346  			}
   347  			break Reading
   348  		}
   349  
   350  		// http://www2.research.att.com/~astopen/man/man1/testregex.html
   351  		//
   352  		// INPUT FORMAT
   353  		//   Input lines may be blank, a comment beginning with #, or a test
   354  		//   specification. A specification is five fields separated by one
   355  		//   or more tabs. NULL denotes the empty string and NIL denotes the
   356  		//   0 pointer.
   357  		if line[0] == '#' || line[0] == '\n' {
   358  			continue Reading
   359  		}
   360  		line = line[:len(line)-1]
   361  		field := notab.FindAllString(line, -1)
   362  		for i, f := range field {
   363  			if f == "NULL" {
   364  				field[i] = ""
   365  			}
   366  			if f == "NIL" {
   367  				t.Logf("%s:%d: skip: %s", file, lineno, line)
   368  				continue Reading
   369  			}
   370  		}
   371  		if len(field) == 0 {
   372  			continue Reading
   373  		}
   374  
   375  		//   Field 1: the regex(3) flags to apply, one character per REG_feature
   376  		//   flag. The test is skipped if REG_feature is not supported by the
   377  		//   implementation. If the first character is not [BEASKLP] then the
   378  		//   specification is a global control line. One or more of [BEASKLP] may be
   379  		//   specified; the test will be repeated for each mode.
   380  		//
   381  		//     B 	basic			BRE	(grep, ed, sed)
   382  		//     E 	REG_EXTENDED		ERE	(egrep)
   383  		//     A	REG_AUGMENTED		ARE	(egrep with negation)
   384  		//     S	REG_SHELL		SRE	(sh glob)
   385  		//     K	REG_SHELL|REG_AUGMENTED	KRE	(ksh glob)
   386  		//     L	REG_LITERAL		LRE	(fgrep)
   387  		//
   388  		//     a	REG_LEFT|REG_RIGHT	implicit ^...$
   389  		//     b	REG_NOTBOL		lhs does not match ^
   390  		//     c	REG_COMMENT		ignore space and #...\n
   391  		//     d	REG_SHELL_DOT		explicit leading . match
   392  		//     e	REG_NOTEOL		rhs does not match $
   393  		//     f	REG_MULTIPLE		multiple \n separated patterns
   394  		//     g	FNM_LEADING_DIR		testfnmatch only -- match until /
   395  		//     h	REG_MULTIREF		multiple digit backref
   396  		//     i	REG_ICASE		ignore case
   397  		//     j	REG_SPAN		. matches \n
   398  		//     k	REG_ESCAPE		\ to escape [...] delimiter
   399  		//     l	REG_LEFT		implicit ^...
   400  		//     m	REG_MINIMAL		minimal match
   401  		//     n	REG_NEWLINE		explicit \n match
   402  		//     o	REG_ENCLOSED		(|&) magic inside [@|&](...)
   403  		//     p	REG_SHELL_PATH		explicit / match
   404  		//     q	REG_DELIMITED		delimited pattern
   405  		//     r	REG_RIGHT		implicit ...$
   406  		//     s	REG_SHELL_ESCAPED	\ not special
   407  		//     t	REG_MUSTDELIM		all delimiters must be specified
   408  		//     u	standard unspecified behavior -- errors not counted
   409  		//     v	REG_CLASS_ESCAPE	\ special inside [...]
   410  		//     w	REG_NOSUB		no subexpression match array
   411  		//     x	REG_LENIENT		let some errors slide
   412  		//     y	REG_LEFT		regexec() implicit ^...
   413  		//     z	REG_NULL		NULL subexpressions ok
   414  		//     $	                        expand C \c escapes in fields 2 and 3
   415  		//     /	                        field 2 is a regsubcomp() expression
   416  		//     =	                        field 3 is a regdecomp() expression
   417  		//
   418  		//   Field 1 control lines:
   419  		//
   420  		//     C		set LC_COLLATE and LC_CTYPE to locale in field 2
   421  		//
   422  		//     ?test ...	output field 5 if passed and != EXPECTED, silent otherwise
   423  		//     &test ...	output field 5 if current and previous passed
   424  		//     |test ...	output field 5 if current passed and previous failed
   425  		//     ; ...	output field 2 if previous failed
   426  		//     {test ...	skip if failed until }
   427  		//     }		end of skip
   428  		//
   429  		//     : comment		comment copied as output NOTE
   430  		//     :comment:test	:comment: ignored
   431  		//     N[OTE] comment	comment copied as output NOTE
   432  		//     T[EST] comment	comment
   433  		//
   434  		//     number		use number for nmatch (20 by default)
   435  		flag := field[0]
   436  		switch flag[0] {
   437  		case '?', '&', '|', ';', '{', '}':
   438  			// Ignore all the control operators.
   439  			// Just run everything.
   440  			flag = flag[1:]
   441  			if flag == "" {
   442  				continue Reading
   443  			}
   444  		case ':':
   445  			var ok bool
   446  			if _, flag, ok = strings.Cut(flag[1:], ":"); !ok {
   447  				t.Logf("skip: %s", line)
   448  				continue Reading
   449  			}
   450  		case 'C', 'N', 'T', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
   451  			t.Logf("skip: %s", line)
   452  			continue Reading
   453  		}
   454  
   455  		// Can check field count now that we've handled the myriad comment formats.
   456  		if len(field) < 4 {
   457  			t.Errorf("%s:%d: too few fields: %s", file, lineno, line)
   458  			continue Reading
   459  		}
   460  
   461  		// Expand C escapes (a.k.a. Go escapes).
   462  		if strings.Contains(flag, "$") {
   463  			f := `"` + field[1] + `"`
   464  			if field[1], err = strconv.Unquote(f); err != nil {
   465  				t.Errorf("%s:%d: cannot unquote %s", file, lineno, f)
   466  			}
   467  			f = `"` + field[2] + `"`
   468  			if field[2], err = strconv.Unquote(f); err != nil {
   469  				t.Errorf("%s:%d: cannot unquote %s", file, lineno, f)
   470  			}
   471  		}
   472  
   473  		//   Field 2: the regular expression pattern; SAME uses the pattern from
   474  		//     the previous specification.
   475  		//
   476  		if field[1] == "SAME" {
   477  			field[1] = lastRegexp
   478  		}
   479  		lastRegexp = field[1]
   480  
   481  		//   Field 3: the string to match.
   482  		text := field[2]
   483  
   484  		//   Field 4: the test outcome...
   485  		ok, shouldCompile, shouldMatch, pos := parseFowlerResult(field[3])
   486  		if !ok {
   487  			t.Errorf("%s:%d: cannot parse result %#q", file, lineno, field[3])
   488  			continue Reading
   489  		}
   490  
   491  		//   Field 5: optional comment appended to the report.
   492  
   493  	Testing:
   494  		// Run test once for each specified capital letter mode that we support.
   495  		for _, c := range flag {
   496  			pattern := field[1]
   497  			syn := syntax.POSIX | syntax.ClassNL
   498  			switch c {
   499  			default:
   500  				continue Testing
   501  			case 'E':
   502  				// extended regexp (what we support)
   503  			case 'L':
   504  				// literal
   505  				pattern = QuoteMeta(pattern)
   506  			}
   507  
   508  			for _, c := range flag {
   509  				switch c {
   510  				case 'i':
   511  					syn |= syntax.FoldCase
   512  				}
   513  			}
   514  
   515  			re, err := compile(pattern, syn, true)
   516  			if err != nil {
   517  				if shouldCompile {
   518  					t.Errorf("%s:%d: %#q did not compile", file, lineno, pattern)
   519  				}
   520  				continue Testing
   521  			}
   522  			if !shouldCompile {
   523  				t.Errorf("%s:%d: %#q should not compile", file, lineno, pattern)
   524  				continue Testing
   525  			}
   526  			match := re.MatchString(text)
   527  			if match != shouldMatch {
   528  				t.Errorf("%s:%d: %#q.Match(%#q) = %v, want %v", file, lineno, pattern, text, match, shouldMatch)
   529  				continue Testing
   530  			}
   531  			have := re.FindStringSubmatchIndex(text)
   532  			if (len(have) > 0) != match {
   533  				t.Errorf("%s:%d: %#q.Match(%#q) = %v, but %#q.FindSubmatchIndex(%#q) = %v", file, lineno, pattern, text, match, pattern, text, have)
   534  				continue Testing
   535  			}
   536  			if len(have) > len(pos) {
   537  				have = have[:len(pos)]
   538  			}
   539  			if !slices.Equal(have, pos) {
   540  				t.Errorf("%s:%d: %#q.FindSubmatchIndex(%#q) = %v, want %v", file, lineno, pattern, text, have, pos)
   541  			}
   542  		}
   543  	}
   544  }
   545  
   546  func parseFowlerResult(s string) (ok, compiled, matched bool, pos []int) {
   547  	//   Field 4: the test outcome. This is either one of the posix error
   548  	//     codes (with REG_ omitted) or the match array, a list of (m,n)
   549  	//     entries with m and n being first and last+1 positions in the
   550  	//     field 3 string, or NULL if REG_NOSUB is in effect and success
   551  	//     is expected. BADPAT is acceptable in place of any regcomp(3)
   552  	//     error code. The match[] array is initialized to (-2,-2) before
   553  	//     each test. All array elements from 0 to nmatch-1 must be specified
   554  	//     in the outcome. Unspecified endpoints (offset -1) are denoted by ?.
   555  	//     Unset endpoints (offset -2) are denoted by X. {x}(o:n) denotes a
   556  	//     matched (?{...}) expression, where x is the text enclosed by {...},
   557  	//     o is the expression ordinal counting from 1, and n is the length of
   558  	//     the unmatched portion of the subject string. If x starts with a
   559  	//     number then that is the return value of re_execf(), otherwise 0 is
   560  	//     returned.
   561  	switch {
   562  	case s == "":
   563  		// Match with no position information.
   564  		ok = true
   565  		compiled = true
   566  		matched = true
   567  		return
   568  	case s == "NOMATCH":
   569  		// Match failure.
   570  		ok = true
   571  		compiled = true
   572  		matched = false
   573  		return
   574  	case 'A' <= s[0] && s[0] <= 'Z':
   575  		// All the other error codes are compile errors.
   576  		ok = true
   577  		compiled = false
   578  		return
   579  	}
   580  	compiled = true
   581  
   582  	var x []int
   583  	for s != "" {
   584  		var end byte = ')'
   585  		if len(x)%2 == 0 {
   586  			if s[0] != '(' {
   587  				ok = false
   588  				return
   589  			}
   590  			s = s[1:]
   591  			end = ','
   592  		}
   593  		i := 0
   594  		for i < len(s) && s[i] != end {
   595  			i++
   596  		}
   597  		if i == 0 || i == len(s) {
   598  			ok = false
   599  			return
   600  		}
   601  		var v = -1
   602  		var err error
   603  		if s[:i] != "?" {
   604  			v, err = strconv.Atoi(s[:i])
   605  			if err != nil {
   606  				ok = false
   607  				return
   608  			}
   609  		}
   610  		x = append(x, v)
   611  		s = s[i+1:]
   612  	}
   613  	if len(x)%2 != 0 {
   614  		ok = false
   615  		return
   616  	}
   617  	ok = true
   618  	matched = true
   619  	pos = x
   620  	return
   621  }
   622  
   623  var text []byte
   624  
   625  func makeText(n int) []byte {
   626  	if len(text) >= n {
   627  		return text[:n]
   628  	}
   629  	text = make([]byte, n)
   630  	x := ^uint32(0)
   631  	for i := range text {
   632  		x += x
   633  		x ^= 1
   634  		if int32(x) < 0 {
   635  			x ^= 0x88888eef
   636  		}
   637  		if x%31 == 0 {
   638  			text[i] = '\n'
   639  		} else {
   640  			text[i] = byte(x%(0x7E+1-0x20) + 0x20)
   641  		}
   642  	}
   643  	return text
   644  }
   645  
   646  func BenchmarkMatch(b *testing.B) {
   647  	isRaceBuilder := strings.HasSuffix(testenv.Builder(), "-race")
   648  
   649  	for _, data := range benchData {
   650  		r := MustCompile(data.re)
   651  		for _, size := range benchSizes {
   652  			if (isRaceBuilder || testing.Short()) && size.n > 1<<10 {
   653  				continue
   654  			}
   655  			t := makeText(size.n)
   656  			b.Run(data.name+"/"+size.name, func(b *testing.B) {
   657  				b.SetBytes(int64(size.n))
   658  				for i := 0; i < b.N; i++ {
   659  					if r.Match(t) {
   660  						b.Fatal("match!")
   661  					}
   662  				}
   663  			})
   664  		}
   665  	}
   666  }
   667  
   668  func BenchmarkMatch_onepass_regex(b *testing.B) {
   669  	isRaceBuilder := strings.HasSuffix(testenv.Builder(), "-race")
   670  	r := MustCompile(`(?s)\A.*\z`)
   671  	if r.onepass == nil {
   672  		b.Fatalf("want onepass regex, but %q is not onepass", r)
   673  	}
   674  	for _, size := range benchSizes {
   675  		if (isRaceBuilder || testing.Short()) && size.n > 1<<10 {
   676  			continue
   677  		}
   678  		t := makeText(size.n)
   679  		b.Run(size.name, func(b *testing.B) {
   680  			b.SetBytes(int64(size.n))
   681  			b.ReportAllocs()
   682  			for i := 0; i < b.N; i++ {
   683  				if !r.Match(t) {
   684  					b.Fatal("not match!")
   685  				}
   686  			}
   687  		})
   688  	}
   689  }
   690  
   691  var benchData = []struct{ name, re string }{
   692  	{"Easy0", "ABCDEFGHIJKLMNOPQRSTUVWXYZ$"},
   693  	{"Easy0i", "(?i)ABCDEFGHIJklmnopqrstuvwxyz$"},
   694  	{"Easy1", "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$"},
   695  	{"Medium", "[XYZ]ABCDEFGHIJKLMNOPQRSTUVWXYZ$"},
   696  	{"Hard", "[ -~]*ABCDEFGHIJKLMNOPQRSTUVWXYZ$"},
   697  	{"Hard1", "ABCD|CDEF|EFGH|GHIJ|IJKL|KLMN|MNOP|OPQR|QRST|STUV|UVWX|WXYZ"},
   698  }
   699  
   700  var benchSizes = []struct {
   701  	name string
   702  	n    int
   703  }{
   704  	{"16", 16},
   705  	{"32", 32},
   706  	{"1K", 1 << 10},
   707  	{"32K", 32 << 10},
   708  	{"1M", 1 << 20},
   709  	{"32M", 32 << 20},
   710  }
   711  
   712  func TestLongest(t *testing.T) {
   713  	re, err := Compile(`a(|b)`)
   714  	if err != nil {
   715  		t.Fatal(err)
   716  	}
   717  	if g, w := re.FindString("ab"), "a"; g != w {
   718  		t.Errorf("first match was %q, want %q", g, w)
   719  	}
   720  	re.Longest()
   721  	if g, w := re.FindString("ab"), "ab"; g != w {
   722  		t.Errorf("longest match was %q, want %q", g, w)
   723  	}
   724  }
   725  
   726  // TestProgramTooLongForBacktrack tests that a regex which is too long
   727  // for the backtracker still executes properly.
   728  func TestProgramTooLongForBacktrack(t *testing.T) {
   729  	longRegex := MustCompile(`(one|two|three|four|five|six|seven|eight|nine|ten|eleven|twelve|thirteen|fourteen|fifteen|sixteen|seventeen|eighteen|nineteen|twenty|twentyone|twentytwo|twentythree|twentyfour|twentyfive|twentysix|twentyseven|twentyeight|twentynine|thirty|thirtyone|thirtytwo|thirtythree|thirtyfour|thirtyfive|thirtysix|thirtyseven|thirtyeight|thirtynine|forty|fortyone|fortytwo|fortythree|fortyfour|fortyfive|fortysix|fortyseven|fortyeight|fortynine|fifty|fiftyone|fiftytwo|fiftythree|fiftyfour|fiftyfive|fiftysix|fiftyseven|fiftyeight|fiftynine|sixty|sixtyone|sixtytwo|sixtythree|sixtyfour|sixtyfive|sixtysix|sixtyseven|sixtyeight|sixtynine|seventy|seventyone|seventytwo|seventythree|seventyfour|seventyfive|seventysix|seventyseven|seventyeight|seventynine|eighty|eightyone|eightytwo|eightythree|eightyfour|eightyfive|eightysix|eightyseven|eightyeight|eightynine|ninety|ninetyone|ninetytwo|ninetythree|ninetyfour|ninetyfive|ninetysix|ninetyseven|ninetyeight|ninetynine|onehundred)`)
   730  	if !longRegex.MatchString("two") {
   731  		t.Errorf("longRegex.MatchString(\"two\") was false, want true")
   732  	}
   733  	if longRegex.MatchString("xxx") {
   734  		t.Errorf("longRegex.MatchString(\"xxx\") was true, want false")
   735  	}
   736  }
   737  

View as plain text