Handling user input with structured concurrency

February 15, 2022

Note: this is a follow-up to Three ways of handling user input. You should read that article first if you haven’t already!

In my last post, I looked at three different ways of handling user input in a web-based interface. The last approach I discussed was based on concurrent processes, using a small, proof-of-concept library I built called Abro.

Since writing the post, I discovered a Python library called Trio, which enables a form of structured concurrency that’s similar to what I was attempting with Abro. The ideas behind Trio have influenced a number of other languages, including Swift, Kotlin, and Java. In JavaScript, Effection seems to be the most mature library.

What is structured concurrency?

The term structured concurrency is general enough that it’s been used to mean a lot of things over the years. The current usage, which comes from Martin Sústrik, specifically means tree-structured concurrency. Here’s how he describes it:

Structured concurrency means that lifetimes of concurrent functions are cleanly nested. If coroutine foo launches coroutine bar, then bar must finish before foo finishes.

This is not structured concurrency:

This is structured concurrency:

The goal of structured concurrency is to guarantee encapsulation. If the main function calls foo, which in turn launches bar in a concurrent fashion, main will be guaranteed that once foo has finished, there will be no leftover functions still running in the background.

What you end up with is a tree of coroutines rooted in the main function. This tree spreads out towards the smallest worker functions, and you may think of this as a generalization of the call stack — a call tree, if you will.

(From libdill: Structured Concurrency for C)

Implementing structured concurrency

or, Lessons learned from Abro

The key ingredients of structured concurrency are:

  1. Some form of coroutines, as the basis for concurrent processes (aka fibers, tasks, etc.).
  2. An explicit parent-child relationship between processes.
  3. A way of canceling processes from the outside, to ensure that no child can outlive its parent.

Let’s take a look at how you can implement these things in JavaScript. Most of these things I learned the hard way, in the process of building and re-building Abro multiple times.

Coroutines

JavaScript actually has two different coroutine-like mechanisms: generators, and async functions. Without putting much thought into it, I built the first version of Abro on async functions. Later, after discovering some of the issues with this approach, I built a second version based on generators.

The main challenge was that async functions are scheduled implicitly: when a promise is ready, its then/catch/finally handlers are automatically scheduled (put into the microtask queue). So you schedule the processes/fibers by controlling the order in which the promises are resolved.

For this to work, the scheduler needs to be aware of all of the promises that are awaited by the fibers. In other words, a fiber can only use await on functions that are provided by the concurrency library (in my case, Abro). This is not a big limitation — it’s possible to support “foreign” promises as long as they’re wrapped by a scheduler-controlled promise — but it’s a bit of a footgun. Using await with any other function would result in all threads being paused until the promise resolves.

Another problem I had was how to run bookkeeping code before a fiber executes. For example, it’s useful to keep track of which fiber is currently running. This is the solution that I ended up with:

// Resolve the promises for all processes waiting on this event.
promises.forEach(({ fiber, resolve }) => {
  if (fiber.state === "RUNNING") {
    queueMicrotask(() => { // 👈 2️⃣
      currentFiber = fiber;
    });
    resolve(evt); // 👈 1️⃣
  }
}

Calling resolve (see 1️⃣ ↩) will enqueue a microtask to perform the promise’s then operation. The call to queueMicrotask (see 2️⃣ ↩) just before that allows me to run some code immediately before the fiber wakes up. Unfortunately, this relies on unspecified behaviour — the ECMAScript spec allows implementations to treat Promise-handling jobs with higher priority. But from what I can tell, V8 handles everything on the microtask queue with equal priority.

Using generators as the basis for coroutines eliminates these problems. It gives the scheduler full control, since a generator must be explicitly resumed by calling its next method. It’s also easy to distinguish between coroutine preemption (yield) and other async function calls. Even if the user makes a mistake (e.g. by yielding the result of an async function), it’s easy to detect and raise a runtime error.

Parent-child relationship

Maintaining a parent-child relationship between fibers is straightforward as long as you keep track of the currently-running fiber. The fiber-creation primitives (e.g., loop, run, and or in Abro) can maintain a list of each fiber’s children.

Cancelation

To ensure that no fiber can outlive its parent, we need a way to cleanly terminate fibers. How this works depends on the coroutine mechanism — either way, we have a notion of explicit suspension points (identified by yield or await) where a fiber yields control to the scheduler. These are the same points where fiber can be canceled.

In the original version of Abro, I handled cancelation by (a) keeping track of the promise that each fiber was waiting on, and (b) rejecting that promise when I needed to cancel the fiber. This requires that a unique promise is created at any possible suspension point, and that promises are never shared between fibers.

In the drag-and-drop example I used in my previous post, the yield points all looked something like this:

const events = new abro.EventSource(draggable);
// ...
await events.pointerdown;

…where events.pointerdown was a getter that allocated a new promise each time. Even if two fibers are waiting on the same event, it’s important that promises aren’t shared. Depending on the relationship between the fibers, it may be necessary to cancel one but not the other. If each promise is owned by a single fiber, then we can cancel a fiber by rejecting the promise that it’s waiting on, without affecting any other fibers.

This solution works, but obviously it’s not ideal. For one thing, there’s no way to prevent promises from being shared between fibers. And there’s another problem: rejecting a promise results in an exception being raised in the async function. It’s possible that user code might (inadvertently or deliberately) handle the rejection and continue running. For example:

try {
  await events.pointerdown; // ⬅ If this promise is rejected...
} finally {
  // ...then by the time this block is executed, the parent fiber could
  // have already exited — breaking the promise of structured concurrency.
  await events.pointerup;
}

With generator-based coroutines, cancelation is trivial. Since the scheduler must explicitly resume fibers, we can cancel a fiber by simply discarding it (along with any associated state).

You do still need to be careful that fibers don’t share state in certain ways. For example, in the generator-based version of Abro, the yield points look like this:

yield abro.await(document, "pointerdown");

The result of abro.await is a promise-like object (but specific to Abro). Depending on the implementation, sharing such an object between fibers could still be problematic.

By this point, it’s probably clear that generator-based coroutines are a much better foundation for structured concurrency in JavaScript. Effection, a JavaScript library for structured concurrency, is based on generators. Trio uses Python 3’s async/await syntax, but Python’s async functions are much closer to generators than they are to JavaScript’s async functions.

Building Abro was a great exercise to help me dig deeper into these ideas, but I don’t currently have plans to develop it further. I’ve already started to use Effection in new projects.

If you want to learn more about the ideas behind structured concurrency, you should read Notes on structured concurrency, or: Go statement considered harmful from the author of Trio. The Trio forum also has a a separate category for general discussion of structured concurrency (in any language). There’s some interesting historical discussions, and links to other articles, talks, etc.

💬 Want to leave feedback? Send me an email or respond on on Twitter.

If you liked this post, you should consider subscribing to my newsletter! I share all new posts there, and the occasional newsletter-only content.