tsort - tsort

Para a localização do Discworld, consulte Discworld (world) § Tsort .

Tsort
lançamento inicial 1979 ; 42 anos atrás  ( 1979 )
Sistema operacional Unix , tipo Unix , V , Inferno
Plataforma Plataforma cruzada
Modelo Comando

O tsort programa é uma linha de comando utilidade em Unix e Unix-like plataformas, que realiza uma ordenação topológica na sua entrada. A partir de 2017, ele faz parte do padrão POSIX .1.

História

De acordo com sua página de informações , esse comando foi inicialmente escrito para fornecer uma ordem de arquivos de objeto que permitisse ao vinculador processá-los sequencialmente (cada um exatamente uma vez e em ordem). A página de manual do FreeBSD data de seu surgimento para a versão 7 do Unix .

Observe que a seguinte descrição descreve o comportamento da implementação do FreeBSD de tsort e menciona recursos GNU onde eles podem existir. Outras implementações ou versões podem ser diferentes.

Sintaxe 

tsort [-dlq] [FILE]

As opções do FreeBSD podem ser: 

-d         turn on debugging
-l         search for and display the longest cycle.
-q         Do not display informational messages about cycles.

GNU oferece apenas as seguintes opções: 

--help     display help message and exit
--version  display version information and exit

Não há opções prescritas pelo POSIX.

Comportamento

tsort lê sua entrada (do FILE fornecido, ou entrada padrão se nenhum arquivo de entrada for fornecido ou para um FILE de '-') como pares de strings, separados por espaços em branco, indicando uma ordem parcial. A saída é uma ordenação total que corresponde à ordenação parcial fornecida.

Em outras palavras: para um grafo acíclico direcionado (usado como grafo de dependência ), tsort produz uma listagem dos vértices de forma que para todas as arestas 'a-> b', 'a' venha antes de 'b' na listagem.

Exemplos

tsort lista os vértices de um gráfico acíclico direcionado em uma ordem em que todas as relações de ordenação / direção sejam respeitadas: 

$ tsort <<EOF
> 3 8
> 3 10
> 5 11
> 7 8
> 7 11
> 8 9
> 11 2
> 11 9
> 11 10
> EOF
3
5
7
11
8
10
2
9
Image
amostra DAG

Gráfico de chamadas

tsort pode ajudar a reorganizar as funções em um arquivo de origem para que o maior número possível são definidas antes de serem usadas (Interpretar o seguinte como: main() chamadas parse_options() , tail_file() e tail_forever() ; tail_file() chamadas pretty_name() ., e assim por diante O resultado é que dump_remainder() devem ser definidos primeiro, start_lines() segundo, etc. ): 

$ cat call-graph
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

$ # note: 'tac' reverses the order
$ 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

Biblioteca

O ld tradicional (vinculador Unix) requer que as entradas de sua biblioteca sejam classificadas em ordem topológica, uma vez que ele processa arquivos em uma única passagem. Isso se aplica a bibliotecas estáticas ( *.a ) e dinâmicas ( *.so ) e, no caso de bibliotecas estáticas, de preferência para os arquivos de objeto individuais contidos nelas.

BSD UNIX usa tsort como uma parte comum das invocações de comando ar & ranlib típicas (de /usr/share/mk/bsd.lib.mk): 

lib${LIB}.a: ${OBJS} ${STATICOBJS}
    @${ECHO} building static ${LIB} library
    @${AR} cq ${.TARGET} `lorder ${OBJS} ${STATICOBJS} | tsort -q` ${ARADD}
    ${RANLIB} ${.TARGET}

Aqui lorder ("ordem da biblioteca") é usado para gerar a lista de dependências entre arquivos inspecionando a tabela de símbolos.

Notas de uso

Observe a intercambialidade dos separadores de espaço em branco para que as seguintes entradas sejam equivalentes: 

a b
b c

a b b
c

a
b b c

a b b c

a
b
b
c

Pares de itens idênticos indicam a presença de um vértice, mas não ordenação (portanto, o seguinte representa um vértice sem arestas): 

a a

Estritamente falando, não há ordenação topológica de um gráfico que contém um ou mais ciclos . No entanto, tsort imprime um aviso e GNU tsort imprime os ciclos detectados no erro padrão (linhas que começam com 'tsort:'): 

$ tsort <<EOF
> a b
> b c
> c a
> EOF
UX: tsort: INFORM: cycle in data
tsort: a
tsort: b
tsort: c
a
b
c

Veja também

Referências

Leitura adicional

links externos

página de manual do tsort em