Experimental support for RegExp lookbehind.

Experimental support for RegExp lookbehind.

R=erikcorry@chromium.org, littledan@chromium.org
BUG=v8:4545
LOG=N

Committed: https://crrev.com/37632606bbce1418238b13fd90cb6ef6705871cd
Cr-Commit-Position: refs/heads/master@{#32029}

Committed: https://crrev.com/906903acb558723edf5bf87581c0c37183dc6c46
Cr-Commit-Position: refs/heads/master@{#32043}

[Yang, 2015-11-10 15:40:53]

I have yet to port this to native platforms. And I'd like to resolve the
semantics of backreferences inside lookbehinds. See related V8 issue.

[Yang, 2015-11-11 14:23:57]

On 2015/11/10 15:40:53, Yang wrote:
> I have yet to port this to native platforms. And I'd like to resolve the
> semantics of backreferences inside lookbehinds. See related V8 issue.

Remaining issues resolved.

[erikcorry, 2015-11-11 15:39:04]

erikcorry@google.com changed reviewers:
+ erikcorry@google.com

[erikcorry, 2015-11-11 15:39:05]

Nice.

LGTM apart from the greedy loop thing.  We could commit it as is and do the
greedy loop optimization in a followup.

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc
File src/regexp/jsregexp.cc (right):

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc#...
src/regexp/jsregexp.cc:3404: return read_backward() ?
kNodeIsTooComplexForGreedyLoops : Length();
This is a case where perhaps we do need a little optimization.  If we have a
very simple loop like:

foo.*bar

or

foo(?:bar)*baz

then the naïve solution can use backtracking stack proportional to the length of
the string.  This is why we recognize greedy loops, which should really be
called "greedy loops with a simple fixed width body". In that case we just use
registers and position counting, instead of pushing a bunch of backtracking
commands that all just decrement the current position.

With this change you can use memory proportional to the string size if you
search for:

(?<=foo.*)bar

as it searches backwards from bar to the start of the string, looking for foo. 
This will overflow the backtracking stack for big strings.

In the Fletch change the greedy loop optimization is taken care of even in
backwards mode.

See the Irregexp slide show for details.  Slides 35 to 57 (skip the interlude in
the middle).

By the way in Unicode mode, .* won't be an optimizable greedy loop in any
direction :-/

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc#...
src/regexp/jsregexp.cc:3408: RegExpNode*
TextNode::GetSuccessorOfOmnivorousTextNode(
Not quite sure, but this optimization may have to be switched off for backwards.
 It's basically there to handle the initial skipping forwards-to-find-the-match
part, which will always be forwards.  You can trigger it in the middle with [^]*
though.

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc#...
src/regexp/jsregexp.cc:5306: new (zone) RegExpCharacterClass('n',
RegExpTree::READ_FORWARD);
Yes :-)

Do we have a test of $ and ^ inside lookbehind in a /m regexp?

https://codereview.chromium.org/1418963009/diff/60001/test/cctest/test-regexp.cc
File test/cctest/test-regexp.cc (right):

https://codereview.chromium.org/1418963009/diff/60001/test/cctest/test-regexp...
test/cctest/test-regexp.cc:163: FLAG_harmony_regexp_lookbehind = true;
Probably better to put this whole test in a static function that takes a bool,
and call it:

TEST(Parser) {
  RegexpParserTest(true);
  RegexpParserTest(false);
}

[Yang, 2015-11-12 08:25:35]

I've added a new patch set to address each suggestion.

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc
File src/regexp/jsregexp.cc (right):

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc#...
src/regexp/jsregexp.cc:3404: return read_backward() ?
kNodeIsTooComplexForGreedyLoops : Length();
On 2015/11/11 15:39:04, erikcorry wrote:
> This is a case where perhaps we do need a little optimization.  If we have a
> very simple loop like:
> 
> foo.*bar
> 
> or
> 
> foo(?:bar)*baz
> 
> then the naïve solution can use backtracking stack proportional to the length
of
> the string.  This is why we recognize greedy loops, which should really be
> called "greedy loops with a simple fixed width body". In that case we just use
> registers and position counting, instead of pushing a bunch of backtracking
> commands that all just decrement the current position.
> 
> With this change you can use memory proportional to the string size if you
> search for:
> 
> (?<=foo.*)bar
> 
> as it searches backwards from bar to the start of the string, looking for foo.

> This will overflow the backtracking stack for big strings.
> 
> In the Fletch change the greedy loop optimization is taken care of even in
> backwards mode.
> 
> See the Irregexp slide show for details.  Slides 35 to 57 (skip the interlude
in
> the middle).
> 
> By the way in Unicode mode, .* won't be an optimizable greedy loop in any
> direction :-/

Done.

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc#...
src/regexp/jsregexp.cc:3408: RegExpNode*
TextNode::GetSuccessorOfOmnivorousTextNode(
On 2015/11/11 15:39:04, erikcorry wrote:
> Not quite sure, but this optimization may have to be switched off for
backwards.
>  It's basically there to handle the initial skipping
forwards-to-find-the-match
> part, which will always be forwards.  You can trigger it in the middle with
[^]*
> though.

I haven't found a test case where this would become an issue. The caller of this
method uses the return value to determine what eats_at_least value to use. But
we already return 0 for nodes that read backward.

I added a line just to be sure.

https://codereview.chromium.org/1418963009/diff/60001/src/regexp/jsregexp.cc#...
src/regexp/jsregexp.cc:5306: new (zone) RegExpCharacterClass('n',
RegExpTree::READ_FORWARD);
On 2015/11/11 15:39:04, erikcorry wrote:
> Yes :-)
> 
> Do we have a test of $ and ^ inside lookbehind in a /m regexp?

Added a couple of tests.

https://codereview.chromium.org/1418963009/diff/60001/test/cctest/test-regexp.cc
File test/cctest/test-regexp.cc (right):

https://codereview.chromium.org/1418963009/diff/60001/test/cctest/test-regexp...
test/cctest/test-regexp.cc:163: FLAG_harmony_regexp_lookbehind = true;
On 2015/11/11 15:39:04, erikcorry wrote:
> Probably better to put this whole test in a static function that takes a bool,
> and call it:
> 
> TEST(Parser) {
>   RegexpParserTest(true);
>   RegexpParserTest(false);
> }

Done.

[Yang, 2015-11-12 09:42:00]

rebase

[Dan Ehrenberg, 2015-11-12 22:25:09]

Looks good at a high level.

[Yang, 2015-11-13 13:55:38]

On 2015/11/12 22:25:09, Dan Ehrenberg wrote:
> Looks good at a high level.

Ported to all required platforms. Do you guys want to take another look?

[erikcorry, 2015-11-13 14:30:13]

https://codereview.chromium.org/1418963009/diff/300001/src/regexp/arm/regexp-...
File src/regexp/arm/regexp-macro-assembler-arm.cc (right):

https://codereview.chromium.org/1418963009/diff/300001/src/regexp/arm/regexp-...
src/regexp/arm/regexp-macro-assembler-arm.cc:697: __ sub(r0, r0, Operand(r1,
LSL, (mode_ == UC16) ? 1 : 0));
This instruction is better than the short for loop with 1 or 2 subs/adds.

https://codereview.chromium.org/1418963009/diff/300001/src/regexp/arm/regexp-...
src/regexp/arm/regexp-macro-assembler-arm.cc:700: __ str(r0,
MemOperand(frame_pointer(), kInputStartMinusOne));
This looks useful.  It's the actual position 1 less than the real start of the
string.  We can use this in the ^-checking code to avoid having to do maths? 
Will also produce more compact code I think.

[Yang, 2015-11-16 14:14:02]

On 2015/11/13 14:30:13, erikcorry wrote:
>
https://codereview.chromium.org/1418963009/diff/300001/src/regexp/arm/regexp-...
> File src/regexp/arm/regexp-macro-assembler-arm.cc (right):
> 
>
https://codereview.chromium.org/1418963009/diff/300001/src/regexp/arm/regexp-...
> src/regexp/arm/regexp-macro-assembler-arm.cc:697: __ sub(r0, r0, Operand(r1,
> LSL, (mode_ == UC16) ? 1 : 0));
> This instruction is better than the short for loop with 1 or 2 subs/adds.
> 
>
https://codereview.chromium.org/1418963009/diff/300001/src/regexp/arm/regexp-...
> src/regexp/arm/regexp-macro-assembler-arm.cc:700: __ str(r0,
> MemOperand(frame_pointer(), kInputStartMinusOne));
> This looks useful.  It's the actual position 1 less than the real start of the
> string.  We can use this in the ^-checking code to avoid having to do maths? 
> Will also produce more compact code I think.

I addressed your comments. Using kInputStartMinusOne is indeed shorter. It
however made no sense to introduce a new local var that holds the negative
string length (which is just a char_size() different than kInputStartMinusOne).
I also renamed it to kStringStartMinusOne to avoid future confusion with
kInputStart.

[Yang, 2015-11-16 14:15:27]

The CQ bit was checked by yangguo@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-11-16 14:15:45]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1418963009/320001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1418963009/320001

[commit-bot: I haz the power, 2015-11-16 14:39:23]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-11-16 14:39:24]

