Skip to content
Snippets Groups Projects
parse.go 44.5 KiB
Newer Older
  • Learn to ignore specific revisions
  • // 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 (
    	"os"
    	"sort"
    
    	"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) String() 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"
    )
    
    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
    
    Russ Cox's avatar
    Russ Cox committed
    	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.
    
    Russ Cox's avatar
    Russ Cox committed
    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
    
    Russ Cox's avatar
    Russ Cox committed
    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.
    
    Russ Cox's avatar
    Russ Cox committed
    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.
    
    Russ Cox's avatar
    Russ Cox committed
    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, os.Error) {
    
    Russ Cox's avatar
    Russ Cox committed
    	flags := p.flags
    	if p.flags&PerlX != 0 {
    
    		if len(after) > 0 && after[0] == '?' {
    			after = after[1:]
    
    Russ Cox's avatar
    Russ Cox committed
    			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.
    
    Russ Cox's avatar
    Russ Cox committed
    	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.
    
    Russ Cox's avatar
    Russ Cox committed
    		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.
    
    Russ Cox's avatar
    Russ Cox committed
    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
    
    Russ Cox's avatar
    Russ Cox committed
    			re.Rune = []rune(s)
    
    			break
    		}
    		re.Rune = append(re.Rune, c)
    	}
    	return re
    }
    
    
    // Parsing.
    
    func Parse(s string, flags Flags) (*Regexp, os.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        os.Error
    
    Russ Cox's avatar
    Russ Cox committed
    		c          rune
    
    		op         Op
    		lastRepeat string
    		min, max   int
    
    	)
    	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 '*', '+', '?':
    
    			switch t[0] {
    			case '*':
    				op = OpStar
    			case '+':
    				op = OpPlus
    			case '?':
    				op = OpQuest
    			}
    
    			after := t[1:]
    			if after, err = p.repeat(op, min, max, before, after, lastRepeat); err != nil {
    
    Russ Cox's avatar
    Russ Cox committed
    				return nil, err
    			}
    
    			repeat = before
    			t = after
    
    			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 {
    
    			repeat = before
    			t = after
    
    			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
    			}
    
    
    			// 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 {
    
    		} 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 os.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.
    
    Russ Cox's avatar
    Russ Cox committed
    	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.