Method FactorAlternation

extern/re2/re2/parse.cc:933–1027

Factors common prefixes from alternation. For example, ABC|ABD|AEF|BCX|BCY simplifies to A(B(C|D)|EF)|BC(X|Y) and thence to A(B[CD]|EF)|BC[XY] Rewrites sub to contain simplified list to alternate and returns the new length of sub. Adjusts reference counts accordingly (incoming sub[i] decremented, outgoing sub[i] incremented).

// the new length of sub.  Adjusts reference counts accordingly
// (incoming sub[i] decremented, outgoing sub[i] incremented).
int Regexp::FactorAlternation(Regexp** sub, int nsub, ParseFlags flags) {
  std::vector<Frame> stk;
  stk.emplace_back(sub, nsub);

  for (;;) {
    auto& sub = stk.back().sub;
    auto& nsub = stk.back().nsub;
    auto& round = stk.back().round;
    auto& splices = stk.back().splices;
    auto& spliceidx = stk.back().spliceidx;

    if (splices.empty()) {
      // Advance to the next round of factoring. Note that this covers
      // the initialised state: when splices is empty and round is 0.
      round++;
    } else if (spliceidx < static_cast<int>(splices.size())) {
      // We have at least one more Splice to factor. Recurse logically.
      stk.emplace_back(splices[spliceidx].sub, splices[spliceidx].nsub);
      continue;
    } else {
      // We have no more Splices to factor. Apply them.
      auto iter = splices.begin();
      int out = 0;
      for (int i = 0; i < nsub; ) {
        // Copy until we reach where the next Splice begins.
        while (sub + i < iter->sub)
          sub[out++] = sub[i++];
        switch (round) {
          case 1:
          case 2: {
            // Assemble the Splice prefix and the suffixes.
            Regexp* re[2];
            re[0] = iter->prefix;
            re[1] = Regexp::AlternateNoFactor(iter->sub, iter->nsuffix, flags);
            sub[out++] = Regexp::Concat(re, 2, flags);
            i += iter->nsub;
            break;
          }
          case 3:
            // Just use the Splice prefix.
            sub[out++] = iter->prefix;
            i += iter->nsub;
            break;
          default:
            LOG(DFATAL) << "unknown round: " << round;
            break;
        }
        // If we are done, copy until the end of sub.
        if (++iter == splices.end()) {
          while (i < nsub)
            sub[out++] = sub[i++];
        }
      }
      splices.clear();
      nsub = out;
      // Advance to the next round of factoring.
      round++;
    }