2650. Design Cancellable Function

Problem Description

In this problem, we are tasked with creating a cancellable asynchronous process. We need to write a function called cancellable that accepts a generator object. The generator is expected to yield promises, representing asynchronous operations. The function cancellable should return an array of two values: a cancel function and a promise that corresponds to the asynchronous operations of the generator.

Here's the behavior we need to implement:

1. Handling Promises: The function will consume the yielded promises from the generator, passing the values resolved by the promises back to the generator. If a promise rejects, the function must throw the error back to the generator.

2. Cancellation: The cancel function, when called, should stop the generator from running further and throw a specific error ("Cancelled") back into the generator. If the generator catches this error, the outer promise (returned by cancellable) should resolve with the next value from the generator, if available. If it doesn't catch the error, the promise should reject with the thrown error.

3. Completion: If the generator completes its process successfully without being cancelled, the promise should resolve with the final returned value from the generator. On the flip side, if the generator throws an error, the returned promise should reject with that error.

As an example, when using the provided tasks generator function, if the cancel function is called before the generator completes, it results in the promise rejecting with "Cancelled". Otherwise, if cancel is not called or called after the generator completes its process, the promise should resolve with the calculated value.

Intuition

The solution to the problem necessitates an understanding of JavaScript ES6 Generators, Promises, and the async/await syntax for handling asynchronous code execution.

The intuition is to create a control mechanism (the cancel function) that competes with the regular execution of the generator. When activated, the cancel function should reject an internal promise (cancelPromise), which interrupts the generator's regular flow.

1. Wrapping the Generator with Async Function: To manage the asynchronous flow, we wrap the generator logic inside an async function, which allows us to use the await keyword to wait for asynchronous operations (Promises) to resolve.

2. Controlling the Flow: The cancel function rejects the cancelPromise, and we use Promise.race to listen to both the current promise from the generator and the cancelPromise. Whichever promise settles first determines the next course of action:

   • If the promise from the generator settles first, we use its value to continue the generator.
   • If the cancelPromise settles first due to the cancel function being called, the generator is interrupted by throwing the "Cancelled" error into it.

3. Error Handling: By employing try-catch blocks, we can handle errors from promises and the generator throwing an error (due to throw(e)). This helps us manage promise rejections and generator errors consistently.

4. Return Value and Promise: Finally, we construct and return an array containing the cancel function and a promise that ultimately resolves to the generator's outcome or rejects if an error is thrown or cancellation occurs.

Solution Approach

The solution implementation details are as follows:

1. Creating Control Mechanisms:

   • A cancel function is declared and later defined within a new Promise called cancelPromise, which only gets rejected when the cancel function is called.
   • The assignment cancel = () => reject('Cancelled') effectively links the calling of the cancel function to the rejection of cancelPromise.
   • A catch is attached to the cancelPromise (cancelPromise.catch(() => {});) to prevent unhandled promise rejections in case it gets rejected before being passed to Promise.race.

2. Handling Generator Execution Flow:

   • The main promise, promise, is created using an immediately invoked async function to handle the asynchronously yielded promises from the generator.
   • A while loop (while (!next.done)) is used to continuously pull values from the generator using next = generator.next(await Promise.race([next.value, cancelPromise]));.
   • Within the loop, Promise.race is used to wait for either the current yielded promise (next.value) or the cancelPromise to settle.
   • If cancelPromise wins the race (when the cancel function is called), the error "Cancelled" is thrown into the generator using generator.throw(e).

3. Error Handling:

   • The try-catch block handles errors that may arise from promises. If a promise is rejected, await will throw an error, which is then caught and thrown back into the generator using generator.throw(e).
   • If the generator catches this error and continues to yield another value, the loop continues. If the generator doesn't catch the error, the next call to generator.next() will result in done being true, and the loop will end.
   • After the generator is done (next.done is true), the value it returned (next.value) is returned as the fulfillment value of the promise.

4. Returning the Output:

   • The function cancellable finally returns an array with the cancel function and the promise.
   • The consumer can use the cancel function to cancel the ongoing generator execution at any point, and the promise to await the result of the generator execution (either resulting from normal completion, cancellation, or an error).

