Source file src/pkg/regexp/syntax/simplify.go

     1	// Copyright 2011 The Go Authors.  All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package syntax
     6	
     7	// Simplify returns a regexp equivalent to re but without counted repetitions
     8	// and with various other simplifications, such as rewriting /(?:a+)+/ to /a+/.
     9	// The resulting regexp will execute correctly but its string representation
    10	// will not produce the same parse tree, because capturing parentheses
    11	// may have been duplicated or removed.  For example, the simplified form
    12	// for /(x){1,2}/ is /(x)(x)?/ but both parentheses capture as $1.
    13	// The returned regexp may share structure with or be the original.
    14	func (re *Regexp) Simplify() *Regexp {
    15		if re == nil {
    16			return nil
    17		}
    18		switch re.Op {
    19		case OpCapture, OpConcat, OpAlternate:
    20			// Simplify children, building new Regexp if children change.
    21			nre := re
    22			for i, sub := range re.Sub {
    23				nsub := sub.Simplify()
    24				if nre == re && nsub != sub {
    25					// Start a copy.
    26					nre = new(Regexp)
    27					*nre = *re
    28					nre.Rune = nil
    29					nre.Sub = append(nre.Sub0[:0], re.Sub[:i]...)
    30				}
    31				if nre != re {
    32					nre.Sub = append(nre.Sub, nsub)
    33				}
    34			}
    35			return nre
    36	
    37		case OpStar, OpPlus, OpQuest:
    38			sub := re.Sub[0].Simplify()
    39			return simplify1(re.Op, re.Flags, sub, re)
    40	
    41		case OpRepeat:
    42			// Special special case: x{0} matches the empty string
    43			// and doesn't even need to consider x.
    44			if re.Min == 0 && re.Max == 0 {
    45				return &Regexp{Op: OpEmptyMatch}
    46			}
    47	
    48			// The fun begins.
    49			sub := re.Sub[0].Simplify()
    50	
    51			// x{n,} means at least n matches of x.
    52			if re.Max == -1 {
    53				// Special case: x{0,} is x*.
    54				if re.Min == 0 {
    55					return simplify1(OpStar, re.Flags, sub, nil)
    56				}
    57	
    58				// Special case: x{1,} is x+.
    59				if re.Min == 1 {
    60					return simplify1(OpPlus, re.Flags, sub, nil)
    61				}
    62	
    63				// General case: x{4,} is xxxx+.
    64				nre := &Regexp{Op: OpConcat}
    65				nre.Sub = nre.Sub0[:0]
    66				for i := 0; i < re.Min-1; i++ {
    67					nre.Sub = append(nre.Sub, sub)
    68				}
    69				nre.Sub = append(nre.Sub, simplify1(OpPlus, re.Flags, sub, nil))
    70				return nre
    71			}
    72	
    73			// Special case x{0} handled above.
    74	
    75			// Special case: x{1} is just x.
    76			if re.Min == 1 && re.Max == 1 {
    77				return sub
    78			}
    79	
    80			// General case: x{n,m} means n copies of x and m copies of x?
    81			// The machine will do less work if we nest the final m copies,
    82			// so that x{2,5} = xx(x(x(x)?)?)?
    83	
    84			// Build leading prefix: xx.
    85			var prefix *Regexp
    86			if re.Min > 0 {
    87				prefix = &Regexp{Op: OpConcat}
    88				prefix.Sub = prefix.Sub0[:0]
    89				for i := 0; i < re.Min; i++ {
    90					prefix.Sub = append(prefix.Sub, sub)
    91				}
    92			}
    93	
    94			// Build and attach suffix: (x(x(x)?)?)?
    95			if re.Max > re.Min {
    96				suffix := simplify1(OpQuest, re.Flags, sub, nil)
    97				for i := re.Min + 1; i < re.Max; i++ {
    98					nre2 := &Regexp{Op: OpConcat}
    99					nre2.Sub = append(nre2.Sub0[:0], sub, suffix)
   100					suffix = simplify1(OpQuest, re.Flags, nre2, nil)
   101				}
   102				if prefix == nil {
   103					return suffix
   104				}
   105				prefix.Sub = append(prefix.Sub, suffix)
   106			}
   107			if prefix != nil {
   108				return prefix
   109			}
   110	
   111			// Some degenerate case like min > max or min < max < 0.
   112			// Handle as impossible match.
   113			return &Regexp{Op: OpNoMatch}
   114		}
   115	
   116		return re
   117	}
   118	
   119	// simplify1 implements Simplify for the unary OpStar,
   120	// OpPlus, and OpQuest operators.  It returns the simple regexp
   121	// equivalent to
   122	//
   123	//	Regexp{Op: op, Flags: flags, Sub: {sub}}
   124	//
   125	// under the assumption that sub is already simple, and
   126	// without first allocating that structure.  If the regexp
   127	// to be returned turns out to be equivalent to re, simplify1
   128	// returns re instead.
   129	//
   130	// simplify1 is factored out of Simplify because the implementation
   131	// for other operators generates these unary expressions.
   132	// Letting them call simplify1 makes sure the expressions they
   133	// generate are simple.
   134	func simplify1(op Op, flags Flags, sub, re *Regexp) *Regexp {
   135		// Special case: repeat the empty string as much as
   136		// you want, but it's still the empty string.
   137		if sub.Op == OpEmptyMatch {
   138			return sub
   139		}
   140		// The operators are idempotent if the flags match.
   141		if op == sub.Op && flags&NonGreedy == sub.Flags&NonGreedy {
   142			return sub
   143		}
   144		if re != nil && re.Op == op && re.Flags&NonGreedy == flags&NonGreedy && sub == re.Sub[0] {
   145			return re
   146		}
   147	
   148		re = &Regexp{Op: op, Flags: flags}
   149		re.Sub = append(re.Sub0[:0], sub)
   150		return re
   151	}