libgo/go/exp/regexp/exec.go

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