# ekuber:pnkfelix:nmatsakis Discussion re two bugs

## PR 83915

https://github.com/rust-lang/rust/pull/83915

The problem:

trait FnOnce {
    type Output; // <-- implies Sized
}

// conceptually
impl<A, R> FnOnce<A> for fn(A) -> R
where
  R: Sized, // <-- not enforced today
{
    type Output = R;
}

function pointers `fn() -> Out` implement `FnOnce<(), Output = Out>` which implies that `Out: Sized`, but this is not enforced.

Where and how to enforce the bound?

What is natural?

1. Put it in the select (what ekuber did)

2. Could make it part of well-formedness rules for fn types.

Today we do not enforce well-formedness rules for things that involve higher-ranked types.

If you had a type like:

trait Trait<'a> { }
for<'a> fn() -> dyn Trait<'a>

we would not enforce well-formedness rules on the `dyn Trait<'a>`.

The intention of not enforcing the well-formedness rules on the higher-ranked type was to enforce the necessary rules on the place where the type is "used" (i.e. where the lifetime parameter is instantiated)

3. Put it in the point of projection.

ekuber: that only triggers if you call it?
nmatsakis: no. only triggers when you project `Output`

fn foo<F: FnOnce<()>>() {
    let a = F::Output::a();
}

fn main() {
    foo::<fn() -> str>()
}

Niko's solution is not complete. But it *is* minimally intrusive, and resolves all problems *on stable*.

So: it could be a decent interim fix. It is probably not the right long-term fix.

ekuber: But well-formedness doesn't account for function pointers at all?
nmatsakis: Yes. But I'd like to change that.

4. Could require that `Output` type is sized for all lifetimes.

ekuber: How does this interact with unsized locals?
nmatsakis: Cannot return unsized values under any known proposal.

nmatsakis: (Would require changing ABI, or runtime support)

nmatsakis: Also, would require adding `?Sized` to `FnOnce::Output`, which would break a lot of stuff.

ekuber: I had considered requiring all return types (including on fn pointers) to be sized, as part of well-formedness check. I had abandoned that because I assumed we wanted to support it in the future, by analogy with unsized locals. If we aren't going to be supporting it, then that seems cleanest?

nmatsakis: There's another challenge w.r.t. well-formedness check. We descend through the type deeply, and if we encounter types that have references to bound regions, we skip the requirement on such types.

struct Foo<'a, T: Ord + Trait<'a>> { }

for<'b> fn(Foo<'b, T>)

// requires:
//     T: Ord <-- we will verify this
//     T: Trait<'b> <-- but not this

potentially though:

* when we get to a fn type:

for<'a> fn() -> SomeType<'a>

* could construct a higher-ranked goal like `for<'a> SomeType<'a>: Sized`

for<'a> fn() -> for<'b> fn() -> (&'a str, &'b str)

Nested cases like above present a problem

Outer one `for<'a> ...` is easy
Inner one `for<'b> ...` ... is a mess.

for<'a, 'b> fn(&'a &'b u32)
// only legal if 'b: 'a
// for<'a, 'b: 'a> fn(&'a &'b u32)

Cases like above cannot be expressed in rustc trait system today.

nmatsakis: Chalk can do it.

pnkfelix: So maybe we adopt a short-term solution, and say that the long-term (well-formedness check) solution is blocked on Chalk.

nmatsakis: Okay. So we just need to choose between one of the short-term solutions, either Niko's or Esteban's.

ekuber: we filter specific obligations to select specific ObligationCauseCode

nmatsakis: Why did you put in a hack to filter out opaque types?
ekuber: To limit fallout. Without that, couldn't compile stage 1 at all. Failed on specific uses.

pnkfelix: Which cases are handled by ekuber's solution that are not handled by nmatsakis's PR? (Answer: see above.)

----

## Issue 80066

