We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Cancellable Function

Number: 2788

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Write a function cancellable that accepts a generator object which yields only promises. The function should return an array containing two items: a cancel function and a promise. As the generator yields promises, your function must wait for each promise to resolve (or reject) and feed the result (or error) back into the generator. If the cancel function is invoked before the generator completes, then an error (the string "Cancelled") must be thrown back into the generator. If that error is caught within the generator, execution will continue and the promise eventually resolves with the next yielded or returned value; otherwise, the promise is rejected with this error. When the generator finishes normally the resulting promise resolves with the returned value, and if the generator throws an error the promise rejects with the error.

Key Insights

  • The generator yields promises; the driver code must resume the generator with the resolved value or throw into it when a promise rejects.
  • Cancellation is implemented by racing the yielded promise with a “cancellation promise” that rejects when cancel() is called.
  • When cancel() is invoked, if the generator is waiting on a promise, the cancellation signal propagates into the generator via generator.throw("Cancelled").
  • If the cancellation error is caught within the generator, processing may resume, otherwise the main promise rejects.
  • Careful management of asynchronous control flow is needed so that no further processing occurs after an uncaught cancellation.

Space and Time Complexity

Time Complexity: O(n), where n is the number of yielded promises from the generator. Space Complexity: O(n) in the worst case, due to the call stack and promise chain.

Solution

The solution revolves around driving the generator in a loop. Each iteration, we call generator.next() (or generator.throw() when an error is injected) and get a yielded promise. We then use a race (or equivalent mechanism) between the yielded promise and a cancellation promise. If the yielded promise resolves first, we feed its value back into the generator to get the next promise; if the cancellation promise “wins” (i.e. cancel() is invoked), we throw the cancellation error ("Cancelled") back into the generator. This process continues until the generator completes normally (in which case the final value is resolved) or an unhandled error occurs (leading to rejection).

To implement this, we: • Create a cancellation promise (or similar mechanism) that is triggered by the cancel function. • Use Promise.race (or similar) to wait for either the yielded promise or the cancellation. • On each resolution or rejection, resume the generator accordingly. • Return the cancel function and a promise that represents the overall computation.

Code Solutions

import asyncio

def cancellable(generator):
    # 'cancelled' flag indicates if cancel() has been called.
    cancelled = False
    # main_future will be our final promise-like future.
    main_future = asyncio.get_event_loop().create_future()
    # cancel_future is used to race with yielded futures.
    cancel_future = asyncio.get_event_loop().create_future()
    
    # Define cancel() which triggers cancellation if not already cancelled.
    def cancel():
        nonlocal cancelled
        if not cancelled:
            cancelled = True
            if not cancel_future.done():
                cancel_future.set_exception("Cancelled")
    
    async def process(gen, send_value=None):
        try:
            # Resume the generator (using next() or send()).
            if send_value is None:
                result = next(gen)
            else:
                result = gen.send(send_value)
        except StopIteration as ex:
            # Generator finished normally; complete the main future.
            main_future.set_result(ex.value)
            return
        except Exception as e:
            # Generator threw an exception; propagate it.
            main_future.set_exception(e)
            return

        try:
            # Race between the yielded promise (result) and cancellation.
            done, pending = await asyncio.wait(
                [result, cancel_future],
                return_when=asyncio.FIRST_COMPLETED
            )
            if cancel_future in done:
                # If cancellation occurred, extract exception.
                exc = cancel_future.exception()
                try:
                    # Throw cancellation error back into the generator.
                    res = gen.throw(exc)
                    await process(gen, res)
                except StopIteration as ex:
                    main_future.set_result(ex.value)
                    return
                except Exception as e:
                    main_future.set_exception(e)
                    return
            else:
                # Cancel the cancellation future in the pending set.
                for fut in pending:
                    fut.cancel()
                # Get the resolved value from the yielded promise.
                for fut in done:
                    value = fut.result()
                    await process(gen, value)
        except Exception as ex:
            try:
                gen.throw(ex)
            except StopIteration as stop:
                main_future.set_result(stop.value)
                return
            except Exception as e:
                main_future.set_exception(e)
                return

    # Start processing the generator asynchronously.
    asyncio.create_task(process(generator))
    return cancel, main_future
← Back to All Questions