rustc_transmute/maybe_transmutable/
mod.rs1use 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#[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 #[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 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 #[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 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 let dst = if assume.safety {
98 dst.prune(&|_def| false)
101 } else {
102 dst.prune(&|def| def.has_safety_invariants())
105 };
106
107 trace!(?dst, "pruned dst");
108
109 let src = match Dfa::from_tree(src) {
114 Ok(src) => src,
115 Err(layout::Uninhabited) => return Answer::Yes,
116 };
117
118 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 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 Answer::Yes
191 } else if src_state == self.src.accept {
192 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 Quantifier::ThereExists
204 } else {
205 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 (None, _) => None,
217 (Some(_), None) => Some(Answer::No(Reason::DstIsBitIncompatible)),
219 (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 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 self.src.refs_from(src_state).map(|(src_ref, src_state_prime)| {
247 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 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 (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
293 | (Answer::No(reason), Answer::No(_))
294 | (Answer::No(reason), _) | (_, Answer::No(reason)) => Answer::No(reason),
296 | (Answer::Yes, other) | (other, Answer::Yes) => other,
298 (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 (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 (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 (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
321 | (Answer::No(reason), Answer::No(_)) => Answer::No(reason),
322 (Answer::No(_), other) | (other, Answer::No(_)) => or(other, Answer::Yes),
324 (Answer::Yes, other) | (other, Answer::Yes) => other,
326 (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 (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 (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}