dom/canvas/test/webgl-conf/checkout/closure-library/closure/bin/build/depstree.py

   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
  18 Offers a queryable tree of dependencies of a given set of sources.  The tree
  19 will also do logical validation to prevent duplicate provides and circular
  20 dependencies.
  21 """
  22
  23 __author__ = 'nnaze@google.com (Nathan Naze)'
  24
  25
  26 class 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
 143 class BaseDepsTreeError(Exception):
 144   """Base DepsTree error."""
 145
 146   def __init__(self):
 147     Exception.__init__(self)
 148
 149
 150 class 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
 162 class 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
 177 class 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