ライブラリ内の循環依存関係を持つクラスの検出 の中身

Other

ライブラリ内の循環依存関係を持つクラスの検出 - しげるメモより。

正直、O(n^4)はあり得ないのでもっとまともな文献あったら紹介してください。

とりあえず、下のような依存関係を持つクラスライブラリについて考えてみる。

Ａ
↓
Ｂ←↑
↓　Ｅ→Ｆ
Ｃ→↑
↓
Ｄ

なお、A→Bは「AがBを利用する (AはBに依存する)」ということです。

上のグラフを升目上に表記してみる。このときのルールは、グラフに X→Y が含まれるばあいに、(X, Y) = ○

そうすると、下のようになる。

　　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　Ｆ
　┌─┬─┬─┬─┬─┬─┐
Ａ│　│●│　│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｂ│　│　│●│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｃ│　│　│　│●│●│　│
　├─┼─┼─┼─┼─┼─┤
Ｄ│　│　│　│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｅ│　│●│　│　│　│●│
　├─┼─┼─┼─┼─┼─┤
Ｆ│　│　│　│　│　│　│
　└─┴─┴─┴─┴─┴─┘

これは直接の依存関係の表で、グラフとしてはA → Dをたどる経路も本来は存在するものの、上記の表には出現しない。

これを間接の依存関係の表に変換するには、(X, Y) のとき、X の行は Y の行に出現するすべての依存関係を背負ってあげればいい。つまり、(X, Y) かつ (Y, Z) のとき、間接依存関係に (X, Z) が含まれるようにする (X → Y → Z)という依存。

プログラムとして書く場合、if (D[i, j]) D[i, *] = D[i, *] | D[j, *] といった感じ。

　　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　Ｆ
　┌─┬─┬─┬─┬─┬─┐
Ａ│　│○│●│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｂ│　│　│○│●│●│　│
　├─┼─┼─┼─┼─┼─┤
Ｃ│　│●│　│○│○│●│
　├─┼─┼─┼─┼─┼─┤
Ｄ│　│　│　│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｅ│　│○│●│●│●│○│
　├─┼─┼─┼─┼─┼─┤
Ｆ│　│　│　│　│　│　│
　└─┴─┴─┴─┴─┴─┘

これだとまだ不十分で、A → D にたどり着けるはずが A → C までしかたどり着けていない。直接依存関係の表に先ほどの処理を施すと、「2つ先の依存関係まで含む表」を作ることができる*1。

なので、同じ処理を何度も繰り返して、変更がなくなるまでやってやればよい。

　　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　Ｆ
　┌─┬─┬─┬─┬─┬─┐
Ａ│　│○│○│●│●│●│
　├─┼─┼─┼─┼─┼─┤
Ｂ│　│●│○│○│○│●│
　├─┼─┼─┼─┼─┼─┤
Ｃ│　│○│●│○│○│○│
　├─┼─┼─┼─┼─┼─┤
Ｄ│　│　│　│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｅ│　│○│○│○│○│○│
　├─┼─┼─┼─┼─┼─┤
Ｆ│　│　│　│　│　│　│
　└─┴─┴─┴─┴─┴─┘

上が変更がなくなるまで間接依存関係を作る処理を施した表。AはA以外のすべての要素にたどり着けるし、Bは自身にたどり着ける ( (B, B) がある )。

ここで、この表をもとに循環依存関係を検出してみる。循環依存関係とは、X → ... → X となるような経路を持つ部分グラフで、要するに自分から自分に戻ってしまうような道のこと。

この計算方法は、次のように考えてみる。

  • 循環依存関係を持つということは、 X → .. → Y → .. → X という経路が存在する
  • X → .. → Y → .. → X という経路を持つということは、X → Y の間接依存関係と、Y → X の間接依存関係を同時に持つ (XからYにたどり着け、かつYからXにもたどり着ける)
  • つまり、間接依存関係の表Iに対して、 I[X, Y] = ○ かつ I[Y, X] = ○ となるようなX, Yの組み合わせが存在すれば、X, Yは循環依存関係を持つ

ということで、間接依存関係の表Iに対して、循環依存関係の表L は L[i, j] = I[i, j] & I[j, i] となる。それを計算したのが↓。

　　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　Ｆ
　┌─┬─┬─┬─┬─┬─┐
Ａ│　│　│　│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｂ│　│●│●│　│●│　│
　├─┼─┼─┼─┼─┼─┤
Ｃ│　│●│●│　│●│　│
　├─┼─┼─┼─┼─┼─┤
Ｄ│　│　│　│　│　│　│
　├─┼─┼─┼─┼─┼─┤
Ｅ│　│●│●│　│●│　│
　├─┼─┼─┼─┼─┼─┤
Ｆ│　│　│　│　│　│　│
　└─┴─┴─┴─┴─┴─┘

上の表のBの行を見ると、{(B, B), (B, C), (B, E)} という組み合わせが見つかる。これは、

  • B は B に循環依存する
  • B は C に循環依存する
  • B は E に循環依存する

というのを同時にあらわしていて、それらをまとめてやると {B, C, E} は循環依存関係を形成していることがわかる。

最初のグラフを見直してみると、B → C → E → B → ... という経路は確かに存在している。

Ａ
↓
Ｂ←↑
↓　Ｅ→Ｆ
Ｃ→↑
↓
Ｄ

というのが10000クラスを超えた状態でやると、間接依存関係の計算で10000^4 (= 10000000000000000)回くらいループを回さなきゃならないというひどいコードでした。
ということで、さえたやり方を募集中です。

*1:厳密には「最低2つ先」