]> granicus.if.org Git - re2c/commit
libre2c: found pathological case for constant-memory POSIX algorithms.
authorUlya Trofimovich <skvadrik@gmail.com>
Wed, 20 Feb 2019 17:00:47 +0000 (17:00 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Wed, 20 Feb 2019 17:00:47 +0000 (17:00 +0000)
commitc0c951cb785d30a48d549df294ef4ea988245eb0
tree97d8277bd8a4133c600b99a0c0c5696be53caf56
parentbbe142c9c694e5476ead6d6ec271445d12c61315
libre2c: found pathological case for constant-memory POSIX algorithms.

The regexp is ((a?){1,200})*, and the input string is just "a".

Takes quibic time in the size of counter. This is caused by quadratic-
time computation of precedence matrix on each step (the number of TNFA
states in the closure approaches TNFA size), multiplied by the length
of compared histores (which also approaches TNFA size). Trie-based
algorithms are not affected, but they consume memory proportional to
the length of the input string, and so are also not practical.
re2c/lib/bench.cc