dajva / rg.el

Emacs search tool based on ripgrep
https://rgel.readthedocs.io
GNU General Public License v3.0
475 stars 41 forks source link

prevent excessive backtracking in regex engine #17

Closed mbunkus closed 7 years ago

mbunkus commented 7 years ago

The following font lock regex pattern leads to excessive backtracking due to an arbitrary number of characters in the parenthesis and an arbitrary number of parenthesis itself:

"^\(?:.+?-\)?[0-9]+-.\n"

This leads to a lot of backtracking. The time required for matching grows exponentially with the input length (the line length in rg's case).

Fixes #14. It might also be the cause of #12.