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 const noStr = `!` 137 138 var onePass = &onePassProg{} 139 140 var onePassTests = []struct { 141 re string 142 onePass *onePassProg 143 prog string 144 }{ 145 {`^(?:a|(?:a*))$`, notOnePass, noStr}, 146 {`^(?:(a)|(?:a*))$`, notOnePass, noStr}, 147 {`^(?:(?:(?:.(?:$))?))$`, onePass, `a`}, 148 {`^abcd$`, onePass, `abcd`}, 149 {`^abcd$`, onePass, `abcde`}, 150 {`^(?:(?:a{0,})*?)$`, onePass, `a`}, 151 {`^(?:(?:a+)*)$`, onePass, ``}, 152 {`^(?:(?:a|(?:aa)))$`, onePass, ``}, 153 {`^(?:[^\s\S])$`, onePass, ``}, 154 {`^(?:(?:a{3,4}){0,})$`, notOnePass, `aaaaaa`}, 155 {`^(?:(?:a+)*)$`, onePass, `a`}, 156 {`^(?:(?:(?:a*)+))$`, onePass, noStr}, 157 {`^(?:(?:a+)*)$`, onePass, ``}, 158 {`^[a-c]+$`, onePass, `abc`}, 159 {`^[a-c]*$`, onePass, `abcdabc`}, 160 {`^(?:a*)$`, onePass, `aaaaaaa`}, 161 {`^(?:(?:aa)|a)$`, onePass, `a`}, 162 {`^[a-c]*`, notOnePass, `abcdabc`}, 163 {`^[a-c]*$`, onePass, `abc`}, 164 {`^...$`, onePass, ``}, 165 {`^(?:a|(?:aa))$`, onePass, `a`}, 166 {`^[a-c]*`, notOnePass, `abcabc`}, 167 {`^a((b))c$`, onePass, noStr}, 168 {`^a.[l-nA-Cg-j]?e$`, onePass, noStr}, 169 {`^a((b))$`, onePass, noStr}, 170 {`^a(?:(b)|(c))c$`, onePass, noStr}, 171 {`^a(?:(b*)|(c))c$`, notOnePass, noStr}, 172 {`^a(?:b|c)$`, onePass, noStr}, 173 {`^a(?:b?|c)$`, onePass, noStr}, 174 {`^a(?:b?|c?)$`, notOnePass, noStr}, 175 {`^a(?:b?|c+)$`, onePass, noStr}, 176 {`^a(?:b+|(bc))d$`, notOnePass, noStr}, 177 {`^a(?:bc)+$`, onePass, noStr}, 178 {`^a(?:[bcd])+$`, onePass, noStr}, 179 {`^a((?:[bcd])+)$`, onePass, noStr}, 180 {`^a(:?b|c)*d$`, onePass, `abbbccbbcbbd"`}, 181 {`^.bc(d|e)*$`, onePass, `abcddddddeeeededd`}, 182 {`^(?:(?:aa)|.)$`, notOnePass, `a`}, 183 {`^(?:(?:a{1,2}){1,2})$`, notOnePass, `aaaa`}, 184 } 185 186 func TestCompileOnePass(t *testing.T) { 187 var ( 188 p *syntax.Prog 189 re *syntax.Regexp 190 err error 191 ) 192 for _, test := range onePassTests { 193 if re, err = syntax.Parse(test.re, syntax.Perl); err != nil { 194 t.Errorf("Parse(%q) got err:%s, want success", test.re, err) 195 continue 196 } 197 // needs to be done before compile... 198 re = re.Simplify() 199 if p, err = syntax.Compile(re); err != nil { 200 t.Errorf("Compile(%q) got err:%s, want success", test.re, err) 201 continue 202 } 203 onePass = compileOnePass(p) 204 if (onePass == notOnePass) != (test.onePass == notOnePass) { 205 t.Errorf("CompileOnePass(%q) got %v, expected %v", test.re, onePass, test.onePass) 206 } 207 } 208 } 209
