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 // An 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 maxBitStateLen
int // max length of string to search with bitstate
42 b
*bitState
// state for backtracker, allocated lazily
43 q0
, q1 queue
// two queues for runq, nextq
44 pool
[]*thread
// pool of available threads
45 matched
bool // whether a match was found
46 matchcap
[]int // capture information for the match
48 // cached inputs, to avoid allocation
50 inputString inputString
51 inputReader inputReader
54 func (m
*machine
) newInputBytes(b
[]byte) input
{
59 func (m
*machine
) newInputString(s
string) input
{
64 func (m
*machine
) newInputReader(r io
.RuneReader
) input
{
66 m
.inputReader
.atEOT
= false
71 // progMachine returns a new machine running the prog p.
72 func progMachine(p
*syntax
.Prog
, op
*onePassProg
) *machine
{
73 m
:= &machine
{p
: p
, op
: op
}
75 m
.q0
= queue
{make([]uint32, n
), make([]entry
, 0, n
)}
76 m
.q1
= queue
{make([]uint32, n
), make([]entry
, 0, n
)}
82 m
.maxBitStateLen
= maxBitStateLen(p
)
84 m
.matchcap
= make([]int, ncap
)
88 func (m
*machine
) init(ncap
int) {
89 for _
, t
:= range m
.pool
{
92 m
.matchcap
= m
.matchcap
[:ncap
]
95 // alloc allocates a new thread with the given instruction.
96 // It uses the free pool if possible.
97 func (m
*machine
) alloc(i
*syntax
.Inst
) *thread
{
99 if n
:= len(m
.pool
); n
> 0 {
101 m
.pool
= m
.pool
[:n
-1]
104 t
.cap = make([]int, len(m
.matchcap
), cap(m
.matchcap
))
110 // match runs the machine over the input starting at pos.
111 // It reports whether a match was found.
112 // If so, m.matchcap holds the submatch information.
113 func (m
*machine
) match(i input
, pos
int) bool {
114 startCond
:= m
.re
.cond
115 if startCond
== ^syntax
.EmptyOp(0) { // impossible
119 for i
:= range m
.matchcap
{
122 runq
, nextq
:= &m
.q0
, &m
.q1
123 r
, r1
:= endOfText
, endOfText
124 width
, width1
:= 0, 0
125 r
, width
= i
.step(pos
)
127 r1
, width1
= i
.step(pos
+ width
)
129 var flag syntax
.EmptyOp
131 flag
= syntax
.EmptyOpContext(-1, r
)
133 flag
= i
.context(pos
)
136 if len(runq
.dense
) == 0 {
137 if startCond
&syntax
.EmptyBeginText
!= 0 && pos
!= 0 {
138 // Anchored match, past beginning of text.
142 // Have match; finished exploring alternatives.
145 if len(m
.re
.prefix
) > 0 && r1
!= m
.re
.prefixRune
&& i
.canCheckPrefix() {
146 // Match requires literal prefix; fast search for it.
147 advance
:= i
.index(m
.re
, pos
)
152 r
, width
= i
.step(pos
)
153 r1
, width1
= i
.step(pos
+ width
)
157 if len(m
.matchcap
) > 0 {
160 m
.add(runq
, uint32(m
.p
.Start
), pos
, m
.matchcap
, flag
, nil)
162 flag
= syntax
.EmptyOpContext(r
, r1
)
163 m
.step(runq
, nextq
, pos
, pos
+width
, r
, flag
)
167 if len(m
.matchcap
) == 0 && m
.matched
{
168 // Found a match and not paying attention
169 // to where it is, so any match will do.
173 r
, width
= r1
, width1
175 r1
, width1
= i
.step(pos
+ width
)
177 runq
, nextq
= nextq
, runq
183 // clear frees all threads on the thread queue.
184 func (m
*machine
) clear(q
*queue
) {
185 for _
, d
:= range q
.dense
{
187 m
.pool
= append(m
.pool
, d
.t
)
190 q
.dense
= q
.dense
[:0]
193 // step executes one step of the machine, running each of the threads
194 // on runq and appending new threads to nextq.
195 // The step processes the rune c (which may be endOfText),
196 // which starts at position pos and ends at nextPos.
197 // nextCond gives the setting for the empty-width flags after c.
198 func (m
*machine
) step(runq
, nextq
*queue
, pos
, nextPos
int, c rune
, nextCond syntax
.EmptyOp
) {
199 longest
:= m
.re
.longest
200 for j
:= 0; j
< len(runq
.dense
); j
++ {
206 if longest
&& m
.matched
&& len(t
.cap) > 0 && m
.matchcap
[0] < t
.cap[0] {
207 m
.pool
= append(m
.pool
, t
)
216 case syntax
.InstMatch
:
217 if len(t
.cap) > 0 && (!longest ||
!m
.matched || m
.matchcap
[1] < pos
) {
219 copy(m
.matchcap
, t
.cap)
222 // First-match mode: cut off all lower-priority threads.
223 for _
, d
:= range runq
.dense
[j
+1:] {
225 m
.pool
= append(m
.pool
, d
.t
)
228 runq
.dense
= runq
.dense
[:0]
232 case syntax
.InstRune
:
234 case syntax
.InstRune1
:
236 case syntax
.InstRuneAny
:
238 case syntax
.InstRuneAnyNotNL
:
242 t
= m
.add(nextq
, i
.Out
, nextPos
, t
.cap, nextCond
, t
)
245 m
.pool
= append(m
.pool
, t
)
248 runq
.dense
= runq
.dense
[:0]
251 // add adds an entry to q for pc, unless the q already has such an entry.
252 // It also recursively adds an entry for all instructions reachable from pc by following
253 // empty-width conditions satisfied by cond. pos gives the current position
255 func (m
*machine
) add(q
*queue
, pc
uint32, pos
int, cap []int, cond syntax
.EmptyOp
, t
*thread
) *thread
{
259 if j
:= q
.sparse
[pc
]; j
< uint32(len(q
.dense
)) && q
.dense
[j
].pc
== pc
{
264 q
.dense
= q
.dense
[:j
+1]
268 q
.sparse
[pc
] = uint32(j
)
274 case syntax
.InstFail
:
276 case syntax
.InstAlt
, syntax
.InstAltMatch
:
277 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
278 t
= m
.add(q
, i
.Arg
, pos
, cap, cond
, t
)
279 case syntax
.InstEmptyWidth
:
280 if syntax
.EmptyOp(i
.Arg
)&^cond
== 0 {
281 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
284 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
285 case syntax
.InstCapture
:
286 if int(i
.Arg
) < len(cap) {
289 m
.add(q
, i
.Out
, pos
, cap, cond
, nil)
292 t
= m
.add(q
, i
.Out
, pos
, cap, cond
, t
)
294 case syntax
.InstMatch
, syntax
.InstRune
, syntax
.InstRune1
, syntax
.InstRuneAny
, syntax
.InstRuneAnyNotNL
:
300 if len(cap) > 0 && &t
.cap[0] != &cap[0] {
309 // onepass runs the machine over the input starting at pos.
310 // It reports whether a match was found.
311 // If so, m.matchcap holds the submatch information.
312 // ncap is the number of captures.
313 func (m
*machine
) onepass(i input
, pos
, ncap
int) bool {
314 startCond
:= m
.re
.cond
315 if startCond
== ^syntax
.EmptyOp(0) { // impossible
319 m
.matchcap
= m
.matchcap
[:ncap
]
320 for i
:= range m
.matchcap
{
323 r
, r1
:= endOfText
, endOfText
324 width
, width1
:= 0, 0
325 r
, width
= i
.step(pos
)
327 r1
, width1
= i
.step(pos
+ width
)
329 var flag syntax
.EmptyOp
331 flag
= syntax
.EmptyOpContext(-1, r
)
333 flag
= i
.context(pos
)
336 inst
:= m
.op
.Inst
[pc
]
337 // If there is a simple literal prefix, skip over it.
338 if pos
== 0 && syntax
.EmptyOp(inst
.Arg
)&^flag
== 0 &&
339 len(m
.re
.prefix
) > 0 && i
.canCheckPrefix() {
340 // Match requires literal prefix; fast search for it.
341 if !i
.hasPrefix(m
.re
) {
344 pos
+= len(m
.re
.prefix
)
345 r
, width
= i
.step(pos
)
346 r1
, width1
= i
.step(pos
+ width
)
347 flag
= i
.context(pos
)
348 pc
= int(m
.re
.prefixEnd
)
356 case syntax
.InstMatch
:
358 if len(m
.matchcap
) > 0 {
363 case syntax
.InstRune
:
364 if !inst
.MatchRune(r
) {
367 case syntax
.InstRune1
:
368 if r
!= inst
.Rune
[0] {
371 case syntax
.InstRuneAny
:
373 case syntax
.InstRuneAnyNotNL
:
377 // peek at the input rune to see which branch of the Alt to take
378 case syntax
.InstAlt
, syntax
.InstAltMatch
:
379 pc
= int(onePassNext(&inst
, r
))
381 case syntax
.InstFail
:
385 case syntax
.InstEmptyWidth
:
386 if syntax
.EmptyOp(inst
.Arg
)&^flag
!= 0 {
390 case syntax
.InstCapture
:
391 if int(inst
.Arg
) < len(m
.matchcap
) {
392 m
.matchcap
[inst
.Arg
] = pos
399 flag
= syntax
.EmptyOpContext(r
, r1
)
401 r
, width
= r1
, width1
403 r1
, width1
= i
.step(pos
+ width
)
409 // doMatch reports whether either r, b or s match the regexp.
410 func (re
*Regexp
) doMatch(r io
.RuneReader
, b
[]byte, s
string) bool {
411 return re
.doExecute(r
, b
, s
, 0, 0, nil) != nil
414 // doExecute finds the leftmost match in the input, appends the position
415 // of its subexpressions to dstCap and returns dstCap.
417 // nil is returned if no matches are found and non-nil if matches are found.
418 func (re
*Regexp
) doExecute(r io
.RuneReader
, b
[]byte, s
string, pos
int, ncap
int, dstCap
[]int) []int {
423 i
= m
.newInputReader(r
)
425 i
= m
.newInputBytes(b
)
428 i
= m
.newInputString(s
)
431 if m
.op
!= notOnePass
{
432 if !m
.onepass(i
, pos
, ncap
) {
436 } else if size
< m
.maxBitStateLen
&& r
== nil {
438 m
.b
= newBitState(m
.p
)
440 if !m
.backtrack(i
, pos
, size
, ncap
) {
446 if !m
.match(i
, pos
) {
451 dstCap
= append(dstCap
, m
.matchcap
...)
453 // Keep the promise of returning non-nil value on match.
454 dstCap
= arrayNoInts
[:0]
460 // arrayNoInts is returned by doExecute match if nil dstCap is passed
461 // to it with ncap=0.
462 var arrayNoInts
[0]int