tsort: -: a entrada contém um número ímpar de tokens

Question

manual do coreutils diz

tsort reads its input as pairs of strings, separated by blanks, indicating a partial ordering. The output is a total ordering that corresponds to the given partial ordering. For example

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

will produce the output

a
b
c
d
e
f

O que significa "tsort lê sua entrada como pares de strings" e quais requisitos são colocados na entrada? No exemplo, a primeira linha a b c não significa nada em si, mas a e b estão emparelhados, assim como c e d ?

Por que isso não funciona?

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

    

Answer 1

tsort faz uma classificação topológica de um gráfico direcionado. Obtém o gráfico como pares de nós. Estes constituem uma ordenação parcial do gráfico e tsort dá-lhe uma ordenação total como resultado (pode haver mais do que uma ordenação total do gráfico, ver a documentação para as opções -f e -h nos sistemas BSD (não disponível nos sistemas GNU AFAIK)).

Exemplo de um gráfico real (estes são os pacotes do OpenBSD necessários para construir o pacote shells/bash em um sistema 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

Um par, A B , nesta lista significa " A está conectado a B " (nessa ordem, já que é um gráfico direcionado) e, no caso específico mostrado aqui, significa " A depende de B "( converters/libiconv precisa ser construído antes de devel/gettext porque o último depende do primeiro).

tsort aceita a ordenação parcial de pares de nós e retorna uma lista de nós em uma ordem total compatível com essa ordenação parcial:

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

Aqui, instruímos tsort a reverter a ordem resultante (não é possível em sistemas GNU, pois -r não é uma opção para o GNU tsort ), o que me dá a ordem na qual o sistema precisa construir os pacotes e, ao mesmo tempo, honrar as dependências entre eles (terminando com a compilação final do pacote shells/bash ).

Se tsort obtiver uma linha de entrada

a b c d

então isso é o mesmo que

a b
c d

e como

a b c
d

Ou seja, ele sempre lê os nós do gráfico em pares , independentemente de estarem separados por espaços ou novas linhas. O problema com seus dados,

a b c
b c d e

é que não pode ser lido como uma lista de pares, pois contém um número ímpar de nós.

    

Answer 2

Sim, o tsort lê suas entradas em pares separados por qualquer espaço em branco, incluindo novas linhas.

Então, o exemplo da documentação do tsort:

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

Define os seguintes pares de pedidos:

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

E colocando tudo isso junto, você recebe um pedido de < b < c < d < e < f, que neste caso é um pedido total.

Uma leitura do código-fonte confirma que o tsort usa readtoken () do gnulib com um conjunto de delimitadores composto por espaço, separador e nova linha , em outras palavras, qualquer espaço em branco.

(Minha interpretação inicial do exemplo do tsort, para responder a sua outra pergunta , foi que uma linha com b c d e criou três pares implícitos, b < c, c < d e d < e, mas esse não é realmente o caso, todo espaço em branco é interpretado da mesma forma, incluindo novas linhas e um único par é lido por vez.