Re: let's beef up the tsort info page

[Ian Lance Taylor]

address@hidden (Kenny McCormack) writes:

> First of all, I'd never heard of tsort before seeing this thread.  Having
> read the thread and checking the man page on my system, it looks kinda
> interesting, although I'd be curious to know where it came from (and why!).

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's 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 for 20 years or so, 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.

Ian