Merging upstream version 1.72.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

2 files changed, 225 insertions, 109 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
+    }
 }
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
index a8675f4ae..e49bebf57 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
@@ -1,9 +1,11 @@
 use super::query_context::test::{Def, UltraMinimal};
 use crate::maybe_transmutable::MaybeTransmutableQuery;
-use crate::{layout, Answer, Reason};
+use crate::{layout, Reason};
 use itertools::Itertools;
 
 mod bool {
+    use crate::Answer;
+
     use super::*;
 
     #[test]