查看“Tsort:拓扑排序”的源代码


tsort对给定的文件执行拓扑排序，如果没有给定输入文件或者输入文件为’-’，则对标准输入进行操作。

<pre>tsort [选项] [文件]</pre>
tsort将其输入作为由空格分隔的字符串对读取，表示部分顺序。输出是与给定部分顺序相对应的总顺序。

<br>

例如

<pre>tsort &lt;&lt;EOF
a b c
d
e f
b c d e
EOF</pre>
<br>

将产生以下输出

<pre>a
b
c
d
e
f</pre>
<br>

考虑一个更实际的例子。你有一个大型函数集，它们都在同一个文件中，但除了一个之外，它们都是静态声明的。目前那个（例如main）是文件中第一个定义的函数，它直接调用的函数紧随其后，然后是它调用的其他函数等。假设你决定利用原型，因此你必须在声明所有这些函数（这意味着从定义中复制大量信息）和重新排列函数之间做出选择，以便尽可能多地在使用时定义它们。自动化后者过程的一种方法是为每个函数获取它直接调用的函数列表。许多程序可以生成这样的列表。它们描述了调用图。考虑以下列表，其中给定的行表示左侧的函数调用右侧的函数。

<pre>main parse_options
main tail_file
main tail_forever
tail_file pretty_name
tail_file write_header
tail_file tail
tail_forever recheck
tail_forever pretty_name
tail_forever write_header
tail_forever dump_remainder
tail tail_lines
tail tail_bytes
tail_lines start_lines
tail_lines dump_remainder
tail_lines file_lines
tail_lines pipe_lines
tail_bytes xlseek
tail_bytes start_bytes
tail_bytes dump_remainder
tail_bytes pipe_bytes
file_lines dump_remainder
recheck pretty_name</pre>
<br>

然后你可以使用tsort生成满足你要求的函数顺序。

<pre>example$ tsort call-graph | tac
dump_remainder
start_lines
file_lines
pipe_lines
xlseek
start_bytes
pipe_bytes
tail_lines
tail_bytes
pretty_name
write_header
tail
recheck
parse_options
tail_file
tail_forever
main</pre>
<br>

tsort检测输入中的任何循环，并将遇到的第一个循环写入标准错误。

<blockquote>注意，对于给定的部分顺序，通常没有唯一的总顺序。在上面的调用图中，函数parse_options可以在列表中的任何地方放置，只要它位于main之前。
</blockquote>
唯一的选项是–help和–version。

<br>

== 背景 ==

tsort存在的原因是早期的Unix链接器会一次性且按顺序处理归档文件。当ld读取归档中的每个对象时，它会根据该对象是否定义了链接时未定义的任何符号来决定是否需要在程序中使用该对象。

<br>

这意味着归档中的依赖关系需要特别处理。例如，scanf可能调用read。这意味着在通过归档进行一次遍历时，scanf.o必须在read.o之前出现，否则调用scanf但不调用read的程序可能会以对read的意外未解析引用结束。

<br>

解决这个问题的方法是首先生成一个对象文件与其他对象文件之间的依赖关系集。这是通过名为lorder的shell脚本完成的。据我所知，GNU工具没有提供lorder的版本，但你仍然可以在BSD发行版中找到它。

<br>

然后，你运行tsort来处理lorder的输出，并使用生成的排序来确定将对象添加到归档中的顺序。

<br>

自大约1980年以来，整个过程已经过时，因为Unix归档现在包含一个符号表（传统上由ranlib构建，现在通常由ar本身构建），并且Unix链接器使用符号表有效地对归档文件进行多次遍历。

<br>

无论如何，这就是tsort的来源。为了解决链接器处理归档文件的方式的老问题，这个问题后来以不同的方式得到了解决。