An additional non-backtracking RegExp engine · V8

Show navigation Starting with v8.8, V8 ships with a new experimental non-backtracking RegExp engine (in addition to the existing Irregexp engine) which guarantees execution in linear time with respect to the size of the subject string. The experimental engine is available behind the feature flags mentioned below. Runtime of /(a*)*b/.exec('a'.repeat(n)) for n ≤ 100Here’s how you can configure the n

[efcl]

V8にバックトラックをしない正規表現エンジンをフラグ付きで実装したという話。 バックトラックによってReDoSのような指数関数的にマッチする問題が知られていて、これを解決するためにバックトラックを使わないアルゴ

[yosuke_furukawa]

V8の正規表現の内部実装で backtrack をやめるっていう話、 re2 みたいな正規表現の実装になることで ReDoS をなるべく防ぐようにするのが入りそう。 --regexp-backtracks-before-fallback みたいな回数閾値でどっち使うか決まるのかな