Forum: Ruby-core [ruby-trunk - Bug #7787][Open] ruby 1.9 regexp quantifiers behave unpredictably when stacked

E31b170ac011f5b770ebc1aef1f8363d?d=identicon&s=25 calfeld (Christopher Alfeld) (Guest)
on 2013-02-05 20:30
(Received via mailing list)
Issue #7787 has been reported by calfeld (Christopher Alfeld).

----------------------------------------
Bug #7787: ruby 1.9 regexp quantifiers behave unpredictably when stacked
https://bugs.ruby-lang.org/issues/7787

Author: calfeld (Christopher Alfeld)
Status: Open
Priority: Normal
Assignee:
Category:
Target version:
ruby -v: ruby 1.9.3p327 (2012-11-10 revision 37606) [x86_64-darwin12]


Ruby (1.8 and 1.9) allows for stacked quantifiers such as /x{2}{5}/ and
appears to treat them more or less as expected, i.e., modulo capturing,
/x{2}{5}/ is equivalent to /(x{2}){5}/ is equivalent to /x{10}/.

However, in Ruby 1.9, such stacking quantifiers can lead to extreme
search time and in ways that are difficult to predict.

    "x"*1000 =~ /x{2}{5}{8}{3}/     # runs instantly
    "x"*1000 =~ /x{2}{5}+{8}{3}/  # runs for an unknown but long time
    "x"*1000 =~ /x{2}{5}+{8}/      # runs instantly
    "x"*1000 =~ /x{2}{5}+{7}{3}/  # runs instantly
    "x"*1000 =~ /x{2}{5}+{7}{3} / # runs for an unknown but long time

All of the above run instantly in Ruby 1.8.  Note that adding
parenthesis does not change the runtime.

I realize this might not be considered a bug and will take no offense if
it as closed as not-a-bug.  But it is surprising, and I hope is of
interest.
9361878d459f1709feec780518946ee5?d=identicon&s=25 naruse (Yui NARUSE) (Guest)
on 2013-02-06 07:54
(Received via mailing list)
Issue #7787 has been updated by naruse (Yui NARUSE).

Status changed from Open to Feedback

It is not considered as a bug, but if there is a reasonable patch I'll
merge it.
----------------------------------------
Bug #7787: ruby 1.9 regexp quantifiers behave unpredictably when stacked
https://bugs.ruby-lang.org/issues/7787#change-35888

Author: calfeld (Christopher Alfeld)
Status: Feedback
Priority: Normal
Assignee:
Category:
Target version:
ruby -v: ruby 1.9.3p327 (2012-11-10 revision 37606) [x86_64-darwin12]


Ruby (1.8 and 1.9) allows for stacked quantifiers such as /x{2}{5}/ and
appears to treat them more or less as expected, i.e., modulo capturing,
/x{2}{5}/ is equivalent to /(x{2}){5}/ is equivalent to /x{10}/.

However, in Ruby 1.9, such stacking quantifiers can lead to extreme
search time and in ways that are difficult to predict.

    "x"*1000 =~ /x{2}{5}{8}{3}/     # runs instantly
    "x"*1000 =~ /x{2}{5}+{8}{3}/  # runs for an unknown but long time
    "x"*1000 =~ /x{2}{5}+{8}/      # runs instantly
    "x"*1000 =~ /x{2}{5}+{7}{3}/  # runs instantly
    "x"*1000 =~ /x{2}{5}+{7}{3} / # runs for an unknown but long time

All of the above run instantly in Ruby 1.8.  Note that adding
parenthesis does not change the runtime.

I realize this might not be considered a bug and will take no offense if
it as closed as not-a-bug.  But it is surprising, and I hope is of
interest.
C4e88907313843cf07f6d85ba8162120?d=identicon&s=25 ko1 (Koichi Sasada) (Guest)
on 2013-02-17 06:22
(Received via mailing list)
Issue #7787 has been updated by ko1 (Koichi Sasada).

Category set to core
Assignee set to naruse (Yui NARUSE)
Target version set to next minor


----------------------------------------
Bug #7787: ruby 1.9 regexp quantifiers behave unpredictably when stacked
https://bugs.ruby-lang.org/issues/7787#change-36377

Author: calfeld (Christopher Alfeld)
Status: Feedback
Priority: Normal
Assignee: naruse (Yui NARUSE)
Category: core
Target version: next minor
ruby -v: ruby 1.9.3p327 (2012-11-10 revision 37606) [x86_64-darwin12]


Ruby (1.8 and 1.9) allows for stacked quantifiers such as /x{2}{5}/ and
appears to treat them more or less as expected, i.e., modulo capturing,
/x{2}{5}/ is equivalent to /(x{2}){5}/ is equivalent to /x{10}/.

However, in Ruby 1.9, such stacking quantifiers can lead to extreme
search time and in ways that are difficult to predict.

    "x"*1000 =~ /x{2}{5}{8}{3}/     # runs instantly
    "x"*1000 =~ /x{2}{5}+{8}{3}/  # runs for an unknown but long time
    "x"*1000 =~ /x{2}{5}+{8}/      # runs instantly
    "x"*1000 =~ /x{2}{5}+{7}{3}/  # runs instantly
    "x"*1000 =~ /x{2}{5}+{7}{3} / # runs for an unknown but long time

All of the above run instantly in Ruby 1.8.  Note that adding
parenthesis does not change the runtime.

I realize this might not be considered a bug and will take no offense if
it as closed as not-a-bug.  But it is surprising, and I hope is of
interest.
This topic is locked and can not be replied to.