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 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