Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | 731x 145x 145x 145x 145x 399x 1x 399x 399x 145x 90x 55x 1x 55x 1x 55x 55x 342x 684x 2x 55x 1x 55x 3x 345x 52x 339x 52x 3x 49x 49x 49x 319x 331x 270x 270x 338x 49x 15x 34x 52x 52x 345x 345x 339x 339x 7x 338x 338x 341x | // Graph shape shared with the PHP engine (classes/local/engine/graph.php). The same
// rules are checked on both sides: the editor for quick feedback, the server for trust.
export interface GraphNode {
id: string;
type: string;
data: Record<string, unknown>;
position?: { x: number; y: number };
}
export interface GraphEdge {
id: string;
source: string;
target: string;
sourceHandle?: string;
}
export interface Graph {
nodes: GraphNode[];
edges: GraphEdge[];
}
export type GraphErrorCode = 'notrigger' | 'manytriggers' | 'duplicateid' | 'danglingedge' | 'cycle' | 'unreachable';
export interface GraphError {
code: GraphErrorCode;
nodeIds?: string[];
}
export const isTrigger = (type: string): boolean => type.startsWith('trigger.');
/** Every problem that stops a graph from running. An empty list means it is valid. */
export function validateGraph(graph: Graph): GraphError[] {
const errors: GraphError[] = [];
const ids = new Set<string>();
const duplicates = new Set<string>();
for (const n of graph.nodes) {
if (ids.has(n.id)) {
duplicates.add(n.id);
}
ids.add(n.id);
}
const triggers = graph.nodes.filter((n) => isTrigger(n.type)).map((n) => n.id);
if (triggers.length === 0) {
return [{ code: 'notrigger' }];
}
if (triggers.length > 1) {
errors.push({ code: 'manytriggers', nodeIds: triggers });
}
if (duplicates.size > 0) {
errors.push({ code: 'duplicateid', nodeIds: [...duplicates] });
}
const dangling = new Set<string>();
for (const e of graph.edges) {
for (const end of [e.target, e.source]) {
if (!ids.has(end)) {
dangling.add(end);
}
}
}
if (dangling.size > 0) {
errors.push({ code: 'danglingedge', nodeIds: [...dangling] });
}
if (errors.length > 0) {
return errors;
}
// Every edge now joins two known nodes.
const next = new Map<string, string[]>([...ids].map((id) => [id, []]));
for (const e of graph.edges) {
(next.get(e.source) as string[]).push(e.target);
}
if (hasCycle([...ids], next)) {
return [{ code: 'cycle' }];
}
const reached = new Set<string>([triggers[0]]);
const queue = [triggers[0]];
while (queue.length > 0) {
for (const target of next.get(queue.shift() as string) as string[]) {
if (!reached.has(target)) {
reached.add(target);
queue.push(target);
}
}
}
const unreachable = [...ids].filter((id) => !reached.has(id));
if (unreachable.length > 0) {
return [{ code: 'unreachable', nodeIds: unreachable }];
}
return [];
}
/** Depth-first search with three colours: a grey node reached again means a cycle. */
function hasCycle(ids: string[], next: Map<string, string[]>): boolean {
const state = new Map<string, 'grey' | 'black'>();
const visit = (id: string): boolean => {
state.set(id, 'grey');
for (const target of next.get(id) as string[]) {
const s = state.get(target);
if (s === 'grey' || (s === undefined && visit(target))) {
return true;
}
}
state.set(id, 'black');
return false;
};
// Stryker disable next-line ConditionalExpression: revisiting a finished node here costs one step and changes nothing.
return ids.some((id) => state.get(id) === undefined && visit(id));
}
|