Dry run: This issue passed the CQ dry run.

[erikcorry, 2015-11-16 14:55:39]

Overflow worries.

https://codereview.chromium.org/1418963009/diff/320001/src/regexp/arm/regexp-...
File src/regexp/arm/regexp-macro-assembler-arm.cc (right):

https://codereview.chromium.org/1418963009/diff/320001/src/regexp/arm/regexp-...
src/regexp/arm/regexp-macro-assembler-arm.cc:216: __ sub(r1, r1, r0, SetCC);  //
Length of capture.
If it's a capture in a backwards section, I think the end will be set correctly,
while the start will be set to the start of the string - 1.  So you will get a
very long length here.

I think it would be safer to catch this case explicitly.

https://codereview.chromium.org/1418963009/diff/320001/src/regexp/arm/regexp-...
src/regexp/arm/regexp-macro-assembler-arm.cc:226: __ sub(r2,
current_input_offset(), r1);
For (?<=\1(.*))

The length can be very big and the current_input_offset can be near the start of
the string. This subtraction will put us in a position a long way before the
start of the string, and it might wrap around 0 to a negative value if the
string is large and near the start of memory?

[Yang, 2015-11-17 09:24:28]

https://codereview.chromium.org/1418963009/diff/320001/src/regexp/arm/regexp-...
File src/regexp/arm/regexp-macro-assembler-arm.cc (right):

