7.5 tsort: Background

tsort exists because very early versions of the Unix linker processed an archive file exactly once, and in order. As ld read each object in the archive, it decided whether it was needed in the program based on whether it defined any symbols which were undefined at that point in the link.

This meant that dependencies within the archive had to be handled specially. For example, scanf probably calls read. That means that in a single pass through an archive, it was important for scanf.o to appear before read.o, because otherwise a program which calls scanf but not read might end up with an unexpected unresolved reference to read.

The way to address this problem was to first generate a set of dependencies of one object file on another. This was done by a shell script called lorder. The GNU tools don't provide a version of lorder, as far as I know, but you can still find it in BSD distributions.

Then you ran tsort over the lorder output, and you used the resulting sort to define the order in which you added objects to the archive.

This whole procedure has been obsolete since about 1980, because Unix archives now contain a symbol table (traditionally built by ranlib, now generally built by ar itself), and the Unix linker uses the symbol table to effectively make multiple passes over an archive file.

Anyhow, that's where tsort came from. To solve an old problem with the way the linker handled archive files, which has since been solved in different ways.