We fall back from irregexp to the experimental engine if a backtrack
limit is exceeded and the experimental engine can handle the regexp.
The feature can be turned on with a boolean flag, and an uint-valued
flag controls the default backtrack limit. For regexps that are
constructed with an explicit backtrack limit (API,
%NewRegExpWithBacktrackLimit), we choose the lower of the explicit and
default backtrack limits.
The default backtrack limit does not apply to regexps that can't be
handled by the experimental engine, and for such regexps an explicitly
specified backtrack limit is handled as before by returning null if we
exceed it.
Cq-Include-Trybots: luci.v8.try:v8_linux64_fyi_rel_ng
Bug: v8:10765
Change-Id: I580df79bd847520985b6c2c2159bc427315c89d1
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2436341
Commit-Queue: Martin Bidlingmaier <mbid@google.com>
Reviewed-by: Jakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#70500}
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: Jakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#69929}
.. similar to how it is applied in the interpreter. We reserve a stack
slot for the backtrack count, increment it on each backtrack, and fail
if the limit is hit.
Bug: v8:9695
Change-Id: I835888c612d6c8bfa2f34e73ab8c8241dcabc6ed
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1864938
Reviewed-by: Peter Marshall <petermarshall@chromium.org>
Commit-Queue: Jakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#64426}
V8 uses a backtracking regexp engine, which has the caveat that some
regexp patterns can have exponential runtime behavior when excessive
backtracking is involved.
Especially when regexp patterns are user-controlled, it would be useful
to be able to set an upper limit for a single regexp execution. This CL
takes an initial step in that direction by adding a backtracking limit
(intended to approximate execution time):
- The limit is stored in the JSRegExp's data array.
- A limit can currently only be set through the %NewRegExpWithLimit
runtime function.
- The limit is applied during interpreter execution. When exceeded, the
interpreter stops execution and returns FAILURE (even if continued
execution would at some later point have resulted in SUCCESS).
In follow-up CLs, this mechanism will be extended to work in jitted
regexp code, and exposed through the V8 API.
Bug: v8:9695
Change-Id: Iadb5c100052f4a63b26f1ec49cf97c6713a66b9b
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1864934
Commit-Queue: Ulan Degenbaev <ulan@chromium.org>
Auto-Submit: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
Reviewed-by: Peter Marshall <petermarshall@chromium.org>
Cr-Commit-Position: refs/heads/master@{#64417}
