Linux Basics: Order Prerequisites with GNU tsort

A small build or migration checklist can be expressed as pairs: one task must precede another. GNU tsort turns those relationships into a total order. A cycle means no valid order exists, even if the command has already written some output.

Prepare a scratch directory

Tested on Linux with GNU coreutils 9.7, GNU findutils 4.10.0, and GNU Bash 5.2.37. You need Bash, a text editor, and the utilities used below. The script creates its own temporary fixture directory and removes only that directory on exit.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_dir="$PWD"
work_dir="$(mktemp -d)" || exit 1
cd -- "$work_dir" || exit 1

Run the example

Save this as demonstrate-gnu-tsort-dependencies.sh:

#!/usr/bin/env bash
set -euo pipefail
export LC_ALL=C
fixture_dir="$(mktemp -d)"
trap 'rm -rf -- "$fixture_dir"' EXIT
cd -- "$fixture_dir"
printf '%s\n' 'fetch compile' 'compile test' 'test package' > dependencies.txt
printf 'Prerequisite order:\n'
tsort dependencies.txt > order.txt
cat order.txt
test "$(head -n 1 order.txt)" = fetch
test "$(tail -n 1 order.txt)" = package
printf '%s\n' 'fetch compile' 'compile fetch' > cycle.txt
if tsort cycle.txt > rejected-order.txt 2> cycle-error.txt; then
    printf 'Unexpected success for a cycle\n' >&2
    exit 1
else
    status=$?
    printf 'Cycle rejected: exit %s\n' "$status"
    test "$status" -ne 0
fi

Run it:

bash demonstrate-gnu-tsort-dependencies.sh

Observed output:

Prerequisite order:
fetch
compile
test
package
Cycle rejected: exit 1

Read the result

Each pair puts the left task before the right task. The first fixture forms a chain, so its order is unambiguous. The second fixture requires both tasks to precede each other. Its nonzero status is expected and handled by the if statement rather than bypassed. The diagnostic is captured in cycle-error.txt, while any unusable partial ordering stays in rejected-order.txt.

Apply it carefully

Treat successful completion as a prerequisite for consuming the output; do not pipe an unchecked order directly into a task runner. When independent tasks exist, several valid orders may satisfy the same dependencies. Do not rely on an unspecified tie order. Input consists of whitespace-separated tokens in pairs, not a CSV format, so task names containing spaces need a separate identifier scheme. This command computes an order; it does not run tasks or schedule parallel jobs.

The GNU reference documents these options and their behavior.

Clean up

Remove the saved script, return to the starting directory, and remove the empty practice directory:

rm -- demonstrate-gnu-tsort-dependencies.sh
cd -- "$start_dir" || exit 1
rmdir -- "$work_dir"
unset start_dir work_dir

If the directory is not empty, inspect what remains rather than deleting unknown files.

Acknowledgements

This post was created with assistance from AI.