Cancellation Tokens (and Collapsing Futures) for Objective-C

Cancellation Tokens (and Collapsing Futures) for Objective-C

In this post: benefits of cancellation tokens, and updates about the Collapsing Futures library.

Cancellation Tokens

Sometimes you want to cancel asynchronous operations. For example, when a user closes a browser tab before it finishes loading a web page, it is expected that the browser will immediately stop fetching that page (as opposed to letting the fetch finish and discarding the result, which is often simpler to implement).

There are many techniques for cancelling operations, but my preferred mechanism is cancellation tokens. A cancellation token is an object that propagates cancellation notifications. To be cancelled by a cancellation token, an asynchronous method registers cleanup callbacks to run when cancellation has occurred (or manually checks if the token has been cancelled at the appropriate times). To cancel an asynchronous method, the caller of that method just cancels the token they passed to it.

The main strength of cancellation tokens over other cancellation mechanisms, such as returning a cancellable result, is that they make ‘wiring’ easier. Usually you can just pass along the token you were given by your caller to the methods you call, and they will cancel at the appropriate time.

For example, suppose you’re writing a method that crawls a website. The crawling continues until the cancellation token given to it is cancelled. How does the crawling operation ensure that, when it’s cancelled, any outstanding page loads are also cancelled? By just passing along the cancellation token, like this:

-(void) crawl:(NSString*)site until:(TOCCancelToken*)untilCancelledToken {
    ...
        Future* futurePage = [self asyncLoadPage:page unless:untilCancelledToken];
        ...
    ...
}

Now compare the above snippet with the following snippet, showing what needs to be done if cancellation is instead attached to the result of the method:

-(Cancellable*) crawl:(NSString*)site {
    NSMutableSet* activeCancellables = [NSMutableSet set];
    ...
        CancellableFuture* cancellableFuturePage = [self asyncLoadPage:page];
        [activeCancellables addObject:cancellableFuturePage];
        ...
            [activeCancellables removeObject:cancellableFuturePage];
            ...
        ...
    ...
    return ^{
        ...
        for (Cancellable* cancellable in activeCancellables) {
            [cancellable cancel];
        }
    };
}

That’s a pretty significant difference. With cancellation tokens, each method takes care of its own cancellation. With cancellable results, the cancellation duties are leaking into the caller (because it needs to track where to propagate cancellations to).

Another situation, where cancellation tokens provide a benefit over the alternative, is removing event handlers. I discussed this more generally in my post on perishable collections. Using an IncludeHandlerUntil method, instead of AddHandler and RemoveHandler methods, makes it a lot harder to forget to remove a handler and impossible to accidentally remove a handler twice.

I’ve implemented cancellation tokens as part of the Collapsing Futures library I’ve been working on. In the library, cancellation tokens are represented by instances of TOCCancelToken and controlled by corresponding instances of TOCCancelTokenSource.

Cancelling Timeouts

Let’s try to perform a simple task using cancellation tokens: calling a method after a delay, unless cancelled first. Perhaps we want to show a notification that auto-dismisses after a few minutes, but if the user manually dismisses it we don’t want to hog resources we don’t need (like whatever the delayed callback is referencing and thus keeping alive).

Objective-C has existing ways to run code after a delay, so we just need to translate:

+(void) runBlock:(VoidBlock)callback
      afterDelay:(NSTimeInterval)delayInSeconds
          unless:(TOCCancelToken*)unlessCancelledToken {

    BlockToSelectorAdapter* blockAsRunObject = [BlockToSelectorAdapter runBlock:callback];
    NSTimer* timer = [NSTimer timerWithTimeInterval:delayInSeconds
                                             target:blockAsRunObject
                                           selector:@selector(run)
                                           userInfo:nil
                                            repeats:NO];
    // Simplification: assuming the current run loop is being run
    [[NSRunLoop currentRunLoop] addTimer:timer forMode:NSDefaultRunLoopMode];
    
    // Simplification: assuming the cancellation token is not long lived (will discuss)
    [unlessCancelledToken whenCancelledDo:^{
        [timer invalidate];
    }];
}

The above method is straightforward: setup an NSTimer in the usual way, using a helper class that allows us to call the callback block as a selector, but invalidate the timer if the token is cancelled. It uses the whenCancelledDo method of TOCCancelToken to make the block that invalidates the timer run when the token is cancelled. (If the token starts off cancelled, the block is just run right away.)

(We can also use Grand Central Dispatch to do the delay but, as far as I know, it doesn’t have any mechanism to cancel a delayed callback. At best we can do a hacky partial cancel.)

