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