Produces a key suitable for describing a state in the DFA cache. The key invariant here is that equivalent keys are produced for any two sets of ordered NFA states (and toggling of whether the previous NFA states contain a match state) that do not discriminate a match for any input. Specifically, q should be an ordered set of NFA states and is_match should be true if and only if the previous NFA
(
&mut self,
q: &SparseSet,
state_flags: &mut StateFlags,
)
| 1209 | /// should be true if and only if the previous NFA states contained a match |
| 1210 | /// state. |
| 1211 | fn cached_state_key( |
| 1212 | &mut self, |
| 1213 | q: &SparseSet, |
| 1214 | state_flags: &mut StateFlags, |
| 1215 | ) -> Option<State> { |
| 1216 | use prog::Inst::*; |
| 1217 | |
| 1218 | // We need to build up enough information to recognize pre-built states |
| 1219 | // in the DFA. Generally speaking, this includes every instruction |
| 1220 | // except for those which are purely epsilon transitions, e.g., the |
| 1221 | // Save and Split instructions. |
| 1222 | // |
| 1223 | // Empty width assertions are also epsilon transitions, but since they |
| 1224 | // are conditional, we need to make them part of a state's key in the |
| 1225 | // cache. |
| 1226 | |
| 1227 | let mut insts = mem::replace( |
| 1228 | &mut self.cache.insts_scratch_space, |
| 1229 | vec![], |
| 1230 | ); |
| 1231 | insts.clear(); |
| 1232 | // Reserve 1 byte for flags. |
| 1233 | insts.push(0); |
| 1234 | |
| 1235 | let mut prev = 0; |
| 1236 | for &ip in q { |
| 1237 | let ip = usize_to_u32(ip); |
| 1238 | match self.prog[ip as usize] { |
| 1239 | Char(_) | Ranges(_) => unreachable!(), |
| 1240 | Save(_) | Split(_) => {} |
| 1241 | Bytes(_) => push_inst_ptr(&mut insts, &mut prev, ip), |
| 1242 | EmptyLook(_) => { |
| 1243 | state_flags.set_empty(); |
| 1244 | push_inst_ptr(&mut insts, &mut prev, ip) |
| 1245 | } |
| 1246 | Match(_) => { |
| 1247 | push_inst_ptr(&mut insts, &mut prev, ip); |
| 1248 | if !self.continue_past_first_match() { |
| 1249 | break; |
| 1250 | } |
| 1251 | } |
| 1252 | } |
| 1253 | } |
| 1254 | // If we couldn't transition to any other instructions and we didn't |
| 1255 | // see a match when expanding NFA states previously, then this is a |
| 1256 | // dead state and no amount of additional input can transition out |
| 1257 | // of this state. |
| 1258 | let opt_state = |
| 1259 | if insts.len() == 1 && !state_flags.is_match() { |
| 1260 | None |
| 1261 | } else { |
| 1262 | let StateFlags(f) = *state_flags; |
| 1263 | insts[0] = f; |
| 1264 | Some(State { data: Arc::from(&*insts) }) |
| 1265 | }; |
| 1266 | self.cache.insts_scratch_space = insts; |
| 1267 | opt_state |
| 1268 | } |
no test coverage detected