[register_obligation_at](https://github.com/rust-lang/rust/blob/109248a4eb99bc83684c94ca4ef36f2fadc17e2a/compiler/rustc_data_structures/src/obligation_forest/mod.rs#L338)

ekuber: obligation.as_cache_key() was adding the same obligations over and over again.
ekuber: The lifetimes were changing between obligations. [so they weren't really "the same"].
ekuber: tried changing things so that it instead builds up a recursive obligation. Not the right thing, but at least that variant finishes.

nmatsakis: When the example has to prove that B: Foo ... (see below)

struct Wrapper<T>(T);

struct Test;

pub unsafe trait Foo: Sized {
    type Bar: Bar<Self>;
}

pub unsafe trait Bar<B: Foo>: Sized {}

unsafe impl<S: Bar<Self>> Foo for Wrapper<&mut S> {
    type Bar = S;
}

unsafe impl<B: Foo<Bar = Self>> Bar<B> for Test {}

fn assert<B: Foo>(b: B) {}

fn test() {
    assert(Wrapper(&mut Test))
}

* Prove that `Wrapper<&'a mut Test>: Foo`
* `S = Test` so `Test: Bar<Wrapper<&'a mut Test>>`
* `Wrapper<&'a mut Test>: Foo` -- cycle
* `<Wrapper<&'a mut Test> as Foo>::Bar = Test` -- cycle
*

nmatsakis: I expect this to fail, due to the cycle
nmatsakis: But you are saying that it continues to attempt the proof, building up a longer and longer

[Using Debug String instead of `ParamEnvAnd<Binder<Predicate>>`](https://github.com/rust-lang/rust/issues/80066#issuecomment-832870830)

error[E0275]: overflow evaluating the requirement `Test: Bar<Wrapper<&mut Test>>`
  --> f20.rs:20:5
   |
17 | fn assert<B: Foo>(b: B) {}
   |              --- required by this bound in `assert`
...
20 |     assert(Wrapper(&mut Test))
   |     ^^^^^^
   |
   = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`f20`)
note: required because of the requirements on the impl of `Foo` for `Wrapper<&mut Test>`
  --> f20.rs:11:27
   |
11 | unsafe impl<S: Bar<Self>> Foo for Wrapper<&mut S> {
   |                           ^^^     ^^^^^^^^^^^^^^^
note: required because of the requirements on the impl of `Bar<Wrapper<&mut Test>>` for `Test`
  --> f20.rs:15:33
   |
15 | unsafe impl<B: Foo<Bar = Self>> Bar<B> for Test {}
   |                                 ^^^^^^     ^^^^
   = note: 127 redundant requirements hidden
   = note: required because of the requirements on the impl of `Foo` for `Wrapper<&mut Test>`

nmatsakis: We have some logic around lifetimes. Normally we don't equate them. But its not triggering here I guess.

(sorry about the ugly output)

├─44ms DEBUG rustc_data_structures::obligation_forest occupied OccupiedEntry { key: ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: UserFacing }, value: Binder(TraitPredicate(TraitRef(DefId(2:2830 ~ core[e453]::marker::Sized) [Type(Ty(Adt(Test, []), (empty), DebruijnIndex(0)))])), []) }, value: 3, .. }: Node { obligation: PendingPredicateObligation { obligation: Obligation(predicate=Binder(TraitPredicate(TraitRef(DefId(2:2830 ~ core[e453]::marker::Sized) [Type(Ty(Adt(Test, []), (empty), DebruijnIndex(0)))])), []), depth=1), stalled_on: [] }, state: Cell { value: Success }, dependents: [1, 7, 8, 12, 13, 15, 16, 22, 23, 25, 26, 28, 29, 31, 32, 42, 43, 45, 46, 48, 49, 51, 52, 54, 55], has_parent: true, obligation_tree_id: ObligationTreeId(2) }
├─44ms DEBUG rustc_data_structures::obligation_forest pushing 57
├─44ms INFO rustc_trait_selection::traits::fulfill as_cache_key Binder(TraitPredicate(TraitRef(DefId(0:11 ~ f20[317d]::Bar) [Type(Ty(Adt(Test, []), (empty), DebruijnIndex(0))), Type(Ty(Adt(Wrapper, [Type(Ty(Ref('_#28r, Ty(Adt(Test, []), (empty), DebruijnIndex(0)), Mut), HAS_RE_INFER | HAS_FREE_LOCAL_REGIONS | HAS_FREE_REGIONS, DebruijnIndex(0)))]), HAS_RE_INFER | HAS_FREE_LOCAL_REGIONS | HAS_FREE_REGIONS, DebruijnIndex(0)))])), [])
├─44ms DEBUG rustc_data_structures::obligation_forest register_obligation_at:
│ key: ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: UserFacing }, value: Binder(TraitPredicate(TraitRef(DefId(0:11 ~ f20[317d]::Bar) [Type(Ty(Adt(Test, []), (empty), DebruijnIndex(0))), Type(Ty(Adt(Wrapper, [Type(Ty(Ref('_#28r, Ty(Adt(Test, []), (empty), DebruijnIndex(0)), Mut), HAS_RE_INFER | HAS_FREE_LOCAL_REGIONS | HAS_FREE_REGIONS, DebruijnIndex(0)))]), HAS_RE_INFER | HAS_FREE_LOCAL_REGIONS | HAS_FREE_REGIONS, DebruijnIndex(0)))])), []) } - 16928730249997226020
│ PendingPredicateObligation { obligation: Obligation(predicate=Binder(TraitPredicate(TraitRef(DefId(0:11 ~ f20[317d]::Bar) [Type(Ty(Adt(Test, []), (empty), DebruijnIndex(0))), Type(Ty(Adt(Wrapper, [Type(Ty(Ref('_#28r, Ty(Adt(Test, []), (empty), DebruijnIndex(0)), Mut), HAS_RE_INFER | HAS_FREE_LOCAL_REGIONS | HAS_FREE_REGIONS, DebruijnIndex(0)))]), HAS_RE_INFER | HAS_FREE_LOCAL_REGIONS | HAS_FREE_REGIONS, DebruijnIndex(0)))])), []), depth=9), stalled_on: [] }

// Lifetime inference usually just accrues:
'0; '1

// At the very end of type-checking, we solve them all at once

nmatsakis: Usually you have some logic, for lifetime inference, that accrues relations [see above].

nmatsakis: Normally you cannot just normalize lifetimes. They just hang around. But we do have special cases where we *do* normalize them. Where you get back the same one. We did that around this projection caching stuff.

nmatsakis: Either missing a normalization step, or there's a place where they are not equating, and why.

nmatsakis: If you go back up, I bet we have some fresh variable. Is it related to the `'a`? Or maybe that equating hasn't happened yet; there have been bugs like that in the past.

ekuber: I added a bunch of debug output to understand what was going on, but didn't understand the lifetime stuff here.

from earlier conversation, Niko sees:

error[E0277]: the size for values of type `<<I as Iterator>::Item as IntoIterator>::IntoIter` cannot be known at compilation time
   --> library/core/src/iter/adapters/flatten.rs:375:46
    |
375 |                 next => self.backiter = next.map(IntoIterator::into_iter),
    |                                              ^^^ doesn't have a size known at compile-time
    |
    = help: the trait `Sized` is not implemented for `<<I as Iterator>::Item as IntoIterator>::IntoIter`
help: consider further restricting the associated type
    |
359 |     fn next_back(&mut self) -> Option<U::Item> where <<I as Iterator>::Item as IntoIterator>::IntoIter: Sized {
    |                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^