package regexp
-import "exp/regexp/syntax"
+import "regexp/syntax"
// A queue is a 'sparse array' holding pending threads of execution.
// See http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
return m
}
+func (m *machine) init(ncap int) {
+ for _, t := range m.pool {
+ t.cap = t.cap[:ncap]
+ }
+ m.matchcap = m.matchcap[:ncap]
+}
+
// alloc allocates a new thread with the given instruction.
// It uses the free pool if possible.
func (m *machine) alloc(i *syntax.Inst) *thread {
m.pool = m.pool[:n-1]
} else {
t = new(thread)
- t.cap = make([]int, cap(m.matchcap))
+ t.cap = make([]int, len(m.matchcap), cap(m.matchcap))
}
- t.cap = t.cap[:len(m.matchcap)]
t.inst = i
return t
}
if rune != endOfText {
rune1, width1 = i.step(pos + width)
}
- // TODO: Let caller specify the initial flag setting.
- // For now assume pos == 0 is beginning of text and
- // pos != 0 is not even beginning of line.
- // TODO: Word boundary.
var flag syntax.EmptyOp
if pos == 0 {
- flag = syntax.EmptyBeginText | syntax.EmptyBeginLine
- }
-
- // Update flag using lookahead rune.
- if rune1 == '\n' {
- flag |= syntax.EmptyEndLine
- }
- if rune1 == endOfText {
- flag |= syntax.EmptyEndText
+ flag = syntax.EmptyOpContext(-1, rune)
+ } else {
+ flag = i.context(pos)
}
-
for {
if len(runq.dense) == 0 {
if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
if len(m.matchcap) > 0 {
m.matchcap[0] = pos
}
- m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag)
- }
- // TODO: word boundary
- flag = 0
- if rune == '\n' {
- flag |= syntax.EmptyBeginLine
- }
- if rune1 == '\n' {
- flag |= syntax.EmptyEndLine
- }
- if rune1 == endOfText {
- flag |= syntax.EmptyEndText
+ m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag, nil)
}
+ flag = syntax.EmptyOpContext(rune, rune1)
m.step(runq, nextq, pos, pos+width, rune, flag)
if width == 0 {
break
}
+ if len(m.matchcap) == 0 && m.matched {
+ // Found a match and not paying attention
+ // to where it is, so any match will do.
+ break
+ }
pos += width
rune, width = rune1, width1
if rune != endOfText {
func (m *machine) clear(q *queue) {
for _, d := range q.dense {
if d.t != nil {
- m.free(d.t)
+ // m.free(d.t)
+ m.pool = append(m.pool, d.t)
}
}
q.dense = q.dense[:0]
// which starts at position pos and ends at nextPos.
// nextCond gives the setting for the empty-width flags after c.
func (m *machine) step(runq, nextq *queue, pos, nextPos, c int, nextCond syntax.EmptyOp) {
+ longest := m.re.longest
for j := 0; j < len(runq.dense); j++ {
d := &runq.dense[j]
t := d.t
if t == nil {
continue
}
- /*
- * If we support leftmost-longest matching:
- if longest && matched && match[0] < t.cap[0] {
- m.free(t)
- continue
- }
- */
-
+ if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] {
+ // m.free(t)
+ m.pool = append(m.pool, t)
+ continue
+ }
i := t.inst
+ add := false
switch i.Op {
default:
panic("bad inst")
case syntax.InstMatch:
- if len(t.cap) > 0 {
+ if len(t.cap) > 0 && (!longest || !m.matched || m.matchcap[1] < pos) {
t.cap[1] = pos
copy(m.matchcap, t.cap)
}
- m.matched = true
- for _, d := range runq.dense[j+1:] {
- if d.t != nil {
- m.free(d.t)
+ if !longest {
+ // First-match mode: cut off all lower-priority threads.
+ for _, d := range runq.dense[j+1:] {
+ if d.t != nil {
+ // m.free(d.t)
+ m.pool = append(m.pool, d.t)
+ }
}
+ runq.dense = runq.dense[:0]
}
- runq.dense = runq.dense[:0]
+ m.matched = true
case syntax.InstRune:
- if i.MatchRune(c) {
- m.add(nextq, i.Out, nextPos, t.cap, nextCond)
- }
+ add = i.MatchRune(c)
+ case syntax.InstRune1:
+ add = c == i.Rune[0]
+ case syntax.InstRuneAny:
+ add = true
+ case syntax.InstRuneAnyNotNL:
+ add = c != '\n'
+ }
+ if add {
+ t = m.add(nextq, i.Out, nextPos, t.cap, nextCond, t)
+ }
+ if t != nil {
+ // m.free(t)
+ m.pool = append(m.pool, t)
}
- m.free(t)
}
runq.dense = runq.dense[:0]
}
// It also recursively adds an entry for all instructions reachable from pc by following
// empty-width conditions satisfied by cond. pos gives the current position
// in the input.
-func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp) {
+func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp, t *thread) *thread {
if pc == 0 {
- return
+ return t
}
if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc {
- return
+ return t
}
j := len(q.dense)
case syntax.InstFail:
// nothing
case syntax.InstAlt, syntax.InstAltMatch:
- m.add(q, i.Out, pos, cap, cond)
- m.add(q, i.Arg, pos, cap, cond)
+ t = m.add(q, i.Out, pos, cap, cond, t)
+ t = m.add(q, i.Arg, pos, cap, cond, t)
case syntax.InstEmptyWidth:
if syntax.EmptyOp(i.Arg)&^cond == 0 {
- m.add(q, i.Out, pos, cap, cond)
+ t = m.add(q, i.Out, pos, cap, cond, t)
}
case syntax.InstNop:
- m.add(q, i.Out, pos, cap, cond)
+ t = m.add(q, i.Out, pos, cap, cond, t)
case syntax.InstCapture:
if int(i.Arg) < len(cap) {
opos := cap[i.Arg]
cap[i.Arg] = pos
- m.add(q, i.Out, pos, cap, cond)
+ m.add(q, i.Out, pos, cap, cond, nil)
cap[i.Arg] = opos
} else {
- m.add(q, i.Out, pos, cap, cond)
+ t = m.add(q, i.Out, pos, cap, cond, t)
}
- case syntax.InstMatch, syntax.InstRune:
- t := m.alloc(i)
- if len(t.cap) > 0 {
+ case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
+ if t == nil {
+ t = m.alloc(i)
+ } else {
+ t.inst = i
+ }
+ if len(cap) > 0 && &t.cap[0] != &cap[0] {
copy(t.cap, cap)
}
d.t = t
+ t = nil
}
+ return t
}
// empty is a non-nil 0-element slice,
// the position of its subexpressions.
func (re *Regexp) doExecute(i input, pos int, ncap int) []int {
m := re.get()
- m.matchcap = m.matchcap[:ncap]
+ m.init(ncap)
if !m.match(i, pos) {
re.put(m)
return nil
OSDN Git Service
