tsort

El programa tsort es una utilidad de línea de comandos en plataformas Unix y similares a Unix que realiza una ordenación topológica sobre su entrada. Forma parte del estándar POSIX .1 ^{[ 1 ]} y lo ha sido desde la Especificación Única de UNIX, Versión 2 ^[²^] .

Historia

Según su página de información ^{[ 3 ]} , este comando se escribió inicialmente para proporcionar un ordenamiento de archivos objeto que permitiera al enlazador 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 . ^{[ 4 ]}

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

Sintaxis

tsort [-dlq] [ARCHIVO]

Las opciones de FreeBSD pueden ser:

-d activar la depuración -l busca y muestra el ciclo más largo. -q No mostrar mensajes informativos sobre los ciclos.

GNU solo ofrece las siguientes opciones:

--help muestra el mensaje de ayuda y sale. --version muestra la información de la versión y sale.

POSIX no prescribe ninguna opción.

Comportamiento

tsort lee su entrada (del archivo especificado, o de la entrada estándar si no se proporciona ningún archivo de entrada o si el archivo es '-') como pares de cadenas separadas por espacios en blanco, que indican un orden parcial. La salida es un orden total que corresponde al orden parcial proporcionado. ^{[ 5 ]}

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

Ejemplos

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

Gráfico de llamadas

tsort puede ayudar a reorganizar las funciones en un archivo fuente para que se definan tantas como sea posible antes de que se utilicen (Interprete lo siguiente como: main()llama a parse_options(), tail_file()y tail_forever(); tail_file()llama a pretty_name(), y así sucesivamente. El resultado es que dump_remainder()debe definirse primero, start_lines()segundo, etc.):

Biblioteca

El enlazador tradicional de Unix ( ld ) requiere que sus entradas de biblioteca estén ordenadas topológicamente, ya que procesa los archivos en una sola pasada. Esto se aplica tanto a las bibliotecas estáticas ( *.a) como a las dinámicas ( *.so), y en el caso de las bibliotecas estáticas, preferiblemente a los archivos objeto individuales que contienen. ^{[ 6 ]}

BSD UNIX utiliza tsort como parte común de las invocaciones típicas de los comandos ar y ranlib (desde /usr/share/mk/bsd.lib.mk):

lib${LIB}.a : ${ OBJS } ${ STATICOBJS } @ ${ ECHO } construyendo biblioteca estática ${ LIB } @ ${ AR } cq ${ .TARGET } ` lorder ${ OBJS } ${ STATICOBJS } | tsort -q ` ${ ARADD } ${ RANLIB } ${ .TARGET }

Aquí lorder("orden de la 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:

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

Automóvil club británico

Estrictamente hablando, no existe un orden topológico de un grafo que contenga 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 > ab > bc > ca > EOF UX: tsort: INFORM: ciclo en datos tsort: a tsort: b tsort: c a b c

Véase también

POSIX

Desde 1997 hasta 2024, la versión POSIX del programa tsort no aceptaba argumentos, salvo el nombre de un archivo opcional que contenía los datos de entrada (si no se especificaba ningún archivo, leía desde la entrada estándar). Con la versión de 2024, POSIX especifica el argumento opcional -w, que informa sobre el número de bucles encontrados en el estado de salida del comando.

Referencias

↑ "tsort" . Especificaciones básicas de The Open Group, edición 8, 2024. The Open Group.
↑ "tsort" . La especificación única de UNIX®, versión 2. The Open Group.
↑ "Fondo de Tsort (GNU Coreutils 9.0)" .
↑ "Tsort" .
↑ "Invocación de Tsort (GNU Coreutils 9.0)" .
↑ "c++ - gcc ld: método para determinar el orden de enlace de las bibliotecas estáticas" . Stack Overflow .

Lecturas adicionales

Knuth, Donald E. (1997). El arte de la programación informática . Vol. 1 (3.ª ed.). págs. 261–268 . ISBN 0-201-89683-4.
Kahn, AB (1962). "Clasificación topológica de grandes redes" . Communications of the ACM . 5 (11): 558– 562. doi : 10.1145/368996.369025 . S2CID 16728233 .

Enlaces externos

página del manual de tsort en

FreeBSD ,
OpenBSD ,
NetBSD archivado el 3 de junio de 2016 en Wayback Machine ,
AIX ,
Solaris ,
HP-UX
dep-trace Ordena las dependencias básicas y despliega las anidadas. (básico: sin representación gráfica en 2D)

[1] "tsort" . Especificaciones básicas de The Open Group, edición 8, 2024. The Open Group.

[2] "tsort" . La especificación única de UNIX®, versión 2. The Open Group.

[3] "Fondo de Tsort (GNU Coreutils 9.0)" .

[4] "Tsort" .

[5] "Invocación de Tsort (GNU Coreutils 9.0)" .

[6] "c++ - gcc ld: método para determinar el orden de enlace de las bibliotecas estáticas" . Stack Overflow .

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]