Source: simplify.go in package regexp/syntax


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 {

Simplify children, building new Regexp if children change.

		nre := re
		for i, sub := range re.Sub {
			nsub := sub.Simplify()

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)

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.

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.

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