Library modernization blockers

[japaric]

This is a list of the blockers (ICEs/bugs) that I found while attempting to modernize the standard library with features like unboxed closures and associated types. This list serves two purposes:

• It should signal which parts of the standard library become actionable. For example, after HRTB: the trait Fn<(&_,), &_> is not implemented for the type fn(&'a u8) -> &'a u8 #19126 gets fixed, the Option/Result API can be updated to use unboxed closures.
• As a list of high priority FIXMEs.

Unboxed closures

-> Move library code away from boxed closures (part of #14798)

In function arguments

Option, Result, etc

// from
fn map<U>(self,  f: |T| -> U) -> Option<U>;
// to
fn map<U, F: FnOnce(T) -> U>(self,  f: F) -> Option<U>;

Blockers

• the trait Fn<(&_,), &_> is not implemented for the type fn(&'a u8) -> &'a u8 HRTB: the trait Fn<(&_,), &_> is not implemented for the type fn(&'a u8) -> &'a u8 #19126 (AFAIK, this will be a compiler change, and will need a snapshot)

In structs fields

core::iter::Map

struct Map<A, B, I, F> where I: Iterator<A>, F: FnMut(A) -> B {
    iter: I,
    f: F,
}

Main issue here is that closures have anonymous types, so they can't be part of the signature of functions, structs, etc. See #19186 (comment)
and/or #18101 (comment) for more details.

Use bare functions instead of closures that capture nothing

core::str::Bytes, core::str::AnyLines
collections::btree::Keys, collections::hash_map::Values

As pointed by @sfackler: If the closure captures nothing, we can use a bare function instead.

type Bytes<'a> = Map<&'a u8, u8, slice::Items<'a, u8>, fn(&u8) -> u8>;

// Self = str
fn bytes(&self) -> Bytes {
    fn deref(&b: &u8) -> u8 { b }
    self.as_bytes().iter().map(deref)
}

Blockers

• the trait Fn<(&_,), &_> is not implemented for the type fn(&'a u8) -> &'a u8 HRTB: the trait Fn<(&_,), &_> is not implemented for the type fn(&'a u8) -> &'a u8 #19126

Use boxed closures otherwise

Add examples here

Blockers

• Box<Fn(int) -> int + 'static> is not accepted: "explicit lifetime bound required" Box<Fn(int) -> int + 'static> is not accepted: "explicit lifetime bound required" #18772 (Fixed in Correct parsing of the precedence of + #19298, but needs to get snaptshot-ed)

Associated types

-> Update library code for associated output types #17826

There are several issues in this area, so I'll list the blockers in increasing complexity order:

Extension traits with only output types

AdditiveIterator, MultiplicativeIterator, etc

Blockers

• ICE: When cross-crate importing trait with associated output types ICE when using associated types in gfx-rs #18048 (comment) (this one blocks any work with associated types)
• rustdoc panics when dealing with associated types rustdoc panics when dealing with associated types #18594 (this one also blocks any work with associated types)
• Associated types Order can cause ICE Associated types Order can cause ICE #18611 (can be worked around by shuffling the code around, but fixing it should reduce the amount of code churn)

Traits with only output types that are used for GP

AsSlice, Hasher, etc

Blockers

• ICE: When using an associated type as the type parameter of a bound ICE: When using an associated type as the type parameter of a bound #19081
• Support the Trait<Output=Type> syntax Support the Trait<Output=Type> syntax #18432

Traits with input and output types

Add, Mul, Sub, etc

Blockers

• ICE: When implementing trait with a generic parameter and an associated output type ICE: When implementing trait with a generic parameter and an associated output type #19129

---

It's likely that we'll find more blockers as we progress, so I'll try to keep this list up to date.

cc @alexcrichton @aturon @nick29581 @nikomatsakis

[aturon]

@japaric Thanks so much for putting this together!

[japaric]

Added #18048 (ICE when cross-crate importing a trait that has associated output types) to the list, which blocks any work on associated types.

[aturon]

cc @nikomatsakis @nick29581

[japaric]

I was exploring using unboxed closures in structs like core::iter::Map, and I hit the bytes()/Bytes issue that I've mentioned before. I explored the alternatives suggested in that thread, but turns out I can't really use any of them. Let me elaborate:

• We want to make Map use unboxed closures like this:

struct Map<A, B, I, F> where I: Iterator<A>, F: FnMut(A) -> B {
    iter: I,
    f: F,
}

• Currently, the StrPrelude::bytes() method returns Bytes which is a type alias to Map. This is how the method looks like:

// Self = str
fn bytes<'a>(&'a self) -> Bytes<'a> {
    self.as_bytes().iter().map(|&b| b)
}

• The issue: The bytes method can't be written like that with the "unboxed" version of Map. The reason is that Bytes would have to be an alias to Map<&'a u8, u8, slice::Items<'a, u8>, ???>, where ??? is the type of the unboxed closure. But since unboxed closures have anonymous types, that return type can't be "written down".

---

These are the suggestions (proposed in the other thread) to work around the issue:

• Use a boxed closure Box<FnMut(..) -> _> instead of ???: This is not possible in this case, because we're dealing with libcore, so there is no Box here.
• Use &'static FnMut(..) -> _ instead of ???: AFAIK, it's not currently possible to create a value with that type. (Do we plan to support that in the future?)
• Use some Struct instead of ??? where Struct: FnMut(..) -> _: Because of Unable to manually implement FnOnce #18835/Coherence and blanket impls interact in a suboptimal fashion with generic impls #19032, is not currently possible to do impl FnMut(..) -> _ for Struct.
• Make Bytes a struct where Bytes: Iterator<u8>, and make StrPrelude::bytes return that struct. This literally means that we won't use closures at all.

---

StrPrelude::bytes()/Bytes is not the only occurrence. There is also StrPrelude::lines_any()/AnyLines in the same module, and there are probably other cases with other iterator adaptors and in other crates.

My question here is: On what issue should we block "Using unboxed closures in structs field"?

• On the availability of &'static Fn(..) -> _ values?
• Should we wait on Coherence and blanket impls interact in a suboptimal fashion with generic impls #19032, and use "callable" structs instead of sugared unboxed closures?
• Should we leave it unblocked, and just use one-use Iterator structs where possible?

I'll explore this last option, because I want to see if any other bug/ICE pops up in the process.

[japaric]

I'll explore this last option, because I want to see if any other bug/ICE pops up in the process.

Just found out that there are a lot of type aliases to Map in libcollections, that will need to be updated to work with unboxed closures. Namely, all the Keys/Values/MoveItems aliases in each module of libcollections, i.e. btree::Keys, hash_map::Values, etc.

Since libcollections has access to liballoc, I tried to use the Box<FnMut(..) -> _> approach, but the Box needs a lifetime specifier (like Box<FnMut(..) -> _ + 'static), and that doesn't currently parses because of #18772. Thankfully, @nikomatsakis already sent PR #19298 fixing the issue!

I'll update the top comment to mention that issue, because we want it to get snapshot-ed.

[sfackler]

Don't functions implement the Fn traits? We might be able to work around some of these issues by using them instead of the closure sugar.

[japaric]

Don't functions implement the Fn traits?

Yes! And it almost works:

#![feature(unboxed_closures)]

use std::{iter, slice};

struct Map<A, B, I, F> where I: Iterator<A>, F: FnMut(A) -> B {
    iter: I,
    f: F,
}

fn bytes<'a>(s: &'a str) -> Map<&'a u8, u8, slice::Items<'a, u8>, fn(&u8) -> u8> {
    //~^ error: the trait `core::ops::Fn<(&'a u8,), u8>` is not implemented for the type `fn(&u8) -> u8`
    fn deref(&b: &u8) -> u8 { b }

    Map {
        iter: s.as_bytes().iter(),
        f: deref,
    }
}

fn this_works() -> Map<u8, uint, iter::Range<u8>, fn(u8) -> uint> {
    fn cast(i: u8) -> uint { i as uint }

    Map {
        iter: range(0, 5),
        f: cast,
    }
}

fn main() {}

Except that due to #19126, bare functions that have lifetimes in their arguments/return value currently don't implement the Fn traits. Still, it's a great idea, I'll add it the top comment. Thanks @sfackler!

[AndyShiue]

Can this be closed?

[japaric]

Can this be closed?

Yes. There are still blockers (mainly for assoc types) but I'm working with @nikomatsakis in a tight feedback loop (on IRC) so this issue is not relevant anymore.