ツリー状の依存関係をシェルスクリプトで表現

実現したいこと

入力: 依存関係

a->b
a->c
a->d
c->e
c->f

出力: ディレクトリツリー

a
|-- b
|-- c
|   |-- e
|   `-- f
`-- d

実装

$ f(){ mkdir -p $1/$2; [ -d $2 ] && (mv $2/* $1/$2/; rmdir $2); ln -s $1/$2 $2;}; export -f f

$ g(){ xargs -n2 bash -c 'f $1 $2' --; rm *;}

$ echo a b a c a d c e c f | g; tree a # 単一の木
a
|-- b
|-- c
|   |-- e
|   `-- f
`-- d

$ echo a b a c a d c e c f g h g i | g; tree # 複数の木でも動く
.
|-- a
|   |-- b
|   |-- c
|   |   |-- e
|   |   `-- f
|   `-- d
`-- g
    |-- h
    `-- i

• 制約
  • ノードにはユニークな名前が付いていると仮定。
  • 表現できるのは木のみ。 (親が2個のノードとかは不可)
  • ルートノード1個だけからなる木 (宙ぶらりんの単一ノード) は表現不可。
    • 入力に依存関係を与える使用のため。

解説

• f(): 1つのノードを追加する処理。
• g(): ノードの数だけ f() をループで回す。

f() の解説

1つのノードを追加する。

f( ) の定義

$ f(){
    mkdir -p $1/$2
    [ -d $2 ] && (mv $2/* $1/$2/; rmdir $2) # $2 がディレクトリの場合の例外処理。
    ln -s $1/$2 $2
}
$ export -f f # xargs で使うため。

f() の mkdir と ln が肝である。
mkdir で木にノードを追加し、ln でそのノードへの参照を保存する。
f a c は基本的に mkdir -p a/c; ln -s a/c c; と等価である。

f( ) の実行例

$ f a c         # mkdir -p a/c; ln -s a/c c と等価。

$ tree
.
|-- a           # ノード (ルート)
|   `-- c       # ノード
`-- c -> a/c    # ノードへの参照

$ f c e         # mkdir -p c/e; ln -s c/e e と等価 。

$ tree
.
|-- a           # ノード (ルート)
|   `-- c       # ノード
|       `-- e   # ノード
|-- c -> a/c    # ノードへの参照
`-- e -> c/e    # ノードへの参照

ディレクトリ (ノード) とシンボリックリンク (ノードへの参照) ができることがわかる。
シンボリックリンクは中間ファイルであり、木の中には存在しない。

では f() の例外処理では何をしているのか?

f( ) の例外処理

    [ -d $2 ] && (mv $2/* $1/$2/; rmdir $2) # $2 がディレクトリの場合の例外処理。

先程の例を逆順に実行するとどうなるかを考える。

$ f a c; f c e # これではなく
$ f c e; f a c # これを実行した場合を考える

f( ) の逆順の実行例

$ f c e

$ tree # 問題なし
.
|-- c
|   `-- e
`-- e -> c/e

### 以下、f a c == mkdir -p a/c; ln -s a/c c を分解して実行

$ mkdir -p a/c

$ tree # ここまでは問題ない
.
|-- a
|   `-- c
|-- c
|   `-- e
`-- e -> c/e

$ ln -s a/c c

$ tree # 変な状態になった
.
|-- a
|   `-- c
|-- c
|   |-- c -> a/c # ディレクトリ (木) の中にシンボリックリンクを作ってしまった。
|   `-- e
`-- e -> c/e

上記の問題は、ln -s a/c c をする時点で c/ が既に存在するため起こる。
そのため、c/ が既に存在し、かつディレクトリの場合に、例外処理が必要となる。

if [ -d c ]; then # c が存在しディレクトリの場合 (= この時点で c/ が独立した木である場合)
    mv c/* a/c    # c の子ノードを木 a の中に移動 (a/c は前段の処理で既に作成されている)
    rmdir c       # c (独立していた木) を削除
fi

ln の実行前に上記の例外処理を行えば、c/ が存在しなくなるので、ln で普通にノードへの参照が作成できる。

ln 実行時に c が存在してかつシンボリックであることはありえない。
なぜなら ln を行うのは新しいノードを作成するときであり、ノードの名前はユニークという制約があるからである。(同じ名前のノードが2度作られない)

g() の解説

ノードの数だけ f() をループで回す。
f() を呼び出すインターフェース的なものである。
本質的な話題ではないのでサラッと流す。

g(){
    xargs -n2 bash -c 'f $1 $2' --
    rm * # シンボリックリンクは中間ファイルなので最後に削除
}

xargs の部分でパイプからの入力を2個ずつに分解して f() を呼び出している

$ echo 0 1 2 3 | xargs -n2 echo # ちなみに echo は省略可能
0 1
2 3

$ echo 0 1 2 3 | xargs -n2 bash -c 'echo $1,$2' -- # f() が関数なのでこんな形で呼び出す必要がある
0,1
2,3

$ echo 0 1 2 3 | xargs -n2 bash -c 'f $1 $2' -- # 最終形