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