]>
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 | ||
27 | // Check if we have any unsolved varibales. If not, no need for fallback. | |
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 | ||
69 | // We now run fallback again, but this time we allow it to replace | |
70 | // unconstrained opaque type variables, in addition to performing | |
71 | // other kinds of fallback. | |
72 | for ty in &self.unsolved_variables() { | |
73 | fallback_has_occurred |= self.fallback_opaque_type_vars(ty); | |
74 | } | |
75 | ||
76 | // See if we can make any more progress. | |
77 | self.select_obligations_where_possible(fallback_has_occurred, |_| {}); | |
78 | ||
79 | fallback_has_occurred | |
80 | } | |
81 | ||
82 | // Tries to apply a fallback to `ty` if it is an unsolved variable. | |
83 | // | |
84 | // - Unconstrained ints are replaced with `i32`. | |
85 | // | |
86 | // - Unconstrained floats are replaced with with `f64`. | |
87 | // | |
c295e0f8 XL |
88 | // - Non-numerics may get replaced with `()` or `!`, depending on |
89 | // how they were categorized by `calculate_diverging_fallback` | |
90 | // (and the setting of `#![feature(never_type_fallback)]`). | |
91 | // | |
92 | // Fallback becomes very dubious if we have encountered | |
93 | // type-checking errors. In that case, fallback to Error. | |
94222f64 | 94 | // |
94222f64 | 95 | // The return value indicates whether fallback has occurred. |
c295e0f8 XL |
96 | fn fallback_if_possible( |
97 | &self, | |
98 | ty: Ty<'tcx>, | |
99 | diverging_fallback: &FxHashMap<Ty<'tcx>, Ty<'tcx>>, | |
100 | ) -> bool { | |
94222f64 | 101 | // Careful: we do NOT shallow-resolve `ty`. We know that `ty` |
c295e0f8 XL |
102 | // is an unsolved variable, and we determine its fallback |
103 | // based solely on how it was created, not what other type | |
104 | // variables it may have been unified with since then. | |
94222f64 | 105 | // |
c295e0f8 XL |
106 | // The reason this matters is that other attempts at fallback |
107 | // may (in principle) conflict with this fallback, and we wish | |
108 | // to generate a type error in that case. (However, this | |
109 | // actually isn't true right now, because we're only using the | |
110 | // builtin fallback rules. This would be true if we were using | |
111 | // user-supplied fallbacks. But it's still useful to write the | |
112 | // code to detect bugs.) | |
94222f64 | 113 | // |
c295e0f8 XL |
114 | // (Note though that if we have a general type variable `?T` |
115 | // that is then unified with an integer type variable `?I` | |
116 | // that ultimately never gets resolved to a special integral | |
117 | // type, `?T` is not considered unsolved, but `?I` is. The | |
118 | // same is true for float variables.) | |
94222f64 XL |
119 | let fallback = match ty.kind() { |
120 | _ if self.is_tainted_by_errors() => self.tcx.ty_error(), | |
121 | ty::Infer(ty::IntVar(_)) => self.tcx.types.i32, | |
122 | ty::Infer(ty::FloatVar(_)) => self.tcx.types.f64, | |
c295e0f8 XL |
123 | _ => match diverging_fallback.get(&ty) { |
124 | Some(&fallback_ty) => fallback_ty, | |
125 | None => return false, | |
94222f64 XL |
126 | }, |
127 | }; | |
128 | debug!("fallback_if_possible(ty={:?}): defaulting to `{:?}`", ty, fallback); | |
129 | ||
130 | let span = self | |
131 | .infcx | |
132 | .type_var_origin(ty) | |
133 | .map(|origin| origin.span) | |
134 | .unwrap_or(rustc_span::DUMMY_SP); | |
135 | self.demand_eqtype(span, ty, fallback); | |
136 | true | |
137 | } | |
138 | ||
c295e0f8 XL |
139 | /// Second round of fallback: Unconstrained type variables created |
140 | /// from the instantiation of an opaque type fall back to the | |
141 | /// opaque type itself. This is a somewhat incomplete attempt to | |
142 | /// manage "identity passthrough" for `impl Trait` types. | |
94222f64 XL |
143 | /// |
144 | /// For example, in this code: | |
145 | /// | |
146 | ///``` | |
147 | /// type MyType = impl Copy; | |
148 | /// fn defining_use() -> MyType { true } | |
149 | /// fn other_use() -> MyType { defining_use() } | |
150 | /// ``` | |
151 | /// | |
152 | /// `defining_use` will constrain the instantiated inference | |
153 | /// variable to `bool`, while `other_use` will constrain | |
154 | /// the instantiated inference variable to `MyType`. | |
155 | /// | |
156 | /// When we process opaque types during writeback, we | |
157 | /// will handle cases like `other_use`, and not count | |
158 | /// them as defining usages | |
159 | /// | |
160 | /// However, we also need to handle cases like this: | |
161 | /// | |
162 | /// ```rust | |
163 | /// pub type Foo = impl Copy; | |
164 | /// fn produce() -> Option<Foo> { | |
165 | /// None | |
166 | /// } | |
167 | /// ``` | |
168 | /// | |
169 | /// In the above snippet, the inference variable created by | |
170 | /// instantiating `Option<Foo>` will be completely unconstrained. | |
171 | /// We treat this as a non-defining use by making the inference | |
172 | /// variable fall back to the opaque type itself. | |
173 | fn fallback_opaque_type_vars(&self, ty: Ty<'tcx>) -> bool { | |
174 | let span = self | |
175 | .infcx | |
176 | .type_var_origin(ty) | |
177 | .map(|origin| origin.span) | |
178 | .unwrap_or(rustc_span::DUMMY_SP); | |
179 | let oty = self.inner.borrow().opaque_types_vars.get(ty).map(|v| *v); | |
180 | if let Some(opaque_ty) = oty { | |
181 | debug!( | |
182 | "fallback_opaque_type_vars(ty={:?}): falling back to opaque type {:?}", | |
183 | ty, opaque_ty | |
184 | ); | |
185 | self.demand_eqtype(span, ty, opaque_ty); | |
186 | true | |
187 | } else { | |
188 | return false; | |
189 | } | |
190 | } | |
c295e0f8 XL |
191 | |
192 | /// The "diverging fallback" system is rather complicated. This is | |
193 | /// a result of our need to balance 'do the right thing' with | |
194 | /// backwards compatibility. | |
195 | /// | |
196 | /// "Diverging" type variables are variables created when we | |
197 | /// coerce a `!` type into an unbound type variable `?X`. If they | |
198 | /// never wind up being constrained, the "right and natural" thing | |
199 | /// is that `?X` should "fallback" to `!`. This means that e.g. an | |
200 | /// expression like `Some(return)` will ultimately wind up with a | |
201 | /// type like `Option<!>` (presuming it is not assigned or | |
202 | /// constrained to have some other type). | |
203 | /// | |
204 | /// However, the fallback used to be `()` (before the `!` type was | |
205 | /// added). Moreover, there are cases where the `!` type 'leaks | |
206 | /// out' from dead code into type variables that affect live | |
207 | /// code. The most common case is something like this: | |
208 | /// | |
209 | /// ```rust | |
210 | /// match foo() { | |
211 | /// 22 => Default::default(), // call this type `?D` | |
212 | /// _ => return, // return has type `!` | |
213 | /// } // call the type of this match `?M` | |
214 | /// ``` | |
215 | /// | |
216 | /// Here, coercing the type `!` into `?M` will create a diverging | |
217 | /// type variable `?X` where `?X <: ?M`. We also have that `?D <: | |
218 | /// ?M`. If `?M` winds up unconstrained, then `?X` will | |
219 | /// fallback. If it falls back to `!`, then all the type variables | |
220 | /// will wind up equal to `!` -- this includes the type `?D` | |
221 | /// (since `!` doesn't implement `Default`, we wind up a "trait | |
222 | /// not implemented" error in code like this). But since the | |
223 | /// original fallback was `()`, this code used to compile with `?D | |
224 | /// = ()`. This is somewhat surprising, since `Default::default()` | |
225 | /// on its own would give an error because the types are | |
226 | /// insufficiently constrained. | |
227 | /// | |
228 | /// Our solution to this dilemma is to modify diverging variables | |
229 | /// so that they can *either* fallback to `!` (the default) or to | |
230 | /// `()` (the backwards compatibility case). We decide which | |
231 | /// fallback to use based on whether there is a coercion pattern | |
232 | /// like this: | |
233 | /// | |
234 | /// ``` | |
235 | /// ?Diverging -> ?V | |
236 | /// ?NonDiverging -> ?V | |
237 | /// ?V != ?NonDiverging | |
238 | /// ``` | |
239 | /// | |
240 | /// Here `?Diverging` represents some diverging type variable and | |
241 | /// `?NonDiverging` represents some non-diverging type | |
242 | /// variable. `?V` can be any type variable (diverging or not), so | |
243 | /// long as it is not equal to `?NonDiverging`. | |
244 | /// | |
245 | /// Intuitively, what we are looking for is a case where a | |
246 | /// "non-diverging" type variable (like `?M` in our example above) | |
247 | /// is coerced *into* some variable `?V` that would otherwise | |
248 | /// fallback to `!`. In that case, we make `?V` fallback to `!`, | |
249 | /// along with anything that would flow into `?V`. | |
250 | /// | |
251 | /// The algorithm we use: | |
252 | /// * Identify all variables that are coerced *into* by a | |
253 | /// diverging variable. Do this by iterating over each | |
254 | /// diverging, unsolved variable and finding all variables | |
255 | /// reachable from there. Call that set `D`. | |
256 | /// * Walk over all unsolved, non-diverging variables, and find | |
257 | /// any variable that has an edge into `D`. | |
258 | fn calculate_diverging_fallback( | |
259 | &self, | |
260 | unsolved_variables: &[Ty<'tcx>], | |
261 | ) -> FxHashMap<Ty<'tcx>, Ty<'tcx>> { | |
262 | debug!("calculate_diverging_fallback({:?})", unsolved_variables); | |
263 | ||
264 | let relationships = self.fulfillment_cx.borrow_mut().relationships().clone(); | |
265 | ||
266 | // Construct a coercion graph where an edge `A -> B` indicates | |
267 | // a type variable is that is coerced | |
268 | let coercion_graph = self.create_coercion_graph(); | |
269 | ||
270 | // Extract the unsolved type inference variable vids; note that some | |
271 | // unsolved variables are integer/float variables and are excluded. | |
272 | let unsolved_vids = unsolved_variables.iter().filter_map(|ty| ty.ty_vid()); | |
273 | ||
274 | // Compute the diverging root vids D -- that is, the root vid of | |
275 | // those type variables that (a) are the target of a coercion from | |
276 | // a `!` type and (b) have not yet been solved. | |
277 | // | |
278 | // These variables are the ones that are targets for fallback to | |
279 | // either `!` or `()`. | |
280 | let diverging_roots: FxHashSet<ty::TyVid> = self | |
281 | .diverging_type_vars | |
282 | .borrow() | |
283 | .iter() | |
284 | .map(|&ty| self.infcx.shallow_resolve(ty)) | |
285 | .filter_map(|ty| ty.ty_vid()) | |
286 | .map(|vid| self.infcx.root_var(vid)) | |
287 | .collect(); | |
288 | debug!( | |
289 | "calculate_diverging_fallback: diverging_type_vars={:?}", | |
290 | self.diverging_type_vars.borrow() | |
291 | ); | |
292 | debug!("calculate_diverging_fallback: diverging_roots={:?}", diverging_roots); | |
293 | ||
294 | // Find all type variables that are reachable from a diverging | |
295 | // type variable. These will typically default to `!`, unless | |
296 | // we find later that they are *also* reachable from some | |
297 | // other type variable outside this set. | |
298 | let mut roots_reachable_from_diverging = DepthFirstSearch::new(&coercion_graph); | |
299 | let mut diverging_vids = vec![]; | |
300 | let mut non_diverging_vids = vec![]; | |
301 | for unsolved_vid in unsolved_vids { | |
302 | let root_vid = self.infcx.root_var(unsolved_vid); | |
303 | debug!( | |
304 | "calculate_diverging_fallback: unsolved_vid={:?} root_vid={:?} diverges={:?}", | |
305 | unsolved_vid, | |
306 | root_vid, | |
307 | diverging_roots.contains(&root_vid), | |
308 | ); | |
309 | if diverging_roots.contains(&root_vid) { | |
310 | diverging_vids.push(unsolved_vid); | |
311 | roots_reachable_from_diverging.push_start_node(root_vid); | |
312 | ||
313 | debug!( | |
314 | "calculate_diverging_fallback: root_vid={:?} reaches {:?}", | |
315 | root_vid, | |
316 | coercion_graph.depth_first_search(root_vid).collect::<Vec<_>>() | |
317 | ); | |
318 | ||
319 | // drain the iterator to visit all nodes reachable from this node | |
320 | roots_reachable_from_diverging.complete_search(); | |
321 | } else { | |
322 | non_diverging_vids.push(unsolved_vid); | |
323 | } | |
324 | } | |
325 | ||
326 | debug!( | |
327 | "calculate_diverging_fallback: roots_reachable_from_diverging={:?}", | |
328 | roots_reachable_from_diverging, | |
329 | ); | |
330 | ||
331 | // Find all type variables N0 that are not reachable from a | |
332 | // diverging variable, and then compute the set reachable from | |
333 | // N0, which we call N. These are the *non-diverging* type | |
334 | // variables. (Note that this set consists of "root variables".) | |
335 | let mut roots_reachable_from_non_diverging = DepthFirstSearch::new(&coercion_graph); | |
336 | for &non_diverging_vid in &non_diverging_vids { | |
337 | let root_vid = self.infcx.root_var(non_diverging_vid); | |
338 | if roots_reachable_from_diverging.visited(root_vid) { | |
339 | continue; | |
340 | } | |
341 | roots_reachable_from_non_diverging.push_start_node(root_vid); | |
342 | roots_reachable_from_non_diverging.complete_search(); | |
343 | } | |
344 | debug!( | |
345 | "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}", | |
346 | roots_reachable_from_non_diverging, | |
347 | ); | |
348 | ||
349 | debug!("inherited: {:#?}", self.inh.fulfillment_cx.borrow_mut().pending_obligations()); | |
350 | debug!("obligations: {:#?}", self.fulfillment_cx.borrow_mut().pending_obligations()); | |
351 | debug!("relationships: {:#?}", relationships); | |
352 | ||
353 | // For each diverging variable, figure out whether it can | |
354 | // reach a member of N. If so, it falls back to `()`. Else | |
355 | // `!`. | |
356 | let mut diverging_fallback = FxHashMap::default(); | |
357 | diverging_fallback.reserve(diverging_vids.len()); | |
358 | for &diverging_vid in &diverging_vids { | |
359 | let diverging_ty = self.tcx.mk_ty_var(diverging_vid); | |
360 | let root_vid = self.infcx.root_var(diverging_vid); | |
361 | let can_reach_non_diverging = coercion_graph | |
362 | .depth_first_search(root_vid) | |
363 | .any(|n| roots_reachable_from_non_diverging.visited(n)); | |
364 | ||
365 | let mut relationship = ty::FoundRelationships { self_in_trait: false, output: false }; | |
366 | ||
367 | for (vid, rel) in relationships.iter() { | |
368 | if self.infcx.root_var(*vid) == root_vid { | |
369 | relationship.self_in_trait |= rel.self_in_trait; | |
370 | relationship.output |= rel.output; | |
371 | } | |
372 | } | |
373 | ||
374 | if relationship.self_in_trait && relationship.output { | |
375 | // This case falls back to () to ensure that the code pattern in | |
376 | // src/test/ui/never_type/fallback-closure-ret.rs continues to | |
377 | // compile when never_type_fallback is enabled. | |
378 | // | |
379 | // This rule is not readily explainable from first principles, | |
380 | // but is rather intended as a patchwork fix to ensure code | |
381 | // which compiles before the stabilization of never type | |
382 | // fallback continues to work. | |
383 | // | |
384 | // Typically this pattern is encountered in a function taking a | |
385 | // closure as a parameter, where the return type of that closure | |
386 | // (checked by `relationship.output`) is expected to implement | |
387 | // some trait (checked by `relationship.self_in_trait`). This | |
388 | // can come up in non-closure cases too, so we do not limit this | |
389 | // rule to specifically `FnOnce`. | |
390 | // | |
391 | // When the closure's body is something like `panic!()`, the | |
392 | // return type would normally be inferred to `!`. However, it | |
393 | // needs to fall back to `()` in order to still compile, as the | |
394 | // trait is specifically implemented for `()` but not `!`. | |
395 | // | |
396 | // For details on the requirements for these relationships to be | |
397 | // set, see the relationship finding module in | |
398 | // compiler/rustc_trait_selection/src/traits/relationships.rs. | |
399 | debug!("fallback to () - found trait and projection: {:?}", diverging_vid); | |
400 | diverging_fallback.insert(diverging_ty, self.tcx.types.unit); | |
401 | } else if can_reach_non_diverging { | |
402 | debug!("fallback to () - reached non-diverging: {:?}", diverging_vid); | |
403 | diverging_fallback.insert(diverging_ty, self.tcx.types.unit); | |
404 | } else { | |
405 | debug!("fallback to ! - all diverging: {:?}", diverging_vid); | |
406 | diverging_fallback.insert(diverging_ty, self.tcx.mk_diverging_default()); | |
407 | } | |
408 | } | |
409 | ||
410 | diverging_fallback | |
411 | } | |
412 | ||
413 | /// Returns a graph whose nodes are (unresolved) inference variables and where | |
414 | /// an edge `?A -> ?B` indicates that the variable `?A` is coerced to `?B`. | |
415 | fn create_coercion_graph(&self) -> VecGraph<ty::TyVid> { | |
416 | let pending_obligations = self.fulfillment_cx.borrow_mut().pending_obligations(); | |
417 | debug!("create_coercion_graph: pending_obligations={:?}", pending_obligations); | |
418 | let coercion_edges: Vec<(ty::TyVid, ty::TyVid)> = pending_obligations | |
419 | .into_iter() | |
420 | .filter_map(|obligation| { | |
421 | // The predicates we are looking for look like `Coerce(?A -> ?B)`. | |
422 | // They will have no bound variables. | |
423 | obligation.predicate.kind().no_bound_vars() | |
424 | }) | |
425 | .filter_map(|atom| { | |
426 | // We consider both subtyping and coercion to imply 'flow' from | |
427 | // some position in the code `a` to a different position `b`. | |
428 | // This is then used to determine which variables interact with | |
429 | // live code, and as such must fall back to `()` to preserve | |
430 | // soundness. | |
431 | // | |
432 | // In practice currently the two ways that this happens is | |
433 | // coercion and subtyping. | |
434 | let (a, b) = if let ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) = atom { | |
435 | (a, b) | |
436 | } else if let ty::PredicateKind::Subtype(ty::SubtypePredicate { | |
437 | a_is_expected: _, | |
438 | a, | |
439 | b, | |
440 | }) = atom | |
441 | { | |
442 | (a, b) | |
443 | } else { | |
444 | return None; | |
445 | }; | |
446 | ||
447 | let a_vid = self.root_vid(a)?; | |
448 | let b_vid = self.root_vid(b)?; | |
449 | Some((a_vid, b_vid)) | |
450 | }) | |
451 | .collect(); | |
452 | debug!("create_coercion_graph: coercion_edges={:?}", coercion_edges); | |
453 | let num_ty_vars = self.infcx.num_ty_vars(); | |
454 | VecGraph::new(num_ty_vars, coercion_edges) | |
455 | } | |
456 | ||
457 | /// If `ty` is an unresolved type variable, returns its root vid. | |
458 | fn root_vid(&self, ty: Ty<'tcx>) -> Option<ty::TyVid> { | |
459 | Some(self.infcx.root_var(self.infcx.shallow_resolve(ty).ty_vid()?)) | |
460 | } | |
94222f64 | 461 | } |