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 langs: 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 get_rating(self
, interface
, impl
, arch
):
142 impl_langs
= (impl
.langs
or 'en').split()
143 my_langs
= self
._lang
_ranks
145 stores
= self
.config
.stores
146 is_available
= impl
.is_available(stores
)
149 stab_policy
= interface
.stability_policy
151 if self
.config
.help_with_testing
: stab_policy
= model
.testing
152 else: stab_policy
= model
.stable
154 stability
= impl
.get_stability()
155 if stability
>= stab_policy
:
156 stability_limited
= model
.preferred
158 stability_limited
= stability
161 # Languages we understand come first
162 max(my_langs
.get(l
.split('-')[0], -1) for l
in impl_langs
),
164 # Preferred versions come first
165 stability
== model
.preferred
,
167 # Prefer available implementations next if we have limited network access
168 self
.config
.network_use
!= model
.network_full
and is_available
,
170 # Packages that require admin access to install come last
171 not impl
.requires_root_install
,
173 # Prefer more stable versions, but treat everything over stab_policy the same
174 # (so we prefer stable over testing if the policy is to prefer "stable", otherwise
178 # Newer versions come before older ones (ignoring modifiers)
181 # Prefer native packages if the main part of the versions are the same
182 impl
.id.startswith('package:'),
184 # Full version compare (after package check, since comparing modifiers between native and non-native
185 # packages doesn't make sense).
189 -arch
.os_ranks
.get(impl
.os
, 999),
192 -arch
.machine_ranks
.get(impl
.machine
, 999),
194 # Slightly prefer languages specialised to our country
195 # (we know a and b have the same base language at this point)
196 max(my_langs
.get(l
, -1) for l
in impl_langs
),
198 # Slightly prefer cached versions
201 # Order by ID so the order isn't random
205 def solve(self
, root_interface
, root_arch
, command_name
= 'run', closest_match
= False):
206 # closest_match is used internally. It adds a lowest-ranked
207 # by valid implementation to every interface, so we can always
208 # select something. Useful for diagnostics.
210 # The basic plan is this:
211 # 1. Scan the root interface and all dependencies recursively, building up a SAT problem.
212 # 2. Solve the SAT problem. Whenever there are multiple options, try the most preferred one first.
213 # 3. Create a Selections object from the results.
215 # All three involve recursively walking the tree in a similar way:
216 # 1) we follow every dependency of every implementation (order not important)
217 # 2) we follow every dependency of every selected implementation (better versions first)
218 # 3) we follow every dependency of every selected implementation (order doesn't matter)
220 # In all cases, a dependency may be on an <implementation> or on a specific <command>.
222 # TODO: We need some way to figure out which feeds to include.
223 # Currently, we include any feed referenced from anywhere but
224 # this is probably too much. We could insert a dummy optimial
225 # implementation in stale/uncached feeds and see whether it
227 iface_cache
= self
.config
.iface_cache
229 problem
= sat
.SATProblem()
231 impl_to_var
= {} # Impl -> sat var
232 self
.feeds_used
= set()
235 self
.details
= self
.record_details
and {}
237 self
.selections
= None
238 self
._failure
_reason
= None
240 ifaces_processed
= set()
242 impls_for_machine_group
= {0 : []} # Machine group (e.g. "64") to [impl] in that group
243 for machine_group
in machine_groups
.values():
244 impls_for_machine_group
[machine_group
] = []
246 impls_for_iface
= {} # Iface -> [impl]
248 group_clause_for
= {} # Iface URI -> AtMostOneClause | bool
249 group_clause_for_command
= {} # (Iface URI, command name) -> AtMostOneClause | bool
251 # Return the dependencies of impl that we should consider.
252 # Skips dependencies if the use flag isn't what we need.
253 # (note: impl may also be a model.Command)
254 def deps_in_use(impl
, arch
):
255 for dep
in impl
.requires
:
256 use
= dep
.metadata
.get("use", None)
257 if use
not in arch
.use
:
261 # Must have already done add_iface on dependency.interface.
262 # If dependency is essential:
263 # Add a clause so that if requiring_impl_var is True then an implementation
264 # matching 'dependency' must also be selected.
265 # If dependency is optional:
266 # Require that no incompatible version is selected.
267 # This ignores any 'command' required. Handle that separately.
268 def find_dependency_candidates(requiring_impl_var
, dependency
):
269 def meets_restrictions(candidate
):
270 for r
in dependency
.restrictions
:
271 if not r
.meets_restriction(candidate
):
272 #warn("%s rejected due to %s", candidate.get_version(), r)
276 essential
= dependency
.importance
== model
.Dependency
.Essential
278 dep_iface
= iface_cache
.get_interface(dependency
.interface
)
279 dep_union
= [sat
.neg(requiring_impl_var
)] # Either requiring_impl_var is False, or ...
280 for candidate
in impls_for_iface
[dep_iface
]:
281 if (candidate
.__class
__ is _DummyImpl
) or meets_restrictions(candidate
):
283 c_var
= impl_to_var
.get(candidate
, None)
284 if c_var
is not None:
285 dep_union
.append(c_var
)
286 # else we filtered that version out, so ignore it
288 # Candidate doesn't meet our requirements
289 # If the dependency is optional add a rule to make sure we don't
290 # select this candidate.
291 # (for essential dependencies this isn't necessary because we must
292 # select a good version and we can't select two)
294 c_var
= impl_to_var
.get(candidate
, None)
295 if c_var
is not None:
296 problem
.add_clause(dep_union
+ [sat
.neg(c_var
)])
297 # else we filtered that version out, so ignore it
300 problem
.add_clause(dep_union
)
302 def is_unusable(impl
, restrictions
, arch
):
303 """@return: whether this implementation is unusable.
305 return get_unusable_reason(impl
, restrictions
, arch
) != None
307 def get_unusable_reason(impl
, restrictions
, arch
):
309 @param impl: Implementation to test.
310 @type restrictions: [L{model.Restriction}]
311 @return: The reason why this impl is unusable, or None if it's OK.
313 @note: The restrictions are for the interface being requested, not the feed
314 of the implementation; they may be different when feeds are being used."""
315 for r
in restrictions
:
316 if not r
.meets_restriction(impl
):
317 return _("Incompatible with another selected implementation")
318 stability
= impl
.get_stability()
319 if stability
<= model
.buggy
:
320 return stability
.name
321 if (self
.config
.network_use
== model
.network_offline
or not impl
.download_sources
) and not impl
.is_available(self
.config
.stores
):
322 if not impl
.download_sources
:
323 return _("No retrieval methods")
324 return _("Not cached and we are off-line")
325 if impl
.os
not in arch
.os_ranks
:
326 return _("Unsupported OS")
327 if impl
.machine
not in arch
.machine_ranks
:
328 if impl
.machine
== 'src':
329 return _("Source code")
330 return _("Unsupported machine type")
333 def usable_feeds(iface
, arch
):
334 """Return all feeds for iface that support arch.
335 @rtype: generator(ZeroInstallFeed)"""
338 for f
in iface_cache
.get_feed_imports(iface
):
339 # Note: when searching for src, None is not in machine_ranks
340 if f
.os
in arch
.os_ranks
and \
341 (f
.machine
is None or f
.machine
in arch
.machine_ranks
):
344 debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
345 {'feed': f
, 'os': f
.os
, 'machine': f
.machine
})
347 # If requiring_var is True then all of requirer's dependencies must be satisfied.
348 # requirer can be a <command> or an <implementation>
349 def process_dependencies(requiring_var
, requirer
, arch
):
350 for d
in deps_in_use(requirer
, arch
):
351 debug(_("Considering command dependency %s"), d
)
353 add_iface(d
.interface
, arch
.child_arch
)
355 for c
in d
.get_required_commands():
356 # We depend on a specific command within the implementation.
357 command_vars
= add_command_iface(d
.interface
, arch
.child_arch
, c
)
359 # If the parent command/impl is chosen, one of the candidate commands
360 # must be too. If there aren't any, then this command is unselectable.
361 problem
.add_clause([sat
.neg(requiring_var
)] + command_vars
)
363 # Must choose one version of d if impl is selected
364 find_dependency_candidates(requiring_var
, d
)
366 def add_iface(uri
, arch
):
367 """Name implementations from feed and assert that only one can be selected."""
368 if uri
in ifaces_processed
: return
369 ifaces_processed
.add(uri
)
371 iface
= iface_cache
.get_interface(uri
)
374 for f
in usable_feeds(iface
, arch
):
375 self
.feeds_used
.add(f
)
376 debug(_("Processing feed %s"), f
)
379 feed
= iface_cache
.get_feed(f
)
380 if feed
is None: continue
381 #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
382 # info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
384 if feed
.implementations
:
385 impls
.extend(feed
.implementations
.values())
387 distro_feed_url
= feed
.get_distro_feed()
389 self
.feeds_used
.add(distro_feed_url
)
390 distro_feed
= iface_cache
.get_feed(distro_feed_url
)
391 if distro_feed
.implementations
:
392 impls
.extend(distro_feed
.implementations
.values())
393 except MissingLocalFeed
as ex
:
394 warn(_("Missing local feed; if it's no longer required, remove it with:") +
395 '\n0install remove-feed ' + iface
.uri
+ ' ' + f
,
396 {'feed': f
, 'interface': iface
, 'exception': ex
})
397 except Exception as ex
:
398 warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f
, 'interface': iface
, 'exception': ex
})
401 impls
.sort(key
= lambda impl
: self
.get_rating(iface
, impl
, arch
), reverse
= True)
403 impls_for_iface
[iface
] = filtered_impls
= []
405 my_extra_restrictions
= self
.extra_restrictions
.get(iface
, [])
407 if self
.record_details
:
408 self
.details
[iface
] = [(impl
, get_unusable_reason(impl
, my_extra_restrictions
, arch
)) for impl
in impls
]
413 if is_unusable(impl
, my_extra_restrictions
, arch
):
416 filtered_impls
.append(impl
)
418 assert impl
not in impl_to_var
419 v
= problem
.add_variable(ImplInfo(iface
, impl
, arch
))
420 impl_to_var
[impl
] = v
424 if impl
.machine
and impl
.machine
!= 'src':
425 impls_for_machine_group
[machine_groups
.get(impl
.machine
, 0)].append(v
)
427 process_dependencies(v
, impl
, arch
)
430 dummy_impl
= _DummyImpl()
431 dummy_var
= problem
.add_variable(ImplInfo(iface
, dummy_impl
, arch
, dummy
= True))
432 var_names
.append(dummy_var
)
433 impl_to_var
[dummy_impl
] = dummy_var
434 filtered_impls
.append(dummy_impl
)
436 # Only one implementation of this interface can be selected
437 if uri
== root_interface
:
439 clause
= problem
.at_most_one(var_names
)
440 problem
.add_clause(var_names
) # at least one
445 clause
= problem
.at_most_one(var_names
)
447 # Don't need to add to group_clause_for because we should
448 # never get a possible selection involving this.
451 assert clause
is not True
452 assert clause
is not None
453 if clause
is not False:
454 group_clause_for
[uri
] = clause
456 def add_command_iface(uri
, arch
, command_name
):
457 """Add every <command> in interface 'uri' with this name.
458 Each one depends on the corresponding implementation and only
459 one can be selected. If closest_match is on, include a dummy
460 command that can always be selected."""
462 # Check whether we've already processed this (interface,command) pair
463 existing
= group_clause_for_command
.get((uri
, command_name
), None)
464 if existing
is not None:
467 # First ensure that the interface itself has been processed
468 # We'll reuse the ordering of the implementations to order
472 iface
= iface_cache
.get_interface(uri
)
473 filtered_impls
= impls_for_iface
[iface
]
476 for impl
in filtered_impls
:
477 command
= impl
.commands
.get(command_name
, None)
479 if not isinstance(impl
, _DummyImpl
):
480 # Mark implementation as unselectable
481 problem
.add_clause([sat
.neg(impl_to_var
[impl
])])
484 # We have a candidate <command>. Require that if it's selected
485 # then we select the corresponding <implementation> too.
486 command_var
= problem
.add_variable(CommandInfo(command_name
, command
, impl
, arch
))
487 problem
.add_clause([impl_to_var
[impl
], sat
.neg(command_var
)])
489 var_names
.append(command_var
)
491 process_dependencies(command_var
, command
, arch
)
493 # Tell the user why we couldn't use this version
494 if self
.record_details
:
495 def new_reason(impl
, old_reason
):
496 if command_name
in impl
.commands
:
498 return old_reason
or (_('No %s command') % command_name
)
499 self
.details
[iface
] = [(impl
, new_reason(impl
, reason
)) for (impl
, reason
) in self
.details
[iface
]]
502 dummy_command
= problem
.add_variable(None)
503 var_names
.append(dummy_command
)
506 # Can't select more than one of them.
507 assert (uri
, command_name
) not in group_clause_for_command
508 group_clause_for_command
[(uri
, command_name
)] = problem
.at_most_one(var_names
)
512 if command_name
is None:
513 add_iface(root_interface
, root_arch
)
515 commands
= add_command_iface(root_interface
, root_arch
, command_name
)
516 if len(commands
) > int(closest_match
):
517 # (we have at least one non-dummy command)
518 problem
.add_clause(commands
) # At least one
520 # (note: might be because we haven't cached it yet)
521 info("No %s <command> in %s", command_name
, root_interface
)
523 impls
= impls_for_iface
[iface_cache
.get_interface(root_interface
)]
524 if impls
== [] or (len(impls
) == 1 and isinstance(impls
[0], _DummyImpl
)):
525 # There were no candidates at all.
526 if self
.config
.network_use
== model
.network_offline
:
527 self
._failure
_reason
= _("Interface '%s' has no usable implementations in the cache (and 0install is in off-line mode)") % root_interface
529 self
._failure
_reason
= _("Interface '%s' has no usable implementations") % root_interface
531 # We had some candidates implementations, but none for the command we need
532 self
._failure
_reason
= _("Interface '%s' cannot be executed directly; it is just a library "
533 "to be used by other programs (or missing '%s' command)") % (root_interface
, command_name
)
537 # Require m<group> to be true if we select an implementation in that group
539 for machine_group
, impls
in impls_for_machine_group
.iteritems():
540 m_group
= 'm%d' % machine_group
541 group_var
= problem
.add_variable(m_group
)
544 problem
.add_clause([group_var
, sat
.neg(impl
)])
545 m_groups
.append(group_var
)
547 m_groups_clause
= problem
.at_most_one(m_groups
)
549 m_groups_clause
= None
552 """Recurse through the current selections until we get to an interface with
553 no chosen version, then tell the solver to try the best version from that."""
555 def find_undecided_dep(impl_or_command
, arch
):
556 # Check for undecided dependencies of impl_or_command
557 for dep
in deps_in_use(impl_or_command
, arch
):
558 for c
in dep
.get_required_commands():
559 dep_lit
= find_undecided_command(dep
.interface
, c
)
560 if dep_lit
is not None:
562 dep_lit
= find_undecided(dep
.interface
)
563 if dep_lit
is not None:
568 def find_undecided(uri
):
570 return # Break cycles
573 group
= group_clause_for
[uri
]
574 #print "Group for %s = %s" % (uri, group)
577 return group
.best_undecided()
578 # else there was only one choice anyway
580 # Check for undecided dependencies
581 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
582 return find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
584 def find_undecided_command(uri
, name
):
585 if name
is None: return find_undecided(uri
)
587 group
= group_clause_for_command
[(uri
, name
)]
590 return group
.best_undecided()
591 # else we've already chosen which <command> to use
593 # Check for undecided command-specific dependencies, and then for
594 # implementation dependencies.
595 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
598 return None # (a dummy command added for better diagnostics; has no dependencies)
599 return find_undecided_dep(lit_info
.command
, lit_info
.arch
) or \
600 find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
602 best
= find_undecided_command(root_interface
, command_name
)
606 # If we're chosen everything we need, we can probably
607 # set everything else to False.
608 for group
in group_clause_for
.values() + group_clause_for_command
.values() + [m_groups_clause
]:
609 if group
.current
is None:
610 best
= group
.best_undecided()
614 return None # Failed to find any valid combination
616 ready
= problem
.run_solver(decide
) is True
618 if not ready
and not closest_match
:
619 # We failed while trying to do a real solve.
620 # Try a closest match solve to get a better
621 # error report for the user.
622 self
.solve(root_interface
, root_arch
, command_name
= command_name
, closest_match
= True)
624 self
.ready
= ready
and not closest_match
625 self
.selections
= selections
.Selections(None)
626 self
.selections
.interface
= root_interface
628 sels
= self
.selections
.selections
632 # Popular sels with the selected implementations.
633 # Also, note down all the commands we need.
634 for uri
, group
in group_clause_for
.iteritems():
635 if group
.current
is not None:
636 lit_info
= problem
.get_varinfo_for_lit(group
.current
).obj
637 if lit_info
.is_dummy
:
638 sels
[lit_info
.iface
.uri
] = None
640 # We selected an implementation for interface 'uri'
643 for b
in impl
.bindings
:
646 commands
.append((uri
, c
))
648 deps
= self
.requires
[lit_info
.iface
] = []
649 for dep
in deps_in_use(lit_info
.impl
, lit_info
.arch
):
651 for c
in dep
.get_required_commands():
652 commands_needed
.append((dep
.interface
, c
))
654 sels
[lit_info
.iface
.uri
] = selections
.ImplSelection(lit_info
.iface
.uri
, impl
, deps
)
656 # Now all all the commands in too.
657 def add_command(iface
, name
):
658 sel
= sels
.get(iface
, None)
660 command
= sel
.impl
.commands
[name
]
661 if name
in sel
._used
_commands
:
662 return # Already added
663 sel
._used
_commands
.add(name
)
665 for dep
in command
.requires
:
666 for dep_command_name
in dep
.get_required_commands():
667 add_command(dep
.interface
, dep_command_name
)
669 # A <command> can depend on another <command> in the same interface
670 # (e.g. the tests depending on the main program)
671 for b
in command
.bindings
:
674 add_command(iface
, c
)
676 for iface
, command
in commands_needed
:
677 add_command(iface
, command
)
679 if command_name
is not None:
680 self
.selections
.command
= command_name
681 add_command(root_interface
, command_name
)
683 def get_failure_reason(self
):
684 """Return an exception explaining why the solve failed."""
685 assert not self
.ready
687 if self
._failure
_reason
:
688 return model
.SafeException(self
._failure
_reason
)
690 return model
.SafeException(_("Can't find all required implementations:") + '\n' +
691 '\n'.join(["- %s -> %s" % (iface
, self
.selections
[iface
])
692 for iface
in self
.selections
]))
694 DefaultSolver
= SATSolver