zeroinstall/injector/solver.py

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