The hypothetical notification-showing problem I mentioned at the top of this section can be solved with our delayed-callback method as follows:

// in NotificationViewController.m
+(void) show {
    NotificationViewController* view = ... init view ...;
    view->cancelledWhenDismissedSource = [TOCCancelTokenSource new];
    ... show view ...
    [TimeUtil runBlock:^{ [view goAway]; } 
            afterDelay:120.0 //seconds
                unless:cancelledWhenDismissedSource.token];
}
-(void) onManuallyDismissed {
    [cancelledWhenDismissedSource cancel];
    [self goAway];
}
...

Note that, given how we implemented our delayed-call method, the above snippet is assuming it’s safe to call goAway twice. The delay might finish just as onManuallyDismissed is about to cancel it, resulting in an extra call to goAway being queued into the run loop. We could improve our delayed-call method by wrapping the callback to check the cancellation token’s isAlreadyCancelled property one last time before running, which would fix these ‘races despite being on same thread’ issues.

There’s also another issue with our delayed-call method: it has a space leak.

Cancelling Cancellation

Consider what happens to the ‘invalidate timer’ block our delayed-call method registers when cancellation doesn’t occur. We’re not doing anything to get rid of that block if it isn’t used, so it just sticks around in the cancellation token’s array of cancel handlers to call. If we keep conditioning delayed callbacks on the same cancellation token, but never get around to cancelling the token, we’ll accumulate arbitrarily many of these blocks. We’ve got a space leak!

To fix this space leak, we need the ability to remove the handlers we registered to be called upon cancellation. We need to be able to cancel cancellation.

TOCCancelToken supports exactly this functionality. The method whenCancelledDo:unless: takes a cancel handler to run, and a second cancel token that removes that handler if the second token is cancelled before the receiving token.

(Incidentally, whenCancelledDo:unless: is line for line one of the hardest methods I’ve ever written. I’m not sure why, since it doesn’t look that hard… But if you’re looking for a challenge: clone the repo, paste this redacted version of TOCCancelTokenAndSource.m over the actual TOCCancelTokenAndSource.m, and try to get the tests passing again.)

With our cancelled-unless-other-cancelled method in hand, we can fix our space leak. Let’s go a bit further, and take advantage of the convenient cancelledOnCompletionToken property on TOCFuture (returns a token that becomes cancelled once the future completes), and modify our delayed-callback method into a delayed-result method:

+(TOCFuture*) futureWithResult:(id)resultValue
                    afterDelay:(NSTimeInterval)delayInSeconds
                        unless:(TOCCancelToken*)unlessCancelledToken {
    
    TOCFutureSource* resultSource = [TOCFutureSource new];
    BlockToSelectorAdapter* blockAsRunObject = [BlockToSelectorAdapter runBlock:^{
        [resultSource trySetResult:resultValue];
    }];
    NSTimer* timer = [NSTimer timerWithTimeInterval:delayInSeconds
                                             target:blockAsRunObject
                                           selector:@selector(run)
                                           userInfo:nil
                                            repeats:NO];
    [[NSRunLoop currentRunLoop] addTimer:timer forMode:NSDefaultRunLoopMode];
    
    [unlessCancelledToken whenCancelledDo:^{
        [timer invalidate];
        [resultSource trySetFailedWithCancel];
    } unless:resultSource.future.cancelledOnCompletionToken];
    
    return resultSource.future;
}

We can easily run callbacks after a delay by thenDo‘ing off of the future produced by this method. We can also determine whether or not the delay finished without being cancelled based on the future containing the result we specified, or a cancellation failure.

Until Cancellation

So far I’ve only been talking about cancelling ongoing operations, or undoing operations, but we can also use cancellation tokens to clean up objects.

For example, I have socket classes where the ‘start’ methods (or the constructor methods) ask for a cancellation token. When the token is cancelled, the socket is closed. That way, when an asynchronous operation uses a socket, the entirety of making sure things get cleaned up is… passing along a token.

By cleaning up objects with cancel tokens, you can re-use the same token that was going to cancel an operation to instead dispose its result. Instead of an operation producing a result unless we cancel a token beforehand, an operation can produce a result that lasts until we cancel a token. I call these operations ‘unless-style’ and ‘until-style’, and in the library I always distinguish between them by the name of the cancel token parameter.

For example, the method asyncRaceOperationsWithWinningResultLastingUntil that I added to NSArray is an ‘until’-style method (that’s why it has ‘until’ instead of ‘unless’ in the name). This drastically simplifies how it’s implemented and how it’s used.

