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