...
Run Format

Source file src/regexp/onepass_test.go

Documentation: regexp

     1  // Copyright 2014 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  	"reflect"
     9  	"regexp/syntax"
    10  	"strings"
    11  	"testing"
    12  )
    13  
    14  var runeMergeTests = []struct {
    15  	left, right, merged []rune
    16  	next                []uint32
    17  	leftPC, rightPC     uint32
    18  }{
    19  	{
    20  		// empty rhs
    21  		[]rune{69, 69},
    22  		[]rune{},
    23  		[]rune{69, 69},
    24  		[]uint32{1},
    25  		1, 2,
    26  	},
    27  	{
    28  		// identical runes, identical targets
    29  		[]rune{69, 69},
    30  		[]rune{69, 69},
    31  		[]rune{},
    32  		[]uint32{mergeFailed},
    33  		1, 1,
    34  	},
    35  	{
    36  		// identical runes, different targets
    37  		[]rune{69, 69},
    38  		[]rune{69, 69},
    39  		[]rune{},
    40  		[]uint32{mergeFailed},
    41  		1, 2,
    42  	},
    43  	{
    44  		// append right-first
    45  		[]rune{69, 69},
    46  		[]rune{71, 71},
    47  		[]rune{69, 69, 71, 71},
    48  		[]uint32{1, 2},
    49  		1, 2,
    50  	},
    51  	{
    52  		// append, left-first
    53  		[]rune{71, 71},
    54  		[]rune{69, 69},
    55  		[]rune{69, 69, 71, 71},
    56  		[]uint32{2, 1},
    57  		1, 2,
    58  	},
    59  	{
    60  		// successful interleave
    61  		[]rune{60, 60, 71, 71, 101, 101},
    62  		[]rune{69, 69, 88, 88},
    63  		[]rune{60, 60, 69, 69, 71, 71, 88, 88, 101, 101},
    64  		[]uint32{1, 2, 1, 2, 1},
    65  		1, 2,
    66  	},
    67  	{
    68  		// left surrounds right
    69  		[]rune{69, 74},
    70  		[]rune{71, 71},
    71  		[]rune{},
    72  		[]uint32{mergeFailed},
    73  		1, 2,
    74  	},
    75  	{
    76  		// right surrounds left
    77  		[]rune{69, 74},
    78  		[]rune{68, 75},
    79  		[]rune{},
    80  		[]uint32{mergeFailed},
    81  		1, 2,
    82  	},
    83  	{
    84  		// overlap at interval begin
    85  		[]rune{69, 74},
    86  		[]rune{74, 75},
    87  		[]rune{},
    88  		[]uint32{mergeFailed},
    89  		1, 2,
    90  	},
    91  	{
    92  		// overlap ar interval end
    93  		[]rune{69, 74},
    94  		[]rune{65, 69},
    95  		[]rune{},
    96  		[]uint32{mergeFailed},
    97  		1, 2,
    98  	},
    99  	{
   100  		// overlap from above
   101  		[]rune{69, 74},
   102  		[]rune{71, 74},
   103  		[]rune{},
   104  		[]uint32{mergeFailed},
   105  		1, 2,
   106  	},
   107  	{
   108  		// overlap from below
   109  		[]rune{69, 74},
   110  		[]rune{65, 71},
   111  		[]rune{},
   112  		[]uint32{mergeFailed},
   113  		1, 2,
   114  	},
   115  	{
   116  		// out of order []rune
   117  		[]rune{69, 74, 60, 65},
   118  		[]rune{66, 67},
   119  		[]rune{},
   120  		[]uint32{mergeFailed},
   121  		1, 2,
   122  	},
   123  }
   124  
   125  func TestMergeRuneSet(t *testing.T) {
   126  	for ix, test := range runeMergeTests {
   127  		merged, next := mergeRuneSets(&test.left, &test.right, test.leftPC, test.rightPC)
   128  		if !reflect.DeepEqual(merged, test.merged) {
   129  			t.Errorf("mergeRuneSet :%d (%v, %v) merged\n have\n%v\nwant\n%v", ix, test.left, test.right, merged, test.merged)
   130  		}
   131  		if !reflect.DeepEqual(next, test.next) {
   132  			t.Errorf("mergeRuneSet :%d(%v, %v) next\n have\n%v\nwant\n%v", ix, test.left, test.right, next, test.next)
   133  		}
   134  	}
   135  }
   136  
   137  var onePass = &onePassProg{}
   138  
   139  var onePassTests = []struct {
   140  	re      string
   141  	onePass *onePassProg
   142  }{
   143  	{`^(?:a|(?:a*))$`, notOnePass},
   144  	{`^(?:(a)|(?:a*))$`, notOnePass},
   145  	{`^(?:(?:(?:.(?:$))?))$`, onePass},
   146  	{`^abcd$`, onePass},
   147  	{`^(?:(?:a{0,})*?)$`, onePass},
   148  	{`^(?:(?:a+)*)$`, onePass},
   149  	{`^(?:(?:a|(?:aa)))$`, onePass},
   150  	{`^(?:[^\s\S])$`, onePass},
   151  	{`^(?:(?:a{3,4}){0,})$`, notOnePass},
   152  	{`^(?:(?:(?:a*)+))$`, onePass},
   153  	{`^[a-c]+$`, onePass},
   154  	{`^[a-c]*$`, onePass},
   155  	{`^(?:a*)$`, onePass},
   156  	{`^(?:(?:aa)|a)$`, onePass},
   157  	{`^[a-c]*`, notOnePass},
   158  	{`^...$`, onePass},
   159  	{`^(?:a|(?:aa))$`, onePass},
   160  	{`^a((b))c$`, onePass},
   161  	{`^a.[l-nA-Cg-j]?e$`, onePass},
   162  	{`^a((b))$`, onePass},
   163  	{`^a(?:(b)|(c))c$`, onePass},
   164  	{`^a(?:(b*)|(c))c$`, notOnePass},
   165  	{`^a(?:b|c)$`, onePass},
   166  	{`^a(?:b?|c)$`, onePass},
   167  	{`^a(?:b?|c?)$`, notOnePass},
   168  	{`^a(?:b?|c+)$`, onePass},
   169  	{`^a(?:b+|(bc))d$`, notOnePass},
   170  	{`^a(?:bc)+$`, onePass},
   171  	{`^a(?:[bcd])+$`, onePass},
   172  	{`^a((?:[bcd])+)$`, onePass},
   173  	{`^a(:?b|c)*d$`, onePass},
   174  	{`^.bc(d|e)*$`, onePass},
   175  	{`^(?:(?:aa)|.)$`, notOnePass},
   176  	{`^(?:(?:a{1,2}){1,2})$`, notOnePass},
   177  	{`^l` + strings.Repeat("o", 2<<8) + `ng$`, onePass},
   178  }
   179  
   180  func TestCompileOnePass(t *testing.T) {
   181  	var (
   182  		p   *syntax.Prog
   183  		re  *syntax.Regexp
   184  		err error
   185  	)
   186  	for _, test := range onePassTests {
   187  		if re, err = syntax.Parse(test.re, syntax.Perl); err != nil {
   188  			t.Errorf("Parse(%q) got err:%s, want success", test.re, err)
   189  			continue
   190  		}
   191  		// needs to be done before compile...
   192  		re = re.Simplify()
   193  		if p, err = syntax.Compile(re); err != nil {
   194  			t.Errorf("Compile(%q) got err:%s, want success", test.re, err)
   195  			continue
   196  		}
   197  		onePass = compileOnePass(p)
   198  		if (onePass == notOnePass) != (test.onePass == notOnePass) {
   199  			t.Errorf("CompileOnePass(%q) got %v, expected %v", test.re, onePass, test.onePass)
   200  		}
   201  	}
   202  }
   203  
   204  // TODO(cespare): Unify with onePassTests and rationalize one-pass test cases.
   205  var onePassTests1 = []struct {
   206  	re    string
   207  	match string
   208  }{
   209  	{`^a(/b+(#c+)*)*$`, "a/b#c"}, // golang.org/issue/11905
   210  }
   211  
   212  func TestRunOnePass(t *testing.T) {
   213  	for _, test := range onePassTests1 {
   214  		re, err := Compile(test.re)
   215  		if err != nil {
   216  			t.Errorf("Compile(%q): got err: %s", test.re, err)
   217  			continue
   218  		}
   219  		if re.onepass == notOnePass {
   220  			t.Errorf("Compile(%q): got notOnePass, want one-pass", test.re)
   221  			continue
   222  		}
   223  		if !re.MatchString(test.match) {
   224  			t.Errorf("onepass %q did not match %q", test.re, test.match)
   225  		}
   226  	}
   227  }
   228  
   229  func BenchmarkCompileOnepass(b *testing.B) {
   230  	for _, test := range onePassTests {
   231  		if test.onePass == notOnePass {
   232  			continue
   233  		}
   234  		name := test.re
   235  		if len(name) > 20 {
   236  			name = name[:20] + "..."
   237  		}
   238  		b.Run(name, func(b *testing.B) {
   239  			b.ReportAllocs()
   240  			for i := 0; i < b.N; i++ {
   241  				if _, err := Compile(test.re); err != nil {
   242  					b.Fatal(err)
   243  				}
   244  			}
   245  		})
   246  	}
   247  }
   248  

View as plain text