Plan CI Build Job Order with Prerequisites, Urgency and Filters

Your team's CI system receives a list of build jobs for each commit and must decide the order in which to dispatch them. The spec has many small rules. None of them is hard on its own, but together they are easy to get subtly wrong, so make every rule explicit and testable.

Each job looks like:

{"id": "test", "needs": ["compile"], "urgency": 4, "tags": ["slow"]}

needs lists jobs that must be dispatched earlier. A higher urgency is more important.

Part 1: Prerequisites first

plan(jobs, by_urgency=False) -> list[str] returns every job id so that each job comes after everything it needs. When several jobs are available, pick the one that appears earliest in the input. Raise an error for duplicate ids, unknown prerequisites, and cycles, and report one actual cycle path (for example x -> z -> y -> x).

Part 2: Urgency

With by_urgency=True, the next job is the available one with the highest urgency, with ties going to input order. Urgency never lets a job jump ahead of its prerequisites, and it does not pull prerequisites forward.

Part 3: Filters

plan(jobs, filters=[...]) takes predicates. A job is kept only if all of them return True. Excluded jobs are not output, but ordering through them is preserved: if kept job D needs excluded job B, and B needs kept job A, then D must still come after A.

Part 4: Parallel waves

waves(jobs) -> list[list[str]] groups jobs into stages. Wave 0 holds jobs with no prerequisites, and each later wave holds jobs whose prerequisites are all in earlier waves. Place each job in the earliest possible wave, and sort jobs within a wave by urgency (descending) and then input order.

Example

fetch   needs []                urgency 1
compile needs [fetch]           urgency 3
lint    needs [fetch]           urgency 5   tags [style]
test    needs [compile]         urgency 4
docs    needs []                urgency 2   tags [docs]
package needs [test, lint]      urgency 2
publish needs [package, docs]   urgency 9

Part 1: fetch, compile, lint, test, docs, package, publish
Part 2: docs, fetch, lint, compile, test, package, publish
Part 3 (drop tags docs and style): fetch, compile, test, package, publish
Part 4: [docs, fetch], [lint, compile], [test], [package], [publish]

Constraints

• Up to 10^4 jobs and 10^5 prerequisite edges. Aim for O((V + E) log V).
• Output must be deterministic for a given input.