Python code coverage for Lib/packaging/depgraph.py

#	count	content
1	n/a	"""Class and functions dealing with dependencies between distributions.
2	n/a
3	n/a	This module provides a DependencyGraph class to represent the
4	n/a	dependencies between distributions. Auxiliary functions can generate a
5	n/a	graph, find reverse dependencies, and print a graph in DOT format.
6	n/a	"""
7	n/a
8	n/a	import sys
9	n/a
10	n/a	from io import StringIO
11	n/a	from packaging.errors import PackagingError
12	n/a	from packaging.version import VersionPredicate, IrrationalVersionError
13	n/a
14	n/a	__all__ = ['DependencyGraph', 'generate_graph', 'dependent_dists',
15	n/a	'graph_to_dot']
16	n/a
17	n/a
18	n/a	class DependencyGraph:
19	n/a	"""
20	n/a	Represents a dependency graph between distributions.
21	n/a
22	n/a	The dependency relationships are stored in an ``adjacency_list`` that maps
23	n/a	distributions to a list of ``(other, label)`` tuples where ``other``
24	n/a	is a distribution and the edge is labeled with ``label`` (i.e. the version
25	n/a	specifier, if such was provided). Also, for more efficient traversal, for
26	n/a	every distribution ``x``, a list of predecessors is kept in
27	n/a	``reverse_list[x]``. An edge from distribution ``a`` to
28	n/a	distribution ``b`` means that ``a`` depends on ``b``. If any missing
29	n/a	dependencies are found, they are stored in ``missing``, which is a
30	n/a	dictionary that maps distributions to a list of requirements that were not
31	n/a	provided by any other distributions.
32	n/a	"""
33	n/a
34	n/a	def __init__(self):
35	n/a	self.adjacency_list = {}
36	n/a	self.reverse_list = {}
37	n/a	self.missing = {}
38	n/a
39	n/a	def add_distribution(self, distribution):
40	n/a	"""Add the distribution to the graph.
41	n/a
42	n/a	:type distribution: :class:`packaging.database.Distribution` or
43	n/a	:class:`packaging.database.EggInfoDistribution`
44	n/a	"""
45	n/a	self.adjacency_list[distribution] = []
46	n/a	self.reverse_list[distribution] = []
47	n/a	self.missing[distribution] = []
48	n/a
49	n/a	def add_edge(self, x, y, label=None):
50	n/a	"""Add an edge from distribution x to distribution y with the given
51	n/a	label.
52	n/a
53	n/a	:type x: :class:`packaging.database.Distribution` or
54	n/a	:class:`packaging.database.EggInfoDistribution`
55	n/a	:type y: :class:`packaging.database.Distribution` or
56	n/a	:class:`packaging.database.EggInfoDistribution`
57	n/a	:type label: ``str`` or ``None``
58	n/a	"""
59	n/a	self.adjacency_list[x].append((y, label))
60	n/a	# multiple edges are allowed, so be careful
61	n/a	if x not in self.reverse_list[y]:
62	n/a	self.reverse_list[y].append(x)
63	n/a
64	n/a	def add_missing(self, distribution, requirement):
65	n/a	"""
66	n/a	Add a missing requirement for the given distribution.
67	n/a
68	n/a	:type distribution: :class:`packaging.database.Distribution` or
69	n/a	:class:`packaging.database.EggInfoDistribution`
70	n/a	:type requirement: ``str``
71	n/a	"""
72	n/a	self.missing[distribution].append(requirement)
73	n/a
74	n/a	def _repr_dist(self, dist):
75	n/a	return '%r %s' % (dist.name, dist.version)
76	n/a
77	n/a	def repr_node(self, dist, level=1):
78	n/a	"""Prints only a subgraph"""
79	n/a	output = []
80	n/a	output.append(self._repr_dist(dist))
81	n/a	for other, label in self.adjacency_list[dist]:
82	n/a	dist = self._repr_dist(other)
83	n/a	if label is not None:
84	n/a	dist = '%s [%s]' % (dist, label)
85	n/a	output.append(' ' * level + str(dist))
86	n/a	suboutput = self.repr_node(other, level + 1)
87	n/a	subs = suboutput.split('\n')
88	n/a	output.extend(subs[1:])
89	n/a	return '\n'.join(output)
90	n/a
91	n/a	def __repr__(self):
92	n/a	"""Representation of the graph"""
93	n/a	output = []
94	n/a	for dist, adjs in self.adjacency_list.items():
95	n/a	output.append(self.repr_node(dist))
96	n/a	return '\n'.join(output)
97	n/a
98	n/a
99	n/a	def graph_to_dot(graph, f, skip_disconnected=True):
100	n/a	"""Writes a DOT output for the graph to the provided file f.
101	n/a
102	n/a	If skip_disconnected is set to ``True``, then all distributions
103	n/a	that are not dependent on any other distribution are skipped.
104	n/a
105	n/a	:type f: has to support ``file``-like operations
106	n/a	:type skip_disconnected: ``bool``
107	n/a	"""
108	n/a	disconnected = []
109	n/a
110	n/a	f.write("digraph dependencies {\n")
111	n/a	for dist, adjs in graph.adjacency_list.items():
112	n/a	if len(adjs) == 0 and not skip_disconnected:
113	n/a	disconnected.append(dist)
114	n/a	for other, label in adjs:
115	n/a	if not label is None:
116	n/a	f.write('"%s" -> "%s" [label="%s"]\n' %
117	n/a	(dist.name, other.name, label))
118	n/a	else:
119	n/a	f.write('"%s" -> "%s"\n' % (dist.name, other.name))
120	n/a	if not skip_disconnected and len(disconnected) > 0:
121	n/a	f.write('subgraph disconnected {\n')
122	n/a	f.write('label = "Disconnected"\n')
123	n/a	f.write('bgcolor = red\n')
124	n/a
125	n/a	for dist in disconnected:
126	n/a	f.write('"%s"' % dist.name)
127	n/a	f.write('\n')
128	n/a	f.write('}\n')
129	n/a	f.write('}\n')
130	n/a
131	n/a
132	n/a	def generate_graph(dists):
133	n/a	"""Generates a dependency graph from the given distributions.
134	n/a
135	n/a	:parameter dists: a list of distributions
136	n/a	:type dists: list of :class:`packaging.database.Distribution` and
137	n/a	:class:`packaging.database.EggInfoDistribution` instances
138	n/a	:rtype: a :class:`DependencyGraph` instance
139	n/a	"""
140	n/a	graph = DependencyGraph()
141	n/a	provided = {} # maps names to lists of (version, dist) tuples
142	n/a
143	n/a	# first, build the graph and find out the provides
144	n/a	for dist in dists:
145	n/a	graph.add_distribution(dist)
146	n/a	provides = (dist.metadata['Provides-Dist'] +
147	n/a	dist.metadata['Provides'] +
148	n/a	['%s (%s)' % (dist.name, dist.version)])
149	n/a
150	n/a	for p in provides:
151	n/a	comps = p.strip().rsplit(" ", 1)
152	n/a	name = comps[0]
153	n/a	version = None
154	n/a	if len(comps) == 2:
155	n/a	version = comps[1]
156	n/a	if len(version) < 3 or version[0] != '(' or version[-1] != ')':
157	n/a	raise PackagingError('distribution %r has ill-formed'
158	n/a	'provides field: %r' % (dist.name, p))
159	n/a	version = version[1:-1] # trim off parenthesis
160	n/a	if name not in provided:
161	n/a	provided[name] = []
162	n/a	provided[name].append((version, dist))
163	n/a
164	n/a	# now make the edges
165	n/a	for dist in dists:
166	n/a	requires = dist.metadata['Requires-Dist'] + dist.metadata['Requires']
167	n/a	for req in requires:
168	n/a	try:
169	n/a	predicate = VersionPredicate(req)
170	n/a	except IrrationalVersionError:
171	n/a	# XXX compat-mode if cannot read the version
172	n/a	name = req.split()[0]
173	n/a	predicate = VersionPredicate(name)
174	n/a
175	n/a	name = predicate.name
176	n/a
177	n/a	if name not in provided:
178	n/a	graph.add_missing(dist, req)
179	n/a	else:
180	n/a	matched = False
181	n/a	for version, provider in provided[name]:
182	n/a	try:
183	n/a	match = predicate.match(version)
184	n/a	except IrrationalVersionError:
185	n/a	# XXX small compat-mode
186	n/a	if version.split(' ') == 1:
187	n/a	match = True
188	n/a	else:
189	n/a	match = False
190	n/a
191	n/a	if match:
192	n/a	graph.add_edge(dist, provider, req)
193	n/a	matched = True
194	n/a	break
195	n/a	if not matched:
196	n/a	graph.add_missing(dist, req)
197	n/a	return graph
198	n/a
199	n/a
200	n/a	def dependent_dists(dists, dist):
201	n/a	"""Recursively generate a list of distributions from dists that are
202	n/a	dependent on dist.
203	n/a
204	n/a	:param dists: a list of distributions
205	n/a	:param dist: a distribution, member of dists for which we are interested
206	n/a	"""
207	n/a	if dist not in dists:
208	n/a	raise ValueError('given distribution %r is not a member of the list' %
209	n/a	dist.name)
210	n/a	graph = generate_graph(dists)
211	n/a
212	n/a	dep = [dist] # dependent distributions
213	n/a	fringe = graph.reverse_list[dist] # list of nodes we should inspect
214	n/a
215	n/a	while not len(fringe) == 0:
216	n/a	node = fringe.pop()
217	n/a	dep.append(node)
218	n/a	for prev in graph.reverse_list[node]:
219	n/a	if prev not in dep:
220	n/a	fringe.append(prev)
221	n/a
222	n/a	dep.pop(0) # remove dist from dep, was there to prevent infinite loops
223	n/a	return dep
224	n/a
225	n/a
226	n/a	def main():
227	n/a	# XXX move to run._graph
228	n/a	from packaging.database import get_distributions
229	n/a	tempout = StringIO()
230	n/a	try:
231	n/a	old = sys.stderr
232	n/a	sys.stderr = tempout
233	n/a	try:
234	n/a	dists = list(get_distributions(use_egg_info=True))
235	n/a	graph = generate_graph(dists)
236	n/a	finally:
237	n/a	sys.stderr = old
238	n/a	except Exception as e:
239	n/a	tempout.seek(0)
240	n/a	tempout = tempout.read()
241	n/a	print('Could not generate the graph')
242	n/a	print(tempout)
243	n/a	print(e)
244	n/a	sys.exit(1)
245	n/a
246	n/a	for dist, reqs in graph.missing.items():
247	n/a	if len(reqs) > 0:
248	n/a	print("Warning: Missing dependencies for %r:" % dist.name,
249	n/a	", ".join(reqs))
250	n/a	# XXX replace with argparse
251	n/a	if len(sys.argv) == 1:
252	n/a	print('Dependency graph:')
253	n/a	print(' ', repr(graph).replace('\n', '\n '))
254	n/a	sys.exit(0)
255	n/a	elif len(sys.argv) > 1 and sys.argv[1] in ('-d', '--dot'):
256	n/a	if len(sys.argv) > 2:
257	n/a	filename = sys.argv[2]
258	n/a	else:
259	n/a	filename = 'depgraph.dot'
260	n/a
261	n/a	with open(filename, 'w') as f:
262	n/a	graph_to_dot(graph, f, True)
263	n/a	tempout.seek(0)
264	n/a	tempout = tempout.read()
265	n/a	print(tempout)
266	n/a	print('Dot file written at %r' % filename)
267	n/a	sys.exit(0)
268	n/a	else:
269	n/a	print('Supported option: -d [filename]')
270	n/a	sys.exit(1)