workflow 0.0.1-preview.1
Incremental workflow engine: steps, dependencies, fingerprints, caching, and services
workflow#
An incremental workflow execution engine for Zena: dependency graphs, content fingerprints, cache keys with early cutoff, fine-grained per-output invalidation, and on-demand service lifecycles.
workflow performs no I/O of its own. Hosts supply leaf fingerprints, a digest function, a step cache, and step callbacks; the engine schedules work in dependency order with bounded parallelism and returns the updated state.
Installation#
zena pkg add zena-lang:workflow
Example#
import { NullCache } from 'zena-lang:workflow/cache';
import { Engine, StepSource, Succeeded } from 'zena-lang:workflow/engine';
import { Fingerprint } from 'zena-lang:workflow/fingerprint';
import { Graph } from 'zena-lang:workflow/graph';
import { OutputEntry, OutputManifest } from 'zena-lang:workflow/manifest';
import { EngineState } from 'zena-lang:workflow/state';
import { LeafInput, StepKey, StepOutputs, TaskStep } from 'zena-lang:workflow/step';
let compile = new TaskStep(
new StepKey('compile'),
new Fingerprint('cmd:compile-v1'),
[new LeafInput('src/main.zena')],
async (ctx) => {
return new OutputManifest([
new OutputEntry('out/main.wasm', new Fingerprint('wasm-hash-1')),
]);
},
);
let bundle = new TaskStep(
new StepKey('bundle'),
new Fingerprint('cmd:bundle-v1'),
[new StepOutputs(new StepKey('compile'))],
async (ctx) => {
return new OutputManifest([
new OutputEntry('dist/app.wasm', new Fingerprint('bundle-hash-1')),
]);
},
);
let graph = new Graph([compile, bundle]);
let leaves = {'src/main.zena' => new Fingerprint('src-hash-1')};
let engine = new Engine((data) => new Fingerprint( sha256(data) ), new NullCache());
// First run executes both steps in topological order.
let first = await engine.run(graph, leaves, EngineState.empty());
// Second run with identical inputs and prior state is a no-op (StepSource.Fresh).
let second = await engine.run(graph, leaves, first.state);
Core Concepts#
- Steps and inputs (
workflow/step):TaskStep: runs to completion and returns anOutputManifest.ServiceStep: starts on demand only when a dependent step actually executes, and stops when its last dependent settles (or stays pinned across watch runs in aServicePool).LeafInput(name): a named external input resolved from theleavesmap passed toEngine.run.LeafSet(name, resolve): a lazy input set resolved after upstream dependencies finish (for example, expanding globs over generated files).StepOutputs(step): a dependency on another step whose output manifest (or service identity) enters this step's cache key. Because dependents key on upstream output fingerprints rather than upstream input fingerprints, an upstream step that reruns and produces identical outputs leaves downstream dependents fresh (early cutoff).StepOrder(step): an ordering-only dependency (like Wireit's"cascade": false) that waits for the upstream step without folding its outputs into the dependent's cache key.
- Validated graph (
workflow/graph):Graphchecks that step keys are unique, all referenced steps exist, no step lists duplicate inputs, and the dependency graph is acyclic (reporting the cycle path inWorkflowError), producing a deterministic topological order. - Caching and freshness (
workflow/engine,workflow/cache,workflow/state):- If a step's
CacheKeymatches theStepRecordin the previousEngineState(and optionalRunOptions.verifyOutputssucceeds), the step isStepSource.Freshwithout consulting the cache or starting services. - Otherwise
StepCache.getis checked (StepSource.Cache), falling back to executing the step callback (StepSource.Ran) under the run's parallelism limit.
- If a step's
- Incremental per-output deltas (
workflow/delta,workflow/manifest):- Each
OutputEntryin anOutputManifestcan recorddependsOn(the namespaced inputsleaf:...,step:...it was derived from). - When a step reruns with the same
configfingerprint,RunContextprovidesdelta(changed,added,removed),previous(OutputManifest), andstaleOutputs. The engine verifies before caching that any output carried over as non-stale kept its previous fingerprint.
- Each
Libraries#
workflow/engine—Engine,RunOptions,RunResult,StepOutcome(Succeeded,Failed,Skipped),StepSource,ServicePool, andPinnedService.workflow/step—Step,TaskStep,ServiceStep,StepKey,InputRef(LeafInput,LeafSet,StepOutputs,StepOrder),RunContext,ServiceContext, andServiceHandle.workflow/graph—Graphvalidation and deterministic topological sorting.workflow/manifest—OutputManifestandOutputEntry.workflow/state—EngineStateandStepRecordfor persisting prior-run state across runs.workflow/cache—StepCacheinterface andNullCache.workflow/fingerprint—Fingerprint,CacheKey, andDigest.workflow/canonical— Canonical length-prefixed encodings (cacheKeyFor,manifestFingerprint,ResolvedInput,compareStrings,sortBy).workflow/delta—InputDelta,computeDelta, andstaleOutputNames.workflow/errors—WorkflowError.
License#
MIT
5.8 KiB
Raw
import { HashSet } from 'zena:collections';
import {StringBuilder} from 'zena:core';
import {WorkflowError} from './errors.zena';
import {LeafInput, LeafSet, StepKey, StepOrder, StepOutputs, Step} from './step.zena';
/**
* A validated set of steps. Construction checks that step keys are
* unique, that every step reference names a step in the set, that no
* step lists the same input twice, and that the dependency graph is
* acyclic; it fails loudly otherwise. Steps come back out in a
* topological order.
*/
export class Graph {
#byKey: HashMap<String, Step>;
#order: GrowableArray<Step>;
/**
* Steps in a topological order: dependencies before dependents.
* Deterministic — derived from the construction order, not from hash
* iteration.
*/
steps: Array<Step> {
get {
return this.#order;
}
}
size: i32 {
get {
return this.#order.length;
}
}
new(steps: Array<Step>)
: #byKey = new HashMap<String, Step>(),
#order = new GrowableArray<Step>() {
for (let step in steps) {
if (this.#byKey.has(step.key.value)) {
throw new WorkflowError('duplicate step key: ' + step.key.value);
}
this.#byKey[step.key.value] = step;
}
let depKeys = new HashMap<String, GrowableArray<String>>();
let dependents = new HashMap<String, GrowableArray<String>>();
let indegree = new HashMap<String, i32>();
for (let step in steps) {
let seen = new HashSet<String>();
let deps = new GrowableArray<String>();
for (let input in step.inputs) {
match (input) {
case LeafInput as leaf: {
if (!seen.add('leaf:' + leaf.name)) {
throw new WorkflowError(
`step "${step.key.value}" lists leaf input "${leaf.name}" twice`,
);
}
}
case LeafSet as leafSet: {
if (!seen.add('leafset:' + leafSet.name)) {
throw new WorkflowError(
`step "${step.key.value}" lists leaf set "${leafSet.name}" twice`,
);
}
}
case StepOutputs as dep: {
let depKey = dep.step.value;
if (!this.#byKey.has(depKey)) {
throw new WorkflowError(
`step "${step.key.value}" depends on unknown step "${depKey}"`,
);
}
if (!seen.add('step:' + depKey)) {
throw new WorkflowError(
`step "${step.key.value}" depends on step "${depKey}" twice`,
);
}
deps.push(depKey);
}
case StepOrder as dep: {
let depKey = dep.step.value;
if (!this.#byKey.has(depKey)) {
throw new WorkflowError(
`step "${step.key.value}" depends on unknown step "${depKey}"`,
);
}
if (!seen.add('step:' + depKey)) {
throw new WorkflowError(
`step "${step.key.value}" depends on step "${depKey}" twice`,
);
}
deps.push(depKey);
}
}
}
depKeys[step.key.value] = deps;
indegree[step.key.value] = deps.length;
for (let depKey in deps) {
if (let (true, list) = dependents.get(depKey)) {
list.push(step.key.value);
} else {
let list = new GrowableArray<String>();
list.push(step.key.value);
dependents[depKey] = list;
}
}
}
// Kahn's algorithm. Ready steps are processed in construction
// order, so the result is deterministic.
let ready = new GrowableArray<Step>();
for (let step in steps) {
if (indegree.getOr(step.key.value, 0) == 0) {
ready.push(step);
}
}
var next = 0;
while (next < ready.length) {
let step = ready[next];
next += 1;
this.#order.push(step);
if (let (true, list) = dependents.get(step.key.value)) {
for (let dependentKey in list) {
let remaining = indegree.getOr(dependentKey, 0) - 1;
indegree[dependentKey] = remaining;
if (remaining == 0) {
if (let (true, dependent) = this.#byKey.get(dependentKey)) {
ready.push(dependent);
}
}
}
}
}
if (this.#order.length < steps.length) {
throw new WorkflowError(
'dependency cycle: ' + cyclePath(steps, indegree, depKeys),
);
}
}
get(key: StepKey): Step? {
if (let (true, step) = this.#byKey.get(key.value)) {
return step;
}
return null;
}
}
/**
* Renders one cycle from the steps Kahn's algorithm could not order
* (those with remaining positive indegree). Walking first-remaining
* dependencies from any such step must revisit a step, and the path
* from the first visit is a cycle.
*/
function cyclePath(
steps: Array<Step>,
indegree: HashMap<String, i32>,
depKeys: HashMap<String, GrowableArray<String>>,
): String {
var start: String? = null;
for (let step in steps) {
if (indegree.getOr(step.key.value, 0) > 0) {
start = step.key.value;
break;
}
}
let chain = new GrowableArray<String>();
let position = new HashMap<String, i32>();
var current = start;
while (current != null) {
if (let (true, pos) = position.get(current)) {
let sb = new StringBuilder();
for (var i = pos; i < chain.length; i += 1) {
sb.append(chain[i]);
sb.append(' -> ');
}
sb.append(current);
return sb.toString();
}
position[current] = chain.length;
chain.push(current);
var nextKey: String? = null;
if (let (true, deps) = depKeys.get(current)) {
for (let depKey in deps) {
if (indegree.getOr(depKey, 0) > 0) {
nextKey = depKey;
break;
}
}
}
current = nextKey;
}
throw new WorkflowError('cycle reporting failed');
}
| Version | Published | Dependencies | Approved by |
|---|---|---|---|
| 0.0.1-preview.1 | 2026-11-19 | none |
|