Method Round3

extern/re2/re2/parse.cc:1145–1198

}

void FactorAlternationImpl::Round3(Regexp** sub, int nsub,
                                   Regexp::ParseFlags flags,
                                   std::vector<Splice>* splices) {
  // Round 3: Merge runs of literals and/or character classes.
  int start = 0;
  Regexp* first = NULL;
  for (int i = 0; i <= nsub; i++) {
    // Invariant: sub[start:i] consists of regexps that all
    // are either literals (i.e. runes) or character classes.
    Regexp* first_i = NULL;
    if (i < nsub) {
      first_i = sub[i];
      if (first != NULL &&
          (first->op() == kRegexpLiteral ||
           first->op() == kRegexpCharClass) &&
          (first_i->op() == kRegexpLiteral ||
           first_i->op() == kRegexpCharClass))
        continue;
    }

    // Found end of a run of Literal/CharClass:
    // sub[start:i] all are either one or the other,
    // but sub[i] is not.
    if (i == start) {
      // Nothing to do - first iteration.
    } else if (i == start+1) {
      // Just one: don't bother factoring.
    } else {
      CharClassBuilder ccb;
      for (int j = start; j < i; j++) {
        Regexp* re = sub[j];
        if (re->op() == kRegexpCharClass) {
          CharClass* cc = re->cc();
          for (CharClass::iterator it = cc->begin(); it != cc->end(); ++it)
            ccb.AddRange(it->lo, it->hi);
        } else if (re->op() == kRegexpLiteral) {
          ccb.AddRangeFlags(re->rune(), re->rune(), re->parse_flags());
        } else {
          LOG(DFATAL) << "RE2: unexpected op: " << re->op() << " "
                      << re->ToString();
        }
        re->Decref();
      }
      Regexp* re = Regexp::NewCharClass(ccb.GetCharClass(), flags);
      splices->emplace_back(re, sub + start, i - start);
    }

    // Prepare for next iteration (if there is one).
    if (i < nsub) {
      start = i;
      first = first_i;
    }
  }
}

// Collapse the regexps on top of the stack, down to the
// first marker, into a new op node (op == kRegexpAlternate