pmndrs/directed

A flexible, minimal scheduler written in TypeScript

Directed

Caution

This is library is in pre-release and its API may change. Until it enters RC, it can only be installed via GitHub.

Directed is a flexible, minimal scheduler written in TypeScript. It is powered by a directed acyclic graph (DAG) allowing for dependency-based scheduling.

npm install pmndrs/directed#v0.0.1-alpha.5

Quickstart

Directed supports a functional and class API depending on what is comfy for you.

Class API

import { Schedule } from 'directed'

const applyGravity = (state) => {}
const moveBody = (state) => {}

const schedule = new Schedule()
schedule.add(moveBody)
schedule.add(applyGravity, { before: moveBody })

schedule.run(state)

Functional API

import * as Scheduler from 'directed'

const applyGravity = (state) => {}
const moveBody = (state) => {}

const schedule = Scheduler.create()
Scheduler.add(schedule, moveBody)
Scheduler.add(schedule, applyGravity, before(moveBody))

Scheduler.run(schedule, state)

React

import { Schedule } from 'directed'
import { useSchedule } from 'directed/react'

const applyGravity = (state) => {}
const moveBody = (state) => {}

const schedule = new Schedule()

// You can create hook bound to your schedule.
function useMySchedule(runnable, options) {
    return useSchedule(schedule, runnable, options)
}

function Foo({ children }) {
    useMySchedule(moveBody)
    useMySchedule(applyGravity, { before: moveBody })

    return children
}

Tip

See the tests for more usage examples until we write out better docs. Here for functional and here for class.

What's the big deal?

Scheduling update functions is simple when you have visibility of an entire static app, you just call them in the order required. The problem comes when the app scales and you no longer have full visibiilty, or if the app is dynamic and updates may or may not exist at any given time. You need to be confident that data is updated in the correct order at all times.

One solution is to arrange updates by a priority number. But this quickly gets back to needing visibility of the entire app, and the problem only gets worst with external libraries. As web devs we all remember the z-index wars.

The most flexible solution is to instead tell the scheduler the dependencies for each update and let it solve for the correct order for us. Any new insertions will respect the already defined dependencies.

schedule.add(A)
schedule.add(B, { before: A, after: C })
schedule.add(C, { before: B })
// Executes with the order C -> B -> A

Directed takes this a step further by allowing tags to be used as dependencies. This allows you to schedule without needing to know any of the internal functions.

schedule.createTag('render')

schedule.add(A, { tag: 'render' })
schedule.add(B, { before: 'render' })
schedule.add(C, { after: 'render' })
// Executes with the order B -> A -> C

API

Caution

Not quite done yet! All functions have JSDoc comments you can read here for the functional API. The class API is virtually the same, just formatted as methods which you can find here.

directed's Issues

`add` builds but `remove` does not

I got caught by a bug this evening because while add builds automatically, remove does not and you have to call build yourself for the command to commit. Is this the intended behavior?

Working with HMR

Using the scheduler with HMR is a bit problematic. So far I have two obvious issues:

1. Duplicates of the same runnable get scheduled if the function regenerates.
2. If it doesn't regenerate it errors out since the same system can't be added twice.

It looks like a solution will involve implementing our own HMR dispose functions: https://vitejs.dev/guide/api-hmr#hot-dispose-cb

RC milestones

This is a fluid list that anyone can edit.

• Documentation #7
• Class sugar layer https://github.com/pmndrs/directed
• React bindings
• Settle on recommended React usage #1
• Settle on expected tag behavior #2 #5

Add an api to add tag/runnable dependencies after creation

Currently, tag/runnable dependencies can only be specified when the tag is created or when the runnable is added to schedule. Add an api to create these relations for a rag or runnable that has already been created/added to the schedule.

Much like add/createTag, the schedule will need to be built after this method is called.

Add ability to disable a runnable

The scheduler should have the ability to temporarily disable a runnable by id or reference. This will cause the scheduler to skip execution of the runnable and should not require a re-build of the schedule.

Clarify scheduling by tag

I had been using this example as how to do a quick game loop with the usual stages:

