reduces constant overhead
(
&mut self,
qcur: &mut SparseSet,
qnext: &mut SparseSet,
text: &[u8],
)
| 575 | /// {qcur,qnext} are scratch ordered sets which may be non-empty. |
| 576 | #[inline(always)] // reduces constant overhead |
| 577 | fn exec_at( |
| 578 | &mut self, |
| 579 | qcur: &mut SparseSet, |
| 580 | qnext: &mut SparseSet, |
| 581 | text: &[u8], |
| 582 | ) -> Result<usize> { |
| 583 | // For the most part, the DFA is basically: |
| 584 | // |
| 585 | // last_match = null |
| 586 | // while current_byte != EOF: |
| 587 | // si = current_state.next[current_byte] |
| 588 | // if si is match |
| 589 | // last_match = si |
| 590 | // return last_match |
| 591 | // |
| 592 | // However, we need to deal with a few things: |
| 593 | // |
| 594 | // 1. This is an *online* DFA, so the current state's next list |
| 595 | // may not point to anywhere yet, so we must go out and compute |
| 596 | // them. (They are then cached into the current state's next list |
| 597 | // to avoid re-computation.) |
| 598 | // 2. If we come across a state that is known to be dead (i.e., never |
| 599 | // leads to a match), then we can quit early. |
| 600 | // 3. If the caller just wants to know if a match occurs, then we |
| 601 | // can quit as soon as we know we have a match. (Full leftmost |
| 602 | // first semantics require continuing on.) |
| 603 | // 4. If we're in the start state, then we can use a pre-computed set |
| 604 | // of prefix literals to skip quickly along the input. |
| 605 | // 5. After the input is exhausted, we run the DFA on one symbol |
| 606 | // that stands for EOF. This is useful for handling empty width |
| 607 | // assertions. |
| 608 | // 6. We can't actually do state.next[byte]. Instead, we have to do |
| 609 | // state.next[byte_classes[byte]], which permits us to keep the |
| 610 | // 'next' list very small. |
| 611 | // |
| 612 | // Since there's a bunch of extra stuff we need to consider, we do some |
| 613 | // pretty hairy tricks to get the inner loop to run as fast as |
| 614 | // possible. |
| 615 | debug_assert!(!self.prog.is_reverse); |
| 616 | |
| 617 | // The last match is the currently known ending match position. It is |
| 618 | // reported as an index to the most recent byte that resulted in a |
| 619 | // transition to a match state and is always stored in capture slot `1` |
| 620 | // when searching forwards. Its maximum value is `text.len()`. |
| 621 | let mut result = Result::NoMatch(self.at); |
| 622 | let (mut prev_si, mut next_si) = (self.start, self.start); |
| 623 | let mut at = self.at; |
| 624 | while at < text.len() { |
| 625 | // This is the real inner loop. We take advantage of special bits |
| 626 | // set in the state pointer to determine whether a state is in the |
| 627 | // "common" case or not. Specifically, the common case is a |
| 628 | // non-match non-start non-dead state that has already been |
| 629 | // computed. So long as we remain in the common case, this inner |
| 630 | // loop will chew through the input. |
| 631 | // |
| 632 | // We also unroll the loop 4 times to amortize the cost of checking |
| 633 | // whether we've consumed the entire input. We are also careful |
| 634 | // to make sure that `prev_si` always represents the previous state |
no test coverage detected