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