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, 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#[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(
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 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 #[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 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 let dst = if assume.safety {
105 dst.prune(&|_def| false)
108 } else {
109 dst.prune(&|def| def.has_safety_invariants())
112 };
113
114 trace!(?dst, "pruned dst");
115
116 let src = match Dfa::from_tree(src) {
121 Ok(src) => src,
122 Err(layout::Uninhabited) => return Answer::Yes,
123 };
124
125 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 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 Answer::Yes
204 } else if src_state == self.src.accept {
205 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 Quantifier::ThereExists
217 } else {
218 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 (None, _) => None,
230 (Some(_), None) => Some(Answer::No(Reason::DstIsBitIncompatible)),
232 (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 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 self.src.refs_from(src_state).map(|(src_ref, src_state_prime)| {
260 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 (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
329 | (Answer::No(reason), Answer::No(_))
330 | (Answer::No(reason), _) | (_, Answer::No(reason)) => Answer::No(reason),
332 | (Answer::Yes, other) | (other, Answer::Yes) => other,
334 (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 (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 (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 (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
355 | (Answer::No(reason), Answer::No(_)) => Answer::No(reason),
356 (Answer::No(_), other) | (other, Answer::No(_)) => other.or(Answer::Yes),
358 (Answer::Yes, other) | (other, Answer::Yes) => other,
360 (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 (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 (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}