"error: trait bound is not satisfied" when it is

[japaric]

STR

# Cargo.toml
[dependencies]
typenum = "=1.9.0"

// src/lib.rs
extern crate typenum;

use std::marker::PhantomData;

use typenum::{Max, Maximum, Unsigned};

/// A resource, a mechanism to safely share data between tasks
trait Resource {
    type Data: Send;
    type Ceiling: Unsigned;

    fn claim<THRESHOLD, F>(&self, t: &mut T<THRESHOLD>, f: F)
    where
        F: FnOnce(
            &R<Self::Data, Self::Ceiling>,
            &mut Maximum<THRESHOLD, Self::Ceiling>,
        ),
        THRESHOLD: Unsigned + Max<Self::Ceiling>;
}

/// Unlocked resource
struct R<DATA, CEILING>
where
    CEILING: Unsigned,
    DATA: Send,
{
    data: DATA,
    _ceiling: PhantomData<CEILING>,
}

impl<DATA, CEILING> Resource for R<DATA, CEILING>
where
    DATA: Send,
    CEILING: Unsigned,
{
    type Data = DATA;
    type Ceiling = CEILING;

    fn claim<THRESHOLD, F>(&self, t: &mut T<THRESHOLD>, f: F)
    where
        F: FnOnce(&R<DATA, CEILING>, &mut Maximum<THRESHOLD, CEILING>),
        THRESHOLD: Unsigned + Max<CEILING>,
    {
        f(self)
    }
}

/// Preemption threshold token
struct T<THRESHOLD>
where
    THRESHOLD: Unsigned,
{
    _threshold: PhantomData<THRESHOLD>,
}

$ cargo build
error[E0277]: the trait bound `THRESHOLD: typenum::Max<CEILING>` is not satisfied
  --> src/lib.rs:39:5
   |
39 | /     fn claim<THRESHOLD, F>(&self, t: &mut T<THRESHOLD>, f: F)
40 | |     where
41 | |         F: FnOnce(&R<DATA, CEILING>, &mut Maximum<THRESHOLD, CEILING>),
42 | |         THRESHOLD: Unsigned + Max<CEILING>,
43 | |     {
44 | |         f(self)
45 | |     }
   | |_____^ the trait `typenum::Max<CEILING>` is not implemented for `THRESHOLD`
   |
   = help: consider adding a `where THRESHOLD: typenum::Max<CEILING>` bound

error[E0277]: the trait bound `THRESHOLD: typenum::Max<CEILING>` is not satisfied
  --> src/lib.rs:39:5
   |
39 | /     fn claim<THRESHOLD, F>(&self, t: &mut T<THRESHOLD>, f: F)
40 | |     where
41 | |         F: FnOnce(&R<DATA, CEILING>, &mut Maximum<THRESHOLD, CEILING>),
42 | |         THRESHOLD: Unsigned + Max<CEILING>,
43 | |     {
44 | |         f(self)
45 | |     }
   | |_____^ the trait `typenum::Max<CEILING>` is not implemented for `THRESHOLD`
   |
   = help: consider adding a `where THRESHOLD: typenum::Max<CEILING>` bound

error[E0276]: impl has stricter requirements than trait
  --> src/lib.rs:39:5
   |
12 | /     fn claim<THRESHOLD, F>(&self, t: &mut T<THRESHOLD>, f: F)
13 | |     where
14 | |         F: FnOnce(
15 | |             &R<Self::Data, Self::Ceiling>,
16 | |             &mut Maximum<THRESHOLD, Self::Ceiling>,
17 | |         ),
18 | |         THRESHOLD: Unsigned + Max<Self::Ceiling>;
   | |_________________________________________________- definition of `claim` from trait
...
39 | /     fn claim<THRESHOLD, F>(&self, t: &mut T<THRESHOLD>, f: F)
40 | |     where
41 | |         F: FnOnce(&R<DATA, CEILING>, &mut Maximum<THRESHOLD, CEILING>),
42 | |         THRESHOLD: Unsigned + Max<CEILING>,
43 | |     {
44 | |         f(self)
45 | |     }
   | |_____^ impl has extra requirement `for<'r, 'r> F: std::ops::FnOnce<(&'r R<DATA, CEILING>, &'r mut _)>`

error: aborting due to 3 previous errors

Expected outcome

I would expect this to compile since the supposedly unsatisfied trait bound is right there in the where clause of claim.

Meta

$ rustc -V
rustc 1.21.0-nightly (599be0d18 2017-07-26)

cc @eddyb @nagisa Any clue what's wrong here? Seems closure related. If you drop the FnOnce bound and replace F with Maximum<..> it compiles.

[eddyb]

impl has extra requirement for<'r, 'r> ...

I believe is the crux of the problem. We don't (yet) support matching HRTB bounds like that.
Although typically I only see that with projections so maybe I'm wrong. cc @nikomatsakis

[japaric]

@eddyb Thanks for taking a look. Could you elaborate on what you mean by "matching HRTB bounds"? I thought you were referring to the constraint that both lifetimes must be the same, 'r in this case, but the problem persists even if I eliminate that constraint by changing the bound to F: for<'a, 'b> FnOnce(&'a ..., &'b mut ...)

[eddyb]

I mean the fact that it's a higher ranked bound, i.e. that it has any for<...>. Can't remember the exact issue to compare to, we don't have a catalog of them :(.

[bkchr]

Hey, we are currently running into the same bug. It mostly manifests in code that uses traits mixed with concrete types. It is hard to find the root cause of it, but as we are also having for<..> in a trait implementation, I suspect that this is related.

I can not provide any easy to replicate code sample. If wanted, I could point to branches/code in our code bases https://github.com/paritytech/substrate and https://github.com/paritytech/polkadot.

[eddyb]

@nikomatsakis Do you happen to know if this is a duplicate of #30472?

[nikomatsakis]

Not sure off the top of my head, would have to investigate more