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 [actualizar], es parte del estándar POSIX .1. [1]
Versión inicial | 1979 |
---|---|
Sistema operativo | Unix , similar a Unix , V , Inferno |
Plataforma | Multiplataforma |
Tipo | Mando |
Historia
Según su página de información [2] , este comando se escribió inicialmente para proporcionar un orden 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 . [3]
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] [ARCHIVO]
Las opciones de FreeBSD pueden ser:
-d activar la depuración-Busco y visualizo el ciclo más largo.-q No muestra mensajes informativos sobre ciclos.
GNU proporciona solo las siguientes opciones:
: ayuda a mostrar el mensaje de ayuda y salir--version muestra información de la versión y sale
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. [4]
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 tal orden 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 | ![]() 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. ):
$ Gato gráfico de llamadas principales parse_options principal tail_file principal tail_forever tail_file pretty_name tail_file write_header tail_file cola tail_forever? Servicios tail_forever pretty_name tail_forever write_header tail_forever dump_remainder tail_lines cola cola 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 ? Servicios pretty_name | $ # nota: 'tac' invierte el orden $ 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 cola ? Servicios parse_options tail_file tail_forever principal |
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 dentro. [5]
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 } construyendo una biblioteca $ { LIB } estática @ $ { 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:
abantes de Cristo | tejidoC | abbc | abbc | aBBC |
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):
Automóvil club británico
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 > ab > bc > ca > EOF UX: tsort: INFORM: ciclo en datos tsort: a tsort: b tsort: c a b c
Ver también
Referencias
- ^ "tsort" . Especificaciones básicas de Open Group, edición 7, edición de 2018 . El grupo abierto.
- ^ https://www.gnu.org/software/coreutils/manual/html_node/tsort-background.html
- ^ http://www.freebsd.org/cgi/man.cgi?query=tsort
- ^ https://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html
- ^ "c ++ - gcc ld: método para determinar el orden de enlace de las bibliotecas estáticas" . Desbordamiento de pila .
Otras lecturas
- Knuth, Donald E. (1997). El arte de la programación informática . 1 (3ª ed.). págs. 261–268. ISBN 0-201-89683-4.
- Kahn, AB (1962). "Clasificación topológica de grandes redes". Comunicaciones de la ACM . 5 (11): 558–562. doi : 10.1145 / 368996.369025 .
enlaces externos
página de manual de tsort en
- FreeBSD ,
- OpenBSD ,
- NetBSD ,
- AIX ,
- Solaris ,
- HP-UX
- dep-trace Ordena las dependencias básicas y despliega las anidadas. (básico: sin presunción gráfica 2D)