1 // Copyright 2008 The RE2 Authors. All Rights Reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Determine whether this library should match PCRE exactly
6 // for a particular Regexp. (If so, the testing framework can
7 // check that it does.)
9 // This library matches PCRE except in these cases:
10 // * the regexp contains a repetition of an empty string,
11 // like (a*)* or (a*)+. In this case, PCRE will treat
12 // the repetition sequence as ending with an empty string,
13 // while this library does not.
14 // * Perl and PCRE differ on whether \v matches \n.
15 // For historical reasons, this library implements the Perl behavior.
16 // * Perl and PCRE allow $ in one-line mode to match either the very
17 // end of the text or just before a \n at the end of the text.
18 // This library requires it to match only the end of the text.
19 // * Similarly, Perl and PCRE do not allow ^ in multi-line mode to
20 // match the end of the text if the last character is a \n.
21 // This library does allow it.
23 // Regexp::MimicsPCRE checks for any of these conditions.
25 #include "util/util.h"
26 #include "re2/regexp.h"
27 #include "re2/walker-inl.h"
31 // Returns whether re might match an empty string.
32 static bool CanBeEmptyString(Regexp *re);
34 // Walker class to compute whether library handles a regexp
35 // exactly as PCRE would. See comment at top for conditions.
37 class PCREWalker : public Regexp::Walker<bool> {
40 bool PostVisit(Regexp* re, bool parent_arg, bool pre_arg, bool* child_args,
43 bool ShortVisit(Regexp* re, bool a) {
44 // Should never be called: we use Walk not WalkExponential.
45 LOG(DFATAL) << "EmptyStringWalker::ShortVisit called";
50 // Called after visiting each of re's children and accumulating
51 // the return values in child_args. So child_args contains whether
52 // this library mimics PCRE for those subexpressions.
53 bool PCREWalker::PostVisit(Regexp* re, bool parent_arg, bool pre_arg,
54 bool* child_args, int nchild_args) {
55 // If children failed, so do we.
56 for (int i = 0; i < nchild_args; i++)
60 // Otherwise look for other reasons to fail.
62 // Look for repeated empty string.
66 if (CanBeEmptyString(re->sub()[0]))
70 if (re->max() == -1 && CanBeEmptyString(re->sub()[0]))
76 if (re->rune() == '\v')
80 // Look for $ in single-line mode.
82 case kRegexpEmptyMatch:
83 if (re->parse_flags() & Regexp::WasDollar)
87 // Look for ^ in multi-line mode.
88 case kRegexpBeginLine:
89 // No condition: in single-line mode ^ becomes kRegexpBeginText.
100 // Returns whether this regexp's behavior will mimic PCRE's exactly.
101 bool Regexp::MimicsPCRE() {
103 return w.Walk(this, true);
107 // Walker class to compute whether a Regexp can match an empty string.
108 // It is okay to overestimate. For example, \b\B cannot match an empty
109 // string, because \b and \B are mutually exclusive, but this isn't
110 // that smart and will say it can. Spurious empty strings
111 // will reduce the number of regexps we sanity check against PCRE,
112 // but they won't break anything.
114 class EmptyStringWalker : public Regexp::Walker<bool> {
116 EmptyStringWalker() { }
117 bool PostVisit(Regexp* re, bool parent_arg, bool pre_arg,
118 bool* child_args, int nchild_args);
120 bool ShortVisit(Regexp* re, bool a) {
121 // Should never be called: we use Walk not WalkExponential.
122 LOG(DFATAL) << "EmptyStringWalker::ShortVisit called";
127 DISALLOW_EVIL_CONSTRUCTORS(EmptyStringWalker);
130 // Called after visiting re's children. child_args contains the return
131 // value from each of the children's PostVisits (i.e., whether each child
132 // can match an empty string). Returns whether this clause can match an
134 bool EmptyStringWalker::PostVisit(Regexp* re, bool parent_arg, bool pre_arg,
135 bool* child_args, int nchild_args) {
137 case kRegexpNoMatch: // never empty
141 case kRegexpCharClass:
142 case kRegexpLiteralString:
145 case kRegexpEmptyMatch: // always empty
146 case kRegexpBeginLine: // always empty, when they match
148 case kRegexpNoWordBoundary:
149 case kRegexpWordBoundary:
150 case kRegexpBeginText:
152 case kRegexpStar: // can always be empty
154 case kRegexpHaveMatch:
157 case kRegexpConcat: // can be empty if all children can
158 for (int i = 0; i < nchild_args; i++)
163 case kRegexpAlternate: // can be empty if any child can
164 for (int i = 0; i < nchild_args; i++)
169 case kRegexpPlus: // can be empty if the child can
171 return child_args[0];
173 case kRegexpRepeat: // can be empty if child can or is x{0}
174 return child_args[0] || re->min() == 0;
179 // Returns whether re can match an empty string.
180 static bool CanBeEmptyString(Regexp* re) {
182 return w.Walk(re, true);