Auto merge of #88804 - Mark-Simulacrum:never-algo-v2, r=nikomatsakis,jackh726

Revise never type fallback algorithm

This is a rebase of https://github.com/rust-lang/rust/pull/84573, but dropping the stabilization of never type (and the accompanying large test diff).

Each commit builds & has tests updated alongside it, and could be reviewed in a more or less standalone fashion. But it may make more sense to review the PR as a whole, I'm not sure. It should be noted that tests being updated isn't really a good indicator of final behavior -- never_type_fallback is not enabled by default in this PR, so we can't really see the full effects of the commits here.

This combines the work by Niko, which is [documented in this gist](https://gist.github.com/nikomatsakis/7a07b265dc12f5c3b3bd0422018fa660), with some additional rules largely derived to target specific known patterns that regress with the algorithm solely derived by Niko. We build these from an intuition that:

* In general, fallback to `()` is *sound* in all cases
* But, in general, we *prefer* fallback to `!` as it accepts more code, particularly that written to intentionally use `!` (e.g., Result's with a Infallible/! variant).

When evaluating Niko's proposed algorithm, we find that there are certain cases where fallback to `!` leads to compilation failures in real-world code, and fallback to `()` fixes those errors. In order to allow for stabilization, we need to fix a good portion of these patterns.

The final rule set this PR proposes is that, by default, we fallback from `?T` to `!`, with the following exceptions:

1. `?T: Foo` and `Bar::Baz = ?T` and `(): Foo`, then fallback to `()`
2. Per [Niko's algorithm](https://gist.github.com/nikomatsakis/7a07b265dc12f5c3b3bd0422018fa660#proposal-fallback-chooses-between--and--based-on-the-coercion-graph), the "live" `?T` also fallback to `()`.

The first rule is necessary to address a fairly common pattern which boils down to something like the snippet below. Without rule 1, we do not see the closure's return type as needing a () fallback, which leads to compilation failure.

```rust
#![feature(never_type_fallback)]

trait Bar { }
impl Bar for () {  }
impl Bar for u32 {  }

fn foo<R: Bar>(_: impl Fn() -> R) {}

fn main() {
    foo(|| panic!());
}
```

r? `@jackh726`

5 files changed, 29 insertions, 57 deletions

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 43d3730c049..632e792bbd1 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;
@@ -702,17 +702,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.inner.borrow_mut().type_variables().var_diverges(vid),
-            _ => Diverging::NotDiverging,
-        }
-    }
-
     /// Returns the origin of the type variable identified by `vid`, or `None`
     /// if this is not a type variable.
     ///
@@ -1071,12 +1060,17 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         })
     }
 
-    pub fn next_ty_var_id(&self, diverging: Diverging, origin: TypeVariableOrigin) -> TyVid {
-        self.inner.borrow_mut().type_variables().new_var(self.universe(), diverging, origin)
+    /// 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, 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(
@@ -1084,18 +1078,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>,
@@ -1207,7 +1193,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 f15268f6895..0e832685310 100644
--- a/compiler/rustc_infer/src/infer/type_variable.rs
+++ b/compiler/rustc_infer/src/infer/type_variable.rs
@@ -129,19 +129,16 @@ 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,
 }
 
 pub(crate) struct TypeVariableData {
     origin: TypeVariableOrigin,
-    diverging: Diverging,
-}
-
-#[derive(Copy, Clone, Debug)]
-pub enum Diverging {
-    NotDiverging,
-    Diverges,
 }
 
 #[derive(Copy, Clone, Debug)]
@@ -191,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
@@ -260,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 });
@@ -268,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_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<PredicateObligation<'tcx>>;
+
+    fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships>;
 }
 
 pub trait TraitEngineExt<'tcx> {