We really like to stick to the original meaning of NFA, so our NFAs have the same problems as a DFA from a SoM perspective. That is, our NFAs are just bitvector

We really like to stick to the original meaning of NFA, so our NFAs have the same problems as a DFA from a SoM perspective. That is, our NFAs are just bitvectors over states, not threads that can hold their own SoM or information about prior quantifiers. "NFA" has suffered a bit of semantic drift over the years... We've heard of redgrep. I think there's a role for JITs here but I'm not sure I buy the concept that it should be a straightforward "turn the DFA states into code and jump around". Predicting the future: if we have a regular expression made up of R1, R2 and Q (where R1, R2 are regexes and Q is a quantified something-or-rather - NOT necessarily with Q and R2 disjoint!) as follows /(R1)(Q)+(R2)/ and we're in streaming mode, 'predicting the future' means that we need to understand what happens beyond a stream boundary to know what to do now. Supposing that we have a stream boundary falling between something matching both (Q)+ and (R2) what is going to happen to future matches of R2. This can be done but is hard - the problems are very similar to SoM tracking in a traditional NFA or DFA, and mean that you are starting to track loads of extra state. The other problem for us with trying to support lazy/greedy quantification is ordering. We might have another regex (in a multiple regex set) that is unambiguously meant to throw a match between two potential matches controlled by something we might need to hold on to until we see whether the equivalent of (R2) matches for the second instance. So we can't just fire and forget if we go the quantifier-support route. The fact is that the client base in network apps is very familiar with 'automata semantics' (i.e. lazy/greedy is a no-op and you get all matches) and supporting anything beyond that is a lot more expensive to get right. Yes, there's something a bit peculiar about the idea of capturing and streaming mode together, isn't there? "Oh, we have the offsets of what matched, but you threw the data away, sorry". Bounded repetition is a huge pain and is a work in progress for us in the general case. Single-character-wide bounded repetition (e.g. \s{100} or .{80,120} etc) works quite well. Depending on the form of the bounded repeat and the context, it is sometimes be possible to replace the repeat by tracking either the location of first or last entry, but the general case is horrible: /a.{20000}b/s is just as bad as it looks. We actually do this, but you better have 20,000 bits handy per stream state. :-)