Soundness regression with for<'lt> closure having an implied bound from return type

[danielhenrymantilla]

Bug originally found by @ast-ral, over Discord, which I've then reduced.

Code

I tried this code:

fn whoops(
    s: String,
    f: impl for<'s> FnOnce(&'s str) -> (&'static str, [&'static &'s (); 0]),
) -> &'static str
{
    f(&s).0
}

I expected to see this happen:

error[E0597]: `s` does not live long enough
 --> <source>:6:7
  |
6 |     f(&s).0
  |     --^^-
  |     | |
  |     | borrowed value does not live long enough
  |     argument requires that `s` is borrowed for `'static`
7 | }
  | - `s` dropped here while still borrowed

error: aborting due to previous error

For more information about this error, try `rustc --explain E0597`.

Instead, this happened: code compiles successfully

Version it soundly rejected this code:

1.64.0

Version with soundness regression

1.65.0 and onwards

Proof of unsoundness:

fn static_str_identity()
  -> impl for<'s> FnOnce(&'s str) -> (
        [&'static &'s (); 0],
        &'static str,
    )
{
    |s: &/* 's */ str| ( // <----------------+ inputs restricted to `'s`.
        [], // `: [&'static &'s (); 0]`,     |
            //   thus `'s : 'static` ->------+
            //            +-<----------------+
            //            |
            //            v
        s, // `: &'s str <: &'static str`
    )
}
​
fn main()
{
    let f = static_str_identity();
    let local = String::from("...");
    let s: &'static str = f(&local).1; // <- should be rejected!
    drop(local);
    let _unrelated = String::from("UB!");
    dbg!(s); // <- compiles and prints `"UB!"`
}

@rustbot modify labels: +I-unsound +regression-from-stable-to-stable -regression-untriaged

Observations

• This does not occur if the implied-lifetime-bounds array is in closure parameter position; so it looks like a bug w.r.t. not properly checking the closure output type implied bounds?

• -Ztrait-solver=next does not help (as of 2023-08-16)

[lqd]

Bisected to nightly-2022-08-10:

• Implement special-cased projection error message for some common traits #98863
• Avoid ICE in rustdoc when using Fn bounds #100205
• Rollup of 6 pull requests #100304
• Add option to mir::MutVisitor to not invalidate CFG. #100089
• Rollup of 7 pull requests #100318
• consider unnormalized types for implied bounds #99217 <- looks maybe interesting
• rustdoc: use a more compact encoding for implementors/trait.*.js #100150

[apiraino]

@lqd you beat me by one minute :)

cc @lcnr for #99217 being possible cause of this unsoundness?

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-high +T-compiler -needs-triage

[ast-ral]

Oh, neat it did turn out to be a new soundness bug instead of a dupe of #25860. Thanks for figuring out this was a regression, @danielhenrymantilla.

[lcnr]

for

fn whoops<'a, F: for<'s> FnOnce(&'s str) -> (&'static str, [&'static &'s (); 0])>(
    s: &'a str,
    f: F,
) -> &'static str
{
    f(s).0
}

we have a terminator calling extern "rust-call" fn(F, (&'?4 str,)) -> <F as FnOnce<(&'?4 str,)>>::Output {<F as FnOnce<(&'?4 str,)>>::call_once}, i.e. a function which returns <F as FnOnce<(&'?4 str,)>>::Output.

This does not include the implied bounds. Checking that <F as FnOnce<(&'?4 str,)>>::Output is WF requires proving F: FnOnce<(&'?4 str,)> which succeeds without checking the usable implied bounds of the trait-ref. This is very related to other soundness bugs (TODO: link to them)edit: there's a bit more to this than I thought 😅

[BoxyUwU]

This soundness bug is effectively only reproducible via the Fn* traits because the impls for it are builtin and so a little screwy. An attempt to write an explicit impl for the builtin Fn* impls would require an explicit bound that 's: 'static holds which is not present on the builtin Fn* impl.

There is an assumption that all it takes for an assoc type to be wf is the where clauses on it and the impl hold, and that all arguments in the traitref are wf. The builtin Fn* impls violate this by not having the required 's: 'static implied bound on the impl so we end up with <F as Fn<...>>::Output being able to be proven wf without proving the implied bounds.

When calling f we check that the fn sig of <F as FnOnce<(&'?4 str,)>>::call_once is wf which is fn(F, (&'?4 str,)) -> <F as Fn<(&'?4 str,)>>::Output. Before #99217 we would check the normalized signature is wf so the return type would be -> (&'static str, [&'static &'s (); 0]) which would cause us to prove 's: 'static. Now that we check the unnormalized signature is wf we end up never seeing the normalized form with the &'static &'s () which introduces the 's: 'static implied bound.

It is generally an invariant of the type system that wf(ty) holding should imply wf(normalize(ty)) also holds. The fact that F::Output can be well formed but (&'static str, [&'static &'s (); 0]) is not, is concerning. In an ideal world proving the Fn* traits would require also proving all the implied bounds hold but right now that is not possible afaik.

A simple fix (albeit hacky until we make implied bounds desugared to actual bounds) would be to make us also check wf(normalized(sig)) not just wf(sig).