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
.injector
.arch
import machine_groups
13 from zeroinstall
.injector
import model
, sat
, selections
16 def __init__(self
, name
, command
, impl
, arch
):
18 self
.command
= command
23 name
= "%s_%s_%s_%s" % (self
.impl
.feed
.get_name(), self
.impl
.get_version(), self
.impl
.arch
, self
.name
)
24 return name
.replace('-', '_').replace('.', '_')
29 def __init__(self
, iface
, impl
, arch
, dummy
= False):
37 name
= "%s_%s_%s" % (self
.impl
.feed
.get_name(), self
.impl
.get_version(), self
.impl
.arch
)
38 return name
.replace('-', '_').replace('.', '_')
40 def _get_command_name(runner
):
41 """Returns the 'command' attribute of a <runner>, or 'run' if there isn't one."""
42 return runner
.qdom
.attrs
.get('command', 'run')
44 class _DummyImpl(object):
53 feed
= property(lambda self
: self
)
55 def get_version(self
):
62 """Chooses a set of implementations to satisfy the requirements of a program and its user.
64 1. Create a Solver object and configure it
66 3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
67 4. If it is 'ready' then you can download and run the chosen versions.
68 @ivar selections: the chosen implementation of each interface
69 @type selections: L{selections.Selections}
70 @ivar requires: the selected dependencies for each chosen version
71 @type requires: {L{model.Interface}: [L{model.Dependency}]}
72 @ivar feeds_used: the feeds which contributed to the choice in L{selections}
73 @type feeds_used: set(str)
74 @ivar record_details: whether to record information about unselected implementations
75 @type record_details: {L{Interface}: [(L{Implementation}, str)]}
76 @ivar details: extra information, if record_details mode was used
77 @type details: {str: [(Implementation, comment)]}
79 __slots__
= ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
82 self
.selections
= self
.requires
= self
.feeds_used
= self
.details
= None
83 self
.record_details
= False
86 def solve(self
, root_interface
, root_arch
, command_name
= 'run'):
87 """Get the best implementation of root_interface and all of its dependencies.
88 @param root_interface: the URI of the program to be solved
89 @type root_interface: str
90 @param root_arch: the desired target architecture
91 @type root_arch: L{arch.Architecture}
92 @param command_name: which <command> element to select
93 @type command_name: str | None
94 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
95 raise NotImplementedError("Abstract")
97 class SATSolver(Solver
):
98 __slots__
= ['_failure_reason', 'config', 'extra_restrictions', 'langs']
101 def iface_cache(self
):
102 return self
.config
.iface_cache
# (deprecated; used by 0compile)
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
, config
, extra_restrictions
= None):
109 @param config: policy preferences (e.g. stability), the iface_cache and the stores to use
110 @type config: L{policy.Config}
111 @param extra_restrictions: extra restrictions on the chosen implementations
112 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
114 Solver
.__init
__(self
)
115 assert not isinstance(config
, str), "API change!"
117 self
.extra_restrictions
= extra_restrictions
or {}
119 self
.langs
= [locale
.getlocale()[0] or 'en']
121 def compare(self
, interface
, b
, a
, arch
):
122 """Compare a and b to see which would be chosen first.
123 Does not consider whether the implementations are usable (check for that yourself first).
124 @param interface: The interface we are trying to resolve, which may
125 not be the interface of a or b if they are from feeds.
128 # Languages we understand come first
129 a_langs
= (a
.langs
or 'en').split()
130 b_langs
= (b
.langs
or 'en').split()
131 main_langs
= set(l
.split('_')[0] for l
in self
.langs
)
132 r
= cmp(any(l
.split('_')[0] in main_langs
for l
in a_langs
),
133 any(l
.split('_')[0] in main_langs
for l
in b_langs
))
136 a_stab
= a
.get_stability()
137 b_stab
= b
.get_stability()
139 # Preferred versions come first
140 r
= cmp(a_stab
== model
.preferred
, b_stab
== model
.preferred
)
143 stores
= self
.config
.stores
144 if self
.config
.network_use
!= model
.network_full
:
145 r
= cmp(a
.is_available(stores
), b
.is_available(stores
))
148 # Packages that require admin access to install come last
149 r
= cmp(b
.requires_root_install
, a
.requires_root_install
)
153 stab_policy
= interface
.stability_policy
155 if self
.config
.help_with_testing
: stab_policy
= model
.testing
156 else: stab_policy
= model
.stable
158 if a_stab
>= stab_policy
: a_stab
= model
.preferred
159 if b_stab
>= stab_policy
: b_stab
= model
.preferred
161 r
= cmp(a_stab
, b_stab
)
164 # Newer versions come before older ones
165 if a
.id.startswith('package:') != b
.id.startswith('package:'):
166 # If one of packages is native, do not compare full versions since
167 # it is useless to compare native and 0install version revisions
168 r
= cmp(a
.version
[0], b
.version
[0])
170 # Othewise, prefer native package
171 return cmp(a
.id.startswith('package:'), b
.id.startswith('package:'))
173 r
= cmp(a
.version
, b
.version
)
177 r
= cmp(arch
.os_ranks
.get(b
.os
, None),
178 arch
.os_ranks
.get(a
.os
, None))
182 r
= cmp(arch
.machine_ranks
.get(b
.machine
, None),
183 arch
.machine_ranks
.get(a
.machine
, None))
186 # Slightly prefer languages specialised to our country
187 r
= cmp(any(l
in self
.langs
for l
in a_langs
),
188 any(l
in self
.langs
for l
in b_langs
))
191 # Slightly prefer cached versions
192 if self
.config
.network_use
== model
.network_full
:
193 r
= cmp(a
.is_available(stores
), b
.is_available(stores
))
196 return cmp(a
.id, b
.id)
198 def solve(self
, root_interface
, root_arch
, command_name
= 'run', closest_match
= False):
199 # closest_match is used internally. It adds a lowest-ranked
200 # by valid implementation to every interface, so we can always
201 # select something. Useful for diagnostics.
203 # TODO: We need some way to figure out which feeds to include.
204 # Currently, we include any feed referenced from anywhere but
205 # this is probably too much. We could insert a dummy optimial
206 # implementation in stale/uncached feeds and see whether it
208 iface_cache
= self
.config
.iface_cache
210 problem
= sat
.SATProblem()
212 impl_to_var
= {} # Impl -> sat var
213 self
.feeds_used
= set()
216 self
.details
= self
.record_details
and {}
218 self
.selections
= None
219 self
._failure
_reason
= None
221 ifaces_processed
= set()
223 impls_for_machine_group
= {0 : []} # Machine group (e.g. "64") to [impl] in that group
224 for machine_group
in machine_groups
.values():
225 impls_for_machine_group
[machine_group
] = []
227 impls_for_iface
= {} # Iface -> [impl]
229 group_clause_for
= {} # Iface URI -> AtMostOneClause | bool
230 group_clause_for_command
= {} # (Iface URI, command name) -> AtMostOneClause | bool
232 # Return the dependencies of impl that we should consider.
233 # Skips dependencies if the use flag isn't what we need.
234 # (note: impl may also be a model.Command)
235 def deps_in_use(impl
, arch
):
236 for dep
in impl
.requires
:
237 use
= dep
.metadata
.get("use", None)
238 if use
not in arch
.use
:
242 # Add a clause so that if requiring_impl_var is True then an implementation
243 # matching 'dependency' must also be selected.
244 # Must have already done add_iface on dependency.interface.
245 def find_dependency_candidates(requiring_impl_var
, dependency
):
246 dep_iface
= iface_cache
.get_interface(dependency
.interface
)
247 dep_union
= [sat
.neg(requiring_impl_var
)] # Either requiring_impl_var is False, or ...
248 for candidate
in impls_for_iface
[dep_iface
]:
249 for r
in dependency
.restrictions
:
250 if candidate
.__class
__ is not _DummyImpl
and not r
.meets_restriction(candidate
):
251 #warn("%s rejected due to %s", candidate.get_version(), r)
252 if candidate
.version
is not None:
255 c_var
= impl_to_var
.get(candidate
, None)
256 if c_var
is not None:
257 dep_union
.append(c_var
)
258 # else we filtered that version out, so ignore it
261 problem
.add_clause(dep_union
)
263 def is_unusable(impl
, restrictions
, arch
):
264 """@return: whether this implementation is unusable.
266 return get_unusable_reason(impl
, restrictions
, arch
) != None
268 def get_unusable_reason(impl
, restrictions
, arch
):
270 @param impl: Implementation to test.
271 @type restrictions: [L{model.Restriction}]
272 @return: The reason why this impl is unusable, or None if it's OK.
274 @note: The restrictions are for the interface being requested, not the feed
275 of the implementation; they may be different when feeds are being used."""
276 for r
in restrictions
:
277 if not r
.meets_restriction(impl
):
278 return _("Incompatible with another selected implementation")
279 stability
= impl
.get_stability()
280 if stability
<= model
.buggy
:
281 return stability
.name
282 if (self
.config
.network_use
== model
.network_offline
or not impl
.download_sources
) and not impl
.is_available(self
.config
.stores
):
283 if not impl
.download_sources
:
284 return _("No retrieval methods")
285 return _("Not cached and we are off-line")
286 if impl
.os
not in arch
.os_ranks
:
287 return _("Unsupported OS")
288 if impl
.machine
not in arch
.machine_ranks
:
289 if impl
.machine
== 'src':
290 return _("Source code")
291 return _("Unsupported machine type")
294 def usable_feeds(iface
, arch
):
295 """Return all feeds for iface that support arch.
296 @rtype: generator(ZeroInstallFeed)"""
299 for f
in iface_cache
.get_feed_imports(iface
):
300 # Note: when searching for src, None is not in machine_ranks
301 if f
.os
in arch
.os_ranks
and \
302 (f
.machine
is None or f
.machine
in arch
.machine_ranks
):
305 debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
306 {'feed': f
, 'os': f
.os
, 'machine': f
.machine
})
308 def add_iface(uri
, arch
):
309 """Name implementations from feed and assert that only one can be selected."""
310 if uri
in ifaces_processed
: return
311 ifaces_processed
.add(uri
)
313 iface
= 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
= 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())
329 distro_feed_url
= feed
.get_distro_feed()
331 self
.feeds_used
.add(distro_feed_url
)
332 distro_feed
= iface_cache
.get_feed(distro_feed_url
)
333 if distro_feed
.implementations
:
334 impls
.extend(distro_feed
.implementations
.values())
335 except Exception, ex
:
336 warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f
, 'interface': iface
, 'exception': ex
})
339 impls
.sort(lambda a
, b
: self
.compare(iface
, a
, b
, arch
))
341 impls_for_iface
[iface
] = filtered_impls
= []
343 my_extra_restrictions
= self
.extra_restrictions
.get(iface
, [])
345 if self
.record_details
:
346 self
.details
[iface
] = [(impl
, get_unusable_reason(impl
, my_extra_restrictions
, arch
)) for impl
in impls
]
351 if is_unusable(impl
, my_extra_restrictions
, arch
):
354 filtered_impls
.append(impl
)
356 assert impl
not in impl_to_var
357 v
= problem
.add_variable(ImplInfo(iface
, impl
, arch
))
358 impl_to_var
[impl
] = v
362 if impl
.machine
and impl
.machine
!= 'src':
363 impls_for_machine_group
[machine_groups
.get(impl
.machine
, 0)].append(v
)
365 for d
in deps_in_use(impl
, arch
):
366 debug(_("Considering dependency %s"), d
)
368 add_iface(d
.interface
, arch
.child_arch
)
370 # Must choose one version of d if impl is selected
371 find_dependency_candidates(v
, d
)
374 dummy_impl
= _DummyImpl()
375 dummy_var
= problem
.add_variable(ImplInfo(iface
, dummy_impl
, arch
, dummy
= True))
376 var_names
.append(dummy_var
)
377 impl_to_var
[dummy_impl
] = dummy_var
378 filtered_impls
.append(dummy_impl
)
380 # Only one implementation of this interface can be selected
381 if uri
== root_interface
:
383 clause
= problem
.at_most_one(var_names
)
384 problem
.add_clause(var_names
) # at least one
389 clause
= problem
.at_most_one(var_names
)
391 # Don't need to add to group_clause_for because we should
392 # never get a possible selection involving this.
395 assert clause
is not True
396 assert clause
is not None
397 if clause
is not False:
398 group_clause_for
[uri
] = clause
400 def add_command_iface(uri
, arch
, command_name
):
401 """Add every <command> in interface 'uri' with this name.
402 Each one depends on the corresponding implementation and only
403 one can be selected."""
404 # First ensure that the interface itself has been processed
405 # We'll reuse the ordering of the implementations to order
409 iface
= iface_cache
.get_interface(uri
)
410 filtered_impls
= impls_for_iface
[iface
]
413 for impl
in filtered_impls
:
414 command
= impl
.commands
.get(command_name
, None)
416 if not isinstance(impl
, _DummyImpl
):
417 # Mark implementation as unselectable
418 problem
.add_clause([sat
.neg(impl_to_var
[impl
])])
421 # We have a candidate <command>. Require that if it's selected
422 # then we select the corresponding <implementation> too.
423 command_var
= problem
.add_variable(CommandInfo(command_name
, command
, impl
, arch
))
424 problem
.add_clause([impl_to_var
[impl
], sat
.neg(command_var
)])
426 var_names
.append(command_var
)
428 runner
= command
.get_runner()
429 for d
in deps_in_use(command
, arch
):
431 # With a <runner>, we depend on a command rather than on an
432 # implementation. This allows us to support recursive <runner>s, etc.
433 debug(_("Considering command runner %s"), d
)
434 runner_command_name
= _get_command_name(d
)
435 runner_vars
= add_command_iface(d
.interface
, arch
.child_arch
, runner_command_name
)
438 dummy_command
= problem
.add_variable(None)
439 runner_vars
.append(dummy_command
)
440 # If the parent command is chosen, one of the candidate runner commands
441 # must be too. If there aren't any, then this command is unselectable.
442 problem
.add_clause([sat
.neg(command_var
)] + runner_vars
)
444 # Can't select more than one of them.
445 group_clause_for_command
[(d
.interface
, runner_command_name
)] = problem
.at_most_one(runner_vars
)
447 debug(_("Considering command dependency %s"), d
)
448 add_iface(d
.interface
, arch
.child_arch
)
450 # Must choose one version of d if impl is selected
451 find_dependency_candidates(command_var
, d
)
453 # Tell the user why we couldn't use this version
454 if self
.record_details
:
455 def new_reason(impl
, old_reason
):
456 if command_name
in impl
.commands
:
458 return old_reason
or (_('No %s command') % command_name
)
459 self
.details
[iface
] = [(impl
, new_reason(impl
, reason
)) for (impl
, reason
) in self
.details
[iface
]]
463 if command_name
is None:
464 add_iface(root_interface
, root_arch
)
466 commands
= add_command_iface(root_interface
, root_arch
, command_name
)
468 problem
.add_clause(commands
) # At least one
469 group_clause_for_command
[(root_interface
, command_name
)] = problem
.at_most_one(commands
)
471 # (note: might be because we haven't cached it yet)
472 info("No %s <command> in %s", command_name
, root_interface
)
474 impls
= impls_for_iface
[iface_cache
.get_interface(root_interface
)]
475 if impls
== [] or (len(impls
) == 1 and isinstance(impls
[0], _DummyImpl
)):
476 # There were no candidates at all.
477 self
._failure
_reason
= _("Interface '%s' has no usable implementations") % root_interface
479 # We had some candidates implementations, but none for the command we need
480 self
._failure
_reason
= _("Interface '%s' cannot be executed directly; it is just a library "
481 "to be used by other programs (or missing '%s' command)") % (root_interface
, command_name
)
485 # Require m<group> to be true if we select an implementation in that group
487 for machine_group
, impls
in impls_for_machine_group
.iteritems():
488 m_group
= 'm%d' % machine_group
489 group_var
= problem
.add_variable(m_group
)
492 problem
.add_clause([group_var
, sat
.neg(impl
)])
493 m_groups
.append(group_var
)
495 m_groups_clause
= problem
.at_most_one(m_groups
)
497 m_groups_clause
= None
500 """Recurse through the current selections until we get to an interface with
501 no chosen version, then tell the solver to try the best version from that."""
503 def find_undecided_dep(impl_or_command
, arch
):
504 # Check for undecided dependencies of impl_or_command
505 for dep
in deps_in_use(impl_or_command
, arch
):
506 if dep
.qdom
.name
== 'runner':
507 dep_lit
= find_undecided_command(dep
.interface
, _get_command_name(dep
))
509 dep_lit
= find_undecided(dep
.interface
)
510 if dep_lit
is not None:
515 def find_undecided(uri
):
517 return # Break cycles
520 group
= group_clause_for
[uri
]
521 #print "Group for %s = %s" % (uri, group)
524 return group
.best_undecided()
525 # else there was only one choice anyway
527 # Check for undecided dependencies
528 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
529 return find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
531 def find_undecided_command(uri
, name
):
532 if name
is None: return find_undecided(uri
)
534 group
= group_clause_for_command
[(uri
, name
)]
537 return group
.best_undecided()
538 # else we've already chosen which <command> to use
540 # Check for undecided command-specific dependencies, and then for
541 # implementation dependencies.
542 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
545 return None # (a dummy command added for better diagnostics; has no dependencies)
546 return find_undecided_dep(lit_info
.command
, lit_info
.arch
) or \
547 find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
549 best
= find_undecided_command(root_interface
, command_name
)
553 # If we're chosen everything we need, we can probably
554 # set everything else to False.
555 for group
in group_clause_for
.values() + group_clause_for_command
.values() + [m_groups_clause
]:
556 if group
.current
is None:
557 best
= group
.best_undecided()
561 return None # Failed to find any valid combination
563 ready
= problem
.run_solver(decide
) is True
565 if not ready
and not closest_match
:
566 # We failed while trying to do a real solve.
567 # Try a closest match solve to get a better
568 # error report for the user.
569 self
.solve(root_interface
, root_arch
, command_name
= command_name
, closest_match
= True)
571 self
.ready
= ready
and not closest_match
572 self
.selections
= selections
.Selections(None)
573 self
.selections
.interface
= root_interface
575 sels
= self
.selections
.selections
577 for uri
, group
in group_clause_for
.iteritems():
578 if group
.current
is not None:
579 lit_info
= problem
.get_varinfo_for_lit(group
.current
).obj
580 if lit_info
.is_dummy
:
581 sels
[lit_info
.iface
.uri
] = None
585 deps
= self
.requires
[lit_info
.iface
] = []
586 for dep
in deps_in_use(lit_info
.impl
, lit_info
.arch
):
589 sels
[lit_info
.iface
.uri
] = selections
.ImplSelection(lit_info
.iface
.uri
, impl
, deps
)
591 def add_command(iface
, name
):
592 sel
= sels
.get(iface
, None)
594 command
= sel
.impl
.commands
[name
]
595 self
.selections
.commands
.append(command
)
596 runner
= command
.get_runner()
598 add_command(runner
.metadata
['interface'], _get_command_name(runner
))
600 if command_name
is not None:
601 add_command(root_interface
, command_name
)
603 def get_failure_reason(self
):
604 """Return an exception explaining why the solve failed."""
605 assert not self
.ready
607 if self
._failure
_reason
:
608 return model
.SafeException(self
._failure
_reason
)
610 return model
.SafeException(_("Can't find all required implementations:") + '\n' +
611 '\n'.join(["- %s -> %s" % (iface
, self
.selections
[iface
])
612 for iface
in self
.selections
]))
614 DefaultSolver
= SATSolver