Facebook Pixel

2650. Design Cancellable Function

Hard
Leetcode Link

Problem Description

This problem asks you to create a function cancellable that takes a generator object as input and returns an array containing two elements: a cancel function and a promise.

The generator function will yield promises throughout its execution. Your cancellable function needs to:

  1. Handle yielded promises: When the generator yields a promise, wait for it to resolve and pass the resolved value back to the generator. If the promise rejects, throw that error back to the generator.

  2. Support cancellation: The returned cancel function, when called, should interrupt the generator's execution by throwing a "Cancelled" string (not an Error object) back to the generator.

  3. Return appropriate results:

    • If the generator completes normally without cancellation, the returned promise should resolve with the generator's final return value
    • If the generator throws an error, the returned promise should reject with that error
    • If cancelled before completion, the behavior depends on whether the generator catches the cancellation:
      • If the generator catches the "Cancelled" error and continues, the promise should resolve with the next yielded or returned value
      • If the generator doesn't catch it, the promise should reject with "Cancelled"

The key challenge is implementing a race condition between each yielded promise and the cancellation. When cancel() is called, any currently pending promise from the generator should be interrupted, and "Cancelled" should be thrown to the generator immediately.

In the provided example, the generator yields two promises - one that resolves immediately with 4, and another that resolves after 100ms. Since cancel() is called at 50ms (during the second promise), the generator receives the cancellation error before completing, causing the returned promise to reject with "Cancelled".

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The core insight is that we need to create a mechanism that can interrupt the generator at any point during its execution. Since generators pause at yield statements and wait for values to be passed back via next(), this is our opportunity to inject cancellation logic.

The key realization is to use Promise.race() to create a competition between two promises:

  1. The promise yielded by the generator (the actual work)
  2. A cancellation promise that will reject when cancel() is called

Think of it like having two runners in a race - whichever finishes first determines the outcome. If the yielded promise resolves first, we continue normally. If the cancellation promise rejects first, we have our cancellation signal.

To implement this, we need:

  • A cancelPromise that starts in a pending state and only rejects when cancel() is called
  • A way to expose the cancel function that triggers this rejection
  • A loop that processes each yielded promise using Promise.race([yieldedPromise, cancelPromise])

The clever part is using a Promise constructor to create both the cancelPromise and the cancel function together:

let cancel;
const cancelPromise = new Promise((resolve, reject) => {
    cancel = () => reject('Cancelled');
});

This gives us a promise that will remain pending indefinitely until cancel() is called, at which point it immediately rejects with 'Cancelled'.

We also need to handle the fact that an unhandled promise rejection would cause issues, so we add cancelPromise.catch(() => {}) to silence any unhandled rejection warnings when the promise is never actually used (if no cancellation occurs).

The main execution flow becomes an async function that:

  1. Calls generator.next() to start/continue the generator
  2. While the generator isn't done, races each yielded promise against cancellation
  3. Passes resolved values back to the generator or throws errors (including cancellation) to it
  4. Returns the final value when the generator completes

Solution Approach

Let's walk through the implementation step by step:

1. Setting up the cancellation mechanism:

let cancel: () => void = () => {};
const cancelPromise = new Promise((resolve, reject) => {
    cancel = () => reject('Cancelled');
});
cancelPromise.catch(() => {});

We create a cancelPromise that will reject with the string 'Cancelled' when the cancel function is called. The empty catch prevents unhandled rejection warnings if cancellation never happens.

2. Creating the main execution promise:

const promise = (async () => {
    let next = generator.next();
    while (!next.done) {
        try {
            next = generator.next(await Promise.race([next.value, cancelPromise]));
        } catch (e) {
            next = generator.throw(e);
        }
    }
    return next.value;
})();

