1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
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
|
