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 langs: languages (and regions), first choice first
 123                 @type langs: [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 get_rating(self, interface, impl, arch):
 142                 impl_langs = (impl.langs or 'en').split()
 143                 my_langs = self._lang_ranks
 144
 145                 stores = self.config.stores
 146                 is_available = impl.is_available(stores)
 147
 148                 # Stability
 149                 stab_policy = interface.stability_policy
 150                 if not stab_policy:
 151                         if self.config.help_with_testing: stab_policy = model.testing
 152                         else: stab_policy = model.stable
 153
 154                 stability = impl.get_stability()
 155                 if stability >= stab_policy:
 156                         stability_limited = model.preferred
 157                 else:
 158                         stability_limited = stability
 159
 160                 return [
 161                         # Languages we understand come first
 162                         max(my_langs.get(l.split('-')[0], -1) for l in impl_langs),
 163
 164                         # Preferred versions come first
 165                         stability == model.preferred,
 166
 167                         # Prefer available implementations next if we have limited network access
 168                         self.config.network_use != model.network_full and is_available,
 169
 170                         # Packages that require admin access to install come last
 171                         not impl.requires_root_install,
 172
 173                         # Prefer more stable versions, but treat everything over stab_policy the same
 174                         # (so we prefer stable over testing if the policy is to prefer "stable", otherwise
 175                         # we don't care)
 176                         stability_limited,
 177
 178                         # Newer versions come before older ones (ignoring modifiers)
 179                         impl.version[0],
 180
 181                         # Prefer native packages if the main part of the versions are the same
 182                         impl.id.startswith('package:'),
 183
 184                         # Full version compare (after package check, since comparing modifiers between native and non-native
 185                         # packages doesn't make sense).
 186                         impl.version,
 187
 188                         # Get best OS
 189                         -arch.os_ranks.get(impl.os, 999),
 190
 191                         # Get best machine
 192                         -arch.machine_ranks.get(impl.machine, 999),
 193
 194                         # Slightly prefer languages specialised to our country
 195                         # (we know a and b have the same base language at this point)
 196                         max(my_langs.get(l, -1) for l in impl_langs),
 197
 198                         # Slightly prefer cached versions
 199                         is_available,
 200
 201                         # Order by ID so the order isn't random
 202                         impl.id
 203                 ]
 204
 205         def solve(self, root_interface, root_arch, command_name = 'run', closest_match = False):
 206                 # closest_match is used internally. It adds a lowest-ranked
 207                 # by valid implementation to every interface, so we can always
 208                 # select something. Useful for diagnostics.
 209
 210                 # The basic plan is this:
 211                 # 1. Scan the root interface and all dependencies recursively, building up a SAT problem.
 212                 # 2. Solve the SAT problem. Whenever there are multiple options, try the most preferred one first.
 213                 # 3. Create a Selections object from the results.
 214                 #
 215                 # All three involve recursively walking the tree in a similar way:
 216                 # 1) we follow every dependency of every implementation (order not important)
 217                 # 2) we follow every dependency of every selected implementation (better versions first)
 218                 # 3) we follow every dependency of every selected implementation (order doesn't matter)
 219                 #
 220                 # In all cases, a dependency may be on an <implementation> or on a specific <command>.
 221
 222                 # TODO: We need some way to figure out which feeds to include.
 223                 # Currently, we include any feed referenced from anywhere but
 224                 # this is probably too much. We could insert a dummy optimial
 225                 # implementation in stale/uncached feeds and see whether it
 226                 # selects that.
 227                 iface_cache = self.config.iface_cache
 228
 229                 problem = sat.SATProblem()
 230
 231                 impl_to_var = {}        # Impl -> sat var
 232                 self.feeds_used = set()
 233                 self.requires = {}
 234                 self.ready = False
 235                 self.details = self.record_details and {}
 236
 237                 self.selections = None
 238                 self._failure_reason = None
 239
 240                 ifaces_processed = set()
 241
 242                 impls_for_machine_group = {0 : []}              # Machine group (e.g. "64") to [impl] in that group
 243                 for machine_group in machine_groups.values():
 244                         impls_for_machine_group[machine_group] = []
 245
 246                 impls_for_iface = {}    # Iface -> [impl]
 247
 248                 group_clause_for = {}   # Iface URI -> AtMostOneClause | bool
 249                 group_clause_for_command = {}   # (Iface URI, command name) -> AtMostOneClause | bool
 250
 251                 # Return the dependencies of impl that we should consider.
 252                 # Skips dependencies if the use flag isn't what we need.
 253                 # (note: impl may also be a model.Command)
 254                 def deps_in_use(impl, arch):
 255                         for dep in impl.requires:
 256                                 use = dep.metadata.get("use", None)
 257                                 if use not in arch.use:
 258                                         continue
 259                                 yield dep
 260
 261                 # Must have already done add_iface on dependency.interface.
 262                 # If dependency is essential:
 263                 #   Add a clause so that if requiring_impl_var is True then an implementation
 264                 #   matching 'dependency' must also be selected.
 265                 # If dependency is optional:
 266                 #   Require that no incompatible version is selected.
 267                 # This ignores any 'command' required. Handle that separately.
 268                 def find_dependency_candidates(requiring_impl_var, dependency):
 269                         def meets_restrictions(candidate):
 270                                 for r in dependency.restrictions:
 271                                         if not r.meets_restriction(candidate):
 272                                                 #warn("%s rejected due to %s", candidate.get_version(), r)
 273                                                 return False
 274                                 return True
 275
 276                         essential = dependency.importance == model.Dependency.Essential
 277
 278                         dep_iface = iface_cache.get_interface(dependency.interface)
 279                         dep_union = [sat.neg(requiring_impl_var)]       # Either requiring_impl_var is False, or ...
 280                         for candidate in impls_for_iface[dep_iface]:
 281                                 if (candidate.__class__ is _DummyImpl) or meets_restrictions(candidate):
 282                                         if essential:
 283                                                 c_var = impl_to_var.get(candidate, None)
 284                                                 if c_var is not None:
 285                                                         dep_union.append(c_var)
 286                                                 # else we filtered that version out, so ignore it
 287                                 else:
 288                                         # Candidate doesn't meet our requirements
 289                                         # If the dependency is optional add a rule to make sure we don't
 290                                         # select this candidate.
 291                                         # (for essential dependencies this isn't necessary because we must
 292                                         # select a good version and we can't select two)
 293                                         if not essential:
 294                                                 c_var = impl_to_var.get(candidate, None)
 295                                                 if c_var is not None:
 296                                                         problem.add_clause(dep_union + [sat.neg(c_var)])
 297                                                 # else we filtered that version out, so ignore it
 298
 299                         if essential:
 300                                 problem.add_clause(dep_union)
 301
 302                 def is_unusable(impl, restrictions, arch):
 303                         """@return: whether this implementation is unusable.
 304                         @rtype: bool"""
 305                         return get_unusable_reason(impl, restrictions, arch) != None
 306
 307                 def get_unusable_reason(impl, restrictions, arch):
 308                         """
 309                         @param impl: Implementation to test.
 310                         @type restrictions: [L{model.Restriction}]
 311                         @return: The reason why this impl is unusable, or None if it's OK.
 312                         @rtype: str
 313                         @note: The restrictions are for the interface being requested, not the feed
 314                         of the implementation; they may be different when feeds are being used."""
 315                         for r in restrictions:
 316                                 if not r.meets_restriction(impl):
 317                                         return _("Incompatible with another selected implementation")
 318                         stability = impl.get_stability()
 319                         if stability <= model.buggy:
 320                                 return stability.name
 321                         if (self.config.network_use == model.network_offline or not impl.download_sources) and not impl.is_available(self.config.stores):
 322                                 if not impl.download_sources:
 323                                         return _("No retrieval methods")
 324                                 return _("Not cached and we are off-line")
 325                         if impl.os not in arch.os_ranks:
 326                                 return _("Unsupported OS")
 327                         if impl.machine not in arch.machine_ranks:
 328                                 if impl.machine == 'src':
 329                                         return _("Source code")
 330                                 return _("Unsupported machine type")
 331                         return None
 332
 333                 def usable_feeds(iface, arch):
 334                         """Return all feeds for iface that support arch.
 335                         @rtype: generator(ZeroInstallFeed)"""
 336                         yield iface.uri
 337
 338                         for f in iface_cache.get_feed_imports(iface):
 339                                 # Note: when searching for src, None is not in machine_ranks
 340                                 if f.os in arch.os_ranks and \
 341                                    (f.machine is None or f.machine in arch.machine_ranks):
 342                                         yield f.uri
 343                                 else:
 344                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 345                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 346
 347                 # If requiring_var is True then all of requirer's dependencies must be satisfied.
 348                 # requirer can be a <command> or an <implementation>
 349                 def process_dependencies(requiring_var, requirer, arch):
 350                         for d in deps_in_use(requirer, arch):
 351                                 debug(_("Considering command dependency %s"), d)
 352
 353                                 add_iface(d.interface, arch.child_arch)
 354
 355                                 for c in d.get_required_commands():
 356                                         # We depend on a specific command within the implementation.
 357                                         command_vars = add_command_iface(d.interface, arch.child_arch, c)
 358
 359                                         # If the parent command/impl is chosen, one of the candidate commands
 360                                         # must be too. If there aren't any, then this command is unselectable.
 361                                         problem.add_clause([sat.neg(requiring_var)] + command_vars)
 362
 363                                 # Must choose one version of d if impl is selected
 364                                 find_dependency_candidates(requiring_var, d)
 365
 366                 def add_iface(uri, arch):
 367                         """Name implementations from feed and assert that only one can be selected."""
 368                         if uri in ifaces_processed: return
 369                         ifaces_processed.add(uri)
 370
 371                         iface = iface_cache.get_interface(uri)
 372
 373                         impls = []
 374                         for f in usable_feeds(iface, arch):
 375                                 self.feeds_used.add(f)
 376                                 debug(_("Processing feed %s"), f)
 377
 378                                 try:
 379                                         feed = iface_cache.get_feed(f)
 380                                         if feed is None: continue
 381                                         #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 382                                         #       info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 383
 384                                         if feed.implementations:
 385                                                 impls.extend(feed.implementations.values())
 386
 387                                         distro_feed_url = feed.get_distro_feed()
 388                                         if distro_feed_url:
 389                                                 self.feeds_used.add(distro_feed_url)
 390                                                 distro_feed = iface_cache.get_feed(distro_feed_url)
 391                                                 if distro_feed.implementations:
 392                                                         impls.extend(distro_feed.implementations.values())
 393                                 except MissingLocalFeed as ex:
 394                                         warn(_("Missing local feed; if it's no longer required, remove it with:") +
 395                                                         '\n0install remove-feed ' + iface.uri + ' ' + f,
 396                                                 {'feed': f, 'interface': iface, 'exception': ex})
 397                                 except Exception as ex:
 398                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': ex})
 399                                         #raise
 400
 401                         impls.sort(key = lambda impl: self.get_rating(iface, impl, arch), reverse = True)
 402
 403                         impls_for_iface[iface] = filtered_impls = []
 404
 405                         my_extra_restrictions = self.extra_restrictions.get(iface, [])
 406
 407                         if self.record_details:
 408                                 self.details[iface] = [(impl, get_unusable_reason(impl, my_extra_restrictions, arch)) for impl in impls]
 409
 410                         rank = 1
 411                         var_names = []
 412                         for impl in impls:
 413                                 if is_unusable(impl, my_extra_restrictions, arch):
 414                                         continue
 415
 416                                 filtered_impls.append(impl)
 417
 418                                 assert impl not in impl_to_var
 419                                 v = problem.add_variable(ImplInfo(iface, impl, arch))
 420                                 impl_to_var[impl] = v
 421                                 rank += 1
 422                                 var_names.append(v)
 423
 424                                 if impl.machine and impl.machine != 'src':
 425                                         impls_for_machine_group[machine_groups.get(impl.machine, 0)].append(v)
 426
 427                                 process_dependencies(v, impl, arch)
 428
 429                         if closest_match:
 430                                 dummy_impl = _DummyImpl()
 431                                 dummy_var = problem.add_variable(ImplInfo(iface, dummy_impl, arch, dummy = True))
 432                                 var_names.append(dummy_var)
 433                                 impl_to_var[dummy_impl] = dummy_var
 434                                 filtered_impls.append(dummy_impl)
 435
 436                         # Only one implementation of this interface can be selected
 437                         if uri == root_interface:
 438                                 if var_names:
 439                                         clause = problem.at_most_one(var_names)
 440                                         problem.add_clause(var_names)   # at least one
 441                                 else:
 442                                         problem.impossible()
 443                                         clause = False
 444                         elif var_names:
 445                                 clause = problem.at_most_one(var_names)
 446                         else:
 447                                 # Don't need to add to group_clause_for because we should
 448                                 # never get a possible selection involving this.
 449                                 return
 450
 451                         assert clause is not True
 452                         assert clause is not None
 453                         if clause is not False:
 454                                 group_clause_for[uri] = clause
 455
 456                 def add_command_iface(uri, arch, command_name):
 457                         """Add every <command> in interface 'uri' with this name.
 458                         Each one depends on the corresponding implementation and only
 459                         one can be selected. If closest_match is on, include a dummy
 460                         command that can always be selected."""
 461
 462                         # Check whether we've already processed this (interface,command) pair
 463                         existing = group_clause_for_command.get((uri, command_name), None)
 464                         if existing is not None:
 465                                 return existing.lits
 466
 467                         # First ensure that the interface itself has been processed
 468                         # We'll reuse the ordering of the implementations to order
 469                         # the commands too.
 470                         add_iface(uri, arch)
 471
 472                         iface = iface_cache.get_interface(uri)
 473                         filtered_impls = impls_for_iface[iface]
 474
 475                         var_names = []
 476                         for impl in filtered_impls:
 477                                 command = impl.commands.get(command_name, None)
 478                                 if not command:
 479                                         if not isinstance(impl, _DummyImpl):
 480                                                 # Mark implementation as unselectable
 481                                                 problem.add_clause([sat.neg(impl_to_var[impl])])
 482                                         continue
 483
 484                                 # We have a candidate <command>. Require that if it's selected
 485                                 # then we select the corresponding <implementation> too.
 486                                 command_var = problem.add_variable(CommandInfo(command_name, command, impl, arch))
 487                                 problem.add_clause([impl_to_var[impl], sat.neg(command_var)])
 488
 489                                 var_names.append(command_var)
 490
 491                                 process_dependencies(command_var, command, arch)
 492
 493                         # Tell the user why we couldn't use this version
 494                         if self.record_details:
 495                                 def new_reason(impl, old_reason):
 496                                         if command_name in impl.commands:
 497                                                 return old_reason
 498                                         return old_reason or (_('No %s command') % command_name)
 499                                 self.details[iface] = [(impl, new_reason(impl, reason)) for (impl, reason) in self.details[iface]]
 500
 501                         if closest_match:
 502                                 dummy_command = problem.add_variable(None)
 503                                 var_names.append(dummy_command)
 504
 505                         if var_names:
 506                                 # Can't select more than one of them.
 507                                 assert (uri, command_name) not in group_clause_for_command
 508                                 group_clause_for_command[(uri, command_name)] = problem.at_most_one(var_names)
 509
 510                         return var_names
 511
 512                 if command_name is None:
 513                         add_iface(root_interface, root_arch)
 514                 else:
 515                         commands = add_command_iface(root_interface, root_arch, command_name)
 516                         if len(commands) > int(closest_match):
 517                                 # (we have at least one non-dummy command)
 518                                 problem.add_clause(commands)            # At least one
 519                         else:
 520                                 # (note: might be because we haven't cached it yet)
 521                                 info("No %s <command> in %s", command_name, root_interface)
 522
 523                                 impls = impls_for_iface[iface_cache.get_interface(root_interface)]
 524                                 if impls == [] or (len(impls) == 1 and isinstance(impls[0], _DummyImpl)):
 525                                         # There were no candidates at all.
 526                                         if self.config.network_use == model.network_offline:
 527                                                 self._failure_reason = _("Interface '%s' has no usable implementations in the cache (and 0install is in off-line mode)") % root_interface
 528                                         else:
 529                                                 self._failure_reason = _("Interface '%s' has no usable implementations") % root_interface
 530                                 else:
 531                                         # We had some candidates implementations, but none for the command we need
 532                                         self._failure_reason = _("Interface '%s' cannot be executed directly; it is just a library "
 533                                                     "to be used by other programs (or missing '%s' command)") % (root_interface, command_name)
 534
 535                                 problem.impossible()
 536
 537                 # Require m<group> to be true if we select an implementation in that group
 538                 m_groups = []
 539                 for machine_group, impls in impls_for_machine_group.iteritems():
 540                         m_group = 'm%d' % machine_group
 541                         group_var = problem.add_variable(m_group)
 542                         if impls:
 543                                 for impl in impls:
 544                                         problem.add_clause([group_var, sat.neg(impl)])
 545                         m_groups.append(group_var)
 546                 if m_groups:
 547                         m_groups_clause = problem.at_most_one(m_groups)
 548                 else:
 549                         m_groups_clause = None
 550
 551                 def decide():
 552                         """Recurse through the current selections until we get to an interface with
 553                         no chosen version, then tell the solver to try the best version from that."""
 554
 555                         def find_undecided_dep(impl_or_command, arch):
 556                                 # Check for undecided dependencies of impl_or_command
 557                                 for dep in deps_in_use(impl_or_command, arch):
 558                                         for c in dep.get_required_commands():
 559                                                 dep_lit = find_undecided_command(dep.interface, c)
 560                                                 if dep_lit is not None:
 561                                                         return dep_lit
 562                                         dep_lit = find_undecided(dep.interface)
 563                                         if dep_lit is not None:
 564                                                 return dep_lit
 565                                 return None
 566
 567                         seen = set()
 568                         def find_undecided(uri):
 569                                 if uri in seen:
 570                                         return  # Break cycles
 571                                 seen.add(uri)
 572
 573                                 group = group_clause_for[uri]
 574                                 #print "Group for %s = %s" % (uri, group)
 575                                 lit = group.current
 576                                 if lit is None:
 577                                         return group.best_undecided()
 578                                 # else there was only one choice anyway
 579
 580                                 # Check for undecided dependencies
 581                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 582                                 return find_undecided_dep(lit_info.impl, lit_info.arch)
 583
 584                         def find_undecided_command(uri, name):
 585                                 if name is None: return find_undecided(uri)
 586
 587                                 group = group_clause_for_command[(uri, name)]
 588                                 lit = group.current
 589                                 if lit is None:
 590                                         return group.best_undecided()
 591                                 # else we've already chosen which <command> to use
 592
 593                                 # Check for undecided command-specific dependencies, and then for
 594                                 # implementation dependencies.
 595                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 596                                 if lit_info is None:
 597                                         assert closest_match
 598                                         return None     # (a dummy command added for better diagnostics; has no dependencies)
 599                                 return find_undecided_dep(lit_info.command, lit_info.arch) or \
 600                                        find_undecided_dep(lit_info.impl, lit_info.arch)
 601
 602                         best = find_undecided_command(root_interface, command_name)
 603                         if best is not None:
 604                                 return best
 605
 606                         # If we're chosen everything we need, we can probably
 607                         # set everything else to False.
 608                         for group in group_clause_for.values() + group_clause_for_command.values() + [m_groups_clause]:
 609                                 if group.current is None:
 610                                         best = group.best_undecided()
 611                                         if best is not None:
 612                                                 return sat.neg(best)
 613
 614                         return None                     # Failed to find any valid combination
 615
 616                 ready = problem.run_solver(decide) is True
 617
 618                 if not ready and not closest_match:
 619                         # We failed while trying to do a real solve.
 620                         # Try a closest match solve to get a better
 621                         # error report for the user.
 622                         self.solve(root_interface, root_arch, command_name = command_name, closest_match = True)
 623                 else:
 624                         self.ready = ready and not closest_match
 625                         self.selections = selections.Selections(None)
 626                         self.selections.interface = root_interface
 627
 628                         sels = self.selections.selections
 629
 630                         commands_needed = []
 631
 632                         # Popular sels with the selected implementations.
 633                         # Also, note down all the commands we need.
 634                         for uri, group in group_clause_for.iteritems():
 635                                 if group.current is not None:
 636                                         lit_info = problem.get_varinfo_for_lit(group.current).obj
 637                                         if lit_info.is_dummy:
 638                                                 sels[lit_info.iface.uri] = None
 639                                         else:
 640                                                 # We selected an implementation for interface 'uri'
 641                                                 impl = lit_info.impl
 642
 643                                                 for b in impl.bindings:
 644                                                         c = b.command
 645                                                         if c is not None:
 646                                                                 commands.append((uri, c))
 647
 648                                                 deps = self.requires[lit_info.iface] = []
 649                                                 for dep in deps_in_use(lit_info.impl, lit_info.arch):
 650                                                         deps.append(dep)
 651                                                         for c in dep.get_required_commands():
 652                                                                 commands_needed.append((dep.interface, c))
 653
 654                                                 sels[lit_info.iface.uri] = selections.ImplSelection(lit_info.iface.uri, impl, deps)
 655
 656                         # Now all all the commands in too.
 657                         def add_command(iface, name):
 658                                 sel = sels.get(iface, None)
 659                                 if sel:
 660                                         command = sel.impl.commands[name]
 661                                         if name in sel._used_commands:
 662                                                 return  # Already added
 663                                         sel._used_commands.add(name)
 664
 665                                         for dep in command.requires:
 666                                                 for dep_command_name in dep.get_required_commands():
 667                                                         add_command(dep.interface, dep_command_name)
 668
 669                                         # A <command> can depend on another <command> in the same interface
 670                                         # (e.g. the tests depending on the main program)
 671                                         for b in command.bindings:
 672                                                 c = b.command
 673                                                 if c is not None:
 674                                                         add_command(iface, c)
 675
 676                         for iface, command in commands_needed:
 677                                 add_command(iface, command)
 678
 679                         if command_name is not None:
 680                                 self.selections.command = command_name
 681                                 add_command(root_interface, command_name)
 682
 683         def get_failure_reason(self):
 684                 """Return an exception explaining why the solve failed."""
 685                 assert not self.ready
 686
 687                 if self._failure_reason:
 688                         return model.SafeException(self._failure_reason)
 689
 690                 return model.SafeException(_("Can't find all required implementations:") + '\n' +
 691                                 '\n'.join(["- %s -> %s" % (iface, self.selections[iface])
 692                                            for iface  in self.selections]))
 693
 694 DefaultSolver = SATSolver