zeroinstall/injector/solver.py

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