3 ms·

> This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA. If by quadratic runtime you mean O

> This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA. If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former. And certainly, "linear additional memory usage" is not relative to the input either. > There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It's not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it's still good enough for most cases. Sure, but now you have to deal with exponential state blow up. :-) You can skirt around that with a lazy DFA, and you're now technically back to O(mn) (same as the NFA algorithm in the worst case), but in the common case, you end up pretty close to the performance of a DFA constructed offline. As "evidence" of my claim, you might peruse these unscientific benchmarks: https://github.com/jneem/regex-benchmarks https://github.com/jneem/regex-benchmarks (The first group uses an offline DFA and the latter two groups are both lazy DFAs. Of course, this is just an anecdote!) My view on this is pretty biased because my goal is not to just be able to deal with untrusted input, but to also deal with untrusted regexes. It's hard to satisfy the latter case with an offline DFA. :-/

wolfgke 11y ago
> If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former. I think he rather means O(len(regex)^2 * len(input)). For the reason: The number of states of an NFA is O(len(regex)) =: m. When parsing with an NFA (standard algorithm) you iterate through all states we are currently in (up to m). On the current input character each state we are in can go into up to m new states for the next state. This is up to m^2 transformations to check.
- burntsushi 11y ago
  That's only true in a naive implementation. In fact, in a naive implementation, it's probably worse than that because there can be loops among epsilon transitions. Consider, for example, `(a{star}){star}`. (HN markup prevents use of a kleene star usefully. Sorry.) In a "real" implementation, when computing the next set of states to visit for some position in the input, you explicitly avoid re-visiting states you've already seen for that position in the input. Cox talks about this quite a bit in his articles. The guarantee of the NFA algorithm as presented by Cox is that each NFA state is visited at most once for each position in the input.
  - amalcon 11y ago
    I think wolfgke's point (different from mine, by the way) was that you need to consider each state in each transition list just to check if it's in the set you've already seen. If you're in all states, and all of them transition to all states on an input, that's quadratic: you need to loop through n lists of n states just to check if you've already visited any of them. Of course, I don't think there's an actual regular expression that would produce that automaton using Thompson's algorithm.
    - burntsushi 11y ago
      No, it can't happen at all. After processing the first state that visits all states on input i, all subsequent states explored in input i stop before traversing states that have already been visited. Since all states have already been visited, each state after the first on input i can be dismissed in constant time. Given that one can check whether a state has been visited in constant time, this is still just linear, not quadratic. Let's just look at code already. Here's the loop over states at input i: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L165 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we match a character at input i, then we follow epsilon transitions: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L237 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we visit a state that we've already seen, skip it: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L300 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If that first state visits all states, then `nlist` (which is maintained while following all states at any position in the input) will contain all states. In each subsequent iteration (line 165), even if the state wants to visit all states, it will be immediately stopped at the first check in line 300. No additional states for that state are followed.
