src/regexp/onepass_test.go

   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 }