Simplifies the expression re{min,max} in terms of *, +, and ?. Returns a new regexp. Does not edit re. Does not consume reference to re. Caller must Decref return value when done with it. The result will *not* necessarily have the right capturing parens if you call ToString() and re-parse it: (x){2} becomes (x)(x), but in the Regexp* representation, both (x) are marked as $1.
| 587 | // if you call ToString() and re-parse it: (x){2} becomes (x)(x), |
| 588 | // but in the Regexp* representation, both (x) are marked as $1. |
| 589 | Regexp* SimplifyWalker::SimplifyRepeat(Regexp* re, int min, int max, |
| 590 | Regexp::ParseFlags f) { |
| 591 | // x{n,} means at least n matches of x. |
| 592 | if (max == -1) { |
| 593 | // Special case: x{0,} is x* |
| 594 | if (min == 0) |
| 595 | return Regexp::Star(re->Incref(), f); |
| 596 | |
| 597 | // Special case: x{1,} is x+ |
| 598 | if (min == 1) |
| 599 | return Regexp::Plus(re->Incref(), f); |
| 600 | |
| 601 | // General case: x{4,} is xxxx+ |
| 602 | PODArray<Regexp*> nre_subs(min); |
| 603 | for (int i = 0; i < min-1; i++) |
| 604 | nre_subs[i] = re->Incref(); |
| 605 | nre_subs[min-1] = Regexp::Plus(re->Incref(), f); |
| 606 | return Regexp::Concat(nre_subs.data(), min, f); |
| 607 | } |
| 608 | |
| 609 | // Special case: (x){0} matches only empty string. |
| 610 | if (min == 0 && max == 0) |
| 611 | return new Regexp(kRegexpEmptyMatch, f); |
| 612 | |
| 613 | // Special case: x{1} is just x. |
| 614 | if (min == 1 && max == 1) |
| 615 | return re->Incref(); |
| 616 | |
| 617 | // General case: x{n,m} means n copies of x and m copies of x?. |
| 618 | // The machine will do less work if we nest the final m copies, |
| 619 | // so that x{2,5} = xx(x(x(x)?)?)? |
| 620 | |
| 621 | // Build leading prefix: xx. Capturing only on the last one. |
| 622 | Regexp* nre = NULL; |
| 623 | if (min > 0) { |
| 624 | PODArray<Regexp*> nre_subs(min); |
| 625 | for (int i = 0; i < min; i++) |
| 626 | nre_subs[i] = re->Incref(); |
| 627 | nre = Regexp::Concat(nre_subs.data(), min, f); |
| 628 | } |
| 629 | |
| 630 | // Build and attach suffix: (x(x(x)?)?)? |
| 631 | if (max > min) { |
| 632 | Regexp* suf = Regexp::Quest(re->Incref(), f); |
| 633 | for (int i = min+1; i < max; i++) |
| 634 | suf = Regexp::Quest(Concat2(re->Incref(), suf, f), f); |
| 635 | if (nre == NULL) |
| 636 | nre = suf; |
| 637 | else |
| 638 | nre = Concat2(nre, suf, f); |
| 639 | } |
| 640 | |
| 641 | if (nre == NULL) { |
| 642 | // Some degenerate case, like min > max, or min < max < 0. |
| 643 | // This shouldn't happen, because the parser rejects such regexps. |
| 644 | LOG(DFATAL) << "Malformed repeat " << re->ToString() << " " << min << " " << max; |
| 645 | return new Regexp(kRegexpNoMatch, f); |
| 646 | } |