amalcon 11y ago
Actually, my mistake is that I was examining a particular pathological case for NFAs, that DFAs handle fine: something like /.+aaaaaaaaaa/. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of "all eleven states". For that regex, the worst case is O(min(len(regex),len(input))*len(input)). This is quadratic in the input length, until a certain point. Which formula is correct then depends on whether the regex or the input is longer. In other cases (e.g. /(aa|ab|ac|ad|ae|af|ag|...)+/), you blow up to the maximum number of states immediately, and for a matching string stay in the same number of states the whole time. Therefore, it is technically correct to leave out the len(input) parameter if you are considering arbitrary regular expressions. > You can skirt around that with a lazy DFA This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process.
- burntsushi 11y ago
  > something like /.+aaaaaaaaaa/. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of "all eleven states". That's just false for the NFA algorithm. I'm not sure where your confusion lay, unfortunately. There are no pathological cases for the NFA algorithm. Zero. Zip. Nada. It's guaranteed O(mn) time. See Cox's articles. They explain. It is true of course that certain regexes run slower than others using the NFA algorithm, but this is because of constant factors, not because of any degradation in runtime complexity. When implementing the NFA algorithm, you can allocate all of the space you need upfront and then execute a search guaranteeing no additional allocation. Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. (I think this is isomorphic to your example, assuming `a{11}$`.) > This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process. Sounds pretty complex to me. Certainly more complex and fiddly IMO than implementing a lazy DFA. (I've done both.)

wolfgke 11y ago

> If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former. I think he rather means O(len(regex)^2 * len(input)). For the reason: The number of states of an NFA is O(len(regex)) =: m. When parsing with an NFA (standard algorithm) you iterate through all states we are currently in (up to m). On the current input character each state we are in can go into up to m new states for the next state. This is up to m^2 transformations to check.

burntsushi 11y ago
That's only true in a naive implementation. In fact, in a naive implementation, it's probably worse than that because there can be loops among epsilon transitions. Consider, for example, `(a{star}){star}`. (HN markup prevents use of a kleene star usefully. Sorry.) In a "real" implementation, when computing the next set of states to visit for some position in the input, you explicitly avoid re-visiting states you've already seen for that position in the input. Cox talks about this quite a bit in his articles. The guarantee of the NFA algorithm as presented by Cox is that each NFA state is visited at most once for each position in the input.
- amalcon 11y ago
  I think wolfgke's point (different from mine, by the way) was that you need to consider each state in each transition list just to check if it's in the set you've already seen. If you're in all states, and all of them transition to all states on an input, that's quadratic: you need to loop through n lists of n states just to check if you've already visited any of them. Of course, I don't think there's an actual regular expression that would produce that automaton using Thompson's algorithm.
  - burntsushi 11y ago
    No, it can't happen at all. After processing the first state that visits all states on input i, all subsequent states explored in input i stop before traversing states that have already been visited. Since all states have already been visited, each state after the first on input i can be dismissed in constant time. Given that one can check whether a state has been visited in constant time, this is still just linear, not quadratic. Let's just look at code already. Here's the loop over states at input i: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L165 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we match a character at input i, then we follow epsilon transitions: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L237 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we visit a state that we've already seen, skip it: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L300 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If that first state visits all states, then `nlist` (which is maintained while following all states at any position in the input) will contain all states. In each subsequent iteration (line 165), even if the state wants to visit all states, it will be immediately stopped at the first check in line 300. No additional states for that state are followed.

amalcon 11y ago

Actually, my mistake is that I was examining a particular pathological case for NFAs, that DFAs handle fine: something like /.+aaaaaaaaaa/. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of "all eleven states". For that regex, the worst case is O(min(len(regex),len(input))*len(input)). This is quadratic in the input length, until a certain point. Which formula is correct then depends on whether the regex or the input is longer. In other cases (e.g. /(aa|ab|ac|ad|ae|af|ag|...)+/), you blow up to the maximum number of states immediately, and for a matching string stay in the same number of states the whole time. Therefore, it is technically correct to leave out the len(input) parameter if you are considering arbitrary regular expressions. > You can skirt around that with a lazy DFA This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process.

burntsushi 11y ago
> something like /.+aaaaaaaaaa/. In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of "all eleven states". That's just false for the NFA algorithm. I'm not sure where your confusion lay, unfortunately. There are no pathological cases for the NFA algorithm. Zero. Zip. Nada. It's guaranteed O(mn) time. See Cox's articles. They explain. It is true of course that certain regexes run slower than others using the NFA algorithm, but this is because of constant factors, not because of any degradation in runtime complexity. When implementing the NFA algorithm, you can allocate all of the space you need upfront and then execute a search guaranteeing no additional allocation. Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. (I think this is isomorphic to your example, assuming `a{11}$`.) > This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process. Sounds pretty complex to me. Certainly more complex and fiddly IMO than implementing a lazy DFA. (I've done both.)