Adding upstream version 1.20.14.upstream/1.20.14upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 554 insertions, 0 deletions

diff --git a/src/regexp/exec.go b/src/regexp/exec.go
new file mode 100644
index 0000000..3fc4b68
--- /dev/null
+++ b/src/regexp/exec.go
@@ -0,0 +1,554 @@
+// Copyright 2011 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 (
+	"io"
+	"regexp/syntax"
+	"sync"
+)
+
+// A queue is a 'sparse array' holding pending threads of execution.
+// See https://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
+type queue struct {
+	sparse []uint32
+	dense  []entry
+}
+
+// An entry is an entry on a queue.
+// It holds both the instruction pc and the actual thread.
+// Some queue entries are just place holders so that the machine
+// knows it has considered that pc. Such entries have t == nil.
+type entry struct {
+	pc uint32
+	t  *thread
+}
+
+// A thread is the state of a single path through the machine:
+// an instruction and a corresponding capture array.
+// See https://swtch.com/~rsc/regexp/regexp2.html
+type thread struct {
+	inst *syntax.Inst
+	cap  []int
+}
+
+// A machine holds all the state during an NFA simulation for p.
+type machine struct {
+	re       *Regexp      // corresponding Regexp
+	p        *syntax.Prog // compiled program
+	q0, q1   queue        // two queues for runq, nextq
+	pool     []*thread    // pool of available threads
+	matched  bool         // whether a match was found
+	matchcap []int        // capture information for the match
+
+	inputs inputs
+}
+
+type inputs struct {
+	// cached inputs, to avoid allocation
+	bytes  inputBytes
+	string inputString
+	reader inputReader
+}
+
+func (i *inputs) newBytes(b []byte) input {
+	i.bytes.str = b
+	return &i.bytes
+}
+
+func (i *inputs) newString(s string) input {
+	i.string.str = s
+	return &i.string
+}
+
+func (i *inputs) newReader(r io.RuneReader) input {
+	i.reader.r = r
+	i.reader.atEOT = false
+	i.reader.pos = 0
+	return &i.reader
+}
+
+func (i *inputs) clear() {
+	// We need to clear 1 of these.
+	// Avoid the expense of clearing the others (pointer write barrier).
+	if i.bytes.str != nil {
+		i.bytes.str = nil
+	} else if i.reader.r != nil {
+		i.reader.r = nil
+	} else {
+		i.string.str = ""
+	}
+}
+
+func (i *inputs) init(r io.RuneReader, b []byte, s string) (input, int) {
+	if r != nil {
+		return i.newReader(r), 0
+	}
+	if b != nil {
+		return i.newBytes(b), len(b)
+	}
+	return i.newString(s), len(s)
+}
+
+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 {
+	var t *thread
+	if n := len(m.pool); n > 0 {
+		t = m.pool[n-1]
+		m.pool = m.pool[:n-1]
+	} else {
+		t = new(thread)
+		t.cap = make([]int, len(m.matchcap), cap(m.matchcap))
+	}
+	t.inst = i
+	return t
+}
+
+// A lazyFlag is a lazily-evaluated syntax.EmptyOp,
+// for checking zero-width flags like ^ $ \A \z \B \b.
+// It records the pair of relevant runes and does not
+// determine the implied flags until absolutely necessary
+// (most of the time, that means never).
+type lazyFlag uint64
+
+func newLazyFlag(r1, r2 rune) lazyFlag {
+	return lazyFlag(uint64(r1)<<32 | uint64(uint32(r2)))
+}
+
+func (f lazyFlag) match(op syntax.EmptyOp) bool {
+	if op == 0 {
+		return true
+	}
+	r1 := rune(f >> 32)
+	if op&syntax.EmptyBeginLine != 0 {
+		if r1 != '\n' && r1 >= 0 {
+			return false
+		}
+		op &^= syntax.EmptyBeginLine
+	}
+	if op&syntax.EmptyBeginText != 0 {
+		if r1 >= 0 {
+			return false
+		}
+		op &^= syntax.EmptyBeginText
+	}
+	if op == 0 {
+		return true
+	}
+	r2 := rune(f)
+	if op&syntax.EmptyEndLine != 0 {
+		if r2 != '\n' && r2 >= 0 {
+			return false
+		}
+		op &^= syntax.EmptyEndLine
+	}
+	if op&syntax.EmptyEndText != 0 {
+		if r2 >= 0 {
+			return false
+		}
+		op &^= syntax.EmptyEndText
+	}
+	if op == 0 {
+		return true
+	}
+	if syntax.IsWordChar(r1) != syntax.IsWordChar(r2) {
+		op &^= syntax.EmptyWordBoundary
+	} else {
+		op &^= syntax.EmptyNoWordBoundary
+	}
+	return op == 0
+}
+
+// match runs the machine over the input starting at pos.
+// It reports whether a match was found.
+// If so, m.matchcap holds the submatch information.
+func (m *machine) match(i input, pos int) bool {
+	startCond := m.re.cond
+	if startCond == ^syntax.EmptyOp(0) { // impossible
+		return false
+	}
+	m.matched = false
+	for i := range m.matchcap {
+		m.matchcap[i] = -1
+	}
+	runq, nextq := &m.q0, &m.q1
+	r, r1 := endOfText, endOfText
+	width, width1 := 0, 0
+	r, width = i.step(pos)
+	if r != endOfText {
+		r1, width1 = i.step(pos + width)
+	}
+	var flag lazyFlag
+	if pos == 0 {
+		flag = newLazyFlag(-1, r)
+	} else {
+		flag = i.context(pos)
+	}
+	for {
+		if len(runq.dense) == 0 {
+			if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
+				// Anchored match, past beginning of text.
+				break
+			}
+			if m.matched {
+				// Have match; finished exploring alternatives.
+				break
+			}
+			if len(m.re.prefix) > 0 && r1 != m.re.prefixRune && i.canCheckPrefix() {
+				// Match requires literal prefix; fast search for it.
+				advance := i.index(m.re, pos)
+				if advance < 0 {
+					break
+				}
+				pos += advance
+				r, width = i.step(pos)
+				r1, width1 = i.step(pos + width)
+			}
+		}
+		if !m.matched {
+			if len(m.matchcap) > 0 {
+				m.matchcap[0] = pos
+			}
+			m.add(runq, uint32(m.p.Start), pos, m.matchcap, &flag, nil)
+		}
+		flag = newLazyFlag(r, r1)
+		m.step(runq, nextq, pos, pos+width, r, &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
+		r, width = r1, width1
+		if r != endOfText {
+			r1, width1 = i.step(pos + width)
+		}
+		runq, nextq = nextq, runq
+	}
+	m.clear(nextq)
+	return m.matched
+}
+
+// clear frees all threads on the thread queue.
+func (m *machine) clear(q *queue) {
+	for _, d := range q.dense {
+		if d.t != nil {
+			m.pool = append(m.pool, d.t)
+		}
+	}
+	q.dense = q.dense[:0]
+}
+
+// step executes one step of the machine, running each of the threads
+// on runq and appending new threads to nextq.
+// The step processes the rune c (which may be endOfText),
+// 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 int, c rune, nextCond *lazyFlag) {
+	longest := m.re.longest
+	for j := 0; j < len(runq.dense); j++ {
+		d := &runq.dense[j]
+		t := d.t
+		if t == nil {
+			continue
+		}
+		if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] {
+			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 && (!longest || !m.matched || m.matchcap[1] < pos) {
+				t.cap[1] = pos
+				copy(m.matchcap, t.cap)
+			}
+			if !longest {
+				// First-match mode: cut off all lower-priority threads.
+				for _, d := range runq.dense[j+1:] {
+					if d.t != nil {
+						m.pool = append(m.pool, d.t)
+					}
+				}
+				runq.dense = runq.dense[:0]
+			}
+			m.matched = true
+
+		case syntax.InstRune:
+			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.pool = append(m.pool, t)
+		}
+	}
+	runq.dense = runq.dense[:0]
+}
+
+// add adds an entry to q for pc, unless the q already has such an entry.
+// 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 *lazyFlag, t *thread) *thread {
+Again:
+	if pc == 0 {
+		return t
+	}
+	if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc {
+		return t
+	}
+
+	j := len(q.dense)
+	q.dense = q.dense[:j+1]
+	d := &q.dense[j]
+	d.t = nil
+	d.pc = pc
+	q.sparse[pc] = uint32(j)
+
+	i := &m.p.Inst[pc]
+	switch i.Op {
+	default:
+		panic("unhandled")
+	case syntax.InstFail:
+		// nothing
+	case syntax.InstAlt, syntax.InstAltMatch:
+		t = m.add(q, i.Out, pos, cap, cond, t)
+		pc = i.Arg
+		goto Again
+	case syntax.InstEmptyWidth:
+		if cond.match(syntax.EmptyOp(i.Arg)) {
+			pc = i.Out
+			goto Again
+		}
+	case syntax.InstNop:
+		pc = i.Out
+		goto Again
+	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, nil)
+			cap[i.Arg] = opos
+		} else {
+			pc = i.Out
+			goto Again
+		}
+	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
+}
+
+type onePassMachine struct {
+	inputs   inputs
+	matchcap []int
+}
+
+var onePassPool sync.Pool
+
+func newOnePassMachine() *onePassMachine {
+	m, ok := onePassPool.Get().(*onePassMachine)
+	if !ok {
+		m = new(onePassMachine)
+	}
+	return m
+}
+
+func freeOnePassMachine(m *onePassMachine) {
+	m.inputs.clear()
+	onePassPool.Put(m)
+}
+
+// doOnePass implements r.doExecute using the one-pass execution engine.
+func (re *Regexp) doOnePass(ir io.RuneReader, ib []byte, is string, pos, ncap int, dstCap []int) []int {
+	startCond := re.cond
+	if startCond == ^syntax.EmptyOp(0) { // impossible
+		return nil
+	}
+
+	m := newOnePassMachine()
+	if cap(m.matchcap) < ncap {
+		m.matchcap = make([]int, ncap)
+	} else {
+		m.matchcap = m.matchcap[:ncap]
+	}
+
+	matched := false
+	for i := range m.matchcap {
+		m.matchcap[i] = -1
+	}
+
+	i, _ := m.inputs.init(ir, ib, is)
+
+	r, r1 := endOfText, endOfText
+	width, width1 := 0, 0
+	r, width = i.step(pos)
+	if r != endOfText {
+		r1, width1 = i.step(pos + width)
+	}
+	var flag lazyFlag
+	if pos == 0 {
+		flag = newLazyFlag(-1, r)
+	} else {
+		flag = i.context(pos)
+	}
+	pc := re.onepass.Start
+	inst := &re.onepass.Inst[pc]
+	// If there is a simple literal prefix, skip over it.
+	if pos == 0 && flag.match(syntax.EmptyOp(inst.Arg)) &&
+		len(re.prefix) > 0 && i.canCheckPrefix() {
+		// Match requires literal prefix; fast search for it.
+		if !i.hasPrefix(re) {
+			goto Return
+		}
+		pos += len(re.prefix)
+		r, width = i.step(pos)
+		r1, width1 = i.step(pos + width)
+		flag = i.context(pos)
+		pc = int(re.prefixEnd)
+	}
+	for {
+		inst = &re.onepass.Inst[pc]
+		pc = int(inst.Out)
+		switch inst.Op {
+		default:
+			panic("bad inst")
+		case syntax.InstMatch:
+			matched = true
+			if len(m.matchcap) > 0 {
+				m.matchcap[0] = 0
+				m.matchcap[1] = pos
+			}
+			goto Return
+		case syntax.InstRune:
+			if !inst.MatchRune(r) {
+				goto Return
+			}
+		case syntax.InstRune1:
+			if r != inst.Rune[0] {
+				goto Return
+			}
+		case syntax.InstRuneAny:
+			// Nothing
+		case syntax.InstRuneAnyNotNL:
+			if r == '\n' {
+				goto Return
+			}
+		// peek at the input rune to see which branch of the Alt to take
+		case syntax.InstAlt, syntax.InstAltMatch:
+			pc = int(onePassNext(inst, r))
+			continue
+		case syntax.InstFail:
+			goto Return
+		case syntax.InstNop:
+			continue
+		case syntax.InstEmptyWidth:
+			if !flag.match(syntax.EmptyOp(inst.Arg)) {
+				goto Return
+			}
+			continue
+		case syntax.InstCapture:
+			if int(inst.Arg) < len(m.matchcap) {
+				m.matchcap[inst.Arg] = pos
+			}
+			continue
+		}
+		if width == 0 {
+			break
+		}
+		flag = newLazyFlag(r, r1)
+		pos += width
+		r, width = r1, width1
+		if r != endOfText {
+			r1, width1 = i.step(pos + width)
+		}
+	}
+
+Return:
+	if !matched {
+		freeOnePassMachine(m)
+		return nil
+	}
+
+	dstCap = append(dstCap, m.matchcap...)
+	freeOnePassMachine(m)
+	return dstCap
+}
+
+// doMatch reports whether either r, b or s match the regexp.
+func (re *Regexp) doMatch(r io.RuneReader, b []byte, s string) bool {
+	return re.doExecute(r, b, s, 0, 0, nil) != nil
+}
+
+// doExecute finds the leftmost match in the input, appends the position
+// of its subexpressions to dstCap and returns dstCap.
+//
+// nil is returned if no matches are found and non-nil if matches are found.
+func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int, dstCap []int) []int {
+	if dstCap == nil {
+		// Make sure 'return dstCap' is non-nil.
+		dstCap = arrayNoInts[:0:0]
+	}
+
+	if r == nil && len(b)+len(s) < re.minInputLen {
+		return nil
+	}
+
+	if re.onepass != nil {
+		return re.doOnePass(r, b, s, pos, ncap, dstCap)
+	}
+	if r == nil && len(b)+len(s) < re.maxBitStateLen {
+		return re.backtrack(b, s, pos, ncap, dstCap)
+	}
+
+	m := re.get()
+	i, _ := m.inputs.init(r, b, s)
+
+	m.init(ncap)
+	if !m.match(i, pos) {
+		re.put(m)
+		return nil
+	}
+
+	dstCap = append(dstCap, m.matchcap...)
+	re.put(m)
+	return dstCap
+}
+
+// arrayNoInts is returned by doExecute match if nil dstCap is passed
+// to it with ncap=0.
+var arrayNoInts [0]int