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