asyncRaceOperationsWithWinningResultLastingUntil takes an array of blocks corresponding to ‘until’-style asynchronous operations, runs them all to get the futures representing their results, and propagates the first finished result into the future it returned to its own caller. Once a race has a winner, all the losers can be cancelled without worrying if they’ve finished or not (because the operations are ‘until’). The winning result lasts until the caller cancels the token they originally passed in.

How is this method useful? Well, I wrote it as part of implementing ‘low latency connecting’, where you start several connections at the same time and only keep the first to finish. Assuming you have a class for handling tcp streams, designed with cancel tokens in mind, you can do a low latency tcp connection in under ten lines of code:

+(TOCFuture*) asyncLowLatencyConnectAmong:(NSArray*)ips until:(TOCCancelToken*)untilCancelledToken {
    NSArray* streamStarters = [ips forEachEval:^(IPAddress* ip) {
        return ^(TOCCancelToken* racerUntilCancelledToken) {
            TcpStream* tcpStream = [TcpStream tcpStreamTo:ip until:racerUntilCancelledToken];
            return tcpStream.futureSelfWhenHandshakeCompleted;
        }
    }];

    return [streamStarters asyncRaceUntilCancelled:untilCancelledToken];
}

That’s pretty sweet. Also, since the racing bit has been separated from the networking bit, it’s a whole lot easier to test.

Timing Out Unless and Until

Another benefit of having a method with until cancellation semantics, instead of unless semantics, is that timing out works a bit better.

The constructor method futureWithResultFromAsyncCancellableOperation:withTimeout:unless: returns the result of an asynchronous operation, but cancels the operation if it takes too long. Unfortunately, it can’t assume the caller doesn’t need to clean up the result of the operation and it doesn’t know how to clean up the result itself. So, when timeout occurs, it can’t immediately report that timeout. It needs to wait for the asynchronous operation it started to confirm it was cancelled (i.e. for its future to fail). Otherwise it would be possible for the operation’s success to race the cancellation, ending with a result that can’t be reported to the caller to be cleaned up because a timeout was already reported.

So, if you happen to pass in a badly written operation that hangs instead of cancelling, the timeout operation will hang too! I might actually cut this method from the library (before v1.0), because of this stupid failure case.

There’s another timeout method in the library: futureWithResultFromAsyncOperationWithResultLastingUntilCancelled:withOperationTimeout:until:. This one actually does immediately fail when it times out, which it can do safely because it knows how to clean up any spurious result: cancel the token given to the operation that created the result.

Dependent Cancellation

Sometimes an asynchronous operation will do more than just pass along a cancellation token. It’s somewhat common to want to add new ways for sub-operations to be cancelled. For example, asyncRaceOperationsWithWinningResultLastingUntil will cancel sub-operations when the token you give it is cancelled or one of the operations has won.

This is common enough that the library includes the constructor method cancelTokenSourceUntil for TOKCancelTokenSource. The cancel token source returned by cancelTokenSourceUntil will be automatically cancelled if the token given to the constructor method is cancelled. The created token source’s token lifetime is thus dependent on the given token not being cancelled.

Library News

That about covers the high level view of cancellation tokens, so on to news about the library.

Two weeks ago the Collapsing Futures library had bare bones futures and nothing. I was a bit surprised there was any feedback at all, let alone positive feedback with useful suggestions. Now the library is something I’ve put some serious design and implementation effort into (also it has a podspec now). I’ve worried about more details than I can list, and I’m looking for more feedback:

• What features are missing? (e.g. it still needs a nice way to get back on the main thread)
• Is the auto-complete documentation (e.g. what’s on cancel token) sufficient? Useful? Confusing?
• Is the API easy to discover and intuit? Are things where they should be? What would make it clearer?
• Have you encountered any bugs? Any mis-features?
• What are your use cases?
• What async tasks should the library translate into future-style? (e.g. should the library implement asyncGetAddressBook)

It’s okay if you just care deeply about the color of a bike shed. I’ll still take it under consideration. I’m new enough to the conventions of Objective-C that I might legitimately not know some trivial expectation.

You can leave feedback here, on github, on reddit, or send it by email. Whatever works best.

I have a couple more posts planned that are related to the collapsing futures library. Next week I’ll talk about how I used immortality states to prevent self-sustaining reference cycles.

Summary

Cancellation tokens make cleaning up a lot easier, allowing each method/component to deal with just its own cancellation while passing along the token to things it uses.

Cancellation tokens are implemented, in Objective-C, by the Collapsing Futures library.

Discuss on Reddit

My Twitter: @CraigGidney

Comments are closed.

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive