Hm it seems to be a copy of the GNU libc regex engine. And coreutils, grep, and awk also package the same engine in user space! That's really annoying.
But yes it looks like it uses a struct re_dfa_t for matching, and some special flags for backreferences? That seems to indicate that they are using linear time maybe with a fallback? Hm.
I think the general turn of events was that libc supported BRE at first, which was implemented using the DFA algorithm. Then Perl implemented a backtracking engine and Perl syntax for REs, and Python/Ruby/etc. wanted to be compatible with Perl, so they also implemented backtracking as well. Because Perl has other features like forward and back assertions that require backtracking.
And then perhaps libc got EREs with backreferences which they bolted onto the existing infrastructure?
Anyway, thanks for the pointer... I may look into these more in the future.
musl libc also uses the TRE regex engine, which apparently uses the DFA algorithm.
But yes it looks like it uses a struct re_dfa_t for matching, and some special flags for backreferences? That seems to indicate that they are using linear time maybe with a fallback? Hm.
I think the general turn of events was that libc supported BRE at first, which was implemented using the DFA algorithm. Then Perl implemented a backtracking engine and Perl syntax for REs, and Python/Ruby/etc. wanted to be compatible with Perl, so they also implemented backtracking as well. Because Perl has other features like forward and back assertions that require backtracking.
And then perhaps libc got EREs with backreferences which they bolted onto the existing infrastructure?
Anyway, thanks for the pointer... I may look into these more in the future.
musl libc also uses the TRE regex engine, which apparently uses the DFA algorithm.