Skip to content

V
V8
Switch branch/tag
  1. 09 Jun, 2021 3 commits
    • Iain Ireland's avatar
      [regexp] Propagate eats_at_least for negative lookahead · 363ab5ae
      Iain Ireland authored 
      In issue 11290, we disabled the propagation of EAL data out of
lookarounds, because it was incorrect for lookahead nodes in
loops. This caused performance regressions: for example,
`/^\P{Letter}+$/u` (matching only characters that are not in Unicode's
Letter category) uses negative lookahead when matching lone
surrogates, and became about 2x slower. I spent some time looking into
fixes, and this is what I've settled on.

Some background: the implementation of lookarounds in irregexp is
split between positive and negative lookaheads. (Lookbehinds aren't
relevant here, because backwards matches always have EAL=0.)  Positive
lookaheads are wrapped in BEGIN_SUBMATCH and POSITIVE_SUBMATCH_SUCCESS
ActionNodes. BEGIN_SUBMATCH saves the current state.
POSITIVE_SUBMATCH_SUCCESS restores the necessary state (while leaving
any captures that occurred during the lookaround intact).

Negative lookaheads also begin with a BEGIN_SUBMATCH node, but follow
it with a NegativeLookaroundChoiceNode. This node has two successors:
a lookaround node, and a continue node. It only executes the continue
node if the lookaround node backtracks, which automatically restores
the previous state. Negative lookarounds also can't update captures.

This affects EAL calculations. It turns out that negative lookaheads
are already doing the right thing: EatsAtLeastPropagator only
propagates information from the continue node, ignoring the lookaround
node. The same is true for quick checks (see the comment in
RegExpLookaround:Builder::ForMatch). A BEGIN_SUBMATCH for a negative
lookahead can simply propagate the EAL data from its successor like
any other ActionNode, and everything works.

Positive lookaheads are harder. I tried saving a pointer to the
successor in BEGIN_SUBMATCH, but ran into problems in FillInBMInfo,
because the EAL value corresponded to the nodes after the lookahead,
but the analysis was still looking at the nodes inside. I fell back
to a more modest approach: split BEGIN_SUBMATCH in two, and propagate
EAL info for BEGIN_NEGATIVE_SUBMATCH while keeping the current
behaviour for BEGIN_POSITIVE_SUBMATCH. This fixes the performance
regression at hand.

Two potential approaches for fixing EAL for positive lookahead are:
 1. Handling positive lookahead with its own dedicated choice node,
    like NegativeLookaroundChoiceNode.
 2. Adding an eats_at_least_inside_loop field to EatsAtLeastInfo,
    which is <= eats_at_least_from_possibly_start, and using that
    value in EatsAtLeastFromLoopEntry.

Both of those approaches are more complex than I want to tackle
right now, though.

Bug: v8:11844
Change-Id: I2a43509c2c21194b8c18f0a587fa21c194db76c2
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2934858Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
Commit-Queue: Jakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75031}
      363ab5ae
    • Frank Tang's avatar
      Address flaky tests · 4a78a7d0
      Frank Tang authored 
      The test push stack boundary and too flaky (timeout) while
running machine with more memory.

Bug: v8:11845
Change-Id: I5b603f05270d224de71c735ece5dd65a27311c25
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2939082Reviewed-by: 's avatarShu-yu Guo <syg@chromium.org>
Commit-Queue: Frank Tang <ftang@chromium.org>
Cr-Commit-Position: refs/heads/master@{#75030}
      4a78a7d0
    • v8-ci-autoroll-builder's avatar
      Update V8 DEPS. · eb3ce72b
      v8-ci-autoroll-builder authored 
      Rolling v8/build: https://chromium.googlesource.com/chromium/src/build/+log/8870cb4..921ea58

Rolling v8/third_party/catapult: https://chromium.googlesource.com/catapult/+log/a8bae77..df0a59a

Rolling v8/third_party/depot_tools: https://chromium.googlesource.com/chromium/tools/depot_tools/+log/b508ecd..b14cdae

Rolling v8/tools/clang: https://chromium.googlesource.com/chromium/src/tools/clang/+log/0c64e83..d987b04

TBR=v8-waterfall-sheriff@grotations.appspotmail.com,mtv-sf-v8-sheriff@grotations.appspotmail.com

Change-Id: I8906ce650c866bd771910fea5db6c735bfe0c7e2
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2947396Reviewed-by: 's avatarv8-ci-autoroll-builder <v8-ci-autoroll-builder@chops-service-accounts.iam.gserviceaccount.com>
Commit-Queue: v8-ci-autoroll-builder <v8-ci-autoroll-builder@chops-service-accounts.iam.gserviceaccount.com>
Cr-Commit-Position: refs/heads/master@{#75029}
      eb3ce72b
  3. 08 Jun, 2021 30 commits
  5. 07 Jun, 2021 7 commits