More automaton translation

- Implemented some more translation from asts to automata, including
  upper/lower bounded repetition, captures, positive and negative
  forward assertions, etc.
- Un-templateified automaton nodes.

[Christian Plesner Hansen, 2008-11-06 15:24:58]

I'll attach an example of the output from the graph translation in an email
follow-up to this code review.

[Lasse Reichstein, 2008-11-06 16:46:44]

LGTM, with questions. I will need an explanation :)

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

http://codereview.chromium.org/9638/diff/1/2#newcode1216
Line 1216: virtual RegExpNode* ToNode(RegExpCompiler* compiler,
Could this be a Visitor instead?

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

http://codereview.chromium.org/9638/diff/1/4#newcode1057
Line 1057: //
Do you test that x didn't match the empty string while t <= r < f ?
That would seem to require an extra register to store the position before x and
test for progress after it.
We also need to clear captures in x between loops.

http://codereview.chromium.org/9638/diff/1/4#newcode1061
Line 1061: int reg = needs_counter ? compiler->AllocateRegister() : -1;
The case where min = 0 and max = 1 (i.e., the '?' quantifier) doesn't need a
loop and could be generated as a simple choice node.
Also, if x is known to be simple and max is low, it might be more efficient to
unroll the loop. But that's an optimization for later.

http://codereview.chromium.org/9638/diff/1/4#newcode1121
Line 1121: RegExpNode* proceed = ActionNode::EndSubmatch(on_success);
What does the Submatch concept cover?
Why isn't a positive lookahead the same as any other expression to match, except
that the on_success goes to a node that restores the position before continuing?
(I.e., am I missing a complexity here?)

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

http://codereview.chromium.org/9638/diff/1/5#newcode323
Line 323: };
What!?! No third out-parameter? ;)
Good call.

[Christian Plesner Hansen, 2008-11-06 17:34:42]

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

http://codereview.chromium.org/9638/diff/1/2#newcode1216
Line 1216: virtual RegExpNode* ToNode(RegExpCompiler* compiler,
It used to be but when I wanted to add the on_failure argument it became
unmanageable.

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

http://codereview.chromium.org/9638/diff/1/4#newcode1057
Line 1057: //
Good points all -- I'm just adding TODOs for now.

http://codereview.chromium.org/9638/diff/1/4#newcode1061
Line 1061: int reg = needs_counter ? compiler->AllocateRegister() : -1;
Yes.  My idea was to add a few transformations at parse time to turn <x>? into
(?:|<x>) and <x>+ into <x><x>*.

http://codereview.chromium.org/9638/diff/1/4#newcode1121
Line 1121: RegExpNode* proceed = ActionNode::EndSubmatch(on_success);
This is based on a long discussion I had with Erik and we're pretty confident
that this matches the specified semantics though something simpler may also
work.

What sets lookahead apart from other expressions (well, one of the things) is
that you're not allowed to backtrack into lookahead once you've completed it;
it's on page 139 in the spec.  In the positive case (and the negative is the
same in principle) you may use backtracking as part of matching the lookahead
itself, but once you've found a match you have to clear any pending backtracks
that were set up to avoid backtracking back into the lookahead again later. 
That's what a submatch does: basically sets up a "scope" where you can push any
number of backtracks you want but if the need arises you can zap them all in one
go using EscapeSubmatch.