1 files changed, 189 insertions, 0 deletions
diff --git a/dom/canvas/test/webgl-conf/checkout/closure-library/closure/bin/build/depstree.py b/dom/canvas/test/webgl-conf/checkout/closure-library/closure/bin/build/depstree.py
new file mode 100755
index 0000000000..f288dd3aa6
--- /dev/null
+++ b/dom/canvas/test/webgl-conf/checkout/closure-library/closure/bin/build/depstree.py
@@ -0,0 +1,189 @@
+# Copyright 2009 The Closure Library Authors. All Rights Reserved.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS-IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+
+"""Class to represent a full Closure Library dependency tree.
+
+Offers a queryable tree of dependencies of a given set of sources.  The tree
+will also do logical validation to prevent duplicate provides and circular
+dependencies.
+"""
+
+__author__ = 'nnaze@google.com (Nathan Naze)'
+
+
+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 isinstance(required_namespaces, 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)
+
+    # If we don't have the source yet, we'll have to visit this namespace and
+    # add the required dependencies to deps_list.
+    if source not in deps_list:
+      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
+
+
+class BaseDepsTreeError(Exception):
+  """Base DepsTree error."""
+
+  def __init__(self):
+    Exception.__init__(self)
+
+
+class CircularDependencyError(BaseDepsTreeError):
+  """Raised when a dependency cycle is encountered."""
+
+  def __init__(self, dependency_list):
+    BaseDepsTreeError.__init__(self)
+    self._dependency_list = dependency_list
+
+  def __str__(self):
+    return ('Encountered circular dependency:\n%s\n' %
+            '\n'.join(self._dependency_list))
+
+
+class MultipleProvideError(BaseDepsTreeError):
+  """Raised when a namespace is provided more than once."""
+
+  def __init__(self, namespace, sources):
+    BaseDepsTreeError.__init__(self)
+    self._namespace = namespace
+    self._sources = sources
+
+  def __str__(self):
+    source_strs = map(str, self._sources)
+
+    return ('Namespace "%s" provided more than once in sources:\n%s\n' %
+            (self._namespace, '\n'.join(source_strs)))
+
+
+class NamespaceNotFoundError(BaseDepsTreeError):
+  """Raised when a namespace is requested but not provided."""
+
+  def __init__(self, namespace, source=None):
+    BaseDepsTreeError.__init__(self)
+    self._namespace = namespace
+    self._source = source
+
+  def __str__(self):
+    msg = 'Namespace "%s" never provided.' % self._namespace
+    if self._source:
+      msg += ' Required in %s' % self._source
+    return msg