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 import model, sat, selections, arch
  14
  15 class CommandInfo:
  16         def __init__(self, name, command, impl, arch):
  17                 self.name = name
  18                 self.command = command
  19                 self.impl = impl
  20                 self.arch = arch
  21
  22         def __repr__(self):
  23                 name = "%s_%s_%s_%s" % (self.impl.feed.get_name(), self.impl.get_version(), self.impl.arch, self.name)
  24                 return name.replace('-', '_').replace('.', '_')
  25
  26 class ImplInfo:
  27         is_dummy = False
  28
  29         def __init__(self, iface, impl, arch, dummy = False):
  30                 self.iface = iface
  31                 self.impl = impl
  32                 self.arch = arch
  33                 if dummy:
  34                         self.is_dummy = True
  35
  36         def __repr__(self):
  37                 name = "%s_%s_%s" % (self.impl.feed.get_name(), self.impl.get_version(), self.impl.arch)
  38                 return name.replace('-', '_').replace('.', '_')
  39
  40 class _DummyImpl(object):
  41         requires = []
  42         version = None
  43         arch = None
  44         commands = {}
  45
  46         def __repr__(self):
  47                 return "dummy"
  48
  49         feed = property(lambda self: self)
  50
  51         def get_version(self):
  52                 return "dummy"
  53
  54         def get_name(self):
  55                 return "dummy"
  56
  57 class _ForceImpl(model.Restriction):
  58         """Used by L{SATSolver.justify_decision}."""
  59
  60         def __init__(self, impl_id):
  61                 self.impl_id = impl_id
  62
  63         def meets_restriction(self, impl):
  64                 return impl.id == self.impl_id
  65
  66 class Solver(object):
  67         """Chooses a set of implementations to satisfy the requirements of a program and its user.
  68         Typical use:
  69          1. Create a Solver object and configure it
  70          2. Call L{solve}.
  71          3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
  72          4. If it is 'ready' then you can download and run the chosen versions.
  73         @ivar selections: the chosen implementation of each interface
  74         @type selections: L{selections.Selections}
  75         @ivar requires: the selected dependencies for each chosen version
  76         @type requires: {L{model.Interface}: [L{model.Dependency}]}
  77         @ivar feeds_used: the feeds which contributed to the choice in L{selections}
  78         @type feeds_used: set(str)
  79         @ivar record_details: whether to record information about unselected implementations
  80         @type record_details: {L{Interface}: [(L{Implementation}, str)]}
  81         @ivar details: extra information, if record_details mode was used
  82         @type details: {str: [(Implementation, comment)]}
  83         """
  84         __slots__ = ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
  85
  86         def __init__(self):
  87                 self.selections = self.requires = self.feeds_used = self.details = None
  88                 self.record_details = False
  89                 self.ready = False
  90
  91         def solve_for(self, requirements):
  92                 """Solve for given requirements.
  93                 @param requirements: the interface, architecture and command to solve for
  94                 @type requirements: L{requirements.Requirements}
  95                 @postcondition: self.ready, self.selections and self.feeds_used are updated
  96                 @since: 1.8"""
  97                 root_arch = arch.get_architecture(requirements.os, requirements.cpu)
  98                 if requirements.source:
  99                         root_arch = arch.SourceArchitecture(root_arch)
 100                 return self.solve(requirements.interface_uri, root_arch, requirements.command)
 101
 102         def solve(self, root_interface, root_arch, command_name = 'run'):
 103                 """Get the best implementation of root_interface and all of its dependencies.
 104                 @param root_interface: the URI of the program to be solved
 105                 @type root_interface: str
 106                 @param root_arch: the desired target architecture
 107                 @type root_arch: L{arch.Architecture}
 108                 @param command_name: which <command> element to select
 109                 @type command_name: str | None
 110                 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
 111                 raise NotImplementedError("Abstract")
 112
 113 class SATSolver(Solver):
 114         """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them.
 115         @ivar langs: the preferred languages (e.g. ["es_ES", "en"]). Initialised to the current locale.
 116         @type langs: str"""
 117
 118         __slots__ = ['_failure_reason', 'config', 'extra_restrictions', '_lang_ranks', '_langs']
 119
 120         @property
 121         def iface_cache(self):
 122                 return self.config.iface_cache  # (deprecated; used by 0compile)
 123
 124         def __init__(self, config, extra_restrictions = None):
 125                 """
 126                 @param config: policy preferences (e.g. stability), the iface_cache and the stores to use
 127                 @type config: L{policy.Config}
 128                 @param extra_restrictions: extra restrictions on the chosen implementations
 129                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
 130                 """
 131                 Solver.__init__(self)
 132                 assert not isinstance(config, str), "API change!"
 133                 self.config = config
 134                 self.extra_restrictions = extra_restrictions or {}
 135
 136                 # By default, prefer the current locale's language first and English second
 137                 self.langs = [locale.getlocale()[0] or 'en', 'en']
 138
 139         def set_langs(self, langs):
 140                 """Set the preferred languages.
 141                 @param langs: languages (and regions), first choice first
 142                 @type langs: [str]
 143                 """
 144                 # _lang_ranks is a map from locale string to score (higher is better)
 145                 _lang_ranks = {}
 146                 score = 0
 147                 i = len(langs)
 148                 # (is there are duplicates, the first occurance takes precedence)
 149                 while i > 0:
 150                         i -= 1
 151                         lang = langs[i].replace('_', '-')
 152                         _lang_ranks[lang.split('-')[0]] = score
 153                         _lang_ranks[lang] = score + 1
 154                         score += 2
 155                 self._langs = langs
 156                 self._lang_ranks = _lang_ranks
 157
 158         langs = property(lambda self: self._langs, set_langs)
 159
 160         def get_rating(self, interface, impl, arch):
 161                 impl_langs = (impl.langs or 'en').split()
 162                 my_langs = self._lang_ranks
 163
 164                 stores = self.config.stores
 165                 is_available = impl.is_available(stores)
 166
 167                 # Stability
 168                 stab_policy = interface.stability_policy
 169                 if not stab_policy:
 170                         if self.config.help_with_testing: stab_policy = model.testing
 171                         else: stab_policy = model.stable
 172
 173                 stability = impl.get_stability()
 174                 if stability >= stab_policy:
 175                         stability_limited = model.preferred
 176                 else:
 177                         stability_limited = stability
 178
 179                 # Note: this list must match _ranking_component_reason above
 180                 return [
 181                         # Languages we understand come first
 182                         max(my_langs.get(l.split('-')[0], -1) for l in impl_langs),
 183
 184                         # Preferred versions come first
 185                         stability == model.preferred,
 186
 187                         # Prefer available implementations next if we have limited network access
 188                         self.config.network_use != model.network_full and is_available,
 189
 190                         # Packages that require admin access to install come last
 191                         not impl.requires_root_install,
 192
 193                         # Prefer more stable versions, but treat everything over stab_policy the same
 194                         # (so we prefer stable over testing if the policy is to prefer "stable", otherwise
 195                         # we don't care)
 196                         stability_limited,
 197
 198                         # Newer versions come before older ones (ignoring modifiers)
 199                         impl.version[0],
 200
 201                         # Prefer native packages if the main part of the versions are the same
 202                         impl.id.startswith('package:'),
 203
 204                         # Full version compare (after package check, since comparing modifiers between native and non-native
 205                         # packages doesn't make sense).
 206                         impl.version,
 207
 208                         # Get best OS
 209                         -arch.os_ranks.get(impl.os, 999),
 210
 211                         # Get best machine
 212                         -arch.machine_ranks.get(impl.machine, 999),
 213
 214                         # Slightly prefer languages specialised to our country
 215                         # (we know a and b have the same base language at this point)
 216                         max(my_langs.get(l, -1) for l in impl_langs),
 217
 218                         # Slightly prefer cached versions
 219                         is_available,
 220
 221                         # Order by ID so the order isn't random
 222                         impl.id
 223                 ]
 224
 225         def solve(self, root_interface, root_arch, command_name = 'run', closest_match = False):
 226                 # closest_match is used internally. It adds a lowest-ranked
 227                 # by valid implementation to every interface, so we can always
 228                 # select something. Useful for diagnostics.
 229
 230                 # The basic plan is this:
 231                 # 1. Scan the root interface and all dependencies recursively, building up a SAT problem.
 232                 # 2. Solve the SAT problem. Whenever there are multiple options, try the most preferred one first.
 233                 # 3. Create a Selections object from the results.
 234                 #
 235                 # All three involve recursively walking the tree in a similar way:
 236                 # 1) we follow every dependency of every implementation (order not important)
 237                 # 2) we follow every dependency of every selected implementation (better versions first)
 238                 # 3) we follow every dependency of every selected implementation (order doesn't matter)
 239                 #
 240                 # In all cases, a dependency may be on an <implementation> or on a specific <command>.
 241
 242                 # TODO: We need some way to figure out which feeds to include.
 243                 # Currently, we include any feed referenced from anywhere but
 244                 # this is probably too much. We could insert a dummy optimial
 245                 # implementation in stale/uncached feeds and see whether it
 246                 # selects that.
 247                 iface_cache = self.config.iface_cache
 248
 249                 problem = sat.SATProblem()
 250
 251                 impl_to_var = {}        # Impl -> sat var
 252                 self.feeds_used = set()
 253                 self.requires = {}
 254                 self.ready = False
 255                 self.details = self.record_details and {}
 256
 257                 self.selections = None
 258                 self._failure_reason = None
 259
 260                 ifaces_processed = set()
 261
 262                 machine_groups = arch.machine_groups
 263                 impls_for_machine_group = {0 : []}              # Machine group (e.g. "64") to [impl] in that group
 264                 for machine_group in machine_groups.values():
 265                         impls_for_machine_group[machine_group] = []
 266
 267                 impls_for_iface = {}    # Iface -> [impl]
 268
 269                 group_clause_for = {}   # Iface URI -> AtMostOneClause | bool
 270                 group_clause_for_command = {}   # (Iface URI, command name) -> AtMostOneClause | bool
 271
 272                 # Return the dependencies of impl that we should consider.
 273                 # Skips dependencies if the use flag isn't what we need.
 274                 # (note: impl may also be a model.Command)
 275                 def deps_in_use(impl, arch):
 276                         for dep in impl.requires:
 277                                 use = dep.metadata.get("use", None)
 278                                 if use not in arch.use:
 279                                         continue
 280                                 yield dep
 281
 282                 # Must have already done add_iface on dependency.interface.
 283                 # If dependency is essential:
 284                 #   Add a clause so that if requiring_impl_var is True then an implementation
 285                 #   matching 'dependency' must also be selected.
 286                 # If dependency is optional:
 287                 #   Require that no incompatible version is selected.
 288                 # This ignores any 'command' required. Handle that separately.
 289                 def find_dependency_candidates(requiring_impl_var, dependency):
 290                         def meets_restrictions(candidate):
 291                                 for r in dependency.restrictions:
 292                                         if not r.meets_restriction(candidate):
 293                                                 #warn("%s rejected due to %s", candidate.get_version(), r)
 294                                                 return False
 295                                 return True
 296
 297                         essential = dependency.importance == model.Dependency.Essential
 298
 299                         dep_iface = iface_cache.get_interface(dependency.interface)
 300                         dep_union = [sat.neg(requiring_impl_var)]       # Either requiring_impl_var is False, or ...
 301                         for candidate in impls_for_iface[dep_iface]:
 302                                 if (candidate.__class__ is _DummyImpl) or meets_restrictions(candidate):
 303                                         if essential:
 304                                                 c_var = impl_to_var.get(candidate, None)
 305                                                 if c_var is not None:
 306                                                         dep_union.append(c_var)
 307                                                 # else we filtered that version out, so ignore it
 308                                 else:
 309                                         # Candidate doesn't meet our requirements
 310                                         # If the dependency is optional add a rule to make sure we don't
 311                                         # select this candidate.
 312                                         # (for essential dependencies this isn't necessary because we must
 313                                         # select a good version and we can't select two)
 314                                         if not essential:
 315                                                 c_var = impl_to_var.get(candidate, None)
 316                                                 if c_var is not None:
 317                                                         problem.add_clause(dep_union + [sat.neg(c_var)])
 318                                                 # else we filtered that version out, so ignore it
 319
 320                         if essential:
 321                                 problem.add_clause(dep_union)
 322
 323                 def is_unusable(impl, restrictions, arch):
 324                         """@return: whether this implementation is unusable.
 325                         @rtype: bool"""
 326                         return get_unusable_reason(impl, restrictions, arch) != None
 327
 328                 def get_unusable_reason(impl, restrictions, arch):
 329                         """
 330                         @param impl: Implementation to test.
 331                         @type restrictions: [L{model.Restriction}]
 332                         @return: The reason why this impl is unusable, or None if it's OK.
 333                         @rtype: str
 334                         @note: The restrictions are for the interface being requested, not the feed
 335                         of the implementation; they may be different when feeds are being used."""
 336                         for r in restrictions:
 337                                 if not r.meets_restriction(impl):
 338                                         return _("Incompatible with another selected implementation")
 339                         stability = impl.get_stability()
 340                         if stability <= model.buggy:
 341                                 return stability.name
 342                         if (self.config.network_use == model.network_offline or not impl.download_sources) and not impl.is_available(self.config.stores):
 343                                 if not impl.download_sources:
 344                                         return _("No retrieval methods")
 345                                 return _("Not cached and we are off-line")
 346                         if impl.os not in arch.os_ranks:
 347                                 return _("Unsupported OS")
 348                         if impl.machine not in arch.machine_ranks:
 349                                 if impl.machine == 'src':
 350                                         return _("Source code")
 351                                 elif 'src' in arch.machine_ranks:
 352                                         return _("Not source code")
 353                                 return _("Unsupported machine type")
 354                         return None
 355
 356                 def usable_feeds(iface, arch):
 357                         """Return all feeds for iface that support arch.
 358                         @rtype: generator(ZeroInstallFeed)"""
 359                         yield iface.uri
 360
 361                         for f in iface_cache.get_feed_imports(iface):
 362                                 # Note: when searching for src, None is not in machine_ranks
 363                                 if f.os in arch.os_ranks and \
 364                                    (f.machine is None or f.machine in arch.machine_ranks):
 365                                         yield f.uri
 366                                 else:
 367                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 368                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 369
 370                 # If requiring_var is True then all of requirer's dependencies must be satisfied.
 371                 # requirer can be a <command> or an <implementation>
 372                 def process_dependencies(requiring_var, requirer, arch):
 373                         for d in deps_in_use(requirer, arch):
 374                                 debug(_("Considering command dependency %s"), d)
 375
 376                                 add_iface(d.interface, arch.child_arch)
 377
 378                                 for c in d.get_required_commands():
 379                                         # We depend on a specific command within the implementation.
 380                                         command_vars = add_command_iface(d.interface, arch.child_arch, c)
 381
 382                                         # If the parent command/impl is chosen, one of the candidate commands
 383                                         # must be too. If there aren't any, then this command is unselectable.
 384                                         problem.add_clause([sat.neg(requiring_var)] + command_vars)
 385
 386                                 # Must choose one version of d if impl is selected
 387                                 find_dependency_candidates(requiring_var, d)
 388
 389                 def add_iface(uri, arch):
 390                         """Name implementations from feed and assert that only one can be selected."""
 391                         if uri in ifaces_processed: return
 392                         ifaces_processed.add(uri)
 393
 394                         iface = iface_cache.get_interface(uri)
 395
 396                         impls = []
 397                         for f in usable_feeds(iface, arch):
 398                                 self.feeds_used.add(f)
 399                                 debug(_("Processing feed %s"), f)
 400
 401                                 try:
 402                                         feed = iface_cache.get_feed(f)
 403                                         if feed is None: continue
 404                                         #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 405                                         #       info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 406
 407                                         if feed.implementations:
 408                                                 impls.extend(feed.implementations.values())
 409
 410                                         distro_feed_url = feed.get_distro_feed()
 411                                         if distro_feed_url:
 412                                                 self.feeds_used.add(distro_feed_url)
 413                                                 distro_feed = iface_cache.get_feed(distro_feed_url)
 414                                                 if distro_feed.implementations:
 415                                                         impls.extend(distro_feed.implementations.values())
 416                                 except MissingLocalFeed as ex:
 417                                         warn(_("Missing local feed; if it's no longer required, remove it with:") +
 418                                                         '\n0install remove-feed ' + iface.uri + ' ' + f,
 419                                                 {'feed': f, 'interface': iface, 'exception': ex})
 420                                 except Exception as ex:
 421                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': ex})
 422                                         #raise
 423
 424                         impls.sort(key = lambda impl: self.get_rating(iface, impl, arch), reverse = True)
 425
 426                         impls_for_iface[iface] = filtered_impls = []
 427
 428                         my_extra_restrictions = self.extra_restrictions.get(iface, [])
 429
 430                         if self.record_details:
 431                                 self.details[iface] = [(impl, get_unusable_reason(impl, my_extra_restrictions, arch)) for impl in impls]
 432
 433                         var_names = []
 434                         for impl in impls:
 435                                 if is_unusable(impl, my_extra_restrictions, arch):
 436                                         continue
 437
 438                                 filtered_impls.append(impl)
 439
 440                                 assert impl not in impl_to_var
 441                                 v = problem.add_variable(ImplInfo(iface, impl, arch))
 442                                 impl_to_var[impl] = v
 443                                 var_names.append(v)
 444
 445                                 if impl.machine and impl.machine != 'src':
 446                                         impls_for_machine_group[machine_groups.get(impl.machine, 0)].append(v)
 447
 448                                 process_dependencies(v, impl, arch)
 449
 450                         if closest_match:
 451                                 dummy_impl = _DummyImpl()
 452                                 dummy_var = problem.add_variable(ImplInfo(iface, dummy_impl, arch, dummy = True))
 453                                 var_names.append(dummy_var)
 454                                 impl_to_var[dummy_impl] = dummy_var
 455                                 filtered_impls.append(dummy_impl)
 456
 457                         # Only one implementation of this interface can be selected
 458                         if uri == root_interface:
 459                                 if var_names:
 460                                         clause = problem.at_most_one(var_names)
 461                                         problem.add_clause(var_names)   # at least one
 462                                 else:
 463                                         problem.impossible()
 464                                         clause = False
 465                         elif var_names:
 466                                 clause = problem.at_most_one(var_names)
 467                         else:
 468                                 # Don't need to add to group_clause_for because we should
 469                                 # never get a possible selection involving this.
 470                                 return
 471
 472                         assert clause is not True
 473                         assert clause is not None
 474                         if clause is not False:
 475                                 group_clause_for[uri] = clause
 476
 477                 def add_command_iface(uri, arch, command_name):
 478                         """Add every <command> in interface 'uri' with this name.
 479                         Each one depends on the corresponding implementation and only
 480                         one can be selected. If closest_match is on, include a dummy
 481                         command that can always be selected."""
 482
 483                         # Check whether we've already processed this (interface,command) pair
 484                         existing = group_clause_for_command.get((uri, command_name), None)
 485                         if existing is not None:
 486                                 return existing.lits
 487
 488                         # First ensure that the interface itself has been processed
 489                         # We'll reuse the ordering of the implementations to order
 490                         # the commands too.
 491                         add_iface(uri, arch)
 492
 493                         iface = iface_cache.get_interface(uri)
 494                         filtered_impls = impls_for_iface[iface]
 495
 496                         var_names = []
 497                         for impl in filtered_impls:
 498                                 command = impl.commands.get(command_name, None)
 499                                 if not command:
 500                                         if not isinstance(impl, _DummyImpl):
 501                                                 # Mark implementation as unselectable
 502                                                 problem.add_clause([sat.neg(impl_to_var[impl])])
 503                                         continue
 504
 505                                 # We have a candidate <command>. Require that if it's selected
 506                                 # then we select the corresponding <implementation> too.
 507                                 command_var = problem.add_variable(CommandInfo(command_name, command, impl, arch))
 508                                 problem.add_clause([impl_to_var[impl], sat.neg(command_var)])
 509
 510                                 var_names.append(command_var)
 511
 512                                 process_dependencies(command_var, command, arch)
 513
 514                         # Tell the user why we couldn't use this version
 515                         if self.record_details:
 516                                 def new_reason(impl, old_reason):
 517                                         if command_name in impl.commands:
 518                                                 return old_reason
 519                                         return old_reason or (_('No %s command') % command_name)
 520                                 self.details[iface] = [(impl, new_reason(impl, reason)) for (impl, reason) in self.details[iface]]
 521
 522                         if closest_match:
 523                                 dummy_command = problem.add_variable(None)
 524                                 var_names.append(dummy_command)
 525
 526                         if var_names:
 527                                 # Can't select more than one of them.
 528                                 assert (uri, command_name) not in group_clause_for_command
 529                                 group_clause_for_command[(uri, command_name)] = problem.at_most_one(var_names)
 530
 531                         return var_names
 532
 533                 if command_name is None:
 534                         add_iface(root_interface, root_arch)
 535                 else:
 536                         commands = add_command_iface(root_interface, root_arch, command_name)
 537                         if len(commands) > int(closest_match):
 538                                 # (we have at least one non-dummy command)
 539                                 problem.add_clause(commands)            # At least one
 540                         else:
 541                                 # (note: might be because we haven't cached it yet)
 542                                 info("No %s <command> in %s", command_name, root_interface)
 543
 544                                 impls = impls_for_iface[iface_cache.get_interface(root_interface)]
 545                                 if impls == [] or (len(impls) == 1 and isinstance(impls[0], _DummyImpl)):
 546                                         # There were no candidates at all.
 547                                         if self.config.network_use == model.network_offline:
 548                                                 self._failure_reason = _("Interface '%s' has no usable implementations in the cache (and 0install is in off-line mode)") % root_interface
 549                                         else:
 550                                                 self._failure_reason = _("Interface '%s' has no usable implementations") % root_interface
 551                                 else:
 552                                         # We had some candidates implementations, but none for the command we need
 553                                         self._failure_reason = _("Interface '%s' cannot be executed directly; it is just a library "
 554                                                     "to be used by other programs (or missing '%s' command)") % (root_interface, command_name)
 555
 556                                 problem.impossible()
 557
 558                 # Require m<group> to be true if we select an implementation in that group
 559                 m_groups = []
 560                 for machine_group, impls in impls_for_machine_group.iteritems():
 561                         m_group = 'm%d' % machine_group
 562                         group_var = problem.add_variable(m_group)
 563                         if impls:
 564                                 for impl in impls:
 565                                         problem.add_clause([group_var, sat.neg(impl)])
 566                         m_groups.append(group_var)
 567                 if m_groups:
 568                         m_groups_clause = problem.at_most_one(m_groups)
 569                 else:
 570                         m_groups_clause = None
 571
 572                 def decide():
 573                         """Recurse through the current selections until we get to an interface with
 574                         no chosen version, then tell the solver to try the best version from that."""
 575
 576                         def find_undecided_dep(impl_or_command, arch):
 577                                 # Check for undecided dependencies of impl_or_command
 578                                 for dep in deps_in_use(impl_or_command, arch):
 579                                         for c in dep.get_required_commands():
 580                                                 dep_lit = find_undecided_command(dep.interface, c)
 581                                                 if dep_lit is not None:
 582                                                         return dep_lit
 583                                         dep_lit = find_undecided(dep.interface)
 584                                         if dep_lit is not None:
 585                                                 return dep_lit
 586                                 return None
 587
 588                         seen = set()
 589                         def find_undecided(uri):
 590                                 if uri in seen:
 591                                         return  # Break cycles
 592                                 seen.add(uri)
 593
 594                                 group = group_clause_for.get(uri, None)
 595
 596                                 if group is None:
 597                                         # (can be None if the selected impl has an optional dependency on
 598                                         # a feed with no implementations)
 599                                         return
 600
 601                                 #print "Group for %s = %s" % (uri, group)
 602                                 lit = group.current
 603                                 if lit is None:
 604                                         return group.best_undecided()
 605                                 # else there was only one choice anyway
 606
 607                                 # Check for undecided dependencies
 608                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 609                                 return find_undecided_dep(lit_info.impl, lit_info.arch)
 610
 611                         def find_undecided_command(uri, name):
 612                                 if name is None: return find_undecided(uri)
 613
 614                                 group = group_clause_for_command[(uri, name)]
 615                                 lit = group.current
 616                                 if lit is None:
 617                                         return group.best_undecided()
 618                                 # else we've already chosen which <command> to use
 619
 620                                 # Check for undecided command-specific dependencies, and then for
 621                                 # implementation dependencies.
 622                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 623                                 if lit_info is None:
 624                                         assert closest_match
 625                                         return None     # (a dummy command added for better diagnostics; has no dependencies)
 626                                 return find_undecided_dep(lit_info.command, lit_info.arch) or \
 627                                        find_undecided_dep(lit_info.impl, lit_info.arch)
 628
 629                         best = find_undecided_command(root_interface, command_name)
 630                         if best is not None:
 631                                 return best
 632
 633                         # If we're chosen everything we need, we can probably
 634                         # set everything else to False.
 635                         for group in group_clause_for.values() + group_clause_for_command.values() + [m_groups_clause]:
 636                                 if group.current is None:
 637                                         best = group.best_undecided()
 638                                         if best is not None:
 639                                                 return sat.neg(best)
 640
 641                         return None                     # Failed to find any valid combination
 642
 643                 ready = problem.run_solver(decide) is True
 644
 645                 if not ready and not closest_match:
 646                         # We failed while trying to do a real solve.
 647                         # Try a closest match solve to get a better
 648                         # error report for the user.
 649                         self.solve(root_interface, root_arch, command_name = command_name, closest_match = True)
 650                 else:
 651                         self.ready = ready and not closest_match
 652                         self.selections = selections.Selections(None)
 653                         self.selections.interface = root_interface
 654
 655                         sels = self.selections.selections
 656
 657                         commands_needed = []
 658
 659                         # Populate sels with the selected implementations.
 660                         # Also, note down all the commands we need.
 661                         for uri, group in group_clause_for.iteritems():
 662                                 if group.current is not None:
 663                                         lit_info = problem.get_varinfo_for_lit(group.current).obj
 664                                         if lit_info.is_dummy:
 665                                                 sels[lit_info.iface.uri] = None
 666                                         else:
 667                                                 # We selected an implementation for interface 'uri'
 668                                                 impl = lit_info.impl
 669
 670                                                 for b in impl.bindings:
 671                                                         c = b.command
 672                                                         if c is not None:
 673                                                                 commands.append((uri, c))
 674
 675                                                 deps = self.requires[lit_info.iface] = []
 676                                                 for dep in deps_in_use(lit_info.impl, lit_info.arch):
 677                                                         deps.append(dep)
 678                                                         for c in dep.get_required_commands():
 679                                                                 commands_needed.append((dep.interface, c))
 680
 681                                                 sels[lit_info.iface.uri] = selections.ImplSelection(lit_info.iface.uri, impl, deps)
 682
 683                         # Now all all the commands in too.
 684                         def add_command(iface, name):
 685                                 sel = sels.get(iface, None)
 686                                 if sel:
 687                                         command = sel.impl.commands[name]
 688                                         if name in sel._used_commands:
 689                                                 return  # Already added
 690                                         sel._used_commands.add(name)
 691
 692                                         for dep in command.requires:
 693                                                 for dep_command_name in dep.get_required_commands():
 694                                                         add_command(dep.interface, dep_command_name)
 695
 696                                         # A <command> can depend on another <command> in the same interface
 697                                         # (e.g. the tests depending on the main program)
 698                                         for b in command.bindings:
 699                                                 c = b.command
 700                                                 if c is not None:
 701                                                         add_command(iface, c)
 702
 703                         for iface, command in commands_needed:
 704                                 add_command(iface, command)
 705
 706                         if command_name is not None:
 707                                 self.selections.command = command_name
 708                                 add_command(root_interface, command_name)
 709
 710         def get_failure_reason(self):
 711                 """Return an exception explaining why the solve failed."""
 712                 assert not self.ready
 713
 714                 if self._failure_reason:
 715                         return model.SafeException(self._failure_reason)
 716
 717                 return model.SafeException(_("Can't find all required implementations:") + '\n' +
 718                                 '\n'.join(["- %s -> %s" % (iface, self.selections[iface])
 719                                            for iface  in self.selections]))
 720
 721         def justify_decision(self, requirements, iface, impl):
 722                 """Run a solve with impl_id forced to be selected, and explain why it wasn't (or was)
 723                 selected in the normal case."""
 724                 assert isinstance(iface, model.Interface), iface
 725
 726                 restrictions = self.extra_restrictions.copy()
 727                 restrictions[iface] = restrictions.get(iface, []) + [_ForceImpl(impl.id)]
 728                 s = SATSolver(self.config, restrictions)
 729                 s.record_details = True
 730                 s.solve_for(requirements)
 731
 732                 wanted = "{iface} {version}".format(iface = iface.get_name(), version = impl.get_version())
 733
 734                 # Could a selection involving impl even be valid?
 735                 if not s.ready or iface.uri not in s.selections.selections:
 736                         reasons = s.details.get(iface, [])
 737                         for (rid, rstr) in reasons:
 738                                 if rid.id == impl.id and rstr is not None:
 739                                         return _("{wanted} cannot be used (regardless of other components): {reason}").format(
 740                                                         wanted = wanted,
 741                                                         reason = rstr)
 742
 743                         if not s.ready:
 744                                 return _("There is no possible selection using {wanted}.\n{reason}").format(
 745                                         wanted = wanted,
 746                                         reason = s.get_failure_reason())
 747
 748                 actual_selection = self.selections.get(iface, None)
 749                 if actual_selection is not None:
 750                         # Was impl actually selected anyway?
 751                         if actual_selection.id == impl.id:
 752                                 return _("{wanted} was selected as the preferred version.").format(wanted = wanted)
 753
 754                         # Was impl ranked below the selected version?
 755                         iface_arch = arch.get_architecture(requirements.os, requirements.cpu)
 756                         if requirements.source and iface.uri == requirements.interface_uri:
 757                                 iface_arch = arch.SourceArchitecture(iface_arch)
 758                         wanted_rating = self.get_rating(iface, impl, arch)
 759                         selected_rating = self.get_rating(iface, actual_selection, arch)
 760
 761                         if wanted_rating < selected_rating:
 762                                 _ranking_component_reason = [
 763                                         _("natural languages we understand are preferred"),
 764                                         _("preferred versions come first"),
 765                                         _("locally-available versions are preferred when network use is limited"),
 766                                         _("packages that don't require admin access to install are preferred"),
 767                                         _("more stable versions preferred"),
 768                                         _("newer versions are preferred"),
 769                                         _("native packages are preferred"),
 770                                         _("newer versions are preferred"),
 771                                         _("better OS match"),
 772                                         _("better CPU match"),
 773                                         _("better locale match"),
 774                                         _("is locally available"),
 775                                         _("better ID (tie-breaker)"),
 776                                 ]
 777
 778                                 actual = actual_selection.get_version()
 779                                 if impl.get_version() == actual:
 780                                         def detail(i):
 781                                                 if len(i.id) < 18:
 782                                                         return " (" + i.id + ")"
 783                                                 else:
 784                                                         return " (" + i.id[:16] + "...)"
 785
 786                                         wanted += detail(impl)
 787                                         actual += detail(actual_selection)
 788
 789                                 for i in range(len(wanted_rating)):
 790                                         if wanted_rating[i] < selected_rating[i]:
 791                                                 return _("{wanted} is ranked lower than {actual}: {why}").format(
 792                                                                 wanted = wanted,
 793                                                                 actual = actual,
 794                                                                 why = _ranking_component_reason[i])
 795
 796                 used_impl = iface.uri in s.selections.selections
 797
 798                 # Impl is selectable and ranked higher than the selected version. Selecting it would cause
 799                 # a problem elsewhere.
 800                 changes = []
 801                 for old_iface, old_sel in self.selections.selections.iteritems():
 802                         if old_iface == iface.uri and used_impl: continue
 803                         new_sel = s.selections.selections.get(old_iface, None)
 804                         if new_sel is None:
 805                                 changes.append(_("{interface}: no longer used").format(interface = old_iface))
 806                         elif old_sel.version != new_sel.version:
 807                                 changes.append(_("{interface}: {old} to {new}").format(interface = old_iface, old = old_sel.version, new = new_sel.version))
 808                         elif old_sel.id != new_sel.id:
 809                                 changes.append(_("{interface}: {old} to {new}").format(interface = old_iface, old = old_sel.id, new = new_sel.id))
 810
 811                 if changes:
 812                         changes_text = '\n\n' + _('The changes would be:') + '\n\n' + '\n'.join(changes)
 813                 else:
 814                         changes_text = ''
 815
 816                 if used_impl:
 817                         return _("{wanted} is selectable, but using it would produce a less optimal solution overall.").format(wanted = wanted) + changes_text
 818                 else:
 819                         return _("If {wanted} were the only option, the best available solution wouldn't use it.").format(wanted = wanted) + changes_text
 820
 821 DefaultSolver = SATSolver