• erikcorry's avatar
    Regexp: Optimize better in presence of lookaround. · 8df7c2a2
    erikcorry authored
    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}
    8df7c2a2
Name
Last commit
Last update
benchmarks Loading commit data...
build_overrides Loading commit data...
docs Loading commit data...
gni Loading commit data...
gypfiles Loading commit data...
include Loading commit data...
infra Loading commit data...
samples Loading commit data...
src Loading commit data...
test Loading commit data...
testing Loading commit data...
third_party Loading commit data...
tools Loading commit data...
.clang-format Loading commit data...
.gitignore Loading commit data...
.gn Loading commit data...
.ycm_extra_conf.py Loading commit data...
AUTHORS Loading commit data...
BUILD.gn Loading commit data...
CODE_OF_CONDUCT.md Loading commit data...
ChangeLog Loading commit data...
DEPS Loading commit data...
LICENSE Loading commit data...
LICENSE.fdlibm Loading commit data...
LICENSE.strongtalk Loading commit data...
LICENSE.v8 Loading commit data...
LICENSE.valgrind Loading commit data...
Makefile Loading commit data...
Makefile.android Loading commit data...
OWNERS Loading commit data...
PRESUBMIT.py Loading commit data...
README.md Loading commit data...
WATCHLISTS Loading commit data...
codereview.settings Loading commit data...
snapshot_toolchain.gni Loading commit data...