conductor

CI task system
git clone git://git.finwo.net/app/conductor
Log | Files | Refs | README | LICENSE

dag.test.js (4036B)

      1 // test/dag.test.js - dependency graph traversal
      2 //
      3 // These cover the two scheduling defects carried over from the prototype:
      4 // serialized dispatch, and a failure cascade that only skipped direct
      5 // dependents.
      6 
      7 import test from 'node:test';
      8 import assert from 'node:assert/strict';
      9 import { topologicalOrder, depths, transitiveDependents, runnable, CycleError } from '../src/lib/pipeline/dag.js';
     10 
     11 // a -> b -> d, a -> c -> d, plus an unrelated island.
     12 const GRAPH = [
     13   { name: 'a', needs: [] },
     14   { name: 'b', needs: ['a'] },
     15   { name: 'c', needs: ['a'] },
     16   { name: 'd', needs: ['b', 'c'] },
     17   { name: 'island', needs: [] },
     18 ];
     19 
     20 function states(overrides = {}) {
     21   const map = new Map(GRAPH.map((j) => [j.name, 'queued']));
     22   for (const [k, v] of Object.entries(overrides)) map.set(k, v);
     23   return map;
     24 }
     25 
     26 test('topological order places dependencies first', () => {
     27   const order = topologicalOrder(GRAPH).map((j) => j.name);
     28   assert.ok(order.indexOf('a') < order.indexOf('b'));
     29   assert.ok(order.indexOf('a') < order.indexOf('c'));
     30   assert.ok(order.indexOf('b') < order.indexOf('d'));
     31   assert.ok(order.indexOf('c') < order.indexOf('d'));
     32 });
     33 
     34 test('topological order is deterministic', () => {
     35   const first = topologicalOrder(GRAPH).map((j) => j.name);
     36   const shuffled = [...GRAPH].reverse();
     37   assert.deepEqual(topologicalOrder(shuffled).map((j) => j.name), first);
     38 });
     39 
     40 test('a cycle is detected and named', () => {
     41   const cyclic = [
     42     { name: 'x', needs: ['z'] },
     43     { name: 'y', needs: ['x'] },
     44     { name: 'z', needs: ['y'] },
     45   ];
     46   assert.throws(() => topologicalOrder(cyclic), CycleError);
     47   try {
     48     topologicalOrder(cyclic);
     49   } catch (e) {
     50     // The reported path returns to where it started.
     51     assert.equal(e.cycle[0], e.cycle[e.cycle.length - 1]);
     52   }
     53 });
     54 
     55 test('depth reflects the longest path, not insertion order', () => {
     56   const d = depths(GRAPH);
     57   assert.equal(d.get('a'), 0);
     58   assert.equal(d.get('island'), 0);
     59   assert.equal(d.get('b'), 1);
     60   assert.equal(d.get('d'), 2);
     61 });
     62 
     63 test('independent tasks are runnable at the same time', () => {
     64   // The prototype could only ever return one task here.
     65   const ready = runnable(GRAPH, states()).map((j) => j.name);
     66   assert.deepEqual(ready.sort(), ['a', 'island']);
     67 });
     68 
     69 test('a task becomes runnable only once every dependency succeeds', () => {
     70   assert.deepEqual(
     71     runnable(GRAPH, states({ a: 'success', b: 'success' })).map((j) => j.name).sort(),
     72     ['c', 'island']
     73   );
     74   assert.deepEqual(
     75     runnable(GRAPH, states({ a: 'success', b: 'success', c: 'success', island: 'success' })).map((j) => j.name),
     76     ['d']
     77   );
     78 });
     79 
     80 test('a running dependency does not release its dependents', () => {
     81   assert.equal(runnable(GRAPH, states({ a: 'running' })).some((j) => j.name === 'b'), false);
     82 });
     83 
     84 test('failure skips transitive dependents, not just direct ones', () => {
     85   // This is the prototype bug: it would have skipped only b and c, leaving
     86   // d queued and dispatchable with its inputs missing.
     87   const skipped = transitiveDependents(GRAPH, ['a']);
     88   assert.deepEqual([...skipped].sort(), ['b', 'c', 'd']);
     89   assert.equal(skipped.has('island'), false);
     90 });
     91 
     92 test('a skipped dependency never releases a dependent', () => {
     93   assert.equal(runnable(GRAPH, states({ a: 'failed' })).some((j) => j.name === 'b'), false);
     94   assert.equal(runnable(GRAPH, states({ a: 'skipped' })).some((j) => j.name === 'b'), false);
     95 });
     96 
     97 test('allowed failures can satisfy a dependency when asked to', () => {
     98   const ready = runnable(GRAPH, states({ a: 'failed' }), { satisfied: ['success', 'failed'] });
     99   assert.deepEqual(ready.map((j) => j.name).sort(), ['b', 'c', 'island']);
    100 });
    101 
    102 test('transitive dependents of a leaf is empty', () => {
    103   assert.equal(transitiveDependents(GRAPH, ['d']).size, 0);
    104 });
    105 
    106 test('graph helpers tolerate dependencies outside the set', () => {
    107   const partial = [{ name: 'only', needs: ['absent'] }];
    108   assert.deepEqual(topologicalOrder(partial).map((j) => j.name), ['only']);
    109   assert.equal(depths(partial).get('only'), 0);
    110 });