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, tempfile, subprocess
  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 requires: the selected dependencies for each chosen version
  27         @type requires: {L{model.Interface}: [L{model.Dependency}]}
  28         @ivar feeds_used: the feeds which contributed to the choice in L{selections}
  29         @type feeds_used: set(str)
  30         @ivar record_details: whether to record information about unselected implementations
  31         @type record_details: {L{Interface}: [(L{Implementation}, str)]}
  32         @ivar details: extra information, if record_details mode was used
  33         @type details: {str: [(Implementation, comment)]}
  34         """
  35         __slots__ = ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
  36
  37         def __init__(self):
  38                 self.selections = self.requires = self.feeds_used = self.details = None
  39                 self.record_details = False
  40                 self.ready = False
  41
  42         def solve(self, root_interface, arch):
  43                 """Get the best implementation of root_interface and all of its dependencies.
  44                 @param root_interface: the URI of the program to be solved
  45                 @type root_interface: str
  46                 @param arch: the desired target architecture
  47                 @type arch: L{arch.Architecture}
  48                 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
  49                 raise NotImplementedError("Abstract")
  50
  51 class PBSolver(Solver):
  52         """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them."""
  53         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
  54                 """
  55                 @param network_use: how much use to make of the network
  56                 @type network_use: L{model.network_levels}
  57                 @param iface_cache: a cache of feeds containing information about available versions
  58                 @type iface_cache: L{iface_cache.IfaceCache}
  59                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
  60                 @type stores: L{zerostore.Stores}
  61                 @param extra_restrictions: extra restrictions on the chosen implementations
  62                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
  63                 """
  64                 Solver.__init__(self)
  65                 self.network_use = network_use
  66                 self.iface_cache = iface_cache
  67                 self.stores = stores
  68                 self.help_with_testing = False
  69                 self.extra_restrictions = extra_restrictions or {}
  70
  71         def solve(self, root_interface, root_arch):
  72                 # TODO: We need some way to figure out which feeds to include.
  73                 # Currently, we include any feed referenced from anywhere but
  74                 # this is probably too much. We could insert a dummy optimial
  75                 # implementation in stale/uncached feeds and see whether it
  76                 # selects that.
  77
  78                 feeds_added = set()
  79                 problem = []
  80                 costs = {}      # impl -> cost
  81
  82                 feed_names = {} # Feed -> "f1"
  83                 impl_names = {} # Impl -> "f1_0"
  84                 self.feeds_used = set()
  85                 name_to_impl = {}       # "f1_0" -> (Iface, Impl)
  86                 self.selections = {}
  87                 self.requires = {}
  88                 self.ready = False
  89                 self.details = self.record_details and {}
  90
  91                 def feed_name(feed):
  92                         name = feed_names.get(feed, None)
  93                         if name: return name
  94                         feed_names[feed] = name = "f%d" % (len(feed_names))
  95                         print feed, "is now known as", name
  96                         self.feeds_used.add(feed.url)
  97                         return name
  98
  99                 def get_cached(impl):
 100                         """Check whether an implementation is available locally.
 101                         @type impl: model.Implementation
 102                         @rtype: bool
 103                         """
 104                         if isinstance(impl, model.DistributionImplementation):
 105                                 return impl.installed
 106                         if impl.local_path:
 107                                 return os.path.exists(impl.local_path)
 108                         else:
 109                                 try:
 110                                         path = self.stores.lookup_any(impl.digests)
 111                                         assert path
 112                                         return True
 113                                 except BadDigest:
 114                                         return False
 115                                 except NotStored:
 116                                         return False
 117
 118                 ifaces_processed = set()
 119
 120                 def find_dependency_candidates(requiring_impl, dependency):
 121                         dep_iface = self.iface_cache.get_interface(dependency.interface)
 122                         # TODO: version restrictions
 123                         dep_exprs = []
 124                         for candidate in dep_iface.implementations.values():
 125                                 c_name = impl_names.get(candidate, None)
 126                                 if c_name:
 127                                         dep_exprs.append("1 * " + c_name)
 128                                 # else we filtered that version out, so ignore it
 129                         problem.append(("-1 * " + requiring_impl) + " " + " + ".join(dep_exprs) + " >= 0")
 130
 131                 def add_iface(uri, arch):
 132                         """Name implementations from feed, assign costs and assert that one one can be selected."""
 133                         if uri in ifaces_processed: return
 134                         ifaces_processed.add(uri)
 135
 136                         iface = self.iface_cache.get_interface(uri)
 137                         impls = sorted(iface.implementations.values())
 138                         rank = 1
 139                         exprs = []
 140                         for impl in impls:
 141                                 if self.network_use == model.network_offline and not get_cached(impl):
 142                                         print "(ignoring uncached impl %s)" % impl
 143                                         continue
 144
 145                                 name = feed_name(impl.feed) + "_" + str(rank)
 146                                 assert impl not in impl_names
 147                                 impl_names[impl] = name
 148                                 name_to_impl[name] = (iface, impl)
 149                                 print "Adding %s as %s" % (impl, name)
 150                                 costs[name] = rank
 151                                 rank += 1
 152                                 exprs.append('1 * ' + name)
 153
 154                                 self.requires[iface] = selected_requires = []
 155                                 for d in impl.requires:
 156                                         debug(_("Considering dependency %s"), d)
 157                                         use = d.metadata.get("use", None)
 158                                         if use not in arch.use:
 159                                                 info("Skipping dependency; use='%s' not in %s", use, arch.use)
 160                                                 continue
 161
 162                                         add_iface(d.interface, arch.child_arch)
 163                                         selected_requires.append(d)
 164
 165                                         # Must choose one version of d if impl is selected
 166                                         find_dependency_candidates(name, d)
 167
 168                         # Only one implementation of this interface can be selected
 169                         if uri == root_interface:
 170                                 problem.append(" + ".join(exprs) + " = 1")
 171                         else:
 172                                 problem.append(" + ".join(exprs) + " <= 1")
 173
 174                 add_iface(root_interface, root_arch)
 175
 176                 prog_fd, tmp_name = tempfile.mkstemp(prefix = '0launch')
 177                 try:
 178                         stream = os.fdopen(prog_fd, 'wb')
 179                         try:
 180                                 print >>stream, "min:", ' + '.join("%d * %s" % (cost, name) for name, cost in costs.iteritems()) + ";"
 181                                 for line in problem:
 182                                         print >>stream, line, ";"
 183                         finally:
 184                                 stream.close()
 185                         child = subprocess.Popen(['minisat+', tmp_name, '-v0'], stdout = subprocess.PIPE)
 186                         data, used = child.communicate()
 187                         for line in data.split('\n'):
 188                                 if line.startswith('v '):
 189                                         bits = line.split(' ')[1:]
 190                                         for bit in bits:
 191                                                 if not bit.startswith('-'):
 192                                                         print bit
 193                                                         iface, impl = name_to_impl[bit]
 194                                                         print "%s (%s)" % (iface, impl.get_version())
 195                                                         self.selections[iface] = impl
 196                                 elif line == "s OPTIMUM FOUND":
 197                                         self.ready = True
 198                                 elif line:
 199                                         print line
 200                 finally:
 201                         #print tmp_name
 202                         os.unlink(tmp_name)
 203
 204 DefaultSolver = PBSolver
 205
 206 class StupidSolver(Solver):
 207         """The standard (rather naive) Zero Install solver."""
 208         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
 209                 """
 210                 @param network_use: how much use to make of the network
 211                 @type network_use: L{model.network_levels}
 212                 @param iface_cache: a cache of feeds containing information about available versions
 213                 @type iface_cache: L{iface_cache.IfaceCache}
 214                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
 215                 @type stores: L{zerostore.Stores}
 216                 @param extra_restrictions: extra restrictions on the chosen implementations
 217                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
 218                 """
 219                 Solver.__init__(self)
 220                 self.network_use = network_use
 221                 self.iface_cache = iface_cache
 222                 self.stores = stores
 223                 self.help_with_testing = False
 224                 self.extra_restrictions = extra_restrictions or {}
 225
 226         def solve(self, root_interface, arch):
 227                 self.selections = {}
 228                 self.requires = {}
 229                 self.feeds_used = set()
 230                 self.details = self.record_details and {}
 231                 self._machine_group = None
 232
 233                 restrictions = {}
 234                 debug(_("Solve! root = %s"), root_interface)
 235                 def process(dep, arch):
 236                         ready = True
 237                         iface = self.iface_cache.get_interface(dep.interface)
 238
 239                         if iface in self.selections:
 240                                 debug("Interface requested twice; skipping second %s", iface)
 241                                 if dep.restrictions:
 242                                         warn("Interface requested twice; I've already chosen an implementation "
 243                                                 "of '%s' but there are more restrictions! Ignoring the second set.", iface)
 244                                 return ready
 245                         self.selections[iface] = None   # Avoid cycles
 246                         self.requires[iface] = selected_requires = []
 247
 248                         assert iface not in restrictions
 249                         restrictions[iface] = dep.restrictions
 250
 251                         impl = get_best_implementation(iface, arch)
 252                         if impl:
 253                                 debug(_("Will use implementation %(implementation)s (version %(version)s)"), {'implementation': impl, 'version': impl.get_version()})
 254                                 self.selections[iface] = impl
 255                                 if self._machine_group is None and impl.machine and impl.machine != 'src':
 256                                         self._machine_group = machine_groups.get(impl.machine, 0)
 257                                         debug(_("Now restricted to architecture group %s"), self._machine_group)
 258                                 for d in impl.requires:
 259                                         debug(_("Considering dependency %s"), d)
 260                                         use = d.metadata.get("use", None)
 261                                         if use not in arch.use:
 262                                                 info("Skipping dependency; use='%s' not in %s", use, arch.use)
 263                                                 continue
 264                                         if not process(d, arch.child_arch):
 265                                                 ready = False
 266                                         selected_requires.append(d)
 267                         else:
 268                                 debug(_("No implementation chould be chosen yet"));
 269                                 ready = False
 270
 271                         return ready
 272
 273                 def get_best_implementation(iface, arch):
 274                         debug(_("get_best_implementation(%(interface)s), with feeds: %(feeds)s"), {'interface': iface, 'feeds': iface.feeds})
 275
 276                         iface_restrictions = restrictions.get(iface, [])
 277                         extra_restrictions = self.extra_restrictions.get(iface, None)
 278                         if extra_restrictions:
 279                                 # Don't modify original
 280                                 iface_restrictions = iface_restrictions + extra_restrictions
 281
 282                         impls = []
 283                         for f in usable_feeds(iface, arch):
 284                                 self.feeds_used.add(f)
 285                                 debug(_("Processing feed %s"), f)
 286
 287                                 try:
 288                                         feed = self.iface_cache.get_interface(f)._main_feed
 289                                         if not feed.last_modified: continue     # DummyFeed
 290                                         if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 291                                                 info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 292
 293                                         if feed.implementations:
 294                                                 impls.extend(feed.implementations.values())
 295                                 except Exception, ex:
 296                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': str(ex)})
 297
 298                         if not impls:
 299                                 info(_("Interface %s has no implementations!"), iface)
 300                                 return None
 301
 302                         if self.record_details:
 303                                 # In details mode, rank all the implementations and then choose the best
 304                                 impls.sort(lambda a, b: compare(iface, a, b, iface_restrictions, arch))
 305                                 best = impls[0]
 306                                 self.details[iface] = [(impl, get_unusable_reason(impl, iface_restrictions, arch)) for impl in impls]
 307                         else:
 308                                 # Otherwise, just choose the best without sorting
 309                                 best = impls[0]
 310                                 for x in impls[1:]:
 311                                         if compare(iface, x, best, iface_restrictions, arch) < 0:
 312                                                 best = x
 313                         unusable = get_unusable_reason(best, iface_restrictions, arch)
 314                         if unusable:
 315                                 info(_("Best implementation of %(interface)s is %(best)s, but unusable (%(unusable)s)"), {'interface': iface, 'best': best, 'unusable': unusable})
 316                                 return None
 317                         return best
 318
 319                 def compare(interface, b, a, iface_restrictions, arch):
 320                         """Compare a and b to see which would be chosen first.
 321                         @param interface: The interface we are trying to resolve, which may
 322                         not be the interface of a or b if they are from feeds.
 323                         @rtype: int"""
 324                         a_stab = a.get_stability()
 325                         b_stab = b.get_stability()
 326
 327                         # Usable ones come first
 328                         r = cmp(is_unusable(b, iface_restrictions, arch), is_unusable(a, iface_restrictions, arch))
 329                         if r: return r
 330
 331                         # Preferred versions come first
 332                         r = cmp(a_stab == model.preferred, b_stab == model.preferred)
 333                         if r: return r
 334
 335                         if self.network_use != model.network_full:
 336                                 r = cmp(get_cached(a), get_cached(b))
 337                                 if r: return r
 338
 339                         # Stability
 340                         stab_policy = interface.stability_policy
 341                         if not stab_policy:
 342                                 if self.help_with_testing: stab_policy = model.testing
 343                                 else: stab_policy = model.stable
 344
 345                         if a_stab >= stab_policy: a_stab = model.preferred
 346                         if b_stab >= stab_policy: b_stab = model.preferred
 347
 348                         r = cmp(a_stab, b_stab)
 349                         if r: return r
 350
 351                         # Newer versions come before older ones
 352                         r = cmp(a.version, b.version)
 353                         if r: return r
 354
 355                         # Get best OS
 356                         r = cmp(arch.os_ranks.get(b.os, None),
 357                                 arch.os_ranks.get(a.os, None))
 358                         if r: return r
 359
 360                         # Get best machine
 361                         r = cmp(arch.machine_ranks.get(b.machine, None),
 362                                 arch.machine_ranks.get(a.machine, None))
 363                         if r: return r
 364
 365                         # Slightly prefer cached versions
 366                         if self.network_use == model.network_full:
 367                                 r = cmp(get_cached(a), get_cached(b))
 368                                 if r: return r
 369
 370                         return cmp(a.id, b.id)
 371
 372                 def usable_feeds(iface, arch):
 373                         """Return all feeds for iface that support arch.
 374                         @rtype: generator(ZeroInstallFeed)"""
 375                         yield iface.uri
 376
 377                         for f in iface.feeds:
 378                                 # Note: when searching for src, None is not in machine_ranks
 379                                 if f.os in arch.os_ranks and \
 380                                    (f.machine is None or f.machine in arch.machine_ranks):
 381                                         yield f.uri
 382                                 else:
 383                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 384                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 385
 386                 def is_unusable(impl, restrictions, arch):
 387                         """@return: whether this implementation is unusable.
 388                         @rtype: bool"""
 389                         return get_unusable_reason(impl, restrictions, arch) != None
 390
 391                 def get_unusable_reason(impl, restrictions, arch):
 392                         """
 393                         @param impl: Implementation to test.
 394                         @type restrictions: [L{model.Restriction}]
 395                         @return: The reason why this impl is unusable, or None if it's OK.
 396                         @rtype: str
 397                         @note: The restrictions are for the interface being requested, not the interface
 398                         of the implementation; they may be different when feeds are being used."""
 399                         machine = impl.machine
 400                         if machine and self._machine_group is not None:
 401                                 if machine_groups.get(machine, 0) != self._machine_group:
 402                                         return _("Incompatible with another selection from a different architecture group")
 403
 404                         for r in restrictions:
 405                                 if not r.meets_restriction(impl):
 406                                         return _("Incompatible with another selected implementation")
 407                         stability = impl.get_stability()
 408                         if stability <= model.buggy:
 409                                 return stability.name
 410                         if self.network_use == model.network_offline and not get_cached(impl):
 411                                 return _("Not cached and we are off-line")
 412                         if impl.os not in arch.os_ranks:
 413                                 return _("Unsupported OS")
 414                         # When looking for source code, we need to known if we're
 415                         # looking at an implementation of the root interface, even if
 416                         # it's from a feed, hence the sneaky restrictions identity check.
 417                         if machine not in arch.machine_ranks:
 418                                 if machine == 'src':
 419                                         return _("Source code")
 420                                 return _("Unsupported machine type")
 421                         return None
 422
 423                 def get_cached(impl):
 424                         """Check whether an implementation is available locally.
 425                         @type impl: model.Implementation
 426                         @rtype: bool
 427                         """
 428                         if isinstance(impl, model.DistributionImplementation):
 429                                 return impl.installed
 430                         if impl.local_path:
 431                                 return os.path.exists(impl.local_path)
 432                         else:
 433                                 try:
 434                                         path = self.stores.lookup_any(impl.digests)
 435                                         assert path
 436                                         return True
 437                                 except BadDigest:
 438                                         return False
 439                                 except NotStored:
 440                                         return False
 441
 442                 self.ready = process(model.InterfaceDependency(root_interface), arch)