summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_transmute
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/rustc_transmute')
-rw-r--r--compiler/rustc_transmute/Cargo.toml28
-rw-r--r--compiler/rustc_transmute/src/layout/dfa.rs184
-rw-r--r--compiler/rustc_transmute/src/layout/mod.rs71
-rw-r--r--compiler/rustc_transmute/src/layout/nfa.rs179
-rw-r--r--compiler/rustc_transmute/src/layout/tree.rs471
-rw-r--r--compiler/rustc_transmute/src/layout/tree/tests.rs80
-rw-r--r--compiler/rustc_transmute/src/lib.rs117
-rw-r--r--compiler/rustc_transmute/src/maybe_transmutable/mod.rs320
-rw-r--r--compiler/rustc_transmute/src/maybe_transmutable/query_context.rs93
-rw-r--r--compiler/rustc_transmute/src/maybe_transmutable/tests.rs115
10 files changed, 1658 insertions, 0 deletions
diff --git a/compiler/rustc_transmute/Cargo.toml b/compiler/rustc_transmute/Cargo.toml
new file mode 100644
index 000000000..9dc96e08a
--- /dev/null
+++ b/compiler/rustc_transmute/Cargo.toml
@@ -0,0 +1,28 @@
+[package]
+name = "rustc_transmute"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+tracing = "0.1"
+rustc_data_structures = { path = "../rustc_data_structures", optional = true}
+rustc_infer = { path = "../rustc_infer", optional = true}
+rustc_macros = { path = "../rustc_macros", optional = true}
+rustc_middle = { path = "../rustc_middle", optional = true}
+rustc_span = { path = "../rustc_span", optional = true}
+rustc_target = { path = "../rustc_target", optional = true}
+
+[features]
+rustc = [
+ "rustc_middle",
+ "rustc_data_structures",
+ "rustc_infer",
+ "rustc_macros",
+ "rustc_span",
+ "rustc_target",
+]
+
+[dev-dependencies]
+itertools = "0.10.1" \ No newline at end of file
diff --git a/compiler/rustc_transmute/src/layout/dfa.rs b/compiler/rustc_transmute/src/layout/dfa.rs
new file mode 100644
index 000000000..b60ea6e7a
--- /dev/null
+++ b/compiler/rustc_transmute/src/layout/dfa.rs
@@ -0,0 +1,184 @@
+use super::{nfa, Byte, Nfa, Ref};
+use crate::Map;
+use std::fmt;
+use std::sync::atomic::{AtomicU32, Ordering};
+
+#[derive(PartialEq, Clone, Debug)]
+pub(crate) struct Dfa<R>
+where
+ R: Ref,
+{
+ pub(crate) transitions: Map<State, Transitions<R>>,
+ pub(crate) start: State,
+ pub(crate) accepting: State,
+}
+
+#[derive(PartialEq, Clone, Debug)]
+pub(crate) struct Transitions<R>
+where
+ R: Ref,
+{
+ byte_transitions: Map<Byte, State>,
+ ref_transitions: Map<R, State>,
+}
+
+impl<R> Default for Transitions<R>
+where
+ R: Ref,
+{
+ fn default() -> Self {
+ Self { byte_transitions: Map::default(), ref_transitions: Map::default() }
+ }
+}
+
+impl<R> Transitions<R>
+where
+ R: Ref,
+{
+ fn insert(&mut self, transition: Transition<R>, state: State) {
+ match transition {
+ Transition::Byte(b) => {
+ self.byte_transitions.insert(b, state);
+ }
+ Transition::Ref(r) => {
+ self.ref_transitions.insert(r, state);
+ }
+ }
+ }
+}
+
+/// The states in a `Nfa` represent byte offsets.
+#[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
+pub(crate) struct State(u32);
+
+#[derive(Hash, Eq, PartialEq, Clone, Copy)]
+pub(crate) enum Transition<R>
+where
+ R: Ref,
+{
+ Byte(Byte),
+ Ref(R),
+}
+
+impl fmt::Debug for State {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "S_{}", self.0)
+ }
+}
+
+impl<R> fmt::Debug for Transition<R>
+where
+ R: Ref,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match &self {
+ Self::Byte(b) => b.fmt(f),
+ Self::Ref(r) => r.fmt(f),
+ }
+ }
+}
+
+impl<R> Dfa<R>
+where
+ R: Ref,
+{
+ pub(crate) fn unit() -> Self {
+ let transitions: Map<State, Transitions<R>> = Map::default();
+ let start = State::new();
+ let accepting = start;
+
+ Self { transitions, start, accepting }
+ }
+
+ #[cfg(test)]
+ pub(crate) fn bool() -> Self {
+ let mut transitions: Map<State, Transitions<R>> = Map::default();
+ let start = State::new();
+ let accepting = State::new();
+
+ transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x00)), accepting);
+
+ transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x01)), accepting);
+
+ Self { transitions, start, accepting }
+ }
+
+ #[instrument(level = "debug")]
+ #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))]
+ pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self {
+ let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa;
+
+ let mut dfa_transitions: Map<State, Transitions<R>> = Map::default();
+ let mut nfa_to_dfa: Map<nfa::State, State> = Map::default();
+ let dfa_start = State::new();
+ nfa_to_dfa.insert(nfa_start, dfa_start);
+
+ let mut queue = vec![(nfa_start, dfa_start)];
+
+ while let Some((nfa_state, dfa_state)) = queue.pop() {
+ if nfa_state == nfa_accepting {
+ continue;
+ }
+
+ for (nfa_transition, next_nfa_states) in nfa_transitions[&nfa_state].iter() {
+ let dfa_transitions =
+ dfa_transitions.entry(dfa_state).or_insert_with(Default::default);
+
+ let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied());
+
+ let next_dfa_state = match nfa_transition {
+ &nfa::Transition::Byte(b) => *dfa_transitions
+ .byte_transitions
+ .entry(b)
+ .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
+ &nfa::Transition::Ref(r) => *dfa_transitions
+ .ref_transitions
+ .entry(r)
+ .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
+ };
+
+ for &next_nfa_state in next_nfa_states {
+ nfa_to_dfa.entry(next_nfa_state).or_insert_with(|| {
+ queue.push((next_nfa_state, next_dfa_state));
+ next_dfa_state
+ });
+ }
+ }
+ }
+
+ let dfa_accepting = nfa_to_dfa[&nfa_accepting];
+
+ Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting }
+ }
+
+ pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> {
+ Some(&self.transitions.get(&start)?.byte_transitions)
+ }
+
+ pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> {
+ self.transitions.get(&start)?.byte_transitions.get(&byte).copied()
+ }
+
+ pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> {
+ Some(&self.transitions.get(&start)?.ref_transitions)
+ }
+}
+
+impl State {
+ pub(crate) fn new() -> Self {
+ static COUNTER: AtomicU32 = AtomicU32::new(0);
+ Self(COUNTER.fetch_add(1, Ordering::SeqCst))
+ }
+}
+
+impl<R> From<nfa::Transition<R>> for Transition<R>
+where
+ R: Ref,
+{
+ fn from(nfa_transition: nfa::Transition<R>) -> Self {
+ match nfa_transition {
+ nfa::Transition::Byte(byte) => Transition::Byte(byte),
+ nfa::Transition::Ref(r) => Transition::Ref(r),
+ }
+ }
+}
diff --git a/compiler/rustc_transmute/src/layout/mod.rs b/compiler/rustc_transmute/src/layout/mod.rs
new file mode 100644
index 000000000..07035ebdf
--- /dev/null
+++ b/compiler/rustc_transmute/src/layout/mod.rs
@@ -0,0 +1,71 @@
+use std::fmt::{self, Debug};
+use std::hash::Hash;
+
+pub(crate) mod tree;
+pub(crate) use tree::Tree;
+
+pub(crate) mod nfa;
+pub(crate) use nfa::Nfa;
+
+pub(crate) mod dfa;
+pub(crate) use dfa::Dfa;
+
+#[derive(Debug)]
+pub(crate) struct Uninhabited;
+
+/// An instance of a byte is either initialized to a particular value, or uninitialized.
+#[derive(Hash, Eq, PartialEq, Clone, Copy)]
+pub(crate) enum Byte {
+ Uninit,
+ Init(u8),
+}
+
+impl fmt::Debug for Byte {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match &self {
+ Self::Uninit => f.write_str("??u8"),
+ Self::Init(b) => write!(f, "{:#04x}u8", b),
+ }
+ }
+}
+
+pub(crate) trait Def: Debug + Hash + Eq + PartialEq + Copy + Clone {}
+pub trait Ref: Debug + Hash + Eq + PartialEq + Copy + Clone {}
+
+impl Def for ! {}
+impl Ref for ! {}
+
+#[cfg(feature = "rustc")]
+pub(crate) mod rustc {
+ use rustc_middle::mir::Mutability;
+ use rustc_middle::ty;
+ use rustc_middle::ty::Region;
+ use rustc_middle::ty::Ty;
+
+ /// A reference in the layout.
+ #[derive(Debug, Hash, Eq, PartialEq, PartialOrd, Ord, Clone, Copy)]
+ pub struct Ref<'tcx> {
+ lifetime: Region<'tcx>,
+ ty: Ty<'tcx>,
+ mutability: Mutability,
+ }
+
+ impl<'tcx> super::Ref for Ref<'tcx> {}
+
+ impl<'tcx> Ref<'tcx> {
+ pub fn min_align(&self) -> usize {
+ todo!()
+ }
+ }
+
+ /// A visibility node in the layout.
+ #[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)]
+ pub enum Def<'tcx> {
+ Adt(ty::AdtDef<'tcx>),
+ Variant(&'tcx ty::VariantDef),
+ Field(&'tcx ty::FieldDef),
+ Primitive,
+ }
+
+ impl<'tcx> super::Def for Def<'tcx> {}
+}
diff --git a/compiler/rustc_transmute/src/layout/nfa.rs b/compiler/rustc_transmute/src/layout/nfa.rs
new file mode 100644
index 000000000..f25e3c1fd
--- /dev/null
+++ b/compiler/rustc_transmute/src/layout/nfa.rs
@@ -0,0 +1,179 @@
+use super::{Byte, Ref, Tree, Uninhabited};
+use crate::{Map, Set};
+use std::fmt;
+use std::sync::atomic::{AtomicU32, Ordering};
+
+/// A non-deterministic finite automaton (NFA) that represents the layout of a type.
+/// The transmutability of two given types is computed by comparing their `Nfa`s.
+#[derive(PartialEq, Debug)]
+pub(crate) struct Nfa<R>
+where
+ R: Ref,
+{
+ pub(crate) transitions: Map<State, Map<Transition<R>, Set<State>>>,
+ pub(crate) start: State,
+ pub(crate) accepting: State,
+}
+
+/// The states in a `Nfa` represent byte offsets.
+#[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
+pub(crate) struct State(u32);
+
+/// The transitions between states in a `Nfa` reflect bit validity.
+#[derive(Hash, Eq, PartialEq, Clone, Copy)]
+pub(crate) enum Transition<R>
+where
+ R: Ref,
+{
+ Byte(Byte),
+ Ref(R),
+}
+
+impl fmt::Debug for State {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "S_{}", self.0)
+ }
+}
+
+impl<R> fmt::Debug for Transition<R>
+where
+ R: Ref,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match &self {
+ Self::Byte(b) => b.fmt(f),
+ Self::Ref(r) => r.fmt(f),
+ }
+ }
+}
+
+impl<R> Nfa<R>
+where
+ R: Ref,
+{
+ pub(crate) fn unit() -> Self {
+ let transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
+ let start = State::new();
+ let accepting = start;
+
+ Nfa { transitions, start, accepting }
+ }
+
+ pub(crate) fn from_byte(byte: Byte) -> Self {
+ let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
+ let start = State::new();
+ let accepting = State::new();
+
+ let source = transitions.entry(start).or_default();
+ let edge = source.entry(Transition::Byte(byte)).or_default();
+ edge.insert(accepting);
+
+ Nfa { transitions, start, accepting }
+ }
+
+ pub(crate) fn from_ref(r: R) -> Self {
+ let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = Map::default();
+ let start = State::new();
+ let accepting = State::new();
+
+ let source = transitions.entry(start).or_default();
+ let edge = source.entry(Transition::Ref(r)).or_default();
+ edge.insert(accepting);
+
+ Nfa { transitions, start, accepting }
+ }
+
+ pub(crate) fn from_tree(tree: Tree<!, R>) -> Result<Self, Uninhabited> {
+ Ok(match tree {
+ Tree::Byte(b) => Self::from_byte(b),
+ Tree::Def(..) => unreachable!(),
+ Tree::Ref(r) => Self::from_ref(r),
+ Tree::Alt(alts) => {
+ let mut alts = alts.into_iter().map(Self::from_tree);
+ let mut nfa = alts.next().ok_or(Uninhabited)??;
+ for alt in alts {
+ nfa = nfa.union(alt?);
+ }
+ nfa
+ }
+ Tree::Seq(elts) => {
+ let mut nfa = Self::unit();
+ for elt in elts.into_iter().map(Self::from_tree) {
+ nfa = nfa.concat(elt?);
+ }
+ nfa
+ }
+ })
+ }
+
+ /// Concatenate two `Nfa`s.
+ pub(crate) fn concat(self, other: Self) -> Self {
+ if self.start == self.accepting {
+ return other;
+ } else if other.start == other.accepting {
+ return self;
+ }
+
+ let start = self.start;
+ let accepting = other.accepting;
+
+ let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = self.transitions;
+
+ // the iteration order doesn't matter
+ #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))]
+ for (source, transition) in other.transitions {
+ let fix_state = |state| if state == other.start { self.accepting } else { state };
+ let entry = transitions.entry(fix_state(source)).or_default();
+ for (edge, destinations) in transition {
+ let entry = entry.entry(edge.clone()).or_default();
+ for destination in destinations {
+ entry.insert(fix_state(destination));
+ }
+ }
+ }
+
+ Self { transitions, start, accepting }
+ }
+
+ /// Compute the union of two `Nfa`s.
+ pub(crate) fn union(self, other: Self) -> Self {
+ let start = self.start;
+ let accepting = self.accepting;
+
+ let mut transitions: Map<State, Map<Transition<R>, Set<State>>> = self.transitions.clone();
+
+ // the iteration order doesn't matter
+ #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))]
+ for (&(mut source), transition) in other.transitions.iter() {
+ // if source is starting state of `other`, replace with starting state of `self`
+ if source == other.start {
+ source = self.start;
+ }
+ let entry = transitions.entry(source).or_default();
+ for (edge, destinations) in transition {
+ let entry = entry.entry(edge.clone()).or_default();
+ // the iteration order doesn't matter
+ #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))]
+ for &(mut destination) in destinations {
+ // if dest is accepting state of `other`, replace with accepting state of `self`
+ if destination == other.accepting {
+ destination = self.accepting;
+ }
+ entry.insert(destination);
+ }
+ }
+ }
+ Self { transitions, start, accepting }
+ }
+
+ pub(crate) fn edges_from(&self, start: State) -> Option<&Map<Transition<R>, Set<State>>> {
+ self.transitions.get(&start)
+ }
+}
+
+impl State {
+ pub(crate) fn new() -> Self {
+ static COUNTER: AtomicU32 = AtomicU32::new(0);
+ Self(COUNTER.fetch_add(1, Ordering::SeqCst))
+ }
+}
diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs
new file mode 100644
index 000000000..70b3ba02b
--- /dev/null
+++ b/compiler/rustc_transmute/src/layout/tree.rs
@@ -0,0 +1,471 @@
+use super::{Byte, Def, Ref};
+
+#[cfg(test)]
+mod tests;
+
+/// A tree-based representation of a type layout.
+///
+/// Invariants:
+/// 1. All paths through the layout have the same length (in bytes).
+///
+/// Nice-to-haves:
+/// 1. An `Alt` is never directly nested beneath another `Alt`.
+/// 2. A `Seq` is never directly nested beneath another `Seq`.
+/// 3. `Seq`s and `Alt`s with a single member do not exist.
+#[derive(Clone, Debug, Hash, PartialEq, Eq)]
+pub(crate) enum Tree<D, R>
+where
+ D: Def,
+ R: Ref,
+{
+ /// A sequence of successive layouts.
+ Seq(Vec<Self>),
+ /// A choice between alternative layouts.
+ Alt(Vec<Self>),
+ /// A definition node.
+ Def(D),
+ /// A reference node.
+ Ref(R),
+ /// A byte node.
+ Byte(Byte),
+}
+
+impl<D, R> Tree<D, R>
+where
+ D: Def,
+ R: Ref,
+{
+ /// A `Tree` consisting only of a definition node.
+ pub(crate) fn def(def: D) -> Self {
+ Self::Def(def)
+ }
+
+ /// A `Tree` representing an uninhabited type.
+ pub(crate) fn uninhabited() -> Self {
+ Self::Alt(vec![])
+ }
+
+ /// A `Tree` representing a zero-sized type.
+ pub(crate) fn unit() -> Self {
+ Self::Seq(Vec::new())
+ }
+
+ /// A `Tree` containing a single, uninitialized byte.
+ pub(crate) fn uninit() -> Self {
+ Self::Byte(Byte::Uninit)
+ }
+
+ /// A `Tree` representing the layout of `bool`.
+ pub(crate) fn bool() -> Self {
+ Self::from_bits(0x00).or(Self::from_bits(0x01))
+ }
+
+ /// A `Tree` whose layout matches that of a `u8`.
+ pub(crate) fn u8() -> Self {
+ Self::Alt((0u8..=255).map(Self::from_bits).collect())
+ }
+
+ /// A `Tree` whose layout accepts exactly the given bit pattern.
+ pub(crate) fn from_bits(bits: u8) -> Self {
+ Self::Byte(Byte::Init(bits))
+ }
+
+ /// A `Tree` whose layout is a number of the given width.
+ pub(crate) fn number(width_in_bytes: usize) -> Self {
+ Self::Seq(vec![Self::u8(); width_in_bytes])
+ }
+
+ /// A `Tree` whose layout is entirely padding of the given width.
+ pub(crate) fn padding(width_in_bytes: usize) -> Self {
+ Self::Seq(vec![Self::uninit(); width_in_bytes])
+ }
+
+ /// Remove all `Def` nodes, and all branches of the layout for which `f` produces false.
+ pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R>
+ where
+ F: Fn(D) -> bool,
+ {
+ match self {
+ Self::Seq(elts) => elts
+ .into_iter()
+ .map(|elt| elt.prune(f))
+ .try_fold(Tree::unit(), |elts, elt| {
+ if elt == Tree::uninhabited() {
+ Err(Tree::uninhabited())
+ } else {
+ Ok(elts.then(elt))
+ }
+ })
+ .into_ok_or_err(),
+ Self::Alt(alts) => alts
+ .into_iter()
+ .map(|alt| alt.prune(f))
+ .fold(Tree::uninhabited(), |alts, alt| alts.or(alt)),
+ Self::Byte(b) => Tree::Byte(b),
+ Self::Ref(r) => Tree::Ref(r),
+ Self::Def(d) => {
+ if !f(d) {
+ Tree::uninhabited()
+ } else {
+ Tree::unit()
+ }
+ }
+ }
+ }
+
+ /// Produces `true` if `Tree` is an inhabited type; otherwise false.
+ pub(crate) fn is_inhabited(&self) -> bool {
+ match self {
+ Self::Seq(elts) => elts.into_iter().all(|elt| elt.is_inhabited()),
+ Self::Alt(alts) => alts.into_iter().any(|alt| alt.is_inhabited()),
+ Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true,
+ }
+ }
+}
+
+impl<D, R> Tree<D, R>
+where
+ D: Def,
+ R: Ref,
+{
+ /// Produces a new `Tree` where `other` is sequenced after `self`.
+ pub(crate) fn then(self, other: Self) -> Self {
+ match (self, other) {
+ (Self::Seq(elts), other) | (other, Self::Seq(elts)) if elts.len() == 0 => other,
+ (Self::Seq(mut lhs), Self::Seq(mut rhs)) => {
+ lhs.append(&mut rhs);
+ Self::Seq(lhs)
+ }
+ (Self::Seq(mut lhs), rhs) => {
+ lhs.push(rhs);
+ Self::Seq(lhs)
+ }
+ (lhs, Self::Seq(mut rhs)) => {
+ rhs.insert(0, lhs);
+ Self::Seq(rhs)
+ }
+ (lhs, rhs) => Self::Seq(vec![lhs, rhs]),
+ }
+ }
+
+ /// Produces a new `Tree` accepting either `self` or `other` as alternative layouts.
+ pub(crate) fn or(self, other: Self) -> Self {
+ match (self, other) {
+ (Self::Alt(alts), other) | (other, Self::Alt(alts)) if alts.len() == 0 => other,
+ (Self::Alt(mut lhs), Self::Alt(rhs)) => {
+ lhs.extend(rhs);
+ Self::Alt(lhs)
+ }
+ (Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => {
+ alts.push(alt);
+ Self::Alt(alts)
+ }
+ (lhs, rhs) => Self::Alt(vec![lhs, rhs]),
+ }
+ }
+}
+
+#[derive(Debug, Copy, Clone)]
+pub(crate) enum Err {
+ /// The layout of the type is unspecified.
+ Unspecified,
+ /// This error will be surfaced elsewhere by rustc, so don't surface it.
+ Unknown,
+}
+
+#[cfg(feature = "rustc")]
+pub(crate) mod rustc {
+ use super::{Err, Tree};
+ use crate::layout::rustc::{Def, Ref};
+
+ use rustc_middle::ty;
+ use rustc_middle::ty::layout::LayoutError;
+ use rustc_middle::ty::util::Discr;
+ use rustc_middle::ty::AdtDef;
+ use rustc_middle::ty::ParamEnv;
+ use rustc_middle::ty::SubstsRef;
+ use rustc_middle::ty::Ty;
+ use rustc_middle::ty::TyCtxt;
+ use rustc_middle::ty::VariantDef;
+ use rustc_target::abi::Align;
+ use std::alloc;
+
+ impl<'tcx> From<LayoutError<'tcx>> for Err {
+ fn from(err: LayoutError<'tcx>) -> Self {
+ match err {
+ LayoutError::Unknown(..) => Self::Unknown,
+ err @ _ => unimplemented!("{:?}", err),
+ }
+ }
+ }
+
+ trait LayoutExt {
+ fn clamp_align(&self, min_align: Align, max_align: Align) -> Self;
+ }
+
+ impl LayoutExt for alloc::Layout {
+ fn clamp_align(&self, min_align: Align, max_align: Align) -> Self {
+ let min_align = min_align.bytes().try_into().unwrap();
+ let max_align = max_align.bytes().try_into().unwrap();
+ Self::from_size_align(self.size(), self.align().clamp(min_align, max_align)).unwrap()
+ }
+ }
+
+ struct LayoutSummary {
+ total_align: Align,
+ total_size: usize,
+ discriminant_size: usize,
+ discriminant_align: Align,
+ }
+
+ impl LayoutSummary {
+ fn from_ty<'tcx>(ty: Ty<'tcx>, ctx: TyCtxt<'tcx>) -> Result<Self, LayoutError<'tcx>> {
+ use rustc_middle::ty::ParamEnvAnd;
+ use rustc_target::abi::{TyAndLayout, Variants};
+
+ let param_env = ParamEnv::reveal_all();
+ let param_env_and_type = ParamEnvAnd { param_env, value: ty };
+ let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?;
+
+ let total_size: usize = layout.size().bytes_usize();
+ let total_align: Align = layout.align().abi;
+ let discriminant_align: Align;
+ let discriminant_size: usize;
+
+ if let Variants::Multiple { tag, .. } = layout.variants() {
+ discriminant_align = tag.align(&ctx).abi;
+ discriminant_size = tag.size(&ctx).bytes_usize();
+ } else {
+ discriminant_align = Align::ONE;
+ discriminant_size = 0;
+ };
+
+ Ok(Self { total_align, total_size, discriminant_align, discriminant_size })
+ }
+
+ fn into(&self) -> alloc::Layout {
+ alloc::Layout::from_size_align(
+ self.total_size,
+ self.total_align.bytes().try_into().unwrap(),
+ )
+ .unwrap()
+ }
+ }
+
+ impl<'tcx> Tree<Def<'tcx>, Ref<'tcx>> {
+ pub fn from_ty(ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Result<Self, Err> {
+ use rustc_middle::ty::FloatTy::*;
+ use rustc_middle::ty::IntTy::*;
+ use rustc_middle::ty::UintTy::*;
+ use rustc_target::abi::HasDataLayout;
+
+ let target = tcx.data_layout();
+
+ match ty.kind() {
+ ty::Bool => Ok(Self::bool()),
+
+ ty::Int(I8) | ty::Uint(U8) => Ok(Self::u8()),
+ ty::Int(I16) | ty::Uint(U16) => Ok(Self::number(2)),
+ ty::Int(I32) | ty::Uint(U32) | ty::Float(F32) => Ok(Self::number(4)),
+ ty::Int(I64) | ty::Uint(U64) | ty::Float(F64) => Ok(Self::number(8)),
+ ty::Int(I128) | ty::Uint(U128) => Ok(Self::number(16)),
+ ty::Int(Isize) | ty::Uint(Usize) => {
+ Ok(Self::number(target.pointer_size.bytes_usize()))
+ }
+
+ ty::Tuple(members) => {
+ if members.len() == 0 {
+ Ok(Tree::unit())
+ } else {
+ Err(Err::Unspecified)
+ }
+ }
+
+ ty::Array(ty, len) => {
+ let len = len.try_eval_usize(tcx, ParamEnv::reveal_all()).unwrap();
+ let elt = Tree::from_ty(*ty, tcx)?;
+ Ok(std::iter::repeat(elt)
+ .take(len as usize)
+ .fold(Tree::unit(), |tree, elt| tree.then(elt)))
+ }
+
+ ty::Adt(adt_def, substs_ref) => {
+ use rustc_middle::ty::AdtKind;
+
+ // If the layout is ill-specified, halt.
+ if !(adt_def.repr().c() || adt_def.repr().int.is_some()) {
+ return Err(Err::Unspecified);
+ }
+
+ // Compute a summary of the type's layout.
+ let layout_summary = LayoutSummary::from_ty(ty, tcx)?;
+
+ // The layout begins with this adt's visibility.
+ let vis = Self::def(Def::Adt(*adt_def));
+
+ // And is followed the layout(s) of its variants
+ Ok(vis.then(match adt_def.adt_kind() {
+ AdtKind::Struct => Self::from_repr_c_variant(
+ ty,
+ *adt_def,
+ substs_ref,
+ &layout_summary,
+ None,
+ adt_def.non_enum_variant(),
+ tcx,
+ )?,
+ AdtKind::Enum => {
+ tracing::trace!(?adt_def, "treeifying enum");
+ let mut tree = Tree::uninhabited();
+
+ for (idx, discr) in adt_def.discriminants(tcx) {
+ tree = tree.or(Self::from_repr_c_variant(
+ ty,
+ *adt_def,
+ substs_ref,
+ &layout_summary,
+ Some(discr),
+ adt_def.variant(idx),
+ tcx,
+ )?);
+ }
+
+ tree
+ }
+ AdtKind::Union => {
+ // is the layout well-defined?
+ if !adt_def.repr().c() {
+ return Err(Err::Unspecified);
+ }
+
+ let ty_layout = layout_of(tcx, ty)?;
+
+ let mut tree = Tree::uninhabited();
+
+ for field in adt_def.all_fields() {
+ let variant_ty = field.ty(tcx, substs_ref);
+ let variant_layout = layout_of(tcx, variant_ty)?;
+ let padding_needed = ty_layout.size() - variant_layout.size();
+ let variant = Self::def(Def::Field(field))
+ .then(Self::from_ty(variant_ty, tcx)?)
+ .then(Self::padding(padding_needed));
+
+ tree = tree.or(variant);
+ }
+
+ tree
+ }
+ }))
+ }
+ _ => Err(Err::Unspecified),
+ }
+ }
+
+ fn from_repr_c_variant(
+ ty: Ty<'tcx>,
+ adt_def: AdtDef<'tcx>,
+ substs_ref: SubstsRef<'tcx>,
+ layout_summary: &LayoutSummary,
+ discr: Option<Discr<'tcx>>,
+ variant_def: &'tcx VariantDef,
+ tcx: TyCtxt<'tcx>,
+ ) -> Result<Self, Err> {
+ let mut tree = Tree::unit();
+
+ let repr = adt_def.repr();
+ let min_align = repr.align.unwrap_or(Align::ONE);
+ let max_align = repr.pack.unwrap_or(Align::MAX);
+
+ let clamp =
+ |align: Align| align.clamp(min_align, max_align).bytes().try_into().unwrap();
+
+ let variant_span = tracing::trace_span!(
+ "treeifying variant",
+ min_align = ?min_align,
+ max_align = ?max_align,
+ )
+ .entered();
+
+ let mut variant_layout = alloc::Layout::from_size_align(
+ 0,
+ layout_summary.total_align.bytes().try_into().unwrap(),
+ )
+ .unwrap();
+
+ // The layout of the variant is prefixed by the discriminant, if any.
+ if let Some(discr) = discr {
+ tracing::trace!(?discr, "treeifying discriminant");
+ let discr_layout = alloc::Layout::from_size_align(
+ layout_summary.discriminant_size,
+ clamp(layout_summary.discriminant_align),
+ )
+ .unwrap();
+ tracing::trace!(?discr_layout, "computed discriminant layout");
+ variant_layout = variant_layout.extend(discr_layout).unwrap().0;
+ tree = tree.then(Self::from_disr(discr, tcx, layout_summary.discriminant_size));
+ }
+
+ // Next come fields.
+ let fields_span = tracing::trace_span!("treeifying fields").entered();
+ for field_def in variant_def.fields.iter() {
+ let field_ty = field_def.ty(tcx, substs_ref);
+ let _span = tracing::trace_span!("treeifying field", field = ?field_ty).entered();
+
+ // begin with the field's visibility
+ tree = tree.then(Self::def(Def::Field(field_def)));
+
+ // compute the field's layout charactaristics
+ let field_layout = layout_of(tcx, field_ty)?.clamp_align(min_align, max_align);
+
+ // next comes the field's padding
+ let padding_needed = variant_layout.padding_needed_for(field_layout.align());
+ if padding_needed > 0 {
+ tree = tree.then(Self::padding(padding_needed));
+ }
+
+ // finally, the field's layout
+ tree = tree.then(Self::from_ty(field_ty, tcx)?);
+
+ // extend the variant layout with the field layout
+ variant_layout = variant_layout.extend(field_layout).unwrap().0;
+ }
+ drop(fields_span);
+
+ // finally: padding
+ let padding_span = tracing::trace_span!("adding trailing padding").entered();
+ let padding_needed = layout_summary.total_size - variant_layout.size();
+ if padding_needed > 0 {
+ tree = tree.then(Self::padding(padding_needed));
+ };
+ drop(padding_span);
+ drop(variant_span);
+ Ok(tree)
+ }
+
+ pub fn from_disr(discr: Discr<'tcx>, tcx: TyCtxt<'tcx>, size: usize) -> Self {
+ // FIXME(@jswrenn): I'm certain this is missing needed endian nuance.
+ let bytes = discr.val.to_ne_bytes();
+ let bytes = &bytes[..size];
+ Self::Seq(bytes.into_iter().copied().map(|b| Self::from_bits(b)).collect())
+ }
+ }
+
+ fn layout_of<'tcx>(
+ ctx: TyCtxt<'tcx>,
+ ty: Ty<'tcx>,
+ ) -> Result<alloc::Layout, LayoutError<'tcx>> {
+ use rustc_middle::ty::ParamEnvAnd;
+ use rustc_target::abi::TyAndLayout;
+
+ let param_env = ParamEnv::reveal_all();
+ let param_env_and_type = ParamEnvAnd { param_env, value: ty };
+ let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?;
+ let layout = alloc::Layout::from_size_align(
+ layout.size().bytes_usize(),
+ layout.align().abi.bytes().try_into().unwrap(),
+ )
+ .unwrap();
+ tracing::trace!(?ty, ?layout, "computed layout for type");
+ Ok(layout)
+ }
+}
diff --git a/compiler/rustc_transmute/src/layout/tree/tests.rs b/compiler/rustc_transmute/src/layout/tree/tests.rs
new file mode 100644
index 000000000..90515e92f
--- /dev/null
+++ b/compiler/rustc_transmute/src/layout/tree/tests.rs
@@ -0,0 +1,80 @@
+use super::Tree;
+
+#[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)]
+pub enum Def {
+ Visible,
+ Invisible,
+}
+
+impl super::Def for Def {}
+
+mod prune {
+ use super::*;
+
+ mod should_simplify {
+ use super::*;
+
+ #[test]
+ fn seq_1() {
+ let layout: Tree<Def, !> = Tree::def(Def::Visible).then(Tree::from_bits(0x00));
+ assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::from_bits(0x00));
+ }
+
+ #[test]
+ fn seq_2() {
+ let layout: Tree<Def, !> =
+ Tree::from_bits(0x00).then(Tree::def(Def::Visible)).then(Tree::from_bits(0x01));
+
+ assert_eq!(
+ layout.prune(&|d| matches!(d, Def::Visible)),
+ Tree::from_bits(0x00).then(Tree::from_bits(0x01))
+ );
+ }
+ }
+
+ mod should_reject {
+ use super::*;
+
+ #[test]
+ fn invisible_def() {
+ let layout: Tree<Def, !> = Tree::def(Def::Invisible);
+ assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::uninhabited());
+ }
+
+ #[test]
+ fn invisible_def_in_seq_len_2() {
+ let layout: Tree<Def, !> = Tree::def(Def::Visible).then(Tree::def(Def::Invisible));
+ assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::uninhabited());
+ }
+
+ #[test]
+ fn invisible_def_in_seq_len_3() {
+ let layout: Tree<Def, !> =
+ Tree::def(Def::Visible).then(Tree::from_bits(0x00)).then(Tree::def(Def::Invisible));
+ assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::uninhabited());
+ }
+ }
+
+ mod should_accept {
+ use super::*;
+
+ #[test]
+ fn visible_def() {
+ let layout: Tree<Def, !> = Tree::def(Def::Visible);
+ assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::unit());
+ }
+
+ #[test]
+ fn visible_def_in_seq_len_2() {
+ let layout: Tree<Def, !> = Tree::def(Def::Visible).then(Tree::def(Def::Visible));
+ assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::unit());
+ }
+
+ #[test]
+ fn visible_def_in_seq_len_3() {
+ let layout: Tree<Def, !> =
+ Tree::def(Def::Visible).then(Tree::from_bits(0x00)).then(Tree::def(Def::Visible));
+ assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::from_bits(0x00));
+ }
+ }
+}
diff --git a/compiler/rustc_transmute/src/lib.rs b/compiler/rustc_transmute/src/lib.rs
new file mode 100644
index 000000000..cfc7c752a
--- /dev/null
+++ b/compiler/rustc_transmute/src/lib.rs
@@ -0,0 +1,117 @@
+#![feature(
+ alloc_layout_extra,
+ control_flow_enum,
+ decl_macro,
+ iterator_try_reduce,
+ never_type,
+ result_into_ok_or_err
+)]
+#![allow(dead_code, unused_variables)]
+
+#[macro_use]
+extern crate tracing;
+
+#[cfg(feature = "rustc")]
+pub(crate) use rustc_data_structures::fx::{FxHashMap as Map, FxHashSet as Set};
+
+#[cfg(not(feature = "rustc"))]
+pub(crate) use std::collections::{HashMap as Map, HashSet as Set};
+
+pub(crate) mod layout;
+pub(crate) mod maybe_transmutable;
+
+#[derive(Default)]
+pub struct Assume {
+ pub alignment: bool,
+ pub lifetimes: bool,
+ pub validity: bool,
+ pub visibility: bool,
+}
+
+/// The type encodes answers to the question: "Are these types transmutable?"
+#[derive(Debug, Hash, Eq, PartialEq, PartialOrd, Ord, Clone)]
+pub enum Answer<R>
+where
+ R: layout::Ref,
+{
+ /// `Src` is transmutable into `Dst`.
+ Yes,
+
+ /// `Src` is NOT transmutable into `Dst`.
+ No(Reason),
+
+ /// `Src` is transmutable into `Dst`, if `src` is transmutable into `dst`.
+ IfTransmutable { src: R, dst: R },
+
+ /// `Src` is transmutable into `Dst`, if all of the enclosed requirements are met.
+ IfAll(Vec<Answer<R>>),
+
+ /// `Src` is transmutable into `Dst` if any of the enclosed requirements are met.
+ IfAny(Vec<Answer<R>>),
+}
+
+/// Answers: Why wasn't the source type transmutable into the destination type?
+#[derive(Debug, Hash, Eq, PartialEq, PartialOrd, Ord, Clone)]
+pub enum Reason {
+ /// The layout of the source type is unspecified.
+ SrcIsUnspecified,
+ /// The layout of the destination type is unspecified.
+ DstIsUnspecified,
+ /// The layout of the destination type is bit-incompatible with the source type.
+ DstIsBitIncompatible,
+ /// There aren't any public constructors for `Dst`.
+ DstIsPrivate,
+ /// `Dst` is larger than `Src`, and the excess bytes were not exclusively uninitialized.
+ DstIsTooBig,
+}
+
+#[cfg(feature = "rustc")]
+mod rustc {
+ use rustc_infer::infer::InferCtxt;
+ use rustc_macros::{TypeFoldable, TypeVisitable};
+ use rustc_middle::traits::ObligationCause;
+ use rustc_middle::ty::Binder;
+ use rustc_middle::ty::Ty;
+
+ /// The source and destination types of a transmutation.
+ #[derive(TypeFoldable, TypeVisitable, Debug, Clone, Copy)]
+ pub struct Types<'tcx> {
+ /// The source type.
+ pub src: Ty<'tcx>,
+ /// The destination type.
+ pub dst: Ty<'tcx>,
+ }
+
+ pub struct TransmuteTypeEnv<'cx, 'tcx> {
+ infcx: &'cx InferCtxt<'cx, 'tcx>,
+ }
+
+ impl<'cx, 'tcx> TransmuteTypeEnv<'cx, 'tcx> {
+ pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>) -> Self {
+ Self { infcx }
+ }
+
+ #[allow(unused)]
+ pub fn is_transmutable(
+ &mut self,
+ cause: ObligationCause<'tcx>,
+ src_and_dst: Binder<'tcx, Types<'tcx>>,
+ scope: Ty<'tcx>,
+ assume: crate::Assume,
+ ) -> crate::Answer<crate::layout::rustc::Ref<'tcx>> {
+ let src = src_and_dst.map_bound(|types| types.src).skip_binder();
+ let dst = src_and_dst.map_bound(|types| types.dst).skip_binder();
+ crate::maybe_transmutable::MaybeTransmutableQuery::new(
+ src,
+ dst,
+ scope,
+ assume,
+ self.infcx.tcx,
+ )
+ .answer()
+ }
+ }
+}
+
+#[cfg(feature = "rustc")]
+pub use rustc::*;
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
new file mode 100644
index 000000000..076d922d1
--- /dev/null
+++ b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
@@ -0,0 +1,320 @@
+use crate::Map;
+use crate::{Answer, Reason};
+
+#[cfg(test)]
+mod tests;
+
+mod query_context;
+use query_context::QueryContext;
+
+use crate::layout::{self, dfa, Byte, Dfa, Nfa, Tree, Uninhabited};
+pub(crate) struct MaybeTransmutableQuery<L, C>
+where
+ C: QueryContext,
+{
+ src: L,
+ dst: L,
+ scope: <C as QueryContext>::Scope,
+ assume: crate::Assume,
+ context: C,
+}
+
+impl<L, C> MaybeTransmutableQuery<L, C>
+where
+ C: QueryContext,
+{
+ pub(crate) fn new(
+ src: L,
+ dst: L,
+ scope: <C as QueryContext>::Scope,
+ assume: crate::Assume,
+ context: C,
+ ) -> Self {
+ Self { src, dst, scope, assume, context }
+ }
+
+ pub(crate) fn map_layouts<F, M>(
+ self,
+ f: F,
+ ) -> Result<MaybeTransmutableQuery<M, C>, Answer<<C as QueryContext>::Ref>>
+ where
+ F: FnOnce(
+ L,
+ L,
+ <C as QueryContext>::Scope,
+ &C,
+ ) -> Result<(M, M), Answer<<C as QueryContext>::Ref>>,
+ {
+ let Self { src, dst, scope, assume, context } = self;
+
+ let (src, dst) = f(src, dst, scope, &context)?;
+
+ Ok(MaybeTransmutableQuery { src, dst, scope, assume, context })
+ }
+}
+
+#[cfg(feature = "rustc")]
+mod rustc {
+ use super::*;
+ use crate::layout::tree::Err;
+
+ use rustc_middle::ty::Ty;
+ use rustc_middle::ty::TyCtxt;
+
+ impl<'tcx> MaybeTransmutableQuery<Ty<'tcx>, TyCtxt<'tcx>> {
+ /// This method begins by converting `src` and `dst` from `Ty`s to `Tree`s,
+ /// then computes an answer using those trees.
+ #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
+ pub fn answer(self) -> Answer<<TyCtxt<'tcx> as QueryContext>::Ref> {
+ let query_or_answer = self.map_layouts(|src, dst, scope, &context| {
+ // Convert `src` and `dst` from their rustc representations, to `Tree`-based
+ // representations. If these conversions fail, conclude that the transmutation is
+ // unacceptable; the layouts of both the source and destination types must be
+ // well-defined.
+ let src = Tree::from_ty(src, context).map_err(|err| match err {
+ // Answer `Yes` here, because "Unknown Type" will already be reported by
+ // rustc. No need to spam the user with more errors.
+ Err::Unknown => Answer::Yes,
+ Err::Unspecified => Answer::No(Reason::SrcIsUnspecified),
+ })?;
+
+ let dst = Tree::from_ty(dst, context).map_err(|err| match err {
+ Err::Unknown => Answer::Yes,
+ Err::Unspecified => Answer::No(Reason::DstIsUnspecified),
+ })?;
+
+ Ok((src, dst))
+ });
+
+ match query_or_answer {
+ Ok(query) => query.answer(),
+ Err(answer) => answer,
+ }
+ }
+ }
+}
+
+impl<C> MaybeTransmutableQuery<Tree<<C as QueryContext>::Def, <C as QueryContext>::Ref>, C>
+where
+ C: QueryContext,
+{
+ /// Answers whether a `Tree` is transmutable into another `Tree`.
+ ///
+ /// This method begins by de-def'ing `src` and `dst`, and prunes private paths from `dst`,
+ /// then converts `src` and `dst` to `Nfa`s, and computes an answer using those NFAs.
+ #[inline(always)]
+ #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
+ pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
+ let assume_visibility = self.assume.visibility;
+ let query_or_answer = self.map_layouts(|src, dst, scope, context| {
+ // Remove all `Def` nodes from `src`, without checking their visibility.
+ let src = src.prune(&|def| true);
+
+ tracing::trace!(?src, "pruned src");
+
+ // Remove all `Def` nodes from `dst`, additionally...
+ let dst = if assume_visibility {
+ // ...if visibility is assumed, don't check their visibility.
+ dst.prune(&|def| true)
+ } else {
+ // ...otherwise, prune away all unreachable paths through the `Dst` layout.
+ dst.prune(&|def| context.is_accessible_from(def, scope))
+ };
+
+ tracing::trace!(?dst, "pruned dst");
+
+ // Convert `src` from a tree-based representation to an NFA-based representation.
+ // If the conversion fails because `src` is uninhabited, conclude that the transmutation
+ // is acceptable, because instances of the `src` type do not exist.
+ let src = Nfa::from_tree(src).map_err(|Uninhabited| Answer::Yes)?;
+
+ // Convert `dst` from a tree-based representation to an NFA-based representation.
+ // If the conversion fails because `src` is uninhabited, conclude that the transmutation
+ // is unacceptable, because instances of the `dst` type do not exist.
+ let dst =
+ Nfa::from_tree(dst).map_err(|Uninhabited| Answer::No(Reason::DstIsPrivate))?;
+
+ Ok((src, dst))
+ });
+
+ match query_or_answer {
+ Ok(query) => query.answer(),
+ Err(answer) => answer,
+ }
+ }
+}
+
+impl<C> MaybeTransmutableQuery<Nfa<<C as QueryContext>::Ref>, C>
+where
+ C: QueryContext,
+{
+ /// Answers whether a `Nfa` is transmutable into another `Nfa`.
+ ///
+ /// This method converts `src` and `dst` to DFAs, then computes an answer using those DFAs.
+ #[inline(always)]
+ #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
+ pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
+ let query_or_answer = self
+ .map_layouts(|src, dst, scope, context| Ok((Dfa::from_nfa(src), Dfa::from_nfa(dst))));
+
+ match query_or_answer {
+ Ok(query) => query.answer(),
+ Err(answer) => answer,
+ }
+ }
+}
+
+impl<C> MaybeTransmutableQuery<Dfa<<C as QueryContext>::Ref>, C>
+where
+ C: QueryContext,
+{
+ /// Answers whether a `Nfa` is transmutable into another `Nfa`.
+ ///
+ /// This method converts `src` and `dst` to DFAs, then computes an answer using those DFAs.
+ pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
+ MaybeTransmutableQuery {
+ src: &self.src,
+ dst: &self.dst,
+ scope: self.scope,
+ assume: self.assume,
+ context: self.context,
+ }
+ .answer()
+ }
+}
+
+impl<'l, C> MaybeTransmutableQuery<&'l Dfa<<C as QueryContext>::Ref>, C>
+where
+ C: QueryContext,
+{
+ pub(crate) fn answer(&mut self) -> Answer<<C as QueryContext>::Ref> {
+ self.answer_memo(&mut Map::default(), self.src.start, self.dst.start)
+ }
+
+ #[inline(always)]
+ #[instrument(level = "debug", skip(self))]
+ fn answer_memo(
+ &self,
+ cache: &mut Map<(dfa::State, dfa::State), Answer<<C as QueryContext>::Ref>>,
+ src_state: dfa::State,
+ dst_state: dfa::State,
+ ) -> Answer<<C as QueryContext>::Ref> {
+ if let Some(answer) = cache.get(&(src_state, dst_state)) {
+ answer.clone()
+ } else {
+ let answer = if dst_state == self.dst.accepting {
+ // truncation: `size_of(Src) >= size_of(Dst)`
+ Answer::Yes
+ } else if src_state == self.src.accepting {
+ // extension: `size_of(Src) >= size_of(Dst)`
+ if let Some(dst_state_prime) = self.dst.byte_from(dst_state, Byte::Uninit) {
+ self.answer_memo(cache, src_state, dst_state_prime)
+ } else {
+ Answer::No(Reason::DstIsTooBig)
+ }
+ } else {
+ let src_quantification = if self.assume.validity {
+ // if the compiler may assume that the programmer is doing additional validity checks,
+ // (e.g.: that `src != 3u8` when the destination type is `bool`)
+ // then there must exist at least one transition out of `src_state` such that the transmute is viable...
+ there_exists
+ } else {
+ // if the compiler cannot assume that the programmer is doing additional validity checks,
+ // then for all transitions out of `src_state`, such that the transmute is viable...
+ // then there must exist at least one transition out of `src_state` such that the transmute is viable...
+ for_all
+ };
+
+ src_quantification(
+ self.src.bytes_from(src_state).unwrap_or(&Map::default()),
+ |(&src_validity, &src_state_prime)| {
+ if let Some(dst_state_prime) = self.dst.byte_from(dst_state, src_validity) {
+ self.answer_memo(cache, src_state_prime, dst_state_prime)
+ } else if let Some(dst_state_prime) =
+ self.dst.byte_from(dst_state, Byte::Uninit)
+ {
+ self.answer_memo(cache, src_state_prime, dst_state_prime)
+ } else {
+ Answer::No(Reason::DstIsBitIncompatible)
+ }
+ },
+ )
+ };
+ cache.insert((src_state, dst_state), answer.clone());
+ answer
+ }
+ }
+}
+
+impl<R> Answer<R>
+where
+ R: layout::Ref,
+{
+ pub(crate) fn and(self, rhs: Self) -> Self {
+ match (self, rhs) {
+ (Self::No(reason), _) | (_, Self::No(reason)) => Self::No(reason),
+ (Self::Yes, Self::Yes) => Self::Yes,
+ (Self::IfAll(mut lhs), Self::IfAll(ref mut rhs)) => {
+ lhs.append(rhs);
+ Self::IfAll(lhs)
+ }
+ (constraint, Self::IfAll(mut constraints))
+ | (Self::IfAll(mut constraints), constraint) => {
+ constraints.push(constraint);
+ Self::IfAll(constraints)
+ }
+ (lhs, rhs) => Self::IfAll(vec![lhs, rhs]),
+ }
+ }
+
+ pub(crate) fn or(self, rhs: Self) -> Self {
+ match (self, rhs) {
+ (Self::Yes, _) | (_, Self::Yes) => Self::Yes,
+ (Self::No(lhr), Self::No(rhr)) => Self::No(lhr),
+ (Self::IfAny(mut lhs), Self::IfAny(ref mut rhs)) => {
+ lhs.append(rhs);
+ Self::IfAny(lhs)
+ }
+ (constraint, Self::IfAny(mut constraints))
+ | (Self::IfAny(mut constraints), constraint) => {
+ constraints.push(constraint);
+ Self::IfAny(constraints)
+ }
+ (lhs, rhs) => Self::IfAny(vec![lhs, rhs]),
+ }
+ }
+}
+
+pub fn for_all<R, I, F>(iter: I, f: F) -> Answer<R>
+where
+ R: layout::Ref,
+ I: IntoIterator,
+ F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
+{
+ use std::ops::ControlFlow::{Break, Continue};
+ let (Continue(result) | Break(result)) =
+ iter.into_iter().map(f).try_fold(Answer::Yes, |constraints, constraint| {
+ match constraint.and(constraints) {
+ Answer::No(reason) => Break(Answer::No(reason)),
+ maybe => Continue(maybe),
+ }
+ });
+ result
+}
+
+pub fn there_exists<R, I, F>(iter: I, f: F) -> Answer<R>
+where
+ R: layout::Ref,
+ I: IntoIterator,
+ F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
+{
+ use std::ops::ControlFlow::{Break, Continue};
+ let (Continue(result) | Break(result)) = iter.into_iter().map(f).try_fold(
+ Answer::No(Reason::DstIsBitIncompatible),
+ |constraints, constraint| match constraint.or(constraints) {
+ Answer::Yes => Break(Answer::Yes),
+ maybe => Continue(maybe),
+ },
+ );
+ result
+}
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs b/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs
new file mode 100644
index 000000000..9c2cf4c9a
--- /dev/null
+++ b/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs
@@ -0,0 +1,93 @@
+use crate::layout;
+
+/// Context necessary to answer the question "Are these types transmutable?".
+pub(crate) trait QueryContext {
+ type Def: layout::Def;
+ type Ref: layout::Ref;
+ type Scope: Copy;
+
+ /// Is `def` accessible from the defining module of `scope`?
+ fn is_accessible_from(&self, def: Self::Def, scope: Self::Scope) -> bool;
+
+ fn min_align(&self, reference: Self::Ref) -> usize;
+}
+
+#[cfg(test)]
+pub(crate) mod test {
+ use super::QueryContext;
+
+ pub(crate) struct UltraMinimal;
+
+ #[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)]
+ pub(crate) enum Def {
+ Visible,
+ Invisible,
+ }
+
+ impl crate::layout::Def for Def {}
+
+ impl QueryContext for UltraMinimal {
+ type Def = Def;
+ type Ref = !;
+ type Scope = ();
+
+ fn is_accessible_from(&self, def: Def, scope: ()) -> bool {
+ matches!(Def::Visible, def)
+ }
+
+ fn min_align(&self, reference: !) -> usize {
+ unimplemented!()
+ }
+ }
+}
+
+#[cfg(feature = "rustc")]
+mod rustc {
+ use super::*;
+ use rustc_middle::ty::{Ty, TyCtxt};
+
+ impl<'tcx> super::QueryContext for TyCtxt<'tcx> {
+ type Def = layout::rustc::Def<'tcx>;
+ type Ref = layout::rustc::Ref<'tcx>;
+
+ type Scope = Ty<'tcx>;
+
+ #[instrument(level = "debug", skip(self))]
+ fn is_accessible_from(&self, def: Self::Def, scope: Self::Scope) -> bool {
+ use layout::rustc::Def;
+ use rustc_middle::ty;
+
+ let parent = if let ty::Adt(adt_def, ..) = scope.kind() {
+ use rustc_middle::ty::DefIdTree;
+ let parent = self.parent(adt_def.did());
+ parent
+ } else {
+ // Is this always how we want to handle a non-ADT scope?
+ return false;
+ };
+
+ let def_id = match def {
+ Def::Adt(adt_def) => adt_def.did(),
+ Def::Variant(variant_def) => variant_def.def_id,
+ Def::Field(field_def) => field_def.did,
+ Def::Primitive => {
+ // primitives do not have a def_id, but they're always accessible
+ return true;
+ }
+ };
+
+ let ret = if self.visibility(def_id).is_accessible_from(parent, *self) {
+ true
+ } else {
+ false
+ };
+
+ tracing::trace!(?ret, "ret");
+ ret
+ }
+
+ fn min_align(&self, reference: Self::Ref) -> usize {
+ unimplemented!()
+ }
+ }
+}
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
new file mode 100644
index 000000000..d9d125687
--- /dev/null
+++ b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
@@ -0,0 +1,115 @@
+use super::query_context::test::{Def, UltraMinimal};
+use crate::maybe_transmutable::MaybeTransmutableQuery;
+use crate::{layout, Answer, Reason, Set};
+use itertools::Itertools;
+
+mod bool {
+ use super::*;
+
+ #[test]
+ fn should_permit_identity_transmutation_tree() {
+ println!("{:?}", layout::Tree::<!, !>::bool());
+ let answer = crate::maybe_transmutable::MaybeTransmutableQuery::new(
+ layout::Tree::<Def, !>::bool(),
+ layout::Tree::<Def, !>::bool(),
+ (),
+ crate::Assume { alignment: false, lifetimes: false, validity: true, visibility: false },
+ UltraMinimal,
+ )
+ .answer();
+ assert_eq!(answer, Answer::Yes);
+ }
+
+ #[test]
+ fn should_permit_identity_transmutation_dfa() {
+ let answer = crate::maybe_transmutable::MaybeTransmutableQuery::new(
+ layout::Dfa::<!>::bool(),
+ layout::Dfa::<!>::bool(),
+ (),
+ crate::Assume { alignment: false, lifetimes: false, validity: true, visibility: false },
+ UltraMinimal,
+ )
+ .answer();
+ assert_eq!(answer, Answer::Yes);
+ }
+
+ #[test]
+ fn should_permit_validity_expansion_and_reject_contraction() {
+ let un = layout::Tree::<Def, !>::uninhabited();
+ let b0 = layout::Tree::<Def, !>::from_bits(0);
+ let b1 = layout::Tree::<Def, !>::from_bits(1);
+ let b2 = layout::Tree::<Def, !>::from_bits(2);
+
+ let alts = [b0, b1, b2];
+
+ let into_layout = |alts: Vec<_>| {
+ alts.into_iter().fold(layout::Tree::<Def, !>::uninhabited(), layout::Tree::<Def, !>::or)
+ };
+
+ let into_set = |alts: Vec<_>| {
+ #[cfg(feature = "rustc")]
+ let mut set = Set::default();
+ #[cfg(not(feature = "rustc"))]
+ let mut set = Set::new();
+ set.extend(alts);
+ set
+ };
+
+ for src_alts in alts.clone().into_iter().powerset() {
+ let src_layout = into_layout(src_alts.clone());
+ let src_set = into_set(src_alts.clone());
+
+ for dst_alts in alts.clone().into_iter().powerset().filter(|alts| !alts.is_empty()) {
+ let dst_layout = into_layout(dst_alts.clone());
+ let dst_set = into_set(dst_alts.clone());
+
+ if src_set.is_subset(&dst_set) {
+ assert_eq!(
+ Answer::Yes,
+ MaybeTransmutableQuery::new(
+ src_layout.clone(),
+ dst_layout.clone(),
+ (),
+ crate::Assume { validity: false, ..crate::Assume::default() },
+ UltraMinimal,
+ )
+ .answer(),
+ "{:?} SHOULD be transmutable into {:?}",
+ src_layout,
+ dst_layout
+ );
+ } else if !src_set.is_disjoint(&dst_set) {
+ assert_eq!(
+ Answer::Yes,
+ MaybeTransmutableQuery::new(
+ src_layout.clone(),
+ dst_layout.clone(),
+ (),
+ crate::Assume { validity: true, ..crate::Assume::default() },
+ UltraMinimal,
+ )
+ .answer(),
+ "{:?} SHOULD be transmutable (assuming validity) into {:?}",
+ src_layout,
+ dst_layout
+ );
+ } else {
+ assert_eq!(
+ Answer::No(Reason::DstIsBitIncompatible),
+ MaybeTransmutableQuery::new(
+ src_layout.clone(),
+ dst_layout.clone(),
+ (),
+ crate::Assume { validity: false, ..crate::Assume::default() },
+ UltraMinimal,
+ )
+ .answer(),
+ "{:?} should NOT be transmutable into {:?}",
+ src_layout,
+ dst_layout
+ );
+ }
+ }
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-03 07:39:18 +0000