From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_transmute/src/layout/dfa.rs | 184 ++++++++ compiler/rustc_transmute/src/layout/mod.rs | 71 ++++ compiler/rustc_transmute/src/layout/nfa.rs | 179 ++++++++ compiler/rustc_transmute/src/layout/tree.rs | 471 +++++++++++++++++++++ compiler/rustc_transmute/src/layout/tree/tests.rs | 80 ++++ compiler/rustc_transmute/src/lib.rs | 117 +++++ .../rustc_transmute/src/maybe_transmutable/mod.rs | 320 ++++++++++++++ .../src/maybe_transmutable/query_context.rs | 93 ++++ .../src/maybe_transmutable/tests.rs | 115 +++++ 9 files changed, 1630 insertions(+) create mode 100644 compiler/rustc_transmute/src/layout/dfa.rs create mode 100644 compiler/rustc_transmute/src/layout/mod.rs create mode 100644 compiler/rustc_transmute/src/layout/nfa.rs create mode 100644 compiler/rustc_transmute/src/layout/tree.rs create mode 100644 compiler/rustc_transmute/src/layout/tree/tests.rs create mode 100644 compiler/rustc_transmute/src/lib.rs create mode 100644 compiler/rustc_transmute/src/maybe_transmutable/mod.rs create mode 100644 compiler/rustc_transmute/src/maybe_transmutable/query_context.rs create mode 100644 compiler/rustc_transmute/src/maybe_transmutable/tests.rs (limited to 'compiler/rustc_transmute/src') 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 +where + R: Ref, +{ + pub(crate) transitions: Map>, + pub(crate) start: State, + pub(crate) accepting: State, +} + +#[derive(PartialEq, Clone, Debug)] +pub(crate) struct Transitions +where + R: Ref, +{ + byte_transitions: Map, + ref_transitions: Map, +} + +impl Default for Transitions +where + R: Ref, +{ + fn default() -> Self { + Self { byte_transitions: Map::default(), ref_transitions: Map::default() } + } +} + +impl Transitions +where + R: Ref, +{ + fn insert(&mut self, transition: Transition, 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 +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 fmt::Debug for Transition +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 Dfa +where + R: Ref, +{ + pub(crate) fn unit() -> Self { + let transitions: Map> = Map::default(); + let start = State::new(); + let accepting = start; + + Self { transitions, start, accepting } + } + + #[cfg(test)] + pub(crate) fn bool() -> Self { + let mut transitions: Map> = 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) -> Self { + let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa; + + let mut dfa_transitions: Map> = Map::default(); + let mut nfa_to_dfa: Map = 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> { + Some(&self.transitions.get(&start)?.byte_transitions) + } + + pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option { + self.transitions.get(&start)?.byte_transitions.get(&byte).copied() + } + + pub(crate) fn refs_from(&self, start: State) -> Option<&Map> { + 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 From> for Transition +where + R: Ref, +{ + fn from(nfa_transition: nfa::Transition) -> 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 +where + R: Ref, +{ + pub(crate) transitions: Map, Set>>, + 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 +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 fmt::Debug for Transition +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 Nfa +where + R: Ref, +{ + pub(crate) fn unit() -> Self { + let transitions: Map, Set>> = 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, Set>> = 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, Set>> = 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) -> Result { + 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, Set>> = 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, Set>> = 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, Set>> { + 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 +where + D: Def, + R: Ref, +{ + /// A sequence of successive layouts. + Seq(Vec), + /// A choice between alternative layouts. + Alt(Vec), + /// A definition node. + Def(D), + /// A reference node. + Ref(R), + /// A byte node. + Byte(Byte), +} + +impl Tree +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(self, f: &F) -> Tree + 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 Tree +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> 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> { + 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, Ref<'tcx>> { + pub fn from_ty(ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Result { + 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>, + variant_def: &'tcx VariantDef, + tcx: TyCtxt<'tcx>, + ) -> Result { + 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> { + 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 = 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 = + 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 = 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 = 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 = + 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 = 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 = 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 = + 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 +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>), + + /// `Src` is transmutable into `Dst` if any of the enclosed requirements are met. + IfAny(Vec>), +} + +/// 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> { + 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 +where + C: QueryContext, +{ + src: L, + dst: L, + scope: ::Scope, + assume: crate::Assume, + context: C, +} + +impl MaybeTransmutableQuery +where + C: QueryContext, +{ + pub(crate) fn new( + src: L, + dst: L, + scope: ::Scope, + assume: crate::Assume, + context: C, + ) -> Self { + Self { src, dst, scope, assume, context } + } + + pub(crate) fn map_layouts( + self, + f: F, + ) -> Result, Answer<::Ref>> + where + F: FnOnce( + L, + L, + ::Scope, + &C, + ) -> Result<(M, M), Answer<::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, 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< 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 MaybeTransmutableQuery::Def, ::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<::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 MaybeTransmutableQuery::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<::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 MaybeTransmutableQuery::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<::Ref> { + MaybeTransmutableQuery { + src: &self.src, + dst: &self.dst, + scope: self.scope, + assume: self.assume, + context: self.context, + } + .answer() + } +} + +impl<'l, C> MaybeTransmutableQuery<&'l Dfa<::Ref>, C> +where + C: QueryContext, +{ + pub(crate) fn answer(&mut self) -> Answer<::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<::Ref>>, + src_state: dfa::State, + dst_state: dfa::State, + ) -> Answer<::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 Answer +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(iter: I, f: F) -> Answer +where + R: layout::Ref, + I: IntoIterator, + F: FnMut(::Item) -> Answer, +{ + 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(iter: I, f: F) -> Answer +where + R: layout::Ref, + I: IntoIterator, + F: FnMut(::Item) -> Answer, +{ + 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::::bool(), + layout::Tree::::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::::uninhabited(); + let b0 = layout::Tree::::from_bits(0); + let b1 = layout::Tree::::from_bits(1); + let b2 = layout::Tree::::from_bits(2); + + let alts = [b0, b1, b2]; + + let into_layout = |alts: Vec<_>| { + alts.into_iter().fold(layout::Tree::::uninhabited(), layout::Tree::::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 + ); + } + } + } + } +} -- cgit v1.2.3