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
  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:
  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, 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 arch: the desired target architecture
  99                 @type 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         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
 106                 """
 107                 @param network_use: how much use to make of the network
 108                 @type network_use: L{model.network_levels}
 109                 @param iface_cache: a cache of feeds containing information about available versions
 110                 @type iface_cache: L{iface_cache.IfaceCache}
 111                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
 112                 @type stores: L{zerostore.Stores}
 113                 @param extra_restrictions: extra restrictions on the chosen implementations
 114                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
 115                 """
 116                 Solver.__init__(self)
 117                 self.network_use = network_use
 118                 self.iface_cache = iface_cache
 119                 self.stores = stores
 120                 self.help_with_testing = False
 121                 self.extra_restrictions = extra_restrictions or {}
 122
 123         def compare(self, interface, b, a, arch):
 124                 """Compare a and b to see which would be chosen first.
 125                 Does not consider whether the implementations are usable (check for that yourself first).
 126                 @param interface: The interface we are trying to resolve, which may
 127                 not be the interface of a or b if they are from feeds.
 128                 @rtype: int"""
 129                 a_stab = a.get_stability()
 130                 b_stab = b.get_stability()
 131
 132                 # Preferred versions come first
 133                 r = cmp(a_stab == model.preferred, b_stab == model.preferred)
 134                 if r: return r
 135
 136                 stores = self.stores
 137                 if self.network_use != model.network_full:
 138                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 139                         if r: return r
 140
 141                 # Stability
 142                 stab_policy = interface.stability_policy
 143                 if not stab_policy:
 144                         if self.help_with_testing: stab_policy = model.testing
 145                         else: stab_policy = model.stable
 146
 147                 if a_stab >= stab_policy: a_stab = model.preferred
 148                 if b_stab >= stab_policy: b_stab = model.preferred
 149
 150                 r = cmp(a_stab, b_stab)
 151                 if r: return r
 152
 153                 # Newer versions come before older ones
 154                 r = cmp(a.version, b.version)
 155                 if r: return r
 156
 157                 # Get best OS
 158                 r = cmp(arch.os_ranks.get(b.os, None),
 159                         arch.os_ranks.get(a.os, None))
 160                 if r: return r
 161
 162                 # Get best machine
 163                 r = cmp(arch.machine_ranks.get(b.machine, None),
 164                         arch.machine_ranks.get(a.machine, None))
 165                 if r: return r
 166
 167                 # Slightly prefer cached versions
 168                 if self.network_use == model.network_full:
 169                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 170                         if r: return r
 171
 172                 return cmp(a.id, b.id)
 173
 174         def solve(self, root_interface, root_arch, closest_match = False):
 175                 # closest_match is used internally. It adds a lowest-ranked
 176                 # by valid implementation to every interface, so we can always
 177                 # select something. Useful for diagnostics.
 178
 179                 # TODO: We need some way to figure out which feeds to include.
 180                 # Currently, we include any feed referenced from anywhere but
 181                 # this is probably too much. We could insert a dummy optimial
 182                 # implementation in stale/uncached feeds and see whether it
 183                 # selects that.
 184
 185                 feeds_added = set()
 186                 problem = sat.Solver()
 187
 188                 impl_to_var = {}        # Impl -> sat var
 189                 self.feeds_used = set()
 190                 self.requires = {}
 191                 self.ready = False
 192                 self.details = self.record_details and {}
 193
 194                 self.selections = None
 195
 196                 ifaces_processed = set()
 197
 198                 impls_for_machine_group = {0 : []}              # Machine group (e.g. "64") to [impl] in that group
 199                 for machine_group in machine_groups.values():
 200                         impls_for_machine_group[machine_group] = []
 201
 202                 impls_for_iface = {}    # Iface -> [impl]
 203
 204                 group_clause_for = {}   # Iface URI -> AtMostOneClause | bool
 205
 206                 def find_dependency_candidates(requiring_impl_var, dependency):
 207                         dep_iface = self.iface_cache.get_interface(dependency.interface)
 208                         dep_union = [sat.neg(requiring_impl_var)]
 209                         for candidate in impls_for_iface[dep_iface]:
 210                                 for r in dependency.restrictions:
 211                                         if not r.meets_restriction(candidate):
 212                                                 #warn("%s rejected due to %s", candidate.get_version(), r)
 213                                                 if candidate.version is not None:
 214                                                         break
 215                                                 # else it's the dummy version that matches everything
 216                                 else:
 217                                         c_var = impl_to_var.get(candidate, None)
 218                                         if c_var is not None:
 219                                                 dep_union.append(c_var)
 220                                         # else we filtered that version out, so ignore it
 221                         if dep_union:
 222                                 problem.add_clause(dep_union)
 223                         else:
 224                                 problem.assign(requiring_impl_var, 0)
 225
 226                 def is_unusable(impl, restrictions, arch):
 227                         """@return: whether this implementation is unusable.
 228                         @rtype: bool"""
 229                         return get_unusable_reason(impl, restrictions, arch) != None
 230
 231                 def get_unusable_reason(impl, restrictions, arch):
 232                         """
 233                         @param impl: Implementation to test.
 234                         @type restrictions: [L{model.Restriction}]
 235                         @return: The reason why this impl is unusable, or None if it's OK.
 236                         @rtype: str
 237                         @note: The restrictions are for the interface being requested, not the feed
 238                         of the implementation; they may be different when feeds are being used."""
 239                         for r in restrictions:
 240                                 if not r.meets_restriction(impl):
 241                                         return _("Incompatible with another selected implementation")
 242                         stability = impl.get_stability()
 243                         if stability <= model.buggy:
 244                                 return stability.name
 245                         if (self.network_use == model.network_offline or not impl.download_sources) and not _get_cached(self.stores, impl):
 246                                 if not impl.download_sources:
 247                                         return _("No retrieval methods")
 248                                 return _("Not cached and we are off-line")
 249                         if impl.os not in arch.os_ranks:
 250                                 return _("Unsupported OS")
 251                         if impl.machine not in arch.machine_ranks:
 252                                 if impl.machine == 'src':
 253                                         return _("Source code")
 254                                 return _("Unsupported machine type")
 255                         return None
 256
 257                 def usable_feeds(iface, arch):
 258                         """Return all feeds for iface that support arch.
 259                         @rtype: generator(ZeroInstallFeed)"""
 260                         yield iface.uri
 261
 262                         for f in iface.feeds:
 263                                 # Note: when searching for src, None is not in machine_ranks
 264                                 if f.os in arch.os_ranks and \
 265                                    (f.machine is None or f.machine in arch.machine_ranks):
 266                                         yield f.uri
 267                                 else:
 268                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 269                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 270
 271                 def add_iface(uri, arch):
 272                         """Name implementations from feed, assign costs and assert that one one can be selected."""
 273                         if uri in ifaces_processed: return
 274                         ifaces_processed.add(uri)
 275                         iface_name = 'i%d' % len(ifaces_processed)
 276
 277                         iface = self.iface_cache.get_interface(uri)
 278
 279                         impls = []
 280                         for f in usable_feeds(iface, arch):
 281                                 self.feeds_used.add(f)
 282                                 debug(_("Processing feed %s"), f)
 283
 284                                 try:
 285                                         feed = self.iface_cache.get_interface(f)._main_feed
 286                                         if not feed.last_modified: continue     # DummyFeed
 287                                         if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 288                                                 info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 289
 290                                         if feed.implementations:
 291                                                 impls.extend(feed.implementations.values())
 292                                 except Exception, ex:
 293                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': str(ex)})
 294
 295                         impls.sort(lambda a, b: self.compare(iface, a, b, arch))
 296
 297                         impls_for_iface[iface] = filtered_impls = []
 298
 299                         my_extra_restrictions = self.extra_restrictions.get(iface, [])
 300
 301                         if self.record_details:
 302                                 self.details[iface] = [(impl, get_unusable_reason(impl, my_extra_restrictions, arch)) for impl in impls]
 303
 304                         rank = 1
 305                         var_names = []
 306                         for impl in impls:
 307                                 if is_unusable(impl, my_extra_restrictions, arch):
 308                                         continue
 309
 310                                 filtered_impls.append(impl)
 311
 312                                 assert impl not in impl_to_var
 313                                 v = problem.add_variable(ImplInfo(iface, impl, arch))
 314                                 impl_to_var[impl] = v
 315                                 rank += 1
 316                                 var_names.append(v)
 317
 318                                 if impl.machine and impl.machine != 'src':
 319                                         impls_for_machine_group[machine_groups.get(impl.machine, 0)].append(v)
 320
 321                                 for d in impl.requires:
 322                                         debug(_("Considering dependency %s"), d)
 323                                         use = d.metadata.get("use", None)
 324                                         if use not in arch.use:
 325                                                 info("Skipping dependency; use='%s' not in %s", use, arch.use)
 326                                                 continue
 327
 328                                         add_iface(d.interface, arch.child_arch)
 329
 330                                         # Must choose one version of d if impl is selected
 331                                         find_dependency_candidates(v, d)
 332
 333                         if closest_match:
 334                                 dummy_impl = _DummyImpl()
 335                                 dummy_var = problem.add_variable(ImplInfo(iface, dummy_impl, arch, dummy = True))
 336                                 var_names.append(dummy_var)
 337                                 impl_to_var[dummy_impl] = dummy_var
 338                                 filtered_impls.append(dummy_impl)
 339
 340                         # Only one implementation of this interface can be selected
 341                         if uri == root_interface:
 342                                 if var_names:
 343                                         clause = problem.at_most_one(var_names)
 344                                         problem.add_clause(var_names)   # at least one
 345                                 else:
 346                                         problem.impossible()
 347                                         clause = False
 348                         elif var_names:
 349                                 clause = problem.at_most_one(var_names)
 350                         else:
 351                                 # Don't need to add to group_clause_for because we should
 352                                 # never get a possible selection involving this.
 353                                 return
 354
 355                         assert clause is not True
 356                         assert clause is not None
 357                         if clause is not False:
 358                                 group_clause_for[uri] = clause
 359
 360                 add_iface(root_interface, root_arch)
 361
 362                 # Require m<group> to be true if we select an implementation in that group
 363                 m_groups = []
 364                 for machine_group, impls in impls_for_machine_group.iteritems():
 365                         m_group = 'm%d' % machine_group
 366                         group_var = problem.add_variable(m_group)
 367                         if impls:
 368                                 for impl in impls:
 369                                         problem.add_clause([group_var, sat.neg(impl)])
 370                         m_groups.append(group_var)
 371                 if m_groups:
 372                         m_groups_clause = problem.at_most_one(m_groups)
 373                 else:
 374                         m_groups_clause = None
 375
 376                 def decide():
 377                         """Recurse through the current selections until we get to an interface with
 378                         no chosen version, then tell the solver to try the best version from that."""
 379
 380                         seen = set()
 381                         def find_undecided(uri):
 382                                 if uri in seen:
 383                                         return  # Break cycles
 384                                 seen.add(uri)
 385
 386                                 group = group_clause_for[uri]
 387                                 #print "Group for %s = %s" % (uri, group)
 388                                 lit = group.current
 389                                 if lit is None:
 390                                         return group.best_undecided()
 391                                 # else there was only one choice anyway
 392
 393                                 # Check for undecided dependencies
 394                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 395
 396                                 for dep in lit_info.impl.requires:
 397                                         use = dep.metadata.get("use", None)
 398                                         if use not in lit_info.arch.use:
 399                                                 continue
 400                                         dep_lit = find_undecided(dep.interface)
 401                                         if dep_lit is not None:
 402                                                 return dep_lit
 403
 404                                 # This whole sub-tree is decided
 405                                 return None
 406
 407                         best = find_undecided(root_interface)
 408                         if best is not None:
 409                                 return best
 410
 411                         # If we're chosen everything we need, we can probably
 412                         # set everything else to False.
 413                         for group in group_clause_for.values() + [m_groups_clause]:
 414                                 if group.current is None:
 415                                         best = group.best_undecided()
 416                                         if best is not None:
 417                                                 return sat.neg(best)
 418
 419                         return None                     # Failed to find any valid combination
 420
 421                 ready = problem.run_solver(decide) is True
 422
 423                 if not ready and not closest_match:
 424                         # We failed while trying to do a real solve.
 425                         # Try a closest match solve to get a better
 426                         # error report for the user.
 427                         self.solve(root_interface, root_arch, closest_match = True)
 428                 else:
 429                         self.ready = ready and not closest_match
 430                         self.selections = {}
 431
 432                         for uri, group in group_clause_for.iteritems():
 433                                 if group.current is not None:
 434                                         lit_info = problem.get_varinfo_for_lit(group.current).obj
 435                                         if lit_info.is_dummy:
 436                                                 self.selections[lit_info.iface] = None
 437                                         else:
 438                                                 self.selections[lit_info.iface] = lit_info.impl
 439                                                 deps = self.requires[lit_info.iface] = []
 440                                                 for dep in lit_info.impl.requires:
 441                                                         use = dep.metadata.get("use", None)
 442                                                         if use not in lit_info.arch.use:
 443                                                                 continue
 444                                                         deps.append(dep)
 445
 446
 447 DefaultSolver = SATSolver