2021-12-01 16:24:29 +00:00
|
|
|
|
/// SPDX-License-Identifier: GPL-3.0-or-later
|
2022-01-26 13:38:38 +00:00
|
|
|
|
/// SPDX-FileCopyrightText: Copyright © 2016-2022 Tony Garnock-Jones <tonyg@leastfixedpoint.com>
|
2021-01-11 22:35:36 +00:00
|
|
|
|
|
|
|
|
|
// Property-based "dataflow"
|
|
|
|
|
|
2021-12-02 13:40:24 +00:00
|
|
|
|
import { FlexSet, FlexMap, Canonicalizer, Value, is } from '@preserves/core';
|
2021-12-02 23:55:42 +00:00
|
|
|
|
import { Ref } from './actor.js';
|
2021-01-11 22:35:36 +00:00
|
|
|
|
import * as MapSet from './mapset.js';
|
|
|
|
|
|
2021-12-02 13:40:24 +00:00
|
|
|
|
export interface ObservingGraph<ObjectId> {
|
|
|
|
|
recordObservation(objectId: ObjectId): void;
|
|
|
|
|
recordDamage(objectId: ObjectId): void;
|
|
|
|
|
}
|
2021-01-11 22:35:36 +00:00
|
|
|
|
|
2021-12-02 13:40:24 +00:00
|
|
|
|
export class Graph<SubjectId, ObjectId> implements ObservingGraph<ObjectId> {
|
2021-01-11 22:35:36 +00:00
|
|
|
|
readonly edgesForward: FlexMap<ObjectId, FlexSet<SubjectId>>;
|
|
|
|
|
readonly edgesReverse: FlexMap<SubjectId, FlexSet<ObjectId>>;
|
|
|
|
|
readonly subjectIdCanonicalizer: Canonicalizer<SubjectId>;
|
|
|
|
|
readonly objectIdCanonicalizer: Canonicalizer<ObjectId>;
|
|
|
|
|
damagedNodes: FlexSet<ObjectId>;
|
|
|
|
|
currentSubjectId: SubjectId | undefined;
|
|
|
|
|
|
|
|
|
|
constructor(subjectIdCanonicalizer: Canonicalizer<SubjectId>,
|
|
|
|
|
objectIdCanonicalizer: Canonicalizer<ObjectId>)
|
|
|
|
|
{
|
|
|
|
|
this.edgesForward = new FlexMap(objectIdCanonicalizer);
|
|
|
|
|
this.edgesReverse = new FlexMap(subjectIdCanonicalizer);
|
|
|
|
|
this.subjectIdCanonicalizer = subjectIdCanonicalizer;
|
|
|
|
|
this.objectIdCanonicalizer = objectIdCanonicalizer;
|
|
|
|
|
this.damagedNodes = new FlexSet(objectIdCanonicalizer);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
withSubject<T>(subjectId: SubjectId | undefined, f: () => T): T {
|
|
|
|
|
let oldSubjectId = this.currentSubjectId;
|
|
|
|
|
this.currentSubjectId = subjectId;
|
|
|
|
|
let result: T;
|
|
|
|
|
try {
|
|
|
|
|
result = f();
|
|
|
|
|
} catch (e) {
|
|
|
|
|
this.currentSubjectId = oldSubjectId;
|
|
|
|
|
throw e;
|
|
|
|
|
}
|
|
|
|
|
this.currentSubjectId = oldSubjectId;
|
|
|
|
|
return result;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
recordObservation(objectId: ObjectId) {
|
|
|
|
|
if (this.currentSubjectId !== void 0) {
|
|
|
|
|
MapSet.add(this.edgesForward, objectId, this.currentSubjectId, this.subjectIdCanonicalizer);
|
|
|
|
|
MapSet.add(this.edgesReverse, this.currentSubjectId, objectId, this.objectIdCanonicalizer);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
recordDamage(objectId: ObjectId) {
|
|
|
|
|
this.damagedNodes.add(objectId);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
forgetSubject(subjectId: SubjectId) {
|
|
|
|
|
const subjectObjects = this.edgesReverse.get(subjectId) ?? [] as Array<ObjectId>;
|
|
|
|
|
this.edgesReverse.delete(subjectId);
|
|
|
|
|
subjectObjects.forEach((oid: ObjectId) => MapSet.del(this.edgesForward, oid, subjectId));
|
|
|
|
|
}
|
|
|
|
|
|
2021-01-29 14:37:27 +00:00
|
|
|
|
observersOf(objectId: ObjectId): Array<SubjectId> {
|
|
|
|
|
const subjects = this.edgesForward.get(objectId);
|
|
|
|
|
if (subjects === void 0) return [];
|
|
|
|
|
return Array.from(subjects);
|
|
|
|
|
}
|
|
|
|
|
|
2021-01-11 22:35:36 +00:00
|
|
|
|
repairDamage(repairNode: (subjectId: SubjectId) => void) {
|
|
|
|
|
let repairedThisRound = new FlexSet(this.objectIdCanonicalizer);
|
|
|
|
|
while (true) {
|
|
|
|
|
let workSet = this.damagedNodes;
|
|
|
|
|
this.damagedNodes = new FlexSet(this.objectIdCanonicalizer);
|
|
|
|
|
|
|
|
|
|
const alreadyDamaged = workSet.intersect(repairedThisRound);
|
|
|
|
|
if (alreadyDamaged.size > 0) {
|
|
|
|
|
console.warn('Cyclic dependencies involving', alreadyDamaged);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
workSet = workSet.subtract(repairedThisRound);
|
|
|
|
|
repairedThisRound = repairedThisRound.union(workSet);
|
|
|
|
|
|
|
|
|
|
if (workSet.size === 0) break;
|
|
|
|
|
|
|
|
|
|
workSet.forEach(objectId => {
|
2021-01-29 14:37:27 +00:00
|
|
|
|
this.observersOf(objectId).forEach((subjectId: SubjectId) => {
|
2021-01-11 22:35:36 +00:00
|
|
|
|
this.forgetSubject(subjectId);
|
|
|
|
|
this.withSubject(subjectId, () => repairNode(subjectId));
|
|
|
|
|
});
|
|
|
|
|
});
|
|
|
|
|
}
|
|
|
|
|
}
|
2021-12-02 13:40:24 +00:00
|
|
|
|
}
|
2021-01-11 22:35:36 +00:00
|
|
|
|
|
2021-12-02 13:40:24 +00:00
|
|
|
|
let __nextCellId = 0;
|
|
|
|
|
|
|
|
|
|
export abstract class Cell {
|
|
|
|
|
readonly id: string = '' + (__nextCellId++);
|
|
|
|
|
readonly graph: ObservingGraph<Cell>;
|
|
|
|
|
__value: unknown;
|
|
|
|
|
|
|
|
|
|
static readonly canonicalizer: Canonicalizer<Cell> = v => v.id;
|
|
|
|
|
|
|
|
|
|
constructor(graph: ObservingGraph<Cell>, initial: unknown) {
|
|
|
|
|
this.graph = graph;
|
|
|
|
|
this.__value = initial;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
observe(): unknown {
|
|
|
|
|
this.graph.recordObservation(this);
|
|
|
|
|
return this.__value;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
update(newValue: unknown) {
|
|
|
|
|
if (!this.valuesEqual(this.__value, newValue)) {
|
|
|
|
|
this.graph.recordDamage(this);
|
|
|
|
|
this.__value = newValue;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
abstract valuesEqual(v1: unknown, v2: unknown): boolean;
|
|
|
|
|
|
|
|
|
|
toString(): string {
|
|
|
|
|
return `𝐶<${this.__value}>`;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
export abstract class TypedCell<V> extends Cell {
|
|
|
|
|
constructor(graph: ObservingGraph<Cell>, initial: V) {
|
|
|
|
|
super(graph, initial);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
get value(): V {
|
|
|
|
|
return this.observe() as V;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
set value(v: V) {
|
|
|
|
|
this.update(v);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
abstract valuesEqual(v1: V, v2: V): boolean;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
export class Field<V extends Value<T>, T = Ref> extends TypedCell<V> {
|
|
|
|
|
readonly name: string | undefined;
|
|
|
|
|
|
|
|
|
|
constructor(graph: ObservingGraph<Cell>, initial: V, name?: string) {
|
|
|
|
|
super(graph, initial);
|
|
|
|
|
this.name = name;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
valuesEqual(v1: V, v2: V): boolean {
|
|
|
|
|
return is(v1, v2);
|
2021-01-11 22:35:36 +00:00
|
|
|
|
}
|
|
|
|
|
|
2021-12-02 13:40:24 +00:00
|
|
|
|
toString(): string {
|
|
|
|
|
return `𝐹<${this.name}=${this.__value}>`;
|
2021-01-11 22:35:36 +00:00
|
|
|
|
}
|
|
|
|
|
}
|