2 Chooses a set of components to make a running program.
5 # Copyright (C) 2009, Thomas Leonard
6 # See the README file for details, or visit http://0install.net.
8 from zeroinstall
import _
9 import os
, tempfile
, subprocess
, sys
, locale
10 from logging
import debug
, warn
, info
12 from zeroinstall
.zerostore
import BadDigest
, NotStored
14 from zeroinstall
.injector
.arch
import machine_groups
15 from zeroinstall
.injector
import model
, sat
17 def _get_cached(stores
, impl
):
18 """Check whether an implementation is available locally.
19 @type impl: model.Implementation
22 if isinstance(impl
, model
.DistributionImplementation
):
25 return os
.path
.exists(impl
.local_path
)
29 warn("No digests given for %s!", impl
)
31 path
= stores
.lookup_any(impl
.digests
)
42 def __init__(self
, iface
, impl
, arch
, dummy
= False):
50 name
= "%s_%s_%s" % (self
.impl
.feed
.get_name(), self
.impl
.get_version(), self
.impl
.arch
)
51 return name
.replace('-', '_').replace('.', '_')
53 class _DummyImpl(object):
61 feed
= property(lambda self
: self
)
63 def get_version(self
):
70 """Chooses a set of implementations to satisfy the requirements of a program and its user.
72 1. Create a Solver object and configure it
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)]}
87 __slots__
= ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
90 self
.selections
= self
.requires
= self
.feeds_used
= self
.details
= None
91 self
.record_details
= False
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")
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.
107 def __init__(self
, network_use
, iface_cache
, stores
, extra_restrictions
= None):
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}]}
118 Solver
.__init
__(self
)
119 self
.network_use
= network_use
120 self
.iface_cache
= iface_cache
122 self
.help_with_testing
= False
123 self
.extra_restrictions
= extra_restrictions
or {}
125 self
.langs
= [locale
.getlocale()[0] or 'en']
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.
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
))
142 a_stab
= a
.get_stability()
143 b_stab
= b
.get_stability()
145 # Preferred versions come first
146 r
= cmp(a_stab
== model
.preferred
, b_stab
== model
.preferred
)
150 if self
.network_use
!= model
.network_full
:
151 r
= cmp(_get_cached(stores
, a
), _get_cached(stores
, b
))
154 # Packages that require admin access to install come last
155 r
= cmp(b
.requires_root_install
, a
.requires_root_install
)
159 stab_policy
= interface
.stability_policy
161 if self
.help_with_testing
: stab_policy
= model
.testing
162 else: stab_policy
= model
.stable
164 if a_stab
>= stab_policy
: a_stab
= model
.preferred
165 if b_stab
>= stab_policy
: b_stab
= model
.preferred
167 r
= cmp(a_stab
, b_stab
)
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])
176 # Othewise, prefer native package
177 return cmp(a
.id.startswith('package:'), b
.id.startswith('package:'))
179 r
= cmp(a
.version
, b
.version
)
183 r
= cmp(arch
.os_ranks
.get(b
.os
, None),
184 arch
.os_ranks
.get(a
.os
, None))
188 r
= cmp(arch
.machine_ranks
.get(b
.machine
, None),
189 arch
.machine_ranks
.get(a
.machine
, None))
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
))
197 # Slightly prefer cached versions
198 if self
.network_use
== model
.network_full
:
199 r
= cmp(_get_cached(stores
, a
), _get_cached(stores
, b
))
202 return cmp(a
.id, b
.id)
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.
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
216 problem
= sat
.Solver()
218 impl_to_var
= {} # Impl -> sat var
219 self
.feeds_used
= set()
222 self
.details
= self
.record_details
and {}
224 self
.selections
= None
226 ifaces_processed
= set()
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
] = []
232 impls_for_iface
= {} # Iface -> [impl]
234 group_clause_for
= {} # Iface URI -> AtMostOneClause | bool
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 not r
.meets_restriction(candidate
):
242 #warn("%s rejected due to %s", candidate.get_version(), r)
243 if candidate
.version
is not None:
245 # else it's the dummy version that matches everything
247 c_var
= impl_to_var
.get(candidate
, None)
248 if c_var
is not None:
249 dep_union
.append(c_var
)
250 # else we filtered that version out, so ignore it
252 problem
.add_clause(dep_union
)
254 problem
.assign(requiring_impl_var
, 0)
256 def is_unusable(impl
, restrictions
, arch
):
257 """@return: whether this implementation is unusable.
259 return get_unusable_reason(impl
, restrictions
, arch
) != None
261 def get_unusable_reason(impl
, restrictions
, arch
):
263 @param impl: Implementation to test.
264 @type restrictions: [L{model.Restriction}]
265 @return: The reason why this impl is unusable, or None if it's OK.
267 @note: The restrictions are for the interface being requested, not the feed
268 of the implementation; they may be different when feeds are being used."""
269 for r
in restrictions
:
270 if not r
.meets_restriction(impl
):
271 return _("Incompatible with another selected implementation")
272 stability
= impl
.get_stability()
273 if stability
<= model
.buggy
:
274 return stability
.name
275 if (self
.network_use
== model
.network_offline
or not impl
.download_sources
) and not _get_cached(self
.stores
, impl
):
276 if not impl
.download_sources
:
277 return _("No retrieval methods")
278 return _("Not cached and we are off-line")
279 if impl
.os
not in arch
.os_ranks
:
280 return _("Unsupported OS")
281 if impl
.machine
not in arch
.machine_ranks
:
282 if impl
.machine
== 'src':
283 return _("Source code")
284 return _("Unsupported machine type")
287 def usable_feeds(iface
, arch
):
288 """Return all feeds for iface that support arch.
289 @rtype: generator(ZeroInstallFeed)"""
292 # Note: we only look one level deep here. Maybe we should recurse further?
293 feeds
= iface
.extra_feeds
294 main_feed
= self
.iface_cache
.get_feed(iface
.uri
)
296 feeds
= feeds
+ main_feed
.feeds
299 # Note: when searching for src, None is not in machine_ranks
300 if f
.os
in arch
.os_ranks
and \
301 (f
.machine
is None or f
.machine
in arch
.machine_ranks
):
304 debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
305 {'feed': f
, 'os': f
.os
, 'machine': f
.machine
})
307 def add_iface(uri
, arch
):
308 """Name implementations from feed, assign costs and assert that one one can be selected."""
309 if uri
in ifaces_processed
: return
310 ifaces_processed
.add(uri
)
311 iface_name
= 'i%d' % len(ifaces_processed
)
313 iface
= self
.iface_cache
.get_interface(uri
)
316 for f
in usable_feeds(iface
, arch
):
317 self
.feeds_used
.add(f
)
318 debug(_("Processing feed %s"), f
)
321 feed
= self
.iface_cache
.get_feed(f
)
322 if feed
is None: continue
323 if feed
.name
and iface
.uri
!= feed
.url
and iface
.uri
not in feed
.feed_for
:
324 info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface
.uri
, 'feed': f
})
326 if feed
.implementations
:
327 impls
.extend(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
})
331 impls
.sort(lambda a
, b
: self
.compare(iface
, a
, b
, arch
))
333 impls_for_iface
[iface
] = filtered_impls
= []
335 my_extra_restrictions
= self
.extra_restrictions
.get(iface
, [])
337 if self
.record_details
:
338 self
.details
[iface
] = [(impl
, get_unusable_reason(impl
, my_extra_restrictions
, arch
)) for impl
in impls
]
343 if is_unusable(impl
, my_extra_restrictions
, arch
):
346 filtered_impls
.append(impl
)
348 assert impl
not in impl_to_var
349 v
= problem
.add_variable(ImplInfo(iface
, impl
, arch
))
350 impl_to_var
[impl
] = v
354 if impl
.machine
and impl
.machine
!= 'src':
355 impls_for_machine_group
[machine_groups
.get(impl
.machine
, 0)].append(v
)
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
)
364 add_iface(d
.interface
, arch
.child_arch
)
366 # Must choose one version of d if impl is selected
367 find_dependency_candidates(v
, d
)
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
)
376 # Only one implementation of this interface can be selected
377 if uri
== root_interface
:
379 clause
= problem
.at_most_one(var_names
)
380 problem
.add_clause(var_names
) # at least one
385 clause
= problem
.at_most_one(var_names
)
387 # Don't need to add to group_clause_for because we should
388 # never get a possible selection involving this.
391 assert clause
is not True
392 assert clause
is not None
393 if clause
is not False:
394 group_clause_for
[uri
] = clause
396 add_iface(root_interface
, root_arch
)
398 # Require m<group> to be true if we select an implementation in that group
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
)
405 problem
.add_clause([group_var
, sat
.neg(impl
)])
406 m_groups
.append(group_var
)
408 m_groups_clause
= problem
.at_most_one(m_groups
)
410 m_groups_clause
= None
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."""
417 def find_undecided(uri
):
419 return # Break cycles
422 group
= group_clause_for
[uri
]
423 #print "Group for %s = %s" % (uri, group)
426 return group
.best_undecided()
427 # else there was only one choice anyway
429 # Check for undecided dependencies
430 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
432 for dep
in lit_info
.impl
.requires
:
433 use
= dep
.metadata
.get("use", None)
434 if use
not in lit_info
.arch
.use
:
436 dep_lit
= find_undecided(dep
.interface
)
437 if dep_lit
is not None:
440 # This whole sub-tree is decided
443 best
= find_undecided(root_interface
)
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()
455 return None # Failed to find any valid combination
457 ready
= problem
.run_solver(decide
) is True
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)
465 self
.ready
= ready
and not closest_match
468 for uri
, group
in group_clause_for
.iteritems():
469 if group
.current
is not None:
470 lit_info
= problem
.get_varinfo_for_lit(group
.current
).obj
471 if lit_info
.is_dummy
:
472 self
.selections
[lit_info
.iface
] = None
474 self
.selections
[lit_info
.iface
] = lit_info
.impl
475 deps
= self
.requires
[lit_info
.iface
] = []
476 for dep
in lit_info
.impl
.requires
:
477 use
= dep
.metadata
.get("use", None)
478 if use
not in lit_info
.arch
.use
:
483 DefaultSolver
= SATSolver