2 use crate::{Answer, Reason};
8 use query_context::QueryContext;
10 use crate::layout::{self, dfa, Byte, Dfa, Nfa, Tree, Uninhabited};
11 pub(crate) struct MaybeTransmutableQuery<L, C>
17 scope: <C as QueryContext>::Scope,
18 assume: crate::Assume,
22 impl<L, C> MaybeTransmutableQuery<L, C>
29 scope: <C as QueryContext>::Scope,
30 assume: crate::Assume,
33 Self { src, dst, scope, assume, context }
36 pub(crate) fn map_layouts<F, M>(
39 ) -> Result<MaybeTransmutableQuery<M, C>, Answer<<C as QueryContext>::Ref>>
44 <C as QueryContext>::Scope,
46 ) -> Result<(M, M), Answer<<C as QueryContext>::Ref>>,
48 let Self { src, dst, scope, assume, context } = self;
50 let (src, dst) = f(src, dst, scope, &context)?;
52 Ok(MaybeTransmutableQuery { src, dst, scope, assume, context })
56 #[cfg(feature = "rustc")]
59 use crate::layout::tree::Err;
61 use rustc_middle::ty::Ty;
62 use rustc_middle::ty::TyCtxt;
64 impl<'tcx> MaybeTransmutableQuery<Ty<'tcx>, TyCtxt<'tcx>> {
65 /// This method begins by converting `src` and `dst` from `Ty`s to `Tree`s,
66 /// then computes an answer using those trees.
67 #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
68 pub fn answer(self) -> Answer<<TyCtxt<'tcx> as QueryContext>::Ref> {
69 let query_or_answer = self.map_layouts(|src, dst, scope, &context| {
70 // Convert `src` and `dst` from their rustc representations, to `Tree`-based
71 // representations. If these conversions fail, conclude that the transmutation is
72 // unacceptable; the layouts of both the source and destination types must be
74 let src = Tree::from_ty(src, context).map_err(|err| match err {
75 // Answer `Yes` here, because "Unknown Type" will already be reported by
76 // rustc. No need to spam the user with more errors.
77 Err::Unknown => Answer::Yes,
78 Err::Unspecified => Answer::No(Reason::SrcIsUnspecified),
81 let dst = Tree::from_ty(dst, context).map_err(|err| match err {
82 Err::Unknown => Answer::Yes,
83 Err::Unspecified => Answer::No(Reason::DstIsUnspecified),
89 match query_or_answer {
90 Ok(query) => query.answer(),
91 Err(answer) => answer,
97 impl<C> MaybeTransmutableQuery<Tree<<C as QueryContext>::Def, <C as QueryContext>::Ref>, C>
101 /// Answers whether a `Tree` is transmutable into another `Tree`.
103 /// This method begins by de-def'ing `src` and `dst`, and prunes private paths from `dst`,
104 /// then converts `src` and `dst` to `Nfa`s, and computes an answer using those NFAs.
106 #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
107 pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
108 let assume_visibility = self.assume.visibility;
109 let query_or_answer = self.map_layouts(|src, dst, scope, context| {
110 // Remove all `Def` nodes from `src`, without checking their visibility.
111 let src = src.prune(&|def| true);
113 trace!(?src, "pruned src");
115 // Remove all `Def` nodes from `dst`, additionally...
116 let dst = if assume_visibility {
117 // ...if visibility is assumed, don't check their visibility.
118 dst.prune(&|def| true)
120 // ...otherwise, prune away all unreachable paths through the `Dst` layout.
121 dst.prune(&|def| context.is_accessible_from(def, scope))
124 trace!(?dst, "pruned dst");
126 // Convert `src` from a tree-based representation to an NFA-based representation.
127 // If the conversion fails because `src` is uninhabited, conclude that the transmutation
128 // is acceptable, because instances of the `src` type do not exist.
129 let src = Nfa::from_tree(src).map_err(|Uninhabited| Answer::Yes)?;
131 // Convert `dst` from a tree-based representation to an NFA-based representation.
132 // If the conversion fails because `src` is uninhabited, conclude that the transmutation
133 // is unacceptable, because instances of the `dst` type do not exist.
135 Nfa::from_tree(dst).map_err(|Uninhabited| Answer::No(Reason::DstIsPrivate))?;
140 match query_or_answer {
141 Ok(query) => query.answer(),
142 Err(answer) => answer,
147 impl<C> MaybeTransmutableQuery<Nfa<<C as QueryContext>::Ref>, C>
151 /// Answers whether a `Nfa` is transmutable into another `Nfa`.
153 /// This method converts `src` and `dst` to DFAs, then computes an answer using those DFAs.
155 #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
156 pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
157 let query_or_answer = self
158 .map_layouts(|src, dst, scope, context| Ok((Dfa::from_nfa(src), Dfa::from_nfa(dst))));
160 match query_or_answer {
161 Ok(query) => query.answer(),
162 Err(answer) => answer,
167 impl<C> MaybeTransmutableQuery<Dfa<<C as QueryContext>::Ref>, C>
171 /// Answers whether a `Nfa` is transmutable into another `Nfa`.
173 /// This method converts `src` and `dst` to DFAs, then computes an answer using those DFAs.
174 pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
175 MaybeTransmutableQuery {
180 context: self.context,
186 impl<'l, C> MaybeTransmutableQuery<&'l Dfa<<C as QueryContext>::Ref>, C>
190 pub(crate) fn answer(&mut self) -> Answer<<C as QueryContext>::Ref> {
191 self.answer_memo(&mut Map::default(), self.src.start, self.dst.start)
195 #[instrument(level = "debug", skip(self))]
198 cache: &mut Map<(dfa::State, dfa::State), Answer<<C as QueryContext>::Ref>>,
199 src_state: dfa::State,
200 dst_state: dfa::State,
201 ) -> Answer<<C as QueryContext>::Ref> {
202 if let Some(answer) = cache.get(&(src_state, dst_state)) {
205 let answer = if dst_state == self.dst.accepting {
206 // truncation: `size_of(Src) >= size_of(Dst)`
208 } else if src_state == self.src.accepting {
209 // extension: `size_of(Src) >= size_of(Dst)`
210 if let Some(dst_state_prime) = self.dst.byte_from(dst_state, Byte::Uninit) {
211 self.answer_memo(cache, src_state, dst_state_prime)
213 Answer::No(Reason::DstIsTooBig)
216 let src_quantification = if self.assume.validity {
217 // if the compiler may assume that the programmer is doing additional validity checks,
218 // (e.g.: that `src != 3u8` when the destination type is `bool`)
219 // then there must exist at least one transition out of `src_state` such that the transmute is viable...
222 // if the compiler cannot assume that the programmer is doing additional validity checks,
223 // then for all transitions out of `src_state`, such that the transmute is viable...
224 // then there must exist at least one transition out of `src_state` such that the transmute is viable...
229 self.src.bytes_from(src_state).unwrap_or(&Map::default()),
230 |(&src_validity, &src_state_prime)| {
231 if let Some(dst_state_prime) = self.dst.byte_from(dst_state, src_validity) {
232 self.answer_memo(cache, src_state_prime, dst_state_prime)
233 } else if let Some(dst_state_prime) =
234 self.dst.byte_from(dst_state, Byte::Uninit)
236 self.answer_memo(cache, src_state_prime, dst_state_prime)
238 Answer::No(Reason::DstIsBitIncompatible)
243 cache.insert((src_state, dst_state), answer.clone());
253 pub(crate) fn and(self, rhs: Self) -> Self {
255 (Self::No(reason), _) | (_, Self::No(reason)) => Self::No(reason),
256 (Self::Yes, Self::Yes) => Self::Yes,
257 (Self::IfAll(mut lhs), Self::IfAll(ref mut rhs)) => {
261 (constraint, Self::IfAll(mut constraints))
262 | (Self::IfAll(mut constraints), constraint) => {
263 constraints.push(constraint);
264 Self::IfAll(constraints)
266 (lhs, rhs) => Self::IfAll(vec![lhs, rhs]),
270 pub(crate) fn or(self, rhs: Self) -> Self {
272 (Self::Yes, _) | (_, Self::Yes) => Self::Yes,
273 (Self::No(lhr), Self::No(rhr)) => Self::No(lhr),
274 (Self::IfAny(mut lhs), Self::IfAny(ref mut rhs)) => {
278 (constraint, Self::IfAny(mut constraints))
279 | (Self::IfAny(mut constraints), constraint) => {
280 constraints.push(constraint);
281 Self::IfAny(constraints)
283 (lhs, rhs) => Self::IfAny(vec![lhs, rhs]),
288 pub fn for_all<R, I, F>(iter: I, f: F) -> Answer<R>
292 F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
294 use std::ops::ControlFlow::{Break, Continue};
295 let (Continue(result) | Break(result)) =
296 iter.into_iter().map(f).try_fold(Answer::Yes, |constraints, constraint| {
297 match constraint.and(constraints) {
298 Answer::No(reason) => Break(Answer::No(reason)),
299 maybe => Continue(maybe),
305 pub fn there_exists<R, I, F>(iter: I, f: F) -> Answer<R>
309 F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
311 use std::ops::ControlFlow::{Break, Continue};
312 let (Continue(result) | Break(result)) = iter.into_iter().map(f).try_fold(
313 Answer::No(Reason::DstIsBitIncompatible),
314 |constraints, constraint| match constraint.or(constraints) {
315 Answer::Yes => Break(Answer::Yes),
316 maybe => Continue(maybe),