From: Josh ben Jore Date: 2010-08-13T05:35:15+09:00 Subject: [ruby-core:31701] [Bug #3679] pathological regular expressions and exponential computation time Issue #3679 has been updated by Josh ben Jore. I apologise in advance for not being informative enough. Perl does in fact suffer from this as well since Perl's computational basis for regexps is in the same paradigm as Ruby's. We have however accumulated a number of optimizations and get-out-of-jail cards over the years. I opened http://perl5.git.perl.org/perl.git/blob/HEAD:/regexec.c just now to see what might show up labeled as an optimization or about being exponential. Sadly, I think I'd need to do a close reading of the source to find the escape clauses. It might be worth reading the commit notes for this source file. Separately, you can view intimate details of the Perl re compilation by enabling debugging for either lexical scope or whatever. I suggest this to you in the hopes you might use it to find useful short-cuts that Oniguruma isn't yet. In particular, there's the Debug and debug flags to the re.pm pragma and used in context for your examples: perl -e 'use re qw( Debug INTUIT OPTIMISE OPTIMISEM ); ("a" x 27 . "b") =~ /(?:a|a|a)+\z/' Want to chat about this over lunch or a beer sometime? I'm in south lake union just north of you. ---------------------------------------- http://redmine.ruby-lang.org/issues/show/3679 ---------------------------------------- http://redmine.ruby-lang.org