обнаружить круговые зависимости в python

Question

Я не понимаю, почему метод _ResolveDependencies в классе DepsTree может обнаруживать циклические зависимости.Кажется, он может обнаружить ситуацию, если 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 до рекурсии и удаления его после. Другими словами, пространство имен находится в traversal_path тогда и только тогда, когда вызов _ResolveDependencies обрабатывает пространство имен. Если _ResolveDependencies требуется проверить пространство имен, которое уже существует в traversal_path, тогда другой вызов _ResolveDependencies обрабатывает пространство имен, и существует путь от узла к самому себе, следовательно, цикл.

В качестве примера рассмотрим простейший цикл зависимости: «a» требует «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