Method Round1

extern/re2/re2/parse.cc:1029–1079

}

void FactorAlternationImpl::Round1(Regexp** sub, int nsub,
                                   Regexp::ParseFlags flags,
                                   std::vector<Splice>* splices) {
  // Round 1: Factor out common literal prefixes.
  int start = 0;
  Rune* rune = NULL;
  int nrune = 0;
  Regexp::ParseFlags runeflags = Regexp::NoParseFlags;
  for (int i = 0; i <= nsub; i++) {
    // Invariant: sub[start:i] consists of regexps that all
    // begin with rune[0:nrune].
    Rune* rune_i = NULL;
    int nrune_i = 0;
    Regexp::ParseFlags runeflags_i = Regexp::NoParseFlags;
    if (i < nsub) {
      rune_i = Regexp::LeadingString(sub[i], &nrune_i, &runeflags_i);
      if (runeflags_i == runeflags) {
        int same = 0;
        while (same < nrune && same < nrune_i && rune[same] == rune_i[same])
          same++;
        if (same > 0) {
          // Matches at least one rune in current range.  Keep going around.
          nrune = same;
          continue;
        }
      }
    }

    // Found end of a run with common leading literal string:
    // sub[start:i] all begin with rune[0:nrune],
    // but sub[i] does not even begin with rune[0].
    if (i == start) {
      // Nothing to do - first iteration.
    } else if (i == start+1) {
      // Just one: don't bother factoring.
    } else {
      Regexp* prefix = Regexp::LiteralString(rune, nrune, runeflags);
      for (int j = start; j < i; j++)
        Regexp::RemoveLeadingString(sub[j], nrune);
      splices->emplace_back(prefix, sub + start, i - start);
    }

    // Prepare for next iteration (if there is one).
    if (i < nsub) {
      start = i;
      rune = rune_i;
      nrune = nrune_i;
      runeflags = runeflags_i;
    }
  }
}

void FactorAlternationImpl::Round2(Regexp** sub, int nsub,
                                   Regexp::ParseFlags flags,