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 _
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
, selections
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
)
40 def __init__(self
, name
, command
, impl
, arch
):
42 self
.command
= command
47 name
= "%s_%s_%s_%s" % (self
.impl
.feed
.get_name(), self
.impl
.get_version(), self
.impl
.arch
, self
.name
)
48 return name
.replace('-', '_').replace('.', '_')
53 def __init__(self
, iface
, impl
, arch
, dummy
= False):
61 name
= "%s_%s_%s" % (self
.impl
.feed
.get_name(), self
.impl
.get_version(), self
.impl
.arch
)
62 return name
.replace('-', '_').replace('.', '_')
64 def _get_command_name(runner
):
65 """Returns the 'command' attribute of a <runner>, or 'run' if there isn't one."""
66 return runner
.qdom
.attrs
.get('command', 'run')
68 class _DummyImpl(object):
77 feed
= property(lambda self
: self
)
79 def get_version(self
):
86 """Chooses a set of implementations to satisfy the requirements of a program and its user.
88 1. Create a Solver object and configure it
90 3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
91 4. If it is 'ready' then you can download and run the chosen versions.
92 @ivar selections: the chosen implementation of each interface
93 @type selections: L{selections.Selections}
94 @ivar requires: the selected dependencies for each chosen version
95 @type requires: {L{model.Interface}: [L{model.Dependency}]}
96 @ivar feeds_used: the feeds which contributed to the choice in L{selections}
97 @type feeds_used: set(str)
98 @ivar record_details: whether to record information about unselected implementations
99 @type record_details: {L{Interface}: [(L{Implementation}, str)]}
100 @ivar details: extra information, if record_details mode was used
101 @type details: {str: [(Implementation, comment)]}
103 __slots__
= ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
106 self
.selections
= self
.requires
= self
.feeds_used
= self
.details
= None
107 self
.record_details
= False
110 def solve(self
, root_interface
, root_arch
, command_name
= 'run'):
111 """Get the best implementation of root_interface and all of its dependencies.
112 @param root_interface: the URI of the program to be solved
113 @type root_interface: str
114 @param root_arch: the desired target architecture
115 @type root_arch: L{arch.Architecture}
116 @param command_name: which <command> element to select
117 @type command_name: str | None
118 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
119 raise NotImplementedError("Abstract")
121 class SATSolver(Solver
):
122 __slots__
= ['_failure_reason', 'config', 'extra_restrictions', 'langs']
125 def iface_cache(self
):
126 return self
.config
.iface_cache
# (deprecated; used by 0compile)
128 """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them.
129 @ivar langs: the preferred languages (e.g. ["es_ES", "en"]). Initialised to the current locale.
131 def __init__(self
, config
, extra_restrictions
= None):
133 @param network_use: how much use to make of the network
134 @type network_use: L{model.network_levels}
135 @param config: policy preferences (e.g. stability), the iface_cache and the stores to use
136 @type config: L{policy.Config}
137 @param extra_restrictions: extra restrictions on the chosen implementations
138 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
140 Solver
.__init
__(self
)
141 assert not isinstance(config
, str), "API change!"
143 self
.extra_restrictions
= extra_restrictions
or {}
145 self
.langs
= [locale
.getlocale()[0] or 'en']
147 def compare(self
, interface
, b
, a
, arch
):
148 """Compare a and b to see which would be chosen first.
149 Does not consider whether the implementations are usable (check for that yourself first).
150 @param interface: The interface we are trying to resolve, which may
151 not be the interface of a or b if they are from feeds.
154 # Languages we understand come first
155 a_langs
= (a
.langs
or 'en').split()
156 b_langs
= (b
.langs
or 'en').split()
157 main_langs
= set(l
.split('_')[0] for l
in self
.langs
)
158 r
= cmp(any(l
.split('_')[0] in main_langs
for l
in a_langs
),
159 any(l
.split('_')[0] in main_langs
for l
in b_langs
))
162 a_stab
= a
.get_stability()
163 b_stab
= b
.get_stability()
165 # Preferred versions come first
166 r
= cmp(a_stab
== model
.preferred
, b_stab
== model
.preferred
)
169 stores
= self
.config
.stores
170 if self
.config
.network_use
!= model
.network_full
:
171 r
= cmp(_get_cached(stores
, a
), _get_cached(stores
, b
))
174 # Packages that require admin access to install come last
175 r
= cmp(b
.requires_root_install
, a
.requires_root_install
)
179 stab_policy
= interface
.stability_policy
181 if self
.config
.help_with_testing
: stab_policy
= model
.testing
182 else: stab_policy
= model
.stable
184 if a_stab
>= stab_policy
: a_stab
= model
.preferred
185 if b_stab
>= stab_policy
: b_stab
= model
.preferred
187 r
= cmp(a_stab
, b_stab
)
190 # Newer versions come before older ones
191 if a
.id.startswith('package:') != b
.id.startswith('package:'):
192 # If one of packages is native, do not compare full versions since
193 # it is useless to compare native and 0install version revisions
194 r
= cmp(a
.version
[0], b
.version
[0])
196 # Othewise, prefer native package
197 return cmp(a
.id.startswith('package:'), b
.id.startswith('package:'))
199 r
= cmp(a
.version
, b
.version
)
203 r
= cmp(arch
.os_ranks
.get(b
.os
, None),
204 arch
.os_ranks
.get(a
.os
, None))
208 r
= cmp(arch
.machine_ranks
.get(b
.machine
, None),
209 arch
.machine_ranks
.get(a
.machine
, None))
212 # Slightly prefer languages specialised to our country
213 r
= cmp(any(l
in self
.langs
for l
in a_langs
),
214 any(l
in self
.langs
for l
in b_langs
))
217 # Slightly prefer cached versions
218 if self
.config
.network_use
== model
.network_full
:
219 r
= cmp(_get_cached(stores
, a
), _get_cached(stores
, b
))
222 return cmp(a
.id, b
.id)
224 def solve(self
, root_interface
, root_arch
, command_name
= 'run', closest_match
= False):
225 # closest_match is used internally. It adds a lowest-ranked
226 # by valid implementation to every interface, so we can always
227 # select something. Useful for diagnostics.
229 # TODO: We need some way to figure out which feeds to include.
230 # Currently, we include any feed referenced from anywhere but
231 # this is probably too much. We could insert a dummy optimial
232 # implementation in stale/uncached feeds and see whether it
234 iface_cache
= self
.config
.iface_cache
236 problem
= sat
.SATProblem()
238 impl_to_var
= {} # Impl -> sat var
239 self
.feeds_used
= set()
242 self
.details
= self
.record_details
and {}
244 self
.selections
= None
245 self
._failure
_reason
= None
247 ifaces_processed
= set()
249 impls_for_machine_group
= {0 : []} # Machine group (e.g. "64") to [impl] in that group
250 for machine_group
in machine_groups
.values():
251 impls_for_machine_group
[machine_group
] = []
253 impls_for_iface
= {} # Iface -> [impl]
255 group_clause_for
= {} # Iface URI -> AtMostOneClause | bool
256 group_clause_for_command
= {} # (Iface URI, command name) -> AtMostOneClause | bool
258 # Return the dependencies of impl that we should consider.
259 # Skips dependencies if the use flag isn't what we need.
260 # (note: impl may also be a model.Command)
261 def deps_in_use(impl
, arch
):
262 for dep
in impl
.requires
:
263 use
= dep
.metadata
.get("use", None)
264 if use
not in arch
.use
:
268 # Add a clause so that if requiring_impl_var is True then an implementation
269 # matching 'dependency' must also be selected.
270 # Must have already done add_iface on dependency.interface.
271 def find_dependency_candidates(requiring_impl_var
, dependency
):
272 dep_iface
= iface_cache
.get_interface(dependency
.interface
)
273 dep_union
= [sat
.neg(requiring_impl_var
)] # Either requiring_impl_var is False, or ...
274 for candidate
in impls_for_iface
[dep_iface
]:
275 for r
in dependency
.restrictions
:
276 if candidate
.__class
__ is not _DummyImpl
and not r
.meets_restriction(candidate
):
277 #warn("%s rejected due to %s", candidate.get_version(), r)
278 if candidate
.version
is not None:
281 c_var
= impl_to_var
.get(candidate
, None)
282 if c_var
is not None:
283 dep_union
.append(c_var
)
284 # else we filtered that version out, so ignore it
287 problem
.add_clause(dep_union
)
289 def is_unusable(impl
, restrictions
, arch
):
290 """@return: whether this implementation is unusable.
292 return get_unusable_reason(impl
, restrictions
, arch
) != None
294 def get_unusable_reason(impl
, restrictions
, arch
):
296 @param impl: Implementation to test.
297 @type restrictions: [L{model.Restriction}]
298 @return: The reason why this impl is unusable, or None if it's OK.
300 @note: The restrictions are for the interface being requested, not the feed
301 of the implementation; they may be different when feeds are being used."""
302 for r
in restrictions
:
303 if not r
.meets_restriction(impl
):
304 return _("Incompatible with another selected implementation")
305 stability
= impl
.get_stability()
306 if stability
<= model
.buggy
:
307 return stability
.name
308 if (self
.config
.network_use
== model
.network_offline
or not impl
.download_sources
) and not _get_cached(self
.config
.stores
, impl
):
309 if not impl
.download_sources
:
310 return _("No retrieval methods")
311 return _("Not cached and we are off-line")
312 if impl
.os
not in arch
.os_ranks
:
313 return _("Unsupported OS")
314 if impl
.machine
not in arch
.machine_ranks
:
315 if impl
.machine
== 'src':
316 return _("Source code")
317 return _("Unsupported machine type")
320 def usable_feeds(iface
, arch
):
321 """Return all feeds for iface that support arch.
322 @rtype: generator(ZeroInstallFeed)"""
325 for f
in iface_cache
.get_feed_imports(iface
):
326 # Note: when searching for src, None is not in machine_ranks
327 if f
.os
in arch
.os_ranks
and \
328 (f
.machine
is None or f
.machine
in arch
.machine_ranks
):
331 debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
332 {'feed': f
, 'os': f
.os
, 'machine': f
.machine
})
334 def add_iface(uri
, arch
):
335 """Name implementations from feed and assert that only one can be selected."""
336 if uri
in ifaces_processed
: return
337 ifaces_processed
.add(uri
)
339 iface
= iface_cache
.get_interface(uri
)
342 for f
in usable_feeds(iface
, arch
):
343 self
.feeds_used
.add(f
)
344 debug(_("Processing feed %s"), f
)
347 feed
= iface_cache
.get_feed(f
)
348 if feed
is None: continue
349 #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
350 # info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
352 if feed
.implementations
:
353 impls
.extend(feed
.implementations
.values())
355 distro_feed_url
= feed
.get_distro_feed()
357 self
.feeds_used
.add(distro_feed_url
)
358 distro_feed
= iface_cache
.get_feed(distro_feed_url
)
359 if distro_feed
.implementations
:
360 impls
.extend(distro_feed
.implementations
.values())
361 except Exception, ex
:
362 warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f
, 'interface': iface
, 'exception': ex
})
365 impls
.sort(lambda a
, b
: self
.compare(iface
, a
, b
, arch
))
367 impls_for_iface
[iface
] = filtered_impls
= []
369 my_extra_restrictions
= self
.extra_restrictions
.get(iface
, [])
371 if self
.record_details
:
372 self
.details
[iface
] = [(impl
, get_unusable_reason(impl
, my_extra_restrictions
, arch
)) for impl
in impls
]
377 if is_unusable(impl
, my_extra_restrictions
, arch
):
380 filtered_impls
.append(impl
)
382 assert impl
not in impl_to_var
383 v
= problem
.add_variable(ImplInfo(iface
, impl
, arch
))
384 impl_to_var
[impl
] = v
388 if impl
.machine
and impl
.machine
!= 'src':
389 impls_for_machine_group
[machine_groups
.get(impl
.machine
, 0)].append(v
)
391 for d
in deps_in_use(impl
, arch
):
392 debug(_("Considering dependency %s"), d
)
394 add_iface(d
.interface
, arch
.child_arch
)
396 # Must choose one version of d if impl is selected
397 find_dependency_candidates(v
, d
)
400 dummy_impl
= _DummyImpl()
401 dummy_var
= problem
.add_variable(ImplInfo(iface
, dummy_impl
, arch
, dummy
= True))
402 var_names
.append(dummy_var
)
403 impl_to_var
[dummy_impl
] = dummy_var
404 filtered_impls
.append(dummy_impl
)
406 # Only one implementation of this interface can be selected
407 if uri
== root_interface
:
409 clause
= problem
.at_most_one(var_names
)
410 problem
.add_clause(var_names
) # at least one
415 clause
= problem
.at_most_one(var_names
)
417 # Don't need to add to group_clause_for because we should
418 # never get a possible selection involving this.
421 assert clause
is not True
422 assert clause
is not None
423 if clause
is not False:
424 group_clause_for
[uri
] = clause
426 def add_command_iface(uri
, arch
, command_name
):
427 """Add every <command> in interface 'uri' with this name.
428 Each one depends on the corresponding implementation and only
429 one can be selected."""
430 # First ensure that the interface itself has been processed
431 # We'll reuse the ordering of the implementations to order
435 iface
= iface_cache
.get_interface(uri
)
436 filtered_impls
= impls_for_iface
[iface
]
439 for impl
in filtered_impls
:
440 command
= impl
.commands
.get(command_name
, None)
442 if not isinstance(impl
, _DummyImpl
):
443 # Mark implementation as unselectable
444 problem
.add_clause([sat
.neg(impl_to_var
[impl
])])
447 # We have a candidate <command>. Require that if it's selected
448 # then we select the corresponding <implementation> too.
449 command_var
= problem
.add_variable(CommandInfo(command_name
, command
, impl
, arch
))
450 problem
.add_clause([impl_to_var
[impl
], sat
.neg(command_var
)])
452 var_names
.append(command_var
)
454 runner
= command
.get_runner()
455 for d
in deps_in_use(command
, arch
):
457 # With a <runner>, we depend on a command rather than on an
458 # implementation. This allows us to support recursive <runner>s, etc.
459 debug(_("Considering command runner %s"), d
)
460 runner_command_name
= _get_command_name(d
)
461 runner_vars
= add_command_iface(d
.interface
, arch
.child_arch
, runner_command_name
)
464 dummy_command
= problem
.add_variable(None)
465 runner_vars
.append(dummy_command
)
466 # If the parent command is chosen, one of the candidate runner commands
467 # must be too. If there aren't any, then this command is unselectable.
468 problem
.add_clause([sat
.neg(command_var
)] + runner_vars
)
470 # Can't select more than one of them.
471 group_clause_for_command
[(d
.interface
, runner_command_name
)] = problem
.at_most_one(runner_vars
)
473 debug(_("Considering command dependency %s"), d
)
474 add_iface(d
.interface
, arch
.child_arch
)
476 # Must choose one version of d if impl is selected
477 find_dependency_candidates(command_var
, d
)
479 # Tell the user why we couldn't use this version
480 if self
.record_details
:
481 def new_reason(impl
, old_reason
):
482 if command_name
in impl
.commands
:
484 return old_reason
or (_('No %s command') % command_name
)
485 self
.details
[iface
] = [(impl
, new_reason(impl
, reason
)) for (impl
, reason
) in self
.details
[iface
]]
489 if command_name
is None:
490 add_iface(root_interface
, root_arch
)
492 commands
= add_command_iface(root_interface
, root_arch
, command_name
)
494 problem
.add_clause(commands
) # At least one
495 group_clause_for_command
[(root_interface
, command_name
)] = problem
.at_most_one(commands
)
497 # (note: might be because we haven't cached it yet)
498 info("No %s <command> in %s", command_name
, root_interface
)
500 impls
= impls_for_iface
[iface_cache
.get_interface(root_interface
)]
501 if impls
== [] or (len(impls
) == 1 and isinstance(impls
[0], _DummyImpl
)):
502 # There were no candidates at all.
503 self
._failure
_reason
= _("Interface '%s' has no usable implementations") % root_interface
505 # We had some candidates implementations, but none for the command we need
506 self
._failure
_reason
= _("Interface '%s' cannot be executed directly; it is just a library "
507 "to be used by other programs (or missing '%s' command)") % (root_interface
, command_name
)
511 # Require m<group> to be true if we select an implementation in that group
513 for machine_group
, impls
in impls_for_machine_group
.iteritems():
514 m_group
= 'm%d' % machine_group
515 group_var
= problem
.add_variable(m_group
)
518 problem
.add_clause([group_var
, sat
.neg(impl
)])
519 m_groups
.append(group_var
)
521 m_groups_clause
= problem
.at_most_one(m_groups
)
523 m_groups_clause
= None
526 """Recurse through the current selections until we get to an interface with
527 no chosen version, then tell the solver to try the best version from that."""
529 def find_undecided_dep(impl_or_command
, arch
):
530 # Check for undecided dependencies of impl_or_command
531 for dep
in deps_in_use(impl_or_command
, arch
):
532 if dep
.qdom
.name
== 'runner':
533 dep_lit
= find_undecided_command(dep
.interface
, _get_command_name(dep
))
535 dep_lit
= find_undecided(dep
.interface
)
536 if dep_lit
is not None:
541 def find_undecided(uri
):
543 return # Break cycles
546 group
= group_clause_for
[uri
]
547 #print "Group for %s = %s" % (uri, group)
550 return group
.best_undecided()
551 # else there was only one choice anyway
553 # Check for undecided dependencies
554 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
555 return find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
557 def find_undecided_command(uri
, name
):
558 if name
is None: return find_undecided(uri
)
560 group
= group_clause_for_command
[(uri
, name
)]
563 return group
.best_undecided()
564 # else we've already chosen which <command> to use
566 # Check for undecided command-specific dependencies, and then for
567 # implementation dependencies.
568 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
571 return None # (a dummy command added for better diagnostics; has no dependencies)
572 return find_undecided_dep(lit_info
.command
, lit_info
.arch
) or \
573 find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
575 best
= find_undecided_command(root_interface
, command_name
)
579 # If we're chosen everything we need, we can probably
580 # set everything else to False.
581 for group
in group_clause_for
.values() + group_clause_for_command
.values() + [m_groups_clause
]:
582 if group
.current
is None:
583 best
= group
.best_undecided()
587 return None # Failed to find any valid combination
589 ready
= problem
.run_solver(decide
) is True
591 if not ready
and not closest_match
:
592 # We failed while trying to do a real solve.
593 # Try a closest match solve to get a better
594 # error report for the user.
595 self
.solve(root_interface
, root_arch
, command_name
= command_name
, closest_match
= True)
597 self
.ready
= ready
and not closest_match
598 self
.selections
= selections
.Selections(None)
599 self
.selections
.interface
= root_interface
601 sels
= self
.selections
.selections
603 for uri
, group
in group_clause_for
.iteritems():
604 if group
.current
is not None:
605 lit_info
= problem
.get_varinfo_for_lit(group
.current
).obj
606 if lit_info
.is_dummy
:
607 sels
[lit_info
.iface
.uri
] = None
611 deps
= self
.requires
[lit_info
.iface
] = []
612 for dep
in deps_in_use(lit_info
.impl
, lit_info
.arch
):
615 sels
[lit_info
.iface
.uri
] = selections
.ImplSelection(lit_info
.iface
.uri
, impl
, deps
)
617 def add_command(iface
, name
):
618 sel
= sels
.get(iface
, None)
620 command
= sel
.impl
.commands
[name
]
621 self
.selections
.commands
.append(command
)
622 runner
= command
.get_runner()
624 add_command(runner
.metadata
['interface'], _get_command_name(runner
))
626 if command_name
is not None:
627 add_command(root_interface
, command_name
)
629 def get_failure_reason(self
):
630 """Return an exception explaining why the solve failed."""
631 assert not self
.ready
633 if self
._failure
_reason
:
634 return model
.SafeException(self
._failure
_reason
)
636 return model
.SafeException(_("Can't find all required implementations:") + '\n' +
637 '\n'.join(["- %s -> %s" % (iface
, self
.selections
[iface
])
638 for iface
in self
.selections
]))
640 DefaultSolver
= SATSolver