libgo/go/regexp/syntax/compile.go

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