summaryrefslogtreecommitdiff
path: root/doc
diff options
context:
space:
mode:
authorJim Meyering <jim@meyering.net>2002-02-17 20:26:43 +0000
committerJim Meyering <jim@meyering.net>2002-02-17 20:26:43 +0000
commit59ad795300c1e103d00c26fa0e3f3d9f679f5c55 (patch)
treeac68d0e4ebbc4b2a5aae6eeeed8065c56c90c0ec /doc
parent3b118bfa86c5d04b424f11d0602bb17e9d01e2b8 (diff)
downloadcoreutils-59ad795300c1e103d00c26fa0e3f3d9f679f5c55.tar.xz
(tsort background): New section.
From Ian Lance Taylor.
Diffstat (limited to 'doc')
-rw-r--r--doc/coreutils.texi38
1 files changed, 37 insertions, 1 deletions
diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index 67bce4a13..99bd03230 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -2737,6 +2737,7 @@ These commands work with (or produce) sorted files.
* comm invocation:: Compare two sorted files line by line.
* ptx invocation:: Produce a permuted index of file contents.
* tsort invocation:: Topological sort.
+* tsort background:: Where tsort came from.
@end menu
@@ -3368,7 +3369,8 @@ If there is an error it exits with nonzero status.
@code{tsort} performs a topological sort on the given @var{file}, or
standard input if no input file is given or for a @var{file} of
-@samp{-}. Synopsis:
+@samp{-}. For more details and some history, see @ref{tsort background}.
+Synopsis:
@example
tsort [@var{option}] [@var{file}]
@@ -3410,6 +3412,40 @@ total ordering.
The only options are @option{--help} and @option{--version}. @xref{Common
options}.
+@node tsort background
+@section @code{tsort}: Background
+
+@code{tsort} exists because very early versions of the Unix linker processed
+an archive file exactly once, and in order. As @code{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, @code{scanf} probably calls @code{read}. That means
+that in a single pass through an archive, it was important for @code{scanf.o}
+to appear before read.o, because otherwise a program which calls
+@code{scanf} but not @code{read} might end up with an unexpected unresolved
+reference to @code{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 @code{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 @code{tsort} over the @code{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
+@code{ranlib}, now generally built by @code{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.
@node ptx invocation
@section @code{ptx}: Produce permuted indexes