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
  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{model.Interface}: Implementation}
  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                         # Note: we only look one level deep here. Maybe we should recurse further?
 292                         feeds = iface.extra_feeds
 293                         main_feed = self.iface_cache.get_feed(iface.uri)
 294                         if main_feed:
 295                                 feeds = feeds + main_feed.feeds
 296
 297                         for f in feeds:
 298                                 # Note: when searching for src, None is not in machine_ranks
 299                                 if f.os in arch.os_ranks and \
 300                                    (f.machine is None or f.machine in arch.machine_ranks):
 301                                         yield f.uri
 302                                 else:
 303                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 304                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 305
 306                 def add_iface(uri, arch):
 307                         """Name implementations from feed, assign costs and assert that one one can be selected."""
 308                         if uri in ifaces_processed: return
 309                         ifaces_processed.add(uri)
 310                         iface_name = 'i%d' % len(ifaces_processed)
 311
 312                         iface = self.iface_cache.get_interface(uri)
 313
 314                         impls = []
 315                         for f in usable_feeds(iface, arch):
 316                                 self.feeds_used.add(f)
 317                                 debug(_("Processing feed %s"), f)
 318
 319                                 try:
 320                                         feed = self.iface_cache.get_feed(f)
 321                                         if feed is None: continue
 322                                         #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 323                                         #       info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 324
 325                                         if feed.implementations:
 326                                                 impls.extend(feed.implementations.values())
 327                                 except Exception, ex:
 328                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': ex})
 329
 330                         impls.sort(lambda a, b: self.compare(iface, a, b, arch))
 331
 332                         impls_for_iface[iface] = filtered_impls = []
 333
 334                         my_extra_restrictions = self.extra_restrictions.get(iface, [])
 335
 336                         if self.record_details:
 337                                 self.details[iface] = [(impl, get_unusable_reason(impl, my_extra_restrictions, arch)) for impl in impls]
 338
 339                         rank = 1
 340                         var_names = []
 341                         for impl in impls:
 342                                 if is_unusable(impl, my_extra_restrictions, arch):
 343                                         continue
 344
 345                                 filtered_impls.append(impl)
 346
 347                                 assert impl not in impl_to_var
 348                                 v = problem.add_variable(ImplInfo(iface, impl, arch))
 349                                 impl_to_var[impl] = v
 350                                 rank += 1
 351                                 var_names.append(v)
 352
 353                                 if impl.machine and impl.machine != 'src':
 354                                         impls_for_machine_group[machine_groups.get(impl.machine, 0)].append(v)
 355
 356                                 for d in impl.requires:
 357                                         debug(_("Considering dependency %s"), d)
 358                                         use = d.metadata.get("use", None)
 359                                         if use not in arch.use:
 360                                                 info("Skipping dependency; use='%s' not in %s", use, arch.use)
 361                                                 continue
 362
 363                                         add_iface(d.interface, arch.child_arch)
 364
 365                                         # Must choose one version of d if impl is selected
 366                                         find_dependency_candidates(v, d)
 367
 368                         if closest_match:
 369                                 dummy_impl = _DummyImpl()
 370                                 dummy_var = problem.add_variable(ImplInfo(iface, dummy_impl, arch, dummy = True))
 371                                 var_names.append(dummy_var)
 372                                 impl_to_var[dummy_impl] = dummy_var
 373                                 filtered_impls.append(dummy_impl)
 374
 375                         # Only one implementation of this interface can be selected
 376                         if uri == root_interface:
 377                                 if var_names:
 378                                         clause = problem.at_most_one(var_names)
 379                                         problem.add_clause(var_names)   # at least one
 380                                 else:
 381                                         problem.impossible()
 382                                         clause = False
 383                         elif var_names:
 384                                 clause = problem.at_most_one(var_names)
 385                         else:
 386                                 # Don't need to add to group_clause_for because we should
 387                                 # never get a possible selection involving this.
 388                                 return
 389
 390                         assert clause is not True
 391                         assert clause is not None
 392                         if clause is not False:
 393                                 group_clause_for[uri] = clause
 394
 395                 add_iface(root_interface, root_arch)
 396
 397                 # Require m<group> to be true if we select an implementation in that group
 398                 m_groups = []
 399                 for machine_group, impls in impls_for_machine_group.iteritems():
 400                         m_group = 'm%d' % machine_group
 401                         group_var = problem.add_variable(m_group)
 402                         if impls:
 403                                 for impl in impls:
 404                                         problem.add_clause([group_var, sat.neg(impl)])
 405                         m_groups.append(group_var)
 406                 if m_groups:
 407                         m_groups_clause = problem.at_most_one(m_groups)
 408                 else:
 409                         m_groups_clause = None
 410
 411                 def decide():
 412                         """Recurse through the current selections until we get to an interface with
 413                         no chosen version, then tell the solver to try the best version from that."""
 414
 415                         seen = set()
 416                         def find_undecided(uri):
 417                                 if uri in seen:
 418                                         return  # Break cycles
 419                                 seen.add(uri)
 420
 421                                 group = group_clause_for[uri]
 422                                 #print "Group for %s = %s" % (uri, group)
 423                                 lit = group.current
 424                                 if lit is None:
 425                                         return group.best_undecided()
 426                                 # else there was only one choice anyway
 427
 428                                 # Check for undecided dependencies
 429                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 430
 431                                 for dep in lit_info.impl.requires:
 432                                         use = dep.metadata.get("use", None)
 433                                         if use not in lit_info.arch.use:
 434                                                 continue
 435                                         dep_lit = find_undecided(dep.interface)
 436                                         if dep_lit is not None:
 437                                                 return dep_lit
 438
 439                                 # This whole sub-tree is decided
 440                                 return None
 441
 442                         best = find_undecided(root_interface)
 443                         if best is not None:
 444                                 return best
 445
 446                         # If we're chosen everything we need, we can probably
 447                         # set everything else to False.
 448                         for group in group_clause_for.values() + [m_groups_clause]:
 449                                 if group.current is None:
 450                                         best = group.best_undecided()
 451                                         if best is not None:
 452                                                 return sat.neg(best)
 453
 454                         return None                     # Failed to find any valid combination
 455
 456                 ready = problem.run_solver(decide) is True
 457
 458                 if not ready and not closest_match:
 459                         # We failed while trying to do a real solve.
 460                         # Try a closest match solve to get a better
 461                         # error report for the user.
 462                         self.solve(root_interface, root_arch, closest_match = True)
 463                 else:
 464                         self.ready = ready and not closest_match
 465                         self.selections = {}
 466
 467                         for uri, group in group_clause_for.iteritems():
 468                                 if group.current is not None:
 469                                         lit_info = problem.get_varinfo_for_lit(group.current).obj
 470                                         if lit_info.is_dummy:
 471                                                 self.selections[lit_info.iface] = None
 472                                         else:
 473                                                 self.selections[lit_info.iface] = lit_info.impl
 474                                                 deps = self.requires[lit_info.iface] = []
 475                                                 for dep in lit_info.impl.requires:
 476                                                         use = dep.metadata.get("use", None)
 477                                                         if use not in lit_info.arch.use:
 478                                                                 continue
 479                                                         deps.append(dep)
 480
 481
 482 DefaultSolver = SATSolver