Bug #7787

ruby 1.9 regexp quantifiers behave unpredictably when stacked

Added by calfeld (Christopher Alfeld) over 7 years ago. Updated over 1 year ago.

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.

Updated by naruse (Yui NARUSE) over 7 years ago

  • Status changed from Open to Feedback

It is not considered as a bug, but if there is a reasonable patch I'll merge it.

Updated by ko1 (Koichi Sasada) over 7 years ago

  • Category set to core
  • Assignee set to naruse (Yui NARUSE)
  • Target version set to 2.6

Updated by naruse (Yui NARUSE) over 2 years ago

  • Target version deleted (2.6)

Updated by naruse (Yui NARUSE) over 1 year ago

  • Status changed from Feedback to Rejected

This should be handled on upstream.

Also available in: Atom PDF