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