From: "mame (Yusuke Endoh)" <noreply@...>
Date: 2022-03-23T17:07:15+00:00
Subject: [ruby-core:108043] [Ruby master Bug#14103] Regexp absense operator has no chance to ^C

Issue #14103 has been updated by mame (Yusuke Endoh).

Status changed from Closed to Open

This change degrades the performance of regular expression matching when frequent backtracking occurs.

Before edc8576a65b7082597d45a694434261ec3ac0d9e

```
$ time ./miniruby -ve '/^a*b?a*$/ =~ "a" * 20000 + "x"'
ruby 3.2.0dev (2022-03-10T19:06:33Z master edc8576a65) [x86_64-linux]

real    0m3.824s
user    0m3.820s
sys     0m0.004s
```

After edc8576a65b7082597d45a694434261ec3ac0d9e

```
$ time ./miniruby -ve '/^a*b?a*$/ =~ "a" * 20000 + "x"'
ruby 3.2.0dev (2022-03-10T19:06:33Z master edc8576a65) [x86_64-linux]

real    0m4.608s
user    0m4.588s
sys     0m0.016s
```

I have no idea if this may lead to any actual problem, but how about reducing the frequency of rb_thread_check_ints? This PR makes the check only once every 128 backtracks.

https://github.com/ruby/ruby/pull/5697

This restores the original performance.

```
$ time ./miniruby -ve '/^a*b?a*$/ =~ "a" * 20000 + "x"'
ruby 3.2.0dev (2022-03-23T14:55:49Z master 8f1c69f27c) [x86_64-linux]

real    0m3.702s
user    0m3.696s
sys     0m0.000s
```

Still, it allows immediate interrupts.

```
$ ./miniruby -e '/^a*b?a*$/ =~ "a" * 20000 + "x"'
^C-e:1:in `<main>': Interrupt

$ ./miniruby -e "/(?<x> (?<! a ) a+ ){0}
 (?<y> (?~ \g<z> ) ){0}
 (?<z> (?<! a ) \k<x> (?! a ) ){0}
 \g<x> \g<y> \g<z>
/xo =~ (1..1024).map{|x| 'b' + 'a' * x }.join"
^C-e:5:in `<main>': Interrupt
```

----------------------------------------
Bug #14103: Regexp absense operator has no chance to ^C
https://bugs.ruby-lang.org/issues/14103#change-97004

* Author: shyouhei (Shyouhei Urabe)
* Status: Open
* Priority: Normal
* ruby -v: ruby 2.5.0dev (2017-11-09 trunk 60720) [x86_64-darwin15]
* Backport: 2.3: UNKNOWN, 2.4: UNKNOWN
----------------------------------------
Following script hangs, with no respond to `^C`.

```ruby
/(?<x> (?<! a ) a+ ){0}
 (?<y> (?~ \g<z> ) ){0}
 (?<z> (?<! a ) \k<x> (?! a ) ){0}
 \g<x> \g<y> \g<z>
/xo =~ (1..1024).map{|x| 'b' + 'a' * x }.join
```



-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>