algorithm - 循環依存を解決するアルゴリズム?

Question

依存関係を循環的にロードできるモジュールシステムを作成したいと思います。その理由は、Ruby on Rails のように、モデルクラス間の関係で循環依存関係があらゆる場所で発生するためです。

# app/models/x.rb
class X < ActiveRecord::Base
  has_many :y
end

# app/models/y.rb
class Y < ActiveRecord::Base
  belongs_to :x
end

これが Ruby on Rails モデルで一般的に機能する方法は、少なくとも、最初に依存関係がシンボルまたは「文字列」であるすべてのモデルを最初にロードすることです。次に、集中管理者がこれらすべてのオブジェクトを取得し、文字列を対応するクラスに変換します。クラスはすべて定義されています。最初のクラスの関係を対応するクラスに設定すると、残りのクラスは引き続き文字列に関連付けられますが、この最初のクラスはクラスに関連付けられるため、一部のモデルがクラスに完全に解決される暫定的な期間があります。アルゴリズムが実行中であり、完了に達していないため、他のものはまだ文字列のままです。すべての文字列が対応するクラスに解決されると、アルゴリズムは完了です。

1 対 1 の循環依存関係ではなく、その間に多くのレイヤーがあり、5 ノードのループのようなものを作成するループを作成して、はるかに複雑になる世界を想像できます。または、次のようなモジュール間で依存関係が相互に存在するものでさえあります。

# file/1.rb
class X
  depends_on A
  depends_on B
end
class Y
  depends_on B
end
class Z
  depends_on Q
end

# file/2.rb
class A
  depends_on Y
end
class B
  depends_on Z
end

# file/3.rb
class Q
  depends_on X
end

これを解決するには:

すべてのファイル *.rb を読み込み、depends_on文字列として扱います。これで、対応するモジュールに各クラスの定義ができましたdepends_onが、目的のクラスではなく as 文字列が含まれています。
ファイルを繰り返し処理し、クラスを解決します。
ファイル 1.rb の場合、X を解決します... など。
X は A に依存するため、2/A と関連付けます。
X も B に依存するため、2/B と関連付けます。
Y は B に依存するため、2/B と関連付けます。
Z は Q に依存するため、3/Q と関連付けます。
A は Y に依存するため、1/Y と関連付けます。
B は Z に依存するため、1/Z と関連付けます。
Q は X に依存するため、1/X と関連付けます。
終わり。

したがって、基本的には 2 つの「ラウンド」があります。最初のラウンドは、すべてのファイルをロードし、クラスを初期化することです。2 番目のラウンドでは、クラスメンバーを対応する他のクラスに関連付けます。順番は問いません。

しかし、これ以上複雑になることはありますか? このような循環依存関係を解決するには、2 回以上のラウンドが必要ですか? わからない。たとえば、次のようなものがあります。

# file/1.rb
class A < A_P
  class AA < A_P::AA_P
    class AAA < A_P::AA_P::AAA_P

    end
  end
end
class B < B_Q
  class BB < B_Q::BB_Q
    class BBB < B_Q::BB_Q::BBB_Q

    end
  end
end

# file/2.rb
class A_P
  class AA_P < B
    class AAA_P < B::BB

    end
  end
end
class B_Q
  class BB_Q < A
    class BBB_Q < A::AA

    end
  end
end

この不自然なケースでは、次のものがあります。

AA_P(file/1) (file/2) に応じて、次のようになります。
AAA_P(file/1)およびに応じてAA_P、次のようになります。
AA_P(file/1) に応じてB(file/2) の場合:
B(file/1) に応じてB_Q(file/2) など....

つまり、何か奇妙なことが起こっているようです。よくわかりません、頭がゴツゴツし始めます。

クラスが完全に解決さAれるまで、どのクラスが拡張されているかを定義することはできません。クラスが完全に解決されるまで、クラスがA_P何であるかを定義することはできません。これは、解決されることに依存します。解決されることに依存します。等..AAAA_PBB_Q

このような循環依存を解決することは可能ですか? 任意に複雑な循環依存関係を解決するための一般的なアルゴリズムは何ですか? そのため、最終的には、すべての循環依存関係が、実際の値を表す文字列やその他のシンボルではなく、実際の値に結び付けられます。循環依存関係を解決することの最終結果は、すべての参照が実際のオブジェクトを参照する必要があるということです。

最初にベースオブジェクトをロードし、依存関係を解決して依存関係の「文字列」をセット内のベースオブジェクトに変換するという、常に単純な2パスアルゴリズムですか?

単純な 2 パスアルゴリズム以上のものを必要とする例を思いつくことができますか? その場合、循環依存関係を解決する際にアルゴリズムがどのように機能するかを説明してください。または、単純な 2 パスアルゴリズムのみが必要であることがどのように確実であるかを証明/説明しますか?

別の例は次のとおりです。

// ./p.jslike
import { method_x } from './q'
import { method_y } from './q'

function method_a() {
  method_x()
}

function method_b() {
  console.log('b')
}

function method_c() {
  method_y()
}

function method_d() {
  console.log('d')
}

// ./q.jslike
import { method_b } from './p'
import { method_d } from './p'

function method_x() {
  method_b()
}

function method_y() {
  method_b()
}

それもツーパスになると思います。

algorithm - 循環依存を解決するアルゴリズム?

1 に答える 1

Related

Reference