https://codereview.chromium.org/1418963009/diff/320001/src/regexp/arm/regexp-...
src/regexp/arm/regexp-macro-assembler-arm.cc:216: __ sub(r1, r1, r0, SetCC);  //
Length of capture.
On 2015/11/16 14:55:39, erikcorry wrote:
> If it's a capture in a backwards section, I think the end will be set
correctly,
> while the start will be set to the start of the string - 1.  So you will get a
> very long length here.
> 
> I think it would be safer to catch this case explicitly.


I checked, and you are right. This can happen. But only if we got a
backreference inside the capture it references to. Regardless of read direction
however, backreferences like these will refer to captures that have not captured
anything yet.

So I addressed this issue in the parser and reintroduced the previous short-cut
in a slightly different way. If the backreference is inside the capture it
references to, it's parsed as RegExpEmpty.

https://codereview.chromium.org/1418963009/diff/320001/src/regexp/arm/regexp-...
src/regexp/arm/regexp-macro-assembler-arm.cc:226: __ sub(r2,
current_input_offset(), r1);
On 2015/11/16 14:55:39, erikcorry wrote:
> For (?<=\1(.*))
> 
> The length can be very big and the current_input_offset can be near the start
of
> the string. This subtraction will put us in a position a long way before the
> start of the string, and it might wrap around 0 to a negative value if the
> string is large and near the start of memory?

Nice catch.

I changed this so that we add the capture length to kStringStartMinusOne
instead.

[erikcorry, 2015-11-17 10:19:17]

lgtm

[Yang, 2015-11-17 10:22:41]

The CQ bit was checked by yangguo@chromium.org

[commit-bot: I haz the power, 2015-11-17 10:22:56]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1418963009/340001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1418963009/340001

[commit-bot: I haz the power, 2015-11-17 11:14:41]

Committed patchset #18 (id:340001)

[commit-bot: I haz the power, 2015-11-17 11:15:23]

Patchset 18 (id:??) landed as
https://crrev.com/37632606bbce1418238b13fd90cb6ef6705871cd
Cr-Commit-Position: refs/heads/master@{#32029}

[Yang, 2015-11-17 11:54:47]

A revert of this CL (patchset #18 id:340001) has been created in
https://codereview.chromium.org/1451373003/ by yangguo@chromium.org.

The reason for reverting is: gc stress breaks due to string_start_minus_one not
being set correctly..

[Yang, 2015-11-17 11:54:47]

Description was changed from

==========
Experimental support for RegExp lookbehind.

R=erikcorry@chromium.org, littledan@chromium.org
BUG=v8:4545
LOG=N

Committed: https://crrev.com/37632606bbce1418238b13fd90cb6ef6705871cd
Cr-Commit-Position: refs/heads/master@{#32029}
==========

to

==========
Experimental support for RegExp lookbehind.

R=erikcorry@chromium.org, littledan@chromium.org
BUG=v8:4545
LOG=N

Committed: https://crrev.com/37632606bbce1418238b13fd90cb6ef6705871cd
Cr-Commit-Position: refs/heads/master@{#32029}
==========

[Yang, 2015-11-17 12:58:50]

The CQ bit was checked by yangguo@chromium.org

[Yang, 2015-11-17 12:58:51]

The patchset sent to the CQ was uploaded after l-g-t-m from erikcorry@google.com
Link to the patchset: https://codereview.chromium.org/1418963009/#ps360001
(title: "fix arm64 debug code assertion")

[commit-bot: I haz the power, 2015-11-17 12:58:59]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1418963009/360001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1418963009/360001

[commit-bot: I haz the power, 2015-11-17 13:33:08]

Committed patchset #19 (id:360001)

[commit-bot: I haz the power, 2015-11-17 13:33:43]

Patchset 19 (id:??) landed as
https://crrev.com/906903acb558723edf5bf87581c0c37183dc6c46
Cr-Commit-Position: refs/heads/master@{#32043}