3 ms·

Very interesting, thanks. I still don't understand how you handle capture groups in loops though? My interest was for high trip counts but I think there's just

• mleonhard 5y ago
  Thank you for filing the issue! Here's how safe-regex works: Every matcher has a variable for each byte (b0, b1, etc.) representing states in the NFA. We iterate through the input bytes. In each iteration, we get the next input byte `b` and calculate the transition of every state for consuming that byte. A matcher with no capturing groups uses the type Option<()> to represent each state. That means each state can be Option::Some(()) "input matched up to this point" or Option::None "no match". When the loop finishes, if the `accept` state is Option::Some, then the input matched. We use `Option::filter` to copy the preceding state only if the byte matches. The core of the matcher for "a" [1]: let mut start = Some(()); let mut b0: Option<()> = None; let mut data_iter = data.iter(); loop { let prev_b0 = b0.clone(); if let Some(b) = data_iter.next() { b0 = start.clone().filter(|_| *b == 97u8); start = None; } else { return prev_b0; } } When matching with capturing groups, we must keep track of every capturing group for every state. A capturing group match is two integers representing the start and end of the matching portion of the input. We store that in a Range<usize> struct. There can be multiple capturing groups, so we store the ranges in a tuple. The state variables become type Option<(Range<usize>,)>. When the input enters a capturing group, we set the Range for that group to the input byte: `.map(|(r0,)| (n..n,))`. Technically, it's the zero-length position between the current byte and the previous byte. Whenever a byte matches inside a group, we expand the range for that group to include the byte: `.map(|(r0,)| (r0.start..n + 1,))`. Here's the core of the matcher for "(a)" [1]: let mut start = Some((usize::MAX..usize::MAX,)); let mut b0: Option<(core::ops::Range<usize>,)> = None; let mut accept: Option<(core::ops::Range<usize>,)> = None; let mut data_iter = data.iter(); let mut n = 0; loop { let prev_b0 = b0.clone(); accept = prev_b0.clone(); if let Some(b) = data_iter.next() { b0 = start .clone() .map(|(r0,)| (n..n,)) .clone() .filter(|_| *b == 97u8) .map(|(r0,)| (r0.start..n + 1,)); start = None; } else { break; } n = n + 1; } The matcher for "(abc)d" [2] is a more thorough example. [0] https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/79106c065dc3a8f942ec7190a4bf82286fe0448b/safe-regex/tests/machine.rs#L14 https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/79106c0... [1] https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/79106c065dc3a8f942ec7190a4bf82286fe0448b/safe-regex/tests/machine.rs#L231 https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/79106c0... [2] https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/79106c065dc3a8f942ec7190a4bf82286fe0448b/safe-regex/tests/machine.rs#L695 https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/79106c0...
  • ridiculous_fish 5y ago
    I don't get it? In a DFA there's no way to store "the value of a capture group" because each state may have multiple values for any capture group, depending on how it was reached. WAIT, I think what you've built is NOT a DFA, but an NDFA! Your code has multiple states active at once, and it just tests them all! Ok, now it all makes sense. In a DFA, it's common for a state to have multiple values for capture groups. For example in /(a*)a*/, state 1 is "in the first loop, or in the second loop with \1={0,0}" and state 2 is "in the first loop, in the second loop with \1={0,0}, or in the second loop with \1={0,1}". So the second state has multiple simultaneous values for group 1; this is why tagged-DFAs usually need more "tags" than there are capture groups and that's why I was asking.