Order Build Steps from Dependencies with tsort

Getting a five-step build order right by hand is easy to mess up, but tsort turns dependency pairs into a safe run order in one line. Feed it pairs of names, first-must-precede-second, and it prints a linear order or tells you the input contains a loop. It never runs anything itself.

This guide uses GNU coreutils 9.4, installed here as package version 9.4-3ubuntu6.3. The local tsort(1) page documents the GNU interface as tsort [OPTION] [FILE]. Allow about five minutes for the worked example.

1. Write the dependency pairs

One whitespace-separated pair per relationship, first word before second word. Here, compilation must precede packaging, and packaging must precede publishing. Compilation also has to precede testing.

compile package
compile test
package publish
test publish

Save that as a file if it comes from a larger workflow:

cat > /tmp/release-dependencies.txt <<'EOF'
compile package
compile test
package publish
test publish
EOF

2. Generate the order

Pass the file as the optional operand. The result is one name per line:

tsort /tmp/release-dependencies.txt
compile
package
test
publish

Tip: more than one valid answer can exist. Here, test and package are both allowed straight after compile, so their relative order is not a promise. If a later step needs a stable tie-break, add a real dependency or record the exact output as part of your workflow rather than relying on one run's arbitrary choice.

With no file operand, tsort reads standard input, which suits a generated list:

printf '%s\n' \
  'compile package' \
  'compile test' \
  'package publish' \
  'test publish' | tsort

Use - explicitly when a script's file name comes from a variable and you want standard input to be unambiguous:

tsort - < /tmp/release-dependencies.txt

3. Verify before acting on the result

tsort only calculates an order, it does not check whether each name is safe to run. Capture the output first, without executing it:

order=$(tsort /tmp/release-dependencies.txt) || {
    printf '%s\n' 'Dependency ordering failed' >&2
    exit 1
}
printf '%s\n' "$order"

For a known list, check the names against an allow-list before dispatching work.

Warning: never write tsort "$file" | sh. That turns data into shell code, and a name containing shell metacharacters could change what runs. Ordering needs no elevated privileges; keep any later privileged step separate and review its exact command before using sudo.

4. Handle a cycle in the input

A topological order cannot satisfy a loop. These pairs say a must precede b and b must precede a:

a b
b a

Run the check as a command whose exit status you actually test:

if ! tsort /tmp/cyclic-dependencies.txt > /tmp/order.txt 2> /tmp/order.err; then
    sed -n '1,20p' /tmp/order.err
    exit 1
fi

GNU coreutils 9.4 exits with status 1 for this input and names the members of the loop it found. It may still print part of an order, so never trust standard output after a non-zero status.

Recovery: fix the relationship in the source data (restore the removed or corrected pair) and rerun. tsort itself changed nothing, the cyclic file is still sitting there for you to correct.

Input traps worth checking

Keep standard output and standard error separate for machine-readable troubleshooting: ordered names belong on standard output, cycle diagnostics belong on standard error. That stops a warning being mistaken for another item in a pipeline.

Useful command checks

Confirm which implementation and version a script is actually using:

command -v tsort
tsort --version

The GNU command supports --help and --version, and needs no configuration file, daemon or working directory. If another implementation sits earlier in PATH, its output and diagnostics may differ, so use the path reported by command -v when reproducibility matters.

Done means