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
, 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 class _DummyImpl(object):
73 feed
= property(lambda self
: self
)
75 def get_version(self
):
82 """Chooses a set of implementations to satisfy the requirements of a program and its user.
84 1. Create a Solver object and configure it
86 3. If any of the returned feeds_used are stale or missing, you may like to start downloading them
87 4. If it is 'ready' then you can download and run the chosen versions.
88 @ivar selections: the chosen implementation of each interface
89 @type selections: L{selections.Selections}
90 @ivar requires: the selected dependencies for each chosen version
91 @type requires: {L{model.Interface}: [L{model.Dependency}]}
92 @ivar feeds_used: the feeds which contributed to the choice in L{selections}
93 @type feeds_used: set(str)
94 @ivar record_details: whether to record information about unselected implementations
95 @type record_details: {L{Interface}: [(L{Implementation}, str)]}
96 @ivar details: extra information, if record_details mode was used
97 @type details: {str: [(Implementation, comment)]}
99 __slots__
= ['selections', 'requires', 'feeds_used', 'details', 'record_details', 'ready']
102 self
.selections
= self
.requires
= self
.feeds_used
= self
.details
= None
103 self
.record_details
= False
106 def solve(self
, root_interface
, root_arch
, command_name
= 'run'):
107 """Get the best implementation of root_interface and all of its dependencies.
108 @param root_interface: the URI of the program to be solved
109 @type root_interface: str
110 @param root_arch: the desired target architecture
111 @type root_arch: L{arch.Architecture}
112 @param command_name: which <command> element to select
113 @type command_name: str | None
114 @postcondition: self.ready, self.selections and self.feeds_used are updated"""
115 raise NotImplementedError("Abstract")
117 class SATSolver(Solver
):
118 __slots__
= ['_failure_reason', 'network_use', 'iface_cache', 'stores', 'help_with_testing', 'extra_restrictions',
121 """Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them.
122 @ivar langs: the preferred languages (e.g. ["es_ES", "en"]). Initialised to the current locale.
124 def __init__(self
, network_use
, iface_cache
, stores
, extra_restrictions
= None):
126 @param network_use: how much use to make of the network
127 @type network_use: L{model.network_levels}
128 @param iface_cache: a cache of feeds containing information about available versions
129 @type iface_cache: L{iface_cache.IfaceCache}
130 @param stores: a cached of implementations (affects choice when offline or when minimising network use)
131 @type stores: L{zerostore.Stores}
132 @param extra_restrictions: extra restrictions on the chosen implementations
133 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}
135 Solver
.__init
__(self
)
136 self
.network_use
= network_use
137 self
.iface_cache
= iface_cache
139 self
.help_with_testing
= False
140 self
.extra_restrictions
= extra_restrictions
or {}
142 self
.langs
= [locale
.getlocale()[0] or 'en']
144 def compare(self
, interface
, b
, a
, arch
):
145 """Compare a and b to see which would be chosen first.
146 Does not consider whether the implementations are usable (check for that yourself first).
147 @param interface: The interface we are trying to resolve, which may
148 not be the interface of a or b if they are from feeds.
151 # Languages we understand come first
152 a_langs
= (a
.langs
or 'en').split()
153 b_langs
= (b
.langs
or 'en').split()
154 main_langs
= set(l
.split('_')[0] for l
in self
.langs
)
155 r
= cmp(any(l
.split('_')[0] in main_langs
for l
in a_langs
),
156 any(l
.split('_')[0] in main_langs
for l
in b_langs
))
159 a_stab
= a
.get_stability()
160 b_stab
= b
.get_stability()
162 # Preferred versions come first
163 r
= cmp(a_stab
== model
.preferred
, b_stab
== model
.preferred
)
167 if self
.network_use
!= model
.network_full
:
168 r
= cmp(_get_cached(stores
, a
), _get_cached(stores
, b
))
171 # Packages that require admin access to install come last
172 r
= cmp(b
.requires_root_install
, a
.requires_root_install
)
176 stab_policy
= interface
.stability_policy
178 if self
.help_with_testing
: stab_policy
= model
.testing
179 else: stab_policy
= model
.stable
181 if a_stab
>= stab_policy
: a_stab
= model
.preferred
182 if b_stab
>= stab_policy
: b_stab
= model
.preferred
184 r
= cmp(a_stab
, b_stab
)
187 # Newer versions come before older ones
188 if a
.id.startswith('package:') != b
.id.startswith('package:'):
189 # If one of packages is native, do not compare full versions since
190 # it is useless to compare native and 0install version revisions
191 r
= cmp(a
.version
[0], b
.version
[0])
193 # Othewise, prefer native package
194 return cmp(a
.id.startswith('package:'), b
.id.startswith('package:'))
196 r
= cmp(a
.version
, b
.version
)
200 r
= cmp(arch
.os_ranks
.get(b
.os
, None),
201 arch
.os_ranks
.get(a
.os
, None))
205 r
= cmp(arch
.machine_ranks
.get(b
.machine
, None),
206 arch
.machine_ranks
.get(a
.machine
, None))
209 # Slightly prefer languages specialised to our country
210 r
= cmp(any(l
in self
.langs
for l
in a_langs
),
211 any(l
in self
.langs
for l
in b_langs
))
214 # Slightly prefer cached versions
215 if self
.network_use
== model
.network_full
:
216 r
= cmp(_get_cached(stores
, a
), _get_cached(stores
, b
))
219 return cmp(a
.id, b
.id)
221 def solve(self
, root_interface
, root_arch
, command_name
= 'run', closest_match
= False):
222 # closest_match is used internally. It adds a lowest-ranked
223 # by valid implementation to every interface, so we can always
224 # select something. Useful for diagnostics.
226 # TODO: We need some way to figure out which feeds to include.
227 # Currently, we include any feed referenced from anywhere but
228 # this is probably too much. We could insert a dummy optimial
229 # implementation in stale/uncached feeds and see whether it
233 problem
= sat
.SATProblem()
235 impl_to_var
= {} # Impl -> sat var
236 self
.feeds_used
= set()
239 self
.details
= self
.record_details
and {}
241 self
.selections
= None
242 self
._failure
_reason
= None
244 ifaces_processed
= set()
246 impls_for_machine_group
= {0 : []} # Machine group (e.g. "64") to [impl] in that group
247 for machine_group
in machine_groups
.values():
248 impls_for_machine_group
[machine_group
] = []
250 impls_for_iface
= {} # Iface -> [impl]
252 group_clause_for
= {} # Iface URI -> AtMostOneClause | bool
253 group_clause_for_command
= {} # (Iface URI, command name) -> AtMostOneClause | bool
255 # Return the dependencies of impl that we should consider.
256 # Skips dependencies if the use flag isn't what we need.
257 # (note: impl may also be a model.Command)
258 def deps_in_use(impl
, arch
):
259 for dep
in impl
.requires
:
260 use
= dep
.metadata
.get("use", None)
261 if use
not in arch
.use
:
265 # Add a clause so that if requiring_impl_var is True then an implementation
266 # matching 'dependency' must also be selected.
267 # Must have already done add_iface on dependency.interface.
268 def find_dependency_candidates(requiring_impl_var
, dependency
):
269 dep_iface
= self
.iface_cache
.get_interface(dependency
.interface
)
270 dep_union
= [sat
.neg(requiring_impl_var
)] # Either requiring_impl_var is False, or ...
271 for candidate
in impls_for_iface
[dep_iface
]:
272 for r
in dependency
.restrictions
:
273 if candidate
.__class
__ is not _DummyImpl
and not r
.meets_restriction(candidate
):
274 #warn("%s rejected due to %s", candidate.get_version(), r)
275 if candidate
.version
is not None:
278 c_var
= impl_to_var
.get(candidate
, None)
279 if c_var
is not None:
280 dep_union
.append(c_var
)
281 # else we filtered that version out, so ignore it
284 problem
.add_clause(dep_union
)
286 def is_unusable(impl
, restrictions
, arch
):
287 """@return: whether this implementation is unusable.
289 return get_unusable_reason(impl
, restrictions
, arch
) != None
291 def get_unusable_reason(impl
, restrictions
, arch
):
293 @param impl: Implementation to test.
294 @type restrictions: [L{model.Restriction}]
295 @return: The reason why this impl is unusable, or None if it's OK.
297 @note: The restrictions are for the interface being requested, not the feed
298 of the implementation; they may be different when feeds are being used."""
299 for r
in restrictions
:
300 if not r
.meets_restriction(impl
):
301 return _("Incompatible with another selected implementation")
302 stability
= impl
.get_stability()
303 if stability
<= model
.buggy
:
304 return stability
.name
305 if (self
.network_use
== model
.network_offline
or not impl
.download_sources
) and not _get_cached(self
.stores
, impl
):
306 if not impl
.download_sources
:
307 return _("No retrieval methods")
308 return _("Not cached and we are off-line")
309 if impl
.os
not in arch
.os_ranks
:
310 return _("Unsupported OS")
311 if impl
.machine
not in arch
.machine_ranks
:
312 if impl
.machine
== 'src':
313 return _("Source code")
314 return _("Unsupported machine type")
317 def usable_feeds(iface
, arch
):
318 """Return all feeds for iface that support arch.
319 @rtype: generator(ZeroInstallFeed)"""
322 for f
in self
.iface_cache
.get_feed_imports(iface
):
323 # Note: when searching for src, None is not in machine_ranks
324 if f
.os
in arch
.os_ranks
and \
325 (f
.machine
is None or f
.machine
in arch
.machine_ranks
):
328 debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"),
329 {'feed': f
, 'os': f
.os
, 'machine': f
.machine
})
331 def add_iface(uri
, arch
):
332 """Name implementations from feed and assert that only one can be selected."""
333 if uri
in ifaces_processed
: return
334 ifaces_processed
.add(uri
)
335 iface_name
= 'i%d' % len(ifaces_processed
)
337 iface
= self
.iface_cache
.get_interface(uri
)
340 for f
in usable_feeds(iface
, arch
):
341 self
.feeds_used
.add(f
)
342 debug(_("Processing feed %s"), f
)
345 feed
= self
.iface_cache
.get_feed(f
)
346 if feed
is None: continue
347 #if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for:
348 # info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f})
350 if feed
.implementations
:
351 impls
.extend(feed
.implementations
.values())
353 distro_feed_url
= feed
.get_distro_feed()
355 self
.feeds_used
.add(distro_feed_url
)
356 distro_feed
= self
.iface_cache
.get_feed(distro_feed_url
)
357 if distro_feed
.implementations
:
358 impls
.extend(distro_feed
.implementations
.values())
359 except Exception, ex
:
360 warn(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"), {'feed': f
, 'interface': iface
, 'exception': ex
})
362 impls
.sort(lambda a
, b
: self
.compare(iface
, a
, b
, arch
))
364 impls_for_iface
[iface
] = filtered_impls
= []
366 my_extra_restrictions
= self
.extra_restrictions
.get(iface
, [])
368 if self
.record_details
:
369 self
.details
[iface
] = [(impl
, get_unusable_reason(impl
, my_extra_restrictions
, arch
)) for impl
in impls
]
374 if is_unusable(impl
, my_extra_restrictions
, arch
):
377 filtered_impls
.append(impl
)
379 assert impl
not in impl_to_var
380 v
= problem
.add_variable(ImplInfo(iface
, impl
, arch
))
381 impl_to_var
[impl
] = v
385 if impl
.machine
and impl
.machine
!= 'src':
386 impls_for_machine_group
[machine_groups
.get(impl
.machine
, 0)].append(v
)
388 for d
in deps_in_use(impl
, arch
):
389 debug(_("Considering dependency %s"), d
)
391 add_iface(d
.interface
, arch
.child_arch
)
393 # Must choose one version of d if impl is selected
394 find_dependency_candidates(v
, d
)
397 dummy_impl
= _DummyImpl()
398 dummy_var
= problem
.add_variable(ImplInfo(iface
, dummy_impl
, arch
, dummy
= True))
399 var_names
.append(dummy_var
)
400 impl_to_var
[dummy_impl
] = dummy_var
401 filtered_impls
.append(dummy_impl
)
403 # Only one implementation of this interface can be selected
404 if uri
== root_interface
:
406 clause
= problem
.at_most_one(var_names
)
407 problem
.add_clause(var_names
) # at least one
412 clause
= problem
.at_most_one(var_names
)
414 # Don't need to add to group_clause_for because we should
415 # never get a possible selection involving this.
418 assert clause
is not True
419 assert clause
is not None
420 if clause
is not False:
421 group_clause_for
[uri
] = clause
423 def add_command_iface(uri
, arch
, command_name
):
424 """Add every <command> in interface 'uri' with this name.
425 Each one depends on the corresponding implementation and only
426 one can be selected."""
428 # First ensure that the interface itself has been processed
429 # We'll reuse the ordering of the implementations to order
433 iface
= self
.iface_cache
.get_interface(uri
)
434 filtered_impls
= impls_for_iface
[iface
]
437 for impl
in filtered_impls
:
438 command
= impl
.commands
.get(command_name
, None)
440 # Mark implementation as unselectable
441 problem
.add_clause([sat
.neg(impl_to_var
[impl
])])
444 # We have a candidate <command>. Require that if it's selected
445 # then we select the corresponding <implementation> too.
446 command_var
= problem
.add_variable(CommandInfo(command_name
, command
, impl
, arch
))
447 problem
.add_clause([impl_to_var
[impl
], sat
.neg(command_var
)])
449 var_names
.append(command_var
)
451 for d
in deps_in_use(command
, arch
):
452 debug(_("Considering command dependency %s"), d
)
454 add_iface(d
.interface
, arch
.child_arch
)
456 # Must choose one version of d if impl is selected
457 find_dependency_candidates(command_var
, d
)
459 # Tell the user why we couldn't use this version
460 if self
.record_details
:
461 def new_reason(impl
, old_reason
):
462 if command_name
in impl
.commands
:
464 return old_reason
or (_('No %s command') % command_name
)
465 self
.details
[iface
] = [(impl
, new_reason(impl
, reason
)) for (impl
, reason
) in self
.details
[iface
]]
469 if command_name
is None:
470 add_iface(root_interface
, root_arch
)
472 commands
= add_command_iface(root_interface
, root_arch
, command_name
)
474 problem
.add_clause(commands
) # At least one
475 group_clause_for_command
[(root_interface
, command_name
)] = problem
.at_most_one(commands
)
477 # (note: might be because we haven't cached it yet)
478 info("No %s <command> in %s", command_name
, root_interface
)
480 impls
= impls_for_iface
[self
.iface_cache
.get_interface(root_interface
)]
481 if impls
== [] or (len(impls
) == 1 and isinstance(impls
[0], _DummyImpl
)):
482 # There were no candidates at all.
483 self
._failure
_reason
= _("Interface '%s' has no usable implementations") % root_interface
485 # We had some candidates implementations, but none for the command we need
486 self
._failure
_reason
= _("Interface '%s' cannot be executed directly; it is just a library "
487 "to be used by other programs (or missing '%s' command)") % (root_interface
, command_name
)
491 # Require m<group> to be true if we select an implementation in that group
493 for machine_group
, impls
in impls_for_machine_group
.iteritems():
494 m_group
= 'm%d' % machine_group
495 group_var
= problem
.add_variable(m_group
)
498 problem
.add_clause([group_var
, sat
.neg(impl
)])
499 m_groups
.append(group_var
)
501 m_groups_clause
= problem
.at_most_one(m_groups
)
503 m_groups_clause
= None
506 """Recurse through the current selections until we get to an interface with
507 no chosen version, then tell the solver to try the best version from that."""
509 def find_undecided_dep(impl_or_command
, arch
):
510 # Check for undecided dependencies of impl_or_command
511 for dep
in deps_in_use(impl_or_command
, arch
):
512 dep_lit
= find_undecided(dep
.interface
)
513 if dep_lit
is not None:
518 def find_undecided(uri
):
520 return # Break cycles
523 group
= group_clause_for
[uri
]
524 #print "Group for %s = %s" % (uri, group)
527 return group
.best_undecided()
528 # else there was only one choice anyway
530 # Check for undecided dependencies
531 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
532 return find_undecided_dep(lit_info
.impl
, lit_info
.arch
)
534 def find_undecided_command(uri
, name
):
535 if name
is None: return find_undecided(uri
)
537 group
= group_clause_for_command
[(uri
, name
)]
540 return group
.best_undecided()
541 # else we've already chosen which <command> to use
543 # Check for undecided command-specific dependencies, and then for
544 # implementation dependencies.
545 lit_info
= problem
.get_varinfo_for_lit(lit
).obj
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() + [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 # TODO: allow depending on other commands, besides 'run'?
599 add_command(runner
.metadata
['interface'], 'run')
601 if command_name
is not None:
602 add_command(root_interface
, command_name
)
604 def get_failure_reason(self
):
605 """Return an exception explaining why the solve failed."""
606 assert not self
.ready
608 if self
._failure
_reason
:
609 return model
.SafeException(self
._failure
_reason
)
611 return model
.SafeException(_("Can't find all required implementations:") + '\n' +
612 '\n'.join(["- %s -> %s" % (iface
, self
.selections
[iface
])
613 for iface
in self
.selections
]))
615 DefaultSolver
= SATSolver