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