GNU tsort: Dependency Pairs, Partial Orders, and Cycle Failures

GNU tsort turns a list of pairwise ordering constraints into one total sequence that satisfies those constraints, when the constraints are acyclic. It is useful for a small build or deployment manifest when one item must precede another but many items are otherwise independent. It does not choose a project-wide policy for those independent items, and it does not run the resulting commands.

The discussion here follows the GNU Coreutils 9.12 manual and version-pinned implementation, the stable release announced on 2026-09-14. The manual describes input as pairs of strings separated by blanks: each pair states a partial ordering, and the output is a total ordering consistent with it. In the 9.12 source, space, tab, and newline are token delimiters, so newline is not a semantic record boundary. The parser consumes a stream of tokens in pairs; an odd number of tokens is an error. The implementation ignores a self-pair such as compile compile, rather than reporting it as a cycle. If self-dependencies are invalid in your workflow, reject them while generating or validating the graph.

Make the edge direction explicit

For a dependency plan, encode the prerequisite first and the dependent second. This makes the emitted order readable as “do this prerequisite before that item”:

tsort <<'EOF'
fetch-sources configure
install-toolchain compile
configure compile
compile package
package publish
EOF

Here fetch-sources and install-toolchain must precede later work; configure must precede compile; and each step must precede the next. The result can place the two independent initial tasks in either order, but every emitted sequence must preserve each supplied pair. Before relying on a generated list, confirm that the producer uses this same direction. A call graph, prerequisite table, or “A depends on B” representation may naturally encode edges in the reverse direction and need transformation first.

tsort only knows names that occur as tokens in its input. A task that never appears cannot be discovered and emitted from the pair stream. A self-pair such as solo solo is a special case: GNU tsort registers solo as a node but ignores the self-relation, so the isolated name can still appear in output. Keep the authoritative task inventory separately, then reconcile it with the ordered names before execution. Likewise, a successful order does not prove that a prerequisite exists, that a command is safe, or that the dependency graph contains every real requirement.

A total output is not a unique or stable schedule

A partial order usually admits several valid total orders. If two tasks have no path constraining their relative order, tsort may emit either one first. GNU’s manual explicitly notes that a partial ordering generally has no unique total ordering. Do not turn one observed output into an undocumented tie-breaking contract or use it as a reproducibility guarantee across implementations or versions.

If repeatable tie-breaking is required, define it as part of the graph-generation or scheduling policy. For example, use a dependency-aware scheduler that chooses the lexically smallest currently eligible task. Sorting the final tsort output can break dependencies; sorting input pairs does not establish an output tie-break contract. If parallel execution is desired, a single linear order is also the wrong abstraction: derive ready sets from the graph and run only tasks whose prerequisites have completed.

Treat cycles as invalid input, not as an order

When constraints form a cycle, no total ordering can satisfy them. The GNU manual says tsort writes the first cycle it encounters to standard error. In the version-pinned 9.12 implementation, the sorter breaks a relation after detecting a cycle and continues; if output later gets stuck on another cycle, it can emit another cycle diagnostic. It does not promise to enumerate every cycle in the input. The exit status is nonzero on failure, and stdout can contain an order that does not satisfy every original constraint. Preserve both streams while diagnosing the graph and discard stdout on any nonzero exit.

Do not pipe directly into a mutating deployment or build step and consume output before checking tsort’s exit status. Stage the generated sequence, check the producer’s status, and inspect the diagnostic before consuming the file:

if tsort dependencies.txt > ordered-tasks.tmp; then
    validate_and_run_plan ordered-tasks.tmp
else
    printf '%s\n' 'dependency graph is invalid; see tsort diagnostics' >&2
    exit 1
fi

The example assumes ordered-tasks.tmp is in a private, job-specific staging directory; it is not the live plan. validate_and_run_plan is application code, not a tsort feature. In production, validate that the ordered names exactly match the approved task inventory and that each task’s inputs are available before starting side effects. A valid topological sequence solves only the ordering constraints represented in the input.

GNU tsort reads a named file, standard input when no file is supplied, or standard input when the file operand is -. In the documented GNU interface, the options are --help, --version, and -w; -w is accepted and ignored for POSIX conformance. Check the installed implementation and version before depending on GNU-specific diagnostics or command-line behavior. The tool is a compact graph-ordering primitive, not a workflow engine, parallel scheduler, missing-dependency validator, or transaction manager.

The token format also sets a naming constraint: an item label containing a space, tab, or newline is parsed as multiple tokens and can shift every subsequent pair. If human-readable task names contain those delimiters or arbitrary external identifiers, map them to validated single-token IDs and keep the mapping beside the plan. The pair file is not a shell program: keep executable arguments in a separate manifest, resolve each emitted ID through that manifest, and do not eval generated text. Before execution, compare the set of emitted IDs with the approved inventory, verify each task’s prerequisites are represented, and retain the original pair file with the diagnostic. This catches malformed graph generation separately from an actual cycle.

The GNU 9.12 implementation writes one parsed node per output line; that is a convenient representation for opaque IDs, not an escaping format for arbitrary names. A runner should resolve each ID to a prevalidated argument vector rather than reconstructing a command string. It must also apply runtime failure policy: tsort will still list a dependent task after an earlier prerequisite command fails, because it knows ordering constraints but does not observe task completion.

Related:

Sources:

Make the edge direction explicit

A total output is not a unique or stable schedule

Treat cycles as invalid input, not as an order

Comments