libgo/go/regexp/syntax/compile.go

   1 package syntax
   2
   3 import (
   4         "os"
   5         "unicode"
   6 )
   7
   8 // A patchList is a list of instruction pointers that need to be filled in (patched).
   9 // Because the pointers haven't been filled in yet, we can reuse their storage
  10 // to hold the list.  It's kind of sleazy, but works well in practice.
  11 // See http://swtch.com/~rsc/regexp/regexp1.html for inspiration.
  12 //
  13 // These aren't really pointers: they're integers, so we can reinterpret them
  14 // this way without using package unsafe.  A value l denotes
  15 // p.inst[l>>1].Out (l&1==0) or .Arg (l&1==1).
  16 // l == 0 denotes the empty list, okay because we start every program
  17 // with a fail instruction, so we'll never want to point at its output link.
  18 type patchList uint32
  19
  20 func (l patchList) next(p *Prog) patchList {
  21         i := &p.Inst[l>>1]
  22         if l&1 == 0 {
  23                 return patchList(i.Out)
  24         }
  25         return patchList(i.Arg)
  26 }
  27
  28 func (l patchList) patch(p *Prog, val uint32) {
  29         for l != 0 {
  30                 i := &p.Inst[l>>1]
  31                 if l&1 == 0 {
  32                         l = patchList(i.Out)
  33                         i.Out = val
  34                 } else {
  35                         l = patchList(i.Arg)
  36                         i.Arg = val
  37                 }
  38         }
  39 }
  40
  41 func (l1 patchList) append(p *Prog, l2 patchList) patchList {
  42         if l1 == 0 {
  43                 return l2
  44         }
  45         if l2 == 0 {
  46                 return l1
  47         }
  48
  49         last := l1
  50         for {
  51                 next := last.next(p)
  52                 if next == 0 {
  53                         break
  54                 }
  55                 last = next
  56         }
  57
  58         i := &p.Inst[last>>1]
  59         if last&1 == 0 {
  60                 i.Out = uint32(l2)
  61         } else {
  62                 i.Arg = uint32(l2)
  63         }
  64         return l1
  65 }
  66
  67 // A frag represents a compiled program fragment.
  68 type frag struct {
  69         i   uint32    // index of first instruction
  70         out patchList // where to record end instruction
  71 }
  72
  73 type compiler struct {
  74         p *Prog
  75 }
  76
  77 // Compile compiles the regexp into a program to be executed.
  78 // The regexp should have been simplified already (returned from re.Simplify).
  79 func Compile(re *Regexp) (*Prog, os.Error) {
  80         var c compiler
  81         c.init()
  82         f := c.compile(re)
  83         f.out.patch(c.p, c.inst(InstMatch).i)
  84         c.p.Start = int(f.i)
  85         return c.p, nil
  86 }
  87
  88 func (c *compiler) init() {
  89         c.p = new(Prog)
  90         c.p.NumCap = 2 // implicit ( and ) for whole match $0
  91         c.inst(InstFail)
  92 }
  93
  94 var anyRuneNotNL = []int{0, '\n' - 1, '\n' + 1, unicode.MaxRune}
  95 var anyRune = []int{0, unicode.MaxRune}
  96
  97 func (c *compiler) compile(re *Regexp) frag {
  98         switch re.Op {
  99         case OpNoMatch:
 100                 return c.fail()
 101         case OpEmptyMatch:
 102                 return c.nop()
 103         case OpLiteral:
 104                 if len(re.Rune) == 0 {
 105                         return c.nop()
 106                 }
 107                 var f frag
 108                 for j := range re.Rune {
 109                         f1 := c.rune(re.Rune[j:j+1], re.Flags)
 110                         if j == 0 {
 111                                 f = f1
 112                         } else {
 113                                 f = c.cat(f, f1)
 114                         }
 115                 }
 116                 return f
 117         case OpCharClass:
 118                 return c.rune(re.Rune, re.Flags)
 119         case OpAnyCharNotNL:
 120                 return c.rune(anyRuneNotNL, 0)
 121         case OpAnyChar:
 122                 return c.rune(anyRune, 0)
 123         case OpBeginLine:
 124                 return c.empty(EmptyBeginLine)
 125         case OpEndLine:
 126                 return c.empty(EmptyEndLine)
 127         case OpBeginText:
 128                 return c.empty(EmptyBeginText)
 129         case OpEndText:
 130                 return c.empty(EmptyEndText)
 131         case OpWordBoundary:
 132                 return c.empty(EmptyWordBoundary)
 133         case OpNoWordBoundary:
 134                 return c.empty(EmptyNoWordBoundary)
 135         case OpCapture:
 136                 bra := c.cap(uint32(re.Cap << 1))
 137                 sub := c.compile(re.Sub[0])
 138                 ket := c.cap(uint32(re.Cap<<1 | 1))
 139                 return c.cat(c.cat(bra, sub), ket)
 140         case OpStar:
 141                 return c.star(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
 142         case OpPlus:
 143                 return c.plus(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
 144         case OpQuest:
 145                 return c.quest(c.compile(re.Sub[0]), re.Flags&NonGreedy != 0)
 146         case OpConcat:
 147                 if len(re.Sub) == 0 {
 148                         return c.nop()
 149                 }
 150                 var f frag
 151                 for i, sub := range re.Sub {
 152                         if i == 0 {
 153                                 f = c.compile(sub)
 154                         } else {
 155                                 f = c.cat(f, c.compile(sub))
 156                         }
 157                 }
 158                 return f
 159         case OpAlternate:
 160                 var f frag
 161                 for _, sub := range re.Sub {
 162                         f = c.alt(f, c.compile(sub))
 163                 }
 164                 return f
 165         }
 166         panic("regexp: unhandled case in compile")
 167 }
 168
 169 func (c *compiler) inst(op InstOp) frag {
 170         // TODO: impose length limit
 171         f := frag{i: uint32(len(c.p.Inst))}
 172         c.p.Inst = append(c.p.Inst, Inst{Op: op})
 173         return f
 174 }
 175
 176 func (c *compiler) nop() frag {
 177         f := c.inst(InstNop)
 178         f.out = patchList(f.i << 1)
 179         return f
 180 }
 181
 182 func (c *compiler) fail() frag {
 183         return frag{}
 184 }
 185
 186 func (c *compiler) cap(arg uint32) frag {
 187         f := c.inst(InstCapture)
 188         f.out = patchList(f.i << 1)
 189         c.p.Inst[f.i].Arg = arg
 190
 191         if c.p.NumCap < int(arg)+1 {
 192                 c.p.NumCap = int(arg) + 1
 193         }
 194         return f
 195 }
 196
 197 func (c *compiler) cat(f1, f2 frag) frag {
 198         // concat of failure is failure
 199         if f1.i == 0 || f2.i == 0 {
 200                 return frag{}
 201         }
 202
 203         // TODO: elide nop
 204
 205         f1.out.patch(c.p, f2.i)
 206         return frag{f1.i, f2.out}
 207 }
 208
 209 func (c *compiler) alt(f1, f2 frag) frag {
 210         // alt of failure is other
 211         if f1.i == 0 {
 212                 return f2
 213         }
 214         if f2.i == 0 {
 215                 return f1
 216         }
 217
 218         f := c.inst(InstAlt)
 219         i := &c.p.Inst[f.i]
 220         i.Out = f1.i
 221         i.Arg = f2.i
 222         f.out = f1.out.append(c.p, f2.out)
 223         return f
 224 }
 225
 226 func (c *compiler) quest(f1 frag, nongreedy bool) frag {
 227         f := c.inst(InstAlt)
 228         i := &c.p.Inst[f.i]
 229         if nongreedy {
 230                 i.Arg = f1.i
 231                 f.out = patchList(f.i << 1)
 232         } else {
 233                 i.Out = f1.i
 234                 f.out = patchList(f.i<<1 | 1)
 235         }
 236         f.out = f.out.append(c.p, f1.out)
 237         return f
 238 }
 239
 240 func (c *compiler) star(f1 frag, nongreedy bool) frag {
 241         f := c.inst(InstAlt)
 242         i := &c.p.Inst[f.i]
 243         if nongreedy {
 244                 i.Arg = f1.i
 245                 f.out = patchList(f.i << 1)
 246         } else {
 247                 i.Out = f1.i
 248                 f.out = patchList(f.i<<1 | 1)
 249         }
 250         f1.out.patch(c.p, f.i)
 251         return f
 252 }
 253
 254 func (c *compiler) plus(f1 frag, nongreedy bool) frag {
 255         return frag{f1.i, c.star(f1, nongreedy).out}
 256 }
 257
 258 func (c *compiler) empty(op EmptyOp) frag {
 259         f := c.inst(InstEmptyWidth)
 260         c.p.Inst[f.i].Arg = uint32(op)
 261         f.out = patchList(f.i << 1)
 262         return f
 263 }
 264
 265 func (c *compiler) rune(rune []int, flags Flags) frag {
 266         f := c.inst(InstRune)
 267         i := &c.p.Inst[f.i]
 268         i.Rune = rune
 269         flags &= FoldCase // only relevant flag is FoldCase
 270         if len(rune) != 1 || unicode.SimpleFold(rune[0]) == rune[0] {
 271                 // and sometimes not even that
 272                 flags &^= FoldCase
 273         }
 274         i.Arg = uint32(flags)
 275         f.out = patchList(f.i << 1)
 276
 277         // Special cases for exec machine.
 278         switch {
 279         case flags&FoldCase == 0 && (len(rune) == 1 || len(rune) == 2 && rune[0] == rune[1]):
 280                 i.Op = InstRune1
 281         case len(rune) == 2 && rune[0] == 0 && rune[1] == unicode.MaxRune:
 282                 i.Op = InstRuneAny
 283         case len(rune) == 4 && rune[0] == 0 && rune[1] == '\n'-1 && rune[2] == '\n'+1 && rune[3] == unicode.MaxRune:
 284                 i.Op = InstRuneAnyNotNL
 285         }
 286
 287         return f
 288 }