libgo/go/regexp/exec.go

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