The async IIFE (Immediately Invoked Function Expression) handles the generator execution:

  • Initialize: Call generator.next() to start the generator and get the first yielded value
  • Loop: While next.done is false (generator hasn't finished):
    • Race condition: Use Promise.race([next.value, cancelPromise]) to wait for either:
      • The yielded promise to resolve (normal flow)
      • The cancel promise to reject (cancellation)
    • Success path: If the race resolves successfully, pass the resolved value back to the generator via generator.next(value)
    • Error path: If the race rejects (either from the yielded promise failing or cancellation), catch the error and throw it to the generator using generator.throw(e)
  • Completion: When the loop exits (next.done is true), return the final value from the generator

3. Returning the result:

return [cancel, promise];

Return both the cancel function and the execution promise as a tuple.

Key behaviors:

  • If cancel() is never called, the cancelPromise remains pending forever and never affects execution
  • If cancel() is called while a yielded promise is pending, Promise.race immediately rejects with 'Cancelled'
  • The generator can catch the thrown 'Cancelled' error and continue execution if it has error handling
  • If the generator doesn't catch the error, it propagates up and causes the main promise to reject

This pattern effectively creates an interruptible async iteration over the generator's yielded promises, with clean cancellation semantics.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's trace through a simple example to understand how the solution works:

function* gen() {
    const result = yield new Promise(res => setTimeout(() => res(10), 100));
    return result + 5;
}

const [cancel, promise] = cancellable(gen());
setTimeout(() => cancel(), 50); // Cancel after 50ms

Step-by-step execution:

  1. Initial Setup (t=0ms)

    • cancellable creates a cancelPromise that stays pending
    • Starts the generator: generator.next() → yields Promise(10) after 100ms
    • Enters the while loop since next.done = false

  2. Racing Promises (t=0-50ms)

    • Promise.race([Promise(10), cancelPromise]) begins
    • Two promises are racing:
      • Promise A: Will resolve with 10 at t=100ms
      • Promise B: cancelPromise - currently pending

  3. Cancellation Triggered (t=50ms)

    • cancel() is called
    • cancelPromise immediately rejects with 'Cancelled'
    • Since Promise A is still pending (needs 100ms total), Promise B wins the race

  4. Error Handling

    • Promise.race rejects with 'Cancelled'
    • The catch block executes: generator.throw('Cancelled')
    • Since the generator has no try-catch, it terminates with an error

  5. Final Result

    • The main promise rejects with 'Cancelled'
    • Result: promise rejects with 'Cancelled' at t=50ms

Alternative scenario without cancellation: If we never called cancel():

  • At t=100ms, Promise A would resolve with 10
  • generator.next(10) would be called, passing 10 back to the generator
  • The generator would compute 10 + 5 and return 15
  • The main promise would resolve with 15

This example illustrates the key mechanism: Promise.race creates an interruptible execution where cancellation can preempt any pending operation.

Solution Implementation

1import asyncio
2from typing import Generator, Tuple, Any, TypeVar, Callable
3from concurrent.futures import Future
4
5T = TypeVar('T')
6
7def cancellable(generator: Generator[Future[Any], T, None]) -> Tuple[Callable[[], None], Future[T]]:
8    """
9    Creates a cancellable wrapper for a generator that yields futures.
10    Allows for manual cancellation of the generator's execution.
11  
12    Args:
13        generator: A generator function that yields futures and returns a value of type T
14      
15    Returns:
16        A tuple containing a cancel function and a future that resolves to the generator's return value
17    """
18    # Initialize the cancel function as a no-op
19    cancel_func = lambda: None
20  
21    # Create a future that will be cancelled when cancel is called
22    # This future acts as a cancellation signal
23    cancel_future = Future()
24  
25    def cancel_impl():
26        """Actual cancel implementation that sets exception with 'Cancelled'"""
27        if not cancel_future.done():
28            cancel_future.set_exception(Exception('Cancelled'))
29  
30    # Assign the actual cancel implementation
31    cancel_func = cancel_impl
32  
33    # Main future that handles the generator execution
34    result_future = Future()
35  
36    async def execute_generator():
37        """Async function to handle generator execution"""
38        try:
39            # Get the first iteration result from the generator
40            next_value = next(generator)
41          
42            # Continue iterating while the generator hasn't completed
43            while True:
44                try:
45                    # Create tasks for racing between yielded future and cancellation
46                    yielded_task = asyncio.create_task(asyncio.wrap_future(next_value))
47                    cancel_task = asyncio.create_task(asyncio.wrap_future(cancel_future))
48                  
49                    # Race between the yielded future and the cancellation future
50                    # If cancelled, the cancel_future will raise exception first
51                    done, pending = await asyncio.wait(
52                        [yielded_task, cancel_task],
53                        return_when=asyncio.FIRST_COMPLETED
54                    )
55                  
56                    # Cancel pending tasks
57                    for task in pending:
58                        task.cancel()
59                  
60                    # Get the result from the completed task
61                    if cancel_task in done:
62                        # Cancellation occurred
63                        raise await cancel_task
64                    else:
65                        # Normal completion
66                        result = await yielded_task
67                      
68                    # Pass the resolved value back to the generator and get the next iteration
69                    next_value = generator.send(result)
70                  
71                except StopIteration as e:
72                    # Generator completed, return the final value
73                    result_future.set_result(e.value)
74                    return e.value
75                except Exception as error:
76                    # If an error occurs (including cancellation), pass it to the generator
77                    # This allows the generator to handle errors with try-except blocks
78                    try:
79                        next_value = generator.throw(error)
80                    except StopIteration as e:
81                        # Generator returned after handling the exception
82                        result_future.set_result(e.value)
83                        return e.value
84                    except Exception as e:
85                        # Generator raised an exception
86                        result_future.set_exception(e)
87                        raise
88                      
89        except Exception as e:
90            # Set exception on the result future if not already done
91            if not result_future.done():
92                result_future.set_exception(e)
93            raise
94  
95    # Start the async execution
96    asyncio.create_task(execute_generator())
97  
98    # Return the cancel function and the execution future
99    return (cancel_func, result_future)
100
101
102# Example usage:
103"""
104def tasks():
105    '''Generator function that yields futures'''
106    future1 = Future()
107    future1.set_result(4)  # 2 + 2
108    val = yield future1
109  
110    future2 = Future()
111    # Simulate setTimeout with asyncio
112    asyncio.get_event_loop().call_later(0.1, lambda: future2.set_result(None))
113    yield future2
114  
115    return val + 1
116
117cancel, promise = cancellable(tasks())
118# Schedule cancellation after 50ms
119asyncio.get_event_loop().call_later(0.05, cancel)
120# Handle the result/error
121promise.add_done_callback(lambda f: print(f.exception() if f.exception() else f.result()))
122"""
123
1import java.util.Iterator;
2import java.util.concurrent.CompletableFuture;
3import java.util.concurrent.CompletionException;
4import java.util.concurrent.atomic.AtomicReference;
5
6/**
7 * Creates a cancellable wrapper for an iterator that yields CompletableFutures.
8 * Allows for manual cancellation of the iterator's execution.
9 * 
10 * @param <T> The type of the final return value
11 */
12public class CancellableGenerator {
13  
14    /**
15     * Represents a generator-like iterator that can yield futures and return a final value
16     * @param <T> The type of the final return value
17     */
18    public interface Generator<T> {
19        /**
20         * Checks if there are more values to yield
21         * @return true if there are more values, false otherwise
22         */
23        boolean hasNext();
24      
25        /**
26         * Gets the next CompletableFuture to yield
27         * @return The next CompletableFuture, or null if done
28         */
29        CompletableFuture<?> next();
30      
31        /**
32         * Passes the result back to the generator
33         * @param result The resolved value from the previous yielded future
34         */
35        void sendValue(Object result);
36      
37        /**
38         * Passes an exception to the generator
39         * @param error The exception that occurred
40         */
41        void sendError(Throwable error);
42      
43        /**
44         * Gets the final return value
45         * @return The final value of type T
46         */
47        T getReturnValue();
48    }
49  
50    /**
51     * Represents a tuple containing a cancel function and a promise
52     * @param <T> The type of the promise result
53     */
54    public static class CancellableResult<T> {
55        private final Runnable cancel;
56        private final CompletableFuture<T> promise;
57      
58        public CancellableResult(Runnable cancel, CompletableFuture<T> promise) {
59            this.cancel = cancel;
60            this.promise = promise;
61        }
62      
63        public Runnable getCancel() {
64            return cancel;
65        }
66      
67        public CompletableFuture<T> getPromise() {
68            return promise;
69        }
70    }
71  
72    /**
73     * Creates a cancellable wrapper for a generator that yields promises.
74     * Allows for manual cancellation of the generator's execution.
75     * 
76     * @param generator A generator that yields CompletableFutures and returns a value of type T
77     * @param <T> The type of the generator's return value
78     * @return A CancellableResult containing a cancel function and a promise that resolves to the generator's return value
79     */
80    public static <T> CancellableResult<T> cancellable(Generator<T> generator) {
81        // Create a CompletableFuture that will be completed exceptionally when cancel is called
82        // This future acts as a cancellation signal
83        CompletableFuture<Object> cancelPromise = new CompletableFuture<>();
84      
85        // Initialize the cancel function to complete the cancelPromise exceptionally
86        Runnable cancel = () -> cancelPromise.completeExceptionally(new CancellationException("Cancelled"));
87      
88        // Prevent unhandled rejection warnings for the cancel promise
89        cancelPromise.exceptionally(throwable -> null);
90      
91        // Main promise that handles the generator execution
92        CompletableFuture<T> promise = CompletableFuture.supplyAsync(() -> {
93            try {
94                // Continue iterating while the generator has more values
95                while (generator.hasNext()) {
96                    // Get the next CompletableFuture from the generator
97                    CompletableFuture<?> nextFuture = generator.next();
98                  
99                    if (nextFuture != null) {
100                        try {
101                            // Race between the yielded future and the cancellation future
102                            // If cancelled, the cancelPromise will complete exceptionally first
103                            CompletableFuture<Object> raceFuture = CompletableFuture.anyOf(
104                                nextFuture.thenApply(result -> result),
105                                cancelPromise
106                            ).thenCompose(obj -> {
107                                if (obj instanceof CompletableFuture) {
108                                    return (CompletableFuture<Object>) obj;
109                                }
110                                return CompletableFuture.completedFuture(obj);
111                            });
112                          
113                            // Wait for the result and pass it back to the generator
114                            Object result = raceFuture.join();
115                            generator.sendValue(result);
116                          
117                        } catch (CompletionException e) {
118                            // If an error occurs (including cancellation), pass it to the generator
119                            // This allows the generator to handle errors with try-catch blocks
120                            Throwable cause = e.getCause();
121                            generator.sendError(cause != null ? cause : e);
122                        }
123                    }
124                }
125              
126                // Return the final value from the generator
127                return generator.getReturnValue();
128              
129            } catch (Exception e) {
130                throw new CompletionException(e);
131            }
132        });
133      
134        // Return the cancel function and the execution promise
135        return new CancellableResult<>(cancel, promise);
136    }
137  
138    /**
139     * Custom exception class for cancellation
140     */
141    public static class CancellationException extends Exception {
142        public CancellationException(String message) {
143            super(message);
144        }
145    }
146}
147
148/**
149 * Example usage:
150 * 
151 * Generator<Integer> tasks = new Generator<Integer>() {
152 *     private int step = 0;
153 *     private Object lastValue;
154 *     
155 *     public boolean hasNext() {
156 *         return step < 2;
157 *     }
158 *     
159 *     public CompletableFuture<?> next() {
160 *         if (step == 0) {
161 *             step++;
162 *             return CompletableFuture.completedFuture(2 + 2);
163 *         } else if (step == 1) {
164 *             step++;
165 *             return CompletableFuture.runAsync(() -> {
166 *                 try { Thread.sleep(100); } catch (InterruptedException e) {}
167 *             });
168 *         }
169 *         return null;
170 *     }
171 *     
172 *     public void sendValue(Object result) {
173 *         if (step == 1) {
174 *             lastValue = result;
175 *         }
176 *     }
177 *     
178 *     public void sendError(Throwable error) {
179 *         // Handle error if needed
180 *     }
181 *     
182 *     public Integer getReturnValue() {
183 *         return ((Integer) lastValue) + 1;
184 *     }
185 * };
186 * 
187 * CancellableResult<Integer> result = CancellableGenerator.cancellable(tasks);
188 * // Schedule cancellation after 50ms
189 * ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);
190 * executor.schedule(result.getCancel(), 50, TimeUnit.MILLISECONDS);
191 * result.getPromise().exceptionally(e -> {
192 *     System.out.println(e.getMessage()); // logs "Cancelled" at t=50ms
193 *     return null;
194 * });
195 */
196
1#include <functional>
2#include <future>
3#include <memory>
4#include <variant>
5#include <chrono>
6#include <thread>
7#include <exception>
8#include <stdexcept>
9
10/**
11 * Generator class that simulates JavaScript generator behavior
12 * Yields futures and returns a value of type T
13 */
14template<typename T>
15class Generator {
16public:
17    struct IterationResult {
18        bool done;
19        std::variant<std::shared_future<void>, T> value;
20    };
21  
22    virtual ~Generator() = default;
23    virtual IterationResult next() = 0;
24    virtual IterationResult next(const std::any& value) = 0;
25    virtual IterationResult throw_error(std::exception_ptr error) = 0;
26};
27
28/**
29 * Custom exception class for cancellation
30 */
31class CancelledException : public std::runtime_error {
32public:
33    CancelledException() : std::runtime_error("Cancelled") {}
34};
35
36/**
37 * Creates a cancellable wrapper for a generator that yields futures.
38 * Allows for manual cancellation of the generator's execution.
39 * 
40 * @param generator - A shared pointer to a generator that yields futures and returns a value of type T
41 * @returns A pair containing a cancel function and a future that resolves to the generator's return value
42 */
43template<typename T>
44std::pair<std::function<void()>, std::future<T>> cancellable(std::shared_ptr<Generator<T>> generator) {
45    // Create a promise/future pair for cancellation signaling
46    auto cancel_promise = std::make_shared<std::promise<void>>();
47    auto cancel_future = cancel_promise->get_future().share();
48  
49    // Create a flag to track if cancellation has been triggered
50    auto is_cancelled = std::make_shared<std::atomic<bool>>(false);
51  
52    // Initialize the cancel function that will trigger cancellation
53    std::function<void()> cancel = [cancel_promise, is_cancelled]() {
54        if (!is_cancelled->exchange(true)) {
55            // Set exception to signal cancellation
56            cancel_promise->set_exception(std::make_exception_ptr(CancelledException()));
57        }
58    };
59  
60    // Create promise for the main execution result
61    auto result_promise = std::make_shared<std::promise<T>>();
62    auto result_future = result_promise->get_future();
63  
64    // Launch async task to handle generator execution
65    std::thread([generator, cancel_future, result_promise, is_cancelled]() {
66        try {
67            // Get the first iteration result from the generator
68            auto next = generator->next();
69          
70            // Continue iterating while the generator hasn't completed
71            while (!next.done) {
72                try {
73                    // Check if we have a future to wait on
74                    if (std::holds_alternative<std::shared_future<void>>(next.value)) {
75                        auto yielded_future = std::get<std::shared_future<void>>(next.value);
76                      
77                        // Race between the yielded future and the cancellation future
78                        // Using polling approach to simulate Promise.race
79                        while (true) {
80                            // Check if cancelled
81                            if (cancel_future.wait_for(std::chrono::milliseconds(0)) == std::future_status::ready) {
82                                cancel_future.get(); // This will throw CancelledException
83                            }
84                          
85                            // Check if yielded future is ready
86                            if (yielded_future.wait_for(std::chrono::milliseconds(10)) == std::future_status::ready) {
87                                yielded_future.get();
88                                break;
89                            }
90                        }
91                      
92                        // Pass the resolved value back to the generator and get the next iteration
93                        next = generator->next(std::any{});
94                    }
95                } catch (...) {
96                    // If an error occurs (including cancellation), pass it to the generator
97                    // This allows the generator to handle errors with try-catch blocks
98                    next = generator->throw_error(std::current_exception());
99                }
100            }
101          
102            // Set the final value from the generator
103            if (std::holds_alternative<T>(next.value)) {
104                result_promise->set_value(std::get<T>(next.value));
105            }
106        } catch (...) {
107            // Set any unhandled exception
108            result_promise->set_exception(std::current_exception());
109        }
110    }).detach();
111  
112    // Return the cancel function and the execution future
113    return {cancel, std::move(result_future)};
114}
115
116/**
117 * Example usage:
118 * 
119 * class TasksGenerator : public Generator<int> {
120 * private:
121 *     int state = 0;
122 *     int val = 0;
123 * 
124 * public:
125 *     IterationResult next() override {
126 *         return next(std::any{});
127 *     }
128 *     
129 *     IterationResult next(const std::any& value) override {
130 *         switch(state++) {
131 *             case 0: {
132 *                 // yield new Promise(resolve => resolve(2 + 2))
133 *                 auto future = std::async(std::launch::async, []() { 
134 *                     return 2 + 2; 
135 *                 });
136 *                 return {false, future.share()};
137 *             }
138 *             case 1: {
139 *                 val = 4; // Result from previous yield
140 *                 // yield new Promise(resolve => setTimeout(resolve, 100))
141 *                 auto future = std::async(std::launch::async, []() {
142 *                     std::this_thread::sleep_for(std::chrono::milliseconds(100));
143 *                 });
144 *                 return {false, future.share()};
145 *             }
146 *             default:
147 *                 return {true, val + 1};
148 *         }
149 *     }
150 *     
151 *     IterationResult throw_error(std::exception_ptr error) override {
152 *         std::rethrow_exception(error);
153 *     }
154 * };
155 * 
156 * auto generator = std::make_shared<TasksGenerator>();
157 * auto [cancel, promise] = cancellable<int>(generator);
158 * std::this_thread::sleep_for(std::chrono::milliseconds(50));
159 * cancel();
160 * try {
161 *     promise.get();
162 * } catch (const CancelledException& e) {
163 *     std::cout << e.what() << std::endl; // logs "Cancelled" at t=50ms
164 * }
165 */
166
1/**
2 * Creates a cancellable wrapper for a generator that yields promises.
3 * Allows for manual cancellation of the generator's execution.
4 * 
5 * @param generator - A generator function that yields promises and returns a value of type T
6 * @returns A tuple containing a cancel function and a promise that resolves to the generator's return value
7 */
8function cancellable<T>(generator: Generator<Promise<any>, T, unknown>): [() => void, Promise<T>] {
9    // Initialize the cancel function as a no-op
10    let cancel: () => void = () => {};
11  
12    // Create a promise that will be rejected when cancel is called
13    // This promise acts as a cancellation signal
14    const cancelPromise = new Promise<never>((resolve, reject) => {
15        // Assign the actual cancel implementation that rejects with 'Cancelled'
16        cancel = () => reject('Cancelled');
17    });
18  
19    // Prevent unhandled rejection warnings for the cancel promise
20    cancelPromise.catch(() => {});
21
22    // Main promise that handles the generator execution
23    const promise = (async (): Promise<T> => {
24        // Get the first iteration result from the generator
25        let next = generator.next();
26      
27        // Continue iterating while the generator hasn't completed
28        while (!next.done) {
29            try {
30                // Race between the yielded promise and the cancellation promise
31                // If cancelled, the cancelPromise will reject first
32                const result = await Promise.race([next.value, cancelPromise]);
33              
34                // Pass the resolved value back to the generator and get the next iteration
35                next = generator.next(result);
36            } catch (error) {
37                // If an error occurs (including cancellation), pass it to the generator
38                // This allows the generator to handle errors with try-catch blocks
39                next = generator.throw(error);
40            }
41        }
42      
43        // Return the final value from the generator
44        return next.value;
45    })();
46
47    // Return the cancel function and the execution promise
48    return [cancel, promise];
49}
50
51/**
52 * Example usage:
53 * 
54 * function* tasks() {
55 *   const val = yield new Promise(resolve => resolve(2 + 2));
56 *   yield new Promise(resolve => setTimeout(resolve, 100));
57 *   return val + 1;
58 * }
59 * const [cancel, promise] = cancellable(tasks());
60 * setTimeout(cancel, 50);
61 * promise.catch(console.log); // logs "Cancelled" at t=50ms
62 */
63

Time and Space Complexity

Time Complexity: O(n) where n is the number of yield statements in the generator function.

The function iterates through the generator, processing each yielded promise sequentially. For each yield:

  • generator.next() is called - O(1)
  • Promise.race() is called with 2 promises - O(1)
  • await waits for the promise resolution - depends on the promise itself, not the cancellable function

Since the while loop runs once for each yield statement, and each iteration performs constant-time operations (excluding the actual promise resolution time), the time complexity is linear with respect to the number of yields.

Space Complexity: O(1) constant space.

The function maintains:

  • A fixed number of variables (cancel, cancelPromise, promise, next)
  • No data structures that grow with input size
  • The Promise.race() creates a new promise but doesn't accumulate them
  • The async function's execution context uses constant space regardless of the number of yields

The space used remains constant regardless of how many yield statements the generator contains, as each yielded value is processed one at a time without storing previous results.

Common Pitfalls

1. Not Handling Already-Completed Generators

Pitfall: If the generator has already completed (either successfully or with an error) when cancel() is called, the cancellation might cause unexpected behavior or leave dangling promises.

Issue Example:

def quick_generator():
    yield Future().set_result(1)
    return "done"

cancel, promise = cancellable(quick_generator())
# Generator completes immediately
# Calling cancel after completion might cause issues
cancel()  # This could create orphaned futures or cause errors

Solution: Check if the result future is already done before processing cancellation:

def cancel_impl():
    """Only cancel if the operation is still pending"""
    if not result_future.done() and not cancel_future.done():
        cancel_future.set_exception(Exception('Cancelled'))

2. Memory Leaks from Uncancelled Tasks

Pitfall: When racing between the yielded future and cancel future, if one completes, the other task remains in memory as a pending task that never gets properly cleaned up.

Issue Example:

# In the execute_generator function
done, pending = await asyncio.wait(
    [yielded_task, cancel_task],
    return_when=asyncio.FIRST_COMPLETED
)
# If we don't cancel pending tasks, they remain in memory

Solution: Always cancel and await cleanup of pending tasks:

# Cancel all pending tasks
for task in pending:
    task.cancel()
    try:
        await task
    except asyncio.CancelledError:
        pass  # Expected when cancelling

3. Race Condition in Cancel Future Creation

Pitfall: The cancel future is created immediately but the actual execution might start later due to event loop scheduling. This can cause a race condition where cancel() is called before the async execution even begins monitoring the cancel future.

Issue Example:

cancel, promise = cancellable(generator)
cancel()  # Called immediately, but execute_generator might not have started

Solution: Use proper synchronization or ensure the cancel mechanism is set up before any async operations:

def cancellable(generator):
    cancel_event = asyncio.Event()
  
    async def execute_generator():
        while True:
            try:
                # Check cancellation at each iteration
                if cancel_event.is_set():
                    raise Exception('Cancelled')
                # ... rest of logic
            except Exception as e:
                # Handle cancellation
                pass
  
    def cancel_impl():
        cancel_event.set()
  
    # Start execution immediately to ensure proper setup
    task = asyncio.create_task(execute_generator())
    return (cancel_impl, asyncio.wrap_future(result_future))

4. Incorrect Exception Type for Cancellation

Pitfall: The problem specifies that cancellation should throw a string "Cancelled", not an Exception object. Using Exception('Cancelled') changes the behavior.

Issue in Python Context: Python's type system expects exceptions to be Exception instances, not strings.

Solution: Either wrap the string in a custom exception type or handle it specially:

class CancelledException(Exception):
    def __str__(self):
        return "Cancelled"

# Or use a sentinel value approach
CANCELLED = object()  # Unique sentinel

# Then in error handling:
if error is CANCELLED or str(error) == "Cancelled":
    # Handle cancellation specifically

5. Generator State After Cancellation

Pitfall: Not properly handling what happens if the generator catches the cancellation error and continues execution. The generator might yield more values after catching the cancellation.

Issue Example:

def resilient_generator():
    try:
        yield some_future
    except:
        # Generator catches cancellation and continues
        yield another_future
        return "completed despite cancellation"

Solution: Track whether cancellation has been requested and handle subsequent iterations appropriately:

async def execute_generator():
    cancelled = False
  
    while True:
        try:
            if cancelled:
                # Don't race with cancel future after cancellation
                result = await asyncio.wrap_future(next_value)
            else:
                # Normal racing logic
                done, pending = await asyncio.wait([yielded_task, cancel_task], ...)
        except Exception as e:
            cancelled = (str(e) == "Cancelled")
            next_value = generator.throw(e)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More