检测 Python 中的循环依赖

Question

我不太明白为什么DepsTree类里的_ResolveDependencies方法能够检测到循环依赖。看起来它能发现如果a需要b和e，而b又需要e，但这并不是循环依赖的情况。

class DepsTree(object):
  """Represents the set of dependencies between source files."""

  def __init__(self, sources):
    """Initializes the tree with a set of sources.

    Args:
      sources: A set of JavaScript sources.

    Raises:
      MultipleProvideError: A namespace is provided by muplitple sources.
      NamespaceNotFoundError: A namespace is required but never provided.
    """

    self._sources = sources
    self._provides_map = dict()

    # Ensure nothing was provided twice.
    for source in sources:
      for provide in source.provides:
        if provide in self._provides_map:
          raise MultipleProvideError(
              provide, [self._provides_map[provide], source])

        self._provides_map[provide] = source

    # Check that all required namespaces are provided.
    for source in sources:
      for require in source.requires:
        if require not in self._provides_map:
          raise NamespaceNotFoundError(require, source)

  def GetDependencies(self, required_namespaces):
    """Get source dependencies, in order, for the given namespaces.

    Args:
      required_namespaces: A string (for one) or list (for one or more) of
        namespaces.

    Returns:
      A list of source objects that provide those namespaces and all
      requirements, in dependency order.

    Raises:
      NamespaceNotFoundError: A namespace is requested but doesn't exist.
      CircularDependencyError: A cycle is detected in the dependency tree.
    """
    if type(required_namespaces) is str:
      required_namespaces = [required_namespaces]

    deps_sources = []

    for namespace in required_namespaces:
      for source in DepsTree._ResolveDependencies(
          namespace, [], self._provides_map, []):
        if source not in deps_sources:
          deps_sources.append(source)

    return deps_sources

  @staticmethod
  def _ResolveDependencies(required_namespace, deps_list, provides_map,
                           traversal_path):
    """Resolve dependencies for Closure source files.

    Follows the dependency tree down and builds a list of sources in dependency
    order.  This function will recursively call itself to fill all dependencies
    below the requested namespaces, and then append its sources at the end of
    the list.

    Args:
      required_namespace: String of required namespace.
      deps_list: List of sources in dependency order.  This function will append
        the required source once all of its dependencies are satisfied.
      provides_map: Map from namespace to source that provides it.
      traversal_path: List of namespaces of our path from the root down the
        dependency/recursion tree.  Used to identify cyclical dependencies.
        This is a list used as a stack -- when the function is entered, the
        current namespace is pushed and popped right before returning.
        Each recursive call will check that the current namespace does not
        appear in the list, throwing a CircularDependencyError if it does.

    Returns:
      The given deps_list object filled with sources in dependency order.

    Raises:
      NamespaceNotFoundError: A namespace is requested but doesn't exist.
      CircularDependencyError: A cycle is detected in the dependency tree.
    """

    source = provides_map.get(required_namespace)
    if not source:
      raise NamespaceNotFoundError(required_namespace)

    if required_namespace in traversal_path:
      traversal_path.append(required_namespace)  # do this *after* the test

      # This must be a cycle.
      raise CircularDependencyError(traversal_path)

    traversal_path.append(required_namespace)

    for require in source.requires:

      # Append all other dependencies before we append our own.
      DepsTree._ResolveDependencies(require, deps_list, provides_map,
                                    traversal_path)
    deps_list.append(source)

    traversal_path.pop()

    return deps_list

Answer 1

简短版：_ResolveDependencies 是一个深度优先遍历依赖树的过程，它会记录路径。如果它遇到一个已经在路径上的节点，那就说明出现了循环。

_ResolveDependencies 会遍历由 Source.requires 表示的依赖森林。在任何时刻，正在调用的 _ResolveDependencies 对应着依赖树中的一条路径（所以有 _path 在 traversal_path 中）；这个过程是通过在递归之前向 traversal_path 添加一个命名空间，然后在递归之后再移除来跟踪的。换句话说，只有当 _ResolveDependencies 正在处理某个命名空间时，这个命名空间才会出现在 traversal_path 中。如果 _ResolveDependencies 被要求检查一个已经在 traversal_path 中的命名空间，那就说明另一个 _ResolveDependencies 正在处理这个命名空间，这样就形成了从一个节点到它自身的路径，也就是出现了循环。

举个例子，考虑最简单的依赖循环：“a” 依赖于 “c”，而 “c” 又依赖于 “a”。我们再加上一个“a”依赖于“b”，来展示当某个分支没有依赖时会发生什么。你会得到以下的调用顺序（伪代码）。大多数情况下，变量的值会替代变量名（例如 a 替代 ns.name）。注意：这不是源代码，而是程序运行时执行的语句顺序。

_RD(ns={name:a, req: [b, c]}, path=[]):
  if a in path: # false
  path += [a]
  for each subns in [b,c]:
    _RD(ns={name: b, req: []}, path=[a]):
      if b in path: # false
      path += [b]
      for each subns in []:
      # done with this branch
      path -= [b]      
    _RD(ns={name: c, req: [a]}, path=[a]):
      if c in path: # false
      path += [c]
      for each subns in [a]:
        _RD(ns={name: a req: [b,c]}, path=[a, c]):
          if a in path: # true
            throw CircularDependencyError