2 use rustc_data_structures
::{
3 fx
::{FxHashMap, FxHashSet}
,
5 graph
::{iterate::DepthFirstSearch, vec_graph::VecGraph}
,
7 use rustc_middle
::ty
::{self, Ty}
;
9 impl<'tcx
> FnCtxt
<'_
, 'tcx
> {
10 /// Performs type inference fallback, setting `FnCtxt::fallback_has_occurred`
11 /// if fallback has occurred.
12 pub(super) fn type_inference_fallback(&self) {
14 "type-inference-fallback start obligations: {:#?}",
15 self.fulfillment_cx
.borrow_mut().pending_obligations()
18 // All type checking constraints were added, try to fallback unsolved variables.
19 self.select_obligations_where_possible(|_
| {}
);
22 "type-inference-fallback post selection obligations: {:#?}",
23 self.fulfillment_cx
.borrow_mut().pending_obligations()
26 // Check if we have any unsolved variables. If not, no need for fallback.
27 let unsolved_variables
= self.unsolved_variables();
28 if unsolved_variables
.is_empty() {
32 let diverging_fallback
= self.calculate_diverging_fallback(&unsolved_variables
);
34 // We do fallback in two passes, to try to generate
35 // better error messages.
36 // The first time, we do *not* replace opaque types.
37 for ty
in unsolved_variables
{
38 debug
!("unsolved_variable = {:?}", ty
);
39 self.fallback_if_possible(ty
, &diverging_fallback
);
42 // We now see if we can make progress. This might cause us to
43 // unify inference variables for opaque types, since we may
44 // have unified some other type variables during the first
45 // phase of fallback. This means that we only replace
46 // inference variables with their underlying opaque types as a
52 // type MyType = impl Copy;
53 // fn produce() -> MyType { true }
54 // fn bad_produce() -> MyType { panic!() }
57 // we want to unify the opaque inference variable in `bad_produce`
58 // with the diverging fallback for `panic!` (e.g. `()` or `!`).
59 // This will produce a nice error message about conflicting concrete
60 // types for `MyType`.
62 // If we had tried to fallback the opaque inference variable to `MyType`,
63 // we will generate a confusing type-check error that does not explicitly
64 // refer to opaque types.
65 self.select_obligations_where_possible(|_
| {}
);
68 // Tries to apply a fallback to `ty` if it is an unsolved variable.
70 // - Unconstrained ints are replaced with `i32`.
72 // - Unconstrained floats are replaced with `f64`.
74 // - Non-numerics may get replaced with `()` or `!`, depending on
75 // how they were categorized by `calculate_diverging_fallback`
76 // (and the setting of `#![feature(never_type_fallback)]`).
78 // Fallback becomes very dubious if we have encountered
79 // type-checking errors. In that case, fallback to Error.
81 // Sets `FnCtxt::fallback_has_occurred` if fallback is performed
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 let Some(e
) = self.tainted_by_errors() => self.tcx
.ty_error_with_guaranteed(e
),
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
,
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
);
123 self.fallback_has_occurred
.set(true);
126 /// The "diverging fallback" system is rather complicated. This is
127 /// a result of our need to balance 'do the right thing' with
128 /// backwards compatibility.
130 /// "Diverging" type variables are variables created when we
131 /// coerce a `!` type into an unbound type variable `?X`. If they
132 /// never wind up being constrained, the "right and natural" thing
133 /// is that `?X` should "fallback" to `!`. This means that e.g. an
134 /// expression like `Some(return)` will ultimately wind up with a
135 /// type like `Option<!>` (presuming it is not assigned or
136 /// constrained to have some other type).
138 /// However, the fallback used to be `()` (before the `!` type was
139 /// added). Moreover, there are cases where the `!` type 'leaks
140 /// out' from dead code into type variables that affect live
141 /// code. The most common case is something like this:
144 /// # fn foo() -> i32 { 4 }
146 /// 22 => Default::default(), // call this type `?D`
147 /// _ => return, // return has type `!`
148 /// } // call the type of this match `?M`
151 /// Here, coercing the type `!` into `?M` will create a diverging
152 /// type variable `?X` where `?X <: ?M`. We also have that `?D <:
153 /// ?M`. If `?M` winds up unconstrained, then `?X` will
154 /// fallback. If it falls back to `!`, then all the type variables
155 /// will wind up equal to `!` -- this includes the type `?D`
156 /// (since `!` doesn't implement `Default`, we wind up a "trait
157 /// not implemented" error in code like this). But since the
158 /// original fallback was `()`, this code used to compile with `?D
159 /// = ()`. This is somewhat surprising, since `Default::default()`
160 /// on its own would give an error because the types are
161 /// insufficiently constrained.
163 /// Our solution to this dilemma is to modify diverging variables
164 /// so that they can *either* fallback to `!` (the default) or to
165 /// `()` (the backwards compatibility case). We decide which
166 /// fallback to use based on whether there is a coercion pattern
169 /// ```ignore (not-rust)
171 /// ?NonDiverging -> ?V
172 /// ?V != ?NonDiverging
175 /// Here `?Diverging` represents some diverging type variable and
176 /// `?NonDiverging` represents some non-diverging type
177 /// variable. `?V` can be any type variable (diverging or not), so
178 /// long as it is not equal to `?NonDiverging`.
180 /// Intuitively, what we are looking for is a case where a
181 /// "non-diverging" type variable (like `?M` in our example above)
182 /// is coerced *into* some variable `?V` that would otherwise
183 /// fallback to `!`. In that case, we make `?V` fallback to `!`,
184 /// along with anything that would flow into `?V`.
186 /// The algorithm we use:
187 /// * Identify all variables that are coerced *into* by a
188 /// diverging variable. Do this by iterating over each
189 /// diverging, unsolved variable and finding all variables
190 /// reachable from there. Call that set `D`.
191 /// * Walk over all unsolved, non-diverging variables, and find
192 /// any variable that has an edge into `D`.
193 fn calculate_diverging_fallback(
195 unsolved_variables
: &[Ty
<'tcx
>],
196 ) -> FxHashMap
<Ty
<'tcx
>, Ty
<'tcx
>> {
197 debug
!("calculate_diverging_fallback({:?})", unsolved_variables
);
199 let relationships
= self.fulfillment_cx
.borrow_mut().relationships().clone();
201 // Construct a coercion graph where an edge `A -> B` indicates
202 // a type variable is that is coerced
203 let coercion_graph
= self.create_coercion_graph();
205 // Extract the unsolved type inference variable vids; note that some
206 // unsolved variables are integer/float variables and are excluded.
207 let unsolved_vids
= unsolved_variables
.iter().filter_map(|ty
| ty
.ty_vid());
209 // Compute the diverging root vids D -- that is, the root vid of
210 // those type variables that (a) are the target of a coercion from
211 // a `!` type and (b) have not yet been solved.
213 // These variables are the ones that are targets for fallback to
214 // either `!` or `()`.
215 let diverging_roots
: FxHashSet
<ty
::TyVid
> = self
219 .map(|&ty
| self.shallow_resolve(ty
))
220 .filter_map(|ty
| ty
.ty_vid())
221 .map(|vid
| self.root_var(vid
))
224 "calculate_diverging_fallback: diverging_type_vars={:?}",
225 self.diverging_type_vars
.borrow()
227 debug
!("calculate_diverging_fallback: diverging_roots={:?}", diverging_roots
);
229 // Find all type variables that are reachable from a diverging
230 // type variable. These will typically default to `!`, unless
231 // we find later that they are *also* reachable from some
232 // other type variable outside this set.
233 let mut roots_reachable_from_diverging
= DepthFirstSearch
::new(&coercion_graph
);
234 let mut diverging_vids
= vec
![];
235 let mut non_diverging_vids
= vec
![];
236 for unsolved_vid
in unsolved_vids
{
237 let root_vid
= self.root_var(unsolved_vid
);
239 "calculate_diverging_fallback: unsolved_vid={:?} root_vid={:?} diverges={:?}",
242 diverging_roots
.contains(&root_vid
),
244 if diverging_roots
.contains(&root_vid
) {
245 diverging_vids
.push(unsolved_vid
);
246 roots_reachable_from_diverging
.push_start_node(root_vid
);
249 "calculate_diverging_fallback: root_vid={:?} reaches {:?}",
251 coercion_graph
.depth_first_search(root_vid
).collect
::<Vec
<_
>>()
254 // drain the iterator to visit all nodes reachable from this node
255 roots_reachable_from_diverging
.complete_search();
257 non_diverging_vids
.push(unsolved_vid
);
262 "calculate_diverging_fallback: roots_reachable_from_diverging={:?}",
263 roots_reachable_from_diverging
,
266 // Find all type variables N0 that are not reachable from a
267 // diverging variable, and then compute the set reachable from
268 // N0, which we call N. These are the *non-diverging* type
269 // variables. (Note that this set consists of "root variables".)
270 let mut roots_reachable_from_non_diverging
= DepthFirstSearch
::new(&coercion_graph
);
271 for &non_diverging_vid
in &non_diverging_vids
{
272 let root_vid
= self.root_var(non_diverging_vid
);
273 if roots_reachable_from_diverging
.visited(root_vid
) {
276 roots_reachable_from_non_diverging
.push_start_node(root_vid
);
277 roots_reachable_from_non_diverging
.complete_search();
280 "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}",
281 roots_reachable_from_non_diverging
,
284 debug
!("inherited: {:#?}", self.inh
.fulfillment_cx
.borrow_mut().pending_obligations());
285 debug
!("obligations: {:#?}", self.fulfillment_cx
.borrow_mut().pending_obligations());
286 debug
!("relationships: {:#?}", relationships
);
288 // For each diverging variable, figure out whether it can
289 // reach a member of N. If so, it falls back to `()`. Else
291 let mut diverging_fallback
= FxHashMap
::default();
292 diverging_fallback
.reserve(diverging_vids
.len());
293 for &diverging_vid
in &diverging_vids
{
294 let diverging_ty
= self.tcx
.mk_ty_var(diverging_vid
);
295 let root_vid
= self.root_var(diverging_vid
);
296 let can_reach_non_diverging
= coercion_graph
297 .depth_first_search(root_vid
)
298 .any(|n
| roots_reachable_from_non_diverging
.visited(n
));
300 let mut relationship
= ty
::FoundRelationships { self_in_trait: false, output: false }
;
302 for (vid
, rel
) in relationships
.iter() {
303 if self.root_var(*vid
) == root_vid
{
304 relationship
.self_in_trait
|= rel
.self_in_trait
;
305 relationship
.output
|= rel
.output
;
309 if relationship
.self_in_trait
&& relationship
.output
{
310 // This case falls back to () to ensure that the code pattern in
311 // src/test/ui/never_type/fallback-closure-ret.rs continues to
312 // compile when never_type_fallback is enabled.
314 // This rule is not readily explainable from first principles,
315 // but is rather intended as a patchwork fix to ensure code
316 // which compiles before the stabilization of never type
317 // fallback continues to work.
319 // Typically this pattern is encountered in a function taking a
320 // closure as a parameter, where the return type of that closure
321 // (checked by `relationship.output`) is expected to implement
322 // some trait (checked by `relationship.self_in_trait`). This
323 // can come up in non-closure cases too, so we do not limit this
324 // rule to specifically `FnOnce`.
326 // When the closure's body is something like `panic!()`, the
327 // return type would normally be inferred to `!`. However, it
328 // needs to fall back to `()` in order to still compile, as the
329 // trait is specifically implemented for `()` but not `!`.
331 // For details on the requirements for these relationships to be
332 // set, see the relationship finding module in
333 // compiler/rustc_trait_selection/src/traits/relationships.rs.
334 debug
!("fallback to () - found trait and projection: {:?}", diverging_vid
);
335 diverging_fallback
.insert(diverging_ty
, self.tcx
.types
.unit
);
336 } else if can_reach_non_diverging
{
337 debug
!("fallback to () - reached non-diverging: {:?}", diverging_vid
);
338 diverging_fallback
.insert(diverging_ty
, self.tcx
.types
.unit
);
340 debug
!("fallback to ! - all diverging: {:?}", diverging_vid
);
341 diverging_fallback
.insert(diverging_ty
, self.tcx
.mk_diverging_default());
348 /// Returns a graph whose nodes are (unresolved) inference variables and where
349 /// an edge `?A -> ?B` indicates that the variable `?A` is coerced to `?B`.
350 fn create_coercion_graph(&self) -> VecGraph
<ty
::TyVid
> {
351 let pending_obligations
= self.fulfillment_cx
.borrow_mut().pending_obligations();
352 debug
!("create_coercion_graph: pending_obligations={:?}", pending_obligations
);
353 let coercion_edges
: Vec
<(ty
::TyVid
, ty
::TyVid
)> = pending_obligations
355 .filter_map(|obligation
| {
356 // The predicates we are looking for look like `Coerce(?A -> ?B)`.
357 // They will have no bound variables.
358 obligation
.predicate
.kind().no_bound_vars()
361 // We consider both subtyping and coercion to imply 'flow' from
362 // some position in the code `a` to a different position `b`.
363 // This is then used to determine which variables interact with
364 // live code, and as such must fall back to `()` to preserve
367 // In practice currently the two ways that this happens is
368 // coercion and subtyping.
369 let (a
, b
) = if let ty
::PredicateKind
::Coerce(ty
::CoercePredicate { a, b }
) = atom
{
371 } else if let ty
::PredicateKind
::Subtype(ty
::SubtypePredicate
{
382 let a_vid
= self.root_vid(a
)?
;
383 let b_vid
= self.root_vid(b
)?
;
387 debug
!("create_coercion_graph: coercion_edges={:?}", coercion_edges
);
388 let num_ty_vars
= self.num_ty_vars();
389 VecGraph
::new(num_ty_vars
, coercion_edges
)
392 /// If `ty` is an unresolved type variable, returns its root vid.
393 fn root_vid(&self, ty
: Ty
<'tcx
>) -> Option
<ty
::TyVid
> {
394 Some(self.root_var(self.shallow_resolve(ty
).ty_vid()?
))