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
