[ruby-core:94236] [Ruby master Bug#8287] Regexp performance issue

Issue #8287 has been updated by jeremyevans0 (Jeremy Evans).

Backport deleted (1.9.3: UNKNOWN, 2.0.0: UNKNOWN)
Status changed from Open to Rejected

From the general problem statement, and looking at the regexp's nested use of `*` and `+` along with `\g`, this regexp probably exhibits exponential backtracking. See https://docs.ruby-lang.org/en/2.6.0/Regexp.html#class-Regexp-label-Performance.  You would need to fix the regexp to avoid the backtracking, possibly using `(?>` for some capture groups. I can't confirm that because as displayed, the regexp is not valid Ruby code (I'm guessing a previous Redmine update broke the syntax used).

----------------------------------------
Bug #8287: Regexp performance issue
https://bugs.ruby-lang.org/issues/8287#change-80542

* Author: mghomn (Justin Peal)
* Status: Rejected
* Priority: Normal
* Assignee: naruse (Yui NARUSE)
* Target version: 
* ruby -v: ruby 1.9.3p374 (2013-01-15) [i386-mingw32]
* Backport: 
----------------------------------------
ADDRESS = # RFC-5322 : http://tools.ietf.org/html/rfc5322
/
  (?<mailbox>
    (?<name_addr>
      (?<display_name>
        (?<phrase>
          (?<word>
            (?<atom>
              #\g<CFWS>?
              #\g<atext>+
              #\g<CFWS>?
            )
            |
            \g<quoted_string>
          )+
        )
      )?
      (?<angle_addr>
        \g<CFWS>?
        <
        \g<addr_spec>
        >
        \g<CFWS>?
      )
    )
    |
    (?<addr_spec>
      (?<local_part>
        (?<dot_atom>
          (?<CFWS>
            (?:
              (?:
                (?<FWS>
                  (
                    \g<WSP>*
                    (?<CRLF>
                      \x0d \x0a
                    )
                  )?
                  (?<WSP>
                    \x09 | \x20
                  )+
                )?
                (?<comment>
                  \(
                  (?:
                    \g<FWS>?
                    (?<ccontent>
                      (?<ctext>
                        [\x21-\x27] | [\x2a-\x5b] | [\x5d-\x7e]
                      )
                      |
                      (?<quoted_pair>
                        \\
                        (?:
                          (?<VCHAR>
                            [\x21-\x7e]
                          )
                          |
                          \g<WSP>
                        )
                      )
                      |
                      \g<comment>
                    )
                  )*
                  \g<FWS>?
                  \)
                )
              )+
              \g<FWS>?
            )
            |
            \g<FWS>
          )?
          (?<dot_atom_text>
            (?<atext>
              [-\w!\#$%&'*+\/=?^`{|}~]
            )+
            (?:
              \.
              \g<atext>+
            )*
          )
          \g<CFWS>?
        )
        |
        (?<quoted_string>
          \g<CFWS>?
          (?<DQUOTE> " )
          (?:
            \g<FWS>?
            (?<qcontent>
              (?<qtext>
                \x21 | [\x23-\x5b] | [\x5d-\x7e]
              )
              |
              \g<quoted_pair>
            )
          )*
          \g<FWS>?
          \g<DQUOTE>
          \g<CFWS>?
        )
      )
      @
      (?<domain>
        \g<dot_atom>
        |
        (?<domain_literal>
          \g<CFWS>?
          \[
          (
            \g<FWS>?
            (?<dtext>
              [\x21-\x5a] | [\x5e-\x7e]
            )
          )*
          \g<FWS>?
          \]
          \g<CFWS>?
        )
      )
    )
  )
  |
  (?<group>
    \g<display_name>
    :
    (?<group_list>
      (?<mailbox_list>
        \g<mailbox>
        (?:
          ,
          \g<mailbox>
        )*
      )
      |
      \g<CFWS>
    )?
    ;
    \g<CFWS>?
  )
/x

puts "start = #{start = Time.now}"
puts '[e-mail]'[ADDRESS]
puts "stop  = #{stop = Time.now}"
puts "#{stop - start} seconds"

=begin
C:\>err
start = 2013-04-18 12:34:02 +0800
[e-mail]
stop  = 2013-04-18 12:34:04 +0800
1.662166 seconds

After uncomment line 9~11:

C:\>err
start = 2013-04-18 12:34:14 +0800
[e-mail]
stop  = 2013-04-18 12:34:14 +0800
0.003001 seconds
=end




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

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>