From 2ee89144e21c10a95b411ff72235da6e29c04a94 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Sun, 22 Nov 2020 09:58:58 -0500 Subject: introduce new fallback algorithm We now fallback type variables using the following rules: * Construct a coercion graph `A -> B` where `A` and `B` are unresolved type variables or the `!` type. * Let D be those variables that are reachable from `!`. * Let N be those variables that are reachable from a variable not in D. * All variables in (D \ N) fallback to `!`. * All variables in (D & N) fallback to `()`. --- compiler/rustc_infer/src/infer/mod.rs | 13 +- compiler/rustc_middle/src/ty/sty.rs | 8 + compiler/rustc_typeck/src/check/fallback.rs | 279 ++++++++++++++++++++++++---- 3 files changed, 264 insertions(+), 36 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_infer/src/infer/mod.rs b/compiler/rustc_infer/src/infer/mod.rs index 354b8e26d53..7302aa13cc4 100644 --- a/compiler/rustc_infer/src/infer/mod.rs +++ b/compiler/rustc_infer/src/infer/mod.rs @@ -707,11 +707,17 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { /// No attempt is made to resolve `ty`. pub fn type_var_diverges(&'a self, ty: Ty<'_>) -> Diverging { match *ty.kind() { - ty::Infer(ty::TyVar(vid)) => self.inner.borrow_mut().type_variables().var_diverges(vid), + ty::Infer(ty::TyVar(vid)) => self.ty_vid_diverges(vid), _ => Diverging::NotDiverging, } } + /// Returns true if the type inference variable `vid` was created + /// as a diverging type variable. No attempt is made to resolve `vid`. + pub fn ty_vid_diverges(&'a self, vid: ty::TyVid) -> Diverging { + self.inner.borrow_mut().type_variables().var_diverges(vid) + } + /// Returns the origin of the type variable identified by `vid`, or `None` /// if this is not a type variable. /// @@ -1070,6 +1076,11 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { }) } + /// Number of type variables created so far. + pub fn num_ty_vars(&self) -> usize { + self.inner.borrow_mut().type_variables().num_vars() + } + pub fn next_ty_var_id(&self, diverging: Diverging, origin: TypeVariableOrigin) -> TyVid { self.inner.borrow_mut().type_variables().new_var(self.universe(), diverging, origin) } diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs index 0fbaf81c21e..1e17ba204b2 100644 --- a/compiler/rustc_middle/src/ty/sty.rs +++ b/compiler/rustc_middle/src/ty/sty.rs @@ -1672,6 +1672,14 @@ impl<'tcx> TyS<'tcx> { matches!(self.kind(), Infer(TyVar(_))) } + #[inline] + pub fn ty_vid(&self) -> Option { + match self.kind() { + &Infer(TyVar(vid)) => Some(vid), + _ => None, + } + } + #[inline] pub fn is_ty_infer(&self) -> bool { matches!(self.kind(), Infer(_)) diff --git a/compiler/rustc_typeck/src/check/fallback.rs b/compiler/rustc_typeck/src/check/fallback.rs index 8f6cdc7bb12..2866cd98758 100644 --- a/compiler/rustc_typeck/src/check/fallback.rs +++ b/compiler/rustc_typeck/src/check/fallback.rs @@ -1,4 +1,7 @@ use crate::check::FnCtxt; +use rustc_data_structures::{ + fx::FxHashMap, graph::vec_graph::VecGraph, graph::WithSuccessors, stable_set::FxHashSet, +}; use rustc_infer::infer::type_variable::Diverging; use rustc_middle::ty::{self, Ty}; @@ -8,22 +11,30 @@ impl<'tcx> FnCtxt<'_, 'tcx> { pub(super) fn type_inference_fallback(&self) -> bool { // All type checking constraints were added, try to fallback unsolved variables. self.select_obligations_where_possible(false, |_| {}); - let mut fallback_has_occurred = false; + // Check if we have any unsolved varibales. If not, no need for fallback. + let unsolved_variables = self.unsolved_variables(); + if unsolved_variables.is_empty() { + return false; + } + + let diverging_fallback = self.calculate_diverging_fallback(&unsolved_variables); + + let mut fallback_has_occurred = false; // We do fallback in two passes, to try to generate // better error messages. // The first time, we do *not* replace opaque types. - for ty in &self.unsolved_variables() { + for ty in unsolved_variables { debug!("unsolved_variable = {:?}", ty); - fallback_has_occurred |= self.fallback_if_possible(ty); + fallback_has_occurred |= self.fallback_if_possible(ty, &diverging_fallback); } - // We now see if we can make progress. This might - // cause us to unify inference variables for opaque types, - // since we may have unified some other type variables - // during the first phase of fallback. - // This means that we only replace inference variables with their underlying - // opaque types as a last resort. + // We now see if we can make progress. This might cause us to + // unify inference variables for opaque types, since we may + // have unified some other type variables during the first + // phase of fallback. This means that we only replace + // inference variables with their underlying opaque types as a + // last resort. // // In code like this: // @@ -62,36 +73,44 @@ impl<'tcx> FnCtxt<'_, 'tcx> { // // - Unconstrained floats are replaced with with `f64`. // - // - Non-numerics get replaced with `!` when `#![feature(never_type_fallback)]` - // is enabled. Otherwise, they are replaced with `()`. + // - Non-numerics may get replaced with `()` or `!`, depending on + // how they were categorized by `calculate_diverging_fallback` + // (and the setting of `#![feature(never_type_fallback)]`). + // + // Fallback becomes very dubious if we have encountered + // type-checking errors. In that case, fallback to Error. // - // Fallback becomes very dubious if we have encountered type-checking errors. - // In that case, fallback to Error. // The return value indicates whether fallback has occurred. - fn fallback_if_possible(&self, ty: Ty<'tcx>) -> bool { + fn fallback_if_possible( + &self, + ty: Ty<'tcx>, + diverging_fallback: &FxHashMap, Ty<'tcx>>, + ) -> bool { // Careful: we do NOT shallow-resolve `ty`. We know that `ty` - // is an unsolved variable, and we determine its fallback based - // solely on how it was created, not what other type variables - // it may have been unified with since then. + // is an unsolved variable, and we determine its fallback + // based solely on how it was created, not what other type + // variables it may have been unified with since then. // - // The reason this matters is that other attempts at fallback may - // (in principle) conflict with this fallback, and we wish to generate - // a type error in that case. (However, this actually isn't true right now, - // because we're only using the builtin fallback rules. This would be - // true if we were using user-supplied fallbacks. But it's still useful - // to write the code to detect bugs.) + // The reason this matters is that other attempts at fallback + // may (in principle) conflict with this fallback, and we wish + // to generate a type error in that case. (However, this + // actually isn't true right now, because we're only using the + // builtin fallback rules. This would be true if we were using + // user-supplied fallbacks. But it's still useful to write the + // code to detect bugs.) // - // (Note though that if we have a general type variable `?T` that is then unified - // with an integer type variable `?I` that ultimately never gets - // resolved to a special integral type, `?T` is not considered unsolved, - // but `?I` is. The same is true for float variables.) + // (Note though that if we have a general type variable `?T` + // that is then unified with an integer type variable `?I` + // that ultimately never gets resolved to a special integral + // type, `?T` is not considered unsolved, but `?I` is. The + // same is true for float variables.) let fallback = match ty.kind() { _ if self.is_tainted_by_errors() => self.tcx.ty_error(), ty::Infer(ty::IntVar(_)) => self.tcx.types.i32, ty::Infer(ty::FloatVar(_)) => self.tcx.types.f64, - _ => match self.type_var_diverges(ty) { - Diverging::Diverges => self.tcx.mk_diverging_default(), - Diverging::NotDiverging => return false, + _ => match diverging_fallback.get(&ty) { + Some(&fallback_ty) => fallback_ty, + None => return false, }, }; debug!("fallback_if_possible(ty={:?}): defaulting to `{:?}`", ty, fallback); @@ -105,11 +124,10 @@ impl<'tcx> FnCtxt<'_, 'tcx> { true } - /// Second round of fallback: Unconstrained type variables - /// created from the instantiation of an opaque - /// type fall back to the opaque type itself. This is a - /// somewhat incomplete attempt to manage "identity passthrough" - /// for `impl Trait` types. + /// Second round of fallback: Unconstrained type variables created + /// from the instantiation of an opaque type fall back to the + /// opaque type itself. This is a somewhat incomplete attempt to + /// manage "identity passthrough" for `impl Trait` types. /// /// For example, in this code: /// @@ -158,4 +176,195 @@ impl<'tcx> FnCtxt<'_, 'tcx> { return false; } } + + /// The "diverging fallback" system is rather complicated. This is + /// a result of our need to balance 'do the right thing' with + /// backwards compatibility. + /// + /// "Diverging" type variables are variables created when we + /// coerce a `!` type into an unbound type variable `?X`. If they + /// never wind up being constrained, the "right and natural" thing + /// is that `?X` should "fallback" to `!`. This means that e.g. an + /// expression like `Some(return)` will ultimately wind up with a + /// type like `Option` (presuming it is not assigned or + /// constrained to have some other type). + /// + /// However, the fallback used to be `()` (before the `!` type was + /// added). Moreover, there are cases where the `!` type 'leaks + /// out' from dead code into type variables that affect live + /// code. The most common case is something like this: + /// + /// ```rust + /// match foo() { + /// 22 => Default::default(), // call this type `?D` + /// _ => return, // return has type `!` + /// } // call the type of this match `?M` + /// ``` + /// + /// Here, coercing the type `!` into `?M` will create a diverging + /// type variable `?X` where `?X <: ?M`. We also have that `?D <: + /// ?M`. If `?M` winds up unconstrained, then `?X` will + /// fallback. If it falls back to `!`, then all the type variables + /// will wind up equal to `!` -- this includes the type `?D` + /// (since `!` doesn't implement `Default`, we wind up a "trait + /// not implemented" error in code like this). But since the + /// original fallback was `()`, this code used to compile with `?D + /// = ()`. This is somewhat surprising, since `Default::default()` + /// on its own would give an error because the types are + /// insufficiently constrained. + /// + /// Our solution to this dilemma is to modify diverging variables + /// so that they can *either* fallback to `!` (the default) or to + /// `()` (the backwards compatibility case). We decide which + /// fallback to use based on whether there is a coercion pattern + /// like this: + /// + /// ``` + /// ?Diverging -> ?V + /// ?NonDiverging -> ?V + /// ?V != ?NonDiverging + /// ``` + /// + /// Here `?Diverging` represents some diverging type variable and + /// `?NonDiverging` represents some non-diverging type + /// variable. `?V` can be any type variable (diverging or not), so + /// long as it is not equal to `?NonDiverging`. + /// + /// Intuitively, what we are looking for is a case where a + /// "non-diverging" type variable (like `?M` in our example above) + /// is coerced *into* some variable `?V` that would otherwise + /// fallback to `!`. In that case, we make `?V` fallback to `!`, + /// along with anything that would flow into `?V`. + /// + /// The algorithm we use: + /// * Identify all variables that are coerced *into* by a + /// diverging variable. Do this by iterating over each + /// diverging, unsolved variable and finding all variables + /// reachable from there. Call that set `D`. + /// * Walk over all unsolved, non-diverging variables, and find + /// any variable that has an edge into `D`. + fn calculate_diverging_fallback( + &self, + unsolved_variables: &[Ty<'tcx>], + ) -> FxHashMap, Ty<'tcx>> { + debug!("calculate_diverging_fallback({:?})", unsolved_variables); + + // Construct a coercion graph where an edge `A -> B` indicates + // a type variable is that is coerced + let coercion_graph = self.create_coercion_graph(); + + // Extract the unsolved type inference variable vids; note that some + // unsolved variables are integer/float variables and are excluded. + let unsolved_vids: Vec<_> = + unsolved_variables.iter().filter_map(|ty| ty.ty_vid()).collect(); + + // Find all type variables that are reachable from a diverging + // type variable. These will typically default to `!`, unless + // we find later that they are *also* reachable from some + // other type variable outside this set. + let mut roots_reachable_from_diverging = FxHashSet::default(); + let mut diverging_vids = vec![]; + let mut non_diverging_vids = vec![]; + for &unsolved_vid in &unsolved_vids { + debug!( + "calculate_diverging_fallback: unsolved_vid={:?} diverges={:?}", + unsolved_vid, + self.infcx.ty_vid_diverges(unsolved_vid) + ); + match self.infcx.ty_vid_diverges(unsolved_vid) { + Diverging::Diverges => { + diverging_vids.push(unsolved_vid); + let root_vid = self.infcx.root_var(unsolved_vid); + debug!( + "calculate_diverging_fallback: root_vid={:?} reaches {:?}", + root_vid, + coercion_graph.depth_first_search(root_vid).collect::>() + ); + roots_reachable_from_diverging + .extend(coercion_graph.depth_first_search(root_vid)); + } + Diverging::NotDiverging => { + non_diverging_vids.push(unsolved_vid); + } + } + } + debug!( + "calculate_diverging_fallback: roots_reachable_from_diverging={:?}", + roots_reachable_from_diverging, + ); + + // Find all type variables N0 that are not reachable from a + // diverging variable, and then compute the set reachable from + // N0, which we call N. These are the *non-diverging* type + // variables. (Note that this set consists of "root variables".) + let mut roots_reachable_from_non_diverging = FxHashSet::default(); + for &non_diverging_vid in &non_diverging_vids { + let root_vid = self.infcx.root_var(non_diverging_vid); + if roots_reachable_from_diverging.contains(&root_vid) { + continue; + } + roots_reachable_from_non_diverging.extend(coercion_graph.depth_first_search(root_vid)); + } + debug!( + "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}", + roots_reachable_from_non_diverging, + ); + + // For each diverging variable, figure out whether it can + // reach a member of N. If so, it falls back to `()`. Else + // `!`. + let mut diverging_fallback = FxHashMap::default(); + for &diverging_vid in &diverging_vids { + let diverging_ty = self.tcx.mk_ty_var(diverging_vid); + let root_vid = self.infcx.root_var(diverging_vid); + let can_reach_non_diverging = coercion_graph + .depth_first_search(root_vid) + .any(|n| roots_reachable_from_non_diverging.contains(&n)); + if can_reach_non_diverging { + debug!("fallback to (): {:?}", diverging_vid); + diverging_fallback.insert(diverging_ty, self.tcx.types.unit); + } else { + debug!("fallback to !: {:?}", diverging_vid); + diverging_fallback.insert(diverging_ty, self.tcx.mk_diverging_default()); + } + } + + diverging_fallback + } + + /// Returns a graph whose nodes are (unresolved) inference variables and where + /// an edge `?A -> ?B` indicates that the variable `?A` is coerced to `?B`. + fn create_coercion_graph(&self) -> VecGraph { + let pending_obligations = self.fulfillment_cx.borrow_mut().pending_obligations(); + debug!("create_coercion_graph: pending_obligations={:?}", pending_obligations); + let coercion_edges: Vec<(ty::TyVid, ty::TyVid)> = pending_obligations + .into_iter() + .filter_map(|obligation| { + // The predicates we are looking for look like `Coerce(?A -> ?B)`. + // They will have no bound variables. + obligation.predicate.kind().no_bound_vars() + }) + .filter_map(|atom| { + if let ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) = atom { + let a_vid = self.root_vid(a)?; + let b_vid = self.root_vid(b)?; + Some((a_vid, b_vid)) + } else { + return None; + }; + + let a_vid = self.root_vid(a)?; + let b_vid = self.root_vid(b)?; + Some((a_vid, b_vid)) + }) + .collect(); + debug!("create_coercion_graph: coercion_edges={:?}", coercion_edges); + let num_ty_vars = self.infcx.num_ty_vars(); + VecGraph::new(num_ty_vars, coercion_edges) + } + + /// If `ty` is an unresolved type variable, returns its root vid. + fn root_vid(&self, ty: Ty<'tcx>) -> Option { + Some(self.infcx.root_var(self.infcx.shallow_resolve(ty).ty_vid()?)) + } } -- cgit 1.4.1-3-g733a5 From ebb8ff9edfe0a908be55fc8c7852f291cc57f62a Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Mon, 23 Nov 2020 07:42:06 -0500 Subject: remove diverging type variables from fn check The comment seems incorrect. Testing revealed that the examples in question still work (as well as some variants) even without the special casing here. --- compiler/rustc_infer/src/infer/type_variable.rs | 6 ++++- compiler/rustc_typeck/src/check/check.rs | 32 +++++++------------------ 2 files changed, 13 insertions(+), 25 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_infer/src/infer/type_variable.rs b/compiler/rustc_infer/src/infer/type_variable.rs index f15268f6895..071cf6e1ea4 100644 --- a/compiler/rustc_infer/src/infer/type_variable.rs +++ b/compiler/rustc_infer/src/infer/type_variable.rs @@ -129,7 +129,11 @@ pub enum TypeVariableOriginKind { SubstitutionPlaceholder, AutoDeref, AdjustmentType, - DivergingFn, + + /// In type check, when we are type checking a function that + /// returns `-> dyn Foo`, we substitute a type variable for the + /// return type for diagnostic purposes. + DynReturnFn, LatticeVariable, } diff --git a/compiler/rustc_typeck/src/check/check.rs b/compiler/rustc_typeck/src/check/check.rs index 1fd1253e527..3b9047318d4 100644 --- a/compiler/rustc_typeck/src/check/check.rs +++ b/compiler/rustc_typeck/src/check/check.rs @@ -241,32 +241,16 @@ pub(super) fn check_fn<'a, 'tcx>( // we saw and assigning it to the expected return type. This isn't // really expected to fail, since the coercions would have failed // earlier when trying to find a LUB. - // - // However, the behavior around `!` is sort of complex. In the - // event that the `actual_return_ty` comes back as `!`, that - // indicates that the fn either does not return or "returns" only - // values of type `!`. In this case, if there is an expected - // return type that is *not* `!`, that should be ok. But if the - // return type is being inferred, we want to "fallback" to `!`: - // - // let x = move || panic!(); - // - // To allow for that, I am creating a type variable with diverging - // fallback. This was deemed ever so slightly better than unifying - // the return value with `!` because it allows for the caller to - // make more assumptions about the return type (e.g., they could do - // - // let y: Option = Some(x()); - // - // which would then cause this return type to become `u32`, not - // `!`). let coercion = fcx.ret_coercion.take().unwrap().into_inner(); let mut actual_return_ty = coercion.complete(&fcx); - if actual_return_ty.is_never() { - actual_return_ty = fcx.next_diverging_ty_var(TypeVariableOrigin { - kind: TypeVariableOriginKind::DivergingFn, - span, - }); + debug!("actual_return_ty = {:?}", actual_return_ty); + if let ty::Dynamic(..) = declared_ret_ty.kind() { + // We have special-cased the case where the function is declared + // `-> dyn Foo` and we don't actually relate it to the + // `fcx.ret_coercion`, so just substitute a type variable. + actual_return_ty = + fcx.next_ty_var(TypeVariableOrigin { kind: TypeVariableOriginKind::DynReturnFn, span }); + debug!("actual_return_ty replaced with {:?}", actual_return_ty); } fcx.demand_suptype(span, revealed_ret_ty, actual_return_ty); -- cgit 1.4.1-3-g733a5 From 1c004f2d438a33ddb6606a3c2c4d14e8340c8107 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Mon, 23 Nov 2020 07:43:33 -0500 Subject: remove reliance on "diverging" type variables Instead, we now record those type variables that are the target of a `NeverToAny` adjustment and consider those to be the "diverging" type variables. This allows us to remove the special case logic that creates a type variable for `!` in coercion. --- compiler/rustc_typeck/src/check/coercion.rs | 19 +------- compiler/rustc_typeck/src/check/fallback.rs | 57 +++++++++++++++--------- compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs | 9 ++++ compiler/rustc_typeck/src/check/inherited.rs | 7 +++ 4 files changed, 53 insertions(+), 39 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_typeck/src/check/coercion.rs b/compiler/rustc_typeck/src/check/coercion.rs index 013aecae586..746f273e69f 100644 --- a/compiler/rustc_typeck/src/check/coercion.rs +++ b/compiler/rustc_typeck/src/check/coercion.rs @@ -159,24 +159,7 @@ impl<'f, 'tcx> Coerce<'f, 'tcx> { // Coercing from `!` to any type is allowed: if a.is_never() { - // Subtle: If we are coercing from `!` to `?T`, where `?T` is an unbound - // type variable, we want `?T` to fallback to `!` if not - // otherwise constrained. An example where this arises: - // - // let _: Option = Some({ return; }); - // - // here, we would coerce from `!` to `?T`. - return if b.is_ty_var() { - // Micro-optimization: no need for this if `b` is - // already resolved in some way. - let diverging_ty = self.next_diverging_ty_var(TypeVariableOrigin { - kind: TypeVariableOriginKind::AdjustmentType, - span: self.cause.span, - }); - self.coerce_from_inference_variable(diverging_ty, b, simple(Adjust::NeverToAny)) - } else { - success(simple(Adjust::NeverToAny)(b), b, vec![]) - }; + return success(simple(Adjust::NeverToAny)(b), b, vec![]); } // Coercing *from* an unresolved inference variable means that diff --git a/compiler/rustc_typeck/src/check/fallback.rs b/compiler/rustc_typeck/src/check/fallback.rs index 2866cd98758..fff771663e9 100644 --- a/compiler/rustc_typeck/src/check/fallback.rs +++ b/compiler/rustc_typeck/src/check/fallback.rs @@ -2,7 +2,6 @@ use crate::check::FnCtxt; use rustc_data_structures::{ fx::FxHashMap, graph::vec_graph::VecGraph, graph::WithSuccessors, stable_set::FxHashSet, }; -use rustc_infer::infer::type_variable::Diverging; use rustc_middle::ty::{self, Ty}; impl<'tcx> FnCtxt<'_, 'tcx> { @@ -255,8 +254,27 @@ impl<'tcx> FnCtxt<'_, 'tcx> { // Extract the unsolved type inference variable vids; note that some // unsolved variables are integer/float variables and are excluded. - let unsolved_vids: Vec<_> = - unsolved_variables.iter().filter_map(|ty| ty.ty_vid()).collect(); + let unsolved_vids = unsolved_variables.iter().filter_map(|ty| ty.ty_vid()); + + // Compute the diverging root vids D -- that is, the root vid of + // those type variables that (a) are the target of a coercion from + // a `!` type and (b) have not yet been solved. + // + // These variables are the ones that are targets for fallback to + // either `!` or `()`. + let diverging_roots: FxHashSet = self + .diverging_type_vars + .borrow() + .iter() + .map(|&ty| self.infcx.shallow_resolve(ty)) + .filter_map(|ty| ty.ty_vid()) + .map(|vid| self.infcx.root_var(vid)) + .collect(); + debug!( + "calculate_diverging_fallback: diverging_type_vars={:?}", + self.diverging_type_vars.borrow() + ); + debug!("calculate_diverging_fallback: diverging_roots={:?}", diverging_roots); // Find all type variables that are reachable from a diverging // type variable. These will typically default to `!`, unless @@ -265,27 +283,24 @@ impl<'tcx> FnCtxt<'_, 'tcx> { let mut roots_reachable_from_diverging = FxHashSet::default(); let mut diverging_vids = vec![]; let mut non_diverging_vids = vec![]; - for &unsolved_vid in &unsolved_vids { + for unsolved_vid in unsolved_vids { + let root_vid = self.infcx.root_var(unsolved_vid); debug!( - "calculate_diverging_fallback: unsolved_vid={:?} diverges={:?}", + "calculate_diverging_fallback: unsolved_vid={:?} root_vid={:?} diverges={:?}", unsolved_vid, - self.infcx.ty_vid_diverges(unsolved_vid) + root_vid, + diverging_roots.contains(&root_vid), ); - match self.infcx.ty_vid_diverges(unsolved_vid) { - Diverging::Diverges => { - diverging_vids.push(unsolved_vid); - let root_vid = self.infcx.root_var(unsolved_vid); - debug!( - "calculate_diverging_fallback: root_vid={:?} reaches {:?}", - root_vid, - coercion_graph.depth_first_search(root_vid).collect::>() - ); - roots_reachable_from_diverging - .extend(coercion_graph.depth_first_search(root_vid)); - } - Diverging::NotDiverging => { - non_diverging_vids.push(unsolved_vid); - } + if diverging_roots.contains(&root_vid) { + diverging_vids.push(unsolved_vid); + debug!( + "calculate_diverging_fallback: root_vid={:?} reaches {:?}", + root_vid, + coercion_graph.depth_first_search(root_vid).collect::>() + ); + roots_reachable_from_diverging.extend(coercion_graph.depth_first_search(root_vid)); + } else { + non_diverging_vids.push(unsolved_vid); } } debug!( diff --git a/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs b/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs index ed01dae59f6..562d05d3ef9 100644 --- a/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs +++ b/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs @@ -286,6 +286,15 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { return; } + for a in &adj { + if let Adjust::NeverToAny = a.kind { + if a.target.is_ty_var() { + self.diverging_type_vars.borrow_mut().insert(a.target); + debug!("apply_adjustments: adding `{:?}` as diverging type var", a.target); + } + } + } + let autoborrow_mut = adj.iter().any(|adj| { matches!( adj, diff --git a/compiler/rustc_typeck/src/check/inherited.rs b/compiler/rustc_typeck/src/check/inherited.rs index 6006c8f7513..f7552c1f4eb 100644 --- a/compiler/rustc_typeck/src/check/inherited.rs +++ b/compiler/rustc_typeck/src/check/inherited.rs @@ -1,6 +1,7 @@ use super::callee::DeferredCallResolution; use super::MaybeInProgressTables; +use rustc_data_structures::fx::FxHashSet; use rustc_hir as hir; use rustc_hir::def_id::{DefIdMap, LocalDefId}; use rustc_hir::HirIdMap; @@ -56,6 +57,11 @@ pub struct Inherited<'a, 'tcx> { pub(super) constness: hir::Constness, pub(super) body_id: Option, + + /// Whenever we introduce an adjustment from `!` into a type variable, + /// we record that type variable here. This is later used to inform + /// fallback. See the `fallback` module for details. + pub(super) diverging_type_vars: RefCell>>, } impl<'a, 'tcx> Deref for Inherited<'a, 'tcx> { @@ -121,6 +127,7 @@ impl Inherited<'a, 'tcx> { deferred_call_resolutions: RefCell::new(Default::default()), deferred_cast_checks: RefCell::new(Vec::new()), deferred_generator_interiors: RefCell::new(Vec::new()), + diverging_type_vars: RefCell::new(Default::default()), constness, body_id, } -- cgit 1.4.1-3-g733a5 From bc2ece2a8d14b1ec6f2e92b316e1a7c4fd216c9a Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Mon, 23 Nov 2020 09:06:37 -0500 Subject: stop categorizing inference variables as diverging when created Instead, we now rely on the code that looks for a NeverToAny adjustment. --- compiler/rustc_infer/src/infer/combine.rs | 15 +++++----- compiler/rustc_infer/src/infer/mod.rs | 36 ++++-------------------- compiler/rustc_infer/src/infer/nll_relate/mod.rs | 4 +-- compiler/rustc_infer/src/infer/type_variable.rs | 23 ++------------- compiler/rustc_typeck/src/check/expr.rs | 2 +- 5 files changed, 17 insertions(+), 63 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_infer/src/infer/combine.rs b/compiler/rustc_infer/src/infer/combine.rs index a0ee212bed0..8dd7e6af257 100644 --- a/compiler/rustc_infer/src/infer/combine.rs +++ b/compiler/rustc_infer/src/infer/combine.rs @@ -22,6 +22,7 @@ // is also useful to track which value is the "expected" value in // terms of error reporting. +use super::equate::Equate; use super::glb::Glb; use super::lub::Lub; use super::sub::Sub; @@ -29,7 +30,6 @@ use super::type_variable::TypeVariableValue; use super::unify_key::replace_if_possible; use super::unify_key::{ConstVarValue, ConstVariableValue}; use super::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; -use super::{equate::Equate, type_variable::Diverging}; use super::{InferCtxt, MiscVariable, TypeTrace}; use crate::traits::{Obligation, PredicateObligations}; @@ -645,7 +645,7 @@ impl TypeRelation<'tcx> for Generalizer<'_, 'tcx> { .inner .borrow_mut() .type_variables() - .new_var(self.for_universe, Diverging::NotDiverging, origin); + .new_var(self.for_universe, origin); let u = self.tcx().mk_ty_var(new_var_id); // Record that we replaced `vid` with `new_var_id` as part of a generalization @@ -885,11 +885,12 @@ impl TypeRelation<'tcx> for ConstInferUnifier<'_, 'tcx> { let origin = *self.infcx.inner.borrow_mut().type_variables().var_origin(vid); - let new_var_id = self.infcx.inner.borrow_mut().type_variables().new_var( - self.for_universe, - Diverging::NotDiverging, - origin, - ); + let new_var_id = self + .infcx + .inner + .borrow_mut() + .type_variables() + .new_var(self.for_universe, origin); let u = self.tcx().mk_ty_var(new_var_id); debug!( "ConstInferUnifier: replacing original vid={:?} with new={:?}", diff --git a/compiler/rustc_infer/src/infer/mod.rs b/compiler/rustc_infer/src/infer/mod.rs index 7302aa13cc4..73eb0d0c782 100644 --- a/compiler/rustc_infer/src/infer/mod.rs +++ b/compiler/rustc_infer/src/infer/mod.rs @@ -46,7 +46,7 @@ use self::region_constraints::{GenericKind, RegionConstraintData, VarInfos, Veri use self::region_constraints::{ RegionConstraintCollector, RegionConstraintStorage, RegionSnapshot, }; -use self::type_variable::{Diverging, TypeVariableOrigin, TypeVariableOriginKind}; +use self::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; pub mod at; pub mod canonical; @@ -701,23 +701,6 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { t.fold_with(&mut self.freshener()) } - /// Returns whether `ty` is a diverging type variable or not. - /// (If `ty` is not a type variable at all, returns not diverging.) - /// - /// No attempt is made to resolve `ty`. - pub fn type_var_diverges(&'a self, ty: Ty<'_>) -> Diverging { - match *ty.kind() { - ty::Infer(ty::TyVar(vid)) => self.ty_vid_diverges(vid), - _ => Diverging::NotDiverging, - } - } - - /// Returns true if the type inference variable `vid` was created - /// as a diverging type variable. No attempt is made to resolve `vid`. - pub fn ty_vid_diverges(&'a self, vid: ty::TyVid) -> Diverging { - self.inner.borrow_mut().type_variables().var_diverges(vid) - } - /// Returns the origin of the type variable identified by `vid`, or `None` /// if this is not a type variable. /// @@ -1081,12 +1064,12 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { self.inner.borrow_mut().type_variables().num_vars() } - pub fn next_ty_var_id(&self, diverging: Diverging, origin: TypeVariableOrigin) -> TyVid { - self.inner.borrow_mut().type_variables().new_var(self.universe(), diverging, origin) + pub fn next_ty_var_id(&self, origin: TypeVariableOrigin) -> TyVid { + self.inner.borrow_mut().type_variables().new_var(self.universe(), origin) } pub fn next_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> { - self.tcx.mk_ty_var(self.next_ty_var_id(Diverging::NotDiverging, origin)) + self.tcx.mk_ty_var(self.next_ty_var_id(origin)) } pub fn next_ty_var_in_universe( @@ -1094,18 +1077,10 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { origin: TypeVariableOrigin, universe: ty::UniverseIndex, ) -> Ty<'tcx> { - let vid = self.inner.borrow_mut().type_variables().new_var( - universe, - Diverging::NotDiverging, - origin, - ); + let vid = self.inner.borrow_mut().type_variables().new_var(universe, origin); self.tcx.mk_ty_var(vid) } - pub fn next_diverging_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> { - self.tcx.mk_ty_var(self.next_ty_var_id(Diverging::Diverges, origin)) - } - pub fn next_const_var( &self, ty: Ty<'tcx>, @@ -1217,7 +1192,6 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { // as the substitutions for the default, `(T, U)`. let ty_var_id = self.inner.borrow_mut().type_variables().new_var( self.universe(), - Diverging::NotDiverging, TypeVariableOrigin { kind: TypeVariableOriginKind::TypeParameterDefinition( param.name, diff --git a/compiler/rustc_infer/src/infer/nll_relate/mod.rs b/compiler/rustc_infer/src/infer/nll_relate/mod.rs index e88c6608aca..73d74584a5e 100644 --- a/compiler/rustc_infer/src/infer/nll_relate/mod.rs +++ b/compiler/rustc_infer/src/infer/nll_relate/mod.rs @@ -22,7 +22,6 @@ //! constituents) use crate::infer::combine::ConstEquateRelation; -use crate::infer::type_variable::Diverging; use crate::infer::InferCtxt; use crate::infer::{ConstVarValue, ConstVariableValue}; use rustc_data_structures::fx::FxHashMap; @@ -927,8 +926,7 @@ where // Replacing with a new variable in the universe `self.universe`, // it will be unified later with the original type variable in // the universe `_universe`. - let new_var_id = - variables.new_var(self.universe, Diverging::NotDiverging, origin); + let new_var_id = variables.new_var(self.universe, origin); let u = self.tcx().mk_ty_var(new_var_id); debug!("generalize: replacing original vid={:?} with new={:?}", vid, u); diff --git a/compiler/rustc_infer/src/infer/type_variable.rs b/compiler/rustc_infer/src/infer/type_variable.rs index 071cf6e1ea4..0e832685310 100644 --- a/compiler/rustc_infer/src/infer/type_variable.rs +++ b/compiler/rustc_infer/src/infer/type_variable.rs @@ -139,13 +139,6 @@ pub enum TypeVariableOriginKind { pub(crate) struct TypeVariableData { origin: TypeVariableOrigin, - diverging: Diverging, -} - -#[derive(Copy, Clone, Debug)] -pub enum Diverging { - NotDiverging, - Diverges, } #[derive(Copy, Clone, Debug)] @@ -195,14 +188,6 @@ impl<'tcx> TypeVariableStorage<'tcx> { } impl<'tcx> TypeVariableTable<'_, 'tcx> { - /// Returns the diverges flag given when `vid` was created. - /// - /// Note that this function does not return care whether - /// `vid` has been unified with something else or not. - pub fn var_diverges(&self, vid: ty::TyVid) -> Diverging { - self.storage.values.get(vid.index()).diverging - } - /// Returns the origin that was given when `vid` was created. /// /// Note that this function does not return care whether @@ -264,7 +249,6 @@ impl<'tcx> TypeVariableTable<'_, 'tcx> { pub fn new_var( &mut self, universe: ty::UniverseIndex, - diverging: Diverging, origin: TypeVariableOrigin, ) -> ty::TyVid { let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe }); @@ -272,13 +256,10 @@ impl<'tcx> TypeVariableTable<'_, 'tcx> { let sub_key = self.sub_relations().new_key(()); assert_eq!(eq_key.vid, sub_key); - let index = self.values().push(TypeVariableData { origin, diverging }); + let index = self.values().push(TypeVariableData { origin }); assert_eq!(eq_key.vid.as_u32(), index as u32); - debug!( - "new_var(index={:?}, universe={:?}, diverging={:?}, origin={:?}", - eq_key.vid, universe, diverging, origin, - ); + debug!("new_var(index={:?}, universe={:?}, origin={:?}", eq_key.vid, universe, origin,); eq_key.vid } diff --git a/compiler/rustc_typeck/src/check/expr.rs b/compiler/rustc_typeck/src/check/expr.rs index 917adf0e2b9..88ce92c3ffe 100644 --- a/compiler/rustc_typeck/src/check/expr.rs +++ b/compiler/rustc_typeck/src/check/expr.rs @@ -77,7 +77,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { !self.typeck_results.borrow().adjustments().contains_key(expr.hir_id), "expression with never type wound up being adjusted" ); - let adj_ty = self.next_diverging_ty_var(TypeVariableOrigin { + let adj_ty = self.next_ty_var(TypeVariableOrigin { kind: TypeVariableOriginKind::AdjustmentType, span: expr.span, }); -- cgit 1.4.1-3-g733a5 From 59dc2013e27adc5a251e81317331890d4015cdf0 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Mon, 23 Nov 2020 10:21:54 -0500 Subject: optimization: use a single DepthFirstSearch instead of hashsets Extend the `DepthFirstSearch` iterator so that it can be re-used and extended with add'l start nodes. Then replace the FxHashSets of nodes we were using in the fallback analysis with a single iterator. This way we won't re-walk portions of the graph that are reached more than once, and we also do less allocation etc. --- compiler/rustc_typeck/src/check/fallback.rs | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) (limited to 'compiler') diff --git a/compiler/rustc_typeck/src/check/fallback.rs b/compiler/rustc_typeck/src/check/fallback.rs index fff771663e9..508cea2845a 100644 --- a/compiler/rustc_typeck/src/check/fallback.rs +++ b/compiler/rustc_typeck/src/check/fallback.rs @@ -1,6 +1,9 @@ use crate::check::FnCtxt; use rustc_data_structures::{ - fx::FxHashMap, graph::vec_graph::VecGraph, graph::WithSuccessors, stable_set::FxHashSet, + fx::FxHashMap, + graph::WithSuccessors, + graph::{iterate::DepthFirstSearch, vec_graph::VecGraph}, + stable_set::FxHashSet, }; use rustc_middle::ty::{self, Ty}; @@ -280,7 +283,7 @@ impl<'tcx> FnCtxt<'_, 'tcx> { // type variable. These will typically default to `!`, unless // we find later that they are *also* reachable from some // other type variable outside this set. - let mut roots_reachable_from_diverging = FxHashSet::default(); + let mut roots_reachable_from_diverging = DepthFirstSearch::new(&coercion_graph); let mut diverging_vids = vec![]; let mut non_diverging_vids = vec![]; for unsolved_vid in unsolved_vids { @@ -293,16 +296,21 @@ impl<'tcx> FnCtxt<'_, 'tcx> { ); if diverging_roots.contains(&root_vid) { diverging_vids.push(unsolved_vid); + roots_reachable_from_diverging.push_start_node(root_vid); + debug!( "calculate_diverging_fallback: root_vid={:?} reaches {:?}", root_vid, coercion_graph.depth_first_search(root_vid).collect::>() ); - roots_reachable_from_diverging.extend(coercion_graph.depth_first_search(root_vid)); + + // drain the iterator to visit all nodes reachable from this node + roots_reachable_from_diverging.complete_search(); } else { non_diverging_vids.push(unsolved_vid); } } + debug!( "calculate_diverging_fallback: roots_reachable_from_diverging={:?}", roots_reachable_from_diverging, @@ -312,13 +320,14 @@ impl<'tcx> FnCtxt<'_, 'tcx> { // diverging variable, and then compute the set reachable from // N0, which we call N. These are the *non-diverging* type // variables. (Note that this set consists of "root variables".) - let mut roots_reachable_from_non_diverging = FxHashSet::default(); + let mut roots_reachable_from_non_diverging = DepthFirstSearch::new(&coercion_graph); for &non_diverging_vid in &non_diverging_vids { let root_vid = self.infcx.root_var(non_diverging_vid); - if roots_reachable_from_diverging.contains(&root_vid) { + if roots_reachable_from_diverging.visited(root_vid) { continue; } - roots_reachable_from_non_diverging.extend(coercion_graph.depth_first_search(root_vid)); + roots_reachable_from_non_diverging.push_start_node(root_vid); + roots_reachable_from_non_diverging.complete_search(); } debug!( "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}", @@ -334,7 +343,7 @@ impl<'tcx> FnCtxt<'_, 'tcx> { let root_vid = self.infcx.root_var(diverging_vid); let can_reach_non_diverging = coercion_graph .depth_first_search(root_vid) - .any(|n| roots_reachable_from_non_diverging.contains(&n)); + .any(|n| roots_reachable_from_non_diverging.visited(n)); if can_reach_non_diverging { debug!("fallback to (): {:?}", diverging_vid); diverging_fallback.insert(diverging_ty, self.tcx.types.unit); -- cgit 1.4.1-3-g733a5 From 078e3fd4bab601f1f8ecfdc1e7fdb6103e9e2b6c Mon Sep 17 00:00:00 2001 From: Mark Rousskov Date: Mon, 26 Apr 2021 19:00:55 -0400 Subject: Add another case of fallback to () avoid breakage This adds src/test/ui/never_type/fallback-closure-ret.rs as a test case which showcases the failure mode fixed by this commit. --- compiler/rustc_infer/src/traits/engine.rs | 3 + compiler/rustc_middle/src/ty/mod.rs | 13 ++++ .../src/traits/chalk_fulfill.rs | 15 +++- .../rustc_trait_selection/src/traits/fulfill.rs | 13 ++++ compiler/rustc_trait_selection/src/traits/mod.rs | 1 + .../src/traits/relationships.rs | 69 ++++++++++++++++++ compiler/rustc_typeck/src/check/fallback.rs | 81 ++++++++++++++++++++-- src/test/ui/never_type/fallback-closure-ret.rs | 23 ++++++ src/test/ui/never_type/fallback-closure-wrap.rs | 30 ++++++++ 9 files changed, 239 insertions(+), 9 deletions(-) create mode 100644 compiler/rustc_trait_selection/src/traits/relationships.rs create mode 100644 src/test/ui/never_type/fallback-closure-ret.rs create mode 100644 src/test/ui/never_type/fallback-closure-wrap.rs (limited to 'compiler') diff --git a/compiler/rustc_infer/src/traits/engine.rs b/compiler/rustc_infer/src/traits/engine.rs index 42333dc29bc..a12f7dc759c 100644 --- a/compiler/rustc_infer/src/traits/engine.rs +++ b/compiler/rustc_infer/src/traits/engine.rs @@ -1,5 +1,6 @@ use crate::infer::InferCtxt; use crate::traits::Obligation; +use rustc_data_structures::fx::FxHashMap; use rustc_hir as hir; use rustc_hir::def_id::DefId; use rustc_middle::ty::{self, ToPredicate, Ty, WithConstness}; @@ -73,6 +74,8 @@ pub trait TraitEngine<'tcx>: 'tcx { } fn pending_obligations(&self) -> Vec>; + + fn relationships(&mut self) -> &mut FxHashMap; } pub trait TraitEngineExt<'tcx> { diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs index 777c6035be8..cc81ddbcc01 100644 --- a/compiler/rustc_middle/src/ty/mod.rs +++ b/compiler/rustc_middle/src/ty/mod.rs @@ -2090,3 +2090,16 @@ impl<'tcx> fmt::Debug for SymbolName<'tcx> { fmt::Display::fmt(&self.name, fmt) } } + +#[derive(Debug, Default, Copy, Clone)] +pub struct FoundRelationships { + /// This is true if we identified that this Ty (`?T`) is found in a `?T: Foo` + /// obligation, where: + /// + /// * `Foo` is not `Sized` + /// * `(): Foo` may be satisfied + pub self_in_trait: bool, + /// This is true if we identified that this Ty (`?T`) is found in a `<_ as + /// _>::AssocType = ?T` + pub output: bool, +} diff --git a/compiler/rustc_trait_selection/src/traits/chalk_fulfill.rs b/compiler/rustc_trait_selection/src/traits/chalk_fulfill.rs index 9c962d30ce0..ec62ee40068 100644 --- a/compiler/rustc_trait_selection/src/traits/chalk_fulfill.rs +++ b/compiler/rustc_trait_selection/src/traits/chalk_fulfill.rs @@ -7,16 +7,21 @@ use crate::traits::{ ChalkEnvironmentAndGoal, FulfillmentError, FulfillmentErrorCode, ObligationCause, PredicateObligation, SelectionError, TraitEngine, }; -use rustc_data_structures::fx::FxIndexSet; +use rustc_data_structures::fx::{FxHashMap, FxIndexSet}; use rustc_middle::ty::{self, Ty}; pub struct FulfillmentContext<'tcx> { obligations: FxIndexSet>, + + relationships: FxHashMap, } impl FulfillmentContext<'tcx> { crate fn new() -> Self { - FulfillmentContext { obligations: FxIndexSet::default() } + FulfillmentContext { + obligations: FxIndexSet::default(), + relationships: FxHashMap::default(), + } } } @@ -39,6 +44,8 @@ impl TraitEngine<'tcx> for FulfillmentContext<'tcx> { assert!(!infcx.is_in_snapshot()); let obligation = infcx.resolve_vars_if_possible(obligation); + super::relationships::update(self, infcx, &obligation); + self.obligations.insert(obligation); } @@ -146,4 +153,8 @@ impl TraitEngine<'tcx> for FulfillmentContext<'tcx> { fn pending_obligations(&self) -> Vec> { self.obligations.iter().cloned().collect() } + + fn relationships(&mut self) -> &mut FxHashMap { + &mut self.relationships + } } diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs index b376f429292..61462f23886 100644 --- a/compiler/rustc_trait_selection/src/traits/fulfill.rs +++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs @@ -1,4 +1,5 @@ use crate::infer::{InferCtxt, TyOrConstInferVar}; +use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::obligation_forest::ProcessResult; use rustc_data_structures::obligation_forest::{Error, ForestObligation, Outcome}; use rustc_data_structures::obligation_forest::{ObligationForest, ObligationProcessor}; @@ -53,6 +54,9 @@ pub struct FulfillmentContext<'tcx> { // A list of all obligations that have been registered with this // fulfillment context. predicates: ObligationForest>, + + relationships: FxHashMap, + // Should this fulfillment context register type-lives-for-region // obligations on its parent infcx? In some cases, region // obligations are either already known to hold (normalization) or @@ -97,6 +101,7 @@ impl<'a, 'tcx> FulfillmentContext<'tcx> { pub fn new() -> FulfillmentContext<'tcx> { FulfillmentContext { predicates: ObligationForest::new(), + relationships: FxHashMap::default(), register_region_obligations: true, usable_in_snapshot: false, } @@ -105,6 +110,7 @@ impl<'a, 'tcx> FulfillmentContext<'tcx> { pub fn new_in_snapshot() -> FulfillmentContext<'tcx> { FulfillmentContext { predicates: ObligationForest::new(), + relationships: FxHashMap::default(), register_region_obligations: true, usable_in_snapshot: true, } @@ -113,6 +119,7 @@ impl<'a, 'tcx> FulfillmentContext<'tcx> { pub fn new_ignoring_regions() -> FulfillmentContext<'tcx> { FulfillmentContext { predicates: ObligationForest::new(), + relationships: FxHashMap::default(), register_region_obligations: false, usable_in_snapshot: false, } @@ -210,6 +217,8 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> { assert!(!infcx.is_in_snapshot() || self.usable_in_snapshot); + super::relationships::update(self, infcx, &obligation); + self.predicates .register_obligation(PendingPredicateObligation { obligation, stalled_on: vec![] }); } @@ -265,6 +274,10 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> { fn pending_obligations(&self) -> Vec> { self.predicates.map_pending_obligations(|o| o.obligation.clone()) } + + fn relationships(&mut self) -> &mut FxHashMap { + &mut self.relationships + } } struct FulfillProcessor<'a, 'b, 'tcx> { diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs index ef208c44471..df2422048b9 100644 --- a/compiler/rustc_trait_selection/src/traits/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/mod.rs @@ -15,6 +15,7 @@ mod object_safety; mod on_unimplemented; mod project; pub mod query; +pub(crate) mod relationships; mod select; mod specialize; mod structural_match; diff --git a/compiler/rustc_trait_selection/src/traits/relationships.rs b/compiler/rustc_trait_selection/src/traits/relationships.rs new file mode 100644 index 00000000000..7751dd84f4c --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/relationships.rs @@ -0,0 +1,69 @@ +use crate::infer::InferCtxt; +use crate::traits::query::evaluate_obligation::InferCtxtExt; +use crate::traits::{ObligationCause, PredicateObligation}; +use rustc_infer::traits::TraitEngine; +use rustc_middle::ty::{self, ToPredicate}; + +pub(crate) fn update<'tcx, T>( + engine: &mut T, + infcx: &InferCtxt<'_, 'tcx>, + obligation: &PredicateObligation<'tcx>, +) where + T: TraitEngine<'tcx>, +{ + // (*) binder skipped + if let ty::PredicateKind::Trait(predicate) = obligation.predicate.kind().skip_binder() { + if let Some(ty) = + infcx.shallow_resolve(predicate.self_ty()).ty_vid().map(|t| infcx.root_var(t)) + { + if infcx + .tcx + .lang_items() + .sized_trait() + .map_or(false, |st| st != predicate.trait_ref.def_id) + { + let new_self_ty = infcx.tcx.types.unit; + + let trait_ref = ty::TraitRef { + substs: infcx + .tcx + .mk_substs_trait(new_self_ty, &predicate.trait_ref.substs[1..]), + ..predicate.trait_ref + }; + + // Then contstruct a new obligation with Self = () added + // to the ParamEnv, and see if it holds. + let o = rustc_infer::traits::Obligation::new( + ObligationCause::dummy(), + obligation.param_env, + obligation + .predicate + .kind() + .map_bound(|_| { + // (*) binder moved here + ty::PredicateKind::Trait(ty::TraitPredicate { + trait_ref, + constness: predicate.constness, + }) + }) + .to_predicate(infcx.tcx), + ); + // Don't report overflow errors. Otherwise equivalent to may_hold. + if let Ok(result) = infcx.probe(|_| infcx.evaluate_obligation(&o)) { + if result.may_apply() { + engine.relationships().entry(ty).or_default().self_in_trait = true; + } + } + } + } + } + + if let ty::PredicateKind::Projection(predicate) = obligation.predicate.kind().skip_binder() { + // If the projection predicate (Foo::Bar == X) has X as a non-TyVid, + // we need to make it into one. + if let Some(vid) = predicate.ty.ty_vid() { + debug!("relationship: {:?}.output = true", vid); + engine.relationships().entry(vid).or_default().output = true; + } + } +} diff --git a/compiler/rustc_typeck/src/check/fallback.rs b/compiler/rustc_typeck/src/check/fallback.rs index 508cea2845a..296e45337ed 100644 --- a/compiler/rustc_typeck/src/check/fallback.rs +++ b/compiler/rustc_typeck/src/check/fallback.rs @@ -11,9 +11,19 @@ impl<'tcx> FnCtxt<'_, 'tcx> { /// Performs type inference fallback, returning true if any fallback /// occurs. pub(super) fn type_inference_fallback(&self) -> bool { + debug!( + "type-inference-fallback start obligations: {:#?}", + self.fulfillment_cx.borrow_mut().pending_obligations() + ); + // All type checking constraints were added, try to fallback unsolved variables. self.select_obligations_where_possible(false, |_| {}); + debug!( + "type-inference-fallback post selection obligations: {:#?}", + self.fulfillment_cx.borrow_mut().pending_obligations() + ); + // Check if we have any unsolved varibales. If not, no need for fallback. let unsolved_variables = self.unsolved_variables(); if unsolved_variables.is_empty() { @@ -251,6 +261,8 @@ impl<'tcx> FnCtxt<'_, 'tcx> { ) -> FxHashMap, Ty<'tcx>> { debug!("calculate_diverging_fallback({:?})", unsolved_variables); + let relationships = self.fulfillment_cx.borrow_mut().relationships().clone(); + // Construct a coercion graph where an edge `A -> B` indicates // a type variable is that is coerced let coercion_graph = self.create_coercion_graph(); @@ -334,21 +346,63 @@ impl<'tcx> FnCtxt<'_, 'tcx> { roots_reachable_from_non_diverging, ); + debug!("inherited: {:#?}", self.inh.fulfillment_cx.borrow_mut().pending_obligations()); + debug!("obligations: {:#?}", self.fulfillment_cx.borrow_mut().pending_obligations()); + debug!("relationships: {:#?}", relationships); + // For each diverging variable, figure out whether it can // reach a member of N. If so, it falls back to `()`. Else // `!`. let mut diverging_fallback = FxHashMap::default(); + diverging_fallback.reserve(diverging_vids.len()); for &diverging_vid in &diverging_vids { let diverging_ty = self.tcx.mk_ty_var(diverging_vid); let root_vid = self.infcx.root_var(diverging_vid); let can_reach_non_diverging = coercion_graph .depth_first_search(root_vid) .any(|n| roots_reachable_from_non_diverging.visited(n)); - if can_reach_non_diverging { - debug!("fallback to (): {:?}", diverging_vid); + + let mut relationship = ty::FoundRelationships { self_in_trait: false, output: false }; + + for (vid, rel) in relationships.iter() { + if self.infcx.root_var(*vid) == root_vid { + relationship.self_in_trait |= rel.self_in_trait; + relationship.output |= rel.output; + } + } + + if relationship.self_in_trait && relationship.output { + // This case falls back to () to ensure that the code pattern in + // src/test/ui/never_type/fallback-closure-ret.rs continues to + // compile when never_type_fallback is enabled. + // + // This rule is not readily explainable from first principles, + // but is rather intended as a patchwork fix to ensure code + // which compiles before the stabilization of never type + // fallback continues to work. + // + // Typically this pattern is encountered in a function taking a + // closure as a parameter, where the return type of that closure + // (checked by `relationship.output`) is expected to implement + // some trait (checked by `relationship.self_in_trait`). This + // can come up in non-closure cases too, so we do not limit this + // rule to specifically `FnOnce`. + // + // When the closure's body is something like `panic!()`, the + // return type would normally be inferred to `!`. However, it + // needs to fall back to `()` in order to still compile, as the + // trait is specifically implemented for `()` but not `!`. + // + // For details on the requirements for these relationships to be + // set, see the relationship finding module in + // compiler/rustc_trait_selection/src/traits/relationships.rs. + debug!("fallback to () - found trait and projection: {:?}", diverging_vid); + diverging_fallback.insert(diverging_ty, self.tcx.types.unit); + } else if can_reach_non_diverging { + debug!("fallback to () - reached non-diverging: {:?}", diverging_vid); diverging_fallback.insert(diverging_ty, self.tcx.types.unit); } else { - debug!("fallback to !: {:?}", diverging_vid); + debug!("fallback to ! - all diverging: {:?}", diverging_vid); diverging_fallback.insert(diverging_ty, self.tcx.mk_diverging_default()); } } @@ -369,10 +423,23 @@ impl<'tcx> FnCtxt<'_, 'tcx> { obligation.predicate.kind().no_bound_vars() }) .filter_map(|atom| { - if let ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) = atom { - let a_vid = self.root_vid(a)?; - let b_vid = self.root_vid(b)?; - Some((a_vid, b_vid)) + // We consider both subtyping and coercion to imply 'flow' from + // some position in the code `a` to a different position `b`. + // This is then used to determine which variables interact with + // live code, and as such must fall back to `()` to preserve + // soundness. + // + // In practice currently the two ways that this happens is + // coercion and subtyping. + let (a, b) = if let ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) = atom { + (a, b) + } else if let ty::PredicateKind::Subtype(ty::SubtypePredicate { + a_is_expected: _, + a, + b, + }) = atom + { + (a, b) } else { return None; }; diff --git a/src/test/ui/never_type/fallback-closure-ret.rs b/src/test/ui/never_type/fallback-closure-ret.rs new file mode 100644 index 00000000000..5c8ce48cbb0 --- /dev/null +++ b/src/test/ui/never_type/fallback-closure-ret.rs @@ -0,0 +1,23 @@ +// This test verifies that never type fallback preserves the following code in a +// compiling state. This pattern is fairly common in the wild, notably seen in +// wasmtime v0.16. Typically this is some closure wrapper that expects a +// collection of 'known' signatures, and -> ! is not included in that set. +// +// This test is specifically targeted by the unit type fallback when +// encountering a set of obligations like `?T: Foo` and `Trait::Projection = +// ?T`. In the code below, these are `R: Bar` and `Fn::Output = R`. +// +// revisions: nofallback fallback +// check-pass + +#![cfg_attr(fallback, feature(never_type_fallback))] + +trait Bar { } +impl Bar for () { } +impl Bar for u32 { } + +fn foo(_: impl Fn() -> R) {} + +fn main() { + foo(|| panic!()); +} diff --git a/src/test/ui/never_type/fallback-closure-wrap.rs b/src/test/ui/never_type/fallback-closure-wrap.rs new file mode 100644 index 00000000000..af0577ac060 --- /dev/null +++ b/src/test/ui/never_type/fallback-closure-wrap.rs @@ -0,0 +1,30 @@ +// This is a minified example from Crater breakage observed when attempting to +// stabilize never type, nstoddard/webgl-gui @ 22f0169f. +// +// This particular test case currently fails as the inference to `()` rather +// than `!` happens as a result of an `as` cast, which is not currently tracked. +// Crater did not find many cases of this occuring, but it is included for +// awareness. +// +// revisions: nofallback fallback +//[nofallback] check-pass +//[fallback] check-fail + +#![cfg_attr(fallback, feature(never_type_fallback))] + +use std::marker::PhantomData; + +fn main() { + let error = Closure::wrap(Box::new(move || { + //[fallback]~^ ERROR type mismatch resolving + panic!("Can't connect to server."); + }) as Box); +} + +struct Closure(PhantomData); + +impl Closure { + fn wrap(data: Box) -> Closure { + todo!() + } +} -- cgit 1.4.1-3-g733a5