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.
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
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.
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
36 // A machine holds all the state during an NFA simulation for p.
38 re
*Regexp
// corresponding Regexp
39 p
*syntax
.Prog
// compiled program
40 op
*onePassProg
// compiled onepass program, or notOnePass
41 q0
, q1 queue
// two queues for runq, nextq
42 pool
[]*thread
// pool of available threads
43 matched
bool // whether a match was found
44 matchcap
[]int // capture information for the match
46 // cached inputs, to avoid allocation
48 inputString inputString
49 inputReader inputReader
52 func (m
*machine
) newInputBytes(b
[]byte) input
{
57 func (m
*machine
) newInputString(s
string) input
{
62 func (m
*machine
) newInputReader(r io
.RuneReader
) input
{
64 m
.inputReader
.atEOT
= false
69 // progMachine returns a new machine running the prog p.
70 func progMachine(p
*syntax
.Prog
, op
*onePassProg
) *machine
{
71 m
:= &machine
{p
: p
, op
: op
}
73 m
.q0
= queue
{make([]uint32, n
), make([]entry
, 0, n
)}
74 m
.q1
= queue
{make([]uint32, n
), make([]entry
, 0, n
)}
79 m
.matchcap
= make([]int, ncap
)
83 func (m
*machine
) init(ncap
int) {
84 for _
, t
:= range m
.pool
{
87 m
.matchcap
= m
.matchcap
[:ncap
]
90 // alloc allocates a new thread with the given instruction.
91 // It uses the free pool if possible.
92 func (m
*machine
) alloc(i
*syntax
.Inst
) *thread
{
94 if n
:= len(m
.pool
); n
> 0 {
99 t
.cap = make([]int, len(m
.matchcap
), cap(m
.matchcap
))
105 // free returns t to the free pool.
106 func (m
*machine
) free(t
*thread
) {
107 m
.inputBytes
.str
= nil
108 m
.inputString
.str
= ""
109 m
.inputReader
.r
= nil
110 m
.pool
= append(m
.pool
, t
)
113 // match runs the machine over the input starting at pos.
114 // It reports whether a match was found.
115 // If so, m.matchcap holds the submatch information.
116 func (m
*machine
) match(i input
, pos
int) bool {
117 startCond
:= m
.re
.cond
118 if startCond
== ^syntax
.EmptyOp(0) { // impossible
122 for i
:= range m
.matchcap
{
125 runq
, nextq
:= &m
.q0
, &m
.q1
126 r
, r1
:= endOfText
, endOfText
127 width
, width1
:= 0, 0
128 r
, width
= i
.step(pos
)
130 r1
, width1
= i
.step(pos
+ width
)
132 var flag syntax
.EmptyOp
134 flag
= syntax
.EmptyOpContext(-1, r
)
136 flag
= i
.context(pos
)
139 if len(runq
.dense
) == 0 {
140 if startCond
&syntax
.EmptyBeginText
!= 0 && pos
!= 0 {
141 // Anchored match, past beginning of text.
145 // Have match; finished exploring alternatives.
148 if len(m
.re
.prefix
) > 0 && r1
!= m
.re
.prefixRune
&& i
.canCheckPrefix() {
149 // Match requires literal prefix; fast search for it.
150 advance
:= i
.index(m
.re
, pos
)
155 r
, width
= i
.step(pos
)
156 r1
, width1
= i
.step(pos
+ width
)
160 if len(m
.matchcap
) > 0 {
163 m
.add(runq
, uint32(m
.p
.Start
), pos
, m
.matchcap
, flag
, nil)
165 flag
= syntax
.EmptyOpContext(r
, r1
)
166 m
.step(runq
, nextq
, pos
, pos
+width
, r
, flag
)
170 if len(m
.matchcap
) == 0 && m
.matched
{
171 // Found a match and not paying attention
172 // to where it is, so any match will do.
176 r
, width
= r1
, width1
178 r1
, width1
= i
.step(pos
+ width
)
180 runq
, nextq
= nextq
, runq
186 // clear frees all threads on the thread queue.
187 func (m
*machine
) clear(q
*queue
) {
188 for _
, d
:= range q
.dense
{
191 m
.pool
= append(m
.pool
, d
.t
)
194 q
.dense
= q
.dense
[:0]
197 // step executes one step of the machine, running each of the threads
198 // on runq and appending new threads to nextq.
199 // The step processes the rune c (which may be endOfText),
200 // which starts at position pos and ends at nextPos.
201 // nextCond gives the setting for the empty-width flags after c.
202 func (m
*machine
) step(runq
, nextq
*queue
, pos
, nextPos
int, c rune
, nextCond syntax
.EmptyOp
) {
203 longest
:= m
.re
.longest
204 for j
:= 0; j
< len(runq
.dense
); j
++ {
210 if longest
&& m
.matched
&& len(t
.cap) > 0 && m
.matchcap
[0] < t
.cap[0] {
212 m
.pool
= append(m
.pool
, t
)
221 case syntax
.InstMatch
:
222 if len(t
.cap) > 0 && (!longest ||
!m
.matched || m
.matchcap
[1] < pos
) {
224 copy(m
.matchcap
, t
.cap)
227 // First-match mode: cut off all lower-priority threads.
228 for _
, d
:= range runq
.dense
[j
+1:] {
231 m
.pool
= append(m
.pool
, d
.t
)
234 runq
.dense
= runq
.dense
[:0]
238 case syntax
.InstRune
:
240 case syntax
.InstRune1
:
242 case syntax
.InstRuneAny
:
244 case syntax
.InstRuneAnyNotNL
:
248 t
= m
.add(nextq
, i
.Out
, nextPos
, t
.cap, nextCond
, t
)
252 m
.pool
= append(m
.pool
, t
)
255 runq
.dense
= runq
.dense
[:0]
258 // add adds an entry to q for pc, unless the q already has such an entry.
259 // It also recursively adds an entry for all instructions reachable from pc by following
260 // empty-width conditions satisfied by cond. pos gives the current position
262 func (m
*machine
) add(q
*queue
, pc
uint32, pos
int, cap []int, cond syntax
.EmptyOp
, t
*thread
) *thread
{
266 if j
:= q
.sparse
[pc
]; j
< uint32(len(q
.dense
)) && q
.dense
[j
].pc
== pc
{
271 q
.dense
= q
.dense
[:j
+1]
275 q
.sparse
[pc
] = uint32(j
)
281 case syntax
.InstFail
:
283 case syntax
.InstAlt
, syntax
.InstAltMatch
:
284 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
285 t
= m
.add(q
, i
.Arg
, pos
, cap, cond
, t
)
286 case syntax
.InstEmptyWidth
:
287 if syntax
.EmptyOp(i
.Arg
)&^cond
== 0 {
288 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
291 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
292 case syntax
.InstCapture
:
293 if int(i
.Arg
) < len(cap) {
296 m
.add(q
, i
.Out
, pos
, cap, cond
, nil)
299 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
301 case syntax
.InstMatch
, syntax
.InstRune
, syntax
.InstRune1
, syntax
.InstRuneAny
, syntax
.InstRuneAnyNotNL
:
307 if len(cap) > 0 && &t
.cap[0] != &cap[0] {
316 // onepass runs the machine over the input starting at pos.
317 // It reports whether a match was found.
318 // If so, m.matchcap holds the submatch information.
319 func (m
*machine
) onepass(i input
, pos
int) bool {
320 startCond
:= m
.re
.cond
321 if startCond
== ^syntax
.EmptyOp(0) { // impossible
325 for i
:= range m
.matchcap
{
328 r
, r1
:= endOfText
, endOfText
329 width
, width1
:= 0, 0
330 r
, width
= i
.step(pos
)
332 r1
, width1
= i
.step(pos
+ width
)
334 var flag syntax
.EmptyOp
336 flag
= syntax
.EmptyOpContext(-1, r
)
338 flag
= i
.context(pos
)
341 inst
:= m
.op
.Inst
[pc
]
342 // If there is a simple literal prefix, skip over it.
343 if pos
== 0 && syntax
.EmptyOp(inst
.Arg
)&^flag
== 0 &&
344 len(m
.re
.prefix
) > 0 && i
.canCheckPrefix() {
345 // Match requires literal prefix; fast search for it.
346 if i
.hasPrefix(m
.re
) {
347 pos
+= len(m
.re
.prefix
)
348 r
, width
= i
.step(pos
)
349 r1
, width1
= i
.step(pos
+ width
)
350 flag
= i
.context(pos
)
351 pc
= int(m
.re
.prefixEnd
)
362 case syntax
.InstMatch
:
364 if len(m
.matchcap
) > 0 {
369 case syntax
.InstRune
:
370 if !inst
.MatchRune(r
) {
373 case syntax
.InstRune1
:
374 if r
!= inst
.Rune
[0] {
377 case syntax
.InstRuneAny
:
379 case syntax
.InstRuneAnyNotNL
:
383 // peek at the input rune to see which branch of the Alt to take
384 case syntax
.InstAlt
, syntax
.InstAltMatch
:
385 pc
= int(onePassNext(&inst
, r
))
387 case syntax
.InstFail
:
391 case syntax
.InstEmptyWidth
:
392 if syntax
.EmptyOp(inst
.Arg
)&^flag
!= 0 {
396 case syntax
.InstCapture
:
397 if int(inst
.Arg
) < len(m
.matchcap
) {
398 m
.matchcap
[inst
.Arg
] = pos
405 flag
= syntax
.EmptyOpContext(r
, r1
)
407 r
, width
= r1
, width1
409 r1
, width1
= i
.step(pos
+ width
)
415 // empty is a non-nil 0-element slice,
416 // so doExecute can avoid an allocation
417 // when 0 captures are requested from a successful match.
418 var empty
= make([]int, 0)
420 // doExecute finds the leftmost match in the input and returns
421 // the position of its subexpressions.
422 func (re
*Regexp
) doExecute(r io
.RuneReader
, b
[]byte, s
string, pos
int, ncap
int) []int {
426 i
= m
.newInputReader(r
)
428 i
= m
.newInputBytes(b
)
430 i
= m
.newInputString(s
)
432 if m
.op
!= notOnePass
{
433 if !m
.onepass(i
, pos
) {
439 if !m
.match(i
, pos
) {
446 return empty
// empty but not nil
448 cap := make([]int, len(m
.matchcap
))
449 copy(cap, m
.matchcap
)