CancelToken.race and propagation of cancelation signals

[domenic]

A new design constraint has come up when working to ensure that cancel tokens are a general enough mechanism to serve as the cancelation primitive for not only promises, but also other parts of the language, such as the proposed observables. It is essentially the following:

let cancel1, cancel2;
const ct1 = new CancelToken(cancel => cancel1 = cancel);
const ct2 = new CancelToken(cancel => cancel2 = cancel);

const ct3 = CancelToken.race([ct1, ct2]);
cancel1(reason);

console.assert(ct3.reason === reason);

As currently specced, this assert will fail, as the reason will be asynchronously propagated from ct1 to ct3. (Note that if the cancel1(reason) call were before the race, the assert would succeed, due to the synchronous probing performed by CancelToken.race. But that is not sufficient, I have recently learned.)

---

One way of approaching this problem is to ask: how do other compositional cancelation mechanisms handle this? For example, consider something like .NET's cancel tokens, which use an ad-hoc subscription protocol with synchronous notification, instead of using promises. There, the composition code would look something like this, translated into JavaScript terms but using .subscribe instead of .promise.then:

function dotNetCTRace(cts) {
  return new CancelToken(cancel => {
    for (const ct of cts) {
      ct.subscribe(reason => cancel(reason));
    }
  });
}

Using "classic observables", EventEmitter/EventTarget, or any other subscription mechanisms works analogously. In all cases, the answer is that each raced cancel token takes a reference to the returned cancel token (often indirectly, via a closure stored in their list of reactions), and becomes responsible for synchronously pushing the result to the returned cancel token upon cancelation. In short: input cancel tokens take a reference to output cancel token which they push a reason to.

---

Taking this design to heart, I think we want to modify the CancelToken proposal to follow this path. However, we should still preserve the surface API of .promise.then as the necessarily-asynchronous mechanism of communication. This preserves the benefits of the .promise API: reusing familiar primitives for single-time occurrences, and avoiding plan interference attacks in the usual way that promises do.

The proposal is then that all cancel tokens get an internal slot, [[FollowerCancelTokens]], which contains a List of cancel tokens that are "followers" this one, such that if this token becomes canceled with reason r, immediately and synchronously all such follower tokens should also become canceled with reason r. Then the cancel token cancel function (passed to the constructor) no longer is simply the promise resolver, but instead is something specialized that both resolves the internal promise and pushes the value to any follower cancel tokens.

This mechanism is only used by CancelToken.race, which may seem strange or limiting. However, consider what it would mean to generalize it. Perhaps the most general thing one could imagine is ct1.addFollower(ct2). But we should only give this capability to the creator of ct2, since it is important that only the creator is able to transition ct2's state. So in the end, what we get is ct2 = CancelToken.race([ct1]). The most general thing possible is recovered from CancelToken.race itself.

---

Another interesting thing to note is that the dotNetCTRace combinator, or any similar combinator based on classic observables or the like, is actually not as efficient as the [[FollowerCancelTokens]] design could potentially be. That is because dotNetCTRace necessarily creates a strong reference from each of the input cancel tokens to the output cancel token. Even if the output cancel token is discarded by the program, it will live forever as long as the input cancel tokens live. With the [[FollowerCancelTokens]] design, this is not necessarily the case: a native implementation could make [[FollowerCancelTokens]] a list of weak references, and thus prevent the input cancel tokens from keeping the output cancel token alive. I'm not sure this is feasible or desirable in implementations, as in general weak references have performance costs, but it's at least an interesting option to note.

---

A final thing worth noting is that with this framework an implementation could lazily instantiate [[CancelTokenPromise]] upon the first get of cancelToken.promise (or use of await.cancelToken). Especially for cancel tokens used in observables, this might be a worthwhile optimization, which would reduce them to essentially lightweight holders for cancel reasons, plus in compositional cases references to followers.

[bergus]

All cancel tokens get an internal slot, [[FollowerCancelTokens]], which contains a List of cancel tokens that are "followers" this one, such that if this token becomes canceled with reason r , immediately and synchronously all such follower tokens should also become canceled with reason r .

