compiler/rustc_transmute/src/maybe_transmutable/mod.rs

   1 use crate::Map;
   2 use crate::{Answer, Reason};
   3
   4 #[cfg(test)]
   5 mod tests;
   6
   7 mod query_context;
   8 use query_context::QueryContext;
   9
  10 use crate::layout::{self, dfa, Byte, Dfa, Nfa, Tree, Uninhabited};
  11 pub(crate) struct MaybeTransmutableQuery<L, C>
  12 where
  13     C: QueryContext,
  14 {
  15     src: L,
  16     dst: L,
  17     scope: <C as QueryContext>::Scope,
  18     assume: crate::Assume,
  19     context: C,
  20 }
  21
  22 impl<L, C> MaybeTransmutableQuery<L, C>
  23 where
  24     C: QueryContext,
  25 {
  26     pub(crate) fn new(
  27         src: L,
  28         dst: L,
  29         scope: <C as QueryContext>::Scope,
  30         assume: crate::Assume,
  31         context: C,
  32     ) -> Self {
  33         Self { src, dst, scope, assume, context }
  34     }
  35
  36     pub(crate) fn map_layouts<F, M>(
  37         self,
  38         f: F,
  39     ) -> Result<MaybeTransmutableQuery<M, C>, Answer<<C as QueryContext>::Ref>>
  40     where
  41         F: FnOnce(
  42             L,
  43             L,
  44             <C as QueryContext>::Scope,
  45             &C,
  46         ) -> Result<(M, M), Answer<<C as QueryContext>::Ref>>,
  47     {
  48         let Self { src, dst, scope, assume, context } = self;
  49
  50         let (src, dst) = f(src, dst, scope, &context)?;
  51
  52         Ok(MaybeTransmutableQuery { src, dst, scope, assume, context })
  53     }
  54 }
  55
  56 #[cfg(feature = "rustc")]
  57 mod rustc {
  58     use super::*;
  59     use crate::layout::tree::Err;
  60
  61     use rustc_middle::ty::Ty;
  62     use rustc_middle::ty::TyCtxt;
  63
  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
  73                 // well-defined.
  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),
  79                 })?;
  80
  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),
  84                 })?;
  85
  86                 Ok((src, dst))
  87             });
  88
  89             match query_or_answer {
  90                 Ok(query) => query.answer(),
  91                 Err(answer) => answer,
  92             }
  93         }
  94     }
  95 }
  96
  97 impl<C> MaybeTransmutableQuery<Tree<<C as QueryContext>::Def, <C as QueryContext>::Ref>, C>
  98 where
  99     C: QueryContext,
 100 {
 101     /// Answers whether a `Tree` is transmutable into another `Tree`.
 102     ///
 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.
 105     #[inline(always)]
 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.safety;
 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);
 112
 113             trace!(?src, "pruned src");
 114
 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)
 119             } else {
 120                 // ...otherwise, prune away all unreachable paths through the `Dst` layout.
 121                 dst.prune(&|def| context.is_accessible_from(def, scope))
 122             };
 123
 124             trace!(?dst, "pruned dst");
 125
 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)?;
 130
 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.
 134             let dst =
 135                 Nfa::from_tree(dst).map_err(|Uninhabited| Answer::No(Reason::DstIsPrivate))?;
 136
 137             Ok((src, dst))
 138         });
 139
 140         match query_or_answer {
 141             Ok(query) => query.answer(),
 142             Err(answer) => answer,
 143         }
 144     }
 145 }
 146
 147 impl<C> MaybeTransmutableQuery<Nfa<<C as QueryContext>::Ref>, C>
 148 where
 149     C: QueryContext,
 150 {
 151     /// Answers whether a `Nfa` is transmutable into another `Nfa`.
 152     ///
 153     /// This method converts `src` and `dst` to DFAs, then computes an answer using those DFAs.
 154     #[inline(always)]
 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))));
 159
 160         match query_or_answer {
 161             Ok(query) => query.answer(),
 162             Err(answer) => answer,
 163         }
 164     }
 165 }
 166
 167 impl<C> MaybeTransmutableQuery<Dfa<<C as QueryContext>::Ref>, C>
 168 where
 169     C: QueryContext,
 170 {
 171     /// Answers whether a `Nfa` is transmutable into another `Nfa`.
 172     ///
 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 {
 176             src: &self.src,
 177             dst: &self.dst,
 178             scope: self.scope,
 179             assume: self.assume,
 180             context: self.context,
 181         }
 182         .answer()
 183     }
 184 }
 185
 186 impl<'l, C> MaybeTransmutableQuery<&'l Dfa<<C as QueryContext>::Ref>, C>
 187 where
 188     C: QueryContext,
 189 {
 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)
 192     }
 193
 194     #[inline(always)]
 195     #[instrument(level = "debug", skip(self))]
 196     fn answer_memo(
 197         &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)) {
 203             answer.clone()
 204         } else {
 205             let answer = if dst_state == self.dst.accepting {
 206                 // truncation: `size_of(Src) >= size_of(Dst)`
 207                 Answer::Yes
 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)
 212                 } else {
 213                     Answer::No(Reason::DstIsTooBig)
 214                 }
 215             } else {
 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...
 220                     there_exists
 221                 } else {
 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...
 225                     for_all
 226                 };
 227
 228                 src_quantification(
 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)
 235                         {
 236                             self.answer_memo(cache, src_state_prime, dst_state_prime)
 237                         } else {
 238                             Answer::No(Reason::DstIsBitIncompatible)
 239                         }
 240                     },
 241                 )
 242             };
 243             cache.insert((src_state, dst_state), answer.clone());
 244             answer
 245         }
 246     }
 247 }
 248
 249 impl<R> Answer<R>
 250 where
 251     R: layout::Ref,
 252 {
 253     pub(crate) fn and(self, rhs: Self) -> Self {
 254         match (self, rhs) {
 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)) => {
 258                 lhs.append(rhs);
 259                 Self::IfAll(lhs)
 260             }
 261             (constraint, Self::IfAll(mut constraints))
 262             | (Self::IfAll(mut constraints), constraint) => {
 263                 constraints.push(constraint);
 264                 Self::IfAll(constraints)
 265             }
 266             (lhs, rhs) => Self::IfAll(vec![lhs, rhs]),
 267         }
 268     }
 269
 270     pub(crate) fn or(self, rhs: Self) -> Self {
 271         match (self, rhs) {
 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)) => {
 275                 lhs.append(rhs);
 276                 Self::IfAny(lhs)
 277             }
 278             (constraint, Self::IfAny(mut constraints))
 279             | (Self::IfAny(mut constraints), constraint) => {
 280                 constraints.push(constraint);
 281                 Self::IfAny(constraints)
 282             }
 283             (lhs, rhs) => Self::IfAny(vec![lhs, rhs]),
 284         }
 285     }
 286 }
 287
 288 pub fn for_all<R, I, F>(iter: I, f: F) -> Answer<R>
 289 where
 290     R: layout::Ref,
 291     I: IntoIterator,
 292     F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
 293 {
 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),
 300             }
 301         });
 302     result
 303 }
 304
 305 pub fn there_exists<R, I, F>(iter: I, f: F) -> Answer<R>
 306 where
 307     R: layout::Ref,
 308     I: IntoIterator,
 309     F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
 310 {
 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),
 317         },
 318     );
 319     result
 320 }