파이썬에서 순환 종속성을 감지합니다.

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"가 "a"를 요구합니다. 브랜치에 의존성이 없을 때 일어나는 일을 보여주기 위해 "a"를 던져 보자. 의사 호출로 다음과 같은 호출 순서를 얻을 수 있습니다. 대부분 변수 이름이 변수 이름으로 대체됩니다 (예 : 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