Hacker News Reader

Perhaps to protect against ReDoS the client should use an extended finite automata (1).

https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf

(1) Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.

Nope. That still supports backreferences, and resolving backreferences is an NP-complete problem.[1] And I don't see anything in that paper that addresses that. Note that there may be some versions of the problem that maybe aren't NP-complete[2], but again, not addressed by that paper.

Besides, that paper was published 12 years ago. Where is the productionized version of it? Or are you suggesting the the OP go spend a few years writing a regex eninge? :-) Doesn't seem like a particularly practical suggestion.

[1] - https://perl.plover.com/NPC/NPC-3SAT.html

[2] - https://branchfree.org/2019/04/04/question-is-matching-fixed...

In the paper there are some bounds about the number of states in the automata as a function of the length of the input. So one could limit the length of the input when using back references to bound the complexity of the algorithm. They have used their algorithm for snort (network intrusion detection) using asic. The author could contact the authors of the paper and ask for (or pay for) an implementation.

By the way, good work ripgrep and rust.

Reply on news.ycombinator.com