1 use crate::check
::FnCtxt
;
2 use rustc_data_structures
::{
5 graph
::{iterate::DepthFirstSearch, vec_graph::VecGraph}
,
8 use rustc_middle
::ty
::{self, Ty}
;
10 impl<'tcx
> FnCtxt
<'_
, 'tcx
> {
11 /// Performs type inference fallback, returning true if any fallback
13 pub(super) fn type_inference_fallback(&self) -> bool
{
15 "type-inference-fallback start obligations: {:#?}",
16 self.fulfillment_cx
.borrow_mut().pending_obligations()
19 // All type checking constraints were added, try to fallback unsolved variables.
20 self.select_obligations_where_possible(false, |_
| {}
);
23 "type-inference-fallback post selection obligations: {:#?}",
24 self.fulfillment_cx
.borrow_mut().pending_obligations()
27 // Check if we have any unsolved variables. If not, no need for fallback.
28 let unsolved_variables
= self.unsolved_variables();
29 if unsolved_variables
.is_empty() {
33 let diverging_fallback
= self.calculate_diverging_fallback(&unsolved_variables
);
35 let mut fallback_has_occurred
= false;
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.
39 for ty
in unsolved_variables
{
40 debug
!("unsolved_variable = {:?}", ty
);
41 fallback_has_occurred
|= self.fallback_if_possible(ty
, &diverging_fallback
);
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
54 // type MyType = impl Copy;
55 // fn produce() -> MyType { true }
56 // fn bad_produce() -> MyType { panic!() }
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`.
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
, |_
| {}
);
72 // Tries to apply a fallback to `ty` if it is an unsolved variable.
74 // - Unconstrained ints are replaced with `i32`.
76 // - Unconstrained floats are replaced with with `f64`.
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)]`).
82 // Fallback becomes very dubious if we have encountered
83 // type-checking errors. In that case, fallback to Error.
85 // The return value indicates whether fallback has occurred.
86 fn fallback_if_possible(
89 diverging_fallback
: &FxHashMap
<Ty
<'tcx
>, Ty
<'tcx
>>,
91 // Careful: we do NOT shallow-resolve `ty`. We know that `ty`
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.
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.)
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.)
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,
113 _
=> match diverging_fallback
.get(&ty
) {
114 Some(&fallback_ty
) => fallback_ty
,
115 None
=> return false,
118 debug
!("fallback_if_possible(ty={:?}): defaulting to `{:?}`", ty
, fallback
);
123 .map(|origin
| origin
.span
)
124 .unwrap_or(rustc_span
::DUMMY_SP
);
125 self.demand_eqtype(span
, ty
, fallback
);
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.
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).
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:
148 /// 22 => Default::default(), // call this type `?D`
149 /// _ => return, // return has type `!`
150 /// } // call the type of this match `?M`
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.
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
173 /// ?NonDiverging -> ?V
174 /// ?V != ?NonDiverging
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`.
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`.
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(
197 unsolved_variables
: &[Ty
<'tcx
>],
198 ) -> FxHashMap
<Ty
<'tcx
>, Ty
<'tcx
>> {
199 debug
!("calculate_diverging_fallback({:?})", unsolved_variables
);
201 let relationships
= self.fulfillment_cx
.borrow_mut().relationships().clone();
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();
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());
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.
215 // These variables are the ones that are targets for fallback to
216 // either `!` or `()`.
217 let diverging_roots
: FxHashSet
<ty
::TyVid
> = self
221 .map(|&ty
| self.infcx
.shallow_resolve(ty
))
222 .filter_map(|ty
| ty
.ty_vid())
223 .map(|vid
| self.infcx
.root_var(vid
))
226 "calculate_diverging_fallback: diverging_type_vars={:?}",
227 self.diverging_type_vars
.borrow()
229 debug
!("calculate_diverging_fallback: diverging_roots={:?}", diverging_roots
);
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
);
241 "calculate_diverging_fallback: unsolved_vid={:?} root_vid={:?} diverges={:?}",
244 diverging_roots
.contains(&root_vid
),
246 if diverging_roots
.contains(&root_vid
) {
247 diverging_vids
.push(unsolved_vid
);
248 roots_reachable_from_diverging
.push_start_node(root_vid
);
251 "calculate_diverging_fallback: root_vid={:?} reaches {:?}",
253 coercion_graph
.depth_first_search(root_vid
).collect
::<Vec
<_
>>()
256 // drain the iterator to visit all nodes reachable from this node
257 roots_reachable_from_diverging
.complete_search();
259 non_diverging_vids
.push(unsolved_vid
);
264 "calculate_diverging_fallback: roots_reachable_from_diverging={:?}",
265 roots_reachable_from_diverging
,
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
) {
278 roots_reachable_from_non_diverging
.push_start_node(root_vid
);
279 roots_reachable_from_non_diverging
.complete_search();
282 "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}",
283 roots_reachable_from_non_diverging
,
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
);
290 // For each diverging variable, figure out whether it can
291 // reach a member of N. If so, it falls back to `()`. Else
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
));
302 let mut relationship
= ty
::FoundRelationships { self_in_trait: false, output: false }
;
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
;
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.
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.
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`.
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 `!`.
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
);
342 debug
!("fallback to ! - all diverging: {:?}", 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 // 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
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
{
373 } else if let ty
::PredicateKind
::Subtype(ty
::SubtypePredicate
{
384 let a_vid
= self.root_vid(a
)?
;
385 let b_vid
= self.root_vid(b
)?
;
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
)
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()?
))