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
.reader
import MissingLocalFeed
13 from zeroinstall
.injector
.arch
import machine_groups
14 from zeroinstall
.injector
import model
, sat
, selections
17 def __init__(self
, name
, command
, impl
, arch
):
19 self
.command
= command
24 name
= "%s_%s_%s_%s" % (self
.impl
.feed
.get_name(), self
.impl
.get_version(), self
.impl
.arch
, self
.name
)
25 return name
.replace('-', '_').replace('.', '_')
30 def __init__(self
, iface
, impl
, arch
, dummy
= False):
38 name
= "%s_%s_%s" % (self
.impl
.feed
.get_name(), self
.impl
.get_version(), self
.impl
.arch
)
39 return name
.replace('-', '_').replace('.', '_')
41 class _DummyImpl(object):
50 feed
= property(lambda self
: self
)
52 def get_version(self
):
59 """Chooses a set of implementations to satisfy the requirements of a program and its user.
61 1. Create a Solver object and configure it
63 3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
64 4. If it is 'ready' then you can download and run the chosen versions.
65 @ivar selections: the chosen implementation of each interface
66 @type selections: L{selections.Selections}
67 @ivar requires: the selected dependencies for each chosen version
68 @type requires: {L{model.Interface}: [L{model.Dependency}]}
69 @ivar feeds_used: the feeds which contributed to the choice in L{selections}
70 @type feeds_used: set(str)
71 @ivar record_details: whether to record information about unselected implementations
72 @type record_details: {L{Interface}: [(L{Implementation}, str)]}
73 @ivar details: extra information, if record_details mode was used
74 @type details: {str: [(Implementation, comment)]}
76 __slots__
= ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
79 self
.selections
= self
.requires
= self
.feeds_used
= self
.details
= None
80 self
.record_details
= False
83 def solve(self
, root_interface
, root_arch
, command_name
= 'run'):
84 """Get the best implementation of root_interface and all of its dependencies.
85 @param root_interface: the URI of the program to be solved
86 @type root_interface: str
87 @param root_arch: the desired target architecture
88 @type root_arch: L{arch.Architecture}
89 @param command_name: which <command> element to select
90 @type command_name: str | None
91 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
92 raise NotImplementedError("Abstract")
94 class SATSolver(Solver
):
95 """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them.
96 @ivar langs: the preferred languages (e.g. ["es_ES", "en"]). Initialised to the current locale.
99 __slots__
= ['_failure_reason', 'config', 'extra_restrictions', '_lang_ranks', '_langs']
102 def iface_cache(self
):
103 return self
.config
.iface_cache
# (deprecated; used by 0compile)
105 def __init__(self
, config
, extra_restrictions
= None):
107 @param config: policy preferences (e.g. stability), the iface_cache and the stores to use
108 @type config: L{policy.Config}
109 @param extra_restrictions: extra restrictions on the chosen implementations
110 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
112 Solver
.__init
__(self
)
113 assert not isinstance(config
, str), "API change!"
115 self
.extra_restrictions
= extra_restrictions
or {}
117 # By default, prefer the current locale's language first and English second
118 self
.langs
= [locale
.getlocale()[0] or 'en', 'en']
120 def set_langs(self
, langs
):
121 """Set the preferred languages.
122 @param lang: languages (and regions), first choice first
125 # _lang_ranks is a map from locale string to score (higher is better)
129 # (is there are duplicates, the first occurance takes precedence)
132 lang
= langs
[i
].replace('_', '-')
133 _lang_ranks
[lang
.split('-')[0]] = score
134 _lang_ranks
[lang
] = score
+ 1
137 self
._lang
_ranks
= _lang_ranks
139 langs
= property(lambda self
: self
._langs
, set_langs
)
141 def compare(self
, interface
, b
, a
, arch
):
142 """Compare a and b to see which would be chosen first.
143 Does not consider whether the implementations are usable (check for that yourself first).
144 @param interface: The interface we are trying to resolve, which may
145 not be the interface of a or b if they are from feeds.
148 # Languages we understand come first
149 a_langs
= (a
.langs
or 'en').split()
150 b_langs
= (b
.langs
or 'en').split()
151 my_langs
= self
._lang
_ranks
153 r
= cmp(max(my_langs
.get(l
.split('-')[0], -1) for l
in a_langs
),
154 max(my_langs
.get(l
.split('-')[0], -1) for l
in b_langs
))
157 a_stab
= a
.get_stability()
158 b_stab
= b
.get_stability()
160 # Preferred versions come first
161 r
= cmp(a_stab
== model
.preferred
, b_stab
== model
.preferred
)
164 stores
= self
.config
.stores
165 if self
.config
.network_use
!= model
.network_full
:
166 r
= cmp(a
.is_available(stores
), b
.is_available(stores
))
169 # Packages that require admin access to install come last
170 r
= cmp(b
.requires_root_install
, a
.requires_root_install
)
174 stab_policy
= interface
.stability_policy
176 if self
.config
.help_with_testing
: stab_policy
= model
.testing
177 else: stab_policy
= model
.stable
179 if a_stab
>= stab_policy
: a_stab
= model
.preferred
180 if b_stab
>= stab_policy
: b_stab
= model
.preferred
182 r
= cmp(a_stab
, b_stab
)
185 # Newer versions come before older ones
186 if a
.id.startswith('package:') != b
.id.startswith('package:'):
187 # If one of packages is native, do not compare full versions since
188 # it is useless to compare native and 0install version revisions
189 r
= cmp(a
.version
[0], b
.version
[0])
191 # Othewise, prefer native package
192 return cmp(a
.id.startswith('package:'), b
.id.startswith('package:'))
194 r
= cmp(a
.version
, b
.version
)
198 r
= cmp(arch
.os_ranks
.get(b
.os
, None),
199 arch
.os_ranks
.get(a
.os
, None))
203 r
= cmp(arch
.machine_ranks
.get(b
.machine
, None),
204 arch
.machine_ranks
.get(a
.machine
, None))
207 # Slightly prefer languages specialised to our country
208 # (we know a and b have the same base language at this point)
209 r
= cmp(max(my_langs
.get(l
, -1) for l
in a_langs
),
210 max(my_langs
.get(l
, -1) for l
in b_langs
))
213 # Slightly prefer cached versions
214 if self
.config
.network_use
== model
.network_full
:
215 r
= cmp(a
.is_available(stores
), b
.is_available(stores
))
218 return cmp(a
.id, b
.id)
220 def solve(self
, root_interface
, root_arch
, command_name
= 'run', closest_match
= False):
221 # closest_match is used internally. It adds a lowest-ranked
222 # by valid implementation to every interface, so we can always
223 # select something. Useful for diagnostics.
225 # The basic plan is this:
226 # 1. Scan the root interface and all dependencies recursively, building up a SAT problem.
227 # 2. Solve the SAT problem. Whenever there are multiple options, try the most preferred one first.
228 # 3. Create a Selections object from the results.
230 # All three involve recursively walking the tree in a similar way:
231 # 1) we follow every dependency of every implementation (order not important)
232 # 2) we follow every dependency of every selected implementation (better versions first)
233 # 3) we follow every dependency of every selected implementation (order doesn't matter)
235 # In all cases, a dependency may be on an <implementation> or on a specific <command>.
237 # TODO: We need some way to figure out which feeds to include.
238 # Currently, we include any feed referenced from anywhere but
239 # this is probably too much. We could insert a dummy optimial
240 # implementation in stale/uncached feeds and see whether it
242 iface_cache
= self
.config
.iface_cache
244 problem
= sat
.SATProblem()
246 impl_to_var
= {} # Impl -> sat var
247 self
.feeds_used
= set()
250 self
.details
= self
.record_details
and {}
252 self
.selections
= None
253 self
._failure
_reason
= None
255 ifaces_processed
= set()
257 impls_for_machine_group
= {0 : []} # Machine group (e.g. "64") to [impl] in that group
258 for machine_group
in machine_groups
.values():
259 impls_for_machine_group
[machine_group
] = []
261 impls_for_iface
= {} # Iface -> [impl]
263 group_clause_for
= {} # Iface URI -> AtMostOneClause | bool
264 group_clause_for_command
= {} # (Iface URI, command name) -> AtMostOneClause | bool
266 # Return the dependencies of impl that we should consider.
267 # Skips dependencies if the use flag isn't what we need.
268 # (note: impl may also be a model.Command)
269 def deps_in_use(impl
, arch
):
270 for dep
in impl
.requires
:
271 use
= dep
.metadata
.get("use", None)
272 if use
not in arch
.use
:
276 # Must have already done add_iface on dependency.interface.
277 # If dependency is essential:
278 # Add a clause so that if requiring_impl_var is True then an implementation
279 # matching 'dependency' must also be selected.
280 # If dependency is optional:
281 # Require that no incompatible version is selected.
282 # This ignores any 'command' required. Handle that separately.
283 def find_dependency_candidates(requiring_impl_var
, dependency
):
284 def meets_restrictions(candidate
):
285 for r
in dependency
.restrictions
:
286 if not r
.meets_restriction(candidate
):
287 #warn("%s rejected due to %s", candidate.get_version(), r)
291 essential
= dependency
.importance
== model
.Dependency
.Essential
293 dep_iface
= iface_cache
.get_interface(dependency
.interface
)
294 dep_union
= [sat
.neg(requiring_impl_var
)] # Either requiring_impl_var is False, or ...
295 for candidate
in impls_for_iface
[dep_iface
]:
296 if (candidate
.__class
__ is _DummyImpl
) or meets_restrictions(candidate
):
298 c_var
= impl_to_var
.get(candidate
, None)
299 if c_var
is not None:
300 dep_union
.append(c_var
)
301 # else we filtered that version out, so ignore it
303 # Candidate doesn't meet our requirements
304 # If the dependency is optional add a rule to make sure we don't
305 # select this candidate.
306 # (for essential dependencies this isn't necessary because we must
307 # select a good version and we can't select two)
309 c_var
= impl_to_var
.get(candidate
, None)
310 if c_var
is not None:
311 problem
.add_clause(dep_union
+ [sat
.neg(c_var
)])
312 # else we filtered that version out, so ignore it
315 problem
.add_clause(dep_union
)
317 def is_unusable(impl
, restrictions
, arch
):
318 """@return: whether this implementation is unusable.
320 return get_unusable_reason(impl
, restrictions
, arch
) != None
322 def get_unusable_reason(impl
, restrictions
, arch
):
324 @param impl: Implementation to test.
325 @type restrictions: [L{model.Restriction}]
326 @return: The reason why this impl is unusable, or None if it's OK.
328 @note: The restrictions are for the interface being requested, not the feed
329 of the implementation; they may be different when feeds are being used."""
330 for r
in restrictions
:
331 if not r
.meets_restriction(impl
):
332 return _("Incompatible with another selected implementation")
333 stability
= impl
.get_stability()
334 if stability
<= model
.buggy
:
335 return stability
.name
336 if (self
.config
.network_use
== model
.network_offline
or not impl
.download_sources
) and not impl
.is_available(self
.config
.stores
):
337 if not impl
.download_sources
:
338 return _("No retrieval methods")
339 return _("Not cached and we are off-line")
340 if impl
.os
not in arch
.os_ranks
:
341 return _("Unsupported OS")
342 if impl
.machine
not in arch
.machine_ranks
:
343 if impl
.machine
== 'src':
344 return _("Source code")
345 return _("Unsupported machine type")
348 def usable_feeds(iface
, arch
):
349 """Return all feeds for iface that support arch.
350 @rtype: generator(ZeroInstallFeed)"""
353 for f
in iface_cache
.get_feed_imports(iface
):
354 # Note: when searching for src, None is not in machine_ranks
355 if f
.os
in arch
.os_ranks
and \
356 (f
.machine
is None or f
.machine
in arch
.machine_ranks
):
359 debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
360 {'feed': f
, 'os': f
.os
, 'machine': f
.machine
})
362 # If requiring_var is True then all of requirer's dependencies must be satisfied.
363 # requirer can be a <command> or an <implementation>
364 def process_dependencies(requiring_var
, requirer
, arch
):
365 for d
in deps_in_use(requirer
, arch
):
366 debug(_("Considering command dependency %s"), d
)
368 add_iface(d
.interface
, arch
.child_arch
)
370 for c
in d
.get_required_commands():
371 # We depend on a specific command within the implementation.
372 command_vars
= add_command_iface(d
.interface
, arch
.child_arch
, c
)
374 # If the parent command/impl is chosen, one of the candidate commands
375 # must be too. If there aren't any, then this command is unselectable.
376 problem
.add_clause([sat
.neg(requiring_var
)] + command_vars
)
378 # Must choose one version of d if impl is selected
379 find_dependency_candidates(requiring_var
, d
)
381 def add_iface(uri
, arch
):
382 """Name implementations from feed and assert that only one can be selected."""
383 if uri
in ifaces_processed
: return
384 ifaces_processed
.add(uri
)
386 iface
= iface_cache
.get_interface(uri
)
389 for f
in usable_feeds(iface
, arch
):
390 self
.feeds_used
.add(f
)
391 debug(_("Processing feed %s"), f
)
394 feed
= iface_cache
.get_feed(f
)
395 if feed
is None: continue
396 #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
397 # info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
399 if feed
.implementations
:
400 impls
.extend(feed
.implementations
.values())
402 distro_feed_url
= feed
.get_distro_feed()
404 self
.feeds_used
.add(distro_feed_url
)
405 distro_feed
= iface_cache
.get_feed(distro_feed_url
)
406 if distro_feed
.implementations
:
407 impls
.extend(distro_feed
.implementations
.values())
408 except MissingLocalFeed
as ex
:
409 warn(_("Missing local feed; if it's no longer required, remove it with:") +
410 '\n0install remove-feed ' + iface
.uri
+ ' ' + f
,
411 {'feed': f
, 'interface': iface
, 'exception': ex
})
412 except Exception as ex
:
413 warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f
, 'interface': iface
, 'exception': ex
})
416 impls
.sort(lambda a
, b
: self
.compare(iface
, a
, b
, arch
))
418 impls_for_iface
[iface
] = filtered_impls
= []
420 my_extra_restrictions
= self
.extra_restrictions
.get(iface
, [])
422 if self
.record_details
:
423 self
.details
[iface
] = [(impl
, get_unusable_reason(impl
, my_extra_restrictions
, arch
)) for impl
in impls
]
428 if is_unusable(impl
, my_extra_restrictions
, arch
):
431 filtered_impls
.append(impl
)
433 assert impl
not in impl_to_var
434 v
= problem
.add_variable(ImplInfo(iface
, impl
, arch
))
435 impl_to_var
[impl
] = v
439 if impl
.machine
and impl
.machine
!= 'src':
440 impls_for_machine_group
[machine_groups
.get(impl
.machine
, 0)].append(v
)
442 process_dependencies(v
, impl
, arch
)
445 dummy_impl
= _DummyImpl()
446 dummy_var
= problem
.add_variable(ImplInfo(iface
, dummy_impl
, arch
, dummy
= True))
447 var_names
.append(dummy_var
)
448 impl_to_var
[dummy_impl
] = dummy_var
449 filtered_impls
.append(dummy_impl
)
451 # Only one implementation of this interface can be selected
452 if uri
== root_interface
:
454 clause
= problem
.at_most_one(var_names
)
455 problem
.add_clause(var_names
) # at least one
460 clause
= problem
.at_most_one(var_names
)
462 # Don't need to add to group_clause_for because we should
463 # never get a possible selection involving this.
466 assert clause
is not True
467 assert clause
is not None
468 if clause
is not False:
469 group_clause_for
[uri
] = clause
471 def add_command_iface(uri
, arch
, command_name
):
472 """Add every <command> in interface 'uri' with this name.
473 Each one depends on the corresponding implementation and only
474 one can be selected. If closest_match is on, include a dummy
475 command that can always be selected."""
477 # Check whether we've already processed this (interface,command) pair
478 existing
= group_clause_for_command
.get((uri
, command_name
), None)
479 if existing
is not None:
482 # First ensure that the interface itself has been processed
483 # We'll reuse the ordering of the implementations to order
487 iface
= iface_cache
.get_interface(uri
)
488 filtered_impls
= impls_for_iface
[iface
]
491 for impl
in filtered_impls
:
492 command
= impl
.commands
.get(command_name
, None)
494 if not isinstance(impl
, _DummyImpl
):
495 # Mark implementation as unselectable
496 problem
.add_clause([sat
.neg(impl_to_var
[impl
])])
499 # We have a candidate <command>. Require that if it's selected
500 # then we select the corresponding <implementation> too.
501 command_var
= problem
.add_variable(CommandInfo(command_name
, command
, impl
, arch
))
502 problem
.add_clause([impl_to_var
[impl
], sat
.neg(command_var
)])
504 var_names
.append(command_var
)
506 process_dependencies(command_var
, command
, arch
)
508 # Tell the user why we couldn't use this version
509 if self
.record_details
:
510 def new_reason(impl
, old_reason
):
511 if command_name
in impl
.commands
:
513 return old_reason
or (_('No %s command') % command_name
)
514 self
.details
[iface
] = [(impl
, new_reason(impl
, reason
)) for (impl
, reason
) in self
.details
[iface
]]
517 dummy_command
= problem
.add_variable(None)
518 var_names
.append(dummy_command
)
521 # Can't select more than one of them.
522 assert (uri
, command_name
) not in group_clause_for_command
523 group_clause_for_command
[(uri
, command_name
)] = problem
.at_most_one(var_names
)
527 if command_name
is None:
528 add_iface(root_interface
, root_arch
)
530 commands
= add_command_iface(root_interface
, root_arch
, command_name
)
531 if len(commands
) > int(closest_match
):
532 # (we have at least one non-dummy command)
533 problem
.add_clause(commands
) # At least one
535 # (note: might be because we haven't cached it yet)
536 info("No %s <command> in %s", command_name
, root_interface
)
538 impls
= impls_for_iface
[iface_cache
.get_interface(root_interface
)]
539 if impls
== [] or (len(impls
) == 1 and isinstance(impls
[0], _DummyImpl
)):
540 # There were no candidates at all.
541 if self
.config
.network_use
== model
.network_offline
:
542 self
._failure
_reason
= _("Interface '%s' has no usable implementations in the cache (and 0install is in off-line mode)") % root_interface
544 self
._failure
_reason
= _("Interface '%s' has no usable implementations") % root_interface
546 # We had some candidates implementations, but none for the command we need
547 self
._failure
_reason
= _("Interface '%s' cannot be executed directly; it is just a library "
548 "to be used by other programs (or missing '%s' command)") % (root_interface
, command_name
)
552 # Require m<group> to be true if we select an implementation in that group
554 for machine_group
, impls
in impls_for_machine_group
.iteritems():
555 m_group
= 'm%d' % machine_group
556 group_var
= problem
.add_variable(m_group
)
559 problem
.add_clause([group_var
, sat
.neg(impl
)])
560 m_groups
.append(group_var
)
562 m_groups_clause
= problem
.at_most_one(m_groups
)
564 m_groups_clause
= None
567 """Recurse through the current selections until we get to an interface with
568 no chosen version, then tell the solver to try the best version from that."""
570 def find_undecided_dep(impl_or_command
, arch
):
571 # Check for undecided dependencies of impl_or_command
572 for dep
in deps_in_use(impl_or_command
, arch
):
573 for c
in dep
.get_required_commands():
574 dep_lit
= find_undecided_command(dep
.interface
, c
)
575 if dep_lit
is not None:
577 dep_lit
= find_undecided(dep
.interface
)
578 if dep_lit
is not None:
583 def find_undecided(uri
):
585 return # Break cycles
588 group
= group_clause_for
[uri
]
589 #print "Group for %s = %s" % (uri, group)
592 return group
.best_undecided()
593 # else there was only one choice anyway
595 # Check for undecided dependencies
596 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
597 return find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
599 def find_undecided_command(uri
, name
):
600 if name
is None: return find_undecided(uri
)
602 group
= group_clause_for_command
[(uri
, name
)]
605 return group
.best_undecided()
606 # else we've already chosen which <command> to use
608 # Check for undecided command-specific dependencies, and then for
609 # implementation dependencies.
610 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
613 return None # (a dummy command added for better diagnostics; has no dependencies)
614 return find_undecided_dep(lit_info
.command
, lit_info
.arch
) or \
615 find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
617 best
= find_undecided_command(root_interface
, command_name
)
621 # If we're chosen everything we need, we can probably
622 # set everything else to False.
623 for group
in group_clause_for
.values() + group_clause_for_command
.values() + [m_groups_clause
]:
624 if group
.current
is None:
625 best
= group
.best_undecided()
629 return None # Failed to find any valid combination
631 ready
= problem
.run_solver(decide
) is True
633 if not ready
and not closest_match
:
634 # We failed while trying to do a real solve.
635 # Try a closest match solve to get a better
636 # error report for the user.
637 self
.solve(root_interface
, root_arch
, command_name
= command_name
, closest_match
= True)
639 self
.ready
= ready
and not closest_match
640 self
.selections
= selections
.Selections(None)
641 self
.selections
.interface
= root_interface
643 sels
= self
.selections
.selections
647 for uri
, group
in group_clause_for
.iteritems():
648 if group
.current
is not None:
649 lit_info
= problem
.get_varinfo_for_lit(group
.current
).obj
650 if lit_info
.is_dummy
:
651 sels
[lit_info
.iface
.uri
] = None
655 deps
= self
.requires
[lit_info
.iface
] = []
656 for dep
in deps_in_use(lit_info
.impl
, lit_info
.arch
):
658 for c
in dep
.get_required_commands():
659 commands_needed
.append((dep
.interface
, c
))
661 sels
[lit_info
.iface
.uri
] = selections
.ImplSelection(lit_info
.iface
.uri
, impl
, deps
)
663 def add_command(iface
, name
):
664 sel
= sels
.get(iface
, None)
666 command
= sel
.impl
.commands
[name
]
667 sel
._used
_commands
.add(name
)
668 runner
= command
.get_runner()
670 add_command(runner
.metadata
['interface'], runner
.command
)
672 for iface
, command
in commands_needed
:
673 add_command(iface
, command
)
675 if command_name
is not None:
676 self
.selections
.command
= command_name
677 add_command(root_interface
, command_name
)
679 def get_failure_reason(self
):
680 """Return an exception explaining why the solve failed."""
681 assert not self
.ready
683 if self
._failure
_reason
:
684 return model
.SafeException(self
._failure
_reason
)
686 return model
.SafeException(_("Can't find all required implementations:") + '\n' +
687 '\n'.join(["- %s -> %s" % (iface
, self
.selections
[iface
])
688 for iface
in self
.selections
]))
690 DefaultSolver
= SATSolver