Class Simplify

java/com/google/re2j/Simplify.java:14–178

import java.util.ArrayList;

class Simplify {

  // 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.
  static Regexp simplify(Regexp re) {
    if (re == null) {
      return null;
    }
    switch (re.op) {
      case CAPTURE:
      case CONCAT:
      case ALTERNATE:
        {
          // Simplify children, building new Regexp if children change.
          Regexp nre = re;
          for (int i = 0; i < re.subs.length; ++i) {
            Regexp sub = re.subs[i];
            Regexp nsub = simplify(sub);
            if (nre == re && nsub != sub) {
              // Start a copy.
              nre = new Regexp(re); // shallow copy
              nre.runes = null;
              nre.subs = Parser.subarray(re.subs, 0, re.subs.length); // clone
            }
            if (nre != re) {
              nre.subs[i] = nsub;
            }
          }
          return nre;
        }
      case STAR:
      case PLUS:
      case QUEST:
        {
          Regexp sub = simplify(re.subs[0]);
          return simplify1(re.op, re.flags, sub, re);
        }
      case REPEAT:
        {
          // 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 new Regexp(Regexp.Op.EMPTY_MATCH);
          }

          // The fun begins.
          Regexp sub = simplify(re.subs[0]);

          // x{n,} means at least n matches of x.
          if (re.max == -1) {
            // Special case: x{0,} is x*.
            if (re.min == 0) {