Add one-shot closures

[eholk]

It's currently really hard to use noncopyable data with things like vec::each or uint::range, since the type system doesn't know how many times these functions will invoke their closures. It'd be nice to have some way for the compiler to know that a closure will be called at most once, so it can be safe to move out of upvars in these closures.

[nikomatsakis]

a long time back I blogged about some thoughts in this direction. I still think this makes sense; it seems like the use cases are a bit clearer now than they were then. Interestingly, vec::each() and uint::range() don't seem like good examples, but things like the calls to swap() in dvec are much more troublesome.

[catamorphism]

Marking as RFC.

[eholk]

We had some discussion about this a while ago and it seems like we might be able to do this with just the kinds on the closure. It will require some type system tweaks though.

[bblum]

Can it be at most once, or does it have to be exactly once? I favour this - the call-exactly-once pattern is quite common.

For example, is this ok?

let x = noncopyable();
do some_option.iter |maybe_value| {
    ... move x ...
}

[catamorphism]

+1. GHC has a notion of "one-shot lambdas", too, fwiw.

[eholk]

I think there's probably cases where we would want both "at least once" and "at most once."

At least once:

let mut x;
do some_option.iter |y| {
    x = y;
}

At least once guarantees that x is initialized after the call to some_option.iter. (Obviously option::iter would not be able to use the "at least once" restriction)

With at most once, we gain the ability to move out of a closure during the function call.

Also, with both at most once and at least once we can have exactly once too.

[nikomatsakis]

I think "at least once" is going to be somewhat tricky. We have to think about what it means, e.g., to fail when you have not executed such a closure. Our lack of recoverable exceptions should help here though. I guess it means that the closure cannot be dropped except in the case of failure? Still, it makes me nervous. At most once seems much closer to what we have.

[bstrie]

Nominated so that Cell becomes less necessary.

[nikomatsakis]

This is partly implemented. I believe the type system support is generally ok but there is no integration with liveness and trans. The most straight-forward way to update liveness is to modify it into a forward-propagating system (most of the infrastructure for which is being added for borrowck). Forward propagation means that it will be hard to emit existing warnings regarding dead assignments, unless we keep the existing liveness code around just for that purpose. In a meeting it was discussed moving to a control-flow graph for this purpose: I think this is a good long-term plan but I found the design constraints somewhat non-obvious so decided to defer until a first version of #5074 is done. (In particular, if we do a plain-jane CFG, we could probably use it for data-flow but not much else, whereas a somewhat more advanced CFG could simplify liveness, borrow checker, trans and numerous other passes by making explicit some of the implicit transformations that take place today such adjustments, for loop closures, etc)

[graydon]

While this looks like "just an addition", it'll probably change all library APIs, so it's a backwards compatibility hazard.

[bblum]

I don't think it's a backwards compatibility hazard... a library with once on some of its argument closures would permit strictly more code to link against it than the same library without.

The only place once could be more restrictive is in a covariant position (in a 3rd-order, or any higher odd-numbered order, function). For example, if you had:

fn foo(arg: fn(callback: once fn())) {
    let x = NonCopyable;
    do arg { move_out_of(x); }; // requires arg's argument to be 1-shot, to move out
}

Then you couldn't use it with:

fn bar() {
    do foo |callback| {
        callback();
        callback();
    }
}

But, if you ship rust-1.0 without once, then no such library function foo can exist that relies on the once-ness of its argument's argument.

[bblum]

By the way, what do y'all think of a compiler warning to warn when an argument closure is not declared once, but only called once? It could be off by default, but enabled for libstd and libextra, to make our libraries higher quality.

The possible problem would be if you had a function that currently only called a function once but didn't want to provide that guarantee to the caller. So there would have to be a way to squelch the warning without taking its suggestion.

e.g.:

fn chain<T>(x: Option<T>, blk: fn(T) -> Option<T>) -> Option<T> {
    match x { Some(x2) => blk(x2), None => None }
}

would produce something like warning: argument closure is only called once; please write "once fn" or use #[allow(non_once_fn)].

[bblum]

I went through the libraries and looked for use cases where one-shot closures would let us avoid using Cells specifically in the case of stack closures, assuming heap closures get replaced by traits, in an attempt to motivate needing one-shot functions anyway. Results are as follows:

in scheduler:
        Local::borrow::<Scheduler>() -- 11 once uses (19 total)
        deschedule_running_task_and_then -- safety guarantee, plus 4 once uses (23 total)
assorted libraries:
        exclusive.with -- 3 uses
        arc/semaphore/mutex/rwlock access() -- 3 uses
        Finally's do ... finally ... pattern -- 1 once use (21 total)
        task::unkillable -- 1 once use (27 total)
in servo:
        fn profile -- 2 once uses (11 total)
        fn with_imm_text in AbstractNode -- 1 once use (2 total)

[bblum]

When stack closures become noncopyable, fn indent in librustc wants this too.