DFA Combination/Product

[esoterra]

It would be very useful for lexing, and I imagine other tasks if it was possible to combine two DFAs. The combination operations result would be a new DFA which retains the mappings in the first DFA which are not overridden by the second, and completely preserves the mappings of the second.

There are multiple possible options for this api, the simplest of which is probably

impl<T, V> Dfa<T, V> {
   ...
   fn product(&self, other: &DFA<T,V>) -> DFA<T,V> {
      ...
   }
   ...
}

[esoterra]

After thinking about it more, it might be a good idea to generalize the product function. One option would be

impl<T, V> Dfa<T, V> {
   ...
   fn product<V2, V3>(&self, other: &DFA<T,V2>, comb: FnMut(V, V2) -> V3) -> DFA<T,V3> {
      ...
   }
   ...
}

The overlay behavior I previously described could be achieved using the following

let overlay = dfa1.product(dfa2, |_left, right| right);

[esoterra]

Correction to my previous comment about overlay using product. In most "overlay" operations, the left value should likely remain if the right value is not present or less important in some way. An example for option might look like the following.

fn overlay<V>(l: &Option<V>, r: &Option<V>) -> Option<V>
    where
        V: Copy {

    match (*l, *r) {
        (Some(lv), None) => Some(lv),
        (_, Some(rv)) => Some(rv),
        (_, _) => None
    }
}