1# Copyright 2009 The Closure Library Authors. All Rights Reserved. 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS-IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14 15 16"""Class to represent a full Closure Library dependency tree. 17 18Offers a queryable tree of dependencies of a given set of sources. The tree 19will also do logical validation to prevent duplicate provides and circular 20dependencies. 21""" 22 23__author__ = 'nnaze@google.com (Nathan Naze)' 24 25 26class DepsTree(object): 27 """Represents the set of dependencies between source files.""" 28 29 def __init__(self, sources): 30 """Initializes the tree with a set of sources. 31 32 Args: 33 sources: A set of JavaScript sources. 34 35 Raises: 36 MultipleProvideError: A namespace is provided by muplitple sources. 37 NamespaceNotFoundError: A namespace is required but never provided. 38 """ 39 40 self._sources = sources 41 self._provides_map = dict() 42 43 # Ensure nothing was provided twice. 44 for source in sources: 45 for provide in source.provides: 46 if provide in self._provides_map: 47 raise MultipleProvideError( 48 provide, [self._provides_map[provide], source]) 49 50 self._provides_map[provide] = source 51 52 # Check that all required namespaces are provided. 53 for source in sources: 54 for require in source.requires: 55 if require not in self._provides_map: 56 raise NamespaceNotFoundError(require, source) 57 58 def GetDependencies(self, required_namespaces): 59 """Get source dependencies, in order, for the given namespaces. 60 61 Args: 62 required_namespaces: A string (for one) or list (for one or more) of 63 namespaces. 64 65 Returns: 66 A list of source objects that provide those namespaces and all 67 requirements, in dependency order. 68 69 Raises: 70 NamespaceNotFoundError: A namespace is requested but doesn't exist. 71 CircularDependencyError: A cycle is detected in the dependency tree. 72 """ 73 if isinstance(required_namespaces, str): 74 required_namespaces = [required_namespaces] 75 76 deps_sources = [] 77 78 for namespace in required_namespaces: 79 for source in DepsTree._ResolveDependencies( 80 namespace, [], self._provides_map, []): 81 if source not in deps_sources: 82 deps_sources.append(source) 83 84 return deps_sources 85 86 @staticmethod 87 def _ResolveDependencies(required_namespace, deps_list, provides_map, 88 traversal_path): 89 """Resolve dependencies for Closure source files. 90 91 Follows the dependency tree down and builds a list of sources in dependency 92 order. This function will recursively call itself to fill all dependencies 93 below the requested namespaces, and then append its sources at the end of 94 the list. 95 96 Args: 97 required_namespace: String of required namespace. 98 deps_list: List of sources in dependency order. This function will append 99 the required source once all of its dependencies are satisfied. 100 provides_map: Map from namespace to source that provides it. 101 traversal_path: List of namespaces of our path from the root down the 102 dependency/recursion tree. Used to identify cyclical dependencies. 103 This is a list used as a stack -- when the function is entered, the 104 current namespace is pushed and popped right before returning. 105 Each recursive call will check that the current namespace does not 106 appear in the list, throwing a CircularDependencyError if it does. 107 108 Returns: 109 The given deps_list object filled with sources in dependency order. 110 111 Raises: 112 NamespaceNotFoundError: A namespace is requested but doesn't exist. 113 CircularDependencyError: A cycle is detected in the dependency tree. 114 """ 115 116 source = provides_map.get(required_namespace) 117 if not source: 118 raise NamespaceNotFoundError(required_namespace) 119 120 if required_namespace in traversal_path: 121 traversal_path.append(required_namespace) # do this *after* the test 122 123 # This must be a cycle. 124 raise CircularDependencyError(traversal_path) 125 126 # If we don't have the source yet, we'll have to visit this namespace and 127 # add the required dependencies to deps_list. 128 if source not in deps_list: 129 traversal_path.append(required_namespace) 130 131 for require in source.requires: 132 133 # Append all other dependencies before we append our own. 134 DepsTree._ResolveDependencies(require, deps_list, provides_map, 135 traversal_path) 136 deps_list.append(source) 137 138 traversal_path.pop() 139 140 return deps_list 141 142 143class BaseDepsTreeError(Exception): 144 """Base DepsTree error.""" 145 146 def __init__(self): 147 Exception.__init__(self) 148 149 150class CircularDependencyError(BaseDepsTreeError): 151 """Raised when a dependency cycle is encountered.""" 152 153 def __init__(self, dependency_list): 154 BaseDepsTreeError.__init__(self) 155 self._dependency_list = dependency_list 156 157 def __str__(self): 158 return ('Encountered circular dependency:\n%s\n' % 159 '\n'.join(self._dependency_list)) 160 161 162class MultipleProvideError(BaseDepsTreeError): 163 """Raised when a namespace is provided more than once.""" 164 165 def __init__(self, namespace, sources): 166 BaseDepsTreeError.__init__(self) 167 self._namespace = namespace 168 self._sources = sources 169 170 def __str__(self): 171 source_strs = map(str, self._sources) 172 173 return ('Namespace "%s" provided more than once in sources:\n%s\n' % 174 (self._namespace, '\n'.join(source_strs))) 175 176 177class NamespaceNotFoundError(BaseDepsTreeError): 178 """Raised when a namespace is requested but not provided.""" 179 180 def __init__(self, namespace, source=None): 181 BaseDepsTreeError.__init__(self) 182 self._namespace = namespace 183 self._source = source 184 185 def __str__(self): 186 msg = 'Namespace "%s" never provided.' % self._namespace 187 if self._source: 188 msg += ' Required in %s' % self._source 189 return msg 190