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  }
   152
View as plain text