Unboxed closure metabug

[aturon]

This is a metabug for tracking work remaining to be done on unboxed closures. It contains only the high-level remaining issues. For a comprehensive list of closure bugs, search using the A-closures label.

1.0 Issues

• Trait selection treats unboxed closure arguments as quasi-associated types #20872 -- Make Fn traits be treated like everything in trait selection
• ICE using parenthetical trait notation in impls  #19982 -- ICE using parenthetical notation in impls
• Unexplained lifetime error in closure type #11740 -- Unexplained lifetime error in closure type
• Unable to manually implement FnOnce #18835 -- Unable to manually implement FnOnce
• FnMut not implemented for mutable FnMut implementors #23015 -- Impl FnMut for &mut F where F: FnMut

Completed issues

• Make return type of the Fn traits an associated type #20871 -- Make return type of the Fn traits an associated type
• Cannot move from individual upvars in a by-ref once closure #21603 -- Allow individual upvars to be moved
• Closure kind inference: infer whether a closure is Fn, FnMut, etc #16640 -- Implement unboxed closure upvar inference
• Unboxed closure: infer move when passing an unboxed closure to Fn* + Send #18799 -- Infer move using Send trait
• |&mut:| wants (Copy) upvar to be mutable when it shouldn't #16749 -- |&mut:| wants (Copy) upvar to be mutable when it shouldn't
• Bad type inference error message with unboxed closures #17881 -- Bad type inference error message with unboxed closures
• Finalize unboxed closure feature gates for 1.0 #18875 -- Adjust feature gates
• Lifetimes in closure return values are inferred to be 'static, unlike with functions #17908 -- clarify lifetimes in closure return type syntax
• by-ref closure capture semantics are a backwards compatibility hazard #12831 -- by-ref closure capture semantics are a backwards compatibility hazard
• Implement higher-ranked trait bounds #17661 -- Implement higher-ranked trait bounds
• Remove old (boxed) closures from the language #14798 -- Remove old (boxed) closures from the language
• Fn trait hierarchy not respected #18387 -- Fn trait hierarchy not respected
• Parentheses notation should respect lifetime elision #18992 -- Parentheses notation should support lifetime elision
• Unboxed closure types are implicitly copyable #19817 -- unboxed closures should not be implicitly copyable
• Unboxed closure trait references should pretty print with parenthesized notation #19836 -- should pretty-print with parenthesized notation
• HRTB rules do not permit "perfect forwarding" of the Fn traits #19730 -- "perfect forwarding" traits are not accepted by HRTB
• ICE on generic type inference failure for unboxed closures #17551 -- ICE on generic type inference failure for unboxed closures
• ICE using explicit lifetime with unboxed closures #17545 -- ICE using explicit lifetime with unboxed closures
• ICE fictitious type O in sizing_type_of() #17060 -- ICE fictitious type O in sizing_type_of()
• ICE when using unboxed closures #17021 -- ICE when using unboxed closures
• ICE calling an unboxed closure with the wrong number of parameters inside another closure #16939 -- ICE calling an unboxed closure with the wrong number of parameters inside another closure
• Unboxed closures ICE when debug println!()d #16808 -- Unboxed closures ICE when debug println!()d
• Internal compiler error related to sizing of unboxes closures #16791 -- ICE related to sizing of unboxes closures
• Internal compiler error in metadata::tydecode::parse_def_id related to unboxes closures #16790 -- ICE in metadata::tydecode::parse_def_id related to unboxes closures
• Running into segmentation fault with new closures #16774 -- Running into segmentation fault with new closures
• ICE: When creating Box<FnOnce<(), ()>> from unsugared unboxed closure #16739 -- ICE: When creating Box<FnOnce<(), ()>> from unsugared unboxed closure
• ICE returning unboxed closure #16672 -- ICE returning unboxed closure
• internal compiler error #18057 -- internal compiler error
• Unboxed closure ICE: cannot relate bound region: ReInfer(16) <= ReLateBound #17816 -- Unboxed closure ICE: cannot relate bound region: ReInfer(16) <= ReLateBound
• Unboxed closures ICE: Expected(expected EBML doc with tag EsEnumVid but found tag 27) #18378 -- Unboxed closures ICE: Expected(expected EBML doc with tag EsEnumVid but found tag 27)
• Unboxed closure + traits bug #18453 -- Unboxed closures and traits ICE
• ICE with lifetimes and associated types #20582 -- normalization failure in return type in impl
• Aliasing rules are broken for closures #17403 -- Aliasing rules are broken for closures
• Struct + Fn fulfills Send, but sugary version |&: ...| does not #16560 -- Struct + Fn fulfills Send, but sugary version |&: ...| does not
• Cannot call a unboxed-closure trait object with () syntax #16929 -- Cannot call a unboxed-closure trait object with () syntax
• Overloaded call notation doesn't work with trait bounds #18385 -- Overloaded call notation doesn't work with trait bounds
• Unboxed closures: ref-prefixed closures still capture by value #16814 -- Unboxed closures: ref-prefixed closures still capture by value
• Unboxed closures: cannot borrow data mutably in aliasable location #16668 -- Unboxed closures: cannot borrow data mutably in aliasable location
• Function pointers should implement the various Fn* types #17961 -- Function pointers should implement the various Fn* types
• Unboxed closures: Type inferencer failed to detect closure argument types #17907 -- Unboxed closures: Type inferencer failed to detect closure argument types
• unboxed closure sugar not working in trait objects #17703 -- unboxed closure sugar not working in trait objects
• Box<Fn(int) -> int + 'static> is not accepted: "explicit lifetime bound required" #18772 -- Box<Fn() + 'static> not accepted

[aturon]

cc @pcwalton @nikomatsakis

[japaric]

