ソート

ソート
初回リリース1979年; 46年前 （1979年）
オペレーティング·システムUnix、Unixライク、V、インフェルノ
プラットフォームクロスプラットフォーム
タイプ指示

tsortプログラムは、UnixおよびUnix系プラットフォーム上のコマンドラインユーティリティであり、入力に対してトポロジカルソートを実行します。POSIX .1標準[1]の一部であり、Single UNIX仕様バージョン2 [2]以降もその一部です。

歴史

このコマンドのinfoページ[3]によると、このコマンドは当初、オブジェクトファイルの順序付けを行い、リンカーがそれらを順番に（各ファイルを1回ずつ、順番に）処理できるようにするために作成されました。FreeBSDのマニュアルページによると、このコマンドの登場はバージョン7 Unixで遡ります。[4]

以下の説明は、 FreeBSD版 tsortの動作について記述しており、GNU の機能については、存在する場合には言及しています。他の実装やバージョンでは動作が異なる場合があります。

構文

tsort [-dlq] [ファイル]

FreeBSD オプションは次のとおりです。

-d デバッグをオンにする-l は最長サイクルを検索して表示します。-q サイクルに関する情報メッセージを表示しません。

GNU は次のオプションのみを提供します。

--help ヘルプメッセージを表示して終了する--version バージョン情報を表示して終了する

POSIX で規定されたオプションはありません。

行動

tsortは、入力（指定されたFILE、または入力ファイルが指定されていない場合、あるいはFILEが'-'の場合は標準入力）を、空白で区切られた文字列のペアとして読み込みます。これは部分順序付けを示します。出力は、指定された部分順序付けに対応する全順序付けです。[5]

言い換えると、有向非巡回グラフ(依存グラフとして使用) の場合、tsort は、すべてのエッジ 'a->b' について、リスト内で 'a' が 'b' の前にくるように頂点のリストを生成します。

例

tsort は、すべての順序/方向関係が尊重される順序で、有向非巡回グラフの頂点をリストします。

$ 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
サンプルDAG

コールグラフ

tsort は、ソース ファイル内の関数を並べ替えて、できるだけ多くの関数が使用される前に定義されるようにするのに役立ちます (以下を、 、および 、 などを呼び出しとして解釈しますmain()。parse_options()結果tail_file()としてtail_forever()、tail_file()はpretty_name()最初dump_remainder()、start_lines()2 番目などと定義される必要があります)。

$ 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
$ # 注記: 'tac' は順序を逆にします$ 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

図書館

従来のld（Unixリンカー）は、ファイルを1回のパスで処理するため、ライブラリ入力をトポロジカル順序でソートする必要があります。これは静的ライブラリ（*.a）と動的ライブラリ（*.so）の両方に適用され、静的ライブラリの場合は、それに含まれる個々のオブジェクトファイルにも適用されます。[6]

BSD UNIX は、典型的なarおよびranlibコマンド呼び出しの共通部分として tsort を使用します(/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(「ライブラリ順序」) は、シンボル テーブルを検査してファイル間の依存関係リストを生成するために使用されます。

使用上の注意

空白区切り文字の互換性に注意して、次の入力は同等になります。

腹筋紀元前
アブc
1つのBBC
ABBC
1つのbbc

同一の項目のペアは頂点の存在を示しますが、順序は示しません (したがって、次はエッジのない 1 つの頂点を表します)。

ああ

厳密に言えば、1つ以上のサイクルを含むグラフには位相的な順序付けは存在しません。しかし、tsortは警告を出力し、GNU tsortは検出されたサイクルを標準エラー出力（「tsort:」で始まる行）に出力します。

$ tsort  <<EOF > ab > bc > ca > EOF UX: tsort: INFORM: データの循環tsort: a tsort: b tsort: c a b c

参照

POSIX

1997年から2024年まで、POSIX版のtsortプログラムは、入力データを含むファイル名（省略可能）以外の引数を受け付けませんでした（ファイルが指定されていない場合は標準入力から読み込みます）。2024年版では、POSIXはオプションの-w引数を指定し、コマンドの終了ステータスで見つかったループ回数を報告します。

参考文献

  1. ^ "tsort". The Open Group 基本仕様 第8版、2024年版。The Open Group。
  2. ^ "tsort". The Single UNIX® 仕様、バージョン2。The Open Group。
  3. ^ 「Tsort の背景 (GNU Coreutils 9.0)」。
  4. ^ 「Tsort」。
  5. ^ 「Tsort の呼び出し (GNU Coreutils 9.0)」。
  6. ^ 「c++ - gcc ld: 静的ライブラリのリンク順序を決定する方法」。Stack Overflow。

さらに読む

tsortのマニュアルページ

  • FreeBSD、
  • OpenBSD、
  • NetBSD、
  • AIX、
  • ソラリス、
  • HP-UX
  • dep-trace 基本的な依存関係を整理し、ネストされた依存関係を展開します。(基本: 2D グラフィカルな前提なし)
「https://en.wikipedia.org/w/index.php?title=Tsort&oldid=1305280952」から取得