That would be one possible implementation, to synchronously cancel everything that depends on the token. But this approach is quite limited when it comes to token compositions other than race.

Instead I would make .requested a getter that synchronously evaluates the states of the dependencies of the token. This way, we get the state immediately, but lazily (only when accessed). The "active" propagation of the cancellation signal (calling listeners) would still be asynchronous (with all the benefits you talked about).

make [[FollowerCancelTokens]] a list of weak references, and thus prevent the input cancel tokens from keeping the output cancel token alive. I'm not sure this is feasible or desirable in implementations.

I would consider this an absolute necessity even, see #52

[benjamingr]

Instead I would make .requested a getter that synchronously evaluates the states of the dependencies of the token. This way, we get the state immediately, but lazily (only when accessed). The "active" propagation of the cancellation signal (calling listeners) would still be asynchronous (with all the benefits you talked about).

This was deemed unacceptable - see https://github.com/tc39/proposal-observable/issues/112#issuecomment-250196468

[benjamingr]

@domenic this indeed solves the problem but I'm wondering if we're not overcomplicating things - now all tokens need to be aware of other tokens which they might be following.

I don't see any other solution given the current design - but I'm wondering if we shouldn't allow synchronous subscription and be over with it.

[domenic]

this indeed solves the problem but I'm wondering if we're not overcomplicating things - now all tokens need to be aware of other tokens which they might be following.

This is already the case, it's just indirected through [[CancelTokenPromise]].[[FulfillReactions]] + a closure per follower.

[bergus]

@benjamingr

This would be unacceptable for performance reasons: "reason" must be O(1)

That can still be achieved by using Domenic's approach with synchronous propagation as a native optimisation for builtins like Promise.race, but should not prevent us from considering the getter approach for the more general cases. We could spec the perf requirements just like for collections. In fact, I believe a getter function that is supplied (and controlled) by the creator of the token is the only viable approach for generic (userland) token composition that allows immediate "propagation" (which is actually lazy evaluation in this case) without making callbacks synchronous, which we don't want for obvious reasons.

[zenparsing]

A final thing worth noting is that with this framework an implementation could lazily instantiate [[CancelTokenPromise]] upon the first get of cancelToken.promise

Another arrangement of the ideas would be to have the cancel token be an instance of Observable with a promise getter:

class CancelToken {
  // ...

  get promise() {
    if (this._promise) {
      return this._promise;
    }
    return this._promise = new Promise(resolve => this.subscribe(resolve));
  }

  // ...
}

Is that not a more natural way to express it?

And then the race implementation is trivial (as in dotNetCTRace) and requires no magic.

[domenic]

I don't find that more natural, no.

[zenparsing]

Does it make sense to build a type which apparently requires synchronous propagation on top of a type which only allows asynchronous propagation?

[domenic]

I think by using the word "propagation" you're conflating two different things: notification and inspection.

IMO the fact that promises don't provide synchronous inspection is a historical accident born of committee exhaustion due to the great monad wars of 2013; if we'd had more budget for promise features (as opposed to promise debates) that surely would have gotten in, alongside other things that are only now making their way through the standards process like Promise.prototype.finally. So I think synchronous inspection is something promises provide just fine, even if right now there doesn't happen to be a public API for it.

Synchronous notification, indeed, is not provided by promises. But as discussed, that's not necessary for cancel tokens. Synchronous inspection suffices for all the propagation needs.

[zenparsing]

a native implementation could make [[FollowerCancelTokens]] a list of weak references, and thus prevent the input cancel tokens from keeping the output cancel token alive

I'm not sure we can do that.

var source = CancelToken.source();
var f = function() { console.log('foo') };
var raced = CancelToken.race([source.token]);
raced.promise.then(f);
// Drop references
raced = null; f = null;
// Do GC!
// Now, presume that "source.token" does not reference "raced"
source.cancel();
// "foo" is *not* logged

I think it would be quite surprising if "foo" were not logged here. Thoughts?

[zenparsing]

For cross-reference, here is a fleshed out counter-proposal for making cancel tokens observable, instead of introducing magic to Promise.race:

https://github.com/zenparsing/es-observable-cancellation