]>
Commit | Line | Data |
---|---|---|
94222f64 | 1 | use crate::check::FnCtxt; |
c295e0f8 XL |
2 | use rustc_data_structures::{ |
3 | fx::FxHashMap, | |
4 | graph::WithSuccessors, | |
5 | graph::{iterate::DepthFirstSearch, vec_graph::VecGraph}, | |
6 | stable_set::FxHashSet, | |
7 | }; | |
94222f64 XL |
8 | use rustc_middle::ty::{self, Ty}; |
9 | ||
10 | impl<'tcx> FnCtxt<'_, 'tcx> { | |
11 | /// Performs type inference fallback, returning true if any fallback | |
12 | /// occurs. | |
13 | pub(super) fn type_inference_fallback(&self) -> bool { | |
c295e0f8 XL |
14 | debug!( |
15 | "type-inference-fallback start obligations: {:#?}", | |
16 | self.fulfillment_cx.borrow_mut().pending_obligations() | |
17 | ); | |
18 | ||
94222f64 XL |
19 | // All type checking constraints were added, try to fallback unsolved variables. |
20 | self.select_obligations_where_possible(false, |_| {}); | |
94222f64 | 21 | |
c295e0f8 XL |
22 | debug!( |
23 | "type-inference-fallback post selection obligations: {:#?}", | |
24 | self.fulfillment_cx.borrow_mut().pending_obligations() | |
25 | ); | |
26 | ||
ee023bcb | 27 | // Check if we have any unsolved variables. If not, no need for fallback. |
c295e0f8 XL |
28 | let unsolved_variables = self.unsolved_variables(); |
29 | if unsolved_variables.is_empty() { | |
30 | return false; | |
31 | } | |
32 | ||
33 | let diverging_fallback = self.calculate_diverging_fallback(&unsolved_variables); | |
34 | ||
35 | let mut fallback_has_occurred = false; | |
94222f64 XL |
36 | // We do fallback in two passes, to try to generate |
37 | // better error messages. | |
38 | // The first time, we do *not* replace opaque types. | |
c295e0f8 | 39 | for ty in unsolved_variables { |
94222f64 | 40 | debug!("unsolved_variable = {:?}", ty); |
c295e0f8 | 41 | fallback_has_occurred |= self.fallback_if_possible(ty, &diverging_fallback); |
94222f64 XL |
42 | } |
43 | ||
c295e0f8 XL |
44 | // We now see if we can make progress. This might cause us to |
45 | // unify inference variables for opaque types, since we may | |
46 | // have unified some other type variables during the first | |
47 | // phase of fallback. This means that we only replace | |
48 | // inference variables with their underlying opaque types as a | |
49 | // last resort. | |
94222f64 XL |
50 | // |
51 | // In code like this: | |
52 | // | |
53 | // ```rust | |
54 | // type MyType = impl Copy; | |
55 | // fn produce() -> MyType { true } | |
56 | // fn bad_produce() -> MyType { panic!() } | |
57 | // ``` | |
58 | // | |
59 | // we want to unify the opaque inference variable in `bad_produce` | |
60 | // with the diverging fallback for `panic!` (e.g. `()` or `!`). | |
61 | // This will produce a nice error message about conflicting concrete | |
62 | // types for `MyType`. | |
63 | // | |
64 | // If we had tried to fallback the opaque inference variable to `MyType`, | |
65 | // we will generate a confusing type-check error that does not explicitly | |
66 | // refer to opaque types. | |
67 | self.select_obligations_where_possible(fallback_has_occurred, |_| {}); | |
68 | ||
94222f64 XL |
69 | fallback_has_occurred |
70 | } | |
71 | ||
72 | // Tries to apply a fallback to `ty` if it is an unsolved variable. | |
73 | // | |
74 | // - Unconstrained ints are replaced with `i32`. | |
75 | // | |
76 | // - Unconstrained floats are replaced with with `f64`. | |
77 | // | |
c295e0f8 XL |
78 | // - Non-numerics may get replaced with `()` or `!`, depending on |
79 | // how they were categorized by `calculate_diverging_fallback` | |
80 | // (and the setting of `#![feature(never_type_fallback)]`). | |
81 | // | |
82 | // Fallback becomes very dubious if we have encountered | |
83 | // type-checking errors. In that case, fallback to Error. | |
94222f64 | 84 | // |
94222f64 | 85 | // The return value indicates whether fallback has occurred. |
c295e0f8 XL |
86 | fn fallback_if_possible( |
87 | &self, | |
88 | ty: Ty<'tcx>, | |
89 | diverging_fallback: &FxHashMap<Ty<'tcx>, Ty<'tcx>>, | |
90 | ) -> bool { | |
94222f64 | 91 | // Careful: we do NOT shallow-resolve `ty`. We know that `ty` |
c295e0f8 XL |
92 | // is an unsolved variable, and we determine its fallback |
93 | // based solely on how it was created, not what other type | |
94 | // variables it may have been unified with since then. | |
94222f64 | 95 | // |
c295e0f8 XL |
96 | // The reason this matters is that other attempts at fallback |
97 | // may (in principle) conflict with this fallback, and we wish | |
98 | // to generate a type error in that case. (However, this | |
99 | // actually isn't true right now, because we're only using the | |
100 | // builtin fallback rules. This would be true if we were using | |
101 | // user-supplied fallbacks. But it's still useful to write the | |
102 | // code to detect bugs.) | |
94222f64 | 103 | // |
c295e0f8 XL |
104 | // (Note though that if we have a general type variable `?T` |
105 | // that is then unified with an integer type variable `?I` | |
106 | // that ultimately never gets resolved to a special integral | |
107 | // type, `?T` is not considered unsolved, but `?I` is. The | |
108 | // same is true for float variables.) | |
94222f64 XL |
109 | let fallback = match ty.kind() { |
110 | _ if self.is_tainted_by_errors() => self.tcx.ty_error(), | |
111 | ty::Infer(ty::IntVar(_)) => self.tcx.types.i32, | |
112 | ty::Infer(ty::FloatVar(_)) => self.tcx.types.f64, | |
c295e0f8 XL |
113 | _ => match diverging_fallback.get(&ty) { |
114 | Some(&fallback_ty) => fallback_ty, | |
115 | None => return false, | |
94222f64 XL |
116 | }, |
117 | }; | |
118 | debug!("fallback_if_possible(ty={:?}): defaulting to `{:?}`", ty, fallback); | |
119 | ||
120 | let span = self | |
121 | .infcx | |
122 | .type_var_origin(ty) | |
123 | .map(|origin| origin.span) | |
124 | .unwrap_or(rustc_span::DUMMY_SP); | |
125 | self.demand_eqtype(span, ty, fallback); | |
126 | true | |
127 | } | |
128 | ||
c295e0f8 XL |
129 | /// The "diverging fallback" system is rather complicated. This is |
130 | /// a result of our need to balance 'do the right thing' with | |
131 | /// backwards compatibility. | |
132 | /// | |
133 | /// "Diverging" type variables are variables created when we | |
134 | /// coerce a `!` type into an unbound type variable `?X`. If they | |
135 | /// never wind up being constrained, the "right and natural" thing | |
136 | /// is that `?X` should "fallback" to `!`. This means that e.g. an | |
137 | /// expression like `Some(return)` will ultimately wind up with a | |
138 | /// type like `Option<!>` (presuming it is not assigned or | |
139 | /// constrained to have some other type). | |
140 | /// | |
141 | /// However, the fallback used to be `()` (before the `!` type was | |
142 | /// added). Moreover, there are cases where the `!` type 'leaks | |
143 | /// out' from dead code into type variables that affect live | |
144 | /// code. The most common case is something like this: | |
145 | /// | |
146 | /// ```rust | |
147 | /// match foo() { | |
148 | /// 22 => Default::default(), // call this type `?D` | |
149 | /// _ => return, // return has type `!` | |
150 | /// } // call the type of this match `?M` | |
151 | /// ``` | |
152 | /// | |
153 | /// Here, coercing the type `!` into `?M` will create a diverging | |
154 | /// type variable `?X` where `?X <: ?M`. We also have that `?D <: | |
155 | /// ?M`. If `?M` winds up unconstrained, then `?X` will | |
156 | /// fallback. If it falls back to `!`, then all the type variables | |
157 | /// will wind up equal to `!` -- this includes the type `?D` | |
158 | /// (since `!` doesn't implement `Default`, we wind up a "trait | |
159 | /// not implemented" error in code like this). But since the | |
160 | /// original fallback was `()`, this code used to compile with `?D | |
161 | /// = ()`. This is somewhat surprising, since `Default::default()` | |
162 | /// on its own would give an error because the types are | |
163 | /// insufficiently constrained. | |
164 | /// | |
165 | /// Our solution to this dilemma is to modify diverging variables | |
166 | /// so that they can *either* fallback to `!` (the default) or to | |
167 | /// `()` (the backwards compatibility case). We decide which | |
168 | /// fallback to use based on whether there is a coercion pattern | |
169 | /// like this: | |
170 | /// | |
171 | /// ``` | |
172 | /// ?Diverging -> ?V | |
173 | /// ?NonDiverging -> ?V | |
174 | /// ?V != ?NonDiverging | |
175 | /// ``` | |
176 | /// | |
177 | /// Here `?Diverging` represents some diverging type variable and | |
178 | /// `?NonDiverging` represents some non-diverging type | |
179 | /// variable. `?V` can be any type variable (diverging or not), so | |
180 | /// long as it is not equal to `?NonDiverging`. | |
181 | /// | |
182 | /// Intuitively, what we are looking for is a case where a | |
183 | /// "non-diverging" type variable (like `?M` in our example above) | |
184 | /// is coerced *into* some variable `?V` that would otherwise | |
185 | /// fallback to `!`. In that case, we make `?V` fallback to `!`, | |
186 | /// along with anything that would flow into `?V`. | |
187 | /// | |
188 | /// The algorithm we use: | |
189 | /// * Identify all variables that are coerced *into* by a | |
190 | /// diverging variable. Do this by iterating over each | |
191 | /// diverging, unsolved variable and finding all variables | |
192 | /// reachable from there. Call that set `D`. | |
193 | /// * Walk over all unsolved, non-diverging variables, and find | |
194 | /// any variable that has an edge into `D`. | |
195 | fn calculate_diverging_fallback( | |
196 | &self, | |
197 | unsolved_variables: &[Ty<'tcx>], | |
198 | ) -> FxHashMap<Ty<'tcx>, Ty<'tcx>> { | |
199 | debug!("calculate_diverging_fallback({:?})", unsolved_variables); | |
200 | ||
201 | let relationships = self.fulfillment_cx.borrow_mut().relationships().clone(); | |
202 | ||
203 | // Construct a coercion graph where an edge `A -> B` indicates | |
204 | // a type variable is that is coerced | |
205 | let coercion_graph = self.create_coercion_graph(); | |
206 | ||
207 | // Extract the unsolved type inference variable vids; note that some | |
208 | // unsolved variables are integer/float variables and are excluded. | |
209 | let unsolved_vids = unsolved_variables.iter().filter_map(|ty| ty.ty_vid()); | |
210 | ||
211 | // Compute the diverging root vids D -- that is, the root vid of | |
212 | // those type variables that (a) are the target of a coercion from | |
213 | // a `!` type and (b) have not yet been solved. | |
214 | // | |
215 | // These variables are the ones that are targets for fallback to | |
216 | // either `!` or `()`. | |
217 | let diverging_roots: FxHashSet<ty::TyVid> = self | |
218 | .diverging_type_vars | |
219 | .borrow() | |
220 | .iter() | |
221 | .map(|&ty| self.infcx.shallow_resolve(ty)) | |
222 | .filter_map(|ty| ty.ty_vid()) | |
223 | .map(|vid| self.infcx.root_var(vid)) | |
224 | .collect(); | |
225 | debug!( | |
226 | "calculate_diverging_fallback: diverging_type_vars={:?}", | |
227 | self.diverging_type_vars.borrow() | |
228 | ); | |
229 | debug!("calculate_diverging_fallback: diverging_roots={:?}", diverging_roots); | |
230 | ||
231 | // Find all type variables that are reachable from a diverging | |
232 | // type variable. These will typically default to `!`, unless | |
233 | // we find later that they are *also* reachable from some | |
234 | // other type variable outside this set. | |
235 | let mut roots_reachable_from_diverging = DepthFirstSearch::new(&coercion_graph); | |
236 | let mut diverging_vids = vec![]; | |
237 | let mut non_diverging_vids = vec![]; | |
238 | for unsolved_vid in unsolved_vids { | |
239 | let root_vid = self.infcx.root_var(unsolved_vid); | |
240 | debug!( | |
241 | "calculate_diverging_fallback: unsolved_vid={:?} root_vid={:?} diverges={:?}", | |
242 | unsolved_vid, | |
243 | root_vid, | |
244 | diverging_roots.contains(&root_vid), | |
245 | ); | |
246 | if diverging_roots.contains(&root_vid) { | |
247 | diverging_vids.push(unsolved_vid); | |
248 | roots_reachable_from_diverging.push_start_node(root_vid); | |
249 | ||
250 | debug!( | |
251 | "calculate_diverging_fallback: root_vid={:?} reaches {:?}", | |
252 | root_vid, | |
253 | coercion_graph.depth_first_search(root_vid).collect::<Vec<_>>() | |
254 | ); | |
255 | ||
256 | // drain the iterator to visit all nodes reachable from this node | |
257 | roots_reachable_from_diverging.complete_search(); | |
258 | } else { | |
259 | non_diverging_vids.push(unsolved_vid); | |
260 | } | |
261 | } | |
262 | ||
263 | debug!( | |
264 | "calculate_diverging_fallback: roots_reachable_from_diverging={:?}", | |
265 | roots_reachable_from_diverging, | |
266 | ); | |
267 | ||
268 | // Find all type variables N0 that are not reachable from a | |
269 | // diverging variable, and then compute the set reachable from | |
270 | // N0, which we call N. These are the *non-diverging* type | |
271 | // variables. (Note that this set consists of "root variables".) | |
272 | let mut roots_reachable_from_non_diverging = DepthFirstSearch::new(&coercion_graph); | |
273 | for &non_diverging_vid in &non_diverging_vids { | |
274 | let root_vid = self.infcx.root_var(non_diverging_vid); | |
275 | if roots_reachable_from_diverging.visited(root_vid) { | |
276 | continue; | |
277 | } | |
278 | roots_reachable_from_non_diverging.push_start_node(root_vid); | |
279 | roots_reachable_from_non_diverging.complete_search(); | |
280 | } | |
281 | debug!( | |
282 | "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}", | |
283 | roots_reachable_from_non_diverging, | |
284 | ); | |
285 | ||
286 | debug!("inherited: {:#?}", self.inh.fulfillment_cx.borrow_mut().pending_obligations()); | |
287 | debug!("obligations: {:#?}", self.fulfillment_cx.borrow_mut().pending_obligations()); | |
288 | debug!("relationships: {:#?}", relationships); | |
289 | ||
290 | // For each diverging variable, figure out whether it can | |
291 | // reach a member of N. If so, it falls back to `()`. Else | |
292 | // `!`. | |
293 | let mut diverging_fallback = FxHashMap::default(); | |
294 | diverging_fallback.reserve(diverging_vids.len()); | |
295 | for &diverging_vid in &diverging_vids { | |
296 | let diverging_ty = self.tcx.mk_ty_var(diverging_vid); | |
297 | let root_vid = self.infcx.root_var(diverging_vid); | |
298 | let can_reach_non_diverging = coercion_graph | |
299 | .depth_first_search(root_vid) | |
300 | .any(|n| roots_reachable_from_non_diverging.visited(n)); | |
301 | ||
302 | let mut relationship = ty::FoundRelationships { self_in_trait: false, output: false }; | |
303 | ||
304 | for (vid, rel) in relationships.iter() { | |
305 | if self.infcx.root_var(*vid) == root_vid { | |
306 | relationship.self_in_trait |= rel.self_in_trait; | |
307 | relationship.output |= rel.output; | |
308 | } | |
309 | } | |
310 | ||
311 | if relationship.self_in_trait && relationship.output { | |
312 | // This case falls back to () to ensure that the code pattern in | |
313 | // src/test/ui/never_type/fallback-closure-ret.rs continues to | |
314 | // compile when never_type_fallback is enabled. | |
315 | // | |
316 | // This rule is not readily explainable from first principles, | |
317 | // but is rather intended as a patchwork fix to ensure code | |
318 | // which compiles before the stabilization of never type | |
319 | // fallback continues to work. | |
320 | // | |
321 | // Typically this pattern is encountered in a function taking a | |
322 | // closure as a parameter, where the return type of that closure | |
323 | // (checked by `relationship.output`) is expected to implement | |
324 | // some trait (checked by `relationship.self_in_trait`). This | |
325 | // can come up in non-closure cases too, so we do not limit this | |
326 | // rule to specifically `FnOnce`. | |
327 | // | |
328 | // When the closure's body is something like `panic!()`, the | |
329 | // return type would normally be inferred to `!`. However, it | |
330 | // needs to fall back to `()` in order to still compile, as the | |
331 | // trait is specifically implemented for `()` but not `!`. | |
332 | // | |
333 | // For details on the requirements for these relationships to be | |
334 | // set, see the relationship finding module in | |
335 | // compiler/rustc_trait_selection/src/traits/relationships.rs. | |
336 | debug!("fallback to () - found trait and projection: {:?}", diverging_vid); | |
337 | diverging_fallback.insert(diverging_ty, self.tcx.types.unit); | |
338 | } else if can_reach_non_diverging { | |
339 | debug!("fallback to () - reached non-diverging: {:?}", diverging_vid); | |
340 | diverging_fallback.insert(diverging_ty, self.tcx.types.unit); | |
341 | } else { | |
342 | debug!("fallback to ! - all diverging: {:?}", diverging_vid); | |
343 | diverging_fallback.insert(diverging_ty, self.tcx.mk_diverging_default()); | |
344 | } | |
345 | } | |
346 | ||
347 | diverging_fallback | |
348 | } | |
349 | ||
350 | /// Returns a graph whose nodes are (unresolved) inference variables and where | |
351 | /// an edge `?A -> ?B` indicates that the variable `?A` is coerced to `?B`. | |
352 | fn create_coercion_graph(&self) -> VecGraph<ty::TyVid> { | |
353 | let pending_obligations = self.fulfillment_cx.borrow_mut().pending_obligations(); | |
354 | debug!("create_coercion_graph: pending_obligations={:?}", pending_obligations); | |
355 | let coercion_edges: Vec<(ty::TyVid, ty::TyVid)> = pending_obligations | |
356 | .into_iter() | |
357 | .filter_map(|obligation| { | |
358 | // The predicates we are looking for look like `Coerce(?A -> ?B)`. | |
359 | // They will have no bound variables. | |
360 | obligation.predicate.kind().no_bound_vars() | |
361 | }) | |
362 | .filter_map(|atom| { | |
363 | // We consider both subtyping and coercion to imply 'flow' from | |
364 | // some position in the code `a` to a different position `b`. | |
365 | // This is then used to determine which variables interact with | |
366 | // live code, and as such must fall back to `()` to preserve | |
367 | // soundness. | |
368 | // | |
369 | // In practice currently the two ways that this happens is | |
370 | // coercion and subtyping. | |
371 | let (a, b) = if let ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) = atom { | |
372 | (a, b) | |
373 | } else if let ty::PredicateKind::Subtype(ty::SubtypePredicate { | |
374 | a_is_expected: _, | |
375 | a, | |
376 | b, | |
377 | }) = atom | |
378 | { | |
379 | (a, b) | |
380 | } else { | |
381 | return None; | |
382 | }; | |
383 | ||
384 | let a_vid = self.root_vid(a)?; | |
385 | let b_vid = self.root_vid(b)?; | |
386 | Some((a_vid, b_vid)) | |
387 | }) | |
388 | .collect(); | |
389 | debug!("create_coercion_graph: coercion_edges={:?}", coercion_edges); | |
390 | let num_ty_vars = self.infcx.num_ty_vars(); | |
391 | VecGraph::new(num_ty_vars, coercion_edges) | |
392 | } | |
393 | ||
394 | /// If `ty` is an unresolved type variable, returns its root vid. | |
395 | fn root_vid(&self, ty: Ty<'tcx>) -> Option<ty::TyVid> { | |
396 | Some(self.infcx.root_var(self.infcx.shallow_resolve(ty).ty_vid()?)) | |
397 | } | |
94222f64 | 398 | } |