circular dependency

循环依赖是和语言无关的一个设计问题，在各个语言环境下都可能存在循环依赖，甚至引起 stackoverflow，这种大多数是由于不好的设计而导致的，一般来说都可以通过提取公共模块而解决，特定的场景下对应用程序做一定的调整也可以在维持循环依赖的前提下避免栈溢出。

 

语言机制：

 

c++

 

c++ 中的循环类定义引用会导致编译出错，一般的解决方案可以通过提前声明来解决:

 

 

b.h
class A;
class B {
  A a;
}

a.h
class B;
class A {
  B b
}

 

 

java

 

java 不需要像 C++ 一样提前声明，其中的循环依赖一般指两个类中实例变量的循环初始化，例如：

 

 

class A {
  B b=new B();
}

class B {
  A a =new A();
}

 

但是有了 spring 就可以很方便地通过依赖反转来解决这个问题，对应用代码做少许改变：

 

 

class A{
 B b;
 void setB(B b){this.b=b;}
}

class B{
 A a;
 void setB(A a){this.a=a;}
}

 

将依赖信息告诉 spring，spring 会设置好两个类实例的对应成员变量（先初始化实例再依赖注入）。

 

 

python

 

循环依赖指模块间的循环 import ，模块间互相使用对方的功能，在某些情景下其实可以通过调整引用顺序而避免引用不到对应模块的功能。

 

 

x.py

import y

def z():
  y.xx();

def q():
  // 


y.py

import x

x.q() //=> 没有 q

 

可以看到 y 的初始化需要立即使用 x模块的功能，而 x 模块初始化并不立即需要 y 模块功能，那么可以通过调整 x 模块中 y 模块的引入位置来避免初始化依赖而导致的空函数

 

 

 

x.py

def z():
  y.xx();

def q():
  //

import y

 

 

javascript

 

javascript 没有原生的模块机制，如果遵从 commonjs modules/1.1.1  ，那么面临和 python 一样的问题：

 

 

// a .js
define(function(require,exports){
  var b=require("b");  
  exports.z=function(){ b.z(); }
  exports.y=function(){}
})

// b.js
define(function(require,exports){
   var a=require("a");
   exports.z=function(){};
   expots.x=a.y();
})

 

 

这种情况下的解决也是类似的调整代码顺序：

 

 

// a .js
define(function(require,exports){
  exports.z=function(){ b.z(); }
  exports.y=function(){}
  var b=require("b");  
})

 

 

而对于 amd (requirejs , kissy ) 形式的模块则无论哪种形式的循环引用都不可能通过简单的调整代码顺序来解决：

 

 

// a .js
define(["b"],function(b){
  var ret={};
  ret.z=function(){ b.z(); }
  ret.y=function(){}
  return ret;
})

// b.js
define(["a"],function(a){
   var ret={};
   ret.z=function(){};
   ret.x=a.y();
   return ret;
})

 

 

 

循环依赖检测

 

程序中出现循环依赖是一种坏味道，所以在出现循环依赖时都希望语言实现以及模块框架能够及时提示，对于客户端的动态加载代码场景，js 的检测方法又有点特殊。

 

 

静态循环检测

 

一般的循环检测是有向图的一个常见问题，最常用的是 floyd 算法，而这种算法的前提是整个依赖图已经都全部知道，而对于 js 模块代码的依赖则是边下载模块脚本边构造模块的依赖图，没有机会等依赖图全部建立好后再进行静态循环分析（存在循环以来时，依赖图实际上永远也建立不好）。

 

动态循环检测

 

对于静态循环依赖检测，floyd 算法在空间和时间两方面都取得了很好的效果，这里提出的在构建依赖图的同时动态检测循环依赖的算法难免在空间方面有所不足。

 

前提：

 

模块 a 的初始化需要在 a 的所有依赖模块初始化之后。

 

步鄹：

 

对每个模块构建 map 结构 all_requires 表示当前模块的所有递归依赖项的集合，那么

 

1. 初始条件下 all_requires 为空 map

 

2. 在两种情况下扩充 all_requires

    2.1 当前模块 a 下载完毕，取得 a 的直接依赖集合 bs，合并 bs 到 all_requires

    2.2 由于模块 b 的初始化而导致作为 b 的依赖模块 a 的初始化：将模块 a 的直接依赖集合 bs 中每个模块的 all_requires 都合并到 a 的 all_requires 中

 

3. 检测当前模块 a 的 all_requires 集合中是否包含 a

    3.1 包含，则 a 的 all_requires 集合中的所有模块形成了循环依赖

 

4. 如果 a 初始化后，a 的 all_requires 仍然没有包含 a ，则 a 不在某个循环依赖模块集合中。

 

举例：

 

a -> b -> c -> a

 

初始 all_requires 集合：

 

a : {}

b: {}

c: {}

 

下载 a 后：

 

a:{b}

b:{}

c:{}

 

下载 b 后

 

a:{b}

b:{c}

c:{}

 

下载 c 后

 

a:{b}

b:{c}

c:{a}

 

c 导致 a 初始化

 

a:{bc}

b:{c}

c:{a}

 

a 导致 b 初始化

 

a:{bc}

b:{ca}

c:{a}

 

b 导致 c 初始化

 

a:{bc}

b:{ca}

c:{abc}

 

结束：

c 发现自己处于 abc 循环依赖中，报错

 

算法复杂度分析：

 

时间复杂度为 o(l), l 为循环依赖模块集合的大小

空间复杂度比较高，为 o(l^2) ，每个模块的 all_requires 集合都包含了近似于所有循环依赖的模块。

 

Refer:

 

http://en.wikipedia.org/wiki/Cycle_detection

 

http://en.wikipedia.org/wiki/Circular_dependency

 

http://effbot.org/zone/import-confusion.htm

 

http://stackoverflow.com/questions/3646113/circular-dependency-in-java-classes

 

http://stackoverflow.com/questions/3485347/circular-dependency-in-spring

 

http://java.dzone.com/articles/tackling-circular-dependency

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

评论

1 楼 xthsky 2011-12-12  

明白了，多谢