Re: #14798 -- Remove old (boxed) closures from the language

Are we going to replace all the uses of boxed closures in the standard library with unboxed closures? I think that in some cases it may not be doable (*) without abstract return types (ART). Let me explain why with a (rather long) story:

(*) Ok, it may be doable, but tedious. See alternatives section at the bottom:

---

I was navigating ancient issues today, and found #12677: "std::str::Bytes should implement Clone". So I decided to investigate why string.bytes() wasn't cloneable:

The bytes method returns an iter::Map which can't implement clone. This is the current definition of iter::Map:

#[deriving(Clone)]
struct Map<'a, A, B, I> {
    iter: I,
    f: |A|:'a -> B,  //~ error: type `|A| -> B` does not implement any method in scope named `clone`
}

So, my first attempt at a solution was: "Let's change Map to use unboxed closures":

#[deriving(Clone)]
struct Map<A, B, I: Iterator<A>, F: FnMut(A) -> B> {
    iter: I,
    f: F,
}

impl<A, B, I: Iterator<A>, F: FnMut(A) -> B> Iterator<B> for Map<A, B, I, F> {
    fn next(&mut self) -> Option<B> {
        self.iter.next().map(|elt| self.f.call_mut((elt,)))
    }
}

Which compiles fine, it's cloneable and should work in principle, but when I tried to replicate the bytes method, I found a more serious problem:

fn bytes<'a>(slice: &'a str) -> () {
    Map {
        iter: slice.as_bytes().iter(),
        f: |&mut: &b| b,
    }
}

I wrote () as the return type to make the compiler tell me what's the actual return type:

error: mismatched types: expected `()`, found `Map<_, _, core::slice::Items<'_, u8>, closure>` (expected (), found struct Map)

Note the 4th specialization argument of Map: closure. I realized that this function is impossible to define because the return type can't be "named", in particular the unboxed closure has an anonymous type.

If we had ART, then the return type could be Map<&'a u8, u8, slice::Items<'a, u8>, impl <'a> FnMut(&'a u8) -> u8, or more succinctly, just: impl Iterator<u8>.

---

Alternatives

Since we don't have ART, here are a few alternatives for the particular case of the bytes method:

• Make bytes return a Bytes struct that implements Iterator<u8>. This basically bypasses the use of unboxed closures, buts add yet another struct to the library.
• Create a DerefCopy struct that implements the general |:&mut &t| t operation, and change the return type of bytes to Map<_, _, _, DerefCopy>. The DerefCopy could be used in some other places of the stdlib.

---

@aturon This is relevant to the library stabilization process:

• As part of the stabilization of std::iter, are we going to fully move to unboxed closures?
• If yes, how do we dealt with these cases where the return type that can't be named?
• Are we going to stabilize functions that return iterator adapters? Or perhaps should we mark them as [unstable = "return type may change"] to account for the introduction of ART in the future.

[aturon]

@japaric Note that you will be able to use "unboxed closures" in boxed form, something like: Box<Fn(uint) -> uint> for example. For library stabilization, we will be switching all APIs currently using closures to use the new closure system, but they will not necessarily all be boxed.

This is just the usual tradeoff between generics (with specialization) and trait objects (with dynamic dispatch). Right now, since we don't have abstract "unboxed" return types, anything returning a closure will have to use the trait object (boxed) form.

Put another way, "unboxed closures" is really an unfortunate misnomer. What's really changing is that closures are going away as a "special" thing, and instead being replaced by use of the existing trait system. That means you can choose to use them in both boxed and unboxed forms.

As we've been stabilizing APIs, we've been leaving anything that uses closures as #[unstable] for this reason. We'll be making a sweep later and determining which kinds of closures to use once the feature is ready.

[japaric]

Note that you will be able to use "unboxed closures" in boxed form, something like: Box<Fn(uint) -> uint> for example.

I'm aware that we can still use boxed closures, but it seemed a rather bad idea to use a boxed closure for the bytes method, hence I didn't listed it under the alternatives.

As we've been stabilizing APIs, we've been leaving anything that uses closures as #[unstable] for this reason.

Since we have to stabilize (as in mark as #[stable]) most of stdlib so it can be used on the stable/beta channels, does this mean well have to make tradeoffs like this one:

• Make bytes return Map<_, _, _, Box<Fn(_) -> _>, which uses boxed closures and its bad for performance, or
• Make bytes return Bytes (which would also need to be marked stable), where Bytes implements Iterator<u8>, which means we'll fill stdlib with more one use structs

right? (FWIW, I prefer the latter option wherever possible)

[alexcrichton]

In this case Box<Fn(..)> may not be that bad because a 0-sized allocation (there's no environment for most of these functions) costs nothing. We may also be able to get away with &'static Fn(..) depending on how much trans wants to cooperate (in theory).

[japaric]

In this case Box<Fn(..)> may not be that bad because a 0-sized allocation (there's no environment for most of these functions) costs nothing.

Doesn't each call still has to go through the trait object tough? Or is LLVM able to optimize it to a function call (or maybe even better: inline it away)?

[alexcrichton]

Yes, but that's precisely what happens today (relying on LLVM to inline), as in all closures are boxed today.

[TeXitoi]

At worst, if you want to return an unboxed closure, you can write the struct by hand and not rely on the syntaxic sugar. It correspond to your DerefCopy alternative. And you can write polymorphic closure! http://is.gd/iqdHfp

[cristicbz]

Found two more ICE-s today: #18652 (to do with move capture) and #18661 (to do with passing Fn-s as args).

[cristicbz]

A whole bunch of these bugs have been fixed:

ICE-s
#16790
#16774
#18378
#18453

Other bugs
#17703

[carllerche]

Infer move using Send trait: #18799

[abonander]

Can check off #17661. HRTB landed today.