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