code review 4538123: exp/regexp/syntax: syntax data structures, parser

src/pkg/exp/regexp/syntax/parse.go

 // 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"
@@ skipping 42 matching lines @@
 
 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

[Sam, 2011/06/10 00:14:55]

I'm kind of confused as to why you need this in this way, and don't need a
parallel for ^ vs \a - it's clearly for use in a follow-up CL. I suspect you
know what you're doing :)

[rsc, 2011/06/10 00:27:38]

In Perl, there is \Z (match end of text or right before \n at end of text)
and then there is \z (end of text only).  
In Perl single-line mode $ means \Z, but we don't
support \Z, so in our single-line mode we map $ to \z.  If we every want
to run tests against PCRE to make sure we get the same answers,
it's important to know if a particular OpEndText was a $, because then
we should expect our library and PCRE to disagree once in a while
about whether something matches.

There is no equivalent for ^ and \A because Perl didn't screw up \A.

         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
@@ skipping 76 matching lines @@
                 re = &Regexp{Op: OpConcat}
                 re.Sub = append(re.Sub0[:0], sub...)
         }
         return p.push(re)
 }
 
 // alternate replaces the top of the stack (above the topmost '(') with its alternation.
 func (p *parser) alternate() *Regexp {
         // TODO: Flatten alternates.
 
-        // Scan down to find pseudo-operator | or (.
+        // Scan down to find pseudo-operator (.
+        // There are no | above (.
         i := len(p.stack)
         for i > 0 && p.stack[i-1].Op < opPseudo {
                 i--
         }
         sub := p.stack[i:]
         p.stack = p.stack[:i]
 
         var re *Regexp
         switch len(sub) {
         case 0:
@@ skipping 24 matching lines @@
                         if len(re.Rune) >= cap(re.Rune) {
                                 // string is too long to fit in Rune0.  let Go handle it
                                 re.Rune = []int(s)
                                 break
                         }
                         re.Rune = append(re.Rune, c)
                 }
                 return re, nil
         }
 
-        // Otherwise, have to do real work.
+        // Otherwise, must do real work.
         var (
                 p   parser
                 err os.Error
                 c   int
                 op  Op
         )
         p.flags = flags
         p.wholeRegexp = s
         t := s
         for t != "" {
@@ skipping 173 matching lines @@
                 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 // ] is okay as first char in class
+        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
 
                 // TODO: Look for [:alnum:]
@@ skipping 135 matching lines @@
         return nil
 }
 
 func nextRune(s string) (c int, t string, err os.Error) {
         c, size := utf8.DecodeRuneInString(s)
         if c == utf8.RuneError && size == 1 {
                 return 0, "", &Error{Code: ErrInvalidUTF8, Expr: s}
         }
         return c, s[size:], nil
 }