7.6 tsort: トポロジカル・ソート

tsort は、指定された file に対してトポロジカル・ソートを行う。 入力ファイルが指定されていない場合や、file として ‘-’ が指定されている場合は、標準入力を対象にする。 より詳しい説明や、このコマンドが作成された経緯については、次節「tsort: 誕生の背景」を御覧になっていただきたい。 tsort: 誕生の背景

書式:

tsort [option] [file]

tsort は入力を、空白で区切られた 2 個一組の文字列として読み込む。 そうした文字列の各組は、部分的な順序を示している。 出力は、与えられた部分的な順序に対応する全体としての順序である。

例を挙げよう。

tsort <<EOF
a b c
d
e f
b c d e
EOF

(訳注: 上の例は、"a b/c d/e f/b c/d e" という組を与えている。)

出力は、こうなる。

a
b
c
d
e
f

もっと現実的な例を考えてみよう。たくさんの関数をすべて一つのファイルに書いているとしよう。 しかも、一つを除いて、他のすべての関数を static として宣言している。 現在のところ、その例外 (main ということにする) が、ファイル中で定義されている最初の関数であり、それが直接呼び出す関数群がそれに続き、 さらにその後に、その関数群が呼び出す関数が続く … という形になっている。さて、ここで、プロトタイプを利用することにしたとしよう。 そうなると、呼び出される関数のすべてを宣言するか (そのためには、定義の部分から情報をどっさりコピーしなければならない）、 あるいは、できるだけ多くの関数が、使用される前に定義されているように、 関数群を並べ替えるか、どちらかを選ばなければならない。 後者の作業を自動化する方法の一つが、各関数についてそれが直接呼び出す関数のリストを作成することである。 そうしたリストを生成するプログラムはたくさんある。 いわゆるコール・グラフを作成するプログラムだ。 以下のリストをご覧になっていただきたい。 各行は、左側の関数が右側の関数を直接呼び出していることを示している。

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

ここで tsort を使用すると、 こうした関数について、上記の後者の要求を満たすような順番を作成することができる。

example$ 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

tsort は、入力にループがあれば検出し、 出会った最初のループを標準エラーに書き出す。

一般に、ある部分的な順序に対して、唯一の全体的な順序というものは存在しないことに、 留意していただきたい。上記のコール・グラフの場合で言えば、 関数 parse_options は、main の前でありさえすれば、 リストのどこにでも来ることができる。

オプションは、‘--help’ と ‘--version’ だけである。 See section 共通オプション.

終了ステータス 0 は成功を示し、0 以外の値は失敗を示す。

This document was generated on June 7, 2022 using texi2html 1.82.