は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に既に存在する名前空間をチェックするように要求された場合は、_ResolveDependenciesの別の呼び出しが名前空間を処理しており、ノードからそのノードへのパスが存在するため、サイクルが存在します。

例として、最も単純な依存サイクルを考えてみましょう。 "a"は "c"が "a"を必要とすることを要求します。ブランチに依存していないときに何が起こるかを示すために、 "a"をスローしてみましょう。以下の呼び出しシーケンスを（擬似Pythonで）取得します。ほとんどの場合、変数名の代わりに変数の値が使用されます（例：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