// Copyright 2014 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package regexp
import (
"regexp/syntax"
"sort"
"strings"
"unicode"
)
// "One-pass" regexp execution.
// Some regexps can be analyzed to determine that they never need
// backtracking: they are guaranteed to run in one pass over the string
// without bothering to save all the usual NFA state.
// Detect those and execute them more quickly.
// A onePassProg is a compiled one-pass regular expression program.
// It is the same as syntax.Prog except for the use of onePassInst.
type onePassProg struct {
Inst []onePassInst
Start int // index of start instruction
NumCap int // number of InstCapture insts in re
}
// A onePassInst is a single instruction in a one-pass regular expression program.
// It is the same as syntax.Inst except for the new 'Next' field.
type onePassInst struct {
syntax.Inst
Next []uint32
}
// OnePassPrefix returns a literal string that all matches for the
// regexp must start with. Complete is true if the prefix
// is the entire match. Pc is the index of the last rune instruction
// in the string. The OnePassPrefix skips over the mandatory
// EmptyBeginText
func onePassPrefix(p *syntax.Prog) (prefix string, complete bool, pc uint32) {
i := &p.Inst[p.Start]
if i.Op != syntax.InstEmptyWidth || (syntax.EmptyOp(i.Arg))&syntax.EmptyBeginText == 0 {
return "", i.Op == syntax.InstMatch, uint32(p.Start)
}
pc = i.Out
i = &p.Inst[pc]
for i.Op == syntax.InstNop {
pc = i.Out
i = &p.Inst[pc]
}
// Avoid allocation of buffer if prefix is empty.
if iop(i) != syntax.InstRune || len(i.Rune) != 1 {
return "", i.Op == syntax.InstMatch, uint32(p.Start)
}
// Have prefix; gather characters.
var buf strings.Builder
for iop(i) == syntax.InstRune && len(i.Rune) == 1 && syntax.Flags(i.Arg)&syntax.FoldCase == 0 {
buf.WriteRune(i.Rune[0])
pc, i = i.Out, &p.Inst[i.Out]
}
if i.Op == syntax.InstEmptyWidth &&
syntax.EmptyOp(i.Arg)&syntax.EmptyEndText != 0 &&
p.Inst[i.Out].Op == syntax.InstMatch {
complete = true
}
return buf.String(), complete, pc
}
// OnePassNext selects the next actionable state of the prog, based on the input character.
// It should only be called when i.Op == InstAlt or InstAltMatch, and from the one-pass machine.
// One of the alternates may ultimately lead without input to end of line. If the instruction
// is InstAltMatch the path to the InstMatch is in i.Out, the normal node in i.Next.
func onePassNext(i *onePassInst, r rune) uint32 {
next := i.MatchRunePos(r)
if next >= 0 {
return i.Next[next]
}
if i.Op == syntax.InstAltMatch {
return i.Out
}
return 0
}
func iop(i *syntax.Inst) syntax.InstOp {
op := i.Op
switch op {
case syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
op = syntax.InstRune
}
return op
}
// Sparse Array implementation is used as a queueOnePass.
type queueOnePass struct {
sparse []uint32
dense []uint32
size, nextIndex uint32
}
func (q *queueOnePass) empty() bool {
return q.nextIndex >= q.size
}
func (q *queueOnePass) next() (n uint32) {
n = q.dense[q.nextIndex]
q.nextIndex++
return
}
func (q *queueOnePass) clear() {
q.size = 0
q.nextIndex = 0
}
func (q *queueOnePass) contains(u uint32) bool {
if u >= uint32(len(q.sparse)) {
return false
}
return q.sparse[u] < q.size && q.dense[q.sparse[u]] == u
}
func (q *queueOnePass) insert(u uint32) {
if !q.contains(u) {
q.insertNew(u)
}
}
func (q *queueOnePass) insertNew(u uint32) {
if u >= uint32(len(q.sparse)) {
return
}
q.sparse[u] = q.size
q.dense[q.size] = u
q.size++
}
func newQueue(size int) (q *queueOnePass) {
return &queueOnePass{
sparse: make([]uint32, size),
dense: make([]uint32, size),
}
}
// mergeRuneSets merges two non-intersecting runesets, and returns the merged result,
// and a NextIp array. The idea is that if a rune matches the OnePassRunes at index
// i, NextIp[i/2] is the target. If the input sets intersect, an empty runeset and a
// NextIp array with the single element mergeFailed is returned.
// The code assumes that both inputs contain ordered and non-intersecting rune pairs.
const mergeFailed = uint32(0xffffffff)
var (
noRune = []rune{}
noNext = []uint32{mergeFailed}
)
func mergeRuneSets(leftRunes, rightRunes *[]rune, leftPC, rightPC uint32) ([]rune, []uint32) {
leftLen := len(*leftRunes)
rightLen := len(*rightRunes)
if leftLen&0x1 != 0 || rightLen&0x1 != 0 {
panic("mergeRuneSets odd length []rune")
}
var (
lx, rx int
)
merged := make([]rune, 0)
next := make([]uint32, 0)
ok := true
defer func() {
if !ok {
merged = nil
next = nil
}
}()
ix := -1
extend := func(newLow *int, newArray *[]rune, pc uint32) bool {
if ix > 0 && (*newArray)[*newLow] <= merged[ix] {
return false
}
merged = append(merged, (*newArray)[*newLow], (*newArray)[*newLow+1])
*newLow += 2
ix += 2
next = append(next, pc)
return true
}
for lx < leftLen || rx < rightLen {
switch {
case rx >= rightLen:
ok = extend(&lx, leftRunes, leftPC)
case lx >= leftLen:
ok = extend(&rx, rightRunes, rightPC)
case (*rightRunes)[rx] < (*leftRunes)[lx]:
ok = extend(&rx, rightRunes, rightPC)
default:
ok = extend(&lx, leftRunes, leftPC)
}
if !ok {
return noRune, noNext
}
}
return merged, next
}
// cleanupOnePass drops working memory, and restores certain shortcut instructions.
func cleanupOnePass(prog *onePassProg, original *syntax.Prog) {
for ix, instOriginal := range original.Inst {
switch instOriginal.Op {
case syntax.InstAlt, syntax.InstAltMatch, syntax.InstRune:
case syntax.InstCapture, syntax.InstEmptyWidth, syntax.InstNop, syntax.InstMatch, syntax.InstFail:
prog.Inst[ix].Next = nil
case syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
prog.Inst[ix].Next = nil
prog.Inst[ix] = onePassInst{Inst: instOriginal}
}
}
}
// onePassCopy creates a copy of the original Prog, as we'll be modifying it
func onePassCopy(prog *syntax.Prog) *onePassProg {
p := &onePassProg{
Start: prog.Start,
NumCap: prog.NumCap,
Inst: make([]onePassInst, len(prog.Inst)),
}
for i, inst := range prog.Inst {
p.Inst[i] = onePassInst{Inst: inst}
}
// rewrites one or more common Prog constructs that enable some otherwise
// non-onepass Progs to be onepass. A:BD (for example) means an InstAlt at
// ip A, that points to ips B & C.
// A:BC + B:DA => A:BC + B:CD
// A:BC + B:DC => A:DC + B:DC
for pc := range p.Inst {
switch p.Inst[pc].Op {
default:
continue
case syntax.InstAlt, syntax.InstAltMatch:
// A:Bx + B:Ay
p_A_Other := &p.Inst[pc].Out
p_A_Alt := &p.Inst[pc].Arg
// make sure a target is another Alt
instAlt := p.Inst[*p_A_Alt]
if !(instAlt.Op == syntax.InstAlt || instAlt.Op == syntax.InstAltMatch) {
p_A_Alt, p_A_Other = p_A_Other, p_A_Alt
instAlt = p.Inst[*p_A_Alt]
if !(instAlt.Op == syntax.InstAlt || instAlt.Op == syntax.InstAltMatch) {
continue
}
}
instOther := p.Inst[*p_A_Other]
// Analyzing both legs pointing to Alts is for another day
if instOther.Op == syntax.InstAlt || instOther.Op == syntax.InstAltMatch {
// too complicated
continue
}
// simple empty transition loop
// A:BC + B:DA => A:BC + B:DC
p_B_Alt := &p.Inst[*p_A_Alt].Out
p_B_Other := &p.Inst[*p_A_Alt].Arg
patch := false
if instAlt.Out == uint32(pc) {
patch = true
} else if instAlt.Arg == uint32(pc) {
patch = true
p_B_Alt, p_B_Other = p_B_Other, p_B_Alt
}
if patch {
*p_B_Alt = *p_A_Other
}
// empty transition to common target
// A:BC + B:DC => A:DC + B:DC
if *p_A_Other == *p_B_Alt {
*p_A_Alt = *p_B_Other
}
}
}
return p
}
// runeSlice exists to permit sorting the case-folded rune sets.
type runeSlice []rune
func (p runeSlice) Len() int { return len(p) }
func (p runeSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p runeSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
var anyRuneNotNL = []rune{0, '\n' - 1, '\n' + 1, unicode.MaxRune}
var anyRune = []rune{0, unicode.MaxRune}
// makeOnePass creates a onepass Prog, if possible. It is possible if at any alt,
// the match engine can always tell which branch to take. The routine may modify
// p if it is turned into a onepass Prog. If it isn't possible for this to be a
// onepass Prog, the Prog nil is returned. makeOnePass is recursive
// to the size of the Prog.
func makeOnePass(p *onePassProg) *onePassProg {
// If the machine is very long, it's not worth the time to check if we can use one pass.
if len(p.Inst) >= 1000 {
return nil
}
var (
instQueue = newQueue(len(p.Inst))
visitQueue = newQueue(len(p.Inst))
check func(uint32, []bool) bool
onePassRunes = make([][]rune, len(p.Inst))
)
// check that paths from Alt instructions are unambiguous, and rebuild the new
// program as a onepass program
check = func(pc uint32, m []bool) (ok bool) {
ok = true
inst := &p.Inst[pc]
if visitQueue.contains(pc) {
return
}
visitQueue.insert(pc)
switch inst.Op {
case syntax.InstAlt, syntax.InstAltMatch:
ok = check(inst.Out, m) && check(inst.Arg, m)
// check no-input paths to InstMatch
matchOut := m[inst.Out]
matchArg := m[inst.Arg]
if matchOut && matchArg {
ok = false
break
}
// Match on empty goes in inst.Out
if matchArg {
inst.Out, inst.Arg = inst.Arg, inst.Out
matchOut, matchArg = matchArg, matchOut
}
if matchOut {
m[pc] = true
inst.Op = syntax.InstAltMatch
}
// build a dispatch operator from the two legs of the alt.
onePassRunes[pc], inst.Next = mergeRuneSets(
&onePassRunes[inst.Out], &onePassRunes[inst.Arg], inst.Out, inst.Arg)
if len(inst.Next) > 0 && inst.Next[0] == mergeFailed {
ok = false
break
}
case syntax.InstCapture, syntax.InstNop:
ok = check(inst.Out, m)
m[pc] = m[inst.Out]
// pass matching runes back through these no-ops.
onePassRunes[pc] = append([]rune{}, onePassRunes[inst.Out]...)
inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
for i := range inst.Next {
inst.Next[i] = inst.Out
}
case syntax.InstEmptyWidth:
ok = check(inst.Out, m)
m[pc] = m[inst.Out]
onePassRunes[pc] = append([]rune{}, onePassRunes[inst.Out]...)
inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
for i := range inst.Next {
inst.Next[i] = inst.Out
}
case syntax.InstMatch, syntax.InstFail:
m[pc] = inst.Op == syntax.InstMatch
case syntax.InstRune:
m[pc] = false
if len(inst.Next) > 0 {
break
}
instQueue.insert(inst.Out)
if len(inst.Rune) == 0 {
onePassRunes[pc] = []rune{}
inst.Next = []uint32{inst.Out}
break
}
runes := make([]rune, 0)
if len(inst.Rune) == 1 && syntax.Flags(inst.Arg)&syntax.FoldCase != 0 {
r0 := inst.Rune[0]
runes = append(runes, r0, r0)
for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) {
runes = append(runes, r1, r1)
}
sort.Sort(runeSlice(runes))
} else {
runes = append(runes, inst.Rune...)
}
onePassRunes[pc] = runes
inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
for i := range inst.Next {
inst.Next[i] = inst.Out
}
inst.Op = syntax.InstRune
case syntax.InstRune1:
m[pc] = false
if len(inst.Next) > 0 {
break
}
instQueue.insert(inst.Out)
runes := []rune{}
// expand case-folded runes
if syntax.Flags(inst.Arg)&syntax.FoldCase != 0 {
r0 := inst.Rune[0]
runes = append(runes, r0, r0)
for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) {
runes = append(runes, r1, r1)
}
sort.Sort(runeSlice(runes))
} else {
runes = append(runes, inst.Rune[0], inst.Rune[0])
}
onePassRunes[pc] = runes
inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
for i := range inst.Next {
inst.Next[i] = inst.Out
}
inst.Op = syntax.InstRune
case syntax.InstRuneAny:
m[pc] = false
if len(inst.Next) > 0 {
break
}
instQueue.insert(inst.Out)
onePassRunes[pc] = append([]rune{}, anyRune...)
inst.Next = []uint32{inst.Out}
case syntax.InstRuneAnyNotNL:
m[pc] = false
if len(inst.Next) > 0 {
break
}
instQueue.insert(inst.Out)
onePassRunes[pc] = append([]rune{}, anyRuneNotNL...)
inst.Next = make([]uint32, len(onePassRunes[pc])/2+1)
for i := range inst.Next {
inst.Next[i] = inst.Out
}
}
return
}
instQueue.clear()
instQueue.insert(uint32(p.Start))
m := make([]bool, len(p.Inst))
for !instQueue.empty() {
visitQueue.clear()
pc := instQueue.next()
if !check(pc, m) {
p = nil
break
}
}
if p != nil {
for i := range p.Inst {
p.Inst[i].Rune = onePassRunes[i]
}
}
return p
}
// compileOnePass returns a new *syntax.Prog suitable for onePass execution if the original Prog
// can be recharacterized as a one-pass regexp program, or syntax.nil if the
// Prog cannot be converted. For a one pass prog, the fundamental condition that must
// be true is: at any InstAlt, there must be no ambiguity about what branch to take.
func compileOnePass(prog *syntax.Prog) (p *onePassProg) {
if prog.Start == 0 {
return nil
}
// onepass regexp is anchored
if prog.Inst[prog.Start].Op != syntax.InstEmptyWidth ||
syntax.EmptyOp(prog.Inst[prog.Start].Arg)&syntax.EmptyBeginText != syntax.EmptyBeginText {
return nil
}
// every instruction leading to InstMatch must be EmptyEndText
for _, inst := range prog.Inst {
opOut := prog.Inst[inst.Out].Op
switch inst.Op {
default:
if opOut == syntax.InstMatch {
return nil
}
case syntax.InstAlt, syntax.InstAltMatch:
if opOut == syntax.InstMatch || prog.Inst[inst.Arg].Op == syntax.InstMatch {
return nil
}
case syntax.InstEmptyWidth:
if opOut == syntax.InstMatch {
if syntax.EmptyOp(inst.Arg)&syntax.EmptyEndText == syntax.EmptyEndText {
continue
}
return nil
}
}
}
// Creates a slightly optimized copy of the original Prog
// that cleans up some Prog idioms that block valid onepass programs
p = onePassCopy(prog)
// checkAmbiguity on InstAlts, build onepass Prog if possible
p = makeOnePass(p)
if p != nil {
cleanupOnePass(p, prog)
}
return p
}
|
