An interesting approach would be the implementation of a regex engine that has optimizations just like a compiler (i think the stdlib one does that to an extent). Using powerset and hopcroft's where it can be used and leaving backtracks where it can't.
That would be fun to implement but very confusing for the user and has the same security problems of a NFA backtracking regex, but the user would be able to choose the backtracking features, being aware that they pose security problems. Powerset algorithm is O(n²) too, so while converting the NFA to DFA some strings like (a*b*)^n can take forever basically, a possible security problem if your regex came from user input. On Sat, 3 Apr 2021, 13:31 bobj...@gmail.com, <bobja...@gmail.com> wrote: > In *my* ideal world, both O(n) and backtracking implementations would be > available in the standard library. > > Most popular languages have only backtracking versions in their standard > libraries (Java, Python, Ruby). It's nice that Go has an O(n) > implementation. But, some regexes that can be written in the modern > backtracking implementations that support "atomic groups", etc. just cannot > be rewritten for O(n) implementations, sometimes resulting in having to > write a lot of code to achieve the equivalent result. The reason that O(n) > implementations lack those features is that they simply can't be done > without violating O(n). So why not let the programmer exercise the choice > -- O(n) where possible for denial-of-service safety or maybe better > performance, and backtracking when O(n) can't be done or maximum > performance is not important, and regexes incoming from the wild do not > happen. > > And... I suspect that well written regexes for backtracking can be nearly > as performant if backtracking is kept under control via skillful use of > those atomic features. It's the sloppy ones that are the problem. > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/7afca073-a3ff-464c-8de4-8b2ba7c4d214n%40googlegroups.com > <https://groups.google.com/d/msgid/golang-nuts/7afca073-a3ff-464c-8de4-8b2ba7c4d214n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAE%3DAWBW9PaP%2BA%2BnKsBfGQgDWLJ73y%3DBpHyP%2B_r%2BPHrOvODDwqA%40mail.gmail.com.
