Regexp: Optimize better in presence of lookaround.

Regexp: Optimize better in presence of lookaround.

Previously the Boyer-Moore-Horspool optimization gave up in the presence of a
submatch.  A submatch is where we record the current position so that we can go
back to it, which is an essential part of the semantics of lookarounds
(lookaheads and lookbehinds).  This has been the case since
Boyer-Moore-Horspool was implemented, but it was overly cautious.

* For positive lookahead it is OK to use the patterns inside the lookahead to
  guide the BMS optimization.
* For positive lookbehind we harmlessly fail to optimize when the patterns
  inside the lookbehind go backwards because TextNode::EatsAtLeast returns 0.
* For negative lookarounds, the NegativeLookaroundChoiceNode::FillInBMInfo method
  (in jsregexp.h) knows to only look at the following pattern.

This is in response to disappointing lookbehind performance in Atom.
See https://github.com/atom/find-and-replace/issues/571

R=yangguo@chromium.org
BUG=

Review-Url: https://codereview.chromium.org/2777583003
Cr-Commit-Position: refs/heads/master@{#44139}
Committed: https://chromium.googlesource.com/v8/v8/+/8df7c2a21b07174c3704894ca1d149b2711dfa58

[Yang, 2017-03-27 07:04:45]

On 2017/03/25 10:53:55, erikcorry wrote:

lgtm.

[erikcorry, 2017-03-27 07:05:36]

The CQ bit was checked by erikcorry@google.com

[commit-bot: I haz the power, 2017-03-27 07:05:41]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-03-27 07:28:56]

CQ is committing da patch.

Bot data: {"patchset_id": 1, "attempt_start_ts": 1490598336488150, "parent_rev":
"cb3174632ee246d830cce969b9abb5e2879d2f58", "commit_rev":
"8df7c2a21b07174c3704894ca1d149b2711dfa58"}

[commit-bot: I haz the power, 2017-03-27 07:29:01]

Description was changed from

==========
Regexp: Optimize better in presence of lookaround.

Previously the Boyer-Moore-Horspool optimization gave up in the presence of a
submatch.  A submatch is where we record the current position so that we can go
back to it, which is an essential part of the semantics of lookarounds
(lookaheads and lookbehinds).  This has been the case since
Boyer-Moore-Horspool was implemented, but it was overly cautious.

* For positive lookahead it is OK to use the patterns inside the lookahead to
  guide the BMS optimization.
* For positive lookbehind we harmlessly fail to optimize when the patterns
  inside the lookbehind go backwards because TextNode::EatsAtLeast returns 0.
* For negative lookarounds, the NegativeLookaroundChoiceNode::FillInBMInfo
method
  (in jsregexp.h) knows to only look at the following pattern.

This is in response to disappointing lookbehind performance in Atom.
See https://github.com/atom/find-and-replace/issues/571

R=yangguo@chromium.org
BUG=
==========

to

==========
Regexp: Optimize better in presence of lookaround.

Previously the Boyer-Moore-Horspool optimization gave up in the presence of a
submatch.  A submatch is where we record the current position so that we can go
back to it, which is an essential part of the semantics of lookarounds
(lookaheads and lookbehinds).  This has been the case since
Boyer-Moore-Horspool was implemented, but it was overly cautious.

* For positive lookahead it is OK to use the patterns inside the lookahead to
  guide the BMS optimization.
* For positive lookbehind we harmlessly fail to optimize when the patterns
  inside the lookbehind go backwards because TextNode::EatsAtLeast returns 0.
* For negative lookarounds, the NegativeLookaroundChoiceNode::FillInBMInfo
method
  (in jsregexp.h) knows to only look at the following pattern.

This is in response to disappointing lookbehind performance in Atom.
See https://github.com/atom/find-and-replace/issues/571

R=yangguo@chromium.org
BUG=

Review-Url: https://codereview.chromium.org/2777583003
Cr-Commit-Position: refs/heads/master@{#44139}
Committed:
https://chromium.googlesource.com/v8/v8/+/8df7c2a21b07174c3704894ca1d149b2711...
==========

[commit-bot: I haz the power, 2017-03-27 07:29:02]

Committed patchset #1 (id:1) as
https://chromium.googlesource.com/v8/v8/+/8df7c2a21b07174c3704894ca1d149b2711...