rustc_transmute/maybe_transmutable/
mod.rs

1use rustc_data_structures::stack::ensure_sufficient_stack;
2use tracing::{debug, instrument, trace};
3
4pub(crate) mod query_context;
5#[cfg(test)]
6mod tests;
7
8use crate::layout::{self, Def, Dfa, Reference, Tree, dfa, union};
9use crate::maybe_transmutable::query_context::QueryContext;
10use crate::{Answer, Condition, Map, Reason};
11
12pub(crate) struct MaybeTransmutableQuery<L, C>
13where
14    C: QueryContext,
15{
16    src: L,
17    dst: L,
18    assume: crate::Assume,
19    context: C,
20}
21
22impl<L, C> MaybeTransmutableQuery<L, C>
23where
24    C: QueryContext,
25{
26    pub(crate) fn new(src: L, dst: L, assume: crate::Assume, context: C) -> Self {
27        Self { src, dst, assume, context }
28    }
29}
30
31// FIXME: Nix this cfg, so we can write unit tests independently of rustc
32#[cfg(feature = "rustc")]
33mod rustc {
34    use rustc_middle::ty::layout::LayoutCx;
35    use rustc_middle::ty::{Ty, TyCtxt, TypingEnv};
36
37    use super::*;
38    use crate::layout::tree::rustc::Err;
39
40    impl<'tcx> MaybeTransmutableQuery<Ty<'tcx>, TyCtxt<'tcx>> {
41        /// This method begins by converting `src` and `dst` from `Ty`s to `Tree`s,
42        /// then computes an answer using those trees.
43        #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
44        pub(crate) fn answer(
45            self,
46        ) -> Answer<<TyCtxt<'tcx> as QueryContext>::Region, <TyCtxt<'tcx> as QueryContext>::Type>
47        {
48            let Self { src, dst, assume, context } = self;
49
50            let layout_cx = LayoutCx::new(context, TypingEnv::fully_monomorphized());
51
52            // Convert `src` and `dst` from their rustc representations, to `Tree`-based
53            // representations.
54            let src = Tree::from_ty(src, layout_cx);
55            let dst = Tree::from_ty(dst, layout_cx);
56
57            match (src, dst) {
58                (Err(Err::TypeError(_)), _) | (_, Err(Err::TypeError(_))) => {
59                    Answer::No(Reason::TypeError)
60                }
61                (Err(Err::UnknownLayout), _) => Answer::No(Reason::SrcLayoutUnknown),
62                (_, Err(Err::UnknownLayout)) => Answer::No(Reason::DstLayoutUnknown),
63                (Err(Err::NotYetSupported), _) => Answer::No(Reason::SrcIsNotYetSupported),
64                (_, Err(Err::NotYetSupported)) => Answer::No(Reason::DstIsNotYetSupported),
65                (Err(Err::SizeOverflow), _) => Answer::No(Reason::SrcSizeOverflow),
66                (_, Err(Err::SizeOverflow)) => Answer::No(Reason::DstSizeOverflow),
67                (Ok(src), Ok(dst)) => MaybeTransmutableQuery { src, dst, assume, context }.answer(),
68            }
69        }
70    }
71}
72
73impl<C>
74    MaybeTransmutableQuery<
75        Tree<<C as QueryContext>::Def, <C as QueryContext>::Region, <C as QueryContext>::Type>,
76        C,
77    >
78where
79    C: QueryContext,
80{
81    /// Answers whether a `Tree` is transmutable into another `Tree`.
82    ///
83    /// This method begins by de-def'ing `src` and `dst`, and prunes private paths from `dst`,
84    /// then converts `src` and `dst` to `Dfa`s, and computes an answer using those DFAs.
85    #[inline(always)]
86    #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
87    pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Region, <C as QueryContext>::Type> {
88        let Self { src, dst, assume, context } = self;
89
90        // Unconditionally remove all `Def` nodes from `src`, without pruning away the
91        // branches they appear in. This is valid to do for value-to-value
92        // transmutations, but not for `&mut T` to `&mut U`; we will need to be
93        // more sophisticated to handle transmutations between mutable
94        // references.
95        let src = src.prune(&|_def| false);
96
97        if src.is_inhabited() && !dst.is_inhabited() {
98            return Answer::No(Reason::DstUninhabited);
99        }
100
101        trace!(?src, "pruned src");
102
103        // Remove all `Def` nodes from `dst`, additionally...
104        let dst = if assume.safety {
105            // ...if safety is assumed, don't check if they carry safety
106            // invariants; retain all paths.
107            dst.prune(&|_def| false)
108        } else {
109            // ...otherwise, prune away all paths with safety invariants from
110            // the `Dst` layout.
111            dst.prune(&|def| def.has_safety_invariants())
112        };
113
114        trace!(?dst, "pruned dst");
115
116        // Convert `src` from a tree-based representation to an DFA-based
117        // representation. If the conversion fails because `src` is uninhabited,
118        // conclude that the transmutation is acceptable, because instances of
119        // the `src` type do not exist.
120        let src = match Dfa::from_tree(src) {
121            Ok(src) => src,
122            Err(layout::Uninhabited) => return Answer::Yes,
123        };
124
125        // Convert `dst` from a tree-based representation to an DFA-based
126        // representation. If the conversion fails because `src` is uninhabited,
127        // conclude that the transmutation is unacceptable. Valid instances of
128        // the `dst` type do not exist, either because it's genuinely
129        // uninhabited, or because there are no branches of the tree that are
130        // free of safety invariants.
131        let dst = match Dfa::from_tree(dst) {
132            Ok(dst) => dst,
133            Err(layout::Uninhabited) => return Answer::No(Reason::DstMayHaveSafetyInvariants),
134        };
135
136        MaybeTransmutableQuery { src, dst, assume, context }.answer()
137    }
138}
139
140impl<C> MaybeTransmutableQuery<Dfa<<C as QueryContext>::Region, <C as QueryContext>::Type>, C>
141where
142    C: QueryContext,
143{
144    /// Answers whether a `Dfa` is transmutable into another `Dfa`.
145    pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Region, <C as QueryContext>::Type> {
146        self.answer_memo(&mut Map::default(), self.src.start, self.dst.start)
147    }
148
149    #[inline(always)]
150    #[instrument(level = "debug", skip(self))]
151    fn answer_memo(
152        &self,
153        cache: &mut Map<
154            (dfa::State, dfa::State),
155            Answer<<C as QueryContext>::Region, <C as QueryContext>::Type>,
156        >,
157        src_state: dfa::State,
158        dst_state: dfa::State,
159    ) -> Answer<<C as QueryContext>::Region, <C as QueryContext>::Type> {
160        if let Some(answer) = cache.get(&(src_state, dst_state)) {
161            answer.clone()
162        } else {
163            let answer = ensure_sufficient_stack(|| self.answer_impl(cache, src_state, dst_state));
164            if let Some(..) = cache.insert((src_state, dst_state), answer.clone()) {
165                panic!("failed to correctly cache transmutability")
166            }
167            answer
168        }
169    }
170
171    fn answer_impl(
172        &self,
173        cache: &mut Map<
174            (dfa::State, dfa::State),
175            Answer<<C as QueryContext>::Region, <C as QueryContext>::Type>,
176        >,
177        src_state: dfa::State,
178        dst_state: dfa::State,
179    ) -> Answer<<C as QueryContext>::Region, <C as QueryContext>::Type> {
180        debug!(?src_state, ?dst_state);
181        debug!(src = ?self.src);
182        debug!(dst = ?self.dst);
183        debug!(
184            src_transitions_len = self.src.transitions.len(),
185            dst_transitions_len = self.dst.transitions.len()
186        );
187        if dst_state == self.dst.accept {
188            // truncation: `size_of(Src) >= size_of(Dst)`
189            //
190            // Why is truncation OK to do? Because even though the Src is bigger, all we care about
191            // is whether we have enough data for the Dst to be valid in accordance with what its
192            // type dictates.
193            // For example, in a u8 to `()` transmutation, we have enough data available from the u8
194            // to transmute it to a `()` (though in this case does `()` really need any data to
195            // begin with? It doesn't). Same thing with u8 to fieldless struct.
196            // Now then, why is something like u8 to bool not allowed? That is not because the bool
197            // is smaller in size, but rather because those 2 bits that we are re-interpreting from
198            // the u8 could introduce invalid states for the bool type.
199            //
200            // So, if it's possible to transmute to a smaller Dst by truncating, and we can guarantee
201            // that none of the actually-used data can introduce an invalid state for Dst's type, we
202            // are able to safely transmute, even with truncation.
203            Answer::Yes
204        } else if src_state == self.src.accept {
205            // extension: `size_of(Src) <= size_of(Dst)`
206            if let Some(dst_state_prime) = self.dst.get_uninit_edge_dst(dst_state) {
207                self.answer_memo(cache, src_state, dst_state_prime)
208            } else {
209                Answer::No(Reason::DstIsTooBig)
210            }
211        } else {
212            let src_quantifier = if self.assume.validity {
213                // if the compiler may assume that the programmer is doing additional validity checks,
214                // (e.g.: that `src != 3u8` when the destination type is `bool`)
215                // then there must exist at least one transition out of `src_state` such that the transmute is viable...
216                Quantifier::ThereExists
217            } else {
218                // if the compiler cannot assume that the programmer is doing additional validity checks,
219                // then for all transitions out of `src_state`, such that the transmute is viable...
220                // then there must exist at least one transition out of `dst_state` such that the transmute is viable...
221                Quantifier::ForAll
222            };
223
224            let bytes_answer = src_quantifier.apply(
225                union(self.src.bytes_from(src_state), self.dst.bytes_from(dst_state)).filter_map(
226                    |(_range, (src_state_prime, dst_state_prime))| {
227                        match (src_state_prime, dst_state_prime) {
228                            // No matching transitions in `src`. Skip.
229                            (None, _) => None,
230                            // No matching transitions in `dst`. Fail.
231                            (Some(_), None) => Some(Answer::No(Reason::DstIsBitIncompatible)),
232                            // Matching transitions. Continue with successor states.
233                            (Some(src_state_prime), Some(dst_state_prime)) => {
234                                Some(self.answer_memo(cache, src_state_prime, dst_state_prime))
235                            }
236                        }
237                    },
238                ),
239            );
240
241            // The below early returns reflect how this code would behave:
242            //   if self.assume.validity {
243            //       or(bytes_answer, refs_answer)
244            //   } else {
245            //       and(bytes_answer, refs_answer)
246            //   }
247            // ...if `refs_answer` was computed lazily. The below early
248            // returns can be deleted without impacting the correctness of
249            // the algorithm; only its performance.
250            debug!(?bytes_answer);
251            match bytes_answer {
252                Answer::No(_) if !self.assume.validity => return bytes_answer,
253                Answer::Yes if self.assume.validity => return bytes_answer,
254                _ => {}
255            };
256
257            let refs_answer = src_quantifier.apply(
258                // for each reference transition out of `src_state`...
259                self.src.refs_from(src_state).map(|(src_ref, src_state_prime)| {
260                    // ...there exists a reference transition out of `dst_state`...
261                    Quantifier::ThereExists.apply(self.dst.refs_from(dst_state).map(
262                        |(dst_ref, dst_state_prime)| {
263                            if !src_ref.is_mut && dst_ref.is_mut {
264                                Answer::No(Reason::DstIsMoreUnique)
265                            } else if !self.assume.alignment
266                                && src_ref.referent_align < dst_ref.referent_align
267                            {
268                                Answer::No(Reason::DstHasStricterAlignment {
269                                    src_min_align: src_ref.referent_align,
270                                    dst_min_align: dst_ref.referent_align,
271                                })
272                            } else if dst_ref.referent_size > src_ref.referent_size {
273                                Answer::No(Reason::DstRefIsTooBig {
274                                    src: src_ref.referent,
275                                    src_size: src_ref.referent_size,
276                                    dst: dst_ref.referent,
277                                    dst_size: dst_ref.referent_size,
278                                })
279                            } else {
280                                let mut conditions = Vec::with_capacity(4);
281                                let mut is_transmutable =
282                                    |src: Reference<_, _>, dst: Reference<_, _>| {
283                                        conditions.push(Condition::Transmutable {
284                                            src: src.referent,
285                                            dst: dst.referent,
286                                        });
287                                        if !self.assume.lifetimes {
288                                            conditions.push(Condition::Outlives {
289                                                long: src.region,
290                                                short: dst.region,
291                                            });
292                                        }
293                                    };
294
295                                is_transmutable(src_ref, dst_ref);
296
297                                if dst_ref.is_mut {
298                                    is_transmutable(dst_ref, src_ref);
299                                } else {
300                                    conditions.push(Condition::Immutable { ty: dst_ref.referent });
301                                }
302
303                                Answer::If(Condition::IfAll(conditions)).and(self.answer_memo(
304                                    cache,
305                                    src_state_prime,
306                                    dst_state_prime,
307                                ))
308                            }
309                        },
310                    ))
311                }),
312            );
313
314            if self.assume.validity {
315                bytes_answer.or(refs_answer)
316            } else {
317                bytes_answer.and(refs_answer)
318            }
319        }
320    }
321}
322
323impl<R, T> Answer<R, T> {
324    fn and(self, rhs: Answer<R, T>) -> Answer<R, T> {
325        let lhs = self;
326        match (lhs, rhs) {
327            // If both are errors, then we should return the more specific one
328            (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
329            | (Answer::No(reason), Answer::No(_))
330            // If either is an error, return it
331            | (Answer::No(reason), _) | (_, Answer::No(reason)) => Answer::No(reason),
332            // If only one side has a condition, pass it along
333            | (Answer::Yes, other) | (other, Answer::Yes) => other,
334            // If both sides have IfAll conditions, merge them
335            (Answer::If(Condition::IfAll(mut lhs)), Answer::If(Condition::IfAll(ref mut rhs))) => {
336                lhs.append(rhs);
337                Answer::If(Condition::IfAll(lhs))
338            }
339            // If only one side is an IfAll, add the other Condition to it
340            (Answer::If(cond), Answer::If(Condition::IfAll(mut conds)))
341            | (Answer::If(Condition::IfAll(mut conds)), Answer::If(cond)) => {
342                conds.push(cond);
343                Answer::If(Condition::IfAll(conds))
344            }
345            // Otherwise, both lhs and rhs conditions can be combined in a parent IfAll
346            (Answer::If(lhs), Answer::If(rhs)) => Answer::If(Condition::IfAll(vec![lhs, rhs])),
347        }
348    }
349
350    fn or(self, rhs: Answer<R, T>) -> Answer<R, T> {
351        let lhs = self;
352        match (lhs, rhs) {
353            // If both are errors, then we should return the more specific one
354            (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
355            | (Answer::No(reason), Answer::No(_)) => Answer::No(reason),
356            // Otherwise, errors can be ignored for the rest of the pattern matching
357            (Answer::No(_), other) | (other, Answer::No(_)) => other.or(Answer::Yes),
358            // If only one side has a condition, pass it along
359            (Answer::Yes, other) | (other, Answer::Yes) => other,
360            // If both sides have IfAny conditions, merge them
361            (Answer::If(Condition::IfAny(mut lhs)), Answer::If(Condition::IfAny(ref mut rhs))) => {
362                lhs.append(rhs);
363                Answer::If(Condition::IfAny(lhs))
364            }
365            // If only one side is an IfAny, add the other Condition to it
366            (Answer::If(cond), Answer::If(Condition::IfAny(mut conds)))
367            | (Answer::If(Condition::IfAny(mut conds)), Answer::If(cond)) => {
368                conds.push(cond);
369                Answer::If(Condition::IfAny(conds))
370            }
371            // Otherwise, both lhs and rhs conditions can be combined in a parent IfAny
372            (Answer::If(lhs), Answer::If(rhs)) => Answer::If(Condition::IfAny(vec![lhs, rhs])),
373        }
374    }
375}
376
377enum Quantifier {
378    ThereExists,
379    ForAll,
380}
381
382impl Quantifier {
383    fn apply<R, T, I>(&self, iter: I) -> Answer<R, T>
384    where
385        R: layout::Region,
386        T: layout::Type,
387        I: IntoIterator<Item = Answer<R, T>>,
388    {
389        use std::ops::ControlFlow::{Break, Continue};
390
391        let (init, try_fold_f): (_, fn(_, _) -> _) = match self {
392            Self::ThereExists => {
393                (Answer::No(Reason::DstIsBitIncompatible), |accum: Answer<R, T>, next| match accum
394                    .or(next)
395                {
396                    Answer::Yes => Break(Answer::Yes),
397                    maybe => Continue(maybe),
398                })
399            }
400            Self::ForAll => (Answer::Yes, |accum: Answer<R, T>, next| {
401                let answer = accum.and(next);
402                match answer {
403                    Answer::No(_) => Break(answer),
404                    maybe => Continue(maybe),
405                }
406            }),
407        };
408
409        let (Continue(result) | Break(result)) = iter.into_iter().try_fold(init, try_fold_f);
410        result
411    }
412}