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, sys, locale
  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, sat, selections
  16
  17 def _get_cached(stores, impl):
  18         """Check whether an implementation is available locally.
  19         @type impl: model.Implementation
  20         @rtype: bool
  21         """
  22         if isinstance(impl, model.DistributionImplementation):
  23                 return impl.installed
  24         if impl.local_path:
  25                 return os.path.exists(impl.local_path)
  26         else:
  27                 try:
  28                         if not impl.digests:
  29                                 warn("No digests given for %s!", impl)
  30                                 return False
  31                         path = stores.lookup_any(impl.digests)
  32                         assert path
  33                         return True
  34                 except BadDigest:
  35                         return False
  36                 except NotStored:
  37                         return False
  38
  39 class CommandInfo:
  40         def __init__(self, name, command, impl, arch):
  41                 self.name = name
  42                 self.command = command
  43                 self.impl = impl
  44                 self.arch = arch
  45
  46         def __repr__(self):
  47                 name = "%s_%s_%s_%s" % (self.impl.feed.get_name(), self.impl.get_version(), self.impl.arch, self.name)
  48                 return name.replace('-', '_').replace('.', '_')
  49
  50 class ImplInfo:
  51         is_dummy = False
  52
  53         def __init__(self, iface, impl, arch, dummy = False):
  54                 self.iface = iface
  55                 self.impl = impl
  56                 self.arch = arch
  57                 if dummy:
  58                         self.is_dummy = True
  59
  60         def __repr__(self):
  61                 name = "%s_%s_%s" % (self.impl.feed.get_name(), self.impl.get_version(), self.impl.arch)
  62                 return name.replace('-', '_').replace('.', '_')
  63
  64 class _DummyImpl(object):
  65         requires = []
  66         version = None
  67         arch = None
  68         commands = {}
  69
  70         def __repr__(self):
  71                 return "dummy"
  72
  73         feed = property(lambda self: self)
  74
  75         def get_version(self):
  76                 return "dummy"
  77
  78         def get_name(self):
  79                 return "dummy"
  80
  81 class Solver(object):
  82         """Chooses a set of implementations to satisfy the requirements of a program and its user.
  83         Typical use:
  84          1. Create a Solver object and configure it
  85          2. Call L{solve}.
  86          3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
  87          4. If it is 'ready' then you can download and run the chosen versions.
  88         @ivar selections: the chosen implementation of each interface
  89         @type selections: L{selections.Selections}
  90         @ivar requires: the selected dependencies for each chosen version
  91         @type requires: {L{model.Interface}: [L{model.Dependency}]}
  92         @ivar feeds_used: the feeds which contributed to the choice in L{selections}
  93         @type feeds_used: set(str)
  94         @ivar record_details: whether to record information about unselected implementations
  95         @type record_details: {L{Interface}: [(L{Implementation}, str)]}
  96         @ivar details: extra information, if record_details mode was used
  97         @type details: {str: [(Implementation, comment)]}
  98         """
  99         __slots__ = ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
 100
 101         def __init__(self):
 102                 self.selections = self.requires = self.feeds_used = self.details = None
 103                 self.record_details = False
 104                 self.ready = False
 105
 106         def solve(self, root_interface, root_arch, command_name = 'run'):
 107                 """Get the best implementation of root_interface and all of its dependencies.
 108                 @param root_interface: the URI of the program to be solved
 109                 @type root_interface: str
 110                 @param root_arch: the desired target architecture
 111                 @type root_arch: L{arch.Architecture}
 112                 @param command_name: which <command> element to select
 113                 @type command_name: str
 114                 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
 115                 raise NotImplementedError("Abstract")
 116
 117 class SATSolver(Solver):
 118         __slots__ = ['_failure_reason', 'network_use', 'iface_cache', 'stores', 'help_with_testing', 'extra_restrictions',
 119                         'langs']
 120
 121         """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them.
 122         @ivar langs: the preferred languages (e.g. ["es_ES", "en"]). Initialised to the current locale.
 123         @type langs: str"""
 124         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
 125                 """
 126                 @param network_use: how much use to make of the network
 127                 @type network_use: L{model.network_levels}
 128                 @param iface_cache: a cache of feeds containing information about available versions
 129                 @type iface_cache: L{iface_cache.IfaceCache}
 130                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
 131                 @type stores: L{zerostore.Stores}
 132                 @param extra_restrictions: extra restrictions on the chosen implementations
 133                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
 134                 """
 135                 Solver.__init__(self)
 136                 self.network_use = network_use
 137                 self.iface_cache = iface_cache
 138                 self.stores = stores
 139                 self.help_with_testing = False
 140                 self.extra_restrictions = extra_restrictions or {}
 141
 142                 self.langs = [locale.getlocale()[0] or 'en']
 143
 144         def compare(self, interface, b, a, arch):
 145                 """Compare a and b to see which would be chosen first.
 146                 Does not consider whether the implementations are usable (check for that yourself first).
 147                 @param interface: The interface we are trying to resolve, which may
 148                 not be the interface of a or b if they are from feeds.
 149                 @rtype: int"""
 150
 151                 # Languages we understand come first
 152                 a_langs = (a.langs or 'en').split()
 153                 b_langs = (b.langs or 'en').split()
 154                 main_langs = set(l.split('_')[0] for l in self.langs)
 155                 r = cmp(any(l.split('_')[0] in main_langs for l in a_langs),
 156                         any(l.split('_')[0] in main_langs for l in b_langs))
 157                 if r: return r
 158
 159                 a_stab = a.get_stability()
 160                 b_stab = b.get_stability()
 161
 162                 # Preferred versions come first
 163                 r = cmp(a_stab == model.preferred, b_stab == model.preferred)
 164                 if r: return r
 165
 166                 stores = self.stores
 167                 if self.network_use != model.network_full:
 168                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 169                         if r: return r
 170
 171                 # Packages that require admin access to install come last
 172                 r = cmp(b.requires_root_install, a.requires_root_install)
 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                 if a.id.startswith('package:') != b.id.startswith('package:'):
 189                         # If one of packages is native, do not compare full versions since
 190                         # it is useless to compare native and 0install version revisions
 191                         r = cmp(a.version[0], b.version[0])
 192                         if r: return r
 193                         # Othewise, prefer native package
 194                         return cmp(a.id.startswith('package:'), b.id.startswith('package:'))
 195                 else:
 196                         r = cmp(a.version, b.version)
 197                         if r: return r
 198
 199                 # Get best OS
 200                 r = cmp(arch.os_ranks.get(b.os, None),
 201                         arch.os_ranks.get(a.os, None))
 202                 if r: return r
 203
 204                 # Get best machine
 205                 r = cmp(arch.machine_ranks.get(b.machine, None),
 206                         arch.machine_ranks.get(a.machine, None))
 207                 if r: return r
 208
 209                 # Slightly prefer languages specialised to our country
 210                 r = cmp(any(l in self.langs for l in a_langs),
 211                         any(l in self.langs for l in b_langs))
 212                 if r: return r
 213
 214                 # Slightly prefer cached versions
 215                 if self.network_use == model.network_full:
 216                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 217                         if r: return r
 218
 219                 return cmp(a.id, b.id)
 220
 221         def solve(self, root_interface, root_arch, command_name = 'run', closest_match = False):
 222                 # closest_match is used internally. It adds a lowest-ranked
 223                 # by valid implementation to every interface, so we can always
 224                 # select something. Useful for diagnostics.
 225
 226                 # TODO: We need some way to figure out which feeds to include.
 227                 # Currently, we include any feed referenced from anywhere but
 228                 # this is probably too much. We could insert a dummy optimial
 229                 # implementation in stale/uncached feeds and see whether it
 230                 # selects that.
 231
 232                 feeds_added = set()
 233                 problem = sat.SATProblem()
 234
 235                 impl_to_var = {}        # Impl -> sat var
 236                 self.feeds_used = set()
 237                 self.requires = {}
 238                 self.ready = False
 239                 self.details = self.record_details and {}
 240
 241                 self.selections = None
 242                 self._failure_reason = None
 243
 244                 ifaces_processed = set()
 245
 246                 impls_for_machine_group = {0 : []}              # Machine group (e.g. "64") to [impl] in that group
 247                 for machine_group in machine_groups.values():
 248                         impls_for_machine_group[machine_group] = []
 249
 250                 impls_for_iface = {}    # Iface -> [impl]
 251
 252                 group_clause_for = {}   # Iface URI -> AtMostOneClause | bool
 253                 group_clause_for_command = {}   # (Iface URI, command name) -> AtMostOneClause | bool
 254
 255                 # Return the dependencies of impl that we should consider.
 256                 # Skips dependencies if the use flag isn't what we need.
 257                 # (note: impl may also be a model.Command)
 258                 def deps_in_use(impl, arch):
 259                         for dep in impl.requires:
 260                                 use = dep.metadata.get("use", None)
 261                                 if use not in arch.use:
 262                                         continue
 263                                 yield dep
 264
 265                 # Add a clause so that if requiring_impl_var is True then an implementation
 266                 # matching 'dependency' must also be selected.
 267                 # Must have already done add_iface on dependency.interface.
 268                 def find_dependency_candidates(requiring_impl_var, dependency):
 269                         dep_iface = self.iface_cache.get_interface(dependency.interface)
 270                         dep_union = [sat.neg(requiring_impl_var)]       # Either requiring_impl_var is False, or ...
 271                         for candidate in impls_for_iface[dep_iface]:
 272                                 for r in dependency.restrictions:
 273                                         if candidate.__class__ is not _DummyImpl and not r.meets_restriction(candidate):
 274                                                 #warn("%s rejected due to %s", candidate.get_version(), r)
 275                                                 if candidate.version is not None:
 276                                                         break
 277                                 else:
 278                                         c_var = impl_to_var.get(candidate, None)
 279                                         if c_var is not None:
 280                                                 dep_union.append(c_var)
 281                                         # else we filtered that version out, so ignore it
 282                         if dep_union:
 283                                 problem.add_clause(dep_union)
 284                         else:
 285                                 assert 0        # XXX: how can this happen?
 286                                 problem.assign(requiring_impl_var, 0)
 287
 288                 def is_unusable(impl, restrictions, arch):
 289                         """@return: whether this implementation is unusable.
 290                         @rtype: bool"""
 291                         return get_unusable_reason(impl, restrictions, arch) != None
 292
 293                 def get_unusable_reason(impl, restrictions, arch):
 294                         """
 295                         @param impl: Implementation to test.
 296                         @type restrictions: [L{model.Restriction}]
 297                         @return: The reason why this impl is unusable, or None if it's OK.
 298                         @rtype: str
 299                         @note: The restrictions are for the interface being requested, not the feed
 300                         of the implementation; they may be different when feeds are being used."""
 301                         for r in restrictions:
 302                                 if not r.meets_restriction(impl):
 303                                         return _("Incompatible with another selected implementation")
 304                         stability = impl.get_stability()
 305                         if stability <= model.buggy:
 306                                 return stability.name
 307                         if (self.network_use == model.network_offline or not impl.download_sources) and not _get_cached(self.stores, impl):
 308                                 if not impl.download_sources:
 309                                         return _("No retrieval methods")
 310                                 return _("Not cached and we are off-line")
 311                         if impl.os not in arch.os_ranks:
 312                                 return _("Unsupported OS")
 313                         if impl.machine not in arch.machine_ranks:
 314                                 if impl.machine == 'src':
 315                                         return _("Source code")
 316                                 return _("Unsupported machine type")
 317                         return None
 318
 319                 def usable_feeds(iface, arch):
 320                         """Return all feeds for iface that support arch.
 321                         @rtype: generator(ZeroInstallFeed)"""
 322                         yield iface.uri
 323
 324                         for f in self.iface_cache.get_feed_imports(iface):
 325                                 # Note: when searching for src, None is not in machine_ranks
 326                                 if f.os in arch.os_ranks and \
 327                                    (f.machine is None or f.machine in arch.machine_ranks):
 328                                         yield f.uri
 329                                 else:
 330                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 331                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 332
 333                 def add_iface(uri, arch):
 334                         """Name implementations from feed and assert that only one can be selected."""
 335                         if uri in ifaces_processed: return
 336                         ifaces_processed.add(uri)
 337                         iface_name = 'i%d' % len(ifaces_processed)
 338
 339                         iface = self.iface_cache.get_interface(uri)
 340
 341                         impls = []
 342                         for f in usable_feeds(iface, arch):
 343                                 self.feeds_used.add(f)
 344                                 debug(_("Processing feed %s"), f)
 345
 346                                 try:
 347                                         feed = self.iface_cache.get_feed(f)
 348                                         if feed is None: continue
 349                                         #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 350                                         #       info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 351
 352                                         if feed.implementations:
 353                                                 impls.extend(feed.implementations.values())
 354
 355                                         distro_feed_url = feed.get_distro_feed()
 356                                         if distro_feed_url:
 357                                                 self.feeds_used.add(distro_feed_url)
 358                                                 distro_feed = self.iface_cache.get_feed(distro_feed_url)
 359                                                 if distro_feed.implementations:
 360                                                         impls.extend(distro_feed.implementations.values())
 361                                 except Exception, ex:
 362                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': ex})
 363
 364                         impls.sort(lambda a, b: self.compare(iface, a, b, arch))
 365
 366                         impls_for_iface[iface] = filtered_impls = []
 367
 368                         my_extra_restrictions = self.extra_restrictions.get(iface, [])
 369
 370                         if self.record_details:
 371                                 self.details[iface] = [(impl, get_unusable_reason(impl, my_extra_restrictions, arch)) for impl in impls]
 372
 373                         rank = 1
 374                         var_names = []
 375                         for impl in impls:
 376                                 if is_unusable(impl, my_extra_restrictions, arch):
 377                                         continue
 378
 379                                 filtered_impls.append(impl)
 380
 381                                 assert impl not in impl_to_var
 382                                 v = problem.add_variable(ImplInfo(iface, impl, arch))
 383                                 impl_to_var[impl] = v
 384                                 rank += 1
 385                                 var_names.append(v)
 386
 387                                 if impl.machine and impl.machine != 'src':
 388                                         impls_for_machine_group[machine_groups.get(impl.machine, 0)].append(v)
 389
 390                                 for d in deps_in_use(impl, arch):
 391                                         debug(_("Considering dependency %s"), d)
 392
 393                                         add_iface(d.interface, arch.child_arch)
 394
 395                                         # Must choose one version of d if impl is selected
 396                                         find_dependency_candidates(v, d)
 397
 398                         if closest_match:
 399                                 dummy_impl = _DummyImpl()
 400                                 dummy_var = problem.add_variable(ImplInfo(iface, dummy_impl, arch, dummy = True))
 401                                 var_names.append(dummy_var)
 402                                 impl_to_var[dummy_impl] = dummy_var
 403                                 filtered_impls.append(dummy_impl)
 404
 405                         # Only one implementation of this interface can be selected
 406                         if uri == root_interface:
 407                                 if var_names:
 408                                         clause = problem.at_most_one(var_names)
 409                                         problem.add_clause(var_names)   # at least one
 410                                 else:
 411                                         problem.impossible()
 412                                         clause = False
 413                         elif var_names:
 414                                 clause = problem.at_most_one(var_names)
 415                         else:
 416                                 # Don't need to add to group_clause_for because we should
 417                                 # never get a possible selection involving this.
 418                                 return
 419
 420                         assert clause is not True
 421                         assert clause is not None
 422                         if clause is not False:
 423                                 group_clause_for[uri] = clause
 424
 425                 def add_command_iface(uri, arch, command_name):
 426                         """Add every <command> in interface 'uri' with this name.
 427                         Each one depends on the corresponding implementation and only
 428                         one can be selected."""
 429
 430                         # First ensure that the interface itself has been processed
 431                         # We'll reuse the ordering of the implementations to order
 432                         # the commands too.
 433                         add_iface(uri, arch)
 434
 435                         iface = self.iface_cache.get_interface(uri)
 436                         filtered_impls = impls_for_iface[iface]
 437
 438                         var_names = []
 439                         for impl in filtered_impls:
 440                                 command = impl.commands.get(command_name, None)
 441                                 if not command: continue
 442
 443                                 # We have a candidate <command>. Require that if it's selected
 444                                 # then we select the corresponding <implementation> too.
 445                                 command_var = problem.add_variable(CommandInfo(command_name, command, impl, arch))
 446                                 problem.add_clause([impl_to_var[impl], sat.neg(command_var)])
 447
 448                                 var_names.append(command_var)
 449
 450                                 for d in deps_in_use(command, arch):
 451                                         debug(_("Considering command dependency %s"), d)
 452
 453                                         add_iface(d.interface, arch.child_arch)
 454
 455                                         # Must choose one version of d if impl is selected
 456                                         find_dependency_candidates(command_var, d)
 457
 458                         return var_names
 459
 460                 commands = add_command_iface(root_interface, root_arch, command_name)
 461                 if commands:
 462                         problem.add_clause(commands)            # At least one
 463                         group_clause_for_command[(root_interface, command_name)] = problem.at_most_one(commands)
 464                 else:
 465                         # (note: might be because we haven't cached it yet)
 466                         info("No %s <command> in %s", command_name, root_interface)
 467
 468                         impls = impls_for_iface[self.iface_cache.get_interface(root_interface)]
 469                         if impls == [] or (len(impls) == 1 and isinstance(impls[0], _DummyImpl)):
 470                                 # There were no candidates at all.
 471                                 self._failure_reason = _("Interface '%s' has no usable implementations") % root_interface
 472                         else:
 473                                 # We had some candidates implementations, but none for the command we need
 474                                 self._failure_reason = _("Interface '%s' cannot be executed directly; it is just a library "
 475                                             "to be used by other programs (or missing '%s' command)") % (root_interface, command_name)
 476
 477                         problem.impossible()
 478
 479                 # Require m<group> to be true if we select an implementation in that group
 480                 m_groups = []
 481                 for machine_group, impls in impls_for_machine_group.iteritems():
 482                         m_group = 'm%d' % machine_group
 483                         group_var = problem.add_variable(m_group)
 484                         if impls:
 485                                 for impl in impls:
 486                                         problem.add_clause([group_var, sat.neg(impl)])
 487                         m_groups.append(group_var)
 488                 if m_groups:
 489                         m_groups_clause = problem.at_most_one(m_groups)
 490                 else:
 491                         m_groups_clause = None
 492
 493                 def decide():
 494                         """Recurse through the current selections until we get to an interface with
 495                         no chosen version, then tell the solver to try the best version from that."""
 496
 497                         def find_undecided_dep(impl_or_command, arch):
 498                                 # Check for undecided dependencies of impl_or_command
 499                                 for dep in deps_in_use(impl_or_command, arch):
 500                                         dep_lit = find_undecided(dep.interface)
 501                                         if dep_lit is not None:
 502                                                 return dep_lit
 503                                 return None
 504
 505                         seen = set()
 506                         def find_undecided(uri):
 507                                 if uri in seen:
 508                                         return  # Break cycles
 509                                 seen.add(uri)
 510
 511                                 group = group_clause_for[uri]
 512                                 #print "Group for %s = %s" % (uri, group)
 513                                 lit = group.current
 514                                 if lit is None:
 515                                         return group.best_undecided()
 516                                 # else there was only one choice anyway
 517
 518                                 # Check for undecided dependencies
 519                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 520                                 return find_undecided_dep(lit_info.impl, lit_info.arch)
 521
 522                         def find_undecided_command(uri, name):
 523                                 if name is None: return find_undecided(uri)
 524
 525                                 group = group_clause_for_command[(uri, name)]
 526                                 lit = group.current
 527                                 if lit is None:
 528                                         return group.best_undecided()
 529                                 # else we've already chosen which <command> to use
 530
 531                                 # Check for undecided command-specific dependencies, and then for
 532                                 # implementation dependencies.
 533                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 534                                 return find_undecided_dep(lit_info.command, lit_info.arch) or \
 535                                        find_undecided_dep(lit_info.impl, lit_info.arch)
 536
 537                         best = find_undecided_command(root_interface, command_name)
 538                         if best is not None:
 539                                 return best
 540
 541                         # If we're chosen everything we need, we can probably
 542                         # set everything else to False.
 543                         for group in group_clause_for.values() + [m_groups_clause]:
 544                                 if group.current is None:
 545                                         best = group.best_undecided()
 546                                         if best is not None:
 547                                                 return sat.neg(best)
 548
 549                         return None                     # Failed to find any valid combination
 550
 551                 ready = problem.run_solver(decide) is True
 552
 553                 if not ready and not closest_match:
 554                         # We failed while trying to do a real solve.
 555                         # Try a closest match solve to get a better
 556                         # error report for the user.
 557                         self.solve(root_interface, root_arch, command_name = command_name, closest_match = True)
 558                 else:
 559                         self.ready = ready and not closest_match
 560                         self.selections = selections.Selections(None)
 561                         self.selections.interface = root_interface
 562
 563                         sels = self.selections.selections
 564
 565                         for uri, group in group_clause_for.iteritems():
 566                                 if group.current is not None:
 567                                         lit_info = problem.get_varinfo_for_lit(group.current).obj
 568                                         if lit_info.is_dummy:
 569                                                 sels[lit_info.iface.uri] = None
 570                                         else:
 571                                                 impl = lit_info.impl
 572
 573                                                 deps = self.requires[lit_info.iface] = []
 574                                                 for dep in deps_in_use(lit_info.impl, lit_info.arch):
 575                                                         deps.append(dep)
 576
 577                                                 sels[lit_info.iface.uri] = selections.ImplSelection(lit_info.iface.uri, impl, deps)
 578
 579                         root_sel = sels.get(root_interface, None)
 580                         if root_sel:
 581                                 self.selections.command = root_sel.impl.commands[command_name]
 582
 583         def get_failure_reason(self):
 584                 """Return an exception explaining why the solve failed."""
 585                 assert not self.ready
 586
 587                 if self._failure_reason:
 588                         return model.SafeException(self._failure_reason)
 589
 590                 return model.SafeException(_("Can't find all required implementations:") + '\n' +
 591                                 '\n'.join(["- %s -> %s" % (iface, self.selections[iface])
 592                                            for iface  in self.selections]))
 593
 594 DefaultSolver = SATSolver