code review 4635082: exp/regexp/syntax: finish Regexp manipulation

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"
         "strings"
@@ skipping 283 matching lines @@
                 }
                 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 flattened into a single node.

[r, 2011/06/30 03:06:02]

odd line break

+// 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)
@@ skipping 57 matching lines @@
                                 }
                         }
                 }
 
                 // 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 - first iteration.

[r, 2011/06/30 03:06:02]

first iteration has i == 0. you mean something else.

+                        // 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 (if there is one).

[r, 2011/06/30 03:06:02]

delete parenthetical remark

+                // 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
@@ skipping 12 matching lines @@
                         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 - first iteration.

[r, 2011/06/30 03:06:02]

first iteration has i == 0. you mean something else.

+                        // 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 (if there is one).

[r, 2011/06/30 03:06:02]

ditto

+                // 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
+                        // 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
                                 }
@@ skipping 23 matching lines @@
                 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 starts with.

[r, 2011/06/30 03:06:02]

s/re starts with/begins re/

+// 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) ([]int, 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
 }
@@ skipping 28 matching lines @@
 
         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 starts with.
+// 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
                 }
@@ skipping 448 matching lines @@
         // 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 re1 = re1|re2.
-// The caller must ensure that re1.Op > re2.Op.

[r, 2011/06/30 03:06:02]

i'd expect re2.Op > re1.Op

-func mergeCharClass(re1, re2 *Regexp) {
-        switch re1.Op {
+// 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:
-                // re2 doesn't add anything.
+                // src doesn't add anything.
         case OpAnyCharNotNL:
-                // re2 might add \n
-                if matchRune(re2, '\n') {
-                        re1.Op = OpAnyChar
+                // src might add \n
+                if matchRune(src, '\n') {
+                        dst.Op = OpAnyChar
                 }
         case OpCharClass:
-                // re2 is simpler, so either literal or char class
-                if re2.Op == OpLiteral {
-                        re1.Rune = appendRange(re1.Rune, re2.Rune[0], re2.Rune[0])
+                // src is simpler, so either literal or char class
+                if src.Op == OpLiteral {
+                        dst.Rune = appendRange(dst.Rune, src.Rune[0], src.Rune[0])
                 } else {
-                        re1.Rune = appendClass(re1.Rune, re2.Rune)
+                        dst.Rune = appendClass(dst.Rune, src.Rune)
                 }
         case OpLiteral:
                 // both literal
-                if re2.Rune[0] == re1.Rune[0] {
+                if src.Rune[0] == dst.Rune[0] {
                         break
                 }
-                re1.Op = OpCharClass
-                re1.Rune = append(re1.Rune, re1.Rune[0])
-                re1.Rune = appendRange(re1.Rune, re2.Rune[0], re2.Rune[0])
+                dst.Op = OpCharClass
+                dst.Rune = append(dst.Rune, dst.Rune[0])
+                dst.Rune = appendRange(dst.Rune, src.Rune[0], src.Rune[0])
         }
 }
 
 // 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)
@@ skipping 711 matching lines @@
                 return c - '0'
         }
         if 'a' <= c && c <= 'f' {
                 return c - 'a' + 10
         }
         if 'A' <= c && c <= 'F' {
                 return c - 'A' + 10
         }
         return -1
 }