This solution cleverly uses JavaScript's concurrency tools, such as Promises and async/await syntax, alongside generator functions, to create a cancellable asynchronous pattern. The use of Promise.race is particularly noteworthy, as it provides a way to handle the cancellation in a non-blocking fashion alongside normal promise resolution.

Example Walkthrough

Let's take a closer look at how the cancellable function can work using a simple example. Consider we have an asynchronous task that waits for a specified delay and then returns a number. We'll define a generator function that performs a sequence of these tasks.

1// Asynchronous task that resolves after a delay
2function delayedTask(value, delay) {
3  return new Promise(resolve => setTimeout(() => resolve(value), delay));
4}
5
6// Generator function that will yield promises from the delayedTask
7function* tasks() {
8  let result = 0;
9
10  // Wait for 500ms, then add 10
11  result += yield delayedTask(10, 500);
12  // Wait for another 500ms, then add 20
13  result += yield delayedTask(20, 500);
14  // Wait for another 500ms, then add 30
15  result += yield delayedTask(30, 500);
16
17  // Return the accumulated result
18  return result;
19}

Now we will use the cancellable function with this generator. We'll demonstrate what happens when the process completes without cancellation and what occurs when we do cancel the process partway through.

1// Executing the cancellable function with our generator
2const [cancel, promise] = cancellable(tasks());
3
4promise.then(result => {
5  console.log(`Completed with the result: ${result}`);
6}).catch(error => {
7  console.log(`The process was cancelled or rejected with an error: ${error}`);
8});

If we let the promise run to completion without invoking cancel, the console output will be:

1Completed with the result: 60

This output means the generator successfully went through all async tasks, yielding the promises and adding up 10 + 20 + 30 to give us the final result of 60.

Now, let's see what happens if we call cancel() after the first task:

1// Start the process
2const [cancel, promise] = cancellable(tasks());
3
4// Schedule a cancellation after the first delay
5setTimeout(() => {
6  cancel();
7}, 250);
8
9// Listen to the outcome
10promise.then(result => {
11  console.log(`Completed with the result: ${result}`);
12}).catch(error => {
13  console.log(`The process was cancelled or rejected with an error: ${error}`);
14});

With this setup, we've introduced a delay before the second await in the generator could complete. The cancel function is called, the cancelPromise wins the race, "Cancelled" is thrown into the generator, and it results in the following console output:

1The process was cancelled or rejected with an error: Cancelled

This demonstrates the cancellation logic, stopping the generator in its tracks and bypassing the completion of further asynchronous tasks. The above examples should help illustrate the behavior of the cancellable function in handling asynchronous generator processes and providing a mechanism for cancellation.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the cancellable function primarily depends on the number of times the generator yields, the time complexity of each promise resolved within the generator, and the overhead of the operations within the async function that drives the generator. The generator is advanced sequentially, yielding promises that are awaited one after the other.

Assuming the generator yields n promises, and the time complexity to resolve each promise is O(p), then the time complexity of running through the generator is O(n * p). Since we do not control the promises the generator yields, we cannot calculate p for arbitrary promises.

The Promise.race call has a very small overhead, O(1) with respect to time complexity, it simply waits for the first promise to resolve or reject.

Lastly, the try-catch block introduces a constant factor overhead but does not change the asymptotic time complexity.

Thus the total time complexity of the cancellable function is O(n * p).

Space Complexity

The space complexity is determined by the number of promises that can be in memory simultaneously, as well as the memory consumed by the generator's state space.

1. For the generator itself, the space complexity will be O(g), where g captures the local state that is stored across yield points.

2. The Promise.race call does not add any space complexity because it does not create new promises but merely operates on the existing promises referenced by next.value and cancelPromise.

3. The cancelPromise and promise are individual promises and thus represent a constant space overhead O(1).

4. 'try-catch' block - does not increase space complexity.

As a result, the space complexity is O(g), where g reflects the space needed to store the state of the generator between yields.