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 "testing" 11 ) 12 13 var 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 124 func 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 136 var onePass = &onePassProg{} 137 138 var onePassTests = []struct { 139 re string 140 onePass *onePassProg 141 }{ 142 {`^(?:a|(?:a*))$`, notOnePass}, 143 {`^(?:(a)|(?:a*))$`, notOnePass}, 144 {`^(?:(?:(?:.(?:$))?))$`, onePass}, 145 {`^abcd$`, onePass}, 146 {`^(?:(?:a{0,})*?)$`, onePass}, 147 {`^(?:(?:a+)*)$`, onePass}, 148 {`^(?:(?:a|(?:aa)))$`, onePass}, 149 {`^(?:[^\s\S])$`, onePass}, 150 {`^(?:(?:a{3,4}){0,})$`, notOnePass}, 151 {`^(?:(?:(?:a*)+))$`, onePass}, 152 {`^[a-c]+$`, onePass}, 153 {`^[a-c]*$`, onePass}, 154 {`^(?:a*)$`, onePass}, 155 {`^(?:(?:aa)|a)$`, onePass}, 156 {`^[a-c]*`, notOnePass}, 157 {`^...$`, onePass}, 158 {`^(?:a|(?:aa))$`, onePass}, 159 {`^a((b))c$`, onePass}, 160 {`^a.[l-nA-Cg-j]?e$`, onePass}, 161 {`^a((b))$`, onePass}, 162 {`^a(?:(b)|(c))c$`, onePass}, 163 {`^a(?:(b*)|(c))c$`, notOnePass}, 164 {`^a(?:b|c)$`, onePass}, 165 {`^a(?:b?|c)$`, onePass}, 166 {`^a(?:b?|c?)$`, notOnePass}, 167 {`^a(?:b?|c+)$`, onePass}, 168 {`^a(?:b+|(bc))d$`, notOnePass}, 169 {`^a(?:bc)+$`, onePass}, 170 {`^a(?:[bcd])+$`, onePass}, 171 {`^a((?:[bcd])+)$`, onePass}, 172 {`^a(:?b|c)*d$`, onePass}, 173 {`^.bc(d|e)*$`, onePass}, 174 {`^(?:(?:aa)|.)$`, notOnePass}, 175 {`^(?:(?:a{1,2}){1,2})$`, notOnePass}, 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 onePass = compileOnePass(p) 196 if (onePass == notOnePass) != (test.onePass == notOnePass) { 197 t.Errorf("CompileOnePass(%q) got %v, expected %v", test.re, onePass, test.onePass) 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 == notOnePass { 218 t.Errorf("Compile(%q): got notOnePass, 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
