onepass_test.go

     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 onePassTests = []struct {
   138  	re        string
   139  	isOnePass bool
   140  }{
   141  	{`^(?:a|(?:a*))$`, false},
   142  	{`^(?:(a)|(?:a*))$`, false},
   143  	{`^(?:(?:(?:.(?:$))?))$`, true},
   144  	{`^abcd$`, true},
   145  	{`^(?:(?:a{0,})*?)$`, false},
   146  	{`^(?:(?:a+)*)$`, true},
   147  	{`^(?:(?:a|(?:aa)))$`, true},
   148  	{`^(?:[^\s\S])$`, true},
   149  	{`^(?:(?:a{3,4}){0,})$`, false},
   150  	{`^(?:(?:(?:a*)+))$`, true},
   151  	{`^[a-c]+$`, true},
   152  	{`^[a-c]*$`, true},
   153  	{`^(?:a*)$`, true},
   154  	{`^(?:(?:aa)|a)$`, true},
   155  	{`^[a-c]*`, false},
   156  	{`^...$`, true},
   157  	{`^(?:a|(?:aa))$`, true},
   158  	{`^a((b))c$`, true},
   159  	{`^a.[l-nA-Cg-j]?e$`, true},
   160  	{`^a((b))$`, true},
   161  	{`^a(?:(b)|(c))c$`, true},
   162  	{`^a(?:(b*)|(c))c$`, false},
   163  	{`^a(?:b|c)$`, true},
   164  	{`^a(?:b?|c)$`, true},
   165  	{`^a(?:b?|c?)$`, false},
   166  	{`^a(?:b?|c+)$`, true},
   167  	{`^a(?:b+|(bc))d$`, false},
   168  	{`^a(?:bc)+$`, true},
   169  	{`^a(?:[bcd])+$`, true},
   170  	{`^a((?:[bcd])+)$`, true},
   171  	{`^a(:?b|c)*d$`, true},
   172  	{`^.bc(d|e)*$`, true},
   173  	{`^(?:(?:aa)|.)$`, false},
   174  	{`^(?:(?:a{1,2}){1,2})$`, false},
   175  	{`^l` + strings.Repeat("o", 2<<8) + `ng$`, true},
   176  }
   177  
   178  func TestCompileOnePass(t *testing.T) {
   179  	var (
   180  		p   *syntax.Prog
   181  		re  *syntax.Regexp
   182  		err error
   183  	)
   184  	for _, test := range onePassTests {
   185  		if re, err = syntax.Parse(test.re, syntax.Perl); err != nil {
   186  			t.Errorf("Parse(%q) got err:%s, want success", test.re, err)
   187  			continue
   188  		}
   189  		// needs to be done before compile...
   190  		re = re.Simplify()
   191  		if p, err = syntax.Compile(re); err != nil {
   192  			t.Errorf("Compile(%q) got err:%s, want success", test.re, err)
   193  			continue
   194  		}
   195  		isOnePass := compileOnePass(p) != nil
   196  		if isOnePass != test.isOnePass {
   197  			t.Errorf("CompileOnePass(%q) got isOnePass=%v, expected %v", test.re, isOnePass, test.isOnePass)
   198  		}
   199  	}
   200  }
   201  
   202  // TODO(cespare): Unify with onePassTests and rationalize one-pass test cases.
   203  var onePassTests1 = []struct {
   204  	re    string
   205  	match string
   206  }{
   207  	{`^a(/b+(#c+)*)*$`, "a/b#c"}, // golang.org/issue/11905
   208  }
   209  
   210  func TestRunOnePass(t *testing.T) {
   211  	for _, test := range onePassTests1 {
   212  		re, err := Compile(test.re)
   213  		if err != nil {
   214  			t.Errorf("Compile(%q): got err: %s", test.re, err)
   215  			continue
   216  		}
   217  		if re.onepass == nil {
   218  			t.Errorf("Compile(%q): got nil, want one-pass", test.re)
   219  			continue
   220  		}
   221  		if !re.MatchString(test.match) {
   222  			t.Errorf("onepass %q did not match %q", test.re, test.match)
   223  		}
   224  	}
   225  }
   226
View as plain text