transmutability: remove NFA intermediate representation

Prior to this commit, the transmutability analysis used an intermediate
NFA representation of type layout. We then determinized this
representation into a DFA, upon which we ran the core transmutability
analysis. Unfortunately, determinizing NFAs is expensive. In this
commit, we avoid NFAs entirely by observing that Rust `union`s are the
only source of nondeterminism and that it is comparatively cheap to
compute the DFA union of DFAs.

We also implement Graphviz DOT debug formatting of DFAs.

Fixes rust-lang/project-safe-transmute#23
Fixes rust-lang/project-safe-transmute#24

1 files changed, 30 insertions, 1 deletions

diff --git a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
index 69a6b1b77f4..cc6a4dce17b 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
@@ -126,7 +126,7 @@ mod bool {
 
         let into_set = |alts: Vec<_>| {
             #[cfg(feature = "rustc")]
-            let mut set = crate::Set::default();
+            let mut set = rustc_data_structures::fx::FxIndexSet::default();
             #[cfg(not(feature = "rustc"))]
             let mut set = std::collections::HashSet::new();
             set.extend(alts);
@@ -174,3 +174,32 @@ mod bool {
         }
     }
 }
+
+mod union {
+    use super::*;
+
+    #[test]
+    fn union() {
+        let [a, b, c, d] = [0, 1, 2, 3];
+        let s = Dfa::from_edges(a, d, &[(a, 0, b), (b, 0, d), (a, 1, c), (c, 1, d)]);
+
+        let t = Dfa::from_edges(a, c, &[(a, 1, b), (b, 0, c)]);
+
+        let mut ctr = 0;
+        let new_state = || {
+            let state = crate::layout::dfa::State(ctr);
+            ctr += 1;
+            state
+        };
+
+        let u = s.clone().union(t.clone(), new_state);
+
+        let expected_u =
+            Dfa::from_edges(b, a, &[(b, 0, c), (b, 1, d), (d, 1, a), (d, 0, a), (c, 0, a)]);
+
+        assert_eq!(u, expected_u);
+
+        assert_eq!(is_transmutable(&s, &u, Assume::default()), Answer::Yes);
+        assert_eq!(is_transmutable(&t, &u, Assume::default()), Answer::Yes);
+    }
+}