zeroinstall/injector/solver.py

   1 """
   2 Chooses a set of components to make a running program.
   3
   4 This class is intended to replace L{policy.Policy}.
   5 """
   6
   7 import os
   8 from logging import debug, warn, info
   9
  10 from zeroinstall.zerostore import BadDigest, NotStored
  11
  12 from zeroinstall.injector import selections
  13 from zeroinstall.injector import model
  14
  15 # Copyright (C) 2008, Thomas Leonard
  16 # See the README file for details, or visit http://0install.net.
  17
  18 class Solver(object):
  19         """Chooses a set of implementations to satisfy the requirements of a program and its user.
  20         Typical use:
  21          1. Create a Solver object and configure it
  22          2. Call L{solve}.
  23          3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
  24          4. If it is 'ready' then you can download and run the chosen versions.
  25         @ivar selections: the chosen implementation of each interface
  26         @type selections: {L{model.Interface}: Implementation}
  27         @ivar feeds_used: the feeds which contributed to the choice in L{selections}
  28         @type feeds_used: set(str)
  29         @ivar record_details: whether to record information about unselected implementations
  30         @type record_details: {L{Interface}: [(L{Implementation}, str)]}
  31         @ivar details: extra information, if record_details mode was used
  32         @type details: {str: [(Implementation, comment)]}
  33         """
  34         __slots__ = ['selections', 'feeds_used', 'details', 'record_details', 'ready']
  35
  36         def __init__(self):
  37                 self.selections = self.feeds_used = self.details = None
  38                 self.record_details = False
  39                 self.ready = False
  40
  41         def solve(self, root_interface, arch):
  42                 """Get the best implementation of root_interface and all of its dependencies.
  43                 @param root_interface: the URI of the program to be solved
  44                 @type root_interface: str
  45                 @param arch: the desired target architecture
  46                 @type arch: L{arch.Architecture}
  47                 @return: whether we have a viable selection
  48                 @rtype: bool
  49                 @postcondition: self.selections and self.feeds_used are updated"""
  50                 raise NotImplementedError("Abstract")
  51
  52 class DefaultSolver(Solver):
  53         def __init__(self, network_use, iface_cache, stores, extra_restrictions = None):
  54                 """
  55                 @param network_use: how much use to make of the network
  56                 @type network_use: L{model.network_levels}
  57                 @param iface_cache: a cache of feeds containing information about available versions
  58                 @type iface_cache: L{iface_cache.IfaceCache}
  59                 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
  60                 @type stores: L{zerostore.Stores}
  61                 @param extra_restrictions: extra restrictions on the chosen implementations
  62                 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
  63                 """
  64                 Solver.__init__(self)
  65                 self.network_use = network_use
  66                 self.iface_cache = iface_cache
  67                 self.stores = stores
  68                 self.help_with_testing = False
  69                 self.extra_restrictions = extra_restrictions or {}
  70
  71         def solve(self, root_interface, arch):
  72                 self.selections = {}
  73                 self.feeds_used = set()
  74                 self.details = self.record_details and {}
  75
  76                 restrictions = {}
  77                 debug("Solve! root = %s", root_interface)
  78                 def process(dep, arch):
  79                         ready = True
  80                         iface = self.iface_cache.get_interface(dep.interface)
  81
  82                         if iface in self.selections:
  83                                 debug("Interface requested twice; skipping second %s", iface)
  84                                 if dep.restrictions:
  85                                         warn("Interface requested twice; I've already chosen an implementation "
  86                                                 "of '%s' but there are more restrictions! Ignoring the second set.", iface)
  87                                 return
  88                         self.selections[iface] = None   # Avoid cycles
  89
  90                         assert iface not in restrictions
  91                         restrictions[iface] = dep.restrictions
  92
  93                         impl = get_best_implementation(iface, arch)
  94                         if impl:
  95                                 debug("Will use implementation %s (version %s)", impl, impl.get_version())
  96                                 self.selections[iface] = impl
  97                                 for d in impl.requires:
  98                                         debug("Considering dependency %s", d)
  99                                         if not process(d, arch.child_arch):
 100                                                 ready = False
 101                         else:
 102                                 debug("No implementation chould be chosen yet");
 103                                 ready = False
 104
 105                         return ready
 106
 107                 def get_best_implementation(iface, arch):
 108                         debug("get_best_implementation(%s), with feeds: %s", iface, iface.feeds)
 109
 110                         iface_restrictions = restrictions.get(iface, [])
 111                         extra_restrictions = self.extra_restrictions.get(iface, None)
 112                         if extra_restrictions:
 113                                 # Don't modify original
 114                                 iface_restrictions = iface_restrictions + extra_restrictions
 115
 116                         impls = []
 117                         for f in usable_feeds(iface, arch):
 118                                 self.feeds_used.add(f)
 119                                 debug("Processing feed %s", f)
 120
 121                                 try:
 122                                         feed = self.iface_cache.get_interface(f)._main_feed
 123                                         if not feed.last_modified: continue     # DummyFeed
 124                                         if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
 125                                                 warn("Missing <feed-for> for '%s' in '%s'", iface.uri, f)
 126
 127                                         if feed.implementations:
 128                                                 impls.extend(feed.implementations.values())
 129                                 except Exception, ex:
 130                                         warn("Failed to load feed %s for %s: %s", f, iface, str(ex))
 131
 132                         if not impls:
 133                                 info("Interface %s has no implementations!", iface)
 134                                 return None
 135
 136                         if self.record_details:
 137                                 # In details mode, rank all the implementations and then choose the best
 138                                 impls.sort(lambda a, b: compare(iface, a, b, iface_restrictions, arch))
 139                                 best = impls[0]
 140                                 self.details[iface] = [(impl, get_unusable_reason(impl, iface_restrictions, arch)) for impl in impls]
 141                         else:
 142                                 # Otherwise, just choose the best without sorting
 143                                 best = impls[0]
 144                                 for x in impls[1:]:
 145                                         if compare(iface, x, best, iface_restrictions, arch) < 0:
 146                                                 best = x
 147                         unusable = get_unusable_reason(best, iface_restrictions, arch)
 148                         if unusable:
 149                                 info("Best implementation of %s is %s, but unusable (%s)", iface, best, unusable)
 150                                 return None
 151                         return best
 152
 153                 def compare(interface, b, a, iface_restrictions, arch):
 154                         """Compare a and b to see which would be chosen first.
 155                         @param interface: The interface we are trying to resolve, which may
 156                         not be the interface of a or b if they are from feeds.
 157                         @rtype: int"""
 158                         a_stab = a.get_stability()
 159                         b_stab = b.get_stability()
 160
 161                         # Usable ones come first
 162                         r = cmp(is_unusable(b, iface_restrictions, arch), is_unusable(a, iface_restrictions, arch))
 163                         if r: return r
 164
 165                         # Preferred versions come first
 166                         r = cmp(a_stab == model.preferred, b_stab == model.preferred)
 167                         if r: return r
 168
 169                         if self.network_use != model.network_full:
 170                                 r = cmp(get_cached(a), get_cached(b))
 171                                 if r: return r
 172
 173                         # Stability
 174                         stab_policy = interface.stability_policy
 175                         if not stab_policy:
 176                                 if self.help_with_testing: stab_policy = model.testing
 177                                 else: stab_policy = model.stable
 178
 179                         if a_stab >= stab_policy: a_stab = model.preferred
 180                         if b_stab >= stab_policy: b_stab = model.preferred
 181
 182                         r = cmp(a_stab, b_stab)
 183                         if r: return r
 184
 185                         # Newer versions come before older ones
 186                         r = cmp(a.version, b.version)
 187                         if r: return r
 188
 189                         # Get best OS
 190                         r = cmp(arch.os_ranks.get(a.os, None),
 191                                 arch.os_ranks.get(b.os, None))
 192                         if r: return r
 193
 194                         # Get best machine
 195                         r = cmp(arch.machine_ranks.get(a.machine, None),
 196                                 arch.machine_ranks.get(b.machine, None))
 197                         if r: return r
 198
 199                         # Slightly prefer cached versions
 200                         if self.network_use == model.network_full:
 201                                 r = cmp(get_cached(a), get_cached(b))
 202                                 if r: return r
 203
 204                         return cmp(a.id, b.id)
 205
 206                 def usable_feeds(iface, arch):
 207                         """Return all feeds for iface that support arch.
 208                         @rtype: generator(ZeroInstallFeed)"""
 209                         yield iface.uri
 210
 211                         for f in iface.feeds:
 212                                 if f.os in arch.os_ranks and f.machine in arch.machine_ranks:
 213                                         yield f.uri
 214                                 else:
 215                                         debug("Skipping '%s'; unsupported architecture %s-%s",
 216                                                 f, f.os, f.machine)
 217
 218                 def is_unusable(impl, restrictions, arch):
 219                         """@return: whether this implementation is unusable.
 220                         @rtype: bool"""
 221                         return get_unusable_reason(impl, restrictions, arch) != None
 222
 223                 def get_unusable_reason(impl, restrictions, arch):
 224                         """
 225                         @param impl: Implementation to test.
 226                         @type restrictions: [L{model.Restriction}]
 227                         @return: The reason why this impl is unusable, or None if it's OK.
 228                         @rtype: str
 229                         @note: The restrictions are for the interface being requested, not the interface
 230                         of the implementation; they may be different when feeds are being used."""
 231                         for r in restrictions:
 232                                 if not r.meets_restriction(impl):
 233                                         return "Incompatible with another selected implementation"
 234                         stability = impl.get_stability()
 235                         if stability <= model.buggy:
 236                                 return stability.name
 237                         if self.network_use == model.network_offline and not get_cached(impl):
 238                                 return "Not cached and we are off-line"
 239                         if impl.os not in arch.os_ranks:
 240                                 return "Unsupported OS"
 241                         # When looking for source code, we need to known if we're
 242                         # looking at an implementation of the root interface, even if
 243                         # it's from a feed, hence the sneaky restrictions identity check.
 244                         if impl.machine not in arch.machine_ranks:
 245                                 if impl.machine == 'src':
 246                                         return "Source code"
 247                                 return "Unsupported machine type"
 248                         return None
 249
 250                 def get_cached(impl):
 251                         """Check whether an implementation is available locally.
 252                         @type impl: model.Implementation
 253                         @rtype: bool
 254                         """
 255                         if isinstance(impl, model.DistributionImplementation):
 256                                 return impl.installed
 257                         if impl.id.startswith('/'):
 258                                 return os.path.exists(impl.id)
 259                         else:
 260                                 try:
 261                                         path = self.stores.lookup(impl.id)
 262                                         assert path
 263                                         return True
 264                                 except BadDigest:
 265                                         return False
 266                                 except NotStored:
 267                                         return False
 268
 269                 self.ready = process(model.InterfaceDependency(root_interface), arch)