]>
Commit | Line | Data |
---|---|---|
064997fb FG |
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.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); | |
112 | ||
113 | tracing::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 | tracing::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 | } |