执行拓扑排序
命令语法格式
tsort [OPTION] [FILE]
命令描述
tsort对给定文件FILE执行拓扑排序。如果没有指定参数FILE或者参数FILE为’-‘，则从标准输入中读取。
tsort读取它的输入，并将其做为字符串的一部分，由空白分隔，表明部分排序。输出则是对应于给定的部分排序的总排序。
tsort检测输入中的任何环形拓扑，并将遇到的第一个环形拓扑写入标准错误。
命令支持的选项及含义
–help
显示帮助信息并退出。
–version
显示版本信息并退出。
退出状态
退出状态为零表示成功，非零值表示失败。
使用示例
如下示例，对于命令：
a b c
d
e f
b c d e
EOF
产生的输出如下：
b
c
d
e
f
考虑一个更现实的例子。你在一个文件中有大量的函数，除了一个函数外，它们都被声明为静态的。目前，一个（称为main）是文件中定义的第一个函数，它所调用的函数会直接跟在它后面，然后后面再跟着它们所调用的函数。假设你决定利用原型，所以你必须选择 在声明所有这些函数之间（这意味着从定义中复制大量信息）并重新安排函数，以便尽可能地在函数被使用之前进行定义。使后一个过程自动化的一种方法是获得它直接调用的函数的每个函数的列表。许多程序可以生成这样的列表。他们描述了一个调用图。考虑下面的列表，其中给定的行指示左侧的函数直接调用右侧的函数：
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
那么你可以使用tsort来产生满足你需求的那些函数的顺序：
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
请注意，对于给定的部分排序，通常不存在唯一的总排序。在上述调用图的上下文中，只要parse_options位于main的前面，parse_options就可以放在列表中的任何位置。
tsort的由来
tsort的存在是因为Unix链接器的早期版本只处理一次档案文件，并按顺序处理。当ld读取档案中的每个对象时，它会根据是否定义链接中未定义的任何符号来决定程序是否需要它。
这意味着档案中的依赖关系必须专门处理。例如，scanf可能会调用read。这意味着，在一次存档中，scanf.o在read.o之前出现很重要，否则调用scanf但未读取的程序可能最终会导致意外的未解析的读取引用。
解决这个问题的方法是首先在另一个目标文件上生成一组依赖关系。这是通过名为lorder的shell脚本完成的。据我们所知，GNU工具不提供lorder版本，但你仍然可以在BSD发行版中找到它。
然后，你在lorder输出上运行tsort，并使用结果排序来定义将对象添加到存档的顺序。
自1980年以来，整个过程已经过时，因为Unix存档现在包含一个符号表（传统上由ranlib构建，现在通常由ar本身构建），Unix链接器使用符号表有效地对存档文件进行多次传递。
无论如何，这是tsort从何而来。用连接器处理归档文件的方式解决一个老问题，这个问题已经以不同的方式解决了。
相关手册
查看在线手册：http://www.gnu.org/software/coreutils/tsort
查看info手册：info ‘(coreutils) tsort invocation’
参考文献
- man 1 tsort, version GNU coreutils 8.28
- 7.6.1 tsort: Background
更新日志
- 06/26/2018 创建文章