Oops sorry, Powerset algo is actually O(n*2^n) time complexity On Sat, 3 Apr 2021, 13:49 Artur Vianna, <lordhowen...@gmail.com> wrote:
> 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%3DAWBUE4fFWWFOVzhF-WpMZZL6L15XCd-L3yAWj9k_CtkFr7Q%40mail.gmail.com.
