Gecko [ 167.86.127.34 ]

Name	Size	Permission
compile.go	6.12 KB	-rw-r--r--
doc.go	5.28 KB	-rw-r--r--
make_perl_groups.pl	2.37 KB	-rwxr-xr-x
op_string.go	663 B	-rw-r--r--
parse.go	46.15 KB	-rw-r--r--
parse_test.go	14.46 KB	-rw-r--r--
perl_groups.go	2.35 KB	-rw-r--r--
prog.go	7.48 KB	-rw-r--r--
prog_test.go	1.83 KB	-rw-r--r--
regexp.go	7.67 KB	-rw-r--r--
simplify.go	4.2 KB	-rw-r--r--
simplify_test.go	4.01 KB	-rw-r--r--

Code Editor : simplify.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

// Simplify returns a regexp equivalent to re but without counted repetitions
// and with various other simplifications, such as rewriting /(?:a+)+/ to /a+/.
// The resulting regexp will execute correctly but its string representation
// will not produce the same parse tree, because capturing parentheses
// may have been duplicated or removed. For example, the simplified form
// for /(x){1,2}/ is /(x)(x)?/ but both parentheses capture as $1.
// The returned regexp may share structure with or be the original.
func (re *Regexp) Simplify() *Regexp {
	if re == nil {
		return nil
	}
	switch re.Op {
	case OpCapture, OpConcat, OpAlternate:
		// Simplify children, building new Regexp if children change.
		nre := re
		for i, sub := range re.Sub {
			nsub := sub.Simplify()
			if nre == re && nsub != sub {
				// Start a copy.
				nre = new(Regexp)
				*nre = *re
				nre.Rune = nil
				nre.Sub = append(nre.Sub0[:0], re.Sub[:i]...)
			}
			if nre != re {
				nre.Sub = append(nre.Sub, nsub)
			}
		}
		return nre

case OpStar, OpPlus, OpQuest:
		sub := re.Sub[0].Simplify()
		return simplify1(re.Op, re.Flags, sub, re)

case OpRepeat:
		// Special special case: x{0} matches the empty string
		// and doesn't even need to consider x.
		if re.Min == 0 && re.Max == 0 {
			return &Regexp{Op: OpEmptyMatch}
		}

// The fun begins.
		sub := re.Sub[0].Simplify()

// x{n,} means at least n matches of x.
		if re.Max == -1 {
			// Special case: x{0,} is x*.
			if re.Min == 0 {
				return simplify1(OpStar, re.Flags, sub, nil)
			}

// Special case: x{1,} is x+.
			if re.Min == 1 {
				return simplify1(OpPlus, re.Flags, sub, nil)
			}

// General case: x{4,} is xxxx+.
			nre := &Regexp{Op: OpConcat}
			nre.Sub = nre.Sub0[:0]
			for i := 0; i < re.Min-1; i++ {
				nre.Sub = append(nre.Sub, sub)
			}
			nre.Sub = append(nre.Sub, simplify1(OpPlus, re.Flags, sub, nil))
			return nre
		}

// Special case x{0} handled above.

// Special case: x{1} is just x.
		if re.Min == 1 && re.Max == 1 {
			return sub
		}

// General case: x{n,m} means n copies of x and m copies of x?
		// The machine will do less work if we nest the final m copies,
		// so that x{2,5} = xx(x(x(x)?)?)?

// Build leading prefix: xx.
		var prefix *Regexp
		if re.Min > 0 {
			prefix = &Regexp{Op: OpConcat}
			prefix.Sub = prefix.Sub0[:0]
			for i := 0; i < re.Min; i++ {
				prefix.Sub = append(prefix.Sub, sub)
			}
		}

// Build and attach suffix: (x(x(x)?)?)?
		if re.Max > re.Min {
			suffix := simplify1(OpQuest, re.Flags, sub, nil)
			for i := re.Min + 1; i < re.Max; i++ {
				nre2 := &Regexp{Op: OpConcat}
				nre2.Sub = append(nre2.Sub0[:0], sub, suffix)
				suffix = simplify1(OpQuest, re.Flags, nre2, nil)
			}
			if prefix == nil {
				return suffix
			}
			prefix.Sub = append(prefix.Sub, suffix)
		}
		if prefix != nil {
			return prefix
		}

// Some degenerate case like min > max or min < max < 0.
		// Handle as impossible match.
		return &Regexp{Op: OpNoMatch}
	}

return re
}

// simplify1 implements Simplify for the unary OpStar,
// OpPlus, and OpQuest operators. It returns the simple regexp
// equivalent to
//
//	Regexp{Op: op, Flags: flags, Sub: {sub}}
//
// under the assumption that sub is already simple, and
// without first allocating that structure. If the regexp
// to be returned turns out to be equivalent to re, simplify1
// returns re instead.
//
// simplify1 is factored out of Simplify because the implementation
// for other operators generates these unary expressions.
// Letting them call simplify1 makes sure the expressions they
// generate are simple.
func simplify1(op Op, flags Flags, sub, re *Regexp) *Regexp {
	// Special case: repeat the empty string as much as
	// you want, but it's still the empty string.
	if sub.Op == OpEmptyMatch {
		return sub
	}
	// The operators are idempotent if the flags match.
	if op == sub.Op && flags&NonGreedy == sub.Flags&NonGreedy {
		return sub
	}
	if re != nil && re.Op == op && re.Flags&NonGreedy == flags&NonGreedy && sub == re.Sub[0] {
		return re
	}

re = &Regexp{Op: op, Flags: flags}
	re.Sub = append(re.Sub0[:0], sub)
	return re
}

${this.title}

Code Editor : simplify.go