Newer
Older
// 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"
)
// An Error describes a failure to parse a regular expression
// and gives the offending expression.
type Error struct {
Code ErrorCode
Expr 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 )"
ErrInvalidDepth ErrorCode = "expression nests too deeply"
)
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
)
// maxHeight is the maximum height of a regexp parse tree.
// It is somewhat arbitrarily chosen, but the idea is to be large enough
// that no one will actually hit in real use but at the same time small enough
// that recursion on the Regexp tree will not hit the 1GB Go stack limit.
// The maximum amount of stack for a single recursive frame is probably
// closer to 1kB, so this could potentially be raised, but it seems unlikely
// that people have regexps nested even this deeply.
// We ran a test on Google's C++ code base and turned up only
// a single use case with depth > 100; it had depth 128.
// Using depth 1000 should be plenty of margin.
// As an optimization, we don't even bother calculating heights
// until we've allocated at least maxHeight Regexp structures.
const maxHeight = 1000
type parser struct {
flags Flags // parse mode flags
stack []*Regexp // stack of parsed expressions
free *Regexp
numCap int // number of capturing groups seen
tmpClass []rune // temporary char class work space
numRegexp int // number of regexps allocated
height map[*Regexp]int // regexp height for height limit check
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) {
if p.height != nil {
delete(p.height, re)
}
re.Sub0[0] = p.free
p.free = re
}
func (p *parser) checkHeight(re *Regexp) {
if p.numRegexp < maxHeight {
return
}
if p.height == nil {
p.height = make(map[*Regexp]int)
for _, re := range p.stack {
p.checkHeight(re)
}
}
if p.calcHeight(re, true) > maxHeight {
}
}
func (p *parser) calcHeight(re *Regexp, force bool) int {
if !force {
if h, ok := p.height[re]; ok {
return h
}
}
h := 1
for _, sub := range re.Sub {
hsub := p.calcHeight(sub, false)
if h < 1+hsub {
h = 1 + hsub
}
}
p.height[re] = h
return h
}
// Parse stack manipulation.
// push pushes the regexp re onto the parse stack and returns the regexp.
func (p *parser) push(re *Regexp) *Regexp {
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
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)
// 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.
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
}
// literal pushes a literal regexp for the rune r on the stack.
func (p *parser) literal(r rune) {
re := p.newRegexp(OpLiteral)
re.Flags = p.flags
if p.flags&FoldCase != 0 {
r = minFoldRune(r)
}
re.Rune0[0] = r
re.Rune = re.Rune0[:1]
// minFoldRune returns the minimum rune fold-equivalent to r.
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
}
// 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) {
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)]}
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
if op == OpRepeat && (min >= 2 || max >= 2) && !repeatIsValid(re, 1000) {
return "", &Error{ErrInvalidRepeatSize, before[:len(before)-len(after)]}
}
// repeatIsValid reports whether the repetition re is valid.
// Valid means that the combination of the top-level repetition
// and any inner repetitions does not exceed n copies of the
// innermost thing.
// This function rewalks the regexp tree and is called for every repetition,
// so we have to worry about inducing quadratic behavior in the parser.
// We avoid this by only calling repeatIsValid when min or max >= 2.
// In that case the depth of any >= 2 nesting can only get to 9 without
// triggering a parse error, so each subtree can only be rewalked 9 times.
func repeatIsValid(re *Regexp, n int) bool {
if re.Op == OpRepeat {
m := re.Max
if m == 0 {
return true
}
if m < 0 {
m = re.Min
}
if m > n {
return false
}
if m > 0 {
n /= m
}
}
for _, sub := range re.Sub {
if !repeatIsValid(sub, n) {
return false
}
}
return true
}
// concat replaces the top of the stack (above the topmost '|' or '(') with its concatenation.
func (p *parser) concat() *Regexp {
// Scan down to find pseudo-operator | or (.
i := len(p.stack)
for i > 0 && p.stack[i-1].Op < opPseudo {
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--
}
// 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 {
}
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 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,
// simplifies by literal prefix extraction to
// which simplifies by character class introduction to
func (p *parser) factor(sub []*Regexp) []*Regexp {
if len(sub) < 2 {
return sub
}
// Round 1: Factor out common literal prefixes.
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.
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
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 simple prefixes,
// just the first piece of each concatenation.
// This will be good enough a lot of the time.
//
// Complex subexpressions (e.g. involving quantifiers)
// are not safe to factor because that collapses their
// distinct paths through the automaton, which affects
// correctness in some cases.
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) &&
// first must be a character class OR a fixed repeat of a character class.
(isCharClass(first) || (first.Op == OpRepeat && first.Min == first.Max && isCharClass(first.Sub[0]))) {
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]
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
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.
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
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
break
}
re.Rune = append(re.Rune, c)
}
return re
}
// 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) {
return parse(s, flags)
}
func parse(s string, flags Flags) (_ *Regexp, err error) {
defer func() {
switch r := recover(); r {
default:
panic(r)
case nil:
// ok
case ErrInvalidDepth:
err = &Error{Code: ErrInvalidDepth, Expr: s}
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 (
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
}
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
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
}
if after, err = p.repeat(op, 0, 0, before, after, lastRepeat); err != nil {
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
for lit != "" {
c, rest, err := nextRune(lit)
if err != nil {
return nil, err
}
p.literal(c)
lit = rest
}
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)
}
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