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`

4 files changed, 96 insertions, 2 deletions

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<PredicateObligation<'tcx>>,
+
+    relationships: FxHashMap<ty::TyVid, ty::FoundRelationships>,
 }
 
 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<PredicateObligation<'tcx>> {
         self.obligations.iter().cloned().collect()
     }
+
+    fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> {
+        &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<PendingPredicateObligation<'tcx>>,
+
+    relationships: FxHashMap<ty::TyVid, ty::FoundRelationships>,
+
     // 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<PredicateObligation<'tcx>> {
         self.predicates.map_pending_obligations(|o| o.obligation.clone())
     }
+
+    fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> {
+        &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;
+        }
+    }
+}