A Tiny Event Loop

Async frameworks run many tasks on one thread by pausing and resuming them. Generators can pause too, so you can build a small event loop out of them.

Write run_tasks(tasks). tasks is a list of (name, generator) pairs. The loop has a clock that starts at 0 and a ready queue that starts with the tasks in the order given. It repeats these steps until every task has finished:

1. If the ready queue is empty, move the clock forward to the earliest time a sleeping task wakes up, and put every task waking at that time on the queue, in the order they went to sleep. 2. Take the task at the front of the queue and resume it with send(value), where value is what it is owed: None the first time, and otherwise what the rules below say. 3. Look at what the task did: - It yielded None (a bare yield): it goes to the back of the queue. When resumed, it is sent the clock time. - It yielded a positive integer k: it sleeps and wakes at clock + k. When resumed, it is sent the clock time at which it woke. - It yielded a generator: it waits for it. That generator becomes a new child task at the back of the queue. When the child finishes, the waiting task goes to the back of the queue and is sent the child's return value. - It finished (raised StopIteration): it leaves the loop. For a task from the original list, record (clock, name, return value). A child task is not recorded; it wakes its parent as described above.

Return the list of records in the order the tasks finished.

Examples

def worker(rounds):
    for _ in range(rounds):
        yield
    return rounds

run_tasks([('a', worker(2)), ('b', worker(1))])
# returns [(0, 'b', 1), (0, 'a', 2)]

def alarm(delay, label):
    woke = yield delay
    return label + '@' + str(woke)

run_tasks([('tea', alarm(5, 'tea')), ('toast', alarm(2, 'toast'))])
# returns [(2, 'toast', 'toast@2'), (5, 'tea', 'tea@5')]

def fetch(item, delay):
    yield delay
    return item.upper()

def main():
    x = yield fetch('x', 3)
    y = yield fetch('y', 1)
    return x + y

run_tasks([('main', main())])
# returns [(4, 'main', 'XY')]

In the last example, main waits for the first fetch, which sleeps until time 3 and returns 'X'; then it waits for the second, which sleeps until time 4. The clock only moves when nobody is ready, so turns taken at the same moment cost no time.

Constraints

• Up to 200 tasks, each yielding up to 1,000 times, and clock times stay below 10^9
• A task only ever yields None, a positive integer or a generator