Re: pre-dependency for fetchmail, fetchmail-ssl
Richard Braakman wrote:
On Sun, Dec 23, 2001 at 07:49:10PM +0100, Torsten Landschoff wrote:
On Mon, Dec 17, 2001 at 08:51:51AM -0600, Adam Heath wrote:
So you can never have two packages that depend on each other?
Correct.
Isn't there this loop break hack in dpkg to allow for that? Not that
I would suggest having two packages depend on each other... :)
Actually a number of packages already have this. For example, libfoo
depending on libfoo-runtime, while libfoo-runtime depends on libfoo.
Unfortunately I didn't have the tools to find an example with which
to prove Adam wrong, but I do remember a FAQ about such a situation,
where people were told to upgrade by installing both packages in one
dpkg invocation. Apt also has an algorithm for breaking such cycles.
Here is my attempt at writing such a tool. Please try the attached
python script as in
python debdep.py --predep_cycles < /var/lib/dpkg/available > graph.dot
an read the output file or do
dot -Tps graph.dot > graph.ps
dot is part of the graphviz package.
I started a thread on the subject a few days ago, it is titled
"Detecting dependency cycles [....]"
Feedback wanted. Hope this helps :-)
--
Nicolas Chauvat
#!/usr/bin/env python
#
# (c) 2001-2002 Nicolas Chauvat <nico@logilab.fr> - License is GPL
"""
Script for Debian that loads the list of available packages, then perform
several checks on the package dependency graph :
- detect dependency cycle
Ex: A depends on B that depends on A (aka A --> B --> A)
Ex: A --> B --> C --> A
- detect conflict dependency problems
Ex: A conflicts with B that depends on A (A **> B --> A)
Ex: A **> B --> C --> A
Any idea of other patterns to look for ?
TODO : deal with version numbers, deal with alternatives.
"""
import sys
import string
import getopt
# debian package description parser ###########################################
class ParseDebDescriptionFile :
def parse(self,file,options={}) :
"""
Parse file and return a dict of result.
options :
desc --> include a description of packages in result
(desc = version, priority and section)
depend --> include a graph of dependencies in result
conflict --> include a graph of conflicts in result
replace --> include a graph of replacements in result
provide --> include a graph of provisions in result
"""
pkg = None
result = {}
for k in options.keys() :
result[k] = {}
for line in file.xreadlines() :
line = string.strip(line)
if not line :
pkg = None
elif line[:8] == 'Package:' :
pkg = string.strip(line[9:])
if options.has_key('desc') :
result['desc'][pkg] = {}
elif line[:8] == 'Section:' and options.has_key('desc') :
result['desc'][pkg]['section'] = string.strip(line[9:])
elif line[:8] == 'Version:' and options.has_key('desc') :
result['desc'][pkg]['version'] = string.strip(line[9:])
elif line[:9] == 'Priority:' and options.has_key('desc') :
result['desc'][pkg]['priority'] = string.strip(line[10:])
elif line[:8] == 'Depends:' and options.has_key('depend') :
result['depend'][pkg] = self.parse_list(line[9:])
elif line[:12] == 'Pre-Depends:' and options.has_key('pre-dep') :
result['pre-dep'][pkg] = self.parse_list(line[13:])
elif line[:10] == 'Conflicts:' and options.has_key('conflict') :
result['conflict'][pkg] = self.parse_list(line[11:])
elif line[:9] == 'Replaces:' and options.has_key('replace') :
result['replace'][pkg] = self.parse_list(line[10:])
elif line[:9] == 'Provides:' and options.has_key('provide') :
result['provide'][pkg] = self.parse_list(line[10:])
return result
def parse_list(self,line) :
d = []
for dep in string.split(line,',') :
for dep in string.split(dep,' | ') :
try:
d.append( string.strip(dep[:dep.index('(')]) )
except ValueError :
d.append(string.strip(dep))
return d
# graph manipulation ##########################################################
def multiply(A,B) :
"""
Multiply matrix A by B.
(Use optimisation as A and B are mostly filled with zeros !)
"""
result = {}
for node, arcs_to in A.items() :
d = {}
for to in arcs_to :
if B.has_key(to) :
for n in B[to] :
d[n] = None
if d :
result[node] = d.keys()
return result
def find_path(graph,start_node,end_node) :
"""
Find shortest path from start_node to end_node in given graph
"""
paths = [ [start_node] ]
while paths:
new_paths = []
cycles = []
for path in paths :
if not graph.has_key(path[-1]) :
continue
for d in graph[path[-1]] :
if not graph.has_key(d) : continue
if d == end_node :
cycles.append( path + [d] )
elif d not in path :
new_paths.append( path + [d] )
else :
pass # let's break that fatal cycle attraction
if cycles :
return cycles
else :
paths = new_paths
return []
def detect_cycles(g,graph,max_len) :
"""
Detect cycles in graph. Stop when reaching paths of length max_len
"""
cycles = []
for p in range(max_len) :
sys.stderr.write('POWER %i - %i nodes left\n'%(p,len(g)))
g = multiply(g,graph)
for node, arcs in g.items() :
if node in arcs :
sys.stderr.write('CYCLE of length %i for %s\n' %(p+2,node))
cycles.append( (node,p) )
del g[node]
for node, arcs in g.items() :
if not arcs :
# dead end, remove to simplify
del g[node]
else :
# remove cycle start points
for arc in arcs[:] :
for node,p in cycles :
if arc == node :
arcs.remove(arc)
if len(g) == 0 : break
return cycles
def focus_on(graph,all_desc,prio_or_sec,fokus) :
r = {}
for pkg,desc in all_desc.items() :
if desc[prio_or_sec] == fokus :
r[pkg] = {}
if not graph.has_key(pkg) : continue #FIXME
for arc in graph[pkg] :
try:
if all_desc[arc][prio_or_sec] == fokus :
r[pkg][arc] = None
else :
to = '%s_%s' % (prio_or_sec,all_desc[arc][prio_or_sec])
r[pkg][to] = None
except KeyError: pass # FIXME
result = {}
for k,i in r.items() :
result[k] = i.keys()
return result
def get_cycles_paths(graph,cycles) :
paths = []
for cycle in cycles :
paths.extend( find_path(graph,cycle[0],cycle[0]) )
return paths
def find_clusters(graph,cycles) :
clusters = []
for path in get_cycles_paths(graph,cycles) :
path = path[:-1]
m = path.index(min(path))
path = path[m:]+path[:m]
if not path in clusters :
clusters.append(path)
return clusters
# output functions ############################################################
def FT(s) :
"""format"""
return string.replace(string.replace(s,'.','_'),'-','_')
def report_cycles(graph,cycles,output) :
sys.stderr.write('reporting cycles...\n')
output.write("digraph dependency_cycle {\n")
for path in get_cycles_paths(graph,cycles) :
output.write(string.join(map(lambda x: '"%s"'%x, path),' -> '))
output.write(';\n')
output.write('}\n')
def report_conflict_problem(c_graph,graph,cycles,output) :
sys.stderr.write('reporting cycles...\n')
output.write("*** CONFLICT DEPENDENCY CYCLES DETECTED ***\n")
for cycle in cycles :
for c in c_graph[cycle[0]] :
for path in find_path(graph,c,cycle[0]) :
output.write('%s **>' % cycle[0])
output.write(string.join(path,' --> '))
output.write('\n')
def report_clusters(clusters,output) :
sys.stderr.write('reporting clusters...\n')
output.write("graph clusters {\n")
for cluster in clusters :
output.write(string.join(map(lambda x,f=FT: f(x),cluster),' -- '))
output.write(';\n')
output.write('}')
# main ########################################################################
def usage(lo) :
print __doc__
print "Options are ",lo
def main() :
sys.stderr.write('WARNING: debdep.py is work in progress... bugs may bite!\n')
# read options
try:
long_opt = ['help','max_path_len=','input=','output=','focus=',
'predep_cycles','dep_cycles','conf_pb','clusters',
]
short_opt= 'hi:o:'
opts, args = getopt.getopt(sys.argv[1:], short_opt, long_opt)
except getopt.GetoptError:
usage()
sys.exit(2)
input = sys.stdin
output = sys.stdout
todo = []
max_path_len = 10
focus = None
for o, a in opts:
if o in ("-h", "--help"):
usage()
sys.exit()
elif o in ("-i", "--input"):
input = open(a)
elif o in ("-o", "--output"):
output = open(a,'w')
elif o in ('--max_path_len',):
max_path_len = int(a)
elif o in ('--focus',):
focus = string.split(focus,',')
else :
todo.append(o)
# main
parse_options = {'desc':None,}
if '--clusters' in todo :
parse_options['depend'] = None
elif '--predep_cycles' in todo :
parse_options['pre-dep'] = None
parse_options['depend'] = None
elif '--dep_cycles' in todo :
parse_options['depend'] = None
elif '--conf_pb' in todo :
parse_options['conflict'] = None
parse_options['depend'] = None
sys.stderr.write('reading graph...\n')
packages = ParseDebDescriptionFile().parse(input,parse_options)
if focus :
graph = focus_on(graph,packages['desc'],focus[0],focus[1])
if '--predep_cycles' in todo :
sys.stderr.write('detecting pre-dependency cycles...\n')
cycles = detect_cycles(packages['pre-dep'],
packages['depend'], max_path_len)
if cycles :
report_cycles(graph,cycles,output)
elif '--clusters' in todo :
sys.stderr.write('detecting dependency cycles...\n')
graph = packages['depend']
cycles = detect_cycles(graph,graph, max_path_len)
clusters = find_clusters(graph,cycles)
if clusters :
report_clusters(clusters,output)
elif '--dep_cycles' in todo :
sys.stderr.write('detecting dependency cycles...\n')
graph = packages['depend']
cycles = detect_cycles(graph,graph, max_path_len)
if cycles :
report_cycles(graph,cycles,output)
elif '--conf_pb' in todo :
sys.stderr.write('detecting conflict problems...\n')
cycles = detect_cycles(packages['conflict'],packages['depend'],
max_path_len)
if cycles :
report_conflict_problem(packages['conflict'],
packages['depend'],cycles,output)
if __name__ == '__main__' :
main()
Reply to: