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 5package regexp 6 7import ( 8 "reflect" 9 "regexp/syntax" 10 "testing" 11) 12 13var runeMergeTests = []struct { 14 left, right, merged []rune 15 next []uint32 16 leftPC, rightPC uint32 17}{ 18 { 19 // empty rhs 20 []rune{69, 69}, 21 []rune{}, 22 []rune{69, 69}, 23 []uint32{1}, 24 1, 2, 25 }, 26 { 27 // identical runes, identical targets 28 []rune{69, 69}, 29 []rune{69, 69}, 30 []rune{}, 31 []uint32{mergeFailed}, 32 1, 1, 33 }, 34 { 35 // identical runes, different targets 36 []rune{69, 69}, 37 []rune{69, 69}, 38 []rune{}, 39 []uint32{mergeFailed}, 40 1, 2, 41 }, 42 { 43 // append right-first 44 []rune{69, 69}, 45 []rune{71, 71}, 46 []rune{69, 69, 71, 71}, 47 []uint32{1, 2}, 48 1, 2, 49 }, 50 { 51 // append, left-first 52 []rune{71, 71}, 53 []rune{69, 69}, 54 []rune{69, 69, 71, 71}, 55 []uint32{2, 1}, 56 1, 2, 57 }, 58 { 59 // successful interleave 60 []rune{60, 60, 71, 71, 101, 101}, 61 []rune{69, 69, 88, 88}, 62 []rune{60, 60, 69, 69, 71, 71, 88, 88, 101, 101}, 63 []uint32{1, 2, 1, 2, 1}, 64 1, 2, 65 }, 66 { 67 // left surrounds right 68 []rune{69, 74}, 69 []rune{71, 71}, 70 []rune{}, 71 []uint32{mergeFailed}, 72 1, 2, 73 }, 74 { 75 // right surrounds left 76 []rune{69, 74}, 77 []rune{68, 75}, 78 []rune{}, 79 []uint32{mergeFailed}, 80 1, 2, 81 }, 82 { 83 // overlap at interval begin 84 []rune{69, 74}, 85 []rune{74, 75}, 86 []rune{}, 87 []uint32{mergeFailed}, 88 1, 2, 89 }, 90 { 91 // overlap ar interval end 92 []rune{69, 74}, 93 []rune{65, 69}, 94 []rune{}, 95 []uint32{mergeFailed}, 96 1, 2, 97 }, 98 { 99 // overlap from above 100 []rune{69, 74}, 101 []rune{71, 74}, 102 []rune{}, 103 []uint32{mergeFailed}, 104 1, 2, 105 }, 106 { 107 // overlap from below 108 []rune{69, 74}, 109 []rune{65, 71}, 110 []rune{}, 111 []uint32{mergeFailed}, 112 1, 2, 113 }, 114 { 115 // out of order []rune 116 []rune{69, 74, 60, 65}, 117 []rune{66, 67}, 118 []rune{}, 119 []uint32{mergeFailed}, 120 1, 2, 121 }, 122} 123 124func TestMergeRuneSet(t *testing.T) { 125 for ix, test := range runeMergeTests { 126 merged, next := mergeRuneSets(&test.left, &test.right, test.leftPC, test.rightPC) 127 if !reflect.DeepEqual(merged, test.merged) { 128 t.Errorf("mergeRuneSet :%d (%v, %v) merged\n have\n%v\nwant\n%v", ix, test.left, test.right, merged, test.merged) 129 } 130 if !reflect.DeepEqual(next, test.next) { 131 t.Errorf("mergeRuneSet :%d(%v, %v) next\n have\n%v\nwant\n%v", ix, test.left, test.right, next, test.next) 132 } 133 } 134} 135 136const noStr = `!` 137 138var onePass = &onePassProg{} 139 140var onePassTests = []struct { 141 re string 142 onePass *onePassProg 143}{ 144 {`^(?:a|(?:a*))$`, notOnePass}, 145 {`^(?:(a)|(?:a*))$`, notOnePass}, 146 {`^(?:(?:(?:.(?:$))?))$`, onePass}, 147 {`^abcd$`, onePass}, 148 {`^(?:(?:a{0,})*?)$`, onePass}, 149 {`^(?:(?:a+)*)$`, onePass}, 150 {`^(?:(?:a|(?:aa)))$`, onePass}, 151 {`^(?:[^\s\S])$`, onePass}, 152 {`^(?:(?:a{3,4}){0,})$`, notOnePass}, 153 {`^(?:(?:(?:a*)+))$`, onePass}, 154 {`^[a-c]+$`, onePass}, 155 {`^[a-c]*$`, onePass}, 156 {`^(?:a*)$`, onePass}, 157 {`^(?:(?:aa)|a)$`, onePass}, 158 {`^[a-c]*`, notOnePass}, 159 {`^...$`, onePass}, 160 {`^(?:a|(?:aa))$`, onePass}, 161 {`^a((b))c$`, onePass}, 162 {`^a.[l-nA-Cg-j]?e$`, onePass}, 163 {`^a((b))$`, onePass}, 164 {`^a(?:(b)|(c))c$`, onePass}, 165 {`^a(?:(b*)|(c))c$`, notOnePass}, 166 {`^a(?:b|c)$`, onePass}, 167 {`^a(?:b?|c)$`, onePass}, 168 {`^a(?:b?|c?)$`, notOnePass}, 169 {`^a(?:b?|c+)$`, onePass}, 170 {`^a(?:b+|(bc))d$`, notOnePass}, 171 {`^a(?:bc)+$`, onePass}, 172 {`^a(?:[bcd])+$`, onePass}, 173 {`^a((?:[bcd])+)$`, onePass}, 174 {`^a(:?b|c)*d$`, onePass}, 175 {`^.bc(d|e)*$`, onePass}, 176 {`^(?:(?:aa)|.)$`, notOnePass}, 177 {`^(?:(?:a{1,2}){1,2})$`, notOnePass}, 178} 179 180func 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. 205var onePassTests1 = []struct { 206 re string 207 match string 208}{ 209 {`^a(/b+(#c+)*)*$`, "a/b#c"}, // golang.org/issue/11905 210} 211 212func 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