Some new regexp infrastructure.

Some new regexp infrastructure.  Pretty rudimentary.

[Lasse Reichstein, 2008-10-27 13:12:57]

LGTM. Mainly style comments.

http://codereview.chromium.org/8188/diff/1/2
File src/ast.cc (right):

http://codereview.chromium.org/8188/diff/1/2#newcode197
Line 197: class RegExpUnparser: public RegExpVisitor {
Would be nice with a comment describing the syntax of the unparsed output.

http://codereview.chromium.org/8188/diff/1/2#newcode253
Line 253: stream()->Add("^");
Needs sqiggly quotes around the then-statement or put on same line as the "if".

http://codereview.chromium.org/8188/diff/1/2#newcode257
Line 257: if (first) first = false;
"first" is equivalent to "i == 0", so it can be omitted.

http://codereview.chromium.org/8188/diff/1/3
File src/ast.h (right):

http://codereview.chromium.org/8188/diff/1/3#newcode1236
Line 1236: enum Type { START, END, BOUNDARY, NON_BOUNDARY };
I suggest having both START_OF_INPUT and START_OF_LINE (and ditto for END), to
match the interpretation of "^" in non-multiline/multiline mode. It avoids the
need to carry the multiline flag around at runtime.

http://codereview.chromium.org/8188/diff/1/3#newcode1249
Line 1249: CharacterRange(uc32 from, uc32 to, bool is_special)
Could you document what "is_special" signifies? (or give it a more telling
name).

http://codereview.chromium.org/8188/diff/1/3#newcode1332
Line 1332: class RegExpCapture: public RegExpTree {
I think keeping the index of the capture in the node will make some later
transformations simpler, and make the tree node more self-contained.

http://codereview.chromium.org/8188/diff/1/6
File src/jsregexp.cc (right):

http://codereview.chromium.org/8188/diff/1/6#newcode904
Line 904: PrintF("Popping backtrack on level %i\n",
Move to same line as "if" or wrap in squiggly braces.

http://codereview.chromium.org/8188/diff/1/6#newcode935
Line 935: return false;
Same line as "if" or squiggly braces. 
There are several more cases like this.

http://codereview.chromium.org/8188/diff/1/6#newcode954
Line 954: case '.':
Is just the "." in the initial implicit ".*?"?
Otherwise it doesn't address "." not matching newline in non-multiline mode.
Why is this a special case, and not just the range [\x00-\uffff] (in multiline
mode, or [^\r\n\u2028\u2029] in non-multiline mode).

http://codereview.chromium.org/8188/diff/1/6#newcode986
Line 986: break;
Is there a reason for splitting the if and the while, and not just using:
while(state.Step() || (!state.is_done() && state.Backtrack()));

http://codereview.chromium.org/8188/diff/1/6#newcode1015
Line 1015: Vector<const uc32> input);
Should input really be uc32?

http://codereview.chromium.org/8188/diff/1/7
File src/jsregexp.h (right):

http://codereview.chromium.org/8188/diff/1/7#newcode131
Line 131: class RegExpEngine {
Should inherit AllStatic?

http://codereview.chromium.org/8188/diff/1/9
File src/parser.cc (right):

http://codereview.chromium.org/8188/diff/1/9#newcode3464
Line 3464: max = RegExpQuantifier::kInfinity;
All the other cases has the Advance() call after the assignment. Swapping the
two lines might cause slightly less confusion.

http://codereview.chromium.org/8188/diff/1/9#newcode3595
Line 3595: // other implementations...
So bitter! ;P
Spec says to read as decimal literal *and* treat as back-reference (if valid as
such). It doesn't say to treat it as a character escape at all. What appears to
happen, in at least one browser, is to parse the number as decimal if it could
be a back-reference, and as an octal character escape if it can't be a
back-reference but is an octal number (using as many octal digits as is
available), and as a *literal backslash* if the first digit is 8 or 9. Seems
like a deliberate strategy to never give an error!
Other browsers have different strategies.
Maybe we shouldn't try to be bug-compatible in this particular case.

http://codereview.chromium.org/8188/diff/1/9#newcode3662
Line 3662: uc32 c = ParseCharacterEscape(CHECK_OK);
If we add parsing of back-references, ParseCharacterEscape will not be the same
outside and inside a character class definition. Again, browsers don't agree
what to do anyway.

[Erik Corry, 2008-10-27 14:58:43]

I only skimmed it.  Looks good to me.

http://codereview.chromium.org/8188/diff/1/3
File src/ast.h (right):

http://codereview.chromium.org/8188/diff/1/3#newcode1184
Line 1184: // Regular expressions
full stop

http://codereview.chromium.org/8188/diff/1/3#newcode1266
Line 1266: unsigned from() { return from_; }
ASSERT !special?

http://codereview.chromium.org/8188/diff/1/3#newcode1271
Line 1271: unsigned from_ : 21;
JS Regexps don't handle anything outside the basic plane.  Should these be 16
bit?

http://codereview.chromium.org/8188/diff/1/6
File src/jsregexp.cc (right):

http://codereview.chromium.org/8188/diff/1/6#newcode647
Line 647: // Dot/dotty output
Cool idea :-)

http://codereview.chromium.org/8188/diff/1/9
File src/parser.cc (right):

http://codereview.chromium.org/8188/diff/1/9#newcode3271
Line 3271: return c == '|' || c == ')' || c == '\0';
This probably won't work in the long run, can't JS strings contain nulls?

[Erik Corry, 2008-10-27 14:59:05]

More comments not in the last group for some reason.

[Christian Plesner Hansen, 2008-10-27 18:57:02]

Thanks for all the comments.  I've fixed (almost) all of them and submitted the
code.

http://codereview.chromium.org/8188/diff/1/2
File src/ast.cc (right):

http://codereview.chromium.org/8188/diff/1/2#newcode197
Line 197: class RegExpUnparser: public RegExpVisitor {
I can't be bothered to write the full format but I've added a comment that says
that it prints the trees as sexps.  This code should be moved to the test file
later but I think it will be useful for us at this point to have it as part of
the library as well.

http://codereview.chromium.org/8188/diff/1/2#newcode253
Line 253: stream()->Add("^");
Nope, the style guide allows both forms.  "In general, curly braces are not
required for single-line statements, but they are allowed if you like them".  I
don't like them.

http://codereview.chromium.org/8188/diff/1/2#newcode257
Line 257: if (first) first = false;
Good point.

http://codereview.chromium.org/8188/diff/1/3
File src/ast.h (right):

http://codereview.chromium.org/8188/diff/1/3#newcode1184
Line 1184: // Regular expressions
I copied the banner style from parser.cc which doesn't use periods at the end so
I prefer to leave it as it is.

http://codereview.chromium.org/8188/diff/1/3#newcode1236
Line 1236: enum Type { START, END, BOUNDARY, NON_BOUNDARY };
Good point.

http://codereview.chromium.org/8188/diff/1/3#newcode1249
Line 1249: CharacterRange(uc32 from, uc32 to, bool is_special)
I've renamed it to is_character_class_.

http://codereview.chromium.org/8188/diff/1/3#newcode1271
Line 1271: unsigned from_ : 21;
Yes, and then when we unfold the character classes so we don't need the
is_character_class_ bit we can fit a CharacterRange in a single word.

http://codereview.chromium.org/8188/diff/1/3#newcode1332
Line 1332: class RegExpCapture: public RegExpTree {
The ast nodes that I don't yet convert into nodes are incomplete so once we
start actually using them we'll add the info.

http://codereview.chromium.org/8188/diff/1/6
File src/jsregexp.cc (right):

http://codereview.chromium.org/8188/diff/1/6#newcode954
Line 954: case '.':
This is the general '.'.  However, I don't expect this code to survive long so
it's probably not worth the bother to fix it.

http://codereview.chromium.org/8188/diff/1/6#newcode986
Line 986: break;
No, I've fixed it.

http://codereview.chromium.org/8188/diff/1/6#newcode1015
Line 1015: Vector<const uc32> input);
No.  It was getting late...

http://codereview.chromium.org/8188/diff/1/7
File src/jsregexp.h (right):

http://codereview.chromium.org/8188/diff/1/7#newcode131
Line 131: class RegExpEngine {
Yes.

http://codereview.chromium.org/8188/diff/1/9
File src/parser.cc (right):

http://codereview.chromium.org/8188/diff/1/9#newcode3271
Line 3271: return c == '|' || c == ')' || c == '\0';
Hmm.  I've replaced it with a special kEndMarker which is just a different name
for kBadChar.

http://codereview.chromium.org/8188/diff/1/9#newcode3595
Line 3595: // other implementations...
I think we're free to do whatever we want with \8 and \9 and I suggest we treat
them as '8' and '9'.  Otherwise we're probably stuck with the
octal/decimal-back-reference confusion.

By the way, you forgot to mention leading zeros.  The spec explicitly disallows
them but lo and behold:

  js> /\000011/.test("\x09")
  true

http://codereview.chromium.org/8188/diff/1/9#newcode3662
Line 3662: uc32 c = ParseCharacterEscape(CHECK_OK);
Right, I expect what we'll do is check for backreferences first in the atom
parser and then if we can verify that it isn't one fall through to here.