Method analyze_dfa

lib/pattern.cpp:3857–4419

}

void Pattern::analyze_dfa(DFA::State *start)
{
  DBGLOG("BEGIN Pattern::analyze_dfa()");
  cut_ = 0;
  lbk_ = 0;
  lbm_ = 0;
  cbk_.reset();
  fst_.reset();
  std::set<DFA::State*> start_states;
  if (start->accept == 0)
  {
    // Analyze DFA with a breadth-first search to produce a set of new starting states for more accurate match prediction.
    // A good starting state is one with few edges (chars); we want select a new set of starting states with few edges.
    // We make a DFA graph s-t cut with few edges from which to predict matches.
    // We also cut away edges to states that precede the new starting states, because these repetitions can be ignored.
    // Characters on removed edges are recorded so we can look back to find a full match with the regex matcher.
    // We name an edge a "backedge" when it points to a state before the new starting states, i.e. a loop, not necessarily a cycle.
    bool backedge = false;       // if we found a loop backedge during breadth-first search
    bool has_backedge = false;   // if we found a loop backedge after the last cut to a state after the cut, not before the cut
    uint16_t fin_depth = 0xffff; // shortest distance to a final state
    uint16_t fin_count = 0;      // number of characters to the final states cut off that are not included in the current cut
    std::set<DFA::State*> states;     // current set of breadth-first-search states
    std::set<DFA::State*> fin_states; // set of states to final states not included in the current cut
    reflex::ORanges<Char> chars;      // set of characters on edges before the current cut, the lookback set
    // current cut
    bool cut_backedge = false;   // if we found a loop backedge for the current cut
    uint16_t cut_depth = 0;      // breadth-first search depth of the current cut
    uint16_t cut_fin_depth = 0;  // shortest distance to a final state for the current cut
    uint16_t cut_fin_count = 0;  // number of characters to the final states
    uint16_t cut_span = 0;       // length of the current cut, from the cut to the last state searched
    uint16_t cut_count = 0xffff; // number of characters at the start of the current cut
    uint16_t min_count = 0xffff; // min count of characters over the span of the current cut
    uint16_t max_count = 0;      // max of number of characters over the span of the current cut
    uint8_t max_freq = 0;        // max character frequency over the span of the current cut
    std::set<DFA::State*> cut_states;     // set of states positioned on the left of the cut
    std::set<DFA::State*> cut_fin_states; // set of states to final states not included in the current cut
    reflex::ORanges<Char> cut_chars;      // set of characters on edges before the current cut, the lookback set
    // best cut saved
    bool best_cut_backedge = false;
    uint16_t best_cut_depth = 0;
    uint16_t best_cut_fin_depth = 0xffff;
    uint16_t best_cut_fin_count = 0;
    uint16_t best_cut_span = 0;
    uint16_t best_cut_count = 0xffff;
    uint16_t best_min_count = 0xffff;
    std::set<DFA::State*> best_cut_states;
    std::set<DFA::State*> best_cut_fin_states;
    reflex::ORanges<Char> best_cut_chars;
    // start analyzing the DFA from the start state using a breadth-first search following forward edges to non-visited states
    start->first = 1;
    states.insert(states.begin(), start);
    std::set<DFA::State*> next_states;
    reflex::ORanges<uint16_t> next_chars;
    bool searching = false;
    for (uint16_t depth = 0; depth < DFA::MAX_DEPTH; ++depth)
    {
      next_states.clear();
      next_chars.clear();