tsort - tsort

Para conocer la ubicación de Mundodisco, consulte Mundodisco (mundo) § Tsort .

tsort
Versión inicial 1979 ; Hace 42 años  ( 1979 )
Sistema operativo Unix , similar a Unix , V , Inferno
Plataforma Multiplataforma
Tipo Mando

El programa tsort es una utilidad de línea de comandos en Unix y plataformas similares a Unix , que realiza una clasificación topológica en su entrada. A partir de 2017, es parte del estándar POSIX .1.

Historia

Según su página de información , este comando se escribió inicialmente para proporcionar un orden de archivos objeto que permitiera al vinculador procesarlos secuencialmente (cada uno exactamente una vez y en orden). La página del manual de FreeBSD fecha su aparición en la Versión 7 de Unix .

Tenga en cuenta que la siguiente descripción describe el comportamiento de la implementación de FreeBSD de tsort y menciona las características de GNU donde pueden existir. Otras implementaciones o versiones pueden diferir.

Sintaxis 

tsort [-dlq] [FILE]

Las opciones de FreeBSD pueden ser: 

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

GNU proporciona solo las siguientes opciones: 

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

POSIX no prescribe opciones.

Comportamiento

tsort lee su entrada (del ARCHIVO dado, o la entrada estándar si no se proporciona un archivo de entrada o para un ARCHIVO de '-') como pares de cadenas, separadas por espacios en blanco, lo que indica un orden parcial. La salida es un pedido total que corresponde al pedido parcial dado.

En otras palabras: para un grafo acíclico dirigido (usado como grafo de dependencia ), tsort produce una lista de los vértices de modo que para todas las aristas 'a-> b', 'a' viene antes de 'b' en la lista.

Ejemplos de

tsort enumera los vértices de un grafo acíclico dirigido en un orden tal que se respetan todas las relaciones de orden / dirección: 

$ 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
muestra de DAG

Gráfico de llamadas

tsort puede ayudar a reorganizar funciones en un archivo fuente para que se definan tantas como sea posible antes de que se utilicen (interprete lo siguiente como: main() llamadas parse_options() , tail_file() y tail_forever() ; tail_file() llamadas pretty_name() , etc. El resultado es que dump_remainder() debe definirse primero, 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

El ld tradicional (enlazador Unix) requiere que las entradas de su biblioteca se clasifiquen en orden topológico, ya que procesa archivos en una sola pasada. Esto se aplica tanto a las bibliotecas estáticas ( *.a ) como a las bibliotecas dinámicas ( *.so ) y, en el caso de las bibliotecas estáticas, preferiblemente para los archivos de objetos individuales contenidos en ellas.

BSD UNIX usa tsort como una parte común de las invocaciones típicas de comandos ar y ranlib (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}

Aquí lorder ("orden de biblioteca") se utiliza para generar la lista de dependencias entre archivos inspeccionando la tabla de símbolos.

Notas de uso

Observe la intercambiabilidad de los separadores de espacios en blanco, por lo que las siguientes entradas son equivalentes: 

a b
b c

a b b
c

a
b b c

a b b c

a
b
b
c

Los pares de elementos idénticos indican la presencia de un vértice, pero sin orden (por lo que lo siguiente representa un vértice sin aristas): 

a a

Estrictamente hablando, no existe un orden topológico de un gráfico que contiene uno o más ciclos . Sin embargo, tsort imprime una advertencia y GNU tsort imprime los ciclos detectados en el error estándar (líneas que comienzan con '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

Ver también

Referencias

Otras lecturas

enlaces externos

página de manual de tsort en