解决循环依赖的算法？

Question

我想创建一个模块系统，您可以在其中以循环方式加载依赖项。原因是循环依赖无处不在，比如 Ruby on Rails，在模型 classes:

之间的关系中

# 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 中 Rails 模型上的一般工作方式至少是首先加载所有模型，依赖项首先是符号或“字符串”。然后集中管理器获取所有这些对象并将字符串转换为相应的 classes，现在 classes 都已定义。当您将第一个 class 的关系设置为其对应的 classes 时，其余 classes 仍然与字符串相关，而第一个 class 与 classes，所以有一个过渡期，其中一些模型完全解析为 classes，而其他模型仍然是字符串，因为算法是运行并且尚未完成。一旦所有字符串都解析为其对应的 classes，算法就完成了。

我可以想象一个世界，它变得更加复杂，创建的循环不是一对一的循环依赖关系，而是在它们之间有很多层，创建一个 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 视为字符串。现在我们在相应的模块中有了每个 class 的定义，但是 depends_on 作为字符串而不是所需的 classes.
遍历文件并解析 classes.
对于文件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相关联。
完成。

基本上，有两个“回合”。第一轮是加载所有文件，并初始化 classes。第二轮是将 class 成员与相应的其他 class 成员相关联。顺序无关紧要。

但是它还能变得更复杂吗？需要两轮以上才能解决这种循环依赖？我不确定。举个例子：

# 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

在这种人为设计的情况下，您有：

A(file/1)取决于A_P(file/2)，则：
AA (file/1) 取决于 A_P 和 AA_P，则：
AA_P(file/2)取决于B(file/1)，则：
B (file/1) 取决于 B_Q (file/2), 等等....

也就是说，好像有什么奇怪的事情发生了。我不确定，我的头开始打结。

在 class A_P 完全解析之前，您无法定义 class A 正在扩展的内容。在 class AA_P 完全解析之前，您无法定义 class AA 是什么，这取决于 B 被解析，这取决于 [=24= 】正在解决。等等

是否可以解决这种循环依赖？解决任意复杂循环依赖的通用算法是什么？这样，最终所有循环依赖项都与实际值连接起来，而不是字符串或其他此类符号表示实际值。解决循环依赖的最终结果是每个引用都应该引用实际对象。

它总是只是一个简单的两遍算法，首先加载基础对象，然后解析它们的依赖关系，将依赖关系的“字符串”转换为集合中的基础对象吗？

你能举出一个例子，它需要的不仅仅是简单的两次通过算法吗？然后描述算法应该如何解决这种情况下的循环依赖？或者prove/explain如何确定只需要简单的两遍算法？

另一个例子可能是：

// ./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()
}

我想那也是两次通过。

Answer 1

您问题的答案取决于您所说的“解决”是什么意思。

考虑以下情况：

你有三个class，A，B和C，它们以循环方式相互依赖。

第一次通过（加载）后，您可以访问每个 class 的所有信息，这些信息都写在源文件中。

现在，假设您想完全“解决”class A。假装你暂时不关心其他 classes。

仅根据文件中的信息，是否可以仅针对 A 执行所需的“解决”？

如果答案是否，那么你的问题的答案也是否。

如果答案是是，则意味着两遍足以完全解决每个class。您可以递归或迭代地执行此操作，并且您可能希望缓存完全解析的 classes 以避免多次解析它们，尽管这不是正确性所必需的（它纯粹是性能优化）。

解决循环依赖的算法？

Algorithm to resolve circular dependencies?

algorithm

dependencies

graph-theory

circular-dependency

cyclic-graph