Support higher-rank lifetimes in traits (e.g. <'a>Trait<'a>)

[pcwalton]

This will be needed as part of unboxed closures to complete the transition.

Nominating for P-backcompat-lang as a dependency of #14798.

[glaebhoerl]

Why only traits? :)

[glaebhoerl]

To elaborate on my drive-by comment: I'm not sufficiently familiar with the innards of the compiler to make a direct judgment, but in the abstract, I don't see why trait objects with higher-rank lifetimes should work any differently than the other candidates like structs and fns, and it may be cleaner to implement the general case than an unnecessarily specialized one.

[pnkfelix]

(I'll be putting an addendum PR on the unboxed closures RFC as a follow-up for this. -- removing I-nominated tag.)

[pnkfelix]

(actually there was already a section in the unboxed closures RFC saying that we need a separate RFC to describe the need for trait references like <'a> Fn<(&'a A), &'a B>)

[ftxqxd]

With the new unboxed closure trait syntax (FnMut(Foo, Bar) -> Baz), will the syntax be <'a>FnMut(&'a Foo, Bar) -> Baz or FnMut<'a>(&'a Foo, Bar) -> Baz? The latter looks much nicer and seems more similar to the fn syntax, but it was never explicitly stated in the unboxed closure syntax RFC what the syntax would look like with higher-rank lifetimes.

[blaenk]

I agree with @P1start that FnMut<'a>(&'a Foo, Bar) -> Baz looks very nice, and more consistent with function types after all. It'll be inconsistent with trait lifetime syntax that'll be implemented by this, but it's sugar already, so it's already an exception.

[emk]

According to @huonw and @BurntSushi, higher-rank lifetimes may be the easiest way to write some sort of zero-allocation StreamingIterator type, which has big performance implications for parsing libraries. Right now, eliminating memory allocation can result in 25x–47x speedups, but there's no way to abstract over the necessary lifetimes required to make a useful generic trait.

The basic goal is to take a trait similar to the standard library's Buffer:

pub trait Buffer: Reader {
    fn fill_buf<'a>(&'a mut self) -> IoResult<&'a [u8]>;
    // ...
}

…but which returns a generic value:

pub trait StreamingIterator<T<'*>> {
    fn next<'a>(&'a mut self) -> Option<T<'a>>;

    // Can we implement _any_ reasonable version of `fold` here? 
    fn fold<'a,S>(&'a mut self, init: B, f: |S, T<'a>| -> S) -> S { ... } 
}

This would be a really nice use-case for Rust: It would allow performing high-speed generic computations on streaming I/O. Right now, we can pick any two of "high-speed," "generic" and "streaming," as far as I can tell. After several days of picking people's brains, it feels like we can almost get all three, but it's just barely of reach.

[zwarich]

@emk Since StreamingIterator is parameterized by a type constructor that takes a single lifetime parameter and all universal quantifiers in function types appear at the far left, that's actually an example of higher-kinded types rather than higher-rank types.

[huonw]

(Whoops, got the terminology wrong, sorry.)

[danburkert]

Will higher-rank lifetimes be inferred where possible? For instance, if I understand correctly, this proposal allows for the following unboxed-closure type:

<'a> Fn<&'a [int], uint>

will the following be possible?

Fn<&[int], uint>

[pcwalton]

@danburkert Yes, I believe.

[pcwalton]

Closing as a dupe of #17661, which is accepted for P-backcompat-lang