stringtranslate.com

tsort

Программа tsort — это утилита командной строки на Unix и Unix-подобных платформах, которая выполняет топологическую сортировку на входе. С 2017 года она является частью стандарта POSIX .1. [1]

История

Согласно информации на странице [2] , эта команда изначально была написана для упорядочивания объектных файлов, что позволяло компоновщику обрабатывать их последовательно (каждый ровно один раз и по порядку). Страница руководства FreeBSD датирует ее появление версией 7 Unix . [3]

Обратите внимание, что следующее описание описывает поведение реализации tsort во FreeBSD и упоминает функции GNU там, где они могут существовать. Другие реализации или версии могут отличаться.

Синтаксис

tsort [-dlq] [ФАЙЛ]

Возможны следующие варианты FreeBSD:

-d включить отладку-l искать и отображать самый длинный цикл.-q Не отображать информационные сообщения о циклах.

GNU предоставляет только следующие возможности:

--help отобразить справочное сообщение и выйти--version отобразить информацию о версии и выйти

POSIX не предписывает никаких опций.

Поведение

tsort считывает свой ввод (из указанного ФАЙЛА или стандартного ввода , если входной файл не указан или для ФАЙЛА '-') как пары строк, разделенных пробелами, что указывает на частичное упорядочение. Вывод — это полное упорядочение, которое соответствует указанному частичному упорядочению. [4]

Другими словами: для направленного ациклического графа (используемого в качестве графа зависимостей ) tsort создает список вершин таким образом, что для всех ребер «a->b» «a» предшествует «b» в списке.

Примеры

tsort перечисляет вершины направленного ациклического графа в таком порядке, чтобы соблюдались все отношения порядка/направления:

График вызовов

tsort может помочь переупорядочить функции в исходном файле так, чтобы как можно большее их количество было определено до их использования (следующее следует интерпретировать как: main()вызовы parse_options(), tail_file()и tail_forever(); tail_file()вызовы pretty_name(), и т. д. Результатом будет то, что dump_remainder()должно быть определено первым, start_lines()вторым и т. д.):

Библиотека

Традиционный ld (компоновщик Unix) требует, чтобы его входные данные библиотеки были отсортированы в топологическом порядке, поскольку он обрабатывает файлы за один проход. Это применимо как к статическим библиотекам ( *.a), так и к динамическим библиотекам ( *.so), а в случае статических библиотек предпочтительно для отдельных объектных файлов, содержащихся внутри. [5]

BSD UNIX использует tsort как общую часть типичных вызовов команд ar и ranlib (из /usr/share/mk/bsd.lib.mk):

lib${LIB}.a :  ${ OBJS } ${ STATICOBJS }  @ ${ ECHO }  создание  статической библиотеки ${ LIB } @ ${ AR } cq ${ .TARGET } ` lorder ${ OBJS } ${ STATICOBJS } | tsort -q ` ${ ARADD } ${ RANLIB } ${ .TARGET }

Здесь lorder(«порядок библиотеки») используется для генерации списка межфайловых зависимостей путем проверки таблицы символов.

Заметки об использовании

Обратите внимание на взаимозаменяемость разделителей пробелов, поэтому следующие входные данные эквивалентны:

Пары одинаковых элементов указывают на наличие вершины, но не на порядок (поэтому следующее представляет одну вершину без ребер):

аа

Строго говоря, топологического упорядочения графа, содержащего один или несколько циклов , не существует . Однако tsort выводит предупреждение, а GNU tsort выводит обнаруженные циклы в стандартный поток ошибок (строки, начинающиеся с 'tsort:'):

$ tsort  <<EOF > ab > bc > ca > EOF UX: tsort: INFORM: цикл в данных tsort: a tsort: b tsort: c a b c

Смотрите также

Ссылки

  1. ^ "tsort". Спецификации Open Group Base, выпуск 7, издание 2018 г. The Open Group.
  2. ^ "Фон Tsort (GNU Coreutils 9.0)".
  3. ^ "Цорт".
  4. ^ "Вызов Tsort (GNU Coreutils 9.0)".
  5. ^ "c++ - gcc ld: метод определения порядка компоновки статических библиотек". Stack Overflow .

Дальнейшее чтение

Внешние ссылки

страница руководства tsort на