Revise never type fallback algorithm by Mark-Simulacrum · Pull Request #88804 ·...

This is a rebase of #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, 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, 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.

#![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