zeroinstall/injector/solver.py

   1 """
   2 Chooses a set of components to make a running program.
   3 """
   4
   5 # Copyright (C) 2009, Thomas Leonard
   6 # See the README file for details, or visit http://0install.net.
   7
   8 from zeroinstall import _
   9 import os, tempfile, subprocess, sys, locale
  10 from logging import debug, warn, info
  11
  12 from zeroinstall.zerostore import BadDigest, NotStored
  13
  14 from zeroinstall.injector.arch import machine_groups
  15 from zeroinstall.injector import model, sat, selections
  16
  17 def _get_cached(stores, impl):
  18         """Check whether an implementation is available locally.
  19         @type impl: model.Implementation
  20         @rtype: bool
  21         """
  22         if isinstance(impl, model.DistributionImplementation):
  23                 return impl.installed
  24         if impl.local_path:
  25                 return os.path.exists(impl.local_path)
  26         else:
  27                 try:
  28                         if not impl.digests:
  29                                 warn("No digests given for %s!", impl)
  30                                 return False
  31                         path = stores.lookup_any(impl.digests)
  32                         assert path
  33                         return True
  34                 except BadDigest:
  35                         return False
  36                 except NotStored:
  37                         return False
  38
  39 class ImplInfo:
  40         is_dummy = False
  41
  42         def __init__(self, iface, impl, arch, dummy = False):
  43                 self.iface = iface
  44                 self.impl = impl
  45                 self.arch = arch
  46                 if dummy:
  47                         self.is_dummy = True
  48
  49         def __repr__(self):
  50                 name = "%s_%s_%s" % (self.impl.feed.get_name(), self.impl.get_version(), self.impl.arch)
  51                 return name.replace('-', '_').replace('.', '_')
  52
  53 class _DummyImpl(object):
  54         requires = []
  55         version = None
  56         arch = None
  57
  58         def __repr__(self):
  59                 return "dummy"
  60
  61         feed = property(lambda self: self)
  62
  63         def get_version(self):
  64                 return "dummy"
  65
  66         def get_name(self):
  67                 return "dummy"
  68
  69 class Solver(object):
  70         """Chooses a set of implementations to satisfy the requirements of a program and its user.
  71         Typical use:
  72          1. Create a Solver object and configure it
  73          2. Call L{solve}.
  74          3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
  75          4. If it is 'ready' then you can download and run the chosen versions.
  76         @ivar selections: the chosen implementation of each interface
  77         @type selections: L{selections.Selections}
  78         @ivar requires: the selected dependencies for each chosen version
  79         @type requires: {L{model.Interface}: [L{model.Dependency}]}
  80         @ivar feeds_used: the feeds which contributed to the choice in L{selections}
  81         @type feeds_used: set(str)
  82         @ivar record_details: whether to record information about unselected implementations
  83         @type record_details: {L{Interface}: [(L{Implementation}, str)]}
  84         @ivar details: extra information, if record_details mode was used
  85         @type details: {str: [(Implementation, comment)]}
  86         """
  87         __slots__ = ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
  88
  89         def __init__(self):
  90                 self.selections = self.requires = self.feeds_used = self.details = None
  91                 self.record_details = False
  92                 self.ready = False
  93
  94         def solve(self, root_interface, root_arch):
  95                 """Get the best implementation of root_interface and all of its dependencies.
  96                 @param root_interface: the URI of the program to be solved
  97                 @type root_interface: str
  98                 @param root_arch: the desired target architecture
  99                 @type root_arch: L{arch.Architecture}
 100                 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
 101                 raise NotImplementedError("Abstract")
 102
 103 class SATSolver(Solver):
 104         """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them.
 105         @ivar langs: the preferred languages (e.g. ["es_ES", "en"]). Initialised to the current locale.
 106         @type langs: str"""
 107         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
 108                 """
 109                 @param network_use: how much use to make of the network
 110                 @type network_use: L{model.network_levels}
 111                 @param iface_cache: a cache of feeds containing information about available versions
 112                 @type iface_cache: L{iface_cache.IfaceCache}
 113                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
 114                 @type stores: L{zerostore.Stores}
 115                 @param extra_restrictions: extra restrictions on the chosen implementations
 116                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
 117                 """
 118                 Solver.__init__(self)
 119                 self.network_use = network_use
 120                 self.iface_cache = iface_cache
 121                 self.stores = stores
 122                 self.help_with_testing = False
 123                 self.extra_restrictions = extra_restrictions or {}
 124
 125                 self.langs = [locale.getlocale()[0] or 'en']
 126
 127         def compare(self, interface, b, a, arch):
 128                 """Compare a and b to see which would be chosen first.
 129                 Does not consider whether the implementations are usable (check for that yourself first).
 130                 @param interface: The interface we are trying to resolve, which may
 131                 not be the interface of a or b if they are from feeds.
 132                 @rtype: int"""
 133
 134                 # Languages we understand come first
 135                 a_langs = (a.langs or 'en').split()
 136                 b_langs = (b.langs or 'en').split()
 137                 main_langs = set(l.split('_')[0] for l in self.langs)
 138                 r = cmp(any(l.split('_')[0] in main_langs for l in a_langs),
 139                         any(l.split('_')[0] in main_langs for l in b_langs))
 140                 if r: return r
 141
 142                 a_stab = a.get_stability()
 143                 b_stab = b.get_stability()
 144
 145                 # Preferred versions come first
 146                 r = cmp(a_stab == model.preferred, b_stab == model.preferred)
 147                 if r: return r
 148
 149                 stores = self.stores
 150                 if self.network_use != model.network_full:
 151                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 152                         if r: return r
 153
 154                 # Packages that require admin access to install come last
 155                 r = cmp(b.requires_root_install, a.requires_root_install)
 156                 if r: return r
 157
 158                 # Stability
 159                 stab_policy = interface.stability_policy
 160                 if not stab_policy:
 161                         if self.help_with_testing: stab_policy = model.testing
 162                         else: stab_policy = model.stable
 163
 164                 if a_stab >= stab_policy: a_stab = model.preferred
 165                 if b_stab >= stab_policy: b_stab = model.preferred
 166
 167                 r = cmp(a_stab, b_stab)
 168                 if r: return r
 169
 170                 # Newer versions come before older ones
 171                 if a.id.startswith('package:') != b.id.startswith('package:'):
 172                         # If one of packages is native, do not compare full versions since
 173                         # it is useless to compare native and 0install version revisions
 174                         r = cmp(a.version[0], b.version[0])
 175                         if r: return r
 176                         # Othewise, prefer native package
 177                         return cmp(a.id.startswith('package:'), b.id.startswith('package:'))
 178                 else:
 179                         r = cmp(a.version, b.version)
 180                         if r: return r
 181
 182                 # Get best OS
 183                 r = cmp(arch.os_ranks.get(b.os, None),
 184                         arch.os_ranks.get(a.os, None))
 185                 if r: return r
 186
 187                 # Get best machine
 188                 r = cmp(arch.machine_ranks.get(b.machine, None),
 189                         arch.machine_ranks.get(a.machine, None))
 190                 if r: return r
 191
 192                 # Slightly prefer languages specialised to our country
 193                 r = cmp(any(l in self.langs for l in a_langs),
 194                         any(l in self.langs for l in b_langs))
 195                 if r: return r
 196
 197                 # Slightly prefer cached versions
 198                 if self.network_use == model.network_full:
 199                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 200                         if r: return r
 201
 202                 return cmp(a.id, b.id)
 203
 204         def solve(self, root_interface, root_arch, closest_match = False):
 205                 # closest_match is used internally. It adds a lowest-ranked
 206                 # by valid implementation to every interface, so we can always
 207                 # select something. Useful for diagnostics.
 208
 209                 # TODO: We need some way to figure out which feeds to include.
 210                 # Currently, we include any feed referenced from anywhere but
 211                 # this is probably too much. We could insert a dummy optimial
 212                 # implementation in stale/uncached feeds and see whether it
 213                 # selects that.
 214
 215                 feeds_added = set()
 216                 problem = sat.SATProblem()
 217
 218                 impl_to_var = {}        # Impl -> sat var
 219                 self.feeds_used = set()
 220                 self.requires = {}
 221                 self.ready = False
 222                 self.details = self.record_details and {}
 223
 224                 self.selections = None
 225
 226                 ifaces_processed = set()
 227
 228                 impls_for_machine_group = {0 : []}              # Machine group (e.g. "64") to [impl] in that group
 229                 for machine_group in machine_groups.values():
 230                         impls_for_machine_group[machine_group] = []
 231
 232                 impls_for_iface = {}    # Iface -> [impl]
 233
 234                 group_clause_for = {}   # Iface URI -> AtMostOneClause | bool
 235
 236                 def find_dependency_candidates(requiring_impl_var, dependency):
 237                         dep_iface = self.iface_cache.get_interface(dependency.interface)
 238                         dep_union = [sat.neg(requiring_impl_var)]
 239                         for candidate in impls_for_iface[dep_iface]:
 240                                 for r in dependency.restrictions:
 241                                         if candidate.__class__ is not _DummyImpl and not r.meets_restriction(candidate):
 242                                                 #warn("%s rejected due to %s", candidate.get_version(), r)
 243                                                 if candidate.version is not None:
 244                                                         break
 245                                 else:
 246                                         c_var = impl_to_var.get(candidate, None)
 247                                         if c_var is not None:
 248                                                 dep_union.append(c_var)
 249                                         # else we filtered that version out, so ignore it
 250                         if dep_union:
 251                                 problem.add_clause(dep_union)
 252                         else:
 253                                 problem.assign(requiring_impl_var, 0)
 254
 255                 def is_unusable(impl, restrictions, arch):
 256                         """@return: whether this implementation is unusable.
 257                         @rtype: bool"""
 258                         return get_unusable_reason(impl, restrictions, arch) != None
 259
 260                 def get_unusable_reason(impl, restrictions, arch):
 261                         """
 262                         @param impl: Implementation to test.
 263                         @type restrictions: [L{model.Restriction}]
 264                         @return: The reason why this impl is unusable, or None if it's OK.
 265                         @rtype: str
 266                         @note: The restrictions are for the interface being requested, not the feed
 267                         of the implementation; they may be different when feeds are being used."""
 268                         for r in restrictions:
 269                                 if not r.meets_restriction(impl):
 270                                         return _("Incompatible with another selected implementation")
 271                         stability = impl.get_stability()
 272                         if stability <= model.buggy:
 273                                 return stability.name
 274                         if (self.network_use == model.network_offline or not impl.download_sources) and not _get_cached(self.stores, impl):
 275                                 if not impl.download_sources:
 276                                         return _("No retrieval methods")
 277                                 return _("Not cached and we are off-line")
 278                         if impl.os not in arch.os_ranks:
 279                                 return _("Unsupported OS")
 280                         if impl.machine not in arch.machine_ranks:
 281                                 if impl.machine == 'src':
 282                                         return _("Source code")
 283                                 return _("Unsupported machine type")
 284                         return None
 285
 286                 def usable_feeds(iface, arch):
 287                         """Return all feeds for iface that support arch.
 288                         @rtype: generator(ZeroInstallFeed)"""
 289                         yield iface.uri
 290
 291                         for f in self.iface_cache.get_feed_imports(iface):
 292                                 # Note: when searching for src, None is not in machine_ranks
 293                                 if f.os in arch.os_ranks and \
 294                                    (f.machine is None or f.machine in arch.machine_ranks):
 295                                         yield f.uri
 296                                 else:
 297                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 298                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 299
 300                 def add_iface(uri, arch):
 301                         """Name implementations from feed, assign costs and assert that one one can be selected."""
 302                         if uri in ifaces_processed: return
 303                         ifaces_processed.add(uri)
 304                         iface_name = 'i%d' % len(ifaces_processed)
 305
 306                         iface = self.iface_cache.get_interface(uri)
 307
 308                         impls = []
 309                         for f in usable_feeds(iface, arch):
 310                                 self.feeds_used.add(f)
 311                                 debug(_("Processing feed %s"), f)
 312
 313                                 try:
 314                                         feed = self.iface_cache.get_feed(f)
 315                                         if feed is None: continue
 316                                         #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 317                                         #       info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 318
 319                                         if feed.implementations:
 320                                                 impls.extend(feed.implementations.values())
 321
 322                                         distro_feed_url = feed.get_distro_feed()
 323                                         if distro_feed_url:
 324                                                 self.feeds_used.add(distro_feed_url)
 325                                                 distro_feed = self.iface_cache.get_feed(distro_feed_url)
 326                                                 if distro_feed.implementations:
 327                                                         impls.extend(distro_feed.implementations.values())
 328                                 except Exception, ex:
 329                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': ex})
 330
 331                         impls.sort(lambda a, b: self.compare(iface, a, b, arch))
 332
 333                         impls_for_iface[iface] = filtered_impls = []
 334
 335                         my_extra_restrictions = self.extra_restrictions.get(iface, [])
 336
 337                         if self.record_details:
 338                                 self.details[iface] = [(impl, get_unusable_reason(impl, my_extra_restrictions, arch)) for impl in impls]
 339
 340                         rank = 1
 341                         var_names = []
 342                         for impl in impls:
 343                                 if is_unusable(impl, my_extra_restrictions, arch):
 344                                         continue
 345
 346                                 filtered_impls.append(impl)
 347
 348                                 assert impl not in impl_to_var
 349                                 v = problem.add_variable(ImplInfo(iface, impl, arch))
 350                                 impl_to_var[impl] = v
 351                                 rank += 1
 352                                 var_names.append(v)
 353
 354                                 if impl.machine and impl.machine != 'src':
 355                                         impls_for_machine_group[machine_groups.get(impl.machine, 0)].append(v)
 356
 357                                 for d in impl.requires:
 358                                         debug(_("Considering dependency %s"), d)
 359                                         use = d.metadata.get("use", None)
 360                                         if use not in arch.use:
 361                                                 info("Skipping dependency; use='%s' not in %s", use, arch.use)
 362                                                 continue
 363
 364                                         add_iface(d.interface, arch.child_arch)
 365
 366                                         # Must choose one version of d if impl is selected
 367                                         find_dependency_candidates(v, d)
 368
 369                         if closest_match:
 370                                 dummy_impl = _DummyImpl()
 371                                 dummy_var = problem.add_variable(ImplInfo(iface, dummy_impl, arch, dummy = True))
 372                                 var_names.append(dummy_var)
 373                                 impl_to_var[dummy_impl] = dummy_var
 374                                 filtered_impls.append(dummy_impl)
 375
 376                         # Only one implementation of this interface can be selected
 377                         if uri == root_interface:
 378                                 if var_names:
 379                                         clause = problem.at_most_one(var_names)
 380                                         problem.add_clause(var_names)   # at least one
 381                                 else:
 382                                         problem.impossible()
 383                                         clause = False
 384                         elif var_names:
 385                                 clause = problem.at_most_one(var_names)
 386                         else:
 387                                 # Don't need to add to group_clause_for because we should
 388                                 # never get a possible selection involving this.
 389                                 return
 390
 391                         assert clause is not True
 392                         assert clause is not None
 393                         if clause is not False:
 394                                 group_clause_for[uri] = clause
 395
 396                 add_iface(root_interface, root_arch)
 397
 398                 # Require m<group> to be true if we select an implementation in that group
 399                 m_groups = []
 400                 for machine_group, impls in impls_for_machine_group.iteritems():
 401                         m_group = 'm%d' % machine_group
 402                         group_var = problem.add_variable(m_group)
 403                         if impls:
 404                                 for impl in impls:
 405                                         problem.add_clause([group_var, sat.neg(impl)])
 406                         m_groups.append(group_var)
 407                 if m_groups:
 408                         m_groups_clause = problem.at_most_one(m_groups)
 409                 else:
 410                         m_groups_clause = None
 411
 412                 def decide():
 413                         """Recurse through the current selections until we get to an interface with
 414                         no chosen version, then tell the solver to try the best version from that."""
 415
 416                         seen = set()
 417                         def find_undecided(uri):
 418                                 if uri in seen:
 419                                         return  # Break cycles
 420                                 seen.add(uri)
 421
 422                                 group = group_clause_for[uri]
 423                                 #print "Group for %s = %s" % (uri, group)
 424                                 lit = group.current
 425                                 if lit is None:
 426                                         return group.best_undecided()
 427                                 # else there was only one choice anyway
 428
 429                                 # Check for undecided dependencies
 430                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 431
 432                                 for dep in lit_info.impl.requires:
 433                                         use = dep.metadata.get("use", None)
 434                                         if use not in lit_info.arch.use:
 435                                                 continue
 436                                         dep_lit = find_undecided(dep.interface)
 437                                         if dep_lit is not None:
 438                                                 return dep_lit
 439
 440                                 # This whole sub-tree is decided
 441                                 return None
 442
 443                         best = find_undecided(root_interface)
 444                         if best is not None:
 445                                 return best
 446
 447                         # If we're chosen everything we need, we can probably
 448                         # set everything else to False.
 449                         for group in group_clause_for.values() + [m_groups_clause]:
 450                                 if group.current is None:
 451                                         best = group.best_undecided()
 452                                         if best is not None:
 453                                                 return sat.neg(best)
 454
 455                         return None                     # Failed to find any valid combination
 456
 457                 ready = problem.run_solver(decide) is True
 458
 459                 if not ready and not closest_match:
 460                         # We failed while trying to do a real solve.
 461                         # Try a closest match solve to get a better
 462                         # error report for the user.
 463                         self.solve(root_interface, root_arch, closest_match = True)
 464                 else:
 465                         self.ready = ready and not closest_match
 466                         self.selections = selections.Selections(None)
 467                         self.selections.interface = root_interface
 468
 469                         sels = self.selections.selections
 470
 471                         for uri, group in group_clause_for.iteritems():
 472                                 if group.current is not None:
 473                                         lit_info = problem.get_varinfo_for_lit(group.current).obj
 474                                         if lit_info.is_dummy:
 475                                                 sels[lit_info.iface.uri] = None
 476                                         else:
 477                                                 impl = lit_info.impl
 478
 479                                                 deps = self.requires[lit_info.iface] = []
 480                                                 for dep in impl.requires:
 481                                                         use = dep.metadata.get("use", None)
 482                                                         if use not in lit_info.arch.use:
 483                                                                 continue
 484                                                         deps.append(dep)
 485
 486                                                 sels[lit_info.iface.uri] = selections.ImplSelection(lit_info.iface.uri, impl, deps)
 487
 488 DefaultSolver = SATSolver