4 ms·

Finite state machines also have their cliffs, in particular bounded repetition. Rust's FA-based regex will explode with /.{12345}/, while v8's backtracking engi

• burntsushi 4y ago
  Yes, but please be careful here. The cliffs are categorically different. The cliffs of a finite state machine are still bounded to O(m * n), where m ~ len(regex) and n ~ len(haystack). The cliffs of a backtracker are exponential and difficult to predict. The repetition operator provokes the cliff because it represents short-hand syntax for easily increasing `m` to very large sizes. Indeed, by default, '.{12345}' will fail to compile because it blows the default limit. That only works because, as I said, the cliffs for finite automata based regex engines are far more predictable.