class Kleene::MultiMatchDFA

def matches(input) # : Hash(NFA, Array(MatchRef))
  mt = match_tracker(input)
  start_index_to_nfas_that_may_match = mt.invert_candidate_match_start_positions
  mt.empty_matches.each do |nfa_with_dead_err, indices|
    original_nfa = machines_from_nfa_with_dead_err(nfa_with_dead_err).nfa
    indices.each do |index|
      mt.add_match(original_nfa, MatchRef.new(input, index...index))
    end
  end
  active_dfas = Array.new    # the Int32 represents the start of match
  input.each_char.with_index do |char, index|
    active_dfas.reject! do |active_dfa_tuple|
      dfa_clone, original_nfa, start_of_match_index = active_dfa_tuple
      dfa_clone.handle_token!(char, index)
      mt.add_match(original_nfa, MatchRef.new(input, start_of_match_index..index)) if dfa_clone.accept?
      dfa_clone.error?
    end
    if nfas_with_dead_err = start_index_to_nfas_that_may_match[index]
      nfas_with_dead_err.each do |nfa_with_dead_err|
        machines = machines_from_nfa_with_dead_err(nfa_with_dead_err)
        original_nfa = machines.nfa
        dfa = machines.dfa
        dfa_clone = dfa.shallow_clone
        dfa_clone.handle_token!(char, index)
        mt.add_match(original_nfa, MatchRef.new(input, index..index)) if dfa_clone.accept?
        active_dfas << [dfa_clone, original_nfa, index] unless dfa_clone.error?
      end
    end
  end
  mt.matches
end