Imported Upstream version 1.4upstream/1.4

1 files changed, 0 insertions, 1863 deletions

diff --git a/src/pkg/regexp/syntax/parse.go b/src/pkg/regexp/syntax/parse.go
deleted file mode 100644
index cb25dca39..000000000
--- a/src/pkg/regexp/syntax/parse.go
+++ /dev/null
@@ -1,1863 +0,0 @@
-// 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 syntax
-
-import (
-	"sort"
-	"strings"
-	"unicode"
-	"unicode/utf8"
-)
-
-// An Error describes a failure to parse a regular expression
-// and gives the offending expression.
-type Error struct {
-	Code ErrorCode
-	Expr string
-}
-
-func (e *Error) Error() string {
-	return "error parsing regexp: " + e.Code.String() + ": `" + e.Expr + "`"
-}
-
-// An ErrorCode describes a failure to parse a regular expression.
-type ErrorCode string
-
-const (
-	// Unexpected error
-	ErrInternalError ErrorCode = "regexp/syntax: internal error"
-
-	// Parse errors
-	ErrInvalidCharClass      ErrorCode = "invalid character class"
-	ErrInvalidCharRange      ErrorCode = "invalid character class range"
-	ErrInvalidEscape         ErrorCode = "invalid escape sequence"
-	ErrInvalidNamedCapture   ErrorCode = "invalid named capture"
-	ErrInvalidPerlOp         ErrorCode = "invalid or unsupported Perl syntax"
-	ErrInvalidRepeatOp       ErrorCode = "invalid nested repetition operator"
-	ErrInvalidRepeatSize     ErrorCode = "invalid repeat count"
-	ErrInvalidUTF8           ErrorCode = "invalid UTF-8"
-	ErrMissingBracket        ErrorCode = "missing closing ]"
-	ErrMissingParen          ErrorCode = "missing closing )"
-	ErrMissingRepeatArgument ErrorCode = "missing argument to repetition operator"
-	ErrTrailingBackslash     ErrorCode = "trailing backslash at end of expression"
-	ErrUnexpectedParen       ErrorCode = "unexpected )"
-)
-
-func (e ErrorCode) String() string {
-	return string(e)
-}
-
-// Flags control the behavior of the parser and record information about regexp context.
-type Flags uint16
-
-const (
-	FoldCase      Flags = 1 << iota // case-insensitive match
-	Literal                         // treat pattern as literal string
-	ClassNL                         // allow character classes like [^a-z] and [[:space:]] to match newline
-	DotNL                           // allow . to match newline
-	OneLine                         // treat ^ and $ as only matching at beginning and end of text
-	NonGreedy                       // make repetition operators default to non-greedy
-	PerlX                           // allow Perl extensions
-	UnicodeGroups                   // allow \p{Han}, \P{Han} for Unicode group and negation
-	WasDollar                       // regexp OpEndText was $, not \z
-	Simple                          // regexp contains no counted repetition
-
-	MatchNL = ClassNL | DotNL
-
-	Perl        = ClassNL | OneLine | PerlX | UnicodeGroups // as close to Perl as possible
-	POSIX Flags = 0                                         // POSIX syntax
-)
-
-// Pseudo-ops for parsing stack.
-const (
-	opLeftParen = opPseudo + iota
-	opVerticalBar
-)
-
-type parser struct {
-	flags       Flags     // parse mode flags
-	stack       []*Regexp // stack of parsed expressions
-	free        *Regexp
-	numCap      int // number of capturing groups seen
-	wholeRegexp string
-	tmpClass    []rune // temporary char class work space
-}
-
-func (p *parser) newRegexp(op Op) *Regexp {
-	re := p.free
-	if re != nil {
-		p.free = re.Sub0[0]
-		*re = Regexp{}
-	} else {
-		re = new(Regexp)
-	}
-	re.Op = op
-	return re
-}
-
-func (p *parser) reuse(re *Regexp) {
-	re.Sub0[0] = p.free
-	p.free = re
-}
-
-// Parse stack manipulation.
-
-// push pushes the regexp re onto the parse stack and returns the regexp.
-func (p *parser) push(re *Regexp) *Regexp {
-	if re.Op == OpCharClass && len(re.Rune) == 2 && re.Rune[0] == re.Rune[1] {
-		// Single rune.
-		if p.maybeConcat(re.Rune[0], p.flags&^FoldCase) {
-			return nil
-		}
-		re.Op = OpLiteral
-		re.Rune = re.Rune[:1]
-		re.Flags = p.flags &^ FoldCase
-	} else if re.Op == OpCharClass && len(re.Rune) == 4 &&
-		re.Rune[0] == re.Rune[1] && re.Rune[2] == re.Rune[3] &&
-		unicode.SimpleFold(re.Rune[0]) == re.Rune[2] &&
-		unicode.SimpleFold(re.Rune[2]) == re.Rune[0] ||
-		re.Op == OpCharClass && len(re.Rune) == 2 &&
-			re.Rune[0]+1 == re.Rune[1] &&
-			unicode.SimpleFold(re.Rune[0]) == re.Rune[1] &&
-			unicode.SimpleFold(re.Rune[1]) == re.Rune[0] {
-		// Case-insensitive rune like [Aa] or [Δδ].
-		if p.maybeConcat(re.Rune[0], p.flags|FoldCase) {
-			return nil
-		}
-
-		// Rewrite as (case-insensitive) literal.
-		re.Op = OpLiteral
-		re.Rune = re.Rune[:1]
-		re.Flags = p.flags | FoldCase
-	} else {
-		// Incremental concatenation.
-		p.maybeConcat(-1, 0)
-	}
-
-	p.stack = append(p.stack, re)
-	return re
-}
-
-// maybeConcat implements incremental concatenation
-// of literal runes into string nodes.  The parser calls this
-// before each push, so only the top fragment of the stack
-// might need processing.  Since this is called before a push,
-// the topmost literal is no longer subject to operators like *
-// (Otherwise ab* would turn into (ab)*.)
-// If r >= 0 and there's a node left over, maybeConcat uses it
-// to push r with the given flags.
-// maybeConcat reports whether r was pushed.
-func (p *parser) maybeConcat(r rune, flags Flags) bool {
-	n := len(p.stack)
-	if n < 2 {
-		return false
-	}
-
-	re1 := p.stack[n-1]
-	re2 := p.stack[n-2]
-	if re1.Op != OpLiteral || re2.Op != OpLiteral || re1.Flags&FoldCase != re2.Flags&FoldCase {
-		return false
-	}
-
-	// Push re1 into re2.
-	re2.Rune = append(re2.Rune, re1.Rune...)
-
-	// Reuse re1 if possible.
-	if r >= 0 {
-		re1.Rune = re1.Rune0[:1]
-		re1.Rune[0] = r
-		re1.Flags = flags
-		return true
-	}
-
-	p.stack = p.stack[:n-1]
-	p.reuse(re1)
-	return false // did not push r
-}
-
-// newLiteral returns a new OpLiteral Regexp with the given flags
-func (p *parser) newLiteral(r rune, flags Flags) *Regexp {
-	re := p.newRegexp(OpLiteral)
-	re.Flags = flags
-	if flags&FoldCase != 0 {
-		r = minFoldRune(r)
-	}
-	re.Rune0[0] = r
-	re.Rune = re.Rune0[:1]
-	return re
-}
-
-// minFoldRune returns the minimum rune fold-equivalent to r.
-func minFoldRune(r rune) rune {
-	if r < minFold || r > maxFold {
-		return r
-	}
-	min := r
-	r0 := r
-	for r = unicode.SimpleFold(r); r != r0; r = unicode.SimpleFold(r) {
-		if min > r {
-			min = r
-		}
-	}
-	return min
-}
-
-// literal pushes a literal regexp for the rune r on the stack
-// and returns that regexp.
-func (p *parser) literal(r rune) {
-	p.push(p.newLiteral(r, p.flags))
-}
-
-// op pushes a regexp with the given op onto the stack
-// and returns that regexp.
-func (p *parser) op(op Op) *Regexp {
-	re := p.newRegexp(op)
-	re.Flags = p.flags
-	return p.push(re)
-}
-
-// repeat replaces the top stack element with itself repeated according to op, min, max.
-// before is the regexp suffix starting at the repetition operator.
-// after is the regexp suffix following after the repetition operator.
-// repeat returns an updated 'after' and an error, if any.
-func (p *parser) repeat(op Op, min, max int, before, after, lastRepeat string) (string, error) {
-	flags := p.flags
-	if p.flags&PerlX != 0 {
-		if len(after) > 0 && after[0] == '?' {
-			after = after[1:]
-			flags ^= NonGreedy
-		}
-		if lastRepeat != "" {
-			// In Perl it is not allowed to stack repetition operators:
-			// a** is a syntax error, not a doubled star, and a++ means
-			// something else entirely, which we don't support!
-			return "", &Error{ErrInvalidRepeatOp, lastRepeat[:len(lastRepeat)-len(after)]}
-		}
-	}
-	n := len(p.stack)
-	if n == 0 {
-		return "", &Error{ErrMissingRepeatArgument, before[:len(before)-len(after)]}
-	}
-	sub := p.stack[n-1]
-	if sub.Op >= opPseudo {
-		return "", &Error{ErrMissingRepeatArgument, before[:len(before)-len(after)]}
-	}
-	re := p.newRegexp(op)
-	re.Min = min
-	re.Max = max
-	re.Flags = flags
-	re.Sub = re.Sub0[:1]
-	re.Sub[0] = sub
-	p.stack[n-1] = re
-	return after, nil
-}
-
-// concat replaces the top of the stack (above the topmost '|' or '(') with its concatenation.
-func (p *parser) concat() *Regexp {
-	p.maybeConcat(-1, 0)
-
-	// Scan down to find pseudo-operator | or (.
-	i := len(p.stack)
-	for i > 0 && p.stack[i-1].Op < opPseudo {
-		i--
-	}
-	subs := p.stack[i:]
-	p.stack = p.stack[:i]
-
-	// Empty concatenation is special case.
-	if len(subs) == 0 {
-		return p.push(p.newRegexp(OpEmptyMatch))
-	}
-
-	return p.push(p.collapse(subs, OpConcat))
-}
-
-// alternate replaces the top of the stack (above the topmost '(') with its alternation.
-func (p *parser) alternate() *Regexp {
-	// Scan down to find pseudo-operator (.
-	// There are no | above (.
-	i := len(p.stack)
-	for i > 0 && p.stack[i-1].Op < opPseudo {
-		i--
-	}
-	subs := p.stack[i:]
-	p.stack = p.stack[:i]
-
-	// Make sure top class is clean.
-	// All the others already are (see swapVerticalBar).
-	if len(subs) > 0 {
-		cleanAlt(subs[len(subs)-1])
-	}
-
-	// Empty alternate is special case
-	// (shouldn't happen but easy to handle).
-	if len(subs) == 0 {
-		return p.push(p.newRegexp(OpNoMatch))
-	}
-
-	return p.push(p.collapse(subs, OpAlternate))
-}
-
-// cleanAlt cleans re for eventual inclusion in an alternation.
-func cleanAlt(re *Regexp) {
-	switch re.Op {
-	case OpCharClass:
-		re.Rune = cleanClass(&re.Rune)
-		if len(re.Rune) == 2 && re.Rune[0] == 0 && re.Rune[1] == unicode.MaxRune {
-			re.Rune = nil
-			re.Op = OpAnyChar
-			return
-		}
-		if len(re.Rune) == 4 && re.Rune[0] == 0 && re.Rune[1] == '\n'-1 && re.Rune[2] == '\n'+1 && re.Rune[3] == unicode.MaxRune {
-			re.Rune = nil
-			re.Op = OpAnyCharNotNL
-			return
-		}
-		if cap(re.Rune)-len(re.Rune) > 100 {
-			// re.Rune will not grow any more.
-			// Make a copy or inline to reclaim storage.
-			re.Rune = append(re.Rune0[:0], re.Rune...)
-		}
-	}
-}
-
-// collapse returns the result of applying op to sub.
-// If sub contains op nodes, they all get hoisted up
-// so that there is never a concat of a concat or an
-// alternate of an alternate.
-func (p *parser) collapse(subs []*Regexp, op Op) *Regexp {
-	if len(subs) == 1 {
-		return subs[0]
-	}
-	re := p.newRegexp(op)
-	re.Sub = re.Sub0[:0]
-	for _, sub := range subs {
-		if sub.Op == op {
-			re.Sub = append(re.Sub, sub.Sub...)
-			p.reuse(sub)
-		} else {
-			re.Sub = append(re.Sub, sub)
-		}
-	}
-	if op == OpAlternate {
-		re.Sub = p.factor(re.Sub, re.Flags)
-		if len(re.Sub) == 1 {
-			old := re
-			re = re.Sub[0]
-			p.reuse(old)
-		}
-	}
-	return re
-}
-
-// factor factors common prefixes from the alternation list sub.
-// It returns a replacement list that reuses the same storage and
-// frees (passes to p.reuse) any removed *Regexps.
-//
-// For example,
-//     ABC|ABD|AEF|BCX|BCY
-// simplifies by literal prefix extraction to
-//     A(B(C|D)|EF)|BC(X|Y)
-// which simplifies by character class introduction to
-//     A(B[CD]|EF)|BC[XY]
-//
-func (p *parser) factor(sub []*Regexp, flags Flags) []*Regexp {
-	if len(sub) < 2 {
-		return sub
-	}
-
-	// Round 1: Factor out common literal prefixes.
-	var str []rune
-	var strflags Flags
-	start := 0
-	out := sub[:0]
-	for i := 0; i <= len(sub); i++ {
-		// Invariant: the Regexps that were in sub[0:start] have been
-		// used or marked for reuse, and the slice space has been reused
-		// for out (len(out) <= start).
-		//
-		// Invariant: sub[start:i] consists of regexps that all begin
-		// with str as modified by strflags.
-		var istr []rune
-		var iflags Flags
-		if i < len(sub) {
-			istr, iflags = p.leadingString(sub[i])
-			if iflags == strflags {
-				same := 0
-				for same < len(str) && same < len(istr) && str[same] == istr[same] {
-					same++
-				}
-				if same > 0 {
-					// Matches at least one rune in current range.
-					// Keep going around.
-					str = str[:same]
-					continue
-				}
-			}
-		}
-
-		// Found end of a run with common leading literal string:
-		// sub[start:i] all begin with str[0:len(str)], but sub[i]
-		// does not even begin with str[0].
-		//
-		// Factor out common string and append factored expression to out.
-		if i == start {
-			// Nothing to do - run of length 0.
-		} else if i == start+1 {
-			// Just one: don't bother factoring.
-			out = append(out, sub[start])
-		} else {
-			// Construct factored form: prefix(suffix1|suffix2|...)
-			prefix := p.newRegexp(OpLiteral)
-			prefix.Flags = strflags
-			prefix.Rune = append(prefix.Rune[:0], str...)
-
-			for j := start; j < i; j++ {
-				sub[j] = p.removeLeadingString(sub[j], len(str))
-			}
-			suffix := p.collapse(sub[start:i], OpAlternate) // recurse
-
-			re := p.newRegexp(OpConcat)
-			re.Sub = append(re.Sub[:0], prefix, suffix)
-			out = append(out, re)
-		}
-
-		// Prepare for next iteration.
-		start = i
-		str = istr
-		strflags = iflags
-	}
-	sub = out
-
-	// Round 2: Factor out common complex prefixes,
-	// just the first piece of each concatenation,
-	// whatever it is.  This is good enough a lot of the time.
-	start = 0
-	out = sub[:0]
-	var first *Regexp
-	for i := 0; i <= len(sub); i++ {
-		// Invariant: the Regexps that were in sub[0:start] have been
-		// used or marked for reuse, and the slice space has been reused
-		// for out (len(out) <= start).
-		//
-		// Invariant: sub[start:i] consists of regexps that all begin with ifirst.
-		var ifirst *Regexp
-		if i < len(sub) {
-			ifirst = p.leadingRegexp(sub[i])
-			if first != nil && first.Equal(ifirst) {
-				continue
-			}
-		}
-
-		// Found end of a run with common leading regexp:
-		// sub[start:i] all begin with first but sub[i] does not.
-		//
-		// Factor out common regexp and append factored expression to out.
-		if i == start {
-			// Nothing to do - run of length 0.
-		} else if i == start+1 {
-			// Just one: don't bother factoring.
-			out = append(out, sub[start])
-		} else {
-			// Construct factored form: prefix(suffix1|suffix2|...)
-			prefix := first
-			for j := start; j < i; j++ {
-				reuse := j != start // prefix came from sub[start]
-				sub[j] = p.removeLeadingRegexp(sub[j], reuse)
-			}
-			suffix := p.collapse(sub[start:i], OpAlternate) // recurse
-
-			re := p.newRegexp(OpConcat)
-			re.Sub = append(re.Sub[:0], prefix, suffix)
-			out = append(out, re)
-		}
-
-		// Prepare for next iteration.
-		start = i
-		first = ifirst
-	}
-	sub = out
-
-	// Round 3: Collapse runs of single literals into character classes.
-	start = 0
-	out = sub[:0]
-	for i := 0; i <= len(sub); i++ {
-		// Invariant: the Regexps that were in sub[0:start] have been
-		// used or marked for reuse, and the slice space has been reused
-		// for out (len(out) <= start).
-		//
-		// Invariant: sub[start:i] consists of regexps that are either
-		// literal runes or character classes.
-		if i < len(sub) && isCharClass(sub[i]) {
-			continue
-		}
-
-		// sub[i] is not a char or char class;
-		// emit char class for sub[start:i]...
-		if i == start {
-			// Nothing to do - run of length 0.
-		} else if i == start+1 {
-			out = append(out, sub[start])
-		} else {
-			// Make new char class.
-			// Start with most complex regexp in sub[start].
-			max := start
-			for j := start + 1; j < i; j++ {
-				if sub[max].Op < sub[j].Op || sub[max].Op == sub[j].Op && len(sub[max].Rune) < len(sub[j].Rune) {
-					max = j
-				}
-			}
-			sub[start], sub[max] = sub[max], sub[start]
-
-			for j := start + 1; j < i; j++ {
-				mergeCharClass(sub[start], sub[j])
-				p.reuse(sub[j])
-			}
-			cleanAlt(sub[start])
-			out = append(out, sub[start])
-		}
-
-		// ... and then emit sub[i].
-		if i < len(sub) {
-			out = append(out, sub[i])
-		}
-		start = i + 1
-	}
-	sub = out
-
-	// Round 4: Collapse runs of empty matches into a single empty match.
-	start = 0
-	out = sub[:0]
-	for i := range sub {
-		if i+1 < len(sub) && sub[i].Op == OpEmptyMatch && sub[i+1].Op == OpEmptyMatch {
-			continue
-		}
-		out = append(out, sub[i])
-	}
-	sub = out
-
-	return sub
-}
-
-// leadingString returns the leading literal string that re begins with.
-// The string refers to storage in re or its children.
-func (p *parser) leadingString(re *Regexp) ([]rune, Flags) {
-	if re.Op == OpConcat && len(re.Sub) > 0 {
-		re = re.Sub[0]
-	}
-	if re.Op != OpLiteral {
-		return nil, 0
-	}
-	return re.Rune, re.Flags & FoldCase
-}
-
-// removeLeadingString removes the first n leading runes
-// from the beginning of re.  It returns the replacement for re.
-func (p *parser) removeLeadingString(re *Regexp, n int) *Regexp {
-	if re.Op == OpConcat && len(re.Sub) > 0 {
-		// Removing a leading string in a concatenation
-		// might simplify the concatenation.
-		sub := re.Sub[0]
-		sub = p.removeLeadingString(sub, n)
-		re.Sub[0] = sub
-		if sub.Op == OpEmptyMatch {
-			p.reuse(sub)
-			switch len(re.Sub) {
-			case 0, 1:
-				// Impossible but handle.
-				re.Op = OpEmptyMatch
-				re.Sub = nil
-			case 2:
-				old := re
-				re = re.Sub[1]
-				p.reuse(old)
-			default:
-				copy(re.Sub, re.Sub[1:])
-				re.Sub = re.Sub[:len(re.Sub)-1]
-			}
-		}
-		return re
-	}
-
-	if re.Op == OpLiteral {
-		re.Rune = re.Rune[:copy(re.Rune, re.Rune[n:])]
-		if len(re.Rune) == 0 {
-			re.Op = OpEmptyMatch
-		}
-	}
-	return re
-}
-
-// leadingRegexp returns the leading regexp that re begins with.
-// The regexp refers to storage in re or its children.
-func (p *parser) leadingRegexp(re *Regexp) *Regexp {
-	if re.Op == OpEmptyMatch {
-		return nil
-	}
-	if re.Op == OpConcat && len(re.Sub) > 0 {
-		sub := re.Sub[0]
-		if sub.Op == OpEmptyMatch {
-			return nil
-		}
-		return sub
-	}
-	return re
-}
-
-// removeLeadingRegexp removes the leading regexp in re.
-// It returns the replacement for re.
-// If reuse is true, it passes the removed regexp (if no longer needed) to p.reuse.
-func (p *parser) removeLeadingRegexp(re *Regexp, reuse bool) *Regexp {
-	if re.Op == OpConcat && len(re.Sub) > 0 {
-		if reuse {
-			p.reuse(re.Sub[0])
-		}
-		re.Sub = re.Sub[:copy(re.Sub, re.Sub[1:])]
-		switch len(re.Sub) {
-		case 0:
-			re.Op = OpEmptyMatch
-			re.Sub = nil
-		case 1:
-			old := re
-			re = re.Sub[0]
-			p.reuse(old)
-		}
-		return re
-	}
-	if reuse {
-		p.reuse(re)
-	}
-	return p.newRegexp(OpEmptyMatch)
-}
-
-func literalRegexp(s string, flags Flags) *Regexp {
-	re := &Regexp{Op: OpLiteral}
-	re.Flags = flags
-	re.Rune = re.Rune0[:0] // use local storage for small strings
-	for _, c := range s {
-		if len(re.Rune) >= cap(re.Rune) {
-			// string is too long to fit in Rune0.  let Go handle it
-			re.Rune = []rune(s)
-			break
-		}
-		re.Rune = append(re.Rune, c)
-	}
-	return re
-}
-
-// Parsing.
-
-// Parse parses a regular expression string s, controlled by the specified
-// Flags, and returns a regular expression parse tree. The syntax is
-// described in the top-level comment.
-func Parse(s string, flags Flags) (*Regexp, error) {
-	if flags&Literal != 0 {
-		// Trivial parser for literal string.
-		if err := checkUTF8(s); err != nil {
-			return nil, err
-		}
-		return literalRegexp(s, flags), nil
-	}
-
-	// Otherwise, must do real work.
-	var (
-		p          parser
-		err        error
-		c          rune
-		op         Op
-		lastRepeat string
-	)
-	p.flags = flags
-	p.wholeRegexp = s
-	t := s
-	for t != "" {
-		repeat := ""
-	BigSwitch:
-		switch t[0] {
-		default:
-			if c, t, err = nextRune(t); err != nil {
-				return nil, err
-			}
-			p.literal(c)
-
-		case '(':
-			if p.flags&PerlX != 0 && len(t) >= 2 && t[1] == '?' {
-				// Flag changes and non-capturing groups.
-				if t, err = p.parsePerlFlags(t); err != nil {
-					return nil, err
-				}
-				break
-			}
-			p.numCap++
-			p.op(opLeftParen).Cap = p.numCap
-			t = t[1:]
-		case '|':
-			if err = p.parseVerticalBar(); err != nil {
-				return nil, err
-			}
-			t = t[1:]
-		case ')':
-			if err = p.parseRightParen(); err != nil {
-				return nil, err
-			}
-			t = t[1:]
-		case '^':
-			if p.flags&OneLine != 0 {
-				p.op(OpBeginText)
-			} else {
-				p.op(OpBeginLine)
-			}
-			t = t[1:]
-		case '$':
-			if p.flags&OneLine != 0 {
-				p.op(OpEndText).Flags |= WasDollar
-			} else {
-				p.op(OpEndLine)
-			}
-			t = t[1:]
-		case '.':
-			if p.flags&DotNL != 0 {
-				p.op(OpAnyChar)
-			} else {
-				p.op(OpAnyCharNotNL)
-			}
-			t = t[1:]
-		case '[':
-			if t, err = p.parseClass(t); err != nil {
-				return nil, err
-			}
-		case '*', '+', '?':
-			before := t
-			switch t[0] {
-			case '*':
-				op = OpStar
-			case '+':
-				op = OpPlus
-			case '?':
-				op = OpQuest
-			}
-			after := t[1:]
-			if after, err = p.repeat(op, 0, 0, before, after, lastRepeat); err != nil {
-				return nil, err
-			}
-			repeat = before
-			t = after
-		case '{':
-			op = OpRepeat
-			before := t
-			min, max, after, ok := p.parseRepeat(t)
-			if !ok {
-				// If the repeat cannot be parsed, { is a literal.
-				p.literal('{')
-				t = t[1:]
-				break
-			}
-			if min < 0 || min > 1000 || max > 1000 || max >= 0 && min > max {
-				// Numbers were too big, or max is present and min > max.
-				return nil, &Error{ErrInvalidRepeatSize, before[:len(before)-len(after)]}
-			}
-			if after, err = p.repeat(op, min, max, before, after, lastRepeat); err != nil {
-				return nil, err
-			}
-			repeat = before
-			t = after
-		case '\\':
-			if p.flags&PerlX != 0 && len(t) >= 2 {
-				switch t[1] {
-				case 'A':
-					p.op(OpBeginText)
-					t = t[2:]
-					break BigSwitch
-				case 'b':
-					p.op(OpWordBoundary)
-					t = t[2:]
-					break BigSwitch
-				case 'B':
-					p.op(OpNoWordBoundary)
-					t = t[2:]
-					break BigSwitch
-				case 'C':
-					// any byte; not supported
-					return nil, &Error{ErrInvalidEscape, t[:2]}
-				case 'Q':
-					// \Q ... \E: the ... is always literals
-					var lit string
-					if i := strings.Index(t, `\E`); i < 0 {
-						lit = t[2:]
-						t = ""
-					} else {
-						lit = t[2:i]
-						t = t[i+2:]
-					}
-					p.push(literalRegexp(lit, p.flags))
-					break BigSwitch
-				case 'z':
-					p.op(OpEndText)
-					t = t[2:]
-					break BigSwitch
-				}
-			}
-
-			re := p.newRegexp(OpCharClass)
-			re.Flags = p.flags
-
-			// Look for Unicode character group like \p{Han}
-			if len(t) >= 2 && (t[1] == 'p' || t[1] == 'P') {
-				r, rest, err := p.parseUnicodeClass(t, re.Rune0[:0])
-				if err != nil {
-					return nil, err
-				}
-				if r != nil {
-					re.Rune = r
-					t = rest
-					p.push(re)
-					break BigSwitch
-				}
-			}
-
-			// Perl character class escape.
-			if r, rest := p.parsePerlClassEscape(t, re.Rune0[:0]); r != nil {
-				re.Rune = r
-				t = rest
-				p.push(re)
-				break BigSwitch
-			}
-			p.reuse(re)
-
-			// Ordinary single-character escape.
-			if c, t, err = p.parseEscape(t); err != nil {
-				return nil, err
-			}
-			p.literal(c)
-		}
-		lastRepeat = repeat
-	}
-
-	p.concat()
-	if p.swapVerticalBar() {
-		// pop vertical bar
-		p.stack = p.stack[:len(p.stack)-1]
-	}
-	p.alternate()
-
-	n := len(p.stack)
-	if n != 1 {
-		return nil, &Error{ErrMissingParen, s}
-	}
-	return p.stack[0], nil
-}
-
-// parseRepeat parses {min} (max=min) or {min,} (max=-1) or {min,max}.
-// If s is not of that form, it returns ok == false.
-// If s has the right form but the values are too big, it returns min == -1, ok == true.
-func (p *parser) parseRepeat(s string) (min, max int, rest string, ok bool) {
-	if s == "" || s[0] != '{' {
-		return
-	}
-	s = s[1:]
-	var ok1 bool
-	if min, s, ok1 = p.parseInt(s); !ok1 {
-		return
-	}
-	if s == "" {
-		return
-	}
-	if s[0] != ',' {
-		max = min
-	} else {
-		s = s[1:]
-		if s == "" {
-			return
-		}
-		if s[0] == '}' {
-			max = -1
-		} else if max, s, ok1 = p.parseInt(s); !ok1 {
-			return
-		} else if max < 0 {
-			// parseInt found too big a number
-			min = -1
-		}
-	}
-	if s == "" || s[0] != '}' {
-		return
-	}
-	rest = s[1:]
-	ok = true
-	return
-}
-
-// parsePerlFlags parses a Perl flag setting or non-capturing group or both,
-// like (?i) or (?: or (?i:.  It removes the prefix from s and updates the parse state.
-// The caller must have ensured that s begins with "(?".
-func (p *parser) parsePerlFlags(s string) (rest string, err error) {
-	t := s
-
-	// Check for named captures, first introduced in Python's regexp library.
-	// As usual, there are three slightly different syntaxes:
-	//
-	//   (?P<name>expr)   the original, introduced by Python
-	//   (?<name>expr)    the .NET alteration, adopted by Perl 5.10
-	//   (?'name'expr)    another .NET alteration, adopted by Perl 5.10
-	//
-	// Perl 5.10 gave in and implemented the Python version too,
-	// but they claim that the last two are the preferred forms.
-	// PCRE and languages based on it (specifically, PHP and Ruby)
-	// support all three as well.  EcmaScript 4 uses only the Python form.
-	//
-	// In both the open source world (via Code Search) and the
-	// Google source tree, (?P<expr>name) is the dominant form,
-	// so that's the one we implement.  One is enough.
-	if len(t) > 4 && t[2] == 'P' && t[3] == '<' {
-		// Pull out name.
-		end := strings.IndexRune(t, '>')
-		if end < 0 {
-			if err = checkUTF8(t); err != nil {
-				return "", err
-			}
-			return "", &Error{ErrInvalidNamedCapture, s}
-		}
-
-		capture := t[:end+1] // "(?P<name>"
-		name := t[4:end]     // "name"
-		if err = checkUTF8(name); err != nil {
-			return "", err
-		}
-		if !isValidCaptureName(name) {
-			return "", &Error{ErrInvalidNamedCapture, capture}
-		}
-
-		// Like ordinary capture, but named.
-		p.numCap++
-		re := p.op(opLeftParen)
-		re.Cap = p.numCap
-		re.Name = name
-		return t[end+1:], nil
-	}
-
-	// Non-capturing group.  Might also twiddle Perl flags.
-	var c rune
-	t = t[2:] // skip (?
-	flags := p.flags
-	sign := +1
-	sawFlag := false
-Loop:
-	for t != "" {
-		if c, t, err = nextRune(t); err != nil {
-			return "", err
-		}
-		switch c {
-		default:
-			break Loop
-
-		// Flags.
-		case 'i':
-			flags |= FoldCase
-			sawFlag = true
-		case 'm':
-			flags &^= OneLine
-			sawFlag = true
-		case 's':
-			flags |= DotNL
-			sawFlag = true
-		case 'U':
-			flags |= NonGreedy
-			sawFlag = true
-
-		// Switch to negation.
-		case '-':
-			if sign < 0 {
-				break Loop
-			}
-			sign = -1
-			// Invert flags so that | above turn into &^ and vice versa.
-			// We'll invert flags again before using it below.
-			flags = ^flags
-			sawFlag = false
-
-		// End of flags, starting group or not.
-		case ':', ')':
-			if sign < 0 {
-				if !sawFlag {
-					break Loop
-				}
-				flags = ^flags
-			}
-			if c == ':' {
-				// Open new group
-				p.op(opLeftParen)
-			}
-			p.flags = flags
-			return t, nil
-		}
-	}
-
-	return "", &Error{ErrInvalidPerlOp, s[:len(s)-len(t)]}
-}
-
-// isValidCaptureName reports whether name
-// is a valid capture name: [A-Za-z0-9_]+.
-// PCRE limits names to 32 bytes.
-// Python rejects names starting with digits.
-// We don't enforce either of those.
-func isValidCaptureName(name string) bool {
-	if name == "" {
-		return false
-	}
-	for _, c := range name {
-		if c != '_' && !isalnum(c) {
-			return false
-		}
-	}
-	return true
-}
-
-// parseInt parses a decimal integer.
-func (p *parser) parseInt(s string) (n int, rest string, ok bool) {
-	if s == "" || s[0] < '0' || '9' < s[0] {
-		return
-	}
-	// Disallow leading zeros.
-	if len(s) >= 2 && s[0] == '0' && '0' <= s[1] && s[1] <= '9' {
-		return
-	}
-	t := s
-	for s != "" && '0' <= s[0] && s[0] <= '9' {
-		s = s[1:]
-	}
-	rest = s
-	ok = true
-	// Have digits, compute value.
-	t = t[:len(t)-len(s)]
-	for i := 0; i < len(t); i++ {
-		// Avoid overflow.
-		if n >= 1e8 {
-			n = -1
-			break
-		}
-		n = n*10 + int(t[i]) - '0'
-	}
-	return
-}
-
-// can this be represented as a character class?
-// single-rune literal string, char class, ., and .|\n.
-func isCharClass(re *Regexp) bool {
-	return re.Op == OpLiteral && len(re.Rune) == 1 ||
-		re.Op == OpCharClass ||
-		re.Op == OpAnyCharNotNL ||
-		re.Op == OpAnyChar
-}
-
-// does re match r?
-func matchRune(re *Regexp, r rune) bool {
-	switch re.Op {
-	case OpLiteral:
-		return len(re.Rune) == 1 && re.Rune[0] == r
-	case OpCharClass:
-		for i := 0; i < len(re.Rune); i += 2 {
-			if re.Rune[i] <= r && r <= re.Rune[i+1] {
-				return true
-			}
-		}
-		return false
-	case OpAnyCharNotNL:
-		return r != '\n'
-	case OpAnyChar:
-		return true
-	}
-	return false
-}
-
-// parseVerticalBar handles a | in the input.
-func (p *parser) parseVerticalBar() error {
-	p.concat()
-
-	// The concatenation we just parsed is on top of the stack.
-	// If it sits above an opVerticalBar, swap it below
-	// (things below an opVerticalBar become an alternation).
-	// Otherwise, push a new vertical bar.
-	if !p.swapVerticalBar() {
-		p.op(opVerticalBar)
-	}
-
-	return nil
-}
-
-// mergeCharClass makes dst = dst|src.
-// The caller must ensure that dst.Op >= src.Op,
-// to reduce the amount of copying.
-func mergeCharClass(dst, src *Regexp) {
-	switch dst.Op {
-	case OpAnyChar:
-		// src doesn't add anything.
-	case OpAnyCharNotNL:
-		// src might add \n
-		if matchRune(src, '\n') {
-			dst.Op = OpAnyChar
-		}
-	case OpCharClass:
-		// src is simpler, so either literal or char class
-		if src.Op == OpLiteral {
-			dst.Rune = appendLiteral(dst.Rune, src.Rune[0], src.Flags)
-		} else {
-			dst.Rune = appendClass(dst.Rune, src.Rune)
-		}
-	case OpLiteral:
-		// both literal
-		if src.Rune[0] == dst.Rune[0] && src.Flags == dst.Flags {
-			break
-		}
-		dst.Op = OpCharClass
-		dst.Rune = appendLiteral(dst.Rune[:0], dst.Rune[0], dst.Flags)
-		dst.Rune = appendLiteral(dst.Rune, src.Rune[0], src.Flags)
-	}
-}
-
-// If the top of the stack is an element followed by an opVerticalBar
-// swapVerticalBar swaps the two and returns true.
-// Otherwise it returns false.
-func (p *parser) swapVerticalBar() bool {
-	// If above and below vertical bar are literal or char class,
-	// can merge into a single char class.
-	n := len(p.stack)
-	if n >= 3 && p.stack[n-2].Op == opVerticalBar && isCharClass(p.stack[n-1]) && isCharClass(p.stack[n-3]) {
-		re1 := p.stack[n-1]
-		re3 := p.stack[n-3]
-		// Make re3 the more complex of the two.
-		if re1.Op > re3.Op {
-			re1, re3 = re3, re1
-			p.stack[n-3] = re3
-		}
-		mergeCharClass(re3, re1)
-		p.reuse(re1)
-		p.stack = p.stack[:n-1]
-		return true
-	}
-
-	if n >= 2 {
-		re1 := p.stack[n-1]
-		re2 := p.stack[n-2]
-		if re2.Op == opVerticalBar {
-			if n >= 3 {
-				// Now out of reach.
-				// Clean opportunistically.
-				cleanAlt(p.stack[n-3])
-			}
-			p.stack[n-2] = re1
-			p.stack[n-1] = re2
-			return true
-		}
-	}
-	return false
-}
-
-// parseRightParen handles a ) in the input.
-func (p *parser) parseRightParen() error {
-	p.concat()
-	if p.swapVerticalBar() {
-		// pop vertical bar
-		p.stack = p.stack[:len(p.stack)-1]
-	}
-	p.alternate()
-
-	n := len(p.stack)
-	if n < 2 {
-		return &Error{ErrUnexpectedParen, p.wholeRegexp}
-	}
-	re1 := p.stack[n-1]
-	re2 := p.stack[n-2]
-	p.stack = p.stack[:n-2]
-	if re2.Op != opLeftParen {
-		return &Error{ErrUnexpectedParen, p.wholeRegexp}
-	}
-	// Restore flags at time of paren.
-	p.flags = re2.Flags
-	if re2.Cap == 0 {
-		// Just for grouping.
-		p.push(re1)
-	} else {
-		re2.Op = OpCapture
-		re2.Sub = re2.Sub0[:1]
-		re2.Sub[0] = re1
-		p.push(re2)
-	}
-	return nil
-}
-
-// parseEscape parses an escape sequence at the beginning of s
-// and returns the rune.
-func (p *parser) parseEscape(s string) (r rune, rest string, err error) {
-	t := s[1:]
-	if t == "" {
-		return 0, "", &Error{ErrTrailingBackslash, ""}
-	}
-	c, t, err := nextRune(t)
-	if err != nil {
-		return 0, "", err
-	}
-
-Switch:
-	switch c {
-	default:
-		if c < utf8.RuneSelf && !isalnum(c) {
-			// Escaped non-word characters are always themselves.
-			// PCRE is not quite so rigorous: it accepts things like
-			// \q, but we don't.  We once rejected \_, but too many
-			// programs and people insist on using it, so allow \_.
-			return c, t, nil
-		}
-
-	// Octal escapes.
-	case '1', '2', '3', '4', '5', '6', '7':
-		// Single non-zero digit is a backreference; not supported
-		if t == "" || t[0] < '0' || t[0] > '7' {
-			break
-		}
-		fallthrough
-	case '0':
-		// Consume up to three octal digits; already have one.
-		r = c - '0'
-		for i := 1; i < 3; i++ {
-			if t == "" || t[0] < '0' || t[0] > '7' {
-				break
-			}
-			r = r*8 + rune(t[0]) - '0'
-			t = t[1:]
-		}
-		return r, t, nil
-
-	// Hexadecimal escapes.
-	case 'x':
-		if t == "" {
-			break
-		}
-		if c, t, err = nextRune(t); err != nil {
-			return 0, "", err
-		}
-		if c == '{' {
-			// Any number of digits in braces.
-			// Perl accepts any text at all; it ignores all text
-			// after the first non-hex digit.  We require only hex digits,
-			// and at least one.
-			nhex := 0
-			r = 0
-			for {
-				if t == "" {
-					break Switch
-				}
-				if c, t, err = nextRune(t); err != nil {
-					return 0, "", err
-				}
-				if c == '}' {
-					break
-				}
-				v := unhex(c)
-				if v < 0 {
-					break Switch
-				}
-				r = r*16 + v
-				if r > unicode.MaxRune {
-					break Switch
-				}
-				nhex++
-			}
-			if nhex == 0 {
-				break Switch
-			}
-			return r, t, nil
-		}
-
-		// Easy case: two hex digits.
-		x := unhex(c)
-		if c, t, err = nextRune(t); err != nil {
-			return 0, "", err
-		}
-		y := unhex(c)
-		if x < 0 || y < 0 {
-			break
-		}
-		return x*16 + y, t, nil
-
-	// C escapes.  There is no case 'b', to avoid misparsing
-	// the Perl word-boundary \b as the C backspace \b
-	// when in POSIX mode.  In Perl, /\b/ means word-boundary
-	// but /[\b]/ means backspace.  We don't support that.
-	// If you want a backspace, embed a literal backspace
-	// character or use \x08.
-	case 'a':
-		return '\a', t, err
-	case 'f':
-		return '\f', t, err
-	case 'n':
-		return '\n', t, err
-	case 'r':
-		return '\r', t, err
-	case 't':
-		return '\t', t, err
-	case 'v':
-		return '\v', t, err
-	}
-	return 0, "", &Error{ErrInvalidEscape, s[:len(s)-len(t)]}
-}
-
-// parseClassChar parses a character class character at the beginning of s
-// and returns it.
-func (p *parser) parseClassChar(s, wholeClass string) (r rune, rest string, err error) {
-	if s == "" {
-		return 0, "", &Error{Code: ErrMissingBracket, Expr: wholeClass}
-	}
-
-	// Allow regular escape sequences even though
-	// many need not be escaped in this context.
-	if s[0] == '\\' {
-		return p.parseEscape(s)
-	}
-
-	return nextRune(s)
-}
-
-type charGroup struct {
-	sign  int
-	class []rune
-}
-
-// parsePerlClassEscape parses a leading Perl character class escape like \d
-// from the beginning of s.  If one is present, it appends the characters to r
-// and returns the new slice r and the remainder of the string.
-func (p *parser) parsePerlClassEscape(s string, r []rune) (out []rune, rest string) {
-	if p.flags&PerlX == 0 || len(s) < 2 || s[0] != '\\' {
-		return
-	}
-	g := perlGroup[s[0:2]]
-	if g.sign == 0 {
-		return
-	}
-	return p.appendGroup(r, g), s[2:]
-}
-
-// parseNamedClass parses a leading POSIX named character class like [:alnum:]
-// from the beginning of s.  If one is present, it appends the characters to r
-// and returns the new slice r and the remainder of the string.
-func (p *parser) parseNamedClass(s string, r []rune) (out []rune, rest string, err error) {
-	if len(s) < 2 || s[0] != '[' || s[1] != ':' {
-		return
-	}
-
-	i := strings.Index(s[2:], ":]")
-	if i < 0 {
-		return
-	}
-	i += 2
-	name, s := s[0:i+2], s[i+2:]
-	g := posixGroup[name]
-	if g.sign == 0 {
-		return nil, "", &Error{ErrInvalidCharRange, name}
-	}
-	return p.appendGroup(r, g), s, nil
-}
-
-func (p *parser) appendGroup(r []rune, g charGroup) []rune {
-	if p.flags&FoldCase == 0 {
-		if g.sign < 0 {
-			r = appendNegatedClass(r, g.class)
-		} else {
-			r = appendClass(r, g.class)
-		}
-	} else {
-		tmp := p.tmpClass[:0]
-		tmp = appendFoldedClass(tmp, g.class)
-		p.tmpClass = tmp
-		tmp = cleanClass(&p.tmpClass)
-		if g.sign < 0 {
-			r = appendNegatedClass(r, tmp)
-		} else {
-			r = appendClass(r, tmp)
-		}
-	}
-	return r
-}
-
-var anyTable = &unicode.RangeTable{
-	R16: []unicode.Range16{{Lo: 0, Hi: 1<<16 - 1, Stride: 1}},
-	R32: []unicode.Range32{{Lo: 1 << 16, Hi: unicode.MaxRune, Stride: 1}},
-}
-
-// unicodeTable returns the unicode.RangeTable identified by name
-// and the table of additional fold-equivalent code points.
-func unicodeTable(name string) (*unicode.RangeTable, *unicode.RangeTable) {
-	// Special case: "Any" means any.
-	if name == "Any" {
-		return anyTable, anyTable
-	}
-	if t := unicode.Categories[name]; t != nil {
-		return t, unicode.FoldCategory[name]
-	}
-	if t := unicode.Scripts[name]; t != nil {
-		return t, unicode.FoldScript[name]
-	}
-	return nil, nil
-}
-
-// parseUnicodeClass parses a leading Unicode character class like \p{Han}
-// from the beginning of s.  If one is present, it appends the characters to r
-// and returns the new slice r and the remainder of the string.
-func (p *parser) parseUnicodeClass(s string, r []rune) (out []rune, rest string, err error) {
-	if p.flags&UnicodeGroups == 0 || len(s) < 2 || s[0] != '\\' || s[1] != 'p' && s[1] != 'P' {
-		return
-	}
-
-	// Committed to parse or return error.
-	sign := +1
-	if s[1] == 'P' {
-		sign = -1
-	}
-	t := s[2:]
-	c, t, err := nextRune(t)
-	if err != nil {
-		return
-	}
-	var seq, name string
-	if c != '{' {
-		// Single-letter name.
-		seq = s[:len(s)-len(t)]
-		name = seq[2:]
-	} else {
-		// Name is in braces.
-		end := strings.IndexRune(s, '}')
-		if end < 0 {
-			if err = checkUTF8(s); err != nil {
-				return
-			}
-			return nil, "", &Error{ErrInvalidCharRange, s}
-		}
-		seq, t = s[:end+1], s[end+1:]
-		name = s[3:end]
-		if err = checkUTF8(name); err != nil {
-			return
-		}
-	}
-
-	// Group can have leading negation too.  \p{^Han} == \P{Han}, \P{^Han} == \p{Han}.
-	if name != "" && name[0] == '^' {
-		sign = -sign
-		name = name[1:]
-	}
-
-	tab, fold := unicodeTable(name)
-	if tab == nil {
-		return nil, "", &Error{ErrInvalidCharRange, seq}
-	}
-
-	if p.flags&FoldCase == 0 || fold == nil {
-		if sign > 0 {
-			r = appendTable(r, tab)
-		} else {
-			r = appendNegatedTable(r, tab)
-		}
-	} else {
-		// Merge and clean tab and fold in a temporary buffer.
-		// This is necessary for the negative case and just tidy
-		// for the positive case.
-		tmp := p.tmpClass[:0]
-		tmp = appendTable(tmp, tab)
-		tmp = appendTable(tmp, fold)
-		p.tmpClass = tmp
-		tmp = cleanClass(&p.tmpClass)
-		if sign > 0 {
-			r = appendClass(r, tmp)
-		} else {
-			r = appendNegatedClass(r, tmp)
-		}
-	}
-	return r, t, nil
-}
-
-// parseClass parses a character class at the beginning of s
-// and pushes it onto the parse stack.
-func (p *parser) parseClass(s string) (rest string, err error) {
-	t := s[1:] // chop [
-	re := p.newRegexp(OpCharClass)
-	re.Flags = p.flags
-	re.Rune = re.Rune0[:0]
-
-	sign := +1
-	if t != "" && t[0] == '^' {
-		sign = -1
-		t = t[1:]
-
-		// If character class does not match \n, add it here,
-		// so that negation later will do the right thing.
-		if p.flags&ClassNL == 0 {
-			re.Rune = append(re.Rune, '\n', '\n')
-		}
-	}
-
-	class := re.Rune
-	first := true // ] and - are okay as first char in class
-	for t == "" || t[0] != ']' || first {
-		// POSIX: - is only okay unescaped as first or last in class.
-		// Perl: - is okay anywhere.
-		if t != "" && t[0] == '-' && p.flags&PerlX == 0 && !first && (len(t) == 1 || t[1] != ']') {
-			_, size := utf8.DecodeRuneInString(t[1:])
-			return "", &Error{Code: ErrInvalidCharRange, Expr: t[:1+size]}
-		}
-		first = false
-
-		// Look for POSIX [:alnum:] etc.
-		if len(t) > 2 && t[0] == '[' && t[1] == ':' {
-			nclass, nt, err := p.parseNamedClass(t, class)
-			if err != nil {
-				return "", err
-			}
-			if nclass != nil {
-				class, t = nclass, nt
-				continue
-			}
-		}
-
-		// Look for Unicode character group like \p{Han}.
-		nclass, nt, err := p.parseUnicodeClass(t, class)
-		if err != nil {
-			return "", err
-		}
-		if nclass != nil {
-			class, t = nclass, nt
-			continue
-		}
-
-		// Look for Perl character class symbols (extension).
-		if nclass, nt := p.parsePerlClassEscape(t, class); nclass != nil {
-			class, t = nclass, nt
-			continue
-		}
-
-		// Single character or simple range.
-		rng := t
-		var lo, hi rune
-		if lo, t, err = p.parseClassChar(t, s); err != nil {
-			return "", err
-		}
-		hi = lo
-		// [a-] means (a|-) so check for final ].
-		if len(t) >= 2 && t[0] == '-' && t[1] != ']' {
-			t = t[1:]
-			if hi, t, err = p.parseClassChar(t, s); err != nil {
-				return "", err
-			}
-			if hi < lo {
-				rng = rng[:len(rng)-len(t)]
-				return "", &Error{Code: ErrInvalidCharRange, Expr: rng}
-			}
-		}
-		if p.flags&FoldCase == 0 {
-			class = appendRange(class, lo, hi)
-		} else {
-			class = appendFoldedRange(class, lo, hi)
-		}
-	}
-	t = t[1:] // chop ]
-
-	// Use &re.Rune instead of &class to avoid allocation.
-	re.Rune = class
-	class = cleanClass(&re.Rune)
-	if sign < 0 {
-		class = negateClass(class)
-	}
-	re.Rune = class
-	p.push(re)
-	return t, nil
-}
-
-// cleanClass sorts the ranges (pairs of elements of r),
-// merges them, and eliminates duplicates.
-func cleanClass(rp *[]rune) []rune {
-
-	// Sort by lo increasing, hi decreasing to break ties.
-	sort.Sort(ranges{rp})
-
-	r := *rp
-	if len(r) < 2 {
-		return r
-	}
-
-	// Merge abutting, overlapping.
-	w := 2 // write index
-	for i := 2; i < len(r); i += 2 {
-		lo, hi := r[i], r[i+1]
-		if lo <= r[w-1]+1 {
-			// merge with previous range
-			if hi > r[w-1] {
-				r[w-1] = hi
-			}
-			continue
-		}
-		// new disjoint range
-		r[w] = lo
-		r[w+1] = hi
-		w += 2
-	}
-
-	return r[:w]
-}
-
-// appendLiteral returns the result of appending the literal x to the class r.
-func appendLiteral(r []rune, x rune, flags Flags) []rune {
-	if flags&FoldCase != 0 {
-		return appendFoldedRange(r, x, x)
-	}
-	return appendRange(r, x, x)
-}
-
-// appendRange returns the result of appending the range lo-hi to the class r.
-func appendRange(r []rune, lo, hi rune) []rune {
-	// Expand last range or next to last range if it overlaps or abuts.
-	// Checking two ranges helps when appending case-folded
-	// alphabets, so that one range can be expanding A-Z and the
-	// other expanding a-z.
-	n := len(r)
-	for i := 2; i <= 4; i += 2 { // twice, using i=2, i=4
-		if n >= i {
-			rlo, rhi := r[n-i], r[n-i+1]
-			if lo <= rhi+1 && rlo <= hi+1 {
-				if lo < rlo {
-					r[n-i] = lo
-				}
-				if hi > rhi {
-					r[n-i+1] = hi
-				}
-				return r
-			}
-		}
-	}
-
-	return append(r, lo, hi)
-}
-
-const (
-	// minimum and maximum runes involved in folding.
-	// checked during test.
-	minFold = 0x0041
-	maxFold = 0x1044f
-)
-
-// appendFoldedRange returns the result of appending the range lo-hi
-// and its case folding-equivalent runes to the class r.
-func appendFoldedRange(r []rune, lo, hi rune) []rune {
-	// Optimizations.
-	if lo <= minFold && hi >= maxFold {
-		// Range is full: folding can't add more.
-		return appendRange(r, lo, hi)
-	}
-	if hi < minFold || lo > maxFold {
-		// Range is outside folding possibilities.
-		return appendRange(r, lo, hi)
-	}
-	if lo < minFold {
-		// [lo, minFold-1] needs no folding.
-		r = appendRange(r, lo, minFold-1)
-		lo = minFold
-	}
-	if hi > maxFold {
-		// [maxFold+1, hi] needs no folding.
-		r = appendRange(r, maxFold+1, hi)
-		hi = maxFold
-	}
-
-	// Brute force.  Depend on appendRange to coalesce ranges on the fly.
-	for c := lo; c <= hi; c++ {
-		r = appendRange(r, c, c)
-		f := unicode.SimpleFold(c)
-		for f != c {
-			r = appendRange(r, f, f)
-			f = unicode.SimpleFold(f)
-		}
-	}
-	return r
-}
-
-// appendClass returns the result of appending the class x to the class r.
-// It assume x is clean.
-func appendClass(r []rune, x []rune) []rune {
-	for i := 0; i < len(x); i += 2 {
-		r = appendRange(r, x[i], x[i+1])
-	}
-	return r
-}
-
-// appendFolded returns the result of appending the case folding of the class x to the class r.
-func appendFoldedClass(r []rune, x []rune) []rune {
-	for i := 0; i < len(x); i += 2 {
-		r = appendFoldedRange(r, x[i], x[i+1])
-	}
-	return r
-}
-
-// appendNegatedClass returns the result of appending the negation of the class x to the class r.
-// It assumes x is clean.
-func appendNegatedClass(r []rune, x []rune) []rune {
-	nextLo := '\u0000'
-	for i := 0; i < len(x); i += 2 {
-		lo, hi := x[i], x[i+1]
-		if nextLo <= lo-1 {
-			r = appendRange(r, nextLo, lo-1)
-		}
-		nextLo = hi + 1
-	}
-	if nextLo <= unicode.MaxRune {
-		r = appendRange(r, nextLo, unicode.MaxRune)
-	}
-	return r
-}
-
-// appendTable returns the result of appending x to the class r.
-func appendTable(r []rune, x *unicode.RangeTable) []rune {
-	for _, xr := range x.R16 {
-		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
-		if stride == 1 {
-			r = appendRange(r, lo, hi)
-			continue
-		}
-		for c := lo; c <= hi; c += stride {
-			r = appendRange(r, c, c)
-		}
-	}
-	for _, xr := range x.R32 {
-		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
-		if stride == 1 {
-			r = appendRange(r, lo, hi)
-			continue
-		}
-		for c := lo; c <= hi; c += stride {
-			r = appendRange(r, c, c)
-		}
-	}
-	return r
-}
-
-// appendNegatedTable returns the result of appending the negation of x to the class r.
-func appendNegatedTable(r []rune, x *unicode.RangeTable) []rune {
-	nextLo := '\u0000' // lo end of next class to add
-	for _, xr := range x.R16 {
-		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
-		if stride == 1 {
-			if nextLo <= lo-1 {
-				r = appendRange(r, nextLo, lo-1)
-			}
-			nextLo = hi + 1
-			continue
-		}
-		for c := lo; c <= hi; c += stride {
-			if nextLo <= c-1 {
-				r = appendRange(r, nextLo, c-1)
-			}
-			nextLo = c + 1
-		}
-	}
-	for _, xr := range x.R32 {
-		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
-		if stride == 1 {
-			if nextLo <= lo-1 {
-				r = appendRange(r, nextLo, lo-1)
-			}
-			nextLo = hi + 1
-			continue
-		}
-		for c := lo; c <= hi; c += stride {
-			if nextLo <= c-1 {
-				r = appendRange(r, nextLo, c-1)
-			}
-			nextLo = c + 1
-		}
-	}
-	if nextLo <= unicode.MaxRune {
-		r = appendRange(r, nextLo, unicode.MaxRune)
-	}
-	return r
-}
-
-// negateClass overwrites r and returns r's negation.
-// It assumes the class r is already clean.
-func negateClass(r []rune) []rune {
-	nextLo := '\u0000' // lo end of next class to add
-	w := 0             // write index
-	for i := 0; i < len(r); i += 2 {
-		lo, hi := r[i], r[i+1]
-		if nextLo <= lo-1 {
-			r[w] = nextLo
-			r[w+1] = lo - 1
-			w += 2
-		}
-		nextLo = hi + 1
-	}
-	r = r[:w]
-	if nextLo <= unicode.MaxRune {
-		// It's possible for the negation to have one more
-		// range - this one - than the original class, so use append.
-		r = append(r, nextLo, unicode.MaxRune)
-	}
-	return r
-}
-
-// ranges implements sort.Interface on a []rune.
-// The choice of receiver type definition is strange
-// but avoids an allocation since we already have
-// a *[]rune.
-type ranges struct {
-	p *[]rune
-}
-
-func (ra ranges) Less(i, j int) bool {
-	p := *ra.p
-	i *= 2
-	j *= 2
-	return p[i] < p[j] || p[i] == p[j] && p[i+1] > p[j+1]
-}
-
-func (ra ranges) Len() int {
-	return len(*ra.p) / 2
-}
-
-func (ra ranges) Swap(i, j int) {
-	p := *ra.p
-	i *= 2
-	j *= 2
-	p[i], p[i+1], p[j], p[j+1] = p[j], p[j+1], p[i], p[i+1]
-}
-
-func checkUTF8(s string) error {
-	for s != "" {
-		rune, size := utf8.DecodeRuneInString(s)
-		if rune == utf8.RuneError && size == 1 {
-			return &Error{Code: ErrInvalidUTF8, Expr: s}
-		}
-		s = s[size:]
-	}
-	return nil
-}
-
-func nextRune(s string) (c rune, t string, err error) {
-	c, size := utf8.DecodeRuneInString(s)
-	if c == utf8.RuneError && size == 1 {
-		return 0, "", &Error{Code: ErrInvalidUTF8, Expr: s}
-	}
-	return c, s[size:], nil
-}
-
-func isalnum(c rune) bool {
-	return '0' <= c && c <= '9' || 'A' <= c && c <= 'Z' || 'a' <= c && c <= 'z'
-}
-
-func unhex(c rune) rune {
-	if '0' <= c && c <= '9' {
-		return c - '0'
-	}
-	if 'a' <= c && c <= 'f' {
-		return c - 'a' + 10
-	}
-	if 'A' <= c && c <= 'F' {
-		return c - 'A' + 10
-	}
-	return -1
-}