diff options
Diffstat (limited to 'compiler/rustc_transmute/src/maybe_transmutable/mod.rs')
-rw-r--r-- | compiler/rustc_transmute/src/maybe_transmutable/mod.rs | 330 |
1 files changed, 222 insertions, 108 deletions
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs index 2e2fb90e7..b223a90f7 100644 --- a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs +++ b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs @@ -1,13 +1,13 @@ -use crate::Map; -use crate::{Answer, Reason}; - +pub(crate) mod query_context; #[cfg(test)] mod tests; -mod query_context; -use query_context::QueryContext; +use crate::{ + layout::{self, dfa, Byte, Dfa, Nfa, Ref, Tree, Uninhabited}, + maybe_transmutable::query_context::QueryContext, + Answer, Condition, Map, Reason, +}; -use crate::layout::{self, dfa, Byte, Dfa, Nfa, Tree, Uninhabited}; pub(crate) struct MaybeTransmutableQuery<L, C> where C: QueryContext, @@ -33,6 +33,7 @@ where Self { src, dst, scope, assume, context } } + // FIXME(bryangarza): Delete this when all usages are removed pub(crate) fn map_layouts<F, M>( self, f: F, @@ -53,6 +54,7 @@ where } } +// FIXME: Nix this cfg, so we can write unit tests independently of rustc #[cfg(feature = "rustc")] mod rustc { use super::*; @@ -66,30 +68,26 @@ mod rustc { /// 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); - let dst = Tree::from_ty(dst, context); - - match (src, dst) { - // Answer `Yes` here, because 'unknown layout' and type errors will already - // be reported by rustc. No need to spam the user with more errors. - (Err(Err::TypeError(_)), _) => Err(Answer::Yes), - (_, Err(Err::TypeError(_))) => Err(Answer::Yes), - (Err(Err::Unknown), _) => Err(Answer::Yes), - (_, Err(Err::Unknown)) => Err(Answer::Yes), - (Err(Err::Unspecified), _) => Err(Answer::No(Reason::SrcIsUnspecified)), - (_, Err(Err::Unspecified)) => Err(Answer::No(Reason::DstIsUnspecified)), - (Ok(src), Ok(dst)) => Ok((src, dst)), - } - }); + let Self { src, dst, scope, assume, context } = self; + + // 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); + let dst = Tree::from_ty(dst, context); - match query_or_answer { - Ok(query) => query.answer(), - Err(answer) => answer, + match (src, dst) { + (Err(Err::TypeError(_)), _) | (_, Err(Err::TypeError(_))) => { + Answer::No(Reason::TypeError) + } + (Err(Err::UnknownLayout), _) => Answer::No(Reason::SrcLayoutUnknown), + (_, Err(Err::UnknownLayout)) => Answer::No(Reason::DstLayoutUnknown), + (Err(Err::Unspecified), _) => Answer::No(Reason::SrcIsUnspecified), + (_, Err(Err::Unspecified)) => Answer::No(Reason::DstIsUnspecified), + (Ok(src), Ok(dst)) => { + MaybeTransmutableQuery { src, dst, scope, assume, context }.answer() + } } } } @@ -107,6 +105,7 @@ where #[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.safety; + // FIXME(bryangarza): Refactor this code to get rid of `map_layouts` 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); @@ -155,6 +154,7 @@ where #[inline(always)] #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))] pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> { + // FIXME(bryangarza): Refactor this code to get rid of `map_layouts` let query_or_answer = self .map_layouts(|src, dst, scope, context| Ok((Dfa::from_nfa(src), Dfa::from_nfa(dst)))); @@ -203,8 +203,29 @@ where if let Some(answer) = cache.get(&(src_state, dst_state)) { answer.clone() } else { + debug!(?src_state, ?dst_state); + debug!(src = ?self.src); + debug!(dst = ?self.dst); + debug!( + src_transitions_len = self.src.transitions.len(), + dst_transitions_len = self.dst.transitions.len() + ); let answer = if dst_state == self.dst.accepting { // truncation: `size_of(Src) >= size_of(Dst)` + // + // Why is truncation OK to do? Because even though the Src is bigger, all we care about + // is whether we have enough data for the Dst to be valid in accordance with what its + // type dictates. + // For example, in a u8 to `()` transmutation, we have enough data available from the u8 + // to transmute it to a `()` (though in this case does `()` really need any data to + // begin with? It doesn't). Same thing with u8 to fieldless struct. + // Now then, why is something like u8 to bool not allowed? That is not because the bool + // is smaller in size, but rather because those 2 bits that we are re-interpreting from + // the u8 could introduce invalid states for the bool type. + // + // So, if it's possible to transmute to a smaller Dst by truncating, and we can guarantee + // that none of the actually-used data can introduce an invalid state for Dst's type, we + // are able to safely transmute, even with truncation. Answer::Yes } else if src_state == self.src.accepting { // extension: `size_of(Src) >= size_of(Dst)` @@ -214,108 +235,201 @@ where Answer::No(Reason::DstIsTooBig) } } else { - let src_quantification = if self.assume.validity { + let src_quantifier = 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 + Quantifier::ThereExists } 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 + // then there must exist at least one transition out of `dst_state` such that the transmute is viable... + Quantifier::ForAll + }; + + let bytes_answer = src_quantifier.apply( + // for each of the byte transitions out of the `src_state`... + self.src.bytes_from(src_state).unwrap_or(&Map::default()).into_iter().map( + |(&src_validity, &src_state_prime)| { + // ...try to find a matching transition out of `dst_state`. + 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) = + // otherwise, see if `dst_state` has any outgoing `Uninit` transitions + // (any init byte is a valid uninit byte) + self.dst.byte_from(dst_state, Byte::Uninit) + { + self.answer_memo(cache, src_state_prime, dst_state_prime) + } else { + // otherwise, we've exhausted our options. + // the DFAs, from this point onwards, are bit-incompatible. + Answer::No(Reason::DstIsBitIncompatible) + } + }, + ), + ); + + // The below early returns reflect how this code would behave: + // if self.assume.validity { + // or(bytes_answer, refs_answer) + // } else { + // and(bytes_answer, refs_answer) + // } + // ...if `refs_answer` was computed lazily. The below early + // returns can be deleted without impacting the correctness of + // the algoritm; only its performance. + debug!(?bytes_answer); + match bytes_answer { + Answer::No(_) if !self.assume.validity => return bytes_answer, + Answer::Yes if self.assume.validity => return bytes_answer, + _ => {} }; - 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) - } - }, - ) + let refs_answer = src_quantifier.apply( + // for each reference transition out of `src_state`... + self.src.refs_from(src_state).unwrap_or(&Map::default()).into_iter().map( + |(&src_ref, &src_state_prime)| { + // ...there exists a reference transition out of `dst_state`... + Quantifier::ThereExists.apply( + self.dst + .refs_from(dst_state) + .unwrap_or(&Map::default()) + .into_iter() + .map(|(&dst_ref, &dst_state_prime)| { + if !src_ref.is_mutable() && dst_ref.is_mutable() { + Answer::No(Reason::DstIsMoreUnique) + } else if !self.assume.alignment + && src_ref.min_align() < dst_ref.min_align() + { + Answer::No(Reason::DstHasStricterAlignment { + src_min_align: src_ref.min_align(), + dst_min_align: dst_ref.min_align(), + }) + } else { + // ...such that `src` is transmutable into `dst`, if + // `src_ref` is transmutability into `dst_ref`. + and( + Answer::If(Condition::IfTransmutable { + src: src_ref, + dst: dst_ref, + }), + self.answer_memo( + cache, + src_state_prime, + dst_state_prime, + ), + ) + } + }), + ) + }, + ), + ); + + if self.assume.validity { + or(bytes_answer, refs_answer) + } else { + and(bytes_answer, refs_answer) + } }; - cache.insert((src_state, dst_state), answer.clone()); + if let Some(..) = cache.insert((src_state, dst_state), answer.clone()) { + panic!("failed to correctly cache transmutability") + } answer } } } -impl<R> Answer<R> +fn and<R>(lhs: Answer<R>, rhs: Answer<R>) -> Answer<R> where - R: layout::Ref, + R: PartialEq, { - 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]), + match (lhs, rhs) { + // If both are errors, then we should return the more specific one + (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason)) + | (Answer::No(reason), Answer::No(_)) + // If either is an error, return it + | (Answer::No(reason), _) | (_, Answer::No(reason)) => Answer::No(reason), + // If only one side has a condition, pass it along + | (Answer::Yes, other) | (other, Answer::Yes) => other, + // If both sides have IfAll conditions, merge them + (Answer::If(Condition::IfAll(mut lhs)), Answer::If(Condition::IfAll(ref mut rhs))) => { + lhs.append(rhs); + Answer::If(Condition::IfAll(lhs)) } - } - - 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]), + // If only one side is an IfAll, add the other Condition to it + (Answer::If(cond), Answer::If(Condition::IfAll(mut conds))) + | (Answer::If(Condition::IfAll(mut conds)), Answer::If(cond)) => { + conds.push(cond); + Answer::If(Condition::IfAll(conds)) } + // Otherwise, both lhs and rhs conditions can be combined in a parent IfAll + (Answer::If(lhs), Answer::If(rhs)) => Answer::If(Condition::IfAll(vec![lhs, rhs])), } } -pub fn for_all<R, I, F>(iter: I, f: F) -> Answer<R> +fn or<R>(lhs: Answer<R>, rhs: Answer<R>) -> Answer<R> where - R: layout::Ref, - I: IntoIterator, - F: FnMut(<I as IntoIterator>::Item) -> Answer<R>, + R: PartialEq, { - 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 + match (lhs, rhs) { + // If both are errors, then we should return the more specific one + (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason)) + | (Answer::No(reason), Answer::No(_)) => Answer::No(reason), + // Otherwise, errors can be ignored for the rest of the pattern matching + (Answer::No(_), other) | (other, Answer::No(_)) => or(other, Answer::Yes), + // If only one side has a condition, pass it along + (Answer::Yes, other) | (other, Answer::Yes) => other, + // If both sides have IfAny conditions, merge them + (Answer::If(Condition::IfAny(mut lhs)), Answer::If(Condition::IfAny(ref mut rhs))) => { + lhs.append(rhs); + Answer::If(Condition::IfAny(lhs)) + } + // If only one side is an IfAny, add the other Condition to it + (Answer::If(cond), Answer::If(Condition::IfAny(mut conds))) + | (Answer::If(Condition::IfAny(mut conds)), Answer::If(cond)) => { + conds.push(cond); + Answer::If(Condition::IfAny(conds)) + } + // Otherwise, both lhs and rhs conditions can be combined in a parent IfAny + (Answer::If(lhs), Answer::If(rhs)) => Answer::If(Condition::IfAny(vec![lhs, rhs])), + } } -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 +pub enum Quantifier { + ThereExists, + ForAll, +} + +impl Quantifier { + pub fn apply<R, I>(&self, iter: I) -> Answer<R> + where + R: layout::Ref, + I: IntoIterator<Item = Answer<R>>, + { + use std::ops::ControlFlow::{Break, Continue}; + + let (init, try_fold_f): (_, fn(_, _) -> _) = match self { + Self::ThereExists => { + (Answer::No(Reason::DstIsBitIncompatible), |accum: Answer<R>, next| { + match or(accum, next) { + Answer::Yes => Break(Answer::Yes), + maybe => Continue(maybe), + } + }) + } + Self::ForAll => (Answer::Yes, |accum: Answer<R>, next| { + let answer = and(accum, next); + match answer { + Answer::No(_) => Break(answer), + maybe => Continue(maybe), + } + }), + }; + + let (Continue(result) | Break(result)) = iter.into_iter().try_fold(init, try_fold_f); + result + } } |