zeroinstall/injector/solver.py

   1 """
   2 Chooses a set of components to make a running program.
   3 """
   4
   5 # Copyright (C) 2009, Thomas Leonard
   6 # See the README file for details, or visit http://0install.net.
   7
   8 from zeroinstall import _
   9 import os
  10 from logging import debug, warn, info
  11
  12 from zeroinstall.zerostore import BadDigest, NotStored
  13
  14 from zeroinstall.injector.arch import machine_groups
  15 from zeroinstall.injector import model
  16
  17 class Solver(object):
  18         """Chooses a set of implementations to satisfy the requirements of a program and its user.
  19         Typical use:
  20          1. Create a Solver object and configure it
  21          2. Call L{solve}.
  22          3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
  23          4. If it is 'ready' then you can download and run the chosen versions.
  24         @ivar selections: the chosen implementation of each interface
  25         @type selections: {L{model.Interface}: Implementation}
  26         @ivar feeds_used: the feeds which contributed to the choice in L{selections}
  27         @type feeds_used: set(str)
  28         @ivar record_details: whether to record information about unselected implementations
  29         @type record_details: {L{Interface}: [(L{Implementation}, str)]}
  30         @ivar details: extra information, if record_details mode was used
  31         @type details: {str: [(Implementation, comment)]}
  32         """
  33         __slots__ = ['selections', 'feeds_used', 'details', 'record_details', 'ready']
  34
  35         def __init__(self):
  36                 self.selections = self.feeds_used = self.details = None
  37                 self.record_details = False
  38                 self.ready = False
  39
  40         def solve(self, root_interface, arch):
  41                 """Get the best implementation of root_interface and all of its dependencies.
  42                 @param root_interface: the URI of the program to be solved
  43                 @type root_interface: str
  44                 @param arch: the desired target architecture
  45                 @type arch: L{arch.Architecture}
  46                 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
  47                 raise NotImplementedError("Abstract")
  48
  49 class DefaultSolver(Solver):
  50         """The standard (rather naive) Zero Install solver."""
  51         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
  52                 """
  53                 @param network_use: how much use to make of the network
  54                 @type network_use: L{model.network_levels}
  55                 @param iface_cache: a cache of feeds containing information about available versions
  56                 @type iface_cache: L{iface_cache.IfaceCache}
  57                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
  58                 @type stores: L{zerostore.Stores}
  59                 @param extra_restrictions: extra restrictions on the chosen implementations
  60                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
  61                 """
  62                 Solver.__init__(self)
  63                 self.network_use = network_use
  64                 self.iface_cache = iface_cache
  65                 self.stores = stores
  66                 self.help_with_testing = False
  67                 self.extra_restrictions = extra_restrictions or {}
  68
  69         def solve(self, root_interface, arch):
  70                 self.selections = {}
  71                 self.feeds_used = set()
  72                 self.details = self.record_details and {}
  73                 self._machine_group = None
  74
  75                 restrictions = {}
  76                 debug(_("Solve! root = %s"), root_interface)
  77                 def process(dep, arch):
  78                         ready = True
  79                         iface = self.iface_cache.get_interface(dep.interface)
  80
  81                         if iface in self.selections:
  82                                 debug("Interface requested twice; skipping second %s", iface)
  83                                 if dep.restrictions:
  84                                         warn("Interface requested twice; I've already chosen an implementation "
  85                                                 "of '%s' but there are more restrictions! Ignoring the second set.", iface)
  86                                 return ready
  87                         self.selections[iface] = None   # Avoid cycles
  88
  89                         assert iface not in restrictions
  90                         restrictions[iface] = dep.restrictions
  91
  92                         impl = get_best_implementation(iface, arch)
  93                         if impl:
  94                                 debug(_("Will use implementation %(implementation)s (version %(version)s)"), {'implementation': impl, 'version': impl.get_version()})
  95                                 self.selections[iface] = impl
  96                                 if self._machine_group is None and impl.machine and impl.machine != 'src':
  97                                         self._machine_group = machine_groups.get(impl.machine, 0)
  98                                         debug(_("Now restricted to architecture group %s"), self._machine_group)
  99                                 for d in impl.requires:
 100                                         debug(_("Considering dependency %s"), d)
 101                                         if not process(d, arch.child_arch):
 102                                                 ready = False
 103                         else:
 104                                 debug(_("No implementation chould be chosen yet"));
 105                                 ready = False
 106
 107                         return ready
 108
 109                 def get_best_implementation(iface, arch):
 110                         debug(_("get_best_implementation(%(interface)s), with feeds: %(feeds)s"), {'interface': iface, 'feeds': iface.feeds})
 111
 112                         iface_restrictions = restrictions.get(iface, [])
 113                         extra_restrictions = self.extra_restrictions.get(iface, None)
 114                         if extra_restrictions:
 115                                 # Don't modify original
 116                                 iface_restrictions = iface_restrictions + extra_restrictions
 117
 118                         impls = []
 119                         for f in usable_feeds(iface, arch):
 120                                 self.feeds_used.add(f)
 121                                 debug(_("Processing feed %s"), f)
 122
 123                                 try:
 124                                         feed = self.iface_cache.get_interface(f)._main_feed
 125                                         if not feed.last_modified: continue     # DummyFeed
 126                                         if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 127                                                 info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 128
 129                                         if feed.implementations:
 130                                                 impls.extend(feed.implementations.values())
 131                                 except Exception, ex:
 132                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': str(ex)})
 133
 134                         if not impls:
 135                                 info(_("Interface %s has no implementations!"), iface)
 136                                 return None
 137
 138                         if self.record_details:
 139                                 # In details mode, rank all the implementations and then choose the best
 140                                 impls.sort(lambda a, b: compare(iface, a, b, iface_restrictions, arch))
 141                                 best = impls[0]
 142                                 self.details[iface] = [(impl, get_unusable_reason(impl, iface_restrictions, arch)) for impl in impls]
 143                         else:
 144                                 # Otherwise, just choose the best without sorting
 145                                 best = impls[0]
 146                                 for x in impls[1:]:
 147                                         if compare(iface, x, best, iface_restrictions, arch) < 0:
 148                                                 best = x
 149                         unusable = get_unusable_reason(best, iface_restrictions, arch)
 150                         if unusable:
 151                                 info(_("Best implementation of %(interface)s is %(best)s, but unusable (%(unusable)s)"), {'interface': iface, 'best': best, 'unusable': unusable})
 152                                 return None
 153                         return best
 154
 155                 def compare(interface, b, a, iface_restrictions, arch):
 156                         """Compare a and b to see which would be chosen first.
 157                         @param interface: The interface we are trying to resolve, which may
 158                         not be the interface of a or b if they are from feeds.
 159                         @rtype: int"""
 160                         a_stab = a.get_stability()
 161                         b_stab = b.get_stability()
 162
 163                         # Usable ones come first
 164                         r = cmp(is_unusable(b, iface_restrictions, arch), is_unusable(a, iface_restrictions, arch))
 165                         if r: return r
 166
 167                         # Preferred versions come first
 168                         r = cmp(a_stab == model.preferred, b_stab == model.preferred)
 169                         if r: return r
 170
 171                         if self.network_use != model.network_full:
 172                                 r = cmp(get_cached(a), get_cached(b))
 173                                 if r: return r
 174
 175                         # Stability
 176                         stab_policy = interface.stability_policy
 177                         if not stab_policy:
 178                                 if self.help_with_testing: stab_policy = model.testing
 179                                 else: stab_policy = model.stable
 180
 181                         if a_stab >= stab_policy: a_stab = model.preferred
 182                         if b_stab >= stab_policy: b_stab = model.preferred
 183
 184                         r = cmp(a_stab, b_stab)
 185                         if r: return r
 186
 187                         # Newer versions come before older ones
 188                         r = cmp(a.version, b.version)
 189                         if r: return r
 190
 191                         # Get best OS
 192                         r = cmp(arch.os_ranks.get(b.os, None),
 193                                 arch.os_ranks.get(a.os, None))
 194                         if r: return r
 195
 196                         # Get best machine
 197                         r = cmp(arch.machine_ranks.get(b.machine, None),
 198                                 arch.machine_ranks.get(a.machine, None))
 199                         if r: return r
 200
 201                         # Slightly prefer cached versions
 202                         if self.network_use == model.network_full:
 203                                 r = cmp(get_cached(a), get_cached(b))
 204                                 if r: return r
 205
 206                         return cmp(a.id, b.id)
 207
 208                 def usable_feeds(iface, arch):
 209                         """Return all feeds for iface that support arch.
 210                         @rtype: generator(ZeroInstallFeed)"""
 211                         yield iface.uri
 212
 213                         for f in iface.feeds:
 214                                 # Note: when searching for src, None is not in machine_ranks
 215                                 if f.os in arch.os_ranks and \
 216                                    (f.machine is None or f.machine in arch.machine_ranks):
 217                                         yield f.uri
 218                                 else:
 219                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 220                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 221
 222                 def is_unusable(impl, restrictions, arch):
 223                         """@return: whether this implementation is unusable.
 224                         @rtype: bool"""
 225                         return get_unusable_reason(impl, restrictions, arch) != None
 226
 227                 def get_unusable_reason(impl, restrictions, arch):
 228                         """
 229                         @param impl: Implementation to test.
 230                         @type restrictions: [L{model.Restriction}]
 231                         @return: The reason why this impl is unusable, or None if it's OK.
 232                         @rtype: str
 233                         @note: The restrictions are for the interface being requested, not the interface
 234                         of the implementation; they may be different when feeds are being used."""
 235                         machine = impl.machine
 236                         if machine and self._machine_group is not None:
 237                                 if machine_groups.get(machine, 0) != self._machine_group:
 238                                         return _("Incompatible with another selection from a different architecture group")
 239
 240                         for r in restrictions:
 241                                 if not r.meets_restriction(impl):
 242                                         return _("Incompatible with another selected implementation")
 243                         stability = impl.get_stability()
 244                         if stability <= model.buggy:
 245                                 return stability.name
 246                         if self.network_use == model.network_offline and not get_cached(impl):
 247                                 return _("Not cached and we are off-line")
 248                         if impl.os not in arch.os_ranks:
 249                                 return _("Unsupported OS")
 250                         # When looking for source code, we need to known if we're
 251                         # looking at an implementation of the root interface, even if
 252                         # it's from a feed, hence the sneaky restrictions identity check.
 253                         if machine not in arch.machine_ranks:
 254                                 if machine == 'src':
 255                                         return _("Source code")
 256                                 return _("Unsupported machine type")
 257                         return None
 258
 259                 def get_cached(impl):
 260                         """Check whether an implementation is available locally.
 261                         @type impl: model.Implementation
 262                         @rtype: bool
 263                         """
 264                         if isinstance(impl, model.DistributionImplementation):
 265                                 return impl.installed
 266                         if impl.id.startswith('/'):
 267                                 return os.path.exists(impl.id)
 268                         else:
 269                                 try:
 270                                         path = self.stores.lookup(impl.id)
 271                                         assert path
 272                                         return True
 273                                 except BadDigest:
 274                                         return False
 275                                 except NotStored:
 276                                         return False
 277
 278                 self.ready = process(model.InterfaceDependency(root_interface), arch)