libgo/go/regexp/exec.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 regexp
   6
   7 import (
   8         "io"
   9         "regexp/syntax"
  10 )
  11
  12 // A queue is a 'sparse array' holding pending threads of execution.
  13 // See http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
  14 type queue struct {
  15         sparse []uint32
  16         dense  []entry
  17 }
  18
  19 // A entry is an entry on a queue.
  20 // It holds both the instruction pc and the actual thread.
  21 // Some queue entries are just place holders so that the machine
  22 // knows it has considered that pc.  Such entries have t == nil.
  23 type entry struct {
  24         pc uint32
  25         t  *thread
  26 }
  27
  28 // A thread is the state of a single path through the machine:
  29 // an instruction and a corresponding capture array.
  30 // See http://swtch.com/~rsc/regexp/regexp2.html
  31 type thread struct {
  32         inst *syntax.Inst
  33         cap  []int
  34 }
  35
  36 // A machine holds all the state during an NFA simulation for p.
  37 type machine struct {
  38         re       *Regexp      // corresponding Regexp
  39         p        *syntax.Prog // compiled program
  40         q0, q1   queue        // two queues for runq, nextq
  41         pool     []*thread    // pool of available threads
  42         matched  bool         // whether a match was found
  43         matchcap []int        // capture information for the match
  44
  45         // cached inputs, to avoid allocation
  46         inputBytes  inputBytes
  47         inputString inputString
  48         inputReader inputReader
  49 }
  50
  51 func (m *machine) newInputBytes(b []byte) input {
  52         m.inputBytes.str = b
  53         return &m.inputBytes
  54 }
  55
  56 func (m *machine) newInputString(s string) input {
  57         m.inputString.str = s
  58         return &m.inputString
  59 }
  60
  61 func (m *machine) newInputReader(r io.RuneReader) input {
  62         m.inputReader.r = r
  63         m.inputReader.atEOT = false
  64         m.inputReader.pos = 0
  65         return &m.inputReader
  66 }
  67
  68 // progMachine returns a new machine running the prog p.
  69 func progMachine(p *syntax.Prog) *machine {
  70         m := &machine{p: p}
  71         n := len(m.p.Inst)
  72         m.q0 = queue{make([]uint32, n), make([]entry, 0, n)}
  73         m.q1 = queue{make([]uint32, n), make([]entry, 0, n)}
  74         ncap := p.NumCap
  75         if ncap < 2 {
  76                 ncap = 2
  77         }
  78         m.matchcap = make([]int, ncap)
  79         return m
  80 }
  81
  82 func (m *machine) init(ncap int) {
  83         for _, t := range m.pool {
  84                 t.cap = t.cap[:ncap]
  85         }
  86         m.matchcap = m.matchcap[:ncap]
  87 }
  88
  89 // alloc allocates a new thread with the given instruction.
  90 // It uses the free pool if possible.
  91 func (m *machine) alloc(i *syntax.Inst) *thread {
  92         var t *thread
  93         if n := len(m.pool); n > 0 {
  94                 t = m.pool[n-1]
  95                 m.pool = m.pool[:n-1]
  96         } else {
  97                 t = new(thread)
  98                 t.cap = make([]int, len(m.matchcap), cap(m.matchcap))
  99         }
 100         t.inst = i
 101         return t
 102 }
 103
 104 // free returns t to the free pool.
 105 func (m *machine) free(t *thread) {
 106         m.inputBytes.str = nil
 107         m.inputString.str = ""
 108         m.inputReader.r = nil
 109         m.pool = append(m.pool, t)
 110 }
 111
 112 // match runs the machine over the input starting at pos.
 113 // It reports whether a match was found.
 114 // If so, m.matchcap holds the submatch information.
 115 func (m *machine) match(i input, pos int) bool {
 116         startCond := m.re.cond
 117         if startCond == ^syntax.EmptyOp(0) { // impossible
 118                 return false
 119         }
 120         m.matched = false
 121         for i := range m.matchcap {
 122                 m.matchcap[i] = -1
 123         }
 124         runq, nextq := &m.q0, &m.q1
 125         r, r1 := endOfText, endOfText
 126         width, width1 := 0, 0
 127         r, width = i.step(pos)
 128         if r != endOfText {
 129                 r1, width1 = i.step(pos + width)
 130         }
 131         var flag syntax.EmptyOp
 132         if pos == 0 {
 133                 flag = syntax.EmptyOpContext(-1, r)
 134         } else {
 135                 flag = i.context(pos)
 136         }
 137         for {
 138                 if len(runq.dense) == 0 {
 139                         if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
 140                                 // Anchored match, past beginning of text.
 141                                 break
 142                         }
 143                         if m.matched {
 144                                 // Have match; finished exploring alternatives.
 145                                 break
 146                         }
 147                         if len(m.re.prefix) > 0 && r1 != m.re.prefixRune && i.canCheckPrefix() {
 148                                 // Match requires literal prefix; fast search for it.
 149                                 advance := i.index(m.re, pos)
 150                                 if advance < 0 {
 151                                         break
 152                                 }
 153                                 pos += advance
 154                                 r, width = i.step(pos)
 155                                 r1, width1 = i.step(pos + width)
 156                         }
 157                 }
 158                 if !m.matched {
 159                         if len(m.matchcap) > 0 {
 160                                 m.matchcap[0] = pos
 161                         }
 162                         m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag, nil)
 163                 }
 164                 flag = syntax.EmptyOpContext(r, r1)
 165                 m.step(runq, nextq, pos, pos+width, r, flag)
 166                 if width == 0 {
 167                         break
 168                 }
 169                 if len(m.matchcap) == 0 && m.matched {
 170                         // Found a match and not paying attention
 171                         // to where it is, so any match will do.
 172                         break
 173                 }
 174                 pos += width
 175                 r, width = r1, width1
 176                 if r != endOfText {
 177                         r1, width1 = i.step(pos + width)
 178                 }
 179                 runq, nextq = nextq, runq
 180         }
 181         m.clear(nextq)
 182         return m.matched
 183 }
 184
 185 // clear frees all threads on the thread queue.
 186 func (m *machine) clear(q *queue) {
 187         for _, d := range q.dense {
 188                 if d.t != nil {
 189                         // m.free(d.t)
 190                         m.pool = append(m.pool, d.t)
 191                 }
 192         }
 193         q.dense = q.dense[:0]
 194 }
 195
 196 // step executes one step of the machine, running each of the threads
 197 // on runq and appending new threads to nextq.
 198 // The step processes the rune c (which may be endOfText),
 199 // which starts at position pos and ends at nextPos.
 200 // nextCond gives the setting for the empty-width flags after c.
 201 func (m *machine) step(runq, nextq *queue, pos, nextPos int, c rune, nextCond syntax.EmptyOp) {
 202         longest := m.re.longest
 203         for j := 0; j < len(runq.dense); j++ {
 204                 d := &runq.dense[j]
 205                 t := d.t
 206                 if t == nil {
 207                         continue
 208                 }
 209                 if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] {
 210                         // m.free(t)
 211                         m.pool = append(m.pool, t)
 212                         continue
 213                 }
 214                 i := t.inst
 215                 add := false
 216                 switch i.Op {
 217                 default:
 218                         panic("bad inst")
 219
 220                 case syntax.InstMatch:
 221                         if len(t.cap) > 0 && (!longest || !m.matched || m.matchcap[1] < pos) {
 222                                 t.cap[1] = pos
 223                                 copy(m.matchcap, t.cap)
 224                         }
 225                         if !longest {
 226                                 // First-match mode: cut off all lower-priority threads.
 227                                 for _, d := range runq.dense[j+1:] {
 228                                         if d.t != nil {
 229                                                 // m.free(d.t)
 230                                                 m.pool = append(m.pool, d.t)
 231                                         }
 232                                 }
 233                                 runq.dense = runq.dense[:0]
 234                         }
 235                         m.matched = true
 236
 237                 case syntax.InstRune:
 238                         add = i.MatchRune(c)
 239                 case syntax.InstRune1:
 240                         add = c == i.Rune[0]
 241                 case syntax.InstRuneAny:
 242                         add = true
 243                 case syntax.InstRuneAnyNotNL:
 244                         add = c != '\n'
 245                 }
 246                 if add {
 247                         t = m.add(nextq, i.Out, nextPos, t.cap, nextCond, t)
 248                 }
 249                 if t != nil {
 250                         // m.free(t)
 251                         m.pool = append(m.pool, t)
 252                 }
 253         }
 254         runq.dense = runq.dense[:0]
 255 }
 256
 257 // add adds an entry to q for pc, unless the q already has such an entry.
 258 // It also recursively adds an entry for all instructions reachable from pc by following
 259 // empty-width conditions satisfied by cond.  pos gives the current position
 260 // in the input.
 261 func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp, t *thread) *thread {
 262         if pc == 0 {
 263                 return t
 264         }
 265         if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc {
 266                 return t
 267         }
 268
 269         j := len(q.dense)
 270         q.dense = q.dense[:j+1]
 271         d := &q.dense[j]
 272         d.t = nil
 273         d.pc = pc
 274         q.sparse[pc] = uint32(j)
 275
 276         i := &m.p.Inst[pc]
 277         switch i.Op {
 278         default:
 279                 panic("unhandled")
 280         case syntax.InstFail:
 281                 // nothing
 282         case syntax.InstAlt, syntax.InstAltMatch:
 283                 t = m.add(q, i.Out, pos, cap, cond, t)
 284                 t = m.add(q, i.Arg, pos, cap, cond, t)
 285         case syntax.InstEmptyWidth:
 286                 if syntax.EmptyOp(i.Arg)&^cond == 0 {
 287                         t = m.add(q, i.Out, pos, cap, cond, t)
 288                 }
 289         case syntax.InstNop:
 290                 t = m.add(q, i.Out, pos, cap, cond, t)
 291         case syntax.InstCapture:
 292                 if int(i.Arg) < len(cap) {
 293                         opos := cap[i.Arg]
 294                         cap[i.Arg] = pos
 295                         m.add(q, i.Out, pos, cap, cond, nil)
 296                         cap[i.Arg] = opos
 297                 } else {
 298                         t = m.add(q, i.Out, pos, cap, cond, t)
 299                 }
 300         case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
 301                 if t == nil {
 302                         t = m.alloc(i)
 303                 } else {
 304                         t.inst = i
 305                 }
 306                 if len(cap) > 0 && &t.cap[0] != &cap[0] {
 307                         copy(t.cap, cap)
 308                 }
 309                 d.t = t
 310                 t = nil
 311         }
 312         return t
 313 }
 314
 315 // empty is a non-nil 0-element slice,
 316 // so doExecute can avoid an allocation
 317 // when 0 captures are requested from a successful match.
 318 var empty = make([]int, 0)
 319
 320 // doExecute finds the leftmost match in the input and returns
 321 // the position of its subexpressions.
 322 func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int) []int {
 323         m := re.get()
 324         var i input
 325         if r != nil {
 326                 i = m.newInputReader(r)
 327         } else if b != nil {
 328                 i = m.newInputBytes(b)
 329         } else {
 330                 i = m.newInputString(s)
 331         }
 332         m.init(ncap)
 333         if !m.match(i, pos) {
 334                 re.put(m)
 335                 return nil
 336         }
 337         if ncap == 0 {
 338                 re.put(m)
 339                 return empty // empty but not nil
 340         }
 341         cap := make([]int, ncap)
 342         copy(cap, m.matchcap)
 343         re.put(m)
 344         return cap
 345 }