You are given a partially specified backend component. Produ...

Prompt

You are given a partially specified backend component. Produce a complete, production-quality implementation in TypeScript. Your entire answer must contain: 1. One TypeScript code block containing the complete implementation. 2. A brief section titled “Design decisions”. 3. A brief section titled “Complexity”. 4. Nothing else. Do not use external packages. Do not use Node-specific APIs. The implementation must compile under TypeScript strict mode. # Task: Deterministic in-memory workflow engine Implement the following public API exactly: type JobStatus = | "pending" | "leased" | "waiting" | "succeeded" | "failed" | "cancelled"; interface JobDefinition { id: string; dependencies?: string[]; maxAttempts: number; retryDelayMs: number; payload: unknown; } interface WorkflowDefinition { id: string; jobs: JobDefinition[]; } interface Lease { workflowId: string; jobId: string; workerId: string; token: string; attempt: number; expiresAt: number; payload: unknown; } interface JobView { id: string; status: JobStatus; dependencies: string[]; attempts: number; availableAt: number; leasedBy?: string; leaseToken?: string; leaseExpiresAt?: number; result?: unknown; failure?: string; } interface WorkflowView { id: string; status: "running" | "succeeded" | "failed" | "cancelled"; jobs: JobView[]; } interface EngineEvent { sequence: number; timestamp: number; workflowId: string; jobId?: string; type: | "workflow_created" | "job_leased" | "lease_expired" | "job_retry_scheduled" | "job_succeeded" | "job_failed" | "workflow_succeeded" | "workflow_failed" | "workflow_cancelled"; data: Readonly<Record<string, unknown>>; } class WorkflowError extends Error { readonly code: | "INVALID_ARGUMENT" | "WORKFLOW_EXISTS" | "WORKFLOW_NOT_FOUND" | "JOB_NOT_FOUND" | "INVALID_GRAPH" | "INVALID_LEASE" | "INVALID_STATE"; constructor(code: WorkflowError["code"], message: string); } class WorkflowEngine { createWorkflow(definition: WorkflowDefinition, now: number): void; claimNext( workflowId: string, workerId: string, now: number, leaseDurationMs: number ): Lease | null; complete( workflowId: string, jobId: string, workerId: string, leaseToken: string, result: unknown, now: number ): void; fail( workflowId: string, jobId: string, workerId: string, leaseToken: string, reason: string, now: number ): void; cancelWorkflow(workflowId: string, now: number): void; getWorkflow(workflowId: string): WorkflowView; getEvents(afterSequence?: number): EngineEvent[]; exportSnapshot(): string; static fromSnapshot(snapshot: string): WorkflowEngine; } # Required behaviour ## General validation All public methods must reject non-finite numeric values. Identifiers and failure reasons must be non-empty after trimming. `maxAttempts` must be a positive integer. `retryDelayMs` must be a non-negative integer. `leaseDurationMs` must be a positive integer. Throw `WorkflowError` with code `INVALID_ARGUMENT` for these violations. Use only the supplied `now` values. Never call `Date.now()`. A method that throws must be atomic: no observable engine state, event, sequence number, attempt count, lease, or workflow status may change. ## Creating workflows Workflow IDs must be unique. Duplicate IDs produce `WORKFLOW_EXISTS`. A workflow must contain at least one job. Job IDs must be unique within the workflow. Every dependency must reference another job in the same workflow. A job cannot depend on itself. The dependency graph must be acyclic. Invalid workflow graphs produce `INVALID_GRAPH`. Dependency order and duplicate dependency entries in input are irrelevant. Store each job’s dependencies as a unique lexicographically sorted array. The engine must not retain mutable references supplied by the caller. Initially: - Jobs with no dependencies are `pending`. - Jobs with dependencies are `waiting`. - `attempts` is 0. - `availableAt` equals `now`. - The workflow is `running`. Append one `workflow_created` event. ## Claiming work Only running workflows may lease jobs. Before selecting a job, process every expired lease in that workflow where `leaseExpiresAt <= now`. Process expired leases in lexicographic job-ID order. Each expired lease appends one `lease_expired` event and removes all lease ownership information. Lease expiry does not itself increment `attempts`; the attempt was already counted when the lease was issued. After expiry: - If `attempts < maxAttempts`, set the job to `pending` and set `availableAt = now + retryDelayMs * 2 ** (attempts - 1)`. Append `job_retry_scheduled`. - Otherwise set the job to `failed`, preserve the failure string `"lease expired"`, and append `job_failed`. After processing expirations, recompute workflow and waiting-job states as described below. A job is claimable only when: - Its status is `pending`. - `availableAt <= now`. - Every dependency has status `succeeded`. If multiple jobs are claimable, select the lexicographically smallest job ID. When leasing: - Increment `attempts`. - Set status to `leased`. - Store the worker ID. - Set expiry to `now + leaseDurationMs`. - Generate the lease token deterministically as: `${workflowId}:${jobId}:${attempts}:${eventSequence}` where `eventSequence` is the sequence number that will be assigned to the new `job_leased` event. - Append `job_leased`. - Return a detached copy of the lease and payload. Return `null` when no job is claimable. Calling `claimNext` may still mutate state by expiring leases, even when it ultimately returns `null`. ## Completing jobs The workflow must be running and the job must currently be leased. The worker ID and lease token must exactly match the active lease. The lease is invalid when `leaseExpiresAt <= now`. Any ownership, token, state, or expiry mismatch produces `INVALID_LEASE`. Successful completion: - Sets the job to `succeeded`. - Stores a detached copy of `result`. - Removes lease information. - Appends `job_succeeded`. - Recomputes waiting-job and workflow states. A succeeded job cannot be completed again. ## Failing jobs Use the same lease validation rules as completion. After a valid failure, remove lease information. If `attempts < maxAttempts`: - Set status to `pending`. - Store the supplied failure reason. - Set: `availableAt = now + retryDelayMs * 2 ** (attempts - 1)` - Append `job_retry_scheduled`. Otherwise: - Set status to `failed`. - Store the supplied failure reason. - Append `job_failed`. Then recompute waiting-job and workflow states. ## Dependency and workflow propagation After any terminal job transition or lease-expiry processing: - A `waiting` job becomes `pending` once all dependencies succeed. - Its `availableAt` becomes the current operation’s `now`. - A waiting or pending job becomes `cancelled` when any dependency is `failed` or `cancelled`. - A leased job is never cancelled through dependency propagation because all dependencies had to succeed before it was leased. Propagation must continue until no status changes remain. A running workflow becomes: - `failed` when at least one job is `failed`. - Otherwise `succeeded` when every job is `succeeded`. - Otherwise it remains `running`. When a workflow first becomes failed, cancel every non-terminal, non-leased job and append exactly one `workflow_failed` event. When it first becomes succeeded, append exactly one `workflow_succeeded` event. Do not emit events for dependency-propagated job cancellation. ## Cancellation Cancelling a missing workflow produces `WORKFLOW_NOT_FOUND`. Cancelling an already terminal workflow produces `INVALID_STATE`. Set the workflow status to `cancelled`. Set every non-terminal job, including leased jobs, to `cancelled`. Remove all active lease information. Append exactly one `workflow_cancelled` event. ## Lookup and isolation Missing workflow or job lookups must use `WORKFLOW_NOT_FOUND` or `JOB_NOT_FOUND` as appropriate. `getWorkflow` returns jobs sorted lexicographically by ID. `getEvents()` returns every event. `getEvents(afterSequence)` returns only events with `sequence > afterSequence`. Event sequence numbers begin at 1 and are contiguous. All returned values must be detached from internal state. Mutating input objects, returned views, leases, events, results, payloads, or parsed snapshots must not mutate the engine. You may support only JSON-compatible payloads and results. Values that cannot be safely cloned as JSON-compatible data must produce `INVALID_ARGUMENT`. ## Snapshots `exportSnapshot()` must return deterministic JSON: - The same logical engine state must always produce byte-for-byte identical output. - Workflows and jobs must be lexicographically sorted. - Object keys must have deterministic ordering. - Event order must remain sequence order. - All state required to continue execution identically must be included. `fromSnapshot()` must validate the complete snapshot before accepting it. It must reject malformed JSON, invalid fields, broken graph references, cycles, impossible statuses, invalid leases, non-contiguous event sequences, duplicate IDs, and any state inconsistent with the rules above. Snapshot failures produce `WorkflowError("INVALID_ARGUMENT", ...)`. Restoring and immediately exporting a valid snapshot must produce exactly the same string. # Additional constraints - Do not use `any`. - Do not use type assertions to bypass validation, such as `as any` or double assertions through `unknown`. - Do not expose internal mutable collections. - Do not silently repair invalid snapshots. - Do not omit snapshot validation. - Do not replace the requested API with a different design. - Keep helper functions private or outside the class. - Include all interfaces, types, errors, and implementation in the code block.