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