gcc-7.1.0gcc-7.1.0

1 files changed, 0 insertions, 1488 deletions

diff --git a/libgo/go/old/regexp/regexp.go b/libgo/go/old/regexp/regexp.go
deleted file mode 100644
index d3044d0c1d..0000000000
--- a/libgo/go/old/regexp/regexp.go
+++ /dev/null
@@ -1,1488 +0,0 @@
-// Copyright 2010 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 implements a simple regular expression library.
-//
-// The syntax of the regular expressions accepted is:
-//
-//	regexp:
-//		concatenation { '|' concatenation }
-//	concatenation:
-//		{ closure }
-//	closure:
-//		term [ '*' | '+' | '?' ]
-//	term:
-//		'^'
-//		'$'
-//		'.'
-//		character
-//		'[' [ '^' ] { character-range } ']'
-//		'(' regexp ')'
-//	character-range:
-//		character [ '-' character ]
-//
-// All characters are UTF-8-encoded code points.  Backslashes escape special
-// characters, including inside character classes.  The standard Go character
-// escapes are also recognized: \a \b \f \n \r \t \v.
-//
-// There are 16 methods of Regexp that match a regular expression and identify
-// the matched text.  Their names are matched by this regular expression:
-//
-//	Find(All)?(String)?(Submatch)?(Index)?
-//
-// If 'All' is present, the routine matches successive non-overlapping
-// matches of the entire expression.  Empty matches abutting a preceding
-// match are ignored.  The return value is a slice containing the successive
-// return values of the corresponding non-'All' routine.  These routines take
-// an extra integer argument, n; if n >= 0, the function returns at most n
-// matches/submatches.
-//
-// If 'String' is present, the argument is a string; otherwise it is a slice
-// of bytes; return values are adjusted as appropriate.
-//
-// If 'Submatch' is present, the return value is a slice identifying the
-// successive submatches of the expression.  Submatches are matches of
-// parenthesized subexpressions within the regular expression, numbered from
-// left to right in order of opening parenthesis.  Submatch 0 is the match of
-// the entire expression, submatch 1 the match of the first parenthesized
-// subexpression, and so on.
-//
-// If 'Index' is present, matches and submatches are identified by byte index
-// pairs within the input string: result[2*n:2*n+1] identifies the indexes of
-// the nth submatch.  The pair for n==0 identifies the match of the entire
-// expression.  If 'Index' is not present, the match is identified by the
-// text of the match/submatch.  If an index is negative, it means that
-// subexpression did not match any string in the input.
-//
-// There is also a subset of the methods that can be applied to text read
-// from a RuneReader:
-//
-//	MatchReader, FindReaderIndex, FindReaderSubmatchIndex
-//
-// This set may grow.  Note that regular expression matches may need to
-// examine text beyond the text returned by a match, so the methods that
-// match text from a RuneReader may read arbitrarily far into the input
-// before returning.
-//
-// (There are a few other methods that do not match this pattern.)
-//
-package regexp
-
-import (
-	"bytes"
-	"io"
-	"strings"
-	"unicode/utf8"
-)
-
-var debug = false
-
-// Error is the local type for a parsing error.
-type Error string
-
-func (e Error) Error() string {
-	return string(e)
-}
-
-// Error codes returned by failures to parse an expression.
-var (
-	ErrInternal            = Error("regexp: internal error")
-	ErrUnmatchedLpar       = Error("regexp: unmatched '('")
-	ErrUnmatchedRpar       = Error("regexp: unmatched ')'")
-	ErrUnmatchedLbkt       = Error("regexp: unmatched '['")
-	ErrUnmatchedRbkt       = Error("regexp: unmatched ']'")
-	ErrBadRange            = Error("regexp: bad range in character class")
-	ErrExtraneousBackslash = Error("regexp: extraneous backslash")
-	ErrBadClosure          = Error("regexp: repeated closure (**, ++, etc.)")
-	ErrBareClosure         = Error("regexp: closure applies to nothing")
-	ErrBadBackslash        = Error("regexp: illegal backslash escape")
-)
-
-const (
-	iStart     = iota // beginning of program
-	iEnd              // end of program: success
-	iBOT              // '^' beginning of text
-	iEOT              // '$' end of text
-	iChar             // 'a' regular character
-	iCharClass        // [a-z] character class
-	iAny              // '.' any character including newline
-	iNotNL            // [^\n] special case: any character but newline
-	iBra              // '(' parenthesized expression: 2*braNum for left, 2*braNum+1 for right
-	iAlt              // '|' alternation
-	iNop              // do nothing; makes it easy to link without patching
-)
-
-// An instruction executed by the NFA
-type instr struct {
-	kind  int    // the type of this instruction: iChar, iAny, etc.
-	index int    // used only in debugging; could be eliminated
-	next  *instr // the instruction to execute after this one
-	// Special fields valid only for some items.
-	char   rune       // iChar
-	braNum int        // iBra, iEbra
-	cclass *charClass // iCharClass
-	left   *instr     // iAlt, other branch
-}
-
-func (i *instr) print() {
-	switch i.kind {
-	case iStart:
-		print("start")
-	case iEnd:
-		print("end")
-	case iBOT:
-		print("bot")
-	case iEOT:
-		print("eot")
-	case iChar:
-		print("char ", string(i.char))
-	case iCharClass:
-		i.cclass.print()
-	case iAny:
-		print("any")
-	case iNotNL:
-		print("notnl")
-	case iBra:
-		if i.braNum&1 == 0 {
-			print("bra", i.braNum/2)
-		} else {
-			print("ebra", i.braNum/2)
-		}
-	case iAlt:
-		print("alt(", i.left.index, ")")
-	case iNop:
-		print("nop")
-	}
-}
-
-// Regexp is the representation of a compiled regular expression.
-// The public interface is entirely through methods.
-// A Regexp is safe for concurrent use by multiple goroutines.
-type Regexp struct {
-	expr        string // the original expression
-	prefix      string // initial plain text string
-	prefixBytes []byte // initial plain text bytes
-	inst        []*instr
-	start       *instr // first instruction of machine
-	prefixStart *instr // where to start if there is a prefix
-	nbra        int    // number of brackets in expression, for subexpressions
-}
-
-type charClass struct {
-	negate bool // is character class negated? ([^a-z])
-	// slice of int, stored pairwise: [a-z] is (a,z); x is (x,x):
-	ranges     []rune
-	cmin, cmax rune
-}
-
-func (cclass *charClass) print() {
-	print("charclass")
-	if cclass.negate {
-		print(" (negated)")
-	}
-	for i := 0; i < len(cclass.ranges); i += 2 {
-		l := cclass.ranges[i]
-		r := cclass.ranges[i+1]
-		if l == r {
-			print(" [", string(l), "]")
-		} else {
-			print(" [", string(l), "-", string(r), "]")
-		}
-	}
-}
-
-func (cclass *charClass) addRange(a, b rune) {
-	// range is a through b inclusive
-	cclass.ranges = append(cclass.ranges, a, b)
-	if a < cclass.cmin {
-		cclass.cmin = a
-	}
-	if b > cclass.cmax {
-		cclass.cmax = b
-	}
-}
-
-func (cclass *charClass) matches(c rune) bool {
-	if c < cclass.cmin || c > cclass.cmax {
-		return cclass.negate
-	}
-	ranges := cclass.ranges
-	for i := 0; i < len(ranges); i = i + 2 {
-		if ranges[i] <= c && c <= ranges[i+1] {
-			return !cclass.negate
-		}
-	}
-	return cclass.negate
-}
-
-func newCharClass() *instr {
-	i := &instr{kind: iCharClass}
-	i.cclass = new(charClass)
-	i.cclass.ranges = make([]rune, 0, 4)
-	i.cclass.cmin = 0x10FFFF + 1 // MaxRune + 1
-	i.cclass.cmax = -1
-	return i
-}
-
-func (re *Regexp) add(i *instr) *instr {
-	i.index = len(re.inst)
-	re.inst = append(re.inst, i)
-	return i
-}
-
-type parser struct {
-	re    *Regexp
-	nlpar int // number of unclosed lpars
-	pos   int
-	ch    rune
-}
-
-func (p *parser) error(err Error) {
-	panic(err)
-}
-
-const endOfText = -1
-
-func (p *parser) c() rune { return p.ch }
-
-func (p *parser) nextc() rune {
-	if p.pos >= len(p.re.expr) {
-		p.ch = endOfText
-	} else {
-		c, w := utf8.DecodeRuneInString(p.re.expr[p.pos:])
-		p.ch = c
-		p.pos += w
-	}
-	return p.ch
-}
-
-func newParser(re *Regexp) *parser {
-	p := new(parser)
-	p.re = re
-	p.nextc() // load p.ch
-	return p
-}
-
-func special(c rune) bool {
-	for _, r := range `\.+*?()|[]^$` {
-		if c == r {
-			return true
-		}
-	}
-	return false
-}
-
-func ispunct(c rune) bool {
-	for _, r := range "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~" {
-		if c == r {
-			return true
-		}
-	}
-	return false
-}
-
-var escapes = []byte("abfnrtv")
-var escaped = []byte("\a\b\f\n\r\t\v")
-
-func escape(c rune) int {
-	for i, b := range escapes {
-		if rune(b) == c {
-			return i
-		}
-	}
-	return -1
-}
-
-func (p *parser) checkBackslash() rune {
-	c := p.c()
-	if c == '\\' {
-		c = p.nextc()
-		switch {
-		case c == endOfText:
-			p.error(ErrExtraneousBackslash)
-		case ispunct(c):
-			// c is as delivered
-		case escape(c) >= 0:
-			c = rune(escaped[escape(c)])
-		default:
-			p.error(ErrBadBackslash)
-		}
-	}
-	return c
-}
-
-func (p *parser) charClass() *instr {
-	i := newCharClass()
-	cc := i.cclass
-	if p.c() == '^' {
-		cc.negate = true
-		p.nextc()
-	}
-	left := rune(-1)
-	for {
-		switch c := p.c(); c {
-		case ']', endOfText:
-			if left >= 0 {
-				p.error(ErrBadRange)
-			}
-			// Is it [^\n]?
-			if cc.negate && len(cc.ranges) == 2 &&
-				cc.ranges[0] == '\n' && cc.ranges[1] == '\n' {
-				nl := &instr{kind: iNotNL}
-				p.re.add(nl)
-				return nl
-			}
-			// Special common case: "[a]" -> "a"
-			if !cc.negate && len(cc.ranges) == 2 && cc.ranges[0] == cc.ranges[1] {
-				c := &instr{kind: iChar, char: cc.ranges[0]}
-				p.re.add(c)
-				return c
-			}
-			p.re.add(i)
-			return i
-		case '-': // do this before backslash processing
-			p.error(ErrBadRange)
-		default:
-			c = p.checkBackslash()
-			p.nextc()
-			switch {
-			case left < 0: // first of pair
-				if p.c() == '-' { // range
-					p.nextc()
-					left = c
-				} else { // single char
-					cc.addRange(c, c)
-				}
-			case left <= c: // second of pair
-				cc.addRange(left, c)
-				left = -1
-			default:
-				p.error(ErrBadRange)
-			}
-		}
-	}
-	panic("unreachable")
-}
-
-func (p *parser) term() (start, end *instr) {
-	switch c := p.c(); c {
-	case '|', endOfText:
-		return nil, nil
-	case '*', '+', '?':
-		p.error(ErrBareClosure)
-	case ')':
-		if p.nlpar == 0 {
-			p.error(ErrUnmatchedRpar)
-		}
-		return nil, nil
-	case ']':
-		p.error(ErrUnmatchedRbkt)
-	case '^':
-		p.nextc()
-		start = p.re.add(&instr{kind: iBOT})
-		return start, start
-	case '$':
-		p.nextc()
-		start = p.re.add(&instr{kind: iEOT})
-		return start, start
-	case '.':
-		p.nextc()
-		start = p.re.add(&instr{kind: iAny})
-		return start, start
-	case '[':
-		p.nextc()
-		start = p.charClass()
-		if p.c() != ']' {
-			p.error(ErrUnmatchedLbkt)
-		}
-		p.nextc()
-		return start, start
-	case '(':
-		p.nextc()
-		p.nlpar++
-		p.re.nbra++ // increment first so first subexpr is \1
-		nbra := p.re.nbra
-		start, end = p.regexp()
-		if p.c() != ')' {
-			p.error(ErrUnmatchedLpar)
-		}
-		p.nlpar--
-		p.nextc()
-		bra := &instr{kind: iBra, braNum: 2 * nbra}
-		p.re.add(bra)
-		ebra := &instr{kind: iBra, braNum: 2*nbra + 1}
-		p.re.add(ebra)
-		if start == nil {
-			if end == nil {
-				p.error(ErrInternal)
-				return
-			}
-			start = ebra
-		} else {
-			end.next = ebra
-		}
-		bra.next = start
-		return bra, ebra
-	default:
-		c = p.checkBackslash()
-		p.nextc()
-		start = &instr{kind: iChar, char: c}
-		p.re.add(start)
-		return start, start
-	}
-	panic("unreachable")
-}
-
-func (p *parser) closure() (start, end *instr) {
-	start, end = p.term()
-	if start == nil {
-		return
-	}
-	switch p.c() {
-	case '*':
-		// (start,end)*:
-		alt := &instr{kind: iAlt}
-		p.re.add(alt)
-		end.next = alt   // after end, do alt
-		alt.left = start // alternate brach: return to start
-		start = alt      // alt becomes new (start, end)
-		end = alt
-	case '+':
-		// (start,end)+:
-		alt := &instr{kind: iAlt}
-		p.re.add(alt)
-		end.next = alt   // after end, do alt
-		alt.left = start // alternate brach: return to start
-		end = alt        // start is unchanged; end is alt
-	case '?':
-		// (start,end)?:
-		alt := &instr{kind: iAlt}
-		p.re.add(alt)
-		nop := &instr{kind: iNop}
-		p.re.add(nop)
-		alt.left = start // alternate branch is start
-		alt.next = nop   // follow on to nop
-		end.next = nop   // after end, go to nop
-		start = alt      // start is now alt
-		end = nop        // end is nop pointed to by both branches
-	default:
-		return
-	}
-	switch p.nextc() {
-	case '*', '+', '?':
-		p.error(ErrBadClosure)
-	}
-	return
-}
-
-func (p *parser) concatenation() (start, end *instr) {
-	for {
-		nstart, nend := p.closure()
-		switch {
-		case nstart == nil: // end of this concatenation
-			if start == nil { // this is the empty string
-				nop := p.re.add(&instr{kind: iNop})
-				return nop, nop
-			}
-			return
-		case start == nil: // this is first element of concatenation
-			start, end = nstart, nend
-		default:
-			end.next = nstart
-			end = nend
-		}
-	}
-	panic("unreachable")
-}
-
-func (p *parser) regexp() (start, end *instr) {
-	start, end = p.concatenation()
-	for {
-		switch p.c() {
-		default:
-			return
-		case '|':
-			p.nextc()
-			nstart, nend := p.concatenation()
-			alt := &instr{kind: iAlt}
-			p.re.add(alt)
-			alt.left = start
-			alt.next = nstart
-			nop := &instr{kind: iNop}
-			p.re.add(nop)
-			end.next = nop
-			nend.next = nop
-			start, end = alt, nop
-		}
-	}
-	panic("unreachable")
-}
-
-func unNop(i *instr) *instr {
-	for i.kind == iNop {
-		i = i.next
-	}
-	return i
-}
-
-func (re *Regexp) eliminateNops() {
-	for _, inst := range re.inst {
-		if inst.kind == iEnd {
-			continue
-		}
-		inst.next = unNop(inst.next)
-		if inst.kind == iAlt {
-			inst.left = unNop(inst.left)
-		}
-	}
-}
-
-func (re *Regexp) dump() {
-	print("prefix <", re.prefix, ">\n")
-	for _, inst := range re.inst {
-		print(inst.index, ": ")
-		inst.print()
-		if inst.kind != iEnd {
-			print(" -> ", inst.next.index)
-		}
-		print("\n")
-	}
-}
-
-func (re *Regexp) doParse() {
-	p := newParser(re)
-	start := &instr{kind: iStart}
-	re.add(start)
-	s, e := p.regexp()
-	start.next = s
-	re.start = start
-	e.next = re.add(&instr{kind: iEnd})
-
-	if debug {
-		re.dump()
-		println()
-	}
-
-	re.eliminateNops()
-	if debug {
-		re.dump()
-		println()
-	}
-	re.setPrefix()
-	if debug {
-		re.dump()
-		println()
-	}
-}
-
-// Extract regular text from the beginning of the pattern,
-// possibly after a leading iBOT.
-// That text can be used by doExecute to speed up matching.
-func (re *Regexp) setPrefix() {
-	var b []byte
-	var utf = make([]byte, utf8.UTFMax)
-	var inst *instr
-	// First instruction is start; skip that.  Also skip any initial iBOT.
-	inst = re.inst[0].next
-	for inst.kind == iBOT {
-		inst = inst.next
-	}
-Loop:
-	for ; inst.kind != iEnd; inst = inst.next {
-		// stop if this is not a char
-		if inst.kind != iChar {
-			break
-		}
-		// stop if this char can be followed by a match for an empty string,
-		// which includes closures, ^, and $.
-		switch inst.next.kind {
-		case iBOT, iEOT, iAlt:
-			break Loop
-		}
-		n := utf8.EncodeRune(utf, inst.char)
-		b = append(b, utf[0:n]...)
-	}
-	// point prefixStart instruction to first non-CHAR after prefix
-	re.prefixStart = inst
-	re.prefixBytes = b
-	re.prefix = string(b)
-}
-
-// String returns the source text used to compile the regular expression.
-func (re *Regexp) String() string {
-	return re.expr
-}
-
-// Compile parses a regular expression and returns, if successful, a Regexp
-// object that can be used to match against text.
-func Compile(str string) (regexp *Regexp, error error) {
-	regexp = new(Regexp)
-	// doParse will panic if there is a parse error.
-	defer func() {
-		if e := recover(); e != nil {
-			regexp = nil
-			error = e.(Error) // Will re-panic if error was not an Error, e.g. nil-pointer exception
-		}
-	}()
-	regexp.expr = str
-	regexp.inst = make([]*instr, 0, 10)
-	regexp.doParse()
-	return
-}
-
-// MustCompile is like Compile but panics if the expression cannot be parsed.
-// It simplifies safe initialization of global variables holding compiled regular
-// expressions.
-func MustCompile(str string) *Regexp {
-	regexp, error := Compile(str)
-	if error != nil {
-		panic(`regexp: compiling "` + str + `": ` + error.Error())
-	}
-	return regexp
-}
-
-// NumSubexp returns the number of parenthesized subexpressions in this Regexp.
-func (re *Regexp) NumSubexp() int { return re.nbra }
-
-// The match arena allows us to reduce the garbage generated by tossing
-// match vectors away as we execute.  Matches are ref counted and returned
-// to a free list when no longer active.  Increases a simple benchmark by 22X.
-type matchArena struct {
-	head  *matchVec
-	len   int // length of match vector
-	pos   int
-	atBOT bool // whether we're at beginning of text
-	atEOT bool // whether we're at end of text
-}
-
-type matchVec struct {
-	m    []int // pairs of bracketing submatches. 0th is start,end
-	ref  int
-	next *matchVec
-}
-
-func (a *matchArena) new() *matchVec {
-	if a.head == nil {
-		const N = 10
-		block := make([]matchVec, N)
-		for i := 0; i < N; i++ {
-			b := &block[i]
-			b.next = a.head
-			a.head = b
-		}
-	}
-	m := a.head
-	a.head = m.next
-	m.ref = 0
-	if m.m == nil {
-		m.m = make([]int, a.len)
-	}
-	return m
-}
-
-func (a *matchArena) free(m *matchVec) {
-	m.ref--
-	if m.ref == 0 {
-		m.next = a.head
-		a.head = m
-	}
-}
-
-func (a *matchArena) copy(m *matchVec) *matchVec {
-	m1 := a.new()
-	copy(m1.m, m.m)
-	return m1
-}
-
-func (a *matchArena) noMatch() *matchVec {
-	m := a.new()
-	for i := range m.m {
-		m.m[i] = -1 // no match seen; catches cases like "a(b)?c" on "ac"
-	}
-	m.ref = 1
-	return m
-}
-
-type state struct {
-	inst     *instr // next instruction to execute
-	prefixed bool   // this match began with a fixed prefix
-	match    *matchVec
-}
-
-// Append new state to to-do list.  Leftmost-longest wins so avoid
-// adding a state that's already active.  The matchVec will be inc-ref'ed
-// if it is assigned to a state.
-func (a *matchArena) addState(s []state, inst *instr, prefixed bool, match *matchVec) []state {
-	switch inst.kind {
-	case iBOT:
-		if a.atBOT {
-			s = a.addState(s, inst.next, prefixed, match)
-		}
-		return s
-	case iEOT:
-		if a.atEOT {
-			s = a.addState(s, inst.next, prefixed, match)
-		}
-		return s
-	case iBra:
-		match.m[inst.braNum] = a.pos
-		s = a.addState(s, inst.next, prefixed, match)
-		return s
-	}
-	l := len(s)
-	// States are inserted in order so it's sufficient to see if we have the same
-	// instruction; no need to see if existing match is earlier (it is).
-	for i := 0; i < l; i++ {
-		if s[i].inst == inst {
-			return s
-		}
-	}
-	s = append(s, state{inst, prefixed, match})
-	match.ref++
-	if inst.kind == iAlt {
-		s = a.addState(s, inst.left, prefixed, a.copy(match))
-		// give other branch a copy of this match vector
-		s = a.addState(s, inst.next, prefixed, a.copy(match))
-	}
-	return s
-}
-
-// input abstracts different representations of the input text. It provides
-// one-character lookahead.
-type input interface {
-	step(pos int) (r rune, width int) // advance one rune
-	canCheckPrefix() bool             // can we look ahead without losing info?
-	hasPrefix(re *Regexp) bool
-	index(re *Regexp, pos int) int
-}
-
-// inputString scans a string.
-type inputString struct {
-	str string
-}
-
-func newInputString(str string) *inputString {
-	return &inputString{str: str}
-}
-
-func (i *inputString) step(pos int) (rune, int) {
-	if pos < len(i.str) {
-		return utf8.DecodeRuneInString(i.str[pos:len(i.str)])
-	}
-	return endOfText, 0
-}
-
-func (i *inputString) canCheckPrefix() bool {
-	return true
-}
-
-func (i *inputString) hasPrefix(re *Regexp) bool {
-	return strings.HasPrefix(i.str, re.prefix)
-}
-
-func (i *inputString) index(re *Regexp, pos int) int {
-	return strings.Index(i.str[pos:], re.prefix)
-}
-
-// inputBytes scans a byte slice.
-type inputBytes struct {
-	str []byte
-}
-
-func newInputBytes(str []byte) *inputBytes {
-	return &inputBytes{str: str}
-}
-
-func (i *inputBytes) step(pos int) (rune, int) {
-	if pos < len(i.str) {
-		return utf8.DecodeRune(i.str[pos:len(i.str)])
-	}
-	return endOfText, 0
-}
-
-func (i *inputBytes) canCheckPrefix() bool {
-	return true
-}
-
-func (i *inputBytes) hasPrefix(re *Regexp) bool {
-	return bytes.HasPrefix(i.str, re.prefixBytes)
-}
-
-func (i *inputBytes) index(re *Regexp, pos int) int {
-	return bytes.Index(i.str[pos:], re.prefixBytes)
-}
-
-// inputReader scans a RuneReader.
-type inputReader struct {
-	r     io.RuneReader
-	atEOT bool
-	pos   int
-}
-
-func newInputReader(r io.RuneReader) *inputReader {
-	return &inputReader{r: r}
-}
-
-func (i *inputReader) step(pos int) (rune, int) {
-	if !i.atEOT && pos != i.pos {
-		return endOfText, 0
-
-	}
-	r, w, err := i.r.ReadRune()
-	if err != nil {
-		i.atEOT = true
-		return endOfText, 0
-	}
-	i.pos += w
-	return r, w
-}
-
-func (i *inputReader) canCheckPrefix() bool {
-	return false
-}
-
-func (i *inputReader) hasPrefix(re *Regexp) bool {
-	return false
-}
-
-func (i *inputReader) index(re *Regexp, pos int) int {
-	return -1
-}
-
-// Search match starting from pos bytes into the input.
-func (re *Regexp) doExecute(i input, pos int) []int {
-	var s [2][]state
-	s[0] = make([]state, 0, 10)
-	s[1] = make([]state, 0, 10)
-	in, out := 0, 1
-	var final state
-	found := false
-	anchored := re.inst[0].next.kind == iBOT
-	if anchored && pos > 0 {
-		return nil
-	}
-	// fast check for initial plain substring
-	if i.canCheckPrefix() && re.prefix != "" {
-		advance := 0
-		if anchored {
-			if !i.hasPrefix(re) {
-				return nil
-			}
-		} else {
-			advance = i.index(re, pos)
-			if advance == -1 {
-				return nil
-			}
-		}
-		pos += advance
-	}
-	// We look one character ahead so we can match $, which checks whether
-	// we are at EOT.
-	nextChar, nextWidth := i.step(pos)
-	arena := &matchArena{
-		len:   2 * (re.nbra + 1),
-		pos:   pos,
-		atBOT: pos == 0,
-		atEOT: nextChar == endOfText,
-	}
-	for c, startPos := rune(0), pos; c != endOfText; {
-		if !found && (pos == startPos || !anchored) {
-			// prime the pump if we haven't seen a match yet
-			match := arena.noMatch()
-			match.m[0] = pos
-			s[out] = arena.addState(s[out], re.start.next, false, match)
-			arena.free(match) // if addState saved it, ref was incremented
-		} else if len(s[out]) == 0 {
-			// machine has completed
-			break
-		}
-		in, out = out, in // old out state is new in state
-		// clear out old state
-		old := s[out]
-		for _, state := range old {
-			arena.free(state.match)
-		}
-		s[out] = old[0:0] // truncate state vector
-		c = nextChar
-		thisPos := pos
-		pos += nextWidth
-		nextChar, nextWidth = i.step(pos)
-		arena.atEOT = nextChar == endOfText
-		arena.atBOT = false
-		arena.pos = pos
-		for _, st := range s[in] {
-			switch st.inst.kind {
-			case iBOT:
-			case iEOT:
-			case iChar:
-				if c == st.inst.char {
-					s[out] = arena.addState(s[out], st.inst.next, st.prefixed, st.match)
-				}
-			case iCharClass:
-				if st.inst.cclass.matches(c) {
-					s[out] = arena.addState(s[out], st.inst.next, st.prefixed, st.match)
-				}
-			case iAny:
-				if c != endOfText {
-					s[out] = arena.addState(s[out], st.inst.next, st.prefixed, st.match)
-				}
-			case iNotNL:
-				if c != endOfText && c != '\n' {
-					s[out] = arena.addState(s[out], st.inst.next, st.prefixed, st.match)
-				}
-			case iBra:
-			case iAlt:
-			case iEnd:
-				// choose leftmost longest
-				if !found || // first
-					st.match.m[0] < final.match.m[0] || // leftmost
-					(st.match.m[0] == final.match.m[0] && thisPos > final.match.m[1]) { // longest
-					if final.match != nil {
-						arena.free(final.match)
-					}
-					final = st
-					final.match.ref++
-					final.match.m[1] = thisPos
-				}
-				found = true
-			default:
-				st.inst.print()
-				panic("unknown instruction in execute")
-			}
-		}
-	}
-	if final.match == nil {
-		return nil
-	}
-	// if match found, back up start of match by width of prefix.
-	if final.prefixed && len(final.match.m) > 0 {
-		final.match.m[0] -= len(re.prefix)
-	}
-	return final.match.m
-}
-
-// LiteralPrefix returns a literal string that must begin any match
-// of the regular expression re.  It returns the boolean true if the
-// literal string comprises the entire regular expression.
-func (re *Regexp) LiteralPrefix() (prefix string, complete bool) {
-	c := make([]rune, len(re.inst)-2) // minus start and end.
-	// First instruction is start; skip that.
-	i := 0
-	for inst := re.inst[0].next; inst.kind != iEnd; inst = inst.next {
-		// stop if this is not a char
-		if inst.kind != iChar {
-			return string(c[:i]), false
-		}
-		c[i] = inst.char
-		i++
-	}
-	return string(c[:i]), true
-}
-
-// MatchReader returns whether the Regexp matches the text read by the
-// RuneReader.  The return value is a boolean: true for match, false for no
-// match.
-func (re *Regexp) MatchReader(r io.RuneReader) bool {
-	return len(re.doExecute(newInputReader(r), 0)) > 0
-}
-
-// MatchString returns whether the Regexp matches the string s.
-// The return value is a boolean: true for match, false for no match.
-func (re *Regexp) MatchString(s string) bool { return len(re.doExecute(newInputString(s), 0)) > 0 }
-
-// Match returns whether the Regexp matches the byte slice b.
-// The return value is a boolean: true for match, false for no match.
-func (re *Regexp) Match(b []byte) bool { return len(re.doExecute(newInputBytes(b), 0)) > 0 }
-
-// MatchReader checks whether a textual regular expression matches the text
-// read by the RuneReader.  More complicated queries need to use Compile and
-// the full Regexp interface.
-func MatchReader(pattern string, r io.RuneReader) (matched bool, error error) {
-	re, err := Compile(pattern)
-	if err != nil {
-		return false, err
-	}
-	return re.MatchReader(r), nil
-}
-
-// MatchString checks whether a textual regular expression
-// matches a string.  More complicated queries need
-// to use Compile and the full Regexp interface.
-func MatchString(pattern string, s string) (matched bool, error error) {
-	re, err := Compile(pattern)
-	if err != nil {
-		return false, err
-	}
-	return re.MatchString(s), nil
-}
-
-// Match checks whether a textual regular expression
-// matches a byte slice.  More complicated queries need
-// to use Compile and the full Regexp interface.
-func Match(pattern string, b []byte) (matched bool, error error) {
-	re, err := Compile(pattern)
-	if err != nil {
-		return false, err
-	}
-	return re.Match(b), nil
-}
-
-// ReplaceAllString returns a copy of src in which all matches for the Regexp
-// have been replaced by repl.  No support is provided for expressions
-// (e.g. \1 or $1) in the replacement string.
-func (re *Regexp) ReplaceAllString(src, repl string) string {
-	return re.ReplaceAllStringFunc(src, func(string) string { return repl })
-}
-
-// ReplaceAllStringFunc returns a copy of src in which all matches for the
-// Regexp have been replaced by the return value of of function repl (whose
-// first argument is the matched string).  No support is provided for
-// expressions (e.g. \1 or $1) in the replacement string.
-func (re *Regexp) ReplaceAllStringFunc(src string, repl func(string) string) string {
-	lastMatchEnd := 0 // end position of the most recent match
-	searchPos := 0    // position where we next look for a match
-	buf := new(bytes.Buffer)
-	for searchPos <= len(src) {
-		a := re.doExecute(newInputString(src), searchPos)
-		if len(a) == 0 {
-			break // no more matches
-		}
-
-		// Copy the unmatched characters before this match.
-		io.WriteString(buf, src[lastMatchEnd:a[0]])
-
-		// Now insert a copy of the replacement string, but not for a
-		// match of the empty string immediately after another match.
-		// (Otherwise, we get double replacement for patterns that
-		// match both empty and nonempty strings.)
-		if a[1] > lastMatchEnd || a[0] == 0 {
-			io.WriteString(buf, repl(src[a[0]:a[1]]))
-		}
-		lastMatchEnd = a[1]
-
-		// Advance past this match; always advance at least one character.
-		_, width := utf8.DecodeRuneInString(src[searchPos:])
-		if searchPos+width > a[1] {
-			searchPos += width
-		} else if searchPos+1 > a[1] {
-			// This clause is only needed at the end of the input
-			// string.  In that case, DecodeRuneInString returns width=0.
-			searchPos++
-		} else {
-			searchPos = a[1]
-		}
-	}
-
-	// Copy the unmatched characters after the last match.
-	io.WriteString(buf, src[lastMatchEnd:])
-
-	return buf.String()
-}
-
-// ReplaceAll returns a copy of src in which all matches for the Regexp
-// have been replaced by repl.  No support is provided for expressions
-// (e.g. \1 or $1) in the replacement text.
-func (re *Regexp) ReplaceAll(src, repl []byte) []byte {
-	return re.ReplaceAllFunc(src, func([]byte) []byte { return repl })
-}
-
-// ReplaceAllFunc returns a copy of src in which all matches for the
-// Regexp have been replaced by the return value of of function repl (whose
-// first argument is the matched []byte).  No support is provided for
-// expressions (e.g. \1 or $1) in the replacement string.
-func (re *Regexp) ReplaceAllFunc(src []byte, repl func([]byte) []byte) []byte {
-	lastMatchEnd := 0 // end position of the most recent match
-	searchPos := 0    // position where we next look for a match
-	buf := new(bytes.Buffer)
-	for searchPos <= len(src) {
-		a := re.doExecute(newInputBytes(src), searchPos)
-		if len(a) == 0 {
-			break // no more matches
-		}
-
-		// Copy the unmatched characters before this match.
-		buf.Write(src[lastMatchEnd:a[0]])
-
-		// Now insert a copy of the replacement string, but not for a
-		// match of the empty string immediately after another match.
-		// (Otherwise, we get double replacement for patterns that
-		// match both empty and nonempty strings.)
-		if a[1] > lastMatchEnd || a[0] == 0 {
-			buf.Write(repl(src[a[0]:a[1]]))
-		}
-		lastMatchEnd = a[1]
-
-		// Advance past this match; always advance at least one character.
-		_, width := utf8.DecodeRune(src[searchPos:])
-		if searchPos+width > a[1] {
-			searchPos += width
-		} else if searchPos+1 > a[1] {
-			// This clause is only needed at the end of the input
-			// string.  In that case, DecodeRuneInString returns width=0.
-			searchPos++
-		} else {
-			searchPos = a[1]
-		}
-	}
-
-	// Copy the unmatched characters after the last match.
-	buf.Write(src[lastMatchEnd:])
-
-	return buf.Bytes()
-}
-
-// QuoteMeta returns a string that quotes all regular expression metacharacters
-// inside the argument text; the returned string is a regular expression matching
-// the literal text.  For example, QuoteMeta(`[foo]`) returns `\[foo\]`.
-func QuoteMeta(s string) string {
-	b := make([]byte, 2*len(s))
-
-	// A byte loop is correct because all metacharacters are ASCII.
-	j := 0
-	for i := 0; i < len(s); i++ {
-		if special(rune(s[i])) {
-			b[j] = '\\'
-			j++
-		}
-		b[j] = s[i]
-		j++
-	}
-	return string(b[0:j])
-}
-
-// Find matches in slice b if b is non-nil, otherwise find matches in string s.
-func (re *Regexp) allMatches(s string, b []byte, n int, deliver func([]int)) {
-	var end int
-	if b == nil {
-		end = len(s)
-	} else {
-		end = len(b)
-	}
-
-	for pos, i, prevMatchEnd := 0, 0, -1; i < n && pos <= end; {
-		var in input
-		if b == nil {
-			in = newInputString(s)
-		} else {
-			in = newInputBytes(b)
-		}
-		matches := re.doExecute(in, pos)
-		if len(matches) == 0 {
-			break
-		}
-
-		accept := true
-		if matches[1] == pos {
-			// We've found an empty match.
-			if matches[0] == prevMatchEnd {
-				// We don't allow an empty match right
-				// after a previous match, so ignore it.
-				accept = false
-			}
-			var width int
-			// TODO: use step()
-			if b == nil {
-				_, width = utf8.DecodeRuneInString(s[pos:end])
-			} else {
-				_, width = utf8.DecodeRune(b[pos:end])
-			}
-			if width > 0 {
-				pos += width
-			} else {
-				pos = end + 1
-			}
-		} else {
-			pos = matches[1]
-		}
-		prevMatchEnd = matches[1]
-
-		if accept {
-			deliver(matches)
-			i++
-		}
-	}
-}
-
-// Find returns a slice holding the text of the leftmost match in b of the regular expression.
-// A return value of nil indicates no match.
-func (re *Regexp) Find(b []byte) []byte {
-	a := re.doExecute(newInputBytes(b), 0)
-	if a == nil {
-		return nil
-	}
-	return b[a[0]:a[1]]
-}
-
-// FindIndex returns a two-element slice of integers defining the location of
-// the leftmost match in b of the regular expression.  The match itself is at
-// b[loc[0]:loc[1]].
-// A return value of nil indicates no match.
-func (re *Regexp) FindIndex(b []byte) (loc []int) {
-	a := re.doExecute(newInputBytes(b), 0)
-	if a == nil {
-		return nil
-	}
-	return a[0:2]
-}
-
-// FindString returns a string holding the text of the leftmost match in s of the regular
-// expression.  If there is no match, the return value is an empty string,
-// but it will also be empty if the regular expression successfully matches
-// an empty string.  Use FindStringIndex or FindStringSubmatch if it is
-// necessary to distinguish these cases.
-func (re *Regexp) FindString(s string) string {
-	a := re.doExecute(newInputString(s), 0)
-	if a == nil {
-		return ""
-	}
-	return s[a[0]:a[1]]
-}
-
-// FindStringIndex returns a two-element slice of integers defining the
-// location of the leftmost match in s of the regular expression.  The match
-// itself is at s[loc[0]:loc[1]].
-// A return value of nil indicates no match.
-func (re *Regexp) FindStringIndex(s string) []int {
-	a := re.doExecute(newInputString(s), 0)
-	if a == nil {
-		return nil
-	}
-	return a[0:2]
-}
-
-// FindReaderIndex returns a two-element slice of integers defining the
-// location of the leftmost match of the regular expression in text read from
-// the RuneReader.  The match itself is at s[loc[0]:loc[1]].  A return
-// value of nil indicates no match.
-func (re *Regexp) FindReaderIndex(r io.RuneReader) []int {
-	a := re.doExecute(newInputReader(r), 0)
-	if a == nil {
-		return nil
-	}
-	return a[0:2]
-}
-
-// FindSubmatch returns a slice of slices holding the text of the leftmost
-// match of the regular expression in b and the matches, if any, of its
-// subexpressions, as defined by the 'Submatch' descriptions in the package
-// comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindSubmatch(b []byte) [][]byte {
-	a := re.doExecute(newInputBytes(b), 0)
-	if a == nil {
-		return nil
-	}
-	ret := make([][]byte, len(a)/2)
-	for i := range ret {
-		if a[2*i] >= 0 {
-			ret[i] = b[a[2*i]:a[2*i+1]]
-		}
-	}
-	return ret
-}
-
-// FindSubmatchIndex returns a slice holding the index pairs identifying the
-// leftmost match of the regular expression in b and the matches, if any, of
-// its subexpressions, as defined by the 'Submatch' and 'Index' descriptions
-// in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindSubmatchIndex(b []byte) []int {
-	return re.doExecute(newInputBytes(b), 0)
-}
-
-// FindStringSubmatch returns a slice of strings holding the text of the
-// leftmost match of the regular expression in s and the matches, if any, of
-// its subexpressions, as defined by the 'Submatch' description in the
-// package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindStringSubmatch(s string) []string {
-	a := re.doExecute(newInputString(s), 0)
-	if a == nil {
-		return nil
-	}
-	ret := make([]string, len(a)/2)
-	for i := range ret {
-		if a[2*i] >= 0 {
-			ret[i] = s[a[2*i]:a[2*i+1]]
-		}
-	}
-	return ret
-}
-
-// FindStringSubmatchIndex returns a slice holding the index pairs
-// identifying the leftmost match of the regular expression in s and the
-// matches, if any, of its subexpressions, as defined by the 'Submatch' and
-// 'Index' descriptions in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindStringSubmatchIndex(s string) []int {
-	return re.doExecute(newInputString(s), 0)
-}
-
-// FindReaderSubmatchIndex returns a slice holding the index pairs
-// identifying the leftmost match of the regular expression of text read by
-// the RuneReader, and the matches, if any, of its subexpressions, as defined
-// by the 'Submatch' and 'Index' descriptions in the package comment.  A
-// return value of nil indicates no match.
-func (re *Regexp) FindReaderSubmatchIndex(r io.RuneReader) []int {
-	return re.doExecute(newInputReader(r), 0)
-}
-
-const startSize = 10 // The size at which to start a slice in the 'All' routines.
-
-// FindAll is the 'All' version of Find; it returns a slice of all successive
-// matches of the expression, as defined by the 'All' description in the
-// package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAll(b []byte, n int) [][]byte {
-	if n < 0 {
-		n = len(b) + 1
-	}
-	result := make([][]byte, 0, startSize)
-	re.allMatches("", b, n, func(match []int) {
-		result = append(result, b[match[0]:match[1]])
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}
-
-// FindAllIndex is the 'All' version of FindIndex; it returns a slice of all
-// successive matches of the expression, as defined by the 'All' description
-// in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAllIndex(b []byte, n int) [][]int {
-	if n < 0 {
-		n = len(b) + 1
-	}
-	result := make([][]int, 0, startSize)
-	re.allMatches("", b, n, func(match []int) {
-		result = append(result, match[0:2])
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}
-
-// FindAllString is the 'All' version of FindString; it returns a slice of all
-// successive matches of the expression, as defined by the 'All' description
-// in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAllString(s string, n int) []string {
-	if n < 0 {
-		n = len(s) + 1
-	}
-	result := make([]string, 0, startSize)
-	re.allMatches(s, nil, n, func(match []int) {
-		result = append(result, s[match[0]:match[1]])
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}
-
-// FindAllStringIndex is the 'All' version of FindStringIndex; it returns a
-// slice of all successive matches of the expression, as defined by the 'All'
-// description in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAllStringIndex(s string, n int) [][]int {
-	if n < 0 {
-		n = len(s) + 1
-	}
-	result := make([][]int, 0, startSize)
-	re.allMatches(s, nil, n, func(match []int) {
-		result = append(result, match[0:2])
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}
-
-// FindAllSubmatch is the 'All' version of FindSubmatch; it returns a slice
-// of all successive matches of the expression, as defined by the 'All'
-// description in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAllSubmatch(b []byte, n int) [][][]byte {
-	if n < 0 {
-		n = len(b) + 1
-	}
-	result := make([][][]byte, 0, startSize)
-	re.allMatches("", b, n, func(match []int) {
-		slice := make([][]byte, len(match)/2)
-		for j := range slice {
-			if match[2*j] >= 0 {
-				slice[j] = b[match[2*j]:match[2*j+1]]
-			}
-		}
-		result = append(result, slice)
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}
-
-// FindAllSubmatchIndex is the 'All' version of FindSubmatchIndex; it returns
-// a slice of all successive matches of the expression, as defined by the
-// 'All' description in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAllSubmatchIndex(b []byte, n int) [][]int {
-	if n < 0 {
-		n = len(b) + 1
-	}
-	result := make([][]int, 0, startSize)
-	re.allMatches("", b, n, func(match []int) {
-		result = append(result, match)
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}
-
-// FindAllStringSubmatch is the 'All' version of FindStringSubmatch; it
-// returns a slice of all successive matches of the expression, as defined by
-// the 'All' description in the package comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAllStringSubmatch(s string, n int) [][]string {
-	if n < 0 {
-		n = len(s) + 1
-	}
-	result := make([][]string, 0, startSize)
-	re.allMatches(s, nil, n, func(match []int) {
-		slice := make([]string, len(match)/2)
-		for j := range slice {
-			if match[2*j] >= 0 {
-				slice[j] = s[match[2*j]:match[2*j+1]]
-			}
-		}
-		result = append(result, slice)
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}
-
-// FindAllStringSubmatchIndex is the 'All' version of
-// FindStringSubmatchIndex; it returns a slice of all successive matches of
-// the expression, as defined by the 'All' description in the package
-// comment.
-// A return value of nil indicates no match.
-func (re *Regexp) FindAllStringSubmatchIndex(s string, n int) [][]int {
-	if n < 0 {
-		n = len(s) + 1
-	}
-	result := make([][]int, 0, startSize)
-	re.allMatches(s, nil, n, func(match []int) {
-		result = append(result, match)
-	})
-	if len(result) == 0 {
-		return nil
-	}
-	return result
-}