gistfile1.md

This demonstrates how different regular expression engines handle catastrophic expressions. Python's "re" module doesn't seem to have any type of backtracking timeout.

awk

awk 4.0.1

» awk --version
GNU Awk 4.0.1

» time echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa | awk '{ gsub("^(([a-z])+.)+[A-Z]([a-z])+$", "test"); print}'
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
echo   0.00s user 0.00s system 0% cpu 0.001 total
awk { gsub("^(([a-z])+.)+[A-Z]([a-z])+$", "test"); print}'  0.00s user 0.00s system 0% cpu 0.069 total

Python

Python 2.7.4

» python --version
Python 2.7.4

» time python -c "import re; mystr = 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'; rest = ['^(([a-z])+.)+[A-Z]([a-z])+$', 'test']; print re.sub(rest[0], rest[1], mystr)" 
^CTraceback (most recent call last):
File "<string>", line 1, in <module>
File "/usr/lib/python2.7/re.py", line 151, in sub
    return _compile(pattern, flags).sub(repl, string, count)
KeyboardInterrupt
python -c   78.52s user 0.13s system 99% cpu 1:19.43 total

Python 3.3.1

» python3 --version
Python 3.3.1

» time python3 -c "import re; mystr = 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'; rest = ['^(([a-z])+.)+[A-Z]([a-z])+$', 'test']; print(re.sub(rest[0], rest[1], mystr))"
^CTraceback (most recent call last):
File "<string>", line 1, in <module>
File "/usr/lib/python3.3/re.py", line 170, in sub
    return _compile(pattern, flags).sub(repl, string, count)
KeyboardInterrupt
python3 -c   28.00s user 0.00s system 99% cpu 28.020 total

sed

sed 4.2.1

» sed --version
GNU sed version 4.2.1

» time echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa | sed -r 's/^(([a-z])+.)+[A-Z]([a-z])+$/test/g'
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
echo   0.00s user 0.00s system 0% cpu 0.001 total
sed -r 's/^(([a-z])+.)+[A-Z]([a-z])+$/test/g'  0.00s user 0.00s system 0% cpu 0.002 total