tsort: -: 输入包含奇数个标记

Question

coreutils 手册说

tsort 将其输入读取为由空格分隔的字符串对，表示部分排序。输出是对应于给定偏序的全序。例如

tsort <<EOF
a b c
d
e f
b c d e
EOF

将产生输出

a
b
c
d
e
f

“tsort 将其输入读取为字符串对”是什么意思，这对输入有什么要求？在这个例子中，所做的第一行a b c没什么意思本身，而是a和b配对，所以是c和d？

为什么这不起作用？

$ tsort <<EOF
> a b c
> b c d e
> EOF
tsort: -: input contains an odd number of tokens

Answer 1

是的，tsort 成对读取由任何空格（包括换行符）分隔的输入。

所以 tsort 文档中的示例：

tsort <<EOF
a b c
d
e f
b c d e
EOF

定义以下排序对：

• a < b
• c < d
• e < f
• b < c
• d < e

将这些放在一起，您可以得到 a < b < c < d < e < f 的排序，在本例中是全排序。

对源代码的阅读证实， tsort 使用gnulib 中的 readtoken()以及一组由空格、制表符和换行符（换句话说，任何空格）组成的分隔符。

（为了回答您的其他问题，我对该 tsort 示例的最初解释是，一行b c d e创建了三个隐式对，b < c、c < d 和 d < e，但事实并非如此，所有空白都被解释为相同，包括换行符，并且一次读取一对。）

Answer 2

tsort对有向图进行拓扑排序。它将图作为节点对获取。这些构成了图的偏序，并tsort为您提供了一个总体排序的结果（也有可能是该图的一个以上的总排序但是，看到的文档-f，并-h选择在BSD系统上的GNU系统AFAIK（不可用）） .

真实图示例（这些是在shells/bashOpenBSD 系统上构建软件包所需的 OpenBSD 软件包）：

$ make -C /usr/ports/shells/bash build-dir-depends
shells/bash devel/ccache
shells/bash devel/gettext
devel/gettext devel/ccache
devel/gettext archivers/xz
archivers/xz devel/ccache
devel/gettext converters/libiconv
converters/libiconv devel/ccache
devel/gettext converters/libiconv

一对, A B, 在此列表中表示“A连接到B”（按此顺序，因为它是有向图），并且在此处显示的特定情况下，它表示“A依赖于B”（converters/libiconv需要在此之前构建，devel/gettext因为后者依赖于以前的）。

tsort 获取节点对的偏序，并返回与该偏序兼容的总排序中的节点列表：

$ make -C /usr/ports/shells/bash build-dir-depends | tsort -r
devel/ccache
archivers/xz
converters/libiconv
devel/gettext
shells/bash

在这里，我已经指示tsort反转结果顺序（在 GNU 系统上不可能，因为-r它不是 GNU 的一个选项tsort），这给了我系统需要构建包的顺序，同时尊重它们之间的依赖关系（以构建最终shells/bash包结束）。

If tsort gets an input line

a b c d

then this is the same as

a b
c d

and as

a b c
d

That is, it always reads the nodes of the graph in pairs, no matter whether these are separated by spaces or newlines. The issue with your data,

a b c
b c d e

is that it can't be read as a list of pairs as it contains an odd number of nodes.