Pipeline Run Order

The story

Your CI server reads a small pipeline file and has to decide in which order to run the jobs. Some jobs needs: the output of others (the tests need the build, the deploy needs the tests), and the file lists them in whatever order the author felt like. A job may only start after every job it needs has finished.

The platform team wants a quick checker that prints the run order for a pipeline file, or says why there is none.

The file format

A hand-rolled, YAML-like format (do not use a YAML library: your program has to parse these few rules itself):

pipeline:
  build:
    needs: []
    script: make build
  test:
    needs: [build, lint]
  lint:

• Everything after a # is a comment. Blank and comment-only lines are ignored.
• The pipeline: line is only a header.
• A line indented by exactly 2 spaces that ends with : defines a job; the name is the text before the colon.
• Lines indented by 4 or more spaces are properties of the most recent job. The only property you care about is needs:, a list in square brackets ([], [a], [a, b], spaces are free). Every other property (script:, image:, needs-review:, ...) is ignored, whatever its value looks like.
• A job without needs: depends on nothing. Job names are unique.

The task

Read the pipeline from stdin and print the job names, one per line, in this order: repeatedly pick, among the jobs not yet run whose needs have all been run, the one that is defined EARLIEST in the file, until all jobs have run.

Two error cases print a single line and nothing else:

• error: unknown job <name>: a needs: list names a job that is not defined. Report the first one found, going through the jobs in definition order and through each list from left to right. This check comes first.
• error: cycle: no unknown jobs, but at some point nothing can run while jobs remain (including a job that needs itself).

Example

pipeline:
  build:
    needs: []
    script: make build
  test:
    needs: [build, lint]
    script: make test
  lint:
    script: make lint
  deploy:
    needs: [test]
    script: ./deploy.sh

Output:

build
lint
test
deploy

build is the earliest defined job that is ready. test is defined before lint but has to wait for it, so lint runs second; then test and deploy follow.

pipeline:
  build:
    needs: []
    script: make build
  test:
    needs: [build, lint]
    script: make test
  lint:
    script: make lint
  deploy:
    needs: [test]
    script: ./deploy.sh