Higher-ranked types in trait bounds

[withoutboats]

Rust already has higher-ranked lifetime parameters; how feasible would it be to introduce higher-ranked type parameters?

[nrc]

What's the motivation?

[nrc]

It wouldn't be very feasible for first-class functions (which is the motivation for higher-ranked lifetimes) because Rust requires that functions are monomorphised before they are referenced.

[withoutboats]

My personal motivation is for making negative bounds as described in #1148 useful. If you have a trait Foo<T> and a trait Bar, you can't bound Bar: !Foo<T> unless you can declare trait Bar: for<T> !Foo<T>.

However their use in other contexts is a lot more limited if you can't do: foobar(func: &F) where F: for<T> Fn(T) -> T. Can Rust not monomorphize the function based on how it is used in the body of foobar?

[eddyb]

@nrc for<'a> fn(...) is technically not HRTB ("higher-ranked trait bounds").
Even though HRTB doesn't mention lifetimes, it's currently limited to it.

@withoutboats T: for<X> Trait<X> would actually only impact the type-system, trans would at most need the same infrastructure changes as everything else.
AFAIK, the hardest part is representing that X (and not breaking everything looking at type parameters), but we already have a solution for lifetimes, so perhaps adapting that would "just work".

I think it would be good to mention that this feature is specifically for implementing HRTB for type parameters, and not "higher-ranked type parameters" in general.

cc @nikomatsakis @arielb1 They should be able to better assess the implementation cost.

[nikomatsakis]

I've certainly thought about it. I think it's feasible, but there are a number of things I'd like to work out first. For example, I'd like to upgrade the compiler's trait implementation so that we can fully check WF for for<'a> -- it seems like something that would be more important in a for<T> Trait sort of scenario. In other words, I think with for<T> you're really going to want for<T where ...> Trait. (So you can, e.g., project out from assoc types on T etc.) It might be we can just extend the lazy approach there indefinitely, but it seems suboptimal. Obviously highly related to HKT (though also somewhat distinct).

[withoutboats]

@eddyb When you say that its HRTB instead of higher ranked type parameters in general, you mean that you're contrasting e.g. the bound F: for<T> Fn(T) -> T with the type e.g. for<T> fn(T) -> T?

I think with for<T> you're really going to want for<T where ...> Trait. (So you can, e.g., project out from assoc types on T etc.)

True, as a user I would expect these parameters to be as expressive as in other contexts.

[sgrif]

FWIW I've had a need for this in Diesel, where I want to limit certain functions to only SQL expressions which can be selected without a from clause (e.g. can be selected from anywhere). Would have been useful to have been able to write fn select<E, ST>(expr: E) -> ... where for<QS> E: SelectableExpression<QS, ST>

[emk]

So here's another use case, this one from serde:

pub fn deserialize_option_with<T, D, F>(d: &mut D, f: F)
                                        -> result::Result<Option<T>, D::Error>
    where T: serde::Deserialize,
          D: serde::Deserializer,
          F: for<D1: Deserializer> Fn(&mut D1) -> result::Result<T, D1::Error>
{
    /// Declare an internal visitor type to handle our input.
    struct OptVisitor<F> {
        wrapped_fn: F,
    }

    impl<T, F> serde::de::Visitor for OptVisitor<F>
        where T: serde::Deserialize,
              F: for<D1: Deserializer> Fn(&mut D1) -> result::Result<T, D1::Error>
    {
        type Value = Option<T>;

        fn visit_none<E>(&mut self) -> result::Result<Self::Value, E>
            where E: serde::Error
        {
            Ok(None)
        }

        fn visit_some<D>(&mut self,
                         deserializer: &mut D)
                         -> result::Result<Self::Value, D::Error>
            where D: serde::de::Deserializer
        {
            self.wrapped_fn(deserializer).map(Some)
        }
    }

    d.deserialize_option(OptVisitor { wrapped_fn: f, phantom: PhantomData })
}

[Rufflewind]

If this feature were to exist, the inability to assign a type to impl Traits covariant positions (rust-lang/rust#34511 (comment)) would no longer be a problem. Instead of

fn create_something() -> impl Trait;

fn foo<F, R>(callback: F) -> R
    where F: FnOnce(impl SomeTrait) -> R {
    callback(create_something())
}

one could simply write:

fn create_something() -> impl Trait;

fn foo<F, R>(callback: F) -> R
    where F: for<T: SomeTrait> FnOnce(T) -> R {
    callback(create_something())
}

Implementation-wise, this is probably easier to implement than expanding impl Trait and also more flexible.

---

That being said, a lot of use cases for higher-ranked types in trait bounds (HRTITB?) can be worked around by asking for a custom “visitor” trait instead of for<T> Fn(...). Consider @emk's example:

pub trait VisitDeserializeSome<'de, T> {
    fn visit_deserialize_some<D1: Deserializer<'de>>(self, D1) -> result::Result<T, D1::Error>;
}

pub fn deserialize_option_with<'de, T, D, F>(d: D, f: F)
                                        -> result::Result<Option<T>, D::Error>
    where T: serde::Deserialize<'de>,
          D: serde::Deserializer<'de>,
          F: VisitDeserializeSome<'de, T>
{
    /// Declare an internal visitor type to handle our input.
    struct OptVisitor<T, F> {
        wrapped_fn: F,
        phantom: PhantomData<T>,
    }

    impl<'de, T, F> serde::de::Visitor<'de> for OptVisitor<T, F>
        where T: serde::Deserialize<'de>,
              F: VisitDeserializeSome<'de, T>
    {
        type Value = Option<T>;

        fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
            write!(formatter, "an option")
        }

        fn visit_none<E>(self) -> result::Result<Self::Value, E>
            where E: serde::de::Error
        {
            Ok(None)
        }

        fn visit_some<D>(self,
                         deserializer: D)
                         -> result::Result<Self::Value, D::Error>
            where D: serde::de::Deserializer<'de>
        {
            self.wrapped_fn.visit_deserialize_some(deserializer).map(Some)
        }
    }

    d.deserialize_option(OptVisitor { wrapped_fn: f, phantom: PhantomData })
}

This is very unergonomic for the poor API user − it’s kind of like C++ back in the days before lambdas were introduced and you had to declare a new class just to create a function object.

Hence, HRTITB would have lots of synergy with generic closures (“polymorphic lambdas” in C++). Consider the foo example earlier:

fn use_foo() {
    foo(::<T: SomeTrait> |t: T| {
        t.some_trait_method();
    });
}

This could desugar to something like:

impl<T: SomeTrait> FnOnce<(T,)> for __AnonymousClosureType {
    type Output = ();
    extern "rust-call" fn call_once(self, args: (T,)) -> Self::Output {
        t.some_trait_method();
    }
}

fn use_foo() {
    foo(__AnonymousClosureType);
}