次: , 前: ptx invocation, 上: Operating on sorted files


7.4 tsort: 位相幾何学的なソート

tsortは,位相幾何学的なソートを,与えられたfile,また は入力ファイルが与えられない場合や`-'のファイルに対しては標準入力 で実行します.詳細とちょっとした歴史はtsort backgroundを参照して ください.概要です.

     tsort [option] [file]

tsortは,その入力を文字列の組で,空白で分離されていて,不完 全な順序で示されているものとして読み込みます.出力は,与えられた不完全 な順序に対応する完全な順序になります.

例えば以下のようにします.

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

これは以下の出力を生成します.

     a
     b
     c
     d
     e
     f

より現実的な例を考えてみましょう.一つのファイルに大きなすべての関数の セットがあり,一つ以外のすべてがスタティックに宣言されていると仮定しま す.現在,それ(いわゆる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 Common options.