import repository from arizona
[raven.git] / apps / stork / storkdependency.py
1 #! /usr/bin/env python
2 """
3 <Program Name>
4    storkdependency.py
5
6 <Started>
7    June 20, 2006
8
9 <Author>
10    Programmed by Jeffry Johnston.
11
12 <Purpose>
13    Resolve package dependencies.
14 """
15
16
17 #           [option, long option,                    variable,      action,        data,  default, metavar, description]
18 """arizonaconfig
19    options=[
20             ["-a",   "--abort",                      "abort",       "store_true",  None,  False,   None,    "if we reject a package then abort"],
21             ["-A",   "--abortdepth",                 "abortdepth",  "store",       "int", 0,       "depth", "ignore rejections past a certain depth (for abort)"],
22             ["",     "--disabletrustedpackagesdata", "disable_tpf", "store_true",  None,  False,   None,    "do not check the trustedpackages file before installing a package (WARNING: allows untrusted package installation)"],
23             ["",     "--noupgradedeps",              "upgrade_deps","store_false", None,  True,    None,    "do not automatically upgrade dependencies when upgrading or installing packages"]]
24    includes=[]
25 """
26
27 import os
28 import sys
29 import string
30 import arizonaconfig
31 import arizonageneral
32 import ravenlib.package.storkpackage
33 import storklog
34 import storkpackagelist
35 import storkpackagesort
36 import storktrustedpackagesparse
37 import arizonareport
38
39 # for new TP file stuff
40 import storktpqualify
41
42 # for old TP file stuff
43 #import storktprank
44
45 from storkpackagesort import EQUAL, LESS, LESS_EQUAL, GREATER, GREATER_EQUAL
46
47 def greater_than_zero(x):
48    """
49    <Purpose>
50       Returns True if x>0. If x cannot be converted to an integer, return False
51    """
52    try:
53       v = int(x)
54       return (v > 0)
55    except ValueError:
56       return False
57
58 def this_satisfies(name, ver, candidate):
59    """
60    <Purpose>
61       Indicates if a candidate string matches the "name", "ver"
62       requirements.
63
64    <Arguments>
65       name:
66               The base name of the package (without version, etc).
67       ver:
68               Package version (usu. starts with relational operator),
69               where relational_operator is one of:
70                  =, >=, <=, >, <
71       candidate:
72               "name of package = version".
73
74    <Exceptions>
75       None.
76
77    <Side Effects>
78       None.
79
80    <Returns>
81       False unless the string meets the name and version requirements.
82    """
83    # check params
84    arizonageneral.check_type_simple(name, "name", str, "stork.this_satisfies")
85    arizonageneral.check_type_simple(ver, "ver", str, "stork.this_satisfies")
86    arizonageneral.check_type_simple(candidate, "candidate", str, "stork.this_satisfies")
87
88    #arizonareport.send_out(4, "[DEBUG] storkdependency.this_satisfies(" +name+ ", " +ver+ ", " +candidate+ ")")
89
90    # Comparison takes place in up to five steps:
91    # 1) compare package names
92    # 2) check for a relational operator
93    # 3) compare epochs, if an epoch exists then steps 4 and 5 are ignored
94    # 4) compare versions
95    # 5) compare release numbers
96
97    required_name = name
98    original_ver = ver
99    original_candidate = candidate
100
101    # Break candidate into name, =, epoch, version, and release parts
102    candidate = candidate.strip()
103
104    # candidate name
105    i = candidate.find("=")
106    if i == -1:
107       candidate_name = candidate
108       candidate_epoch = ""
109       candidate_version = ""
110       candidate_release = ""
111       candidate = ""
112    else:
113       candidate_name = candidate[:i].rstrip()
114       candidate = candidate[i + 1:].lstrip()
115
116    # Step 1: Compare package names
117    # -----------------------------
118    if candidate_name != required_name:
119       return False
120
121    # if the candidate has no version number, then always return True
122    # XXX this appears to be how rpm behaves
123    if not candidate:
124        return True
125
126    # Break ver into relational operator, epoch, version, and release parts
127    ver = ver.strip()
128
129    # relational operator
130    # TODO need to support >> and << for Debian
131    if ver.startswith(">="):
132       rel_oper = GREATER_EQUAL
133       ver = ver[2:]
134    elif ver.startswith(">"):
135       rel_oper = GREATER
136       ver = ver[1:]
137    elif ver.startswith("<="):
138       rel_oper = LESS_EQUAL
139       ver = ver[2:]
140    elif ver.startswith("<"):
141       rel_oper = LESS
142       ver = ver[1:]
143    elif ver.startswith("="):
144       rel_oper = EQUAL
145       ver = ver[1:]
146    else:
147       rel_oper = None
148    ver = ver.lstrip()
149
150    #arizonareport.send_out(4, "[DEBUG] storkdependency.this_satisfies rel_oper " + str(rel_oper))
151
152    # Step 2: Check for a relational operator
153    # ---------------------------------------
154    if rel_oper == None:
155       # if there isn't a relational operator, then anything with the
156       # correct name satisfies the dependency
157       return True
158
159    # required epoch
160    i = ver.find(":")
161    if i == -1:
162       required_epoch = ""
163    else:
164       required_epoch = ver[:i].rstrip()
165       ver = ver[i + 1:].lstrip()
166
167    # candidate epoch
168    i = candidate.find(":")
169    if i == -1:
170       candidate_epoch = ""
171    else:
172       candidate_epoch = candidate[:i].rstrip()
173       candidate = candidate[i + 1:].lstrip()
174
175    # Step 3: Compare epochs
176    # ----------------------
177    # Note: If one has an nonzero epoch and the other does not, then the one with
178    #       the epoch is automatically greater than the one without an
179    #       epoch.
180    if greater_than_zero(required_epoch) or greater_than_zero(candidate_epoch):
181       if not greater_than_zero(required_epoch):
182          # required didn't have an epoch, so candidate is automatically
183          # greater than required
184          result = GREATER
185       elif not greater_than_zero(candidate_epoch):
186          # candidate didn't have an epoch, so candidate is automatically
187          # less than required
188          result = LESS
189       else:
190          # both candidate and required have epochs, compare them directly
191          if candidate_epoch > required_epoch:
192             result = GREATER
193          elif candidate_epoch < required_epoch:
194             result = LESS
195          else:
196             result = EQUAL
197
198       # if rel_oper contains the result, then the candidate satisfies the
199       # dependency, otherwise it doesn't
200       return (rel_oper & result) != 0
201
202    # required version and release
203    i = ver.rfind("-")
204    if i == -1:
205       required_version = ver
206       required_release = ""
207    else:
208       required_version = ver[:i].rstrip()
209       required_release = ver[i + 1:].lstrip()
210
211    # candidate version and release
212    i = candidate.rfind("-")
213    if i == -1:
214       candidate_version = candidate
215       candidate_release = ""
216    else:
217       candidate_version = candidate[:i].rstrip()
218       candidate_release = candidate[i + 1:].lstrip()
219
220    # Step 4: Compare versions
221    # ------------------------
222    if required_version == "":
223       # if there isn't a specific required version, then any version
224       # should satisfy the dependency
225       return True
226
227    if candidate_version == "":
228       # we don't know what version the candidate is, so reject to be safe
229       return False
230
231    result = storkpackagesort.compare_version(candidate_version, required_version)
232
233    #arizonareport.send_out(4, "[DEBUG]   ver cand=" + candidate_version + " req=" +required_version+ " res=" + str(result))
234
235    # if the result contains LESS or GREATER, and we're looking for something
236    # that is less or greater, then we have satisfied the dependency and do not
237    # need to check release numbers.
238    if (rel_oper & result & LESS) != 0:
239       return True
240    if (rel_oper & result & GREATER) != 0:
241       return True
242
243    # we're done unless the versions were equal
244    if result != EQUAL:
245       return False
246
247    # Step 5: Compare release numbers
248    # -------------------------------
249    if required_release == "":
250       # if there isn't a specific required release, then any release
251       # satisfies the dependency if the version was satisifed
252       return (rel_oper & result) != 0
253
254    if candidate_version == "":
255       # we don't know what release the candidate is, so reject to be safe
256       return False
257
258    result = storkpackagesort.compare_version(candidate_release, required_release)
259    #arizonareport.send_out(4, "[DEBUG]   rel cand=" + candidate_release + " req=" +required_release+ " res=" + str(result))
260
261    # if rel_oper contains the result, then the candidate satisfies the
262    # dependency, otherwise it doesn't
263    return (rel_oper & result) != 0
264
265
266
267
268
269 def this_satisfies_list(name, ver, candidate_list):
270    """
271    <Purpose>
272       Indicates if a candidate string matches the "name", "ver"
273       requirements.
274    """
275
276    for candidate in candidate_list:
277        if this_satisfies(name, ver, candidate):
278            return True
279
280    return False
281
282
283 def find_satisfying_packages(name, ver):
284    """
285    <Purpose>
286       Searches for packages meeting the name and version requirements.
287
288    <Arguments>
289       name:
290               The single dependency needing to be satisfied.
291       ver:
292               The required version of the dependency, in the format:
293               "OPERATOR VERSION", or "".  Where, OPERATOR is a relational
294               operator (=, >, etc), and version is a plain version,
295               without release number (example: 1.2.3, not 1.2.3-1)
296
297    <Exceptions>
298       None.
299
300    <Side Effects>
301       None.
302
303    <Returns>
304       Returns a list of package information dictionaries.
305    """
306    # check params
307    arizonageneral.check_type_simple(name, "name", str, "stork.find_satisfying_packages")
308    arizonageneral.check_type_simple(ver, "ver", str, "stork.find_satisfying_packages")
309
310    arizonareport.send_out(4, "[DEBUG] storkdependency.find_statisfying_packages " +
311                              "name = " + name + "ver = " + ver);
312
313    # find packages that have the desired package name in their provides
314    # field (this means they satisfy the dependency)
315    criteria_dict = {}
316    criteria_dict['provides'] = name
317    mylist = storkpackagelist.find_packages(criteria_dict)
318    criteria_dict['provides'] = name + " =*"
319    mylist += storkpackagelist.find_packages(criteria_dict)
320    retlist = []
321
322    arizonareport.send_out(4, "[DEBUG] storkdependency.find_satisfying_packages mylist = " +
323        str([(pack['name'], pack['version'], pack['release']) for pack in mylist]));
324
325    # now check that the version is adequate
326    for package in mylist:
327       for provided in package['provides']:
328          if this_satisfies(name, ver, provided):
329             retlist.append(package)
330    return retlist
331
332
333
334
335
336 def find_file_satisfying_packages(filename):
337    """
338    <Purpose>
339       Searches for packages meeting the filename requirement.
340
341    <Arguments>
342       filename:
343               The single file dependency needing to be satisfied.
344
345    <Exceptions>
346       None.
347
348    <Side Effects>
349       None.
350
351    <Returns>
352       Returns a list of package information dictionaries.
353    """
354    # check params
355    arizonageneral.check_type_simple(filename, "filename", str, "stork.find_file_satisfying_packages")
356
357    # find packages that have the desired filename in their files
358    # field (this means they satisfy the dependency)
359    criteria_dict = {}
360    criteria_dict['files'] = filename
361    packages = storkpackagelist.find_packages(criteria_dict)
362
363    arizonareport.send_out(4, "[DEBUG] storkdependency.find_file_satisfying_packages packages = " +
364        str([(pack['name'], pack['version'], pack['release']) for pack in packages]));
365
366    return packages
367
368
369
370
371
372 def find_trusted_satisfying_packages(name, ver, tags, ignore_mantags=False):
373    """
374    <Purpose>
375       Searches for packages meeting the name and version requirements that
376       are also trusted by the user.
377
378    <Arguments>
379       name:
380               The single dependency needing to be satisfied.
381       ver:
382               The required version of the dependency, in the format:
383               "OPERATOR VERSION", or "".  Where, OPERATOR is a relational
384               operator (=, >, etc), and version is a plain version,
385               without release number (example: 1.2.3, not 1.2.3-1)
386       tags:
387               A comma-delimited string of tags.
388
389    <Exceptions>
390       None.
391
392    <Side Effects>
393       None.
394
395    <Returns>
396       Returns a list of package information dictionaries.
397    """
398    # check params
399    arizonageneral.check_type_simple(name, "name", str, "stork.find_trusted_satisfying_packages")
400    arizonageneral.check_type_simple(ver, "ver", str, "stork.find_trusted_satisfying_packages")
401
402    # Find a list of possible packages to fulfill this requirement
403    if name[0] == "/":
404       # file dependency
405       pkg_list = find_file_satisfying_packages(name)
406    else:
407       # package dependency
408       pkg_list = find_satisfying_packages(name, ver)
409
410    # remove duplicate entries
411    pkg_list = arizonageneral.uniq(pkg_list)
412
413    # remove any invalid packages from list
414    pkg_list = [pkg for pkg in pkg_list if ravenlib.package.storkpackage.package_metadata_dict_validate(pkg)]
415
416    arizonareport.send_out(4, "[DEBUG] storkdependency.find_trusted_satisfying_packages pkg_list = " +
417        str([(pack['name'], pack['version'], pack['release']) for pack in pkg_list]));
418
419    # create a list of allowed (trusted) packages
420    trusted_pkg_list = []
421
422    # if we've disabled trusted packages data, then use the above (unsafe!)
423    # otherwise, filter out packages that are untrusted or unwanted
424    if arizonaconfig.get_option("disable_tpf"):
425       trusted_pkg_list = pkt_list[:]
426    else:
427       (allow_list, deny_list, unspecified_list) = storktpqualify.qualify_packages(pkg_list, tags, ignore_mantags)
428
429       # we only care about the list of allowed items
430       trusted_pkg_list = allow_list[:]
431
432       for item in deny_list:
433          arizonareport.send_out(2, "   package " + item["filename"] + " was denied by a trusted packages file")
434
435       for item in unspecified_list:
436          arizonareport.send_out(2, "   package " + item["filename"] + " ignored because it does not match any tp files")
437
438    # return the list of package dictionaries
439    trusted_pkg_list = arizonageneral.uniq(trusted_pkg_list)
440
441    sorted_trusted_pkg_list = storkpackagesort.sort_packages(trusted_pkg_list)
442
443    return sorted_trusted_pkg_list
444
445
446
447
448 def find_trusted_satisfying_packages_old(name, ver, tags, ignore_mantags=False):
449    """
450    <Purpose>
451       Searches for packages meeting the name and version requirements that
452       are also trusted by the user.
453
454    <Arguments>
455       name:
456               The single dependency needing to be satisfied.
457       ver:
458               The required version of the dependency, in the format:
459               "OPERATOR VERSION", or "".  Where, OPERATOR is a relational
460               operator (=, >, etc), and version is a plain version,
461               without release number (example: 1.2.3, not 1.2.3-1)
462       tags:
463               A comma-delimited string of tags.
464
465    <Exceptions>
466       None.
467
468    <Side Effects>
469       None.
470
471    <Returns>
472       Returns a list of package information dictionaries.
473    """
474    # check params
475    arizonageneral.check_type_simple(name, "name", str, "stork.find_trusted_satisfying_packages")
476    arizonageneral.check_type_simple(ver, "ver", str, "stork.find_trusted_satisfying_packages")
477
478    # Find a list of possible packages to fulfill this requirement
479    if name[0] == "/":
480       # file dependency
481       pkg_list = find_file_satisfying_packages(name)
482    else:
483       # package dependency
484       pkg_list = find_satisfying_packages(name, ver)
485
486    # remove duplicate entries
487    pkg_list = arizonageneral.uniq(pkg_list)
488
489    # remove any invalid packages from list
490    pkg_list = [pkg for pkg in pkg_list if ravenlib.package.storkpackage.package_metadata_dict_validate(pkg)]
491
492    arizonareport.send_out(4, "[DEBUG] storkdependency.find_trusted_satisfying_packages pkg_list = " +
493        str([(pack['name'], pack['version'], pack['release']) for pack in pkg_list]));
494
495    # create a list of allowed (trusted) packages
496    trusted_pkg_list = []
497
498    # if we've disabled trusted packages data, then use the above (unsafe!)
499    # otherwise, filter out packages that are untrusted or unwanted
500    if arizonaconfig.get_option("disable_tpf"):
501       # Use what we were given... unsafe, but assume the user knows best
502       for package in pkg_list:
503          # append package dictionary, as is
504          trusted_pkg_list.append(package)
505    else:
506       # Form a list of (filename, metahash, dictionary) tuples that rank_packages will use
507       rank_packages_list = []
508       for package in pkg_list:
509          rank_packages_list.append((package["filename"], package["_metadatahash"], package))
510
511       # Clobber/rank packages based upon trust and version information
512       (allow_list, deny_list, unspecified_list) = \
513          storktprank.rank_packages(rank_packages_list, tags, ignore_mantags)
514
515       # a list of items that we don't want to issue warnings about.
516       do_not_warn_list = []
517
518       # we only care about the list of allowed items (element 0)
519       for item in allow_list:
520          # allowed is a tuple: (filename, metahash, dictionary, tpentry) same as we
521          # passed in above.  So, package[0]=filename, package[1]=metahash,
522          # package[2]=package dictionary
523          # we don't need the separate filename or metahash anymore
524          trusted_pkg_list.append(item[2])
525          do_not_warn_list.append(item[2])
526
527       for item in deny_list:
528          if not item[0] in do_not_warn_list:
529             arizonareport.send_out(2, "   package " + item[0] + " was denied by a trusted packages file")
530             do_not_warn_list.append(item[0])
531
532       for item in unspecified_list:
533          if not item[0] in do_not_warn_list:
534             arizonareport.send_out(2, "   package " + item[0] + " ignored because it does not match any tp files")
535             do_not_warn_list.append(item[0])
536
537    # return the list of package dictionaries
538    return arizonageneral.uniq(trusted_pkg_list)
539
540
541
542
543 def split_pack_name(pack):
544    """
545    <Purpose>
546       Splits a package name of the form packOPver, pack OPver, or pack OP ver
547       into the package name (pack) and the op+version (ver)
548    <Returns>
549       A tuple (name, ver, tags)
550    """
551
552    # check params
553    arizonageneral.check_type_simple(pack, "pack", str, "storkdependency.split_pack_name")
554
555    # find relational operators, if any
556    pos = pack.find(">") # also handles >=
557    if pos == -1:
558       pos = pack.find("<") # also handles <=
559       if pos == -1:
560          pos = pack.find("=")
561
562    # add the package to the list of packages that need to be installed
563    if pos == -1:
564       # package
565       name = pack
566       ver = ""
567    else:
568       # package and version
569       name = pack[:pos].rstrip()
570       ver = pack[pos:]
571
572    # Depending on whether the user did 'pack = ver # tag' or 'pack # tag = ver',
573    # the tags could be in either 'name', or 'ver' at this point, so check them
574    # both.
575       
576    tags = ""
577    pos = name.find("#")
578    if pos != -1:
579       tags = name[pos+1:].lstrip()
580       name = name[:pos].rstrip()
581    else:
582       pos = ver.find("#")
583       if pos != -1:
584           tags = ver[pos+1:].lstrip()
585           ver = ver[:pos].rstrip()
586
587    return (name, ver, tags)
588
589    
590
591
592 def get_installed_by_name(pack):
593     """
594     <Purpose>
595        Given a package and optional relop and version (nameOPver), see what
596        packages satisfy the version requirements. Packages are checked based
597        on name and version number, not provided dependencies.
598     <Returns>
599        A tuple (sat_vers, unsat_vers), where sat_vers is a list of packages
600        that satisfy the version requirement, and unsat_vers is a list of 
601        packags (of the same name) that do not satisfy the version requirement.
602     """   
603
604     # check params
605     arizonageneral.check_type_simple(pack, "pack", str, "storkdependency.get_installed_by_name")
606    
607     (name, ver, tags) = split_pack_name(pack)
608     
609     cur_versions = ravenlib.package.storkpackage.get_installed_versions([name])
610
611     unsatisfying_versions = []
612     satisfying_versions = []
613
614     for cur in cur_versions:
615         if cur != None:
616             # cur will be of the format "name = ver". we want "name-ver"
617             packname = cur;
618             if packname.find(" = "):
619                 packname = packname.replace(" = ", "-")
620                 
621             if this_satisfies(name, ver, cur):
622                 satisfying_versions.append(packname)
623             else:
624                 unsatisfying_versions.append(packname)
625
626     if satisfying_versions or unsatisfying_versions:
627         arizonareport.send_out(3, "[INFO] pack " + str(pack) +
628                                   " has installed satisfying versions " + str(satisfying_versions) +
629                                   " and unsatisfying versions " + str(unsatisfying_versions)) 
630
631     return (satisfying_versions, unsatisfying_versions)
632
633
634
635 def remove_version_numbers(dep_list):
636     """
637     <Purpose>
638        Remove version numbers from dependencies in a list
639     <Returns>
640        A list of dependencies with the version numbers removed
641     """  
642     
643     # check params
644     arizonageneral.check_type_stringlist(dep_list, "dep_list", "storkdependency.remove_version_numbers")
645     
646     dep_list_new = []
647     for dep in dep_list:
648        pos = dep.find('=')
649        if pos != -1:
650            dep = dep[:pos].rstrip()
651        dep_list_new.append(dep)
652
653     return dep_list_new
654
655         
656
657 def get_installed_by_provides(dep_list):
658     """
659     <Purpose>
660        Given a list of dependencies, return the packages that provide those
661        dependencies.
662     <Returns>
663        A list of packages that provide the dependencies
664     """   
665
666     # check params
667     arizonageneral.check_type_stringlist(dep_list, "dep_list", "storkdependency.get_installed_by_provides")
668
669     #dep_list_orig = dep_list
670
671     # remove any version numbers from the dep_list.
672     dep_list = remove_version_numbers(dep_list)
673    
674     (unmet_list, dep_list) = installed_satisfy_list(dep_list, [], True)
675
676     #print "get_installed_by_provides("+str(dep_list_orig)+") = "+str(dep_list)
677
678     return dep_list
679
680
681
682 def get_reverse_dep(check_list, remove_list, install_list):
683     """
684     <Purpose>
685        Given a list of packages that are currently installed, see what existing
686        packages depend on those. Optionally, a list of packages that are to
687        be installed may be provided, and this function will compute the packages
688        that depend on 'remove_list', but are not satisfied by 'install_list'
689     <Arguments>
690        check_list:
691               A list of packages whose dependencies we wish to check.
692        remove_list:
693               A list of existing packages that are installed that we are
694               intending to remove. This list contains package names.
695        install_list:
696               [optional] A list of new packages that we intend to install 
697               (possibly replacing some of those packages in remove_list). This
698               list contains package dictionaries.
699     <Returns>
700        A list of packages that will be broken if the packages are removed.
701     """
702
703     # check params
704     arizonageneral.check_type_stringlist(check_list, "check_list", "storkdependency.get_referse_dep")
705     arizonageneral.check_type_stringlist(remove_list, "remove_list", "storkdependency.get_reverse_dep")
706
707     arizonareport.send_out(4, "[DEBUG] get_reverse_dep check_list=" + str(check_list))
708     arizonareport.send_out(4, "[DEBUG] remove_list=" + str(remove_list))
709
710     # install_list can either be None or a list of package dicts.
711     if install_list:
712        arizonageneral.check_type_simple(install_list, "install_list", list, "storkdependency.get_reverse_dep")
713        arizonareport.send_out(4, "[DEBUG] install_list = " + str([pack['name']+'-'+pack['version'] for pack in install_list]))
714
715     # build up a list of what is provided by the packages that we want to
716     # check
717     provides_list = ravenlib.package.storkpackage.get_installedpackages_provide(check_list)
718
719     provides_list = arizonageneral.uniq(provides_list)
720
721     # generate a list of dependencies that will be provided by the packages in
722     # the install_list.
723     replace_list = []
724     if install_list != None:
725         for pack in install_list:
726            if pack.get('provides', None):
727                replace_list += pack['provides']
728         replace_list = arizonageneral.uniq(replace_list)
729
730     arizonareport.send_out(4, "[DEBUG] replace_list="+str(replace_list))
731     arizonareport.send_out(4, "[DEBUG] provides_list="+str(provides_list))
732
733     # get a list of the packages that depend on the packages we intend to
734     # remove. We have to do this without version numbers because
735     # 'rpm -q --whatrequires' does not support version numbers. We'll have to
736     # recheck our results against version numbers later.
737     requires_list = ravenlib.package.storkpackage.get_installedpackages_requiring(
738                                       remove_version_numbers(provides_list))
739
740     # remove the packages that we're deleting from the requires list
741     # this also takes care of packages that depend on themselves
742     for pack in remove_list:
743         while pack in requires_list:
744             requires_list.remove(pack)
745
746     arizonareport.send_out(4, "[DEBUG] requires_list="+str(requires_list))
747
748     #return requires_list
749
750     # TODO: smbaker: more tests of the following...
751
752     # now we match the version numbers...
753     broken_list = []
754     for pack in requires_list:
755         # get the dependencies that are required by the package.
756         requires = ravenlib.package.storkpackage.get_installedpackages_requires([pack])
757         arizonareport.send_out(4, "[DEBUG] pack "+str(pack)+ " requires " +str(requires))
758
759         for dep in requires:
760             (depname, depver, deptags) = split_pack_name(dep)
761             arizonareport.send_out(4, "[DEBUG]   checking "+str((depname, depver)))
762
763             # see if the dependency matches one of the ones we are removing
764             if this_satisfies_list(depname, depver, provides_list):
765                 arizonareport.send_out(4, "[DEBUG]     "+str((depname, depver))+" matched by provides_list")
766
767                 # see if the dependency matches on of the ones that we will be
768                 # adding.
769                 if not this_satisfies_list(depname, depver, replace_list):
770                     arizonareport.send_out(4, "[DEBUG]        and not matched by replace_list")
771                     broken_list.append(pack)
772                 else:
773                     arizonareport.send_out(4, "[DEBUG]        *** and matched by replace_list")
774             else:
775                 arizonareport.send_out(4, "[DEBUG]     "+str((depname, depver))+" not matched by provides_list")
776
777     arizonareport.send_out(4, "[DEBUG] broken_list="+str(broken_list))
778
779     # what we have left is the packages that will be broken if we remove the
780     # packages in remove_list (and install the packages in install_list)
781
782     return broken_list
783
784
785
786
787         
788 def installed_satisfy_list(dep_list, upgrade_pack=[], reportInstalled=False):
789    """
790    <Purpose>
791       Given a list of dependencies, decides which dependencies are met by
792       installed packages, and returns a filtered list containing only the 
793       unmet dependencies.
794
795    <Arguments>
796       dep_list:
797               A list of dependencies in one of the following forms:
798                 name
799                 name OP ver
800                 nameOPver  
801               Where OP is one of: = < > <= >=
802
803       upgrade_pack:
804               (Default: [])
805               List of packages scheduled for an upgrade.
806       
807       reportInstalled:        
808               (Default: False)
809               If True, returns a tuple ([unmet], [satisfying_packages])
810               Where unmet is the list of unmet dependencies, and 
811               satisfying_packages is a list of installed packages that 
812               satisfied at least one dependency.
813    
814    <Exceptions>
815       None.
816
817    <Side Effects>
818       None.
819
820    <Returns>
821       Returns a either a list of unmet dependencies or a tuple containing 
822       a list of unmet dependencies, and a list of installed packages that
823       met at least one dependency.
824    """
825    # check params
826    arizonageneral.check_type_stringlist(dep_list, "dep_list", "stork.installed_satisfy_list")
827    arizonageneral.check_type_stringlist(upgrade_pack, "upgrade_pack", "installed_satisfy")
828
829    # remove duplicate entries
830    temp_list = arizonageneral.uniq(dep_list)
831    #arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, unique dependencies: " + str(temp_list))
832
833    # separate out file dependencies, and build some lists we'll need later
834    name_list = []
835    dep_list = []
836    filedep_list = []
837    for item in temp_list:
838       # if this is a file dependency, see if it is already on the disk
839       # if not, there are two situations: 
840       #   1) the file was deleted
841       #   2) the file dependency has not been met
842       # TODO? for now, we assume that 1) is very rare, so we assume that
843       # any remaining file dependencies are not met by installed packages
844       item = item.strip()
845       if item[0] == "/":
846          if not os.path.exists(item):
847             filedep_list.append(item)
848       else:
849          (name, ver, tags) = split_pack_name(item)
850          name_list.append(name)   
851          dep_list.append((name, ver, item))
852          
853    arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, filedep_list: " + str(filedep_list))
854    arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, dep_list: " + str(dep_list))
855    arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, name_list: " + str(name_list)) 
856
857    # get a list of packages that provide the dependencies
858    try:
859       candidate_list = ravenlib.package.storkpackage.get_installedpackages_fulfilling(name_list)
860    except TypeError: #changed from a general exception
861       exc_info = sys.exc_info()
862       e = exc_info[1]
863       try:
864          message = e.message
865       except:
866          raise exc_info[0], exc_info[1], exc_info[2]
867       arizonareport.send_error(0, "An error occurred while finding packages to fulfill the `" + \
868                                   ", ".join(name_list) + "' dependencies:\n" + message)
869       arizonareport.send_error(0, "Aborting installation.")
870       sys.exit(1)
871
872    arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, candidate_list: " + str(candidate_list))
873
874    # Remove from consideration any installed packages that are scheduled
875    # for an upgrade
876    for item in candidate_list:
877       if item in upgrade_pack:
878          candidate_list.remove(item)
879
880    # now, get a list of what dependencies these packages provide.  We have
881    # to do this because it is possible that dependencies weren't provided
882    # by the above packages, and we need to figure out which dependencies
883    # those are.  Also, some packages might not be of the required version.
884    try:
885       if reportInstalled:
886          # this is slower, but we need to keep track of which candidate
887          # package satisfied which dependency
888          provide_list = []
889          for candidate in candidate_list:
890             temp_list = ravenlib.package.storkpackage.get_installedpackages_provide([candidate])
891             for item in temp_list:
892                provide_list.append((item, candidate))
893          satisfying_packages = []
894       else:
895          # faster: don't care which package satisfied the dependency as
896          # long as one of them did
897          provide_list = ravenlib.package.storkpackage.get_installedpackages_provide(candidate_list)
898          arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, provide_list: " + str(provide_list))
899    except (TypeError, IOError): #changed from a general exception
900       exc_info = sys.exc_info()
901       e = exc_info[1]
902       try:
903          message = e.message
904       except:
905          raise exc_info[0], exc_info[1], exc_info[2]
906       arizonareport.send_error(0, "An error occurred while finding what the packages `" + \
907                                   ", ".join(candidate_list) + "' provide:\n" + message)
908       arizonareport.send_error(0, "Aborting installation.")
909       sys.exit(1)
910
911    # go through the above provides list and remove provided dependencies
912    #arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, provide_list: " + str(provide_list))
913    unsat_dep_list = []
914    for i, dep in enumerate(dep_list):
915       satisfied = None
916       for item in provide_list:
917          if reportInstalled:
918             if this_satisfies(dep[0], dep[1], item[0]):
919                satisfying_packages.append(item[1])
920                satisfied = item
921                break
922          else:
923 #            if dep[0].startswith("perl(File::Path") and item.startswith("perl(File::Path"):
924 #               print "dep=" + str(dep) + " item=" + str(item) + " ts=" + str(this_satisfies(dep[0], dep[1], item))
925             if this_satisfies(dep[0], dep[1], item):
926                #arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, satisfied: " + dep[0] + ", " + dep[1] + ", " + item)
927                satisfied = item
928                break
929       if satisfied:
930           arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, satisfied: " + dep[0] + ", " + dep[1] + " with " + satisfied)
931       else:
932           arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, did not satisfy: " + dep[0] + ", " + dep[1])
933           unsat_dep_list.append(dep)
934
935    arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, unsat_dep_list=" + str(unsat_dep_list))
936
937    missing_list = []
938    for dep in unsat_dep_list:                    
939       missing_list.append(dep[2])
940
941    arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, filedep_list: " + str(filedep_list))
942    arizonareport.send_out(4, "[DEBUG] installed_satisfy_list, missing_list: " + str(missing_list))
943
944    # add on file dependencies and return the combined list of unmet deps
945    missing_list = filedep_list + missing_list
946
947    # return the requested information
948    if reportInstalled:
949       return (missing_list, arizonageneral.uniq(satisfying_packages))
950    else:
951       return missing_list
952       
953
954
955
956
957 glo_internal_deps = []
958 def find_unsat_dependencies(package):
959    """
960    <Purpose>
961       Given a package dictionary entry, returns a list of unsatisfied
962       dependencies.
963    
964    <Arguments>
965       package:
966                 Package dictionary entry.
967    
968    <Exceptions>
969       None.
970
971    <Side Effects>
972       None.
973
974    <Returns>             
975       Returns a list of what dependencies of a package aren't satisfied, 
976       in other words, returns a list of unmet dependencies.
977    """
978    global glo_internal_deps
979
980    # check params
981    arizonageneral.check_type_simple(package, "package", dict, "stork.find_unsat_dependencies")
982    
983    # build a list of raw dependencies of this package
984    dep_list = package['requires']
985    #arizonareport.send_out(4, "[DEBUG] find_unsat_dependencies, requires: " + str(dep_list))
986
987    # filter out the met dependencies (some packages are installed)
988    dep_list = installed_satisfy_list(dep_list)
989    #arizonareport.send_out(4, "[DEBUG] find_unsat_dependencies, filtered installed: " + str(dep_list)) 
990    
991    # remove any dependencies fulfilled by the package managers themselves
992    ret_list = []
993    for dep in dep_list:
994       # split up dependency into name and ver parts
995       fields = dep.split()
996       name = fields[0]
997       if len(fields) > 1:
998          ver = " ".join(fields[1:])
999       else:
1000          ver = ""
1001       
1002       # see if any of the internal dependencies match
1003       for intdep in ravenlib.package.storkpackage.get_packagemanagers_provide():
1004          if this_satisfies(name, ver, intdep):
1005             break
1006       else:
1007          # nope, this must be a real dependency
1008          ret_list.append(dep)
1009    #arizonareport.send_out(4, "[DEBUG] find_unsat_dependencies, filtered internal: " + str(ret_list))
1010
1011    return arizonageneral.uniq(ret_list)
1012
1013
1014
1015 glo_pkgver_satisfied = []
1016 glo_filemeta_satisfied = []
1017 glo_cannot_satisfy = []
1018 def satisfy(pkg, ver="", tags="", upgrade=False, trace=[], ignore_mantags=False):
1019    """
1020    <Purpose>
1021       This returns a list of every package needed to satisfy all
1022       installation dependencies of a given version of a package, and all
1023       installation dependencies of the needed packages.
1024
1025    <Arguments>
1026        pkg:
1027            the name of the package, minus version number.
1028        ver:
1029            the version number of the desired package. May contain relational
1030            operators.
1031        upgrade:
1032            True if upgrades are allowed.
1033            Note: At this time, recursive upgrading is not supported. Satisfy
1034               will always pass 'False' to recursive calls to satisfy.
1035        trace:
1036            Used to filter out circular dependencies.
1037
1038    TODO fix comment
1039    """
1040    global glo_pkgver_satisfied
1041    global glo_filemeta_satisfied
1042    global glo_cannot_satisfy
1043
1044    # check params
1045    arizonageneral.check_type_simple(pkg, "pkg", str, "stork.satisfy")
1046    arizonageneral.check_type_simple(ver, "ver", str, "stork.satisfy")
1047    arizonageneral.check_type_stringlist(trace, "trace", "stork.satisfy")
1048
1049    pkgver = (pkg, ver)
1050    if pkgver in glo_pkgver_satisfied:
1051       return []
1052
1053    # tell the user which package we're trying to satisfy
1054    arizonareport.send_out(2, (arizonageneral.recur_depth("satisfy") - 1) * "   " + \
1055                              "Attempting to satisfy " + pkg + " " + ver)
1056
1057    # Find a list of trusted packages that fulfill the immediately obvious
1058    # dependency requirements (not recursive, so these answers are verified
1059    # below)
1060    trusted_pkg_list = find_trusted_satisfying_packages(pkg, ver, tags, ignore_mantags)
1061
1062    arizonareport.send_out(4, "[DEBUG] storkdependency.satisfy trusted_pkg_list = " +
1063       str([(pack['name'], pack['version'], pack['release']) for pack in trusted_pkg_list]));
1064
1065    # Now there is a list of packages that can satisfy the requirement,
1066    # however some of these packages might not be satisfiable themselves.
1067    # Go through the candidates in order and try to satisfy them:
1068    for package in trusted_pkg_list:
1069       # build package id from package filename and metahash (assumed to be unique)
1070       pack_id = package['name'] + "_" + package['_metadatahash']
1071
1072       # check for circular package dependencies
1073       if pack_id in trace:
1074          if not pkgver in glo_pkgver_satisfied:
1075             glo_pkgver_satisfied.append(pkgver)
1076          arizonareport.send_out(2, (arizonageneral.recur_depth("satisfy") - 1) * "   " + \
1077                                    "Satisfied " + pkg + " by " + package['filename'])
1078          return []
1079       trace.append(pack_id)
1080
1081       # if we've previously found that the candidate package cannot be
1082       # satisfied, then reject the package now before we waste time
1083       # rediscovering the fact
1084       if pack_id in glo_cannot_satisfy:
1085          continue
1086
1087       # if we've previously found that the candidate package is satisfied,
1088       # then accept the package right away.
1089       if pack_id in glo_filemeta_satisfied:
1090          if not pkgver in glo_pkgver_satisfied:
1091             glo_pkgver_satisfied.append(pkgver)
1092          return []
1093
1094       # keep the user informed
1095       arizonareport.send_out(2, (arizonageneral.recur_depth("satisfy") - 1) * "   " + \
1096                                 "Trying " + package['filename'] + \
1097                                 " to satisfy " + pkg + " " + ver)
1098
1099       # find out what unmet dependencies (if any) this candidate has
1100       dep_list = find_unsat_dependencies(package)
1101
1102       # find what existing packages will conflict with this package. There are
1103       # two different ways we could do this:
1104       #   a) a package conflicts if the name is identical
1105       #   b) a package conflicts if it provides the same dependencies
1106       #   or... c) a packages conflicts if contains the same files
1107       # 'c' is probably the right one (it's what RPM does?)
1108       # 'b' doesn't appear to be correct
1109       # ... so let's do 'a' for now.
1110       # TODO: implement 'c'? research what yum/apt do?
1111       
1112       # conflict_list = get_installed_by_provides(package['provides'])  # 'b'
1113       
1114       (conflict_list, nothing) = get_installed_by_name(package['name'])  # 'a'
1115
1116       # see what conflicts we have with existing installed packages
1117       if conflict_list:
1118           if upgrade:
1119               # upgrade: we'll end up removing the conflicts
1120               package['_upgrade_conflicts'] = conflict_list
1121               arizonareport.send_out(3, (arizonageneral.recur_depth("satisfy") - 1) * 
1122                                         "   " + "Upgrade of package "+package['filename'] + 
1123                                         " will replace package " + str(conflict_list))
1124           else:
1125               # install: we cannot remove a conflict, so we cannot use this
1126               # package
1127               arizonareport.send_out(1, (arizonageneral.recur_depth("satisfy") - 1) * 
1128                                         "   " + "Cannot use package "+package['filename'] + 
1129                                         " because version "+str(conflict_list)+" is already installed")
1130               glo_cannot_satisfy.append(pack_id)
1131               continue
1132
1133       # tell extra verbose user which dependencies need to be met
1134       if dep_list:
1135          arizonareport.send_out(3, (arizonageneral.recur_depth("satisfy") - 1) * \
1136                                    "   " + pkg + " has unmet dependencies on: " + \
1137                                    ", ".join(dep_list))
1138
1139       # go through each dependency and try to satisfy it
1140       need_to_install = []
1141       for dep in dep_list:
1142          # recursively call satisfy on this dependency.  base case occurs
1143          # when a package either has no unmet dependencies (see the "else"
1144          # part of this for loop), or when a package cannot be satisfied.
1145
1146          # TODO handle OR dependencies (only one is needed): a | b | ...
1147
1148          # split dependency string into package name and version
1149          dep_pieces = dep.split(None, 1)
1150          dep_pkg = dep_pieces[0]
1151          if len(dep_pieces) == 2:
1152             dep_ver = dep_pieces[1]
1153          else:
1154             dep_ver = ""
1155
1156          # skip file dependency if it is satisfied by the package itself
1157          if dep[0] == "/" and (dep in package['files']):
1158             continue
1159
1160          # skip dependency if it is satisfied by the package itself
1161          # go through provides candidates to try to find a match
1162          skip = False
1163          for candidate in package['provides']:
1164             if this_satisfies(dep_pkg, dep_ver, candidate):
1165                skip = True
1166                break
1167          if skip:
1168             continue
1169
1170          # find a list of packages that need to be installed
1171          dep_needs_to_install = satisfy(dep_pkg, dep_ver, "",
1172                                         arizonaconfig.get_option("upgrade_deps"),
1173                                         trace,
1174                                         True)  # ignore mandataory tags on deps
1175
1176          # could the package be satisfied?  (if not, cur_ans == None)
1177          if dep_needs_to_install == None:
1178             # no.. remember this package so we never want to try it again
1179             glo_cannot_satisfy.append(pack_id)
1180
1181             # let user know we took a wrong turn
1182             # TODO: should we combine these two print statements?
1183             arizonareport.send_out(1, (arizonageneral.recur_depth("satisfy") - 1) * \
1184                                       "   " + "Cannot satisfy dependency: " + \
1185                                       dep + " of " + package['filename'])
1186             arizonareport.send_out(1, (arizonageneral.recur_depth("satisfy") - 1) * \
1187                                       "   " + "Rejecting " + \
1188                                       package['filename'])
1189             if arizonaconfig.get_option("abort") and \
1190                  (arizonaconfig.get_option("abortdepth") == 0 or \
1191                  arizonaconfig.get_option("abortdepth") < \
1192                  arizonageneral.recur_depth("satisfy")):
1193                arizonareport.send_out(1, "Aborting because " + \
1194                                          package['filename'] + \
1195                                          " was rejected...")
1196                sys.exit(1)
1197             break
1198
1199          # dependency was satisfied
1200          for item in dep_needs_to_install:
1201             # remember this package, so we never need to check it again
1202             pack_id = item["filename"] + "_" + item["_metadatahash"]
1203
1204             # only add it to the list once
1205             if not pack_id in glo_filemeta_satisfied:
1206                glo_filemeta_satisfied.append(pack_id)
1207
1208             if not pkgver in glo_pkgver_satisfied:
1209                glo_pkgver_satisfied.append(pkgver)
1210
1211          # dependency was satisfied.. add whatever packages it needed to
1212          # a master list of needed packages
1213          need_to_install += dep_needs_to_install
1214       else:
1215          # Either the package had no unmet dependencies, or all of them
1216          # have tentatively been met (recursively).  So the package has
1217          # or can be satisfied.  (This is the base case)
1218          arizonareport.send_out(2, (arizonageneral.recur_depth("satisfy") - 1) * \
1219                                    "   " + "Satisfied " + pkg + \
1220                                    " by " + package['filename'])
1221          need_to_install.append(package)
1222          need_to_install = arizonageneral.uniq(need_to_install)
1223          return need_to_install
1224
1225       # reaches this comment if the package was rejected.. now tries the
1226       # next candidate package in trusted_pkg_list
1227    else:
1228       # went through every candidate package, but none could be satisfied.
1229       # cannot satisfy this pkg/ver dependency
1230       storklog.warn("Failed to satisfy " + pkg + " " + ver)
1231       arizonareport.send_out(2, (arizonageneral.recur_depth("satisfy") - 1) * "   " + \
1232                                 "Cannot satisfy " + pkg + " " + ver)
1233       return None