HRTB impl selection does not cover type parameters not directly related to the trait.

[eddyb]

The following doesn't compile, as it tries to assign U a concrete &'x i32 instead of &'a i32:

trait Unary<T> {}
impl<T, U, F: Fn(T) -> U> Unary<T> for F {}
fn unary<F: for<'a> Unary<&'a T>, T>() {}

fn test<F: for<'a> Fn(&'a i32) -> &'a i32>() {
    unary::<F, i32>()
}

Removing the U type parameter makes it work - U is only used for the associated type Fn::Output anyway:

#![feature(unboxed_closures)]

trait Unary<T> {}
impl<T, F: Fn<(T,)>> Unary<T> for F {}
fn unary<F: for<'a> Unary<&'a T>, T>() {}

fn test<F: for<'a> Fn(&'a i32) -> &'a i32>() {
    unary::<F, i32>()
}

AFAICT, the selection results in for<'a, U> F: Fn<(&'a i32,), Output=U> in the first case, and for<'a> F: Fn<(&'a i32,)> in the second case, and we refuse to allow U to be parameterized by 'a in the former case, even though it's only used to satisfy the sugary form of the Fn trait.

[eddyb]

@nikomatsakis Is this the same issue as with the impls for fn(T) -> U not matching for<'a> fn(&'a i32) -> &'a i32?

[nikomatsakis]

I'm trying to decide if this is an actual bug :) It does seem like the "HR capture" logic is being unnecessarily conservative. Let me poke at the debug logs and see if that reveals to me why it is rejecting the impl when you include U but not if you don't (also, it works if you do Fn(T) -> T).

[eddyb]

@nikomatsakis I believe it breaks for type parameters which cannot be extracted from the TraitRef, i.e. <Unary<T> as Fn<(T,)>>. You should be able to relate multiple argument types, but not the return type (because it's an associated type and not part of the TraitRef).

[nikomatsakis]

Hmm, the problem is a bit of a subtle one and, in this particular example, tied to the associated type projection. But really I think it can occur with dependent where clauses of any kind. (No I don't, see update below.) No doubt this is already filed somewhere under another guise. I'm not sure of the best fix, but let me lay out how the problem arises in terms of what the compiler actually does.

We start out with a trait reference to solve:

for<'a> F: Unary<'a i32>

We match this against the impl

impl<T, U, F: Fn(T) -> U> Unary<T> for F {}

Which, internally, is lowered to:

impl<T, U, F> Unary<T> for F
    where F: Fn<(T,)>, <F as Fn<(T,)>>::Output = U

In so doing, we first "open" the for<'a> binder, so that the trait we are searching for becomes:

F: Unary<&'0 i32>

where '0 is a region variable. We then check whether we can match this against the impl in question. We can, with Self=F and T=&'0 i32. U is left unconstrained. The where clauses on the impl are always processed after we perform the initial match. So we wind up saying that the impl applies and that we now have various subobligations. The '0 region variable appears in some of those, and in that case we "regeneralize" by adding back a for<'a> binder so that '0 becomes a bound region again:

F: Sized
for<'a> F: Fn<(&'a i32,)>
for<'a> &'a i32: Sized
for<'a> <F as Fn<(&'a i32,)>>::Output == $U
$U: Sized

Note that $U is what was substituted for the variable U (but never constrained). And this is where the problem arises.

I think that the basic strategy here is somewhat wrong. It would be OK in the absence of variables like U, which do not appear in the trait reference but which are constrained by projections, but it's wrong now. The problem is that $U was created "inside" the binder along with with $T and $Self but, unlike those other variables, it was never constrained. Thus we kind of silently promote it to live outside the scope of the for, since it is completely unconstrained. This is not necessarily wrong I guess but it is overly conservative.

One possible fix here would be to recursively (and before returning) handle the projection constraints, so that U winds up being "determined" to be &'0 i32, which could then be generalized to &'a i32 wherever it appeared. That may be the best short term fix at least, though I am not so keen on it overall because I don't like doing work recursively like that.

If we had had lazy normalization, this would be much easier, because then we could just unify U with <F as Fn<(&'0 i32,)>>::Output, which would then be generalized to a bound region as needed. That's probably my preferred fix, presuming it can be made to work. This is basically the same as processing the projection constraint recursively, except that we could defer the actual normalization until later (and we may never have to do it).

(The other solutions I can imagine are quite a bit more complicated. It seems like you would need to capture, in the tree, what variables are bound where. What makes this hard is that $U is shared across two obligations.)

UPDATE: Remove sentence I don't think. I think that for this problem to arise you really need an associated type, since you need a type variable that is not found in the trait reference, which is otherwise verboten.

[nikomatsakis]

cc @arielb1 -- this seems related to the changes you made to order projection predicates earlier in the list. Does my earlier comment make sense to you?

[arielb1]

@nikomatsakis

I am not sure we should not evaluate associated type projections recursively - RFC447 basically forces this to work.

Unfortunately, it will work imperfectly without lazy normalization, because we can't represent a constraint like for<'a> <_ as Fn<(&'a u32,)>>::Output: Sized.

[nikomatsakis]

On Thu, Jan 14, 2016 at 12:54:36PM -0800, arielb1 wrote:

I am not sure we should not evaluate associated type projections recursively - RFC447 basically forces this to work.

Sorry, the double negative in this sentence is throwing me a bit. I'm
not sure I understand what you are saying. Are you saying my proposed
solution would or would not work? Also, when you say evaluate, I
presume you are not referring to the evaluate family of fns in
select but just using a generic verb.

[nikomatsakis]

@arielb1:

Unfortunately, it will work imperfectly without lazy normalization, because we can't represent a constraint like `for<'a> <_ as Fn<(&'a u32,)>>::Output: Sized`.

Can you elaborate just a bit on this? When does this kind of constraint arise?

[arielb1]

Can you elaborate just a bit on this? When does this kind of constraint arise?

impl<T> Foo for Option<T> where
    T: Fn(&u32),
    for<'a> <T as Fn(&'a u32)>::Output: Sized
{}

// evaluate <Option<_> as Foo>

[arielb1]

Sorry, the double negative in this sentence is throwing me a bit. I'm
not sure I understand what you are saying. Are you saying my proposed
solution would or would not work?

Recursively applying constraining-projections during confirmation should work, except for the type-inference case.

[nikomatsakis]

@arielb1

Sorry for not replying. I'm afraid I still don't quite follow you, so let me try and work it out. First off, I guess you meant to have impl<T>, like so, and probably Fn<(&'a u32,)>:

impl<T> Foo for Option<T> where
    for<'a> T: Fn<(&'a u32,)>,
    for<'a> <T as Fn<(&'a u32,)>>::Output: Sized
{}

// evaluate <Option<_> as Foo>

I'm not quite sure what the last line means, but if we were to follow the model of the original problem, we'd start with something to prove like for<'a> Option<&'a X>: Foo. "Opening" the for and matching this against the impl yields:

Option<$T> = Option<&'0 X>

and hence T = &'0 X. This suggests that we would translate the where clauses on the impl to:

for<'a> &'0 X: Fn<(&'a u32,)>
for<'a> <&'0 X as Fn<(&'a u32,)>>::Output: Sized

which we would could then cover back up as:

for<'a, 'b> &'b X: Fn<(&'a u32,)>
for<'a, 'b> <&'b X as Fn<(&'a u32,)>>::Output: Sized

This all seems...OK. Ah, wait, I guess your point is that we would need to normalize the <&'b X as Fn<(&'a u32,)>>::Output. I feel like we have issues normalizing under for binders still, right?