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