And then to complicate things I add an update camera system that gets the default tag and a new camera tag. I explicitly schedule it before render but the expectation was that I don't have to. Since moveBody is scheduler before render and it also has the default tag I expect the tag to inherit this requirement

Is that correct?

Add ability to disable a tag group

Much like issue #15 , the scheduler should have the ability to temporarily disable a tag and all runnables in it.

Add multiple runnables at once

I have many runnables with the same options:

schedule.add(updateSettings, { tag: PRE_RENDER_GROUP });
schedule.add(updateAttachmentTextures, { tag: PRE_RENDER_GROUP });
schedule.add(updateTransformMatrices, { tag: PRE_RENDER_GROUP });
schedule.add(updateMaterialBindGroups, { tag: PRE_RENDER_GROUP });
schedule.add(generateVertexBuffersLayout, { tag: PRE_RENDER_GROUP });
schedule.add(updateGeometryBuffers, { tag: PRE_RENDER_GROUP });
schedule.add(updateCameraAspectRatio, { tag: PRE_RENDER_GROUP });
schedule.add(updateCameraMatrices, { tag: PRE_RENDER_GROUP });
schedule.add(createPipelines, { tag: PRE_RENDER_GROUP });
...

It would be more convenient and readable to be able to add them all at once:

schedule.add(
  [
    updateSettings,
    updateAttachmentTextures,
    updateTransformMatrices,
    updateMaterialBindGroups,
    generateVertexBuffersLayout,
    updateGeometryBuffers,
    updateCameraAspectRatio,
    updateCameraMatrices,
    createPipelines,
  ],
  { tag: PRE_RENDER_GROUP }
);

Reference vertices in the directed graph by an id instead of object reference

Currently the DAG structure references vertices by an object reference. This is fine, but has a number of awkward side effects, since the object reference is used as a key. This also prevents being able to "override" an item in the graph from an external source (see #6 ).

Replace vertex references with a string or symbol id instead of an object reference.

Gracefully scheduling the same runnable twice

Currently if the same runnable is scheduled twice it throws an error.

add(schedule, aFn, id('A'));
add(schedule, aFn, id('A'));

In imperative apps this probably isn't an issue, you just check to make sure you are scheduling the runnable once, but in dynamic apps like React this can be a real issue. Here are two scenarios where I think it is legitimate to handle this case more gracefully than an error:

1. A user needs to reschedule a runnable. Here it would be ideal to get feedback that it is already scheduled and needs to be removed and readded instead of an error.
2. A schedule call is part of a React component and is called each time a view instance is rendered even though it only needs to mount once.

(2) is relevant since a React component is intended to have all of its behavior and state included with the view. The scheduler, especially with a hook, allows for including global level behavior, usually to do with a simulation.

My proposed solution is to have add return a boolean where true is successfully adding and false is unsuccessful, meaning it was already in the system. Then this can be used as feedback for determining what to do next, either ignore or remove/add to reschedule.

Async runnables

I have a need to support async runnables, for example a runnable that waits for distributed work on workers to complete before moving on. In this case the runnable would stall the execution of the schedule until it resolves.

Overriding a runnable via ID

This idea came from @pietrovismara. An ID is currently only used for debug, but it also allows an alias for overriding.
This would be useful for mocking during tests, but also for ecosystem integration where you can override a runnable that is loaded by another library.

Scheduling runnables to run first or last

I run into situations where I want something to run first or last, for example for performance profiling. Now, of course, telling two runnables to be scheduled last runs into a logic problem, only one can truly be last. But would it make sense to have built in tags, first and last where trying to scheduler before first throws an error and trying to scheduler after last throws an error? Then there would be some guarantees that these tags stick your runnables before or after game code.

Schedule runnables to run once

An example is an init function. A work around is to early out after the first run, but it would be even better if it were just removed from the sort entirely.

I figure the API can look like this, though I don't know the best way it could be implemented.

test('scheduling runnables once', () => {
    const schedule = create();

    add(schedule, aFn, id('A'), once());
    add(schedule, bFn, after('A'), id('B'));
    add(schedule, cFn, after('B'), id('C'));

    run(schedule, {});

    expect(order).toEqual(['A', 'B', 'C']);

    order = [];
    run(schedule, {});

    expect(order).toEqual(['B', 'C']);
})