tsort

According to its info{{Cite web|url=https://www.gnu.org/software/coreutils/manual/html_node/tsort-background.html|title = Tsort background (GNU Coreutils 9.0)}} page, this command was initially written for providing an ordering of object files that allowed the linker to process them sequentially (each one exactly once, and in order). The FreeBSD manual page dates its appearance to Version 7 Unix.{{Cite web|url=http://www.freebsd.org/cgi/man.cgi?query=tsort|title = Tsort}}

Note that the following description is describing the behavior of the FreeBSD implementation of tsort and mentions GNU features where they may exist. Other implementations or versions may differ.

tsort [-dlq] [FILE]

FreeBSD options can be:

-d turn on debugging

-l search for and display the longest cycle.

-q Do not display informational messages about cycles.

GNU provides the following options only:

--help display help message and exit

--version display version information and exit

There are no options prescribed by POSIX.

tsort reads its input (from the given FILE, or standard input if no input file is given or for a FILE of '-') as pairs of strings, separated by blanks, indicating a partial ordering. The output is a total ordering that corresponds to the given partial ordering.{{Cite web|url=https://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html|title = Tsort invocation (GNU Coreutils 9.0)}}

In other words: for a directed acyclic graph (used as a dependency graph), tsort produces a listing of the

vertices so that for all edges 'a->b', 'a' comes before 'b' in the listing.

tsort lists the vertices of a directed acyclic graph in such an order that all ordering/direction relations are respected:

tsort can help rearranging functions in a source file so that as many as possible are defined before they are used (Interpret the following as: {{code|main()}} calls {{code|parse_options()}}, {{code|tail_file()}} and {{code|tail_forever()}}; {{code|tail_file()}} calls {{code|pretty_name()}}, and so on. The result is that {{code|dump_remainder()}} should be defined first, {{code|start_lines()}} second, etc.):

The traditional ld (Unix linker) requires that its library inputs be sorted in topological order, since it processes files in a single pass. This applies both to static libraries ({{code|*.a}}) and dynamic libraries ({{code|*.so}}), and in the case of static libraries preferably for the individual object files contained within.{{cite web |title=c++ - gcc ld: method to determine link order of static libraries |url=https://stackoverflow.com/questions/34164594/gcc-ld-method-to-determine-link-order-of-static-libraries/63530973 |website=Stack Overflow}}

BSD UNIX uses tsort as a common part of the typical ar & ranlib command invocations (from /usr/share/mk/bsd.lib.mk):

lib${LIB}.a: ${OBJS} ${STATICOBJS}

@${ECHO} building static ${LIB} library

@${AR} cq ${.TARGET} `lorder ${OBJS} ${STATICOBJS} | tsort -q` ${ARADD}

${RANLIB} ${.TARGET}

Here {{code|lorder}} ("library order") is used to generate the inter-file dependency list by inspecting the symbol table.

Notice the interchangeability of white space separators so the following inputs are equivalent:

Pairs of identical items indicate presence of a vertex, but not ordering (so the following represents one vertex without edges):

a a

Strictly speaking there is no topological ordering of a graph that contains one or more cycles. However tsort prints a warning and GNU tsort prints the detected cycles to standard error (lines beginning with 'tsort:'):

$ tsort <

> a b

> b c

> c a

> EOF

UX: tsort: INFORM: cycle in data

tsort: a

tsort: b

tsort: c

a

b

c

{{Portal|Free and open-source software}}

• Sort (Unix)
• Make (software)
• Topological sorting
• List of Unix commands
• Call graph

From 1997 until 2024, the POSIX version of the tsort program accepted no arguments other than an optional file name containing the input data (it reads from standard input if no file is specified). With the 2024 version, POSIX specifies an optional -w argument that reports on the number of loops found in the exit status of the command.

{{Reflist}}

• {{Cite book |last=Knuth |first=Donald E. |authorlink=Donald E. Knuth |title=The Art of Computer Programming |edition=3rd |volume=1 |pages=261–268 |year=1997 |isbn=0-201-89683-4}}
• {{Cite journal |last=Kahn |first=A.B. |title=Topological sorting of large networks |journal=Communications of the ACM |volume=5 |number=11 |year=1962 |pages=558–562 |doi=10.1145/368996.369025|s2cid=16728233 |doi-access=free }}

manual page of tsort on

• [http://www.freebsd.org/cgi/man.cgi?query=tsort FreeBSD],
• [http://man.openbsd.org/tsort.1 OpenBSD],
• [http://netbsd.gw.com/cgi-bin/man-cgi?tsort NetBSD],
• [http://publib.boulder.ibm.com/infocenter/pseries/v5r3/topic/com.ibm.aix.cmds/doc/aixcmds5/tsort.htm AIX],
• [http://download.oracle.com/docs/cd/E19963-01/html/821-1461/tsort-1.html Solaris],
• [http://h20000.www2.hp.com/bc/docs/support/SupportManual/c02280845/c02280845.pdf HP-UX]
• [http://sourceforge.net/projects/dep-trace/ dep-trace] Orders basic dependencies and unfolds nested ones. (basic: without 2D graphical presumption)

{{Unix commands}}

{{Core Utilities commands}}

Category:Unix SUS2008 utilities

Category:Inferno (operating system) commands