3 ms·
> Not constant, bounded. If I can do this: re = regexp(".+aaaaaaaaaaa") state = malloc(len(re)) match1 = exec(re, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
by burntsushi 11y ago
> Not constant, bounded.
If I can do this:
re = regexp(".+aaaaaaaaaaa")
state = malloc(len(re))
match1 = exec(re, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
match2 = exec(re, "aaa")
match3 = exec(re, "aaaaaaaaaaa")
...
And I also claim that `exec` is guaranteed to never call `malloc` in any of its executions (or otherwise allocate).
Do you consider that constant or bounded? It looks like it's constant to me.
If you're talking about CPU resources, then the absolute worst case in the NFA algorithm is requiring `len(re)` operations per position in the input. I guess this is what you're referring to as bounded? If so, then it is a linear bound. :-) An attacker can't make matching take more than linear time.
I feel like this entire conversation has been one roundabout exploration of "DFAs are faster than NFAs." :-/
> I also didn't sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you're correct about this with the convention you are using.
You had me doubting myself there for a second, so kudos. :-)
- amalcon 11y agoHuh, I didn't consider the possibility of pre-allocating space for the entire state list. That's a cute trick, making it less memory efficient in the average case (though more efficient CPU-wise by avoiding malloc) but also addressing my exact concern. Nice. edit: I guess I should have just looked that up sooner. Sorry for any hassle or aggravations.
- burntsushi 11y agoInteresting. I had never even considered not pre-allocating space for it... :-) In a "real" implementation, you also need space to store sub-capture locations. You get to reuse this space on each execution of the regex, so it's a really nice win. There are also certain crazy people in this world who have encoded the NFA algorithm into a code generation tool, which enables it to run completely malloc-free and entirely on the stack. :-)