1 use crate::check::FnCtxt;
2 use rustc_data_structures::{
3 fx::FxHashMap, graph::vec_graph::VecGraph, graph::WithSuccessors, stable_set::FxHashSet,
5 use rustc_middle::ty::{self, Ty};
7 impl<'tcx> FnCtxt<'_, 'tcx> {
8 /// Performs type inference fallback, returning true if any fallback
10 pub(super) fn type_inference_fallback(&self) -> bool {
11 // All type checking constraints were added, try to fallback unsolved variables.
12 self.select_obligations_where_possible(false, |_| {});
14 // Check if we have any unsolved varibales. If not, no need for fallback.
15 let unsolved_variables = self.unsolved_variables();
16 if unsolved_variables.is_empty() {
20 let diverging_fallback = self.calculate_diverging_fallback(&unsolved_variables);
22 let mut fallback_has_occurred = false;
23 // We do fallback in two passes, to try to generate
24 // better error messages.
25 // The first time, we do *not* replace opaque types.
26 for ty in unsolved_variables {
27 debug!("unsolved_variable = {:?}", ty);
28 fallback_has_occurred |= self.fallback_if_possible(ty, &diverging_fallback);
31 // We now see if we can make progress. This might cause us to
32 // unify inference variables for opaque types, since we may
33 // have unified some other type variables during the first
34 // phase of fallback. This means that we only replace
35 // inference variables with their underlying opaque types as a
41 // type MyType = impl Copy;
42 // fn produce() -> MyType { true }
43 // fn bad_produce() -> MyType { panic!() }
46 // we want to unify the opaque inference variable in `bad_produce`
47 // with the diverging fallback for `panic!` (e.g. `()` or `!`).
48 // This will produce a nice error message about conflicting concrete
49 // types for `MyType`.
51 // If we had tried to fallback the opaque inference variable to `MyType`,
52 // we will generate a confusing type-check error that does not explicitly
53 // refer to opaque types.
54 self.select_obligations_where_possible(fallback_has_occurred, |_| {});
56 // We now run fallback again, but this time we allow it to replace
57 // unconstrained opaque type variables, in addition to performing
58 // other kinds of fallback.
59 for ty in &self.unsolved_variables() {
60 fallback_has_occurred |= self.fallback_opaque_type_vars(ty);
63 // See if we can make any more progress.
64 self.select_obligations_where_possible(fallback_has_occurred, |_| {});
69 // Tries to apply a fallback to `ty` if it is an unsolved variable.
71 // - Unconstrained ints are replaced with `i32`.
73 // - Unconstrained floats are replaced with with `f64`.
75 // - Non-numerics may get replaced with `()` or `!`, depending on
76 // how they were categorized by `calculate_diverging_fallback`
77 // (and the setting of `#![feature(never_type_fallback)]`).
79 // Fallback becomes very dubious if we have encountered
80 // type-checking errors. In that case, fallback to Error.
82 // The return value indicates whether fallback has occurred.
83 fn fallback_if_possible(
86 diverging_fallback: &FxHashMap<Ty<'tcx>, Ty<'tcx>>,
88 // Careful: we do NOT shallow-resolve `ty`. We know that `ty`
89 // is an unsolved variable, and we determine its fallback
90 // based solely on how it was created, not what other type
91 // variables it may have been unified with since then.
93 // The reason this matters is that other attempts at fallback
94 // may (in principle) conflict with this fallback, and we wish
95 // to generate a type error in that case. (However, this
96 // actually isn't true right now, because we're only using the
97 // builtin fallback rules. This would be true if we were using
98 // user-supplied fallbacks. But it's still useful to write the
99 // code to detect bugs.)
101 // (Note though that if we have a general type variable `?T`
102 // that is then unified with an integer type variable `?I`
103 // that ultimately never gets resolved to a special integral
104 // type, `?T` is not considered unsolved, but `?I` is. The
105 // same is true for float variables.)
106 let fallback = match ty.kind() {
107 _ if self.is_tainted_by_errors() => self.tcx.ty_error(),
108 ty::Infer(ty::IntVar(_)) => self.tcx.types.i32,
109 ty::Infer(ty::FloatVar(_)) => self.tcx.types.f64,
110 _ => match diverging_fallback.get(&ty) {
111 Some(&fallback_ty) => fallback_ty,
112 None => return false,
115 debug!("fallback_if_possible(ty={:?}): defaulting to `{:?}`", ty, fallback);
120 .map(|origin| origin.span)
121 .unwrap_or(rustc_span::DUMMY_SP);
122 self.demand_eqtype(span, ty, fallback);
126 /// Second round of fallback: Unconstrained type variables created
127 /// from the instantiation of an opaque type fall back to the
128 /// opaque type itself. This is a somewhat incomplete attempt to
129 /// manage "identity passthrough" for `impl Trait` types.
131 /// For example, in this code:
134 /// type MyType = impl Copy;
135 /// fn defining_use() -> MyType { true }
136 /// fn other_use() -> MyType { defining_use() }
139 /// `defining_use` will constrain the instantiated inference
140 /// variable to `bool`, while `other_use` will constrain
141 /// the instantiated inference variable to `MyType`.
143 /// When we process opaque types during writeback, we
144 /// will handle cases like `other_use`, and not count
145 /// them as defining usages
147 /// However, we also need to handle cases like this:
150 /// pub type Foo = impl Copy;
151 /// fn produce() -> Option<Foo> {
156 /// In the above snippet, the inference variable created by
157 /// instantiating `Option<Foo>` will be completely unconstrained.
158 /// We treat this as a non-defining use by making the inference
159 /// variable fall back to the opaque type itself.
160 fn fallback_opaque_type_vars(&self, ty: Ty<'tcx>) -> bool {
164 .map(|origin| origin.span)
165 .unwrap_or(rustc_span::DUMMY_SP);
166 let oty = self.inner.borrow().opaque_types_vars.get(ty).map(|v| *v);
167 if let Some(opaque_ty) = oty {
169 "fallback_opaque_type_vars(ty={:?}): falling back to opaque type {:?}",
172 self.demand_eqtype(span, ty, opaque_ty);
179 /// The "diverging fallback" system is rather complicated. This is
180 /// a result of our need to balance 'do the right thing' with
181 /// backwards compatibility.
183 /// "Diverging" type variables are variables created when we
184 /// coerce a `!` type into an unbound type variable `?X`. If they
185 /// never wind up being constrained, the "right and natural" thing
186 /// is that `?X` should "fallback" to `!`. This means that e.g. an
187 /// expression like `Some(return)` will ultimately wind up with a
188 /// type like `Option<!>` (presuming it is not assigned or
189 /// constrained to have some other type).
191 /// However, the fallback used to be `()` (before the `!` type was
192 /// added). Moreover, there are cases where the `!` type 'leaks
193 /// out' from dead code into type variables that affect live
194 /// code. The most common case is something like this:
198 /// 22 => Default::default(), // call this type `?D`
199 /// _ => return, // return has type `!`
200 /// } // call the type of this match `?M`
203 /// Here, coercing the type `!` into `?M` will create a diverging
204 /// type variable `?X` where `?X <: ?M`. We also have that `?D <:
205 /// ?M`. If `?M` winds up unconstrained, then `?X` will
206 /// fallback. If it falls back to `!`, then all the type variables
207 /// will wind up equal to `!` -- this includes the type `?D`
208 /// (since `!` doesn't implement `Default`, we wind up a "trait
209 /// not implemented" error in code like this). But since the
210 /// original fallback was `()`, this code used to compile with `?D
211 /// = ()`. This is somewhat surprising, since `Default::default()`
212 /// on its own would give an error because the types are
213 /// insufficiently constrained.
215 /// Our solution to this dilemma is to modify diverging variables
216 /// so that they can *either* fallback to `!` (the default) or to
217 /// `()` (the backwards compatibility case). We decide which
218 /// fallback to use based on whether there is a coercion pattern
223 /// ?NonDiverging -> ?V
224 /// ?V != ?NonDiverging
227 /// Here `?Diverging` represents some diverging type variable and
228 /// `?NonDiverging` represents some non-diverging type
229 /// variable. `?V` can be any type variable (diverging or not), so
230 /// long as it is not equal to `?NonDiverging`.
232 /// Intuitively, what we are looking for is a case where a
233 /// "non-diverging" type variable (like `?M` in our example above)
234 /// is coerced *into* some variable `?V` that would otherwise
235 /// fallback to `!`. In that case, we make `?V` fallback to `!`,
236 /// along with anything that would flow into `?V`.
238 /// The algorithm we use:
239 /// * Identify all variables that are coerced *into* by a
240 /// diverging variable. Do this by iterating over each
241 /// diverging, unsolved variable and finding all variables
242 /// reachable from there. Call that set `D`.
243 /// * Walk over all unsolved, non-diverging variables, and find
244 /// any variable that has an edge into `D`.
245 fn calculate_diverging_fallback(
247 unsolved_variables: &[Ty<'tcx>],
248 ) -> FxHashMap<Ty<'tcx>, Ty<'tcx>> {
249 debug!("calculate_diverging_fallback({:?})", unsolved_variables);
251 // Construct a coercion graph where an edge `A -> B` indicates
252 // a type variable is that is coerced
253 let coercion_graph = self.create_coercion_graph();
255 // Extract the unsolved type inference variable vids; note that some
256 // unsolved variables are integer/float variables and are excluded.
257 let unsolved_vids = unsolved_variables.iter().filter_map(|ty| ty.ty_vid());
259 // Compute the diverging root vids D -- that is, the root vid of
260 // those type variables that (a) are the target of a coercion from
261 // a `!` type and (b) have not yet been solved.
263 // These variables are the ones that are targets for fallback to
264 // either `!` or `()`.
265 let diverging_roots: FxHashSet<ty::TyVid> = self
269 .map(|&ty| self.infcx.shallow_resolve(ty))
270 .filter_map(|ty| ty.ty_vid())
271 .map(|vid| self.infcx.root_var(vid))
274 "calculate_diverging_fallback: diverging_type_vars={:?}",
275 self.diverging_type_vars.borrow()
277 debug!("calculate_diverging_fallback: diverging_roots={:?}", diverging_roots);
279 // Find all type variables that are reachable from a diverging
280 // type variable. These will typically default to `!`, unless
281 // we find later that they are *also* reachable from some
282 // other type variable outside this set.
283 let mut roots_reachable_from_diverging = FxHashSet::default();
284 let mut diverging_vids = vec![];
285 let mut non_diverging_vids = vec![];
286 for unsolved_vid in unsolved_vids {
287 let root_vid = self.infcx.root_var(unsolved_vid);
289 "calculate_diverging_fallback: unsolved_vid={:?} root_vid={:?} diverges={:?}",
292 diverging_roots.contains(&root_vid),
294 if diverging_roots.contains(&root_vid) {
295 diverging_vids.push(unsolved_vid);
297 "calculate_diverging_fallback: root_vid={:?} reaches {:?}",
299 coercion_graph.depth_first_search(root_vid).collect::<Vec<_>>()
301 roots_reachable_from_diverging.extend(coercion_graph.depth_first_search(root_vid));
303 non_diverging_vids.push(unsolved_vid);
307 "calculate_diverging_fallback: roots_reachable_from_diverging={:?}",
308 roots_reachable_from_diverging,
311 // Find all type variables N0 that are not reachable from a
312 // diverging variable, and then compute the set reachable from
313 // N0, which we call N. These are the *non-diverging* type
314 // variables. (Note that this set consists of "root variables".)
315 let mut roots_reachable_from_non_diverging = FxHashSet::default();
316 for &non_diverging_vid in &non_diverging_vids {
317 let root_vid = self.infcx.root_var(non_diverging_vid);
318 if roots_reachable_from_diverging.contains(&root_vid) {
321 roots_reachable_from_non_diverging.extend(coercion_graph.depth_first_search(root_vid));
324 "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}",
325 roots_reachable_from_non_diverging,
328 // For each diverging variable, figure out whether it can
329 // reach a member of N. If so, it falls back to `()`. Else
331 let mut diverging_fallback = FxHashMap::default();
332 for &diverging_vid in &diverging_vids {
333 let diverging_ty = self.tcx.mk_ty_var(diverging_vid);
334 let root_vid = self.infcx.root_var(diverging_vid);
335 let can_reach_non_diverging = coercion_graph
336 .depth_first_search(root_vid)
337 .any(|n| roots_reachable_from_non_diverging.contains(&n));
338 if can_reach_non_diverging {
339 debug!("fallback to (): {:?}", diverging_vid);
340 diverging_fallback.insert(diverging_ty, self.tcx.types.unit);
342 debug!("fallback to !: {:?}", diverging_vid);
343 diverging_fallback.insert(diverging_ty, self.tcx.mk_diverging_default());
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
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()
363 if let ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) = atom {
364 let a_vid = self.root_vid(a)?;
365 let b_vid = self.root_vid(b)?;
371 let a_vid = self.root_vid(a)?;
372 let b_vid = self.root_vid(b)?;
376 debug!("create_coercion_graph: coercion_edges={:?}", coercion_edges);
377 let num_ty_vars = self.infcx.num_ty_vars();
378 VecGraph::new(num_ty_vars, coercion_edges)
381 /// If `ty` is an unresolved type variable, returns its root vid.
382 fn root_vid(&self, ty: Ty<'tcx>) -> Option<ty::TyVid> {
383 Some(self.infcx.root_var(self.infcx.shallow_resolve(ty).ty_vid()?))