• Martin Bidlingmaier's avatar
    [regexp] Support capture groups in experimental engine · 98b8ca89
    Martin Bidlingmaier authored
    This commit adds support for capture groups (as in e.g. /x(123|abc)y/)
    in the experimental regexp engine.  Now every InterpreterThread owns a
    register array containing (sub)match boundaries. There is a new
    instruction to record the current input index in some register.
    
    Submatches in quantifier bodies should be reported only if they occur
    during the last repetition.  Thus we reset those registers before
    attempting to match the body of a quantifier.  This is implemented with
    another new instruction.
    
    Because of concerns for the growing sizeof the NfaInterpreter object
    (which is allocated on the stack), this commit replaces the
    `SmallVector` members of the NfaInterpreter with zone-allocated arrays.
    Register arrays, which for a fixed regexp are all the same size, are
    allocated with a RecyclingZoneAllocator for cheap memory reclamation via
    a linked list of equally-sized free blocks.
    
    Possible optimizations for management of register array memory:
    1. If there are few register per thread, then it is likely faster to
       store them inline in the InterpreterThread struct.
    2. re2 implements copy-on-write:  InterpreterThreads can share the same
       register array. If a thread attempts to write to shared register
       array, the register array is cloned first.
    3. The register at index 1 contains the end of the match; this is only
       written to right before an ACCEPT statement.  We could make ACCEPT
       equivalent to what's currently CAPTURE 1 followed by ACCEPT.  We
       could then save the memory for register 1 for threads that haven't
       finished yet.  This is particularly interesting if now optimization 1
       kicks in.
    
    Cq-Include-Trybots: luci.v8.try:v8_linux64_fyi_rel_ng
    Bug: v8:10765
    Change-Id: I2c0503206ce331e13ac9912945bb66736d740197
    Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2390770
    Commit-Queue: Martin Bidlingmaier <mbid@google.com>
    Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#69929}
    98b8ca89
Name
Last commit
Last update
build_overrides Loading commit data...
custom_deps Loading commit data...
docs Loading commit data...
gni 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...
.clang-tidy Loading commit data...
.editorconfig Loading commit data...
.flake8 Loading commit data...
.git-blame-ignore-revs Loading commit data...
.gitattributes Loading commit data...
.gitignore Loading commit data...
.gn Loading commit data...
.vpython 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...
COMMON_OWNERS Loading commit data...
DEPS Loading commit data...
ENG_REVIEW_OWNERS Loading commit data...
INFRA_OWNERS Loading commit data...
INTL_OWNERS Loading commit data...
LICENSE Loading commit data...
LICENSE.fdlibm Loading commit data...
LICENSE.strongtalk Loading commit data...
LICENSE.v8 Loading commit data...
MIPS_OWNERS Loading commit data...
OWNERS Loading commit data...
PPC_OWNERS Loading commit data...
PRESUBMIT.py Loading commit data...
README.md Loading commit data...
S390_OWNERS Loading commit data...
WATCHLISTS Loading commit data...
codereview.settings Loading commit data...