// 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"
	"os"
	"strings"
	"utf8"
)

var debug = false

// Error is the local type for a parsing error.
type Error string

func (e Error) String() 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 os.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.String())
	}
	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 os.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 os.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 os.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
}