A topological order respecting signals library inspired by SolidJS.
What's topological ordering you ask? Check out the readme to understand the problem with most signals libraries.
Wait, this is the readme file... uhmm
Non-mandatory example:
// reactively compute the bounding-boxes of many nested rectangles.
// the computation should be lazy: if the bounding-box of a child-rectangle hasn't changed, then it shouldn't invoke an update in its parent-rectangle.
// if the top-most rectangle's `right` or `top` bounding-box's sides exceed `600`, then we should log `"overflow"` in the console.
// at the end of every reaction cycle, log the number of computations done in the console.
import { Context } from "../src/context.ts"
import { StateSignal_Factory, MemoSignal_Factory, EffectSignal_Factory } from "../src/signal.ts"
import type { Accessor, Setter } from "../src/typedefs.ts"
/** `x` and `y` are relative to the parent-rectangle's top-left corner (which is their (x, y) position). */
interface Rect { x: number, y: number, width: number, height: number }
/** the bounding box of a `Rect` */
interface Box { left: number, top: number, right: number, bottom: number }
const signal_ctx = new Context()
const createState = signal_ctx.addClass(StateSignal_Factory)
const createMemo = signal_ctx.addClass(MemoSignal_Factory)
const createEffect = signal_ctx.addClass(EffectSignal_Factory)
const rectEqualityFn = (rect1: Rect | undefined, rect2: Rect): boolean => {
return rect1 === undefined ? false :
rect1.x === rect2.x &&
rect1.y === rect2.y &&
rect1.width === rect2.width &&
rect1.height === rect2.height
}
const boxEqualityFn = (box1: Box | undefined, box2: Box): boolean => {
return box1 === undefined ? false :
box1.top === box2.top &&
box1.left === box2.left &&
box1.bottom === box2.bottom &&
box1.right === box2.right
}
type RectangleObject = Rect & { children?: RectangleObject[] }
class Rectangle {
rect: Accessor<Rect>
setRect: Setter<Rect>
box: Accessor<Box>
children: Rectangle[] = []
constructor(initial_rect: Rect) {
const [idRect, getRect, setRect] = createState(initial_rect, { equals: rectEqualityFn })
const [idBox, getBox] = createMemo<Box>((id) => {
const { x, y, width, height } = getRect(id)
const children_boxes = this.children.map((child) => child.box(idBox))
const
top = Math.min(y, ...children_boxes.map((child_box) => child_box.top)),
left = Math.min(x, ...children_boxes.map((child_box) => child_box.left)),
bottom = Math.max(y + height, ...children_boxes.map((child_box) => y + child_box.bottom)),
right = Math.max(x + width, ...children_boxes.map((child_box) => x + child_box.right))
return { top, left, bottom, right }
}, { equals: boxEqualityFn })
this.rect = getRect
this.setRect = setRect
this.box = getBox
}
render(ctx: CanvasRenderingContext2D) {
const { x, y, width, height } = this.rect()
const { top, left, bottom, right } = this.box()
const children = this.children
ctx.fillStyle = get_next_fillcolor()
ctx.strokeStyle = get_next_strokecolor()
ctx.fillRect(x, y, width, height)
ctx.strokeRect(left, top, right - left, bottom - top)
ctx.translate(x, y)
for (const child of children) {
child.render(ctx)
}
ctx.translate(-x, -y)
}
static fromObject(object: RectangleObject): Rectangle {
const { children, ...rect } = object
const instance = new Rectangle(rect)
const children_instances = children?.map(Rectangle.fromObject) ?? []
instance.children.push(...children_instances)
return instance
}
}
let color_idx = 0
const fillcolors = ["blue", "cyan", "goldenrod", "gray", "green", "khaki", "magenta", "orange", "orchid", "red", "salmon", "seagreen", "turquoise", "violet",]
const strokecolors = fillcolors.map((color) => "dark" + color)
const get_next_fillcolor = () => { return fillcolors[color_idx++ % fillcolors.length] }
const get_next_strokecolor = () => { return strokecolors[color_idx++ % strokecolors.length] }
const all_rectangles = Rectangle.fromObject({
x: 10, y: 20, width: 70, height: 80, children: [
{
x: 15, y: 25, width: 50, height: 60, children: [
{
x: 20, y: 30, width: 40, height: 50, children: [
{
x: 25, y: 35, width: 30, height: 40, children: [
{ x: 30, y: 40, width: 20, height: 30 },
{ x: 35, y: 45, width: 10, height: 20 }
]
},
{ x: 40, y: 50, width: 10, height: 20 }
]
},
{
x: 45, y: 55, width: 10, height: 15, children: [
{ x: 0, y: 40, width: 30, height: 50 },
{ x: 70, y: 80, width: 50, height: 20 }
]
}
]
},
{ x: 50, y: 60, width: 40, height: 30 }
]
})
const canvas = document.createElement("canvas")
const ctx = canvas.getContext("2d")!
document.body.appendChild(canvas)
const [idRedraw, awaitRedraw, fireRedraw] = createEffect((id) => {
// add dependence on all rectangles
const add_dependence = (rect_object: Rectangle) => {
rect_object.rect(id)
rect_object.box(id)
rect_object.children.forEach(add_dependence)
}
add_dependence(all_rectangles)
color_idx = 0
ctx.reset()
ctx.scale(2, 2)
all_rectangles.render(ctx)
})
fireRedraw()
// try the following lines in your console (one by one) to witness reactivity:
// all_rectangles.children[0].children[0].children[0].setRect({x:10, y:10, width: 20, height: 50})
// all_rectangles.children[0].children[1].setRect({x:50, y:50, width: 100, height: 50})
here is a list of all signal classes that are currently available:
a signal-based reactivity system can be thought of as a DAG (directed acyclic graph) - which is something that resembles a dependency graph.
in a DAG, each signal object is a node/vertex of the graph, and each directed-relation (or dependency) is described as an edge of the graph.
we use the following notation to describe one relation in our graph:
SourceSignal -> [DestinationSignal_1, DestinationSignal_2, DestinationSignal_3, ...]
which is basically saying that: updating SourceSignal
should result in an update in DestinationSignal_1
, DestinationSignal_2
, etc... .
or another way of reading it is: each of DestinationSignal_1
, DestinationSignal_2
, and etc... depend on SourceSignal
(i.e. the destination signals are observers of SourceSignal
).
a DAG graph can then be described as a series/array of relations:
MyGraph = [
Signal_A -> [Signal_B, Signal_C],
Signal_B -> [Signal_D, Signal_F],
Signal_C -> [Signal_E, Signal_F, Signal_H],
...
]
a topologically sorted array of the nodes of a DAG is basically an array of the nodes, where every dependency node appears before the node which depends on it.
so, for example the following DAG graph:
---
title: "graph"
---
flowchart LR
332796(("A")) --> 590207(("B"))
332796 --> 763885(("C"))
590207 --> 562158(("D"))
763885 --> 932932(("E"))
763885 --> 940461(("H"))
562158 --> 831043(("G"))
831043 --> 450102(("I"))
932932 --> 940461
940461 --> 450102
590207 --> 270457(("F"))
562158 --> 270457
763885 --> 270457
932932 --> 270457
450102 --> 770803(("J"))
graph = [ A->[B, C] , B->[D, F] , C->[E, F, H] , D->[F, G] , E->[F, H] , F->[I] , G->[I] , H->[I] , I->[J] ]
has the following (non-unique) topologically sorted array:
nodes_sorted = [ A, B, D, G, C, E, H, F, I, J ]
in this library, during an update cycle, when a signal is executed to update (through its run method
in {@link typedefs!Signal.run}), it returns the numeric enum SignalUpdateStatus
, which conveys a specific instruction to the Context
's update loop:
-
1
orSignalUpdateStatus.UPDATED
: this signal's value has been updated, and therefore its observers should be updated too. -
0
orSignalUpdateStatus.UNCHANGED
: this signal's value has not changed, and therefore its observers should be not be updated by this signal. do note that an observer signal will still run if some other of its dependency signal did update this cycle (i.e. had a status value of1
). -
-1
orSignalUpdateStatus.ABORTED
: this signal has been aborted, and therefore its observers must abort execution as well. the observers will abort even if they had a dependency that did update (had a status value of1
). should the aborted observer signal also abort its own observers? that's a thing that is open to debate. currently, it does not abort its own observers.
given an array of source_ids
to initiate the signal from (simultaneously),
the Context
's update cycle ({@link context!Context.fireUpdateCycle}) works by following the steps below:
- starting with the
source_ids
, sort the DAG graph into a topologically ordered arraytopological_ids
(via DFS), where:-
source_ids
are always at the beginning of thetopological_ids
array.
-
- create an empty set of signal ids called
not_to_visit
, which will contain the signals whose dependencies (at least one) have declared an aborted status (SignalUpdateStatus.ABORTED
). - create an empty set of signal ids called
next_to_visit
, which will contain the signals that are awaiting/in-queue to be executed next. - fill the set
next_to_visit
with our initialsource_ids
- now, in an ordered loop, for each
id
inside oftopological_ids
(starting with the source ids), do:- check that
id
exists innext_to_visit
ANDid
does not exist inside ofnot_to_visit
. if true, then:- delete
id
fromnext_to_visit
- run the signal associated with the
id
, and save its execution's returnedSignalUpdateStatus
tostatus
. - is
status == SignalUpdateStatus.UPDATED
(i.e.status == 1
)? if true, then:- for every
observer_id
of this signal'sid
, addobserver_id
tonext_to_visit
- for every
- is
status == SignalUpdateStatus.ABORTED
(i.e.status == -1
)? if true, then:- for every
observer_id
of this signal'sid
, addobserver_id
tonot_to_visit
- for every
- delete
- is
next_to_visit
set now empty? if true, then:- terminate/break the loop early, since there is no way any more ids will ever be added to
next_to_visit
- terminate/break the loop early, since there is no way any more ids will ever be added to
- check that
starting with the following graph
, and its topological_ids
sorted array, and the initial source_ids
:
graph = [ A->[B, C] , B->[D, F] , C->[E, F, H] , D->[F, G] , E->[F, H] , F->[I] , G->[I] , H->[I] , I->[J] ]
topological_ids = [ A, B, D, G, C, E, H, F, I, J ]
source_ids = [ A, ]
and assuming that signal B
does not change when executed (i.e. status = SignalUpdateStatus.UNCHANGED
), we get the following update cycle:
- assign
not_to_visit = { }
- assign
next_to_visit = {A}
-
id
= A:next_to_visit == {}
-
status = run(A)
== 1- add each of
graph[A]
= [B, C] tonext_to_visit
- add each of
-
next_to_visit == {B, C}
and is not empty -
id
= B:next_to_visit == {C}
-
status = run(B)
== 0
-
next_to_visit == {C}
and is not empty -
id
= D: skipped because it is not innext_to_visit
-
next_to_visit == {C}
and is not empty -
id
= G: skipped because it is not innext_to_visit
-
next_to_visit == {C}
and is not empty -
id
= C:next_to_visit == {}
-
status = run(C)
== 1- add each of
graph[C]
= [E, F, H] tonext_to_visit
- add each of
-
next_to_visit == {E, F, H}
and is not empty -
id
= E:next_to_visit == {F, H}
-
status = run(E)
== 1- add each of
graph[E]
= [F, H] tonext_to_visit
- add each of
-
next_to_visit == {F, H}
and is not empty -
id
= H:next_to_visit == {F}
-
status = run(H)
== 1- add each of
graph[H]
= [I] tonext_to_visit
- add each of
-
next_to_visit == {F, I}
and is not empty -
id
= F:next_to_visit == {I}
-
status = run(F)
== 1- add each of
graph[F]
= [I] tonext_to_visit
- add each of
-
next_to_visit == {I}
and is not empty -
id
= I:next_to_visit == {}
-
status = run(I)
== 1- add each of
graph[I]
= [J] tonext_to_visit
- add each of
-
next_to_visit == {J}
and is not empty -
id
= I:next_to_visit == {}
-
status = run(I)
== 1- add each of
graph[J]
= [ ] tonext_to_visit
- add each of
-
next_to_visit == { }
and is empty, so terminate
recomputing the topologically ordered signal ids at the beginning of every update cycle is wasteful,
so instead, we memorize the result of a topological ordering when certain the update is initiated from a certain source_ids
.
in order to memorize the result, we first hash the array source_ids
to a number
that is invariant to the positional ordering of the ids inside of source_ids
.
the hashing function is defined in hash_ids
({@link funcdefs!hash_ids}),
and the memorization/caching function is defined in get_ids_to_visit
({@link context!get_ids_to_visit}).
the cache is only valid if no mutations to the DAG graph (addition or deletion of nodes or edges) have been done.
that's why we clear the cache whenever a mutative action is taken within the Context
's graph, such as:
- introducing a new signal
- a signal declares a new dependency or observer
- deleting a signal
TODO: explain the difference between a signal's id
and its rid
. then explain how non-zero rid
are an idication for a new observation.