zeroinstall/injector/solver.py

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