Source file src/pkg/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 }