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         def __init__(self, iface, impl, arch):
  41                 self.iface = iface
  42                 self.impl = impl
  43                 self.arch = arch
  44
  45         def __repr__(self):
  46                 return str(self.impl.feed.get_name() + "-" + self.impl.get_version())
  47
  48 class Solver(object):
  49         """Chooses a set of implementations to satisfy the requirements of a program and its user.
  50         Typical use:
  51          1. Create a Solver object and configure it
  52          2. Call L{solve}.
  53          3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
  54          4. If it is 'ready' then you can download and run the chosen versions.
  55         @ivar selections: the chosen implementation of each interface
  56         @type selections: {L{model.Interface}: Implementation}
  57         @ivar requires: the selected dependencies for each chosen version
  58         @type requires: {L{model.Interface}: [L{model.Dependency}]}
  59         @ivar feeds_used: the feeds which contributed to the choice in L{selections}
  60         @type feeds_used: set(str)
  61         @ivar record_details: whether to record information about unselected implementations
  62         @type record_details: {L{Interface}: [(L{Implementation}, str)]}
  63         @ivar details: extra information, if record_details mode was used
  64         @type details: {str: [(Implementation, comment)]}
  65         """
  66         __slots__ = ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
  67
  68         def __init__(self):
  69                 self.selections = self.requires = self.feeds_used = self.details = None
  70                 self.record_details = False
  71                 self.ready = False
  72
  73         def solve(self, root_interface, arch):
  74                 """Get the best implementation of root_interface and all of its dependencies.
  75                 @param root_interface: the URI of the program to be solved
  76                 @type root_interface: str
  77                 @param arch: the desired target architecture
  78                 @type arch: L{arch.Architecture}
  79                 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
  80                 raise NotImplementedError("Abstract")
  81
  82 class SATSolver(Solver):
  83         """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them."""
  84         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
  85                 """
  86                 @param network_use: how much use to make of the network
  87                 @type network_use: L{model.network_levels}
  88                 @param iface_cache: a cache of feeds containing information about available versions
  89                 @type iface_cache: L{iface_cache.IfaceCache}
  90                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
  91                 @type stores: L{zerostore.Stores}
  92                 @param extra_restrictions: extra restrictions on the chosen implementations
  93                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
  94                 """
  95                 Solver.__init__(self)
  96                 self.network_use = network_use
  97                 self.iface_cache = iface_cache
  98                 self.stores = stores
  99                 self.help_with_testing = False
 100                 self.extra_restrictions = extra_restrictions or {}
 101
 102         def compare(self, interface, b, a, arch):
 103                 """Compare a and b to see which would be chosen first.
 104                 Does not consider whether the implementations are usable (check for that yourself first).
 105                 @param interface: The interface we are trying to resolve, which may
 106                 not be the interface of a or b if they are from feeds.
 107                 @rtype: int"""
 108                 a_stab = a.get_stability()
 109                 b_stab = b.get_stability()
 110
 111                 # Preferred versions come first
 112                 r = cmp(a_stab == model.preferred, b_stab == model.preferred)
 113                 if r: return r
 114
 115                 stores = self.stores
 116                 if self.network_use != model.network_full:
 117                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 118                         if r: return r
 119
 120                 # Stability
 121                 stab_policy = interface.stability_policy
 122                 if not stab_policy:
 123                         if self.help_with_testing: stab_policy = model.testing
 124                         else: stab_policy = model.stable
 125
 126                 if a_stab >= stab_policy: a_stab = model.preferred
 127                 if b_stab >= stab_policy: b_stab = model.preferred
 128
 129                 r = cmp(a_stab, b_stab)
 130                 if r: return r
 131
 132                 # Newer versions come before older ones
 133                 r = cmp(a.version, b.version)
 134                 if r: return r
 135
 136                 # Get best OS
 137                 r = cmp(arch.os_ranks.get(b.os, None),
 138                         arch.os_ranks.get(a.os, None))
 139                 if r: return r
 140
 141                 # Get best machine
 142                 r = cmp(arch.machine_ranks.get(b.machine, None),
 143                         arch.machine_ranks.get(a.machine, None))
 144                 if r: return r
 145
 146                 # Slightly prefer cached versions
 147                 if self.network_use == model.network_full:
 148                         r = cmp(_get_cached(stores, a), _get_cached(stores, b))
 149                         if r: return r
 150
 151                 return cmp(a.id, b.id)
 152
 153         def solve(self, root_interface, root_arch):
 154                 # TODO: We need some way to figure out which feeds to include.
 155                 # Currently, we include any feed referenced from anywhere but
 156                 # this is probably too much. We could insert a dummy optimial
 157                 # implementation in stale/uncached feeds and see whether it
 158                 # selects that.
 159
 160                 feeds_added = set()
 161                 problem = sat.Solver()
 162
 163                 feed_names = {} # Feed -> "f1"
 164                 impl_names = {} # Impl -> "f1_0"
 165                 self.feeds_used = set()
 166                 self.requires = {}
 167                 self.ready = False
 168                 self.details = self.record_details and {}
 169
 170                 self.selections = None
 171
 172                 comment_problem = False # debugging only
 173
 174                 # TODO: simplify this; there's no need for two mappings!
 175                 var = {}                # our var names to sat var/literal numbers
 176
 177                 if self.help_with_testing:
 178                         # Choose the newest, not the most stable.
 179                         # Preferred still affects the choice, though.
 180                         stability_cost = {
 181                                 model.preferred :    0,
 182                                 model.packaged  : 1000,
 183                                 model.stable    : 1000,
 184                                 model.testing   : 1000,
 185                                 model.developer : 1000,
 186                         }
 187                 else:
 188                         # Strongly prefer packaged or stable versions.
 189                         stability_cost = {
 190                                 model.preferred :    0,
 191                                 model.packaged  : 1000,
 192                                 model.stable    : 1100,
 193                                 model.testing   : 3000,
 194                                 model.developer : 8000,
 195                         }
 196
 197                 def feed_name(feed):
 198                         name = feed_names.get(feed, None)
 199                         if name: return name
 200                         feed_names[feed] = name = "f%d" % (len(feed_names))
 201                         if comment_problem:
 202                                 problem.append("* feed %s is now known as %s" % (feed, name))
 203                         self.feeds_used.add(feed.url)
 204                         return name
 205
 206                 ifaces_processed = set()
 207
 208                 impls_for_machine_group = {0 : []}              # Machine group (e.g. "64") to [impl] in that group
 209                 for machine_group in machine_groups.values():
 210                         impls_for_machine_group[machine_group] = []
 211
 212                 impls_for_iface = {}    # Iface -> [impl]
 213
 214                 group_clause_for = {}   # Iface URI -> AtMostOneClause | bool
 215
 216                 def find_dependency_candidates(requiring_impl, dependency):
 217                         dep_iface = self.iface_cache.get_interface(dependency.interface)
 218                         dep_union = [sat.neg(var[requiring_impl])]
 219                         for candidate in impls_for_iface[dep_iface]:
 220                                 for r in dependency.restrictions:
 221                                         if not r.meets_restriction(candidate):
 222                                                 #warn("%s rejected due to %s", candidate.get_version(), r)
 223                                                 break
 224                                 else:
 225                                         c_name = impl_names.get(candidate, None)
 226                                         if c_name:
 227                                                 dep_union.append(var[c_name])
 228                                         # else we filtered that version out, so ignore it
 229                         if comment_problem:
 230                                 problem.append("* %s requires %s" % (requiring_impl, dependency))
 231                         if dep_union:
 232                                 problem.add_clause(dep_union)
 233                         else:
 234                                 problem.assign(requiring_impl, 0)
 235
 236                 def is_unusable(impl, restrictions, arch):
 237                         """@return: whether this implementation is unusable.
 238                         @rtype: bool"""
 239                         return get_unusable_reason(impl, restrictions, arch) != None
 240
 241                 def get_unusable_reason(impl, restrictions, arch):
 242                         """
 243                         @param impl: Implementation to test.
 244                         @type restrictions: [L{model.Restriction}]
 245                         @return: The reason why this impl is unusable, or None if it's OK.
 246                         @rtype: str
 247                         @note: The restrictions are for the interface being requested, not the feed
 248                         of the implementation; they may be different when feeds are being used."""
 249                         for r in restrictions:
 250                                 if not r.meets_restriction(impl):
 251                                         return _("Incompatible with another selected implementation")
 252                         stability = impl.get_stability()
 253                         if stability <= model.buggy:
 254                                 return stability.name
 255                         if (self.network_use == model.network_offline or not impl.download_sources) and not _get_cached(self.stores, impl):
 256                                 if not impl.download_sources:
 257                                         return _("No retrieval methods")
 258                                 return _("Not cached and we are off-line")
 259                         if impl.os not in arch.os_ranks:
 260                                 return _("Unsupported OS")
 261                         if impl.machine not in arch.machine_ranks:
 262                                 if impl.machine == 'src':
 263                                         return _("Source code")
 264                                 return _("Unsupported machine type")
 265                         return None
 266
 267                 def usable_feeds(iface, arch):
 268                         """Return all feeds for iface that support arch.
 269                         @rtype: generator(ZeroInstallFeed)"""
 270                         yield iface.uri
 271
 272                         for f in iface.feeds:
 273                                 # Note: when searching for src, None is not in machine_ranks
 274                                 if f.os in arch.os_ranks and \
 275                                    (f.machine is None or f.machine in arch.machine_ranks):
 276                                         yield f.uri
 277                                 else:
 278                                         debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
 279                                                 {'feed': f, 'os': f.os, 'machine': f.machine})
 280
 281                 def add_iface(uri, arch):
 282                         """Name implementations from feed, assign costs and assert that one one can be selected."""
 283                         if uri in ifaces_processed: return
 284                         ifaces_processed.add(uri)
 285                         iface_name = 'i%d' % len(ifaces_processed)
 286
 287                         iface = self.iface_cache.get_interface(uri)
 288
 289                         impls = []
 290                         for f in usable_feeds(iface, arch):
 291                                 self.feeds_used.add(f)
 292                                 debug(_("Processing feed %s"), f)
 293
 294                                 try:
 295                                         feed = self.iface_cache.get_interface(f)._main_feed
 296                                         if not feed.last_modified: continue     # DummyFeed
 297                                         if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 298                                                 info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
 299
 300                                         if feed.implementations:
 301                                                 impls.extend(feed.implementations.values())
 302                                 except Exception, ex:
 303                                         warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f, 'interface': iface, 'exception': str(ex)})
 304
 305                         impls.sort(lambda a, b: self.compare(iface, a, b, arch))
 306
 307                         impls_for_iface[iface] = filtered_impls = []
 308
 309                         my_extra_restrictions = self.extra_restrictions.get(iface, [])
 310
 311                         if self.record_details:
 312                                 self.details[iface] = [(impl, get_unusable_reason(impl, my_extra_restrictions, arch)) for impl in impls]
 313
 314                         rank = 1
 315                         var_names = []
 316                         for impl in impls:
 317                                 if is_unusable(impl, my_extra_restrictions, arch):
 318                                         continue
 319
 320                                 filtered_impls.append(impl)
 321
 322                                 # TODO: simplify me!
 323                                 name = feed_name(impl.feed) + "_" + str(rank)
 324                                 assert impl not in impl_names
 325                                 v = problem.add_variable(ImplInfo(iface, impl, arch))
 326                                 var[name] = v
 327                                 impl_names[impl] = name
 328                                 rank += 1
 329                                 var_names.append(var[name])
 330
 331                                 if impl.machine and impl.machine != 'src':
 332                                         impls_for_machine_group[machine_groups.get(impl.machine, 0)].append(name)
 333
 334                                 for d in impl.requires:
 335                                         debug(_("Considering dependency %s"), d)
 336                                         use = d.metadata.get("use", None)
 337                                         if use not in arch.use:
 338                                                 info("Skipping dependency; use='%s' not in %s", use, arch.use)
 339                                                 continue
 340
 341                                         add_iface(d.interface, arch.child_arch)
 342
 343                                         # Must choose one version of d if impl is selected
 344                                         find_dependency_candidates(name, d)
 345
 346                         # Only one implementation of this interface can be selected
 347                         if uri == root_interface:
 348                                 if var_names:
 349                                         clause = problem.at_most_one(var_names)
 350                                         problem.add_clause(var_names)   # at least one
 351                                 else:
 352                                         problem.impossible()
 353                                         clause = False
 354                         elif var_names:
 355                                 clause = problem.at_most_one(var_names)
 356                         else:
 357                                 # Don't need to add to group_clause_for because we should
 358                                 # never get a possible selection involving this.
 359                                 return
 360
 361                         assert clause is not True
 362                         assert clause is not None
 363                         if clause is not False:
 364                                 group_clause_for[uri] = clause
 365
 366                 add_iface(root_interface, root_arch)
 367
 368                 # Require m<group> to be true if we select an implementation in that group
 369                 m_groups = []
 370                 for machine_group, impls in impls_for_machine_group.iteritems():
 371                         m_group = 'm%d' % machine_group
 372                         var[m_group] = problem.add_variable(m_group)
 373                         if impls:
 374                                 if comment_problem:
 375                                         problem.append("* define machine group %d" % m_group)
 376                                 for impl in impls:
 377                                         problem.add_clause([var[m_group], sat.neg(var[impl])])
 378                         m_groups.append(var[m_group])
 379                 if m_groups:
 380                         if comment_problem:
 381                                 problem.append("* select implementations from at most one machine group")
 382                         m_groups_clause = problem.at_most_one(m_groups)
 383                 else:
 384                         m_groups_clause = None
 385
 386                 def decide():
 387                         """Recurse through the current selections until we get to an interface with
 388                         no chosen version, then tell the solver to try the best version from that."""
 389
 390                         seen = set()
 391                         def find_undecided(uri):
 392                                 if uri in seen:
 393                                         return  # Break cycles
 394                                 seen.add(uri)
 395
 396                                 group = group_clause_for[uri]
 397                                 #print "Group for %s = %s" % (uri, group)
 398                                 lit = group.current
 399                                 if lit is None:
 400                                         return group.best_undecided()
 401                                 # else there was only one choice anyway
 402
 403                                 # Check for undecided dependencies
 404                                 lit_info = problem.get_varinfo_for_lit(lit).obj
 405
 406                                 for dep in lit_info.impl.requires:
 407                                         use = dep.metadata.get("use", None)
 408                                         if use not in lit_info.arch.use:
 409                                                 continue
 410                                         dep_lit = find_undecided(dep.interface)
 411                                         if dep_lit is not None:
 412                                                 return dep_lit
 413
 414                                 # This whole sub-tree is decided
 415                                 return None
 416
 417                         best = find_undecided(root_interface)
 418                         if best is not None:
 419                                 return best
 420
 421                         # If we're chosen everything we need, we can probably
 422                         # set everything else to False.
 423                         for group in group_clause_for.values() + [m_groups_clause]:
 424                                 if group.current is None:
 425                                         best = group.best_undecided()
 426                                         if best is not None:
 427                                                 return sat.neg(best)
 428
 429                         return None                     # Failed to find any valid combination
 430
 431                 self.ready = problem.run_solver(decide) is True
 432
 433                 # Pointing the root at None by default is just
 434                 # to make the unit-tests happy :-/
 435                 self.selections = {self.iface_cache.get_interface(root_interface): None}
 436
 437                 for uri, group in group_clause_for.iteritems():
 438                         if group.current is not None:
 439                                 lit_info = problem.get_varinfo_for_lit(group.current).obj
 440                                 self.selections[lit_info.iface] = lit_info.impl
 441                                 deps = self.requires[lit_info.iface] = []
 442                                 for dep in lit_info.impl.requires:
 443                                         use = dep.metadata.get("use", None)
 444                                         if use not in lit_info.arch.use:
 445                                                 continue
 446                                         deps.append(dep)
 447
 448 DefaultSolver = SATSolver