[regexp] break recursion in mutually recursive capture/back references.

[regexp] break recursion in mutually recursive capture/back references.

TBR=adamk@chromium.org
R=erik.corry@gmail.com
BUG=v8:4616
LOG=N

Committed: https://crrev.com/44a8fec8a1d101e90f429dcd4828e930ee690b71
Cr-Commit-Position: refs/heads/master@{#32879}

[Yang, 2015-12-15 07:55:35]

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

[commit-bot: I haz the power, 2015-12-15 07:55:40]

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

[erikcorry, 2015-12-15 08:09:19]

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

[erikcorry, 2015-12-15 08:09:19]

https://codereview.chromium.org/1522353002/diff/1/src/ast/ast.cc
File src/ast/ast.cc (right):

https://codereview.chromium.org/1522353002/diff/1/src/ast/ast.cc#newcode929
src/ast/ast.cc:929: int RegExpBackReference::max_match() {
Alternative simpler implementation is to return kInfinity here.

https://codereview.chromium.org/1522353002/diff/1/test/mjsunit/regexp.js
File test/mjsunit/regexp.js (right):

https://codereview.chromium.org/1522353002/diff/1/test/mjsunit/regexp.js#newc...
test/mjsunit/regexp.js:728: assertEquals(["a", "", ""],
/(\2).(\1)/.exec("aba"));
Can we also test:

/(.\2).(\1)/

and

/w(.\2)x(\1)$/

which should match "foo....wyxy"

This tests cases where there is mutual recursion, but the max length is not
zero.

[Yang, 2015-12-15 08:15:58]

On 2015/12/15 08:09:19, erikcorry wrote:
> https://codereview.chromium.org/1522353002/diff/1/src/ast/ast.cc
> File src/ast/ast.cc (right):
> 
> https://codereview.chromium.org/1522353002/diff/1/src/ast/ast.cc#newcode929
> src/ast/ast.cc:929: int RegExpBackReference::max_match() {
> Alternative simpler implementation is to return kInfinity here.
> 
> https://codereview.chromium.org/1522353002/diff/1/test/mjsunit/regexp.js
> File test/mjsunit/regexp.js (right):
> 
>
https://codereview.chromium.org/1522353002/diff/1/test/mjsunit/regexp.js#newc...
> test/mjsunit/regexp.js:728: assertEquals(["a", "", ""],
> /(\2).(\1)/.exec("aba"));
> Can we also test:
> 
> /(.\2).(\1)/
> 
> and
> 
> /w(.\2)x(\1)$/
> 
> which should match "foo....wyxy"
> 
> This tests cases where there is mutual recursion, but the max length is not
> zero.

Added suggested tests. The max length of the captures are not 0, but the max
length of the back references are.

[erikcorry, 2015-12-15 08:37:48]

I wonder if we can add lookbehind tests.  We don't really use the max length in
a lookbehind, so it may be impossible to test, or it may not matter whether we
calculate the max length correctly.

https://codereview.chromium.org/1522353002/diff/40001/src/ast/ast.cc
File src/ast/ast.cc (right):

https://codereview.chromium.org/1522353002/diff/40001/src/ast/ast.cc#newcode946
src/ast/ast.cc:946: // exist. Hence the length is 0.
This comment doesn't make sense.

[erikcorry, 2015-12-15 09:45:43]

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc
File src/ast/ast.cc (right):

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc#newcode934
src/ast/ast.cc:934: // Such captures cannot be satisfied and have the length 0.
This may well just be a bug in a comment, but here's a recursion that can be
satisfied and has a length not == 0.

/(x\2)(y\1)$/.test("...xyx")   // True

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc#newcode1123
src/ast/ast.cc:1123: min_match_ = first_alternative->min_match();
This looks a bit dodgy.  We are not done calculating it, but we overwrite the
kUninitialized already here?  I think we should write kRecursionMarker here,
then accumulate it in a temporary variable and overwrite the recursion marker at
the end.

Think about:

(foo|bar|baz|(\1)|\2)

or maybe don't.  It made my head hurt and didn't bring enlightenment.

[Yang, 2015-12-15 09:52:18]

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc
File src/ast/ast.cc (right):

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc#newcode934
src/ast/ast.cc:934: // Such captures cannot be satisfied and have the length 0.
On 2015/12/15 09:45:43, erikcorry wrote:
> This may well just be a bug in a comment, but here's a recursion that can be
> satisfied and has a length not == 0.
> 
> /(x\2)(y\1)$/.test("...xyx")   // True
> 

You are right. It should be "Such back references must have the length 0".

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc#newcode1123
src/ast/ast.cc:1123: min_match_ = first_alternative->min_match();
On 2015/12/15 09:45:43, erikcorry wrote:
> This looks a bit dodgy.  We are not done calculating it, but we overwrite the
> kUninitialized already here?  I think we should write kRecursionMarker here,
> then accumulate it in a temporary variable and overwrite the recursion marker
at
> the end.
> 
> Think about:
> 
> (foo|bar|baz|(\1)|\2)
> 
> or maybe don't.  It made my head hurt and didn't bring enlightenment.

I think this is fine. We can only have a recursion if both capture and back
references are involved. In that case however we would already catch the
recursion inside the call.

[erikcorry, 2015-12-15 10:18:18]

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc
File src/ast/ast.cc (right):

https://codereview.chromium.org/1522353002/diff/60001/src/ast/ast.cc#newcode934
src/ast/ast.cc:934: // Such captures cannot be satisfied and have the length 0.
On 2015/12/15 09:52:18, Yang wrote:
> On 2015/12/15 09:45:43, erikcorry wrote:
> > This may well just be a bug in a comment, but here's a recursion that can be
> > satisfied and has a length not == 0.
> > 
> > /(x\2)(y\1)$/.test("...xyx")   // True
> > 
> 
> You are right. It should be "Such back references must have the length 0".

My example regexp seems to contradict the revised version of the comment still.

[erikcorry, 2015-12-15 10:37:45]

lgtm

[Yang, 2015-12-15 10:41:05]

On 2015/12/15 10:37:45, erikcorry wrote:
> lgtm

Adam, could I get a ell-gee-tee-em from you as well? Thanks.

[Yang, 2015-12-15 12:20:20]

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

[commit-bot: I haz the power, 2015-12-15 12:20:30]

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

[commit-bot: I haz the power, 2015-12-15 12:42:18]

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

[commit-bot: I haz the power, 2015-12-15 12:42:19]

Dry run: This issue passed the CQ dry run.

[Yang, 2015-12-16 06:57:18]

Description was changed from

==========
[regexp] break recursion in mutually recursive capture/back references.

R=adamk@chromium.org, erik.corry@gmail.com
BUG=v8:4616
LOG=N
==========

to

==========
[regexp] break recursion in mutually recursive capture/back references.

TBR=adamk@chromium.org
R=erik.corry@gmail.com
BUG=v8:4616
LOG=N
==========

[Yang, 2015-12-16 06:57:22]

The CQ bit was checked by yangguo@chromium.org

[Yang, 2015-12-16 06:57:22]

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/1522353002/#ps120001
(title: "new test expectations")

[commit-bot: I haz the power, 2015-12-16 06:57:29]

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

[commit-bot: I haz the power, 2015-12-16 06:58:40]

Description was changed from

==========
[regexp] break recursion in mutually recursive capture/back references.

TBR=adamk@chromium.org
R=erik.corry@gmail.com
BUG=v8:4616
LOG=N
==========

to

==========
[regexp] break recursion in mutually recursive capture/back references.

TBR=adamk@chromium.org
R=erik.corry@gmail.com
BUG=v8:4616
LOG=N
==========

[commit-bot: I haz the power, 2015-12-16 06:58:40]

Committed patchset #7 (id:120001)

[commit-bot: I haz the power, 2015-12-16 06:59:02]

Description was changed from

==========
[regexp] break recursion in mutually recursive capture/back references.

TBR=adamk@chromium.org
R=erik.corry@gmail.com
BUG=v8:4616
LOG=N
==========

to

==========
[regexp] break recursion in mutually recursive capture/back references.

TBR=adamk@chromium.org
R=erik.corry@gmail.com
BUG=v8:4616
LOG=N

Committed: https://crrev.com/44a8fec8a1d101e90f429dcd4828e930ee690b71
Cr-Commit-Position: refs/heads/master@{#32879}
==========

[commit-bot: I haz the power, 2015-12-16 06:59:02]

Patchset 7 (id:??) landed as
https://crrev.com/44a8fec8a1d101e90f429dcd4828e930ee690b71
Cr-Commit-Position: refs/heads/master@{#32879}

[adamk, 2015-12-16 08:47:38]

lgtm