| 1079 | } |
| 1080 | |
| 1081 | void FactorAlternationImpl::Round2(Regexp** sub, int nsub, |
| 1082 | Regexp::ParseFlags flags, |
| 1083 | std::vector<Splice>* splices) { |
| 1084 | // Round 2: Factor out common simple prefixes, |
| 1085 | // just the first piece of each concatenation. |
| 1086 | // This will be good enough a lot of the time. |
| 1087 | // |
| 1088 | // Complex subexpressions (e.g. involving quantifiers) |
| 1089 | // are not safe to factor because that collapses their |
| 1090 | // distinct paths through the automaton, which affects |
| 1091 | // correctness in some cases. |
| 1092 | int start = 0; |
| 1093 | Regexp* first = NULL; |
| 1094 | for (int i = 0; i <= nsub; i++) { |
| 1095 | // Invariant: sub[start:i] consists of regexps that all |
| 1096 | // begin with first. |
| 1097 | Regexp* first_i = NULL; |
| 1098 | if (i < nsub) { |
| 1099 | first_i = Regexp::LeadingRegexp(sub[i]); |
| 1100 | if (first != NULL && |
| 1101 | // first must be an empty-width op |
| 1102 | // OR a char class, any char or any byte |
| 1103 | // OR a fixed repeat of a literal, char class, any char or any byte. |
| 1104 | (first->op() == kRegexpBeginLine || |
| 1105 | first->op() == kRegexpEndLine || |
| 1106 | first->op() == kRegexpWordBoundary || |
| 1107 | first->op() == kRegexpNoWordBoundary || |
| 1108 | first->op() == kRegexpBeginText || |
| 1109 | first->op() == kRegexpEndText || |
| 1110 | first->op() == kRegexpCharClass || |
| 1111 | first->op() == kRegexpAnyChar || |
| 1112 | first->op() == kRegexpAnyByte || |
| 1113 | (first->op() == kRegexpRepeat && |
| 1114 | first->min() == first->max() && |
| 1115 | (first->sub()[0]->op() == kRegexpLiteral || |
| 1116 | first->sub()[0]->op() == kRegexpCharClass || |
| 1117 | first->sub()[0]->op() == kRegexpAnyChar || |
| 1118 | first->sub()[0]->op() == kRegexpAnyByte))) && |
| 1119 | Regexp::Equal(first, first_i)) |
| 1120 | continue; |
| 1121 | } |
| 1122 | |
| 1123 | // Found end of a run with common leading regexp: |
| 1124 | // sub[start:i] all begin with first, |
| 1125 | // but sub[i] does not. |
| 1126 | if (i == start) { |
| 1127 | // Nothing to do - first iteration. |
| 1128 | } else if (i == start+1) { |
| 1129 | // Just one: don't bother factoring. |
| 1130 | } else { |
| 1131 | Regexp* prefix = first->Incref(); |
| 1132 | for (int j = start; j < i; j++) |
| 1133 | sub[j] = Regexp::RemoveLeadingRegexp(sub[j]); |
| 1134 | splices->emplace_back(prefix, sub + start, i - start); |
| 1135 | } |
| 1136 | |
| 1137 | // Prepare for next iteration (if there is one). |
| 1138 | if (i < nsub) { |