88"""Chooses a set of implementations to satisfy the requirements of a program and its user. 89 Typical use: 90 1. Create a Solver object and configure it 91 2. Call L{solve}. 92 3. If any of the returned feeds_used are stale or missing, you may like to start downloading them 93 4. If it is 'ready' then you can download and run the chosen versions. 94 @ivar selections: the chosen implementation of each interface 95 @type selections: L{selections.Selections} 96 @ivar requires: the selected dependencies for each chosen version 97 @type requires: {L{model.Interface}: [L{model.Dependency}]} 98 @ivar feeds_used: the feeds which contributed to the choice in L{selections} 99 @type feeds_used: set(str) 100 @ivar record_details: whether to record information about unselected implementations 101 @type record_details: {L{Interface}: [(L{Implementation}, str)]} 102 @ivar details: extra information, if record_details mode was used 103 @type details: {str: [(Implementation, comment)]} 104 """ 105__slots__=['selections','requires','feeds_used','details','record_details','ready'] 106
113"""Solve for given requirements. 114 @param requirements: the interface, architecture and command to solve for 115 @type requirements: L{requirements.Requirements} 116 @postcondition: self.ready, self.selections and self.feeds_used are updated 117 @since: 1.8""" 118returnself.solve(requirements.interface_uri,self.get_arch_for(requirements),requirements.command)
121"""Get the best implementation of root_interface and all of its dependencies. 122 @param root_interface: the URI of the program to be solved 123 @type root_interface: str 124 @param root_arch: the desired target architecture 125 @type root_arch: L{arch.Architecture} 126 @param command_name: which <command> element to select 127 @type command_name: str | None 128 @postcondition: self.ready, self.selections and self.feeds_used are updated""" 129raiseNotImplementedError("Abstract")
132"""Return the Architecture we would use when solving for this interface. 133 Normally, this architecture is constructed from the OS and CPU type in the requirements, 134 using the host platform's settings if these are not given. 135 If interface is the root, then we wrap this in a SourceArchitecture if looking 136 for source code and (for backwards compatibility) we enable use="testing" dependencies 137 if the command is "test". 138 @param requirements: the overall requirements for the solve 139 @type requirements: L{requirements.Requirements} 140 @param interface: the interface of interest 141 @type interface: L{model.Interface} 142 @return: the architecture that would be used 143 @rtype: L{architecture.Architecture} 144 @since: 1.9""" 145root_arch=arch.get_architecture(requirements.os,requirements.cpu) 146ifinterfaceisNoneorinterface.uri==requirements.interface_uri: 147ifrequirements.source: 148root_arch=arch.SourceArchitecture(root_arch) 149ifrequirements.command=='test': 150# This is for old feeds that have use='testing' instead of the newer 151# 'test' command for giving test-only dependencies. 152root_arch=arch.Architecture(root_arch.os_ranks,root_arch.machine_ranks) 153root_arch.use=frozenset([None,"testing"]) 154returnroot_arch 155# Assume we use the same arch for all descendants 156returnroot_arch.child_arch
159"""Converts the problem to a set of pseudo-boolean constraints and uses a PB solver to solve them. 160 @ivar langs: the preferred languages (e.g. ["es_ES", "en"]). Initialised to the current locale. 161 @type langs: str""" 162 163__slots__=['_impls_for_iface','_iface_to_vars','_problem','config','extra_restrictions','_lang_ranks','_langs'] 164 165@property
170"""@param config: policy preferences (e.g. stability), the iface_cache and the stores to use 171 @type config: L{policy.Config} 172 @param extra_restrictions: extra restrictions on the chosen implementations 173 @type extra_restrictions: {L{model.Interface}: [L{model.Restriction}]}""" 174Solver.__init__(self) 175assertnotisinstance(config,str),"API change!" 176self.config=config 177self.extra_restrictions=extra_restrictionsor{} 178 179# By default, prefer the current locale's language first and English second 180self.langs=[locale.getlocale()[0]or'en','en']
183"""Set the preferred languages. 184 @param langs: languages (and regions), first choice first 185 @type langs: [str]""" 186# _lang_ranks is a map from locale string to score (higher is better) 187_lang_ranks={} 188score=0 189i=len(langs) 190# (is there are duplicates, the first occurance takes precedence) 191whilei>0: 192i-=1 193lang=langs[i].replace('_','-') 194_lang_ranks[lang.split('-')[0]]=score 195_lang_ranks[lang]=score+1 196score+=2 197self._langs=langs 198self._lang_ranks=_lang_ranks
203"""@type interface: L{zeroinstall.injector.model.Interface} 204 @type impl: L{zeroinstall.injector.model.Implementation} 205 @type arch: L{zeroinstall.injector.arch.Architecture} 206 @rtype: [object]""" 207impl_langs=(impl.langsor'en').split() 208my_langs=self._lang_ranks 209 210stores=self.config.stores 211is_available=impl.is_available(stores) 212 213# Stability 214stab_policy=interface.stability_policy 215ifnotstab_policy: 216ifself.config.help_with_testing:stab_policy=model.testing 217else:stab_policy=model.stable 218 219stability=impl.get_stability() 220ifstability>=stab_policy: 221stability_limited=model.preferred 222else: 223stability_limited=stability 224 225# Note: this list must match _ranking_component_reason above 226return[ 227# Languages we understand come first 228max(my_langs.get(l.split('-')[0],-1)forlinimpl_langs), 229 230# Preferred versions come first 231stability==model.preferred, 232 233# Prefer available implementations next if we have limited network access 234self.config.network_use!=model.network_fullandis_available, 235 236# Packages that require admin access to install come last 237notimpl.requires_root_install, 238 239# Prefer more stable versions, but treat everything over stab_policy the same 240# (so we prefer stable over testing if the policy is to prefer "stable", otherwise 241# we don't care) 242stability_limited, 243 244# Newer versions come before older ones (ignoring modifiers) 245impl.version[0], 246 247# Prefer native packages if the main part of the versions are the same 248impl.id.startswith('package:'), 249 250# Full version compare (after package check, since comparing modifiers between native and non-native 251# packages doesn't make sense). 252impl.version, 253 254# Get best OS 255-arch.os_ranks.get(impl.os,999), 256 257# Get best machine 258-arch.machine_ranks.get(impl.machine,999), 259 260# Slightly prefer languages specialised to our country 261# (we know a and b have the same base language at this point) 262max(my_langs.get(l,-1)forlinimpl_langs), 263 264# Slightly prefer cached versions 265is_available, 266 267# Order by ID so the order isn't random 268impl.id 269]
272"""@type root_interface: str 273 @type root_arch: L{zeroinstall.injector.arch.Architecture} 274 @type command_name: str | None 275 @type closest_match: bool""" 276 277# closest_match is used internally. It adds a lowest-ranked 278# by valid implementation to every interface, so we can always 279# select something. Useful for diagnostics. 280 281# The basic plan is this: 282# 1. Scan the root interface and all dependencies recursively, building up a SAT problem. 283# 2. Solve the SAT problem. Whenever there are multiple options, try the most preferred one first. 284# 3. Create a Selections object from the results. 285# 286# All three involve recursively walking the tree in a similar way: 287# 1) we follow every dependency of every implementation (order not important) 288# 2) we follow every dependency of every selected implementation (better versions first) 289# 3) we follow every dependency of every selected implementation (order doesn't matter) 290# 291# In all cases, a dependency may be on an <implementation> or on a specific <command>. 292 293# TODO: We need some way to figure out which feeds to include. 294# Currently, we include any feed referenced from anywhere but 295# this is probably too much. We could insert a dummy optimial 296# implementation in stale/uncached feeds and see whether it 297# selects that. 298iface_cache=self.config.iface_cache 299 300problem=sat.SATProblem() 301 302# For each (interface, impl) we have a sat variable which, if true, means that we have selected 303# that impl as the implementation of the interface. We have to index on interface and impl (not 304# just impl) because the same feed can provide implementations for different interfaces. This 305# happens, for example, when an interface is renamed and the new interface imports the old feed: 306# old versions of a program are likely to use the old interface name while new ones use the new 307# name. 308iface_to_vars=collections.defaultdict(lambda:{})# Iface -> (Impl -> sat var) 309 310self.feeds_used=set() 311self.requires={} 312self.ready=False 313self.details={}ifself.record_detailsorclosest_matchelseFalse 314 315self.selections=None 316 317# Only set if there is an error 318self._impls_for_iface=None 319self._iface_to_vars=None 320self._problem=None 321 322ifaces_processed=set() 323 324machine_groups=arch.machine_groups 325impls_for_machine_group={0:[]}# Machine group (e.g. "64") to [impl] in that group 326formachine_groupinmachine_groups.values(): 327impls_for_machine_group[machine_group]=[] 328 329impls_for_iface={}# Iface -> [impl] 330 331# For each interface, the group clause says we can't select two implementations of it at once. 332# We use this map at the end to find out what was actually selected. 333group_clause_for={}# Iface URI -> AtMostOneClause 334group_clause_for_command={}# (Iface URI, command name) -> AtMostOneClause | bool 335 336# Return the dependencies of impl that we should consider. 337# Skips dependencies if the use flag isn't what we need. 338# (note: impl may also be a model.Command) 339defdeps_in_use(impl,arch): 340fordepinimpl.requires: 341use=dep.metadata.get("use",None) 342ifusenotinarch.use: 343continue 344 345# Ignore dependency if 'os' attribute is present and doesn't match 346os=dep.metadata.get("os",None) 347ifosandosnotinarch.os_ranks: 348continue 349 350yielddep
351 352defclone_command_for(command,arch): 353# This is a bit messy. We need to make a copy of the command, without the 354# unnecessary <requires> elements. 355all_dep_elems=set(dep.qdomfordepincommand.requires) 356required_dep_elems=set(dep.qdomfordepindeps_in_use(command,arch)) 357ifall_dep_elems==required_dep_elems: 358returncommand# No change 359dep_elems_to_remove=all_dep_elems-required_dep_elems 360old_root=command.qdom 361new_qdom=qdom.Element(old_root.uri,old_root.name,old_root.attrs) 362new_qdom.childNodes=[nodefornodeincommand.qdom.childNodesif 363nodenotindep_elems_to_remove] 364returnmodel.Command(new_qdom,command._local_dir)
365 366# Must have already done add_iface on dependency.interface. 367# If dependency is essential: 368# Add a clause so that if requiring_impl_var is True then an implementation 369# matching 'dependency' must also be selected. 370# If dependency is optional: 371# Require that no incompatible version is selected. 372# This ignores any 'command' required. Handle that separately. 373deffind_dependency_candidates(requiring_impl_var,dependency): 374defmeets_restrictions(candidate): 375forrindependency.restrictions: 376ifnotr.meets_restriction(candidate): 377#warn("%s rejected due to %s", candidate.get_version(), r) 378returnFalse 379returnTrue 380 381essential=dependency.importance==model.Dependency.Essential 382 383dep_iface=iface_cache.get_interface(dependency.interface) 384dep_union=[sat.neg(requiring_impl_var)]# Either requiring_impl_var is False, or ... 385 386impl_to_var=iface_to_vars[dep_iface]# Impl -> sat var 387 388forcandidateinimpls_for_iface[dep_iface]: 389if(candidate.__class__is_DummyImpl)ormeets_restrictions(candidate): 390ifessential: 391c_var=impl_to_var.get(candidate,None) 392ifc_varisnotNone: 393dep_union.append(c_var) 394# else we filtered that version out, so ignore it 395else: 396# Candidate doesn't meet our requirements 397# If the dependency is optional add a rule to make sure we don't 398# select this candidate. 399# (for essential dependencies this isn't necessary because we must 400# select a good version and we can't select two) 401ifnotessential: 402c_var=impl_to_var.get(candidate,None) 403ifc_varisnotNone: 404problem.add_clause(dep_union+[sat.neg(c_var)]) 405# else we filtered that version out, so ignore it 406 407ifessential: 408problem.add_clause(dep_union) 409 410defis_unusable(impl,restrictions,arch): 411"""@return: whether this implementation is unusable. 412 @rtype: bool""" 413returnget_unusable_reason(impl,restrictions,arch)!=None 414 415defget_unusable_reason(impl,restrictions,arch): 416""" 417 @param impl: Implementation to test. 418 @param restrictions: user-provided restrictions (extra_restrictions) 419 @type restrictions: [L{model.Restriction}] 420 @return: The reason why this impl is unusable, or None if it's OK. 421 @rtype: str 422 @note: The restrictions are for the interface being requested, not the feed 423 of the implementation; they may be different when feeds are being used.""" 424forrinrestrictions: 425ifnotr.meets_restriction(impl): 426returnr.reason 427stability=impl.get_stability() 428ifstability<=model.buggy: 429returnstability.name 430if(self.config.network_use==model.network_offlineornotimpl.download_sources)andnotimpl.is_available(self.config.stores): 431ifnotimpl.download_sources: 432return_("No retrieval methods") 433return_("Not cached and we are off-line") 434ifimpl.osnotinarch.os_ranks: 435return_("Unsupported OS") 436ifimpl.machinenotinarch.machine_ranks: 437ifimpl.machine=='src': 438return_("Source code") 439elif'src'inarch.machine_ranks: 440return_("Not source code") 441return_("Unsupported machine type") 442returnNone 443 444defusable_feeds(iface,arch): 445"""Return all feeds for iface that support arch. 446 @rtype: generator(ZeroInstallFeed)""" 447yieldiface.uri 448 449forfiniface_cache.get_feed_imports(iface): 450# Note: when searching for src, None is not in machine_ranks 451iff.osinarch.os_ranksand \ 452(f.machineisNoneorf.machineinarch.machine_ranks): 453yieldf.uri 454else: 455logger.debug(_("Skipping '%(feed)s'; unsupported architecture %(os)s-%(machine)s"), 456{'feed':f,'os':f.os,'machine':f.machine}) 457 458# If requiring_var is True then all of requirer's dependencies must be satisfied. 459# requirer can be a <command> or an <implementation> 460defprocess_dependencies(requiring_var,requirer,arch): 461fordindeps_in_use(requirer,arch): 462#logger.debug(_("Considering command dependency %s"), d) 463 464add_iface(d.interface,arch.child_arch) 465 466forcind.get_required_commands(): 467# We depend on a specific command within the implementation. 468command_vars=add_command_iface(d.interface,arch.child_arch,c) 469 470# If the parent command/impl is chosen, one of the candidate commands 471# must be too. If there aren't any, then this command is unselectable. 472problem.add_clause([sat.neg(requiring_var)]+command_vars) 473 474# Must choose one version of d if impl is selected 475find_dependency_candidates(requiring_var,d) 476 477replacement_for={}# Interface -> Replacement Interface 478 479defadd_iface(uri,arch): 480"""Name implementations from feed and assert that only one can be selected.""" 481ifuriinifaces_processed:return 482ifaces_processed.add(uri) 483 484iface=iface_cache.get_interface(uri) 485 486main_feed=iface_cache.get_feed(uri) 487ifmain_feed: 488replacement=main_feed.get_replaced_by() 489ifreplacementisnotNone: 490replacement_for[iface]=iface_cache.get_interface(replacement) 491 492impls=[] 493forfinusable_feeds(iface,arch): 494self.feeds_used.add(f) 495logger.debug(_("Processing feed %s"),f) 496 497try: 498feed=iface_cache.get_feed(f) 499iffeedisNone:continue 500#if feed.name and iface.uri != feed.url and iface.uri not in feed.feed_for: 501# info(_("Missing <feed-for> for '%(uri)s' in '%(feed)s'"), {'uri': iface.uri, 'feed': f}) 502 503iffeed.implementations: 504impls.extend(feed.implementations.values()) 505 506distro_feed_url=feed.get_distro_feed() 507ifdistro_feed_url: 508self.feeds_used.add(distro_feed_url) 509distro_feed=iface_cache.get_feed(distro_feed_url) 510ifdistro_feed.implementations: 511impls.extend(distro_feed.implementations.values()) 512exceptMissingLocalFeedasex: 513logger.warning(_("Missing local feed; if it's no longer required, remove it with:")+ 514'\n0install remove-feed '+iface.uri+' '+f, 515{'feed':f,'interface':iface,'exception':ex}) 516exceptmodel.SafeExceptionasex: 517logger.warning(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"),{'feed':f,'interface':iface,'exception':ex}) 518#raise 519exceptExceptionasex: 520importlogging 521logger.warning(_("Failed to load feed %(feed)s for %(interface)s: %(exception)s"),{'feed':f,'interface':iface,'exception':ex}, 522exc_info=Trueiflogger.isEnabledFor(logging.INFO)elseNone) 523 524impls.sort(key=lambdaimpl:self.get_rating(iface,impl,arch),reverse=True) 525 526impls_for_iface[iface]=filtered_impls=[] 527 528my_extra_restrictions=self.extra_restrictions.get(iface,[]) 529 530ifself.detailsisnotFalse: 531self.details[iface]=[(impl,get_unusable_reason(impl,my_extra_restrictions,arch))forimplinimpls] 532 533impl_to_var=iface_to_vars[iface]# Impl -> sat var 534 535var_names=[] 536forimplinimpls: 537ifis_unusable(impl,my_extra_restrictions,arch): 538continue 539 540filtered_impls.append(impl) 541 542assertimplnotinimpl_to_var,impl 543v=problem.add_variable(ImplInfo(iface,impl,arch)) 544impl_to_var[impl]=v 545var_names.append(v) 546 547ifimpl.machineandimpl.machine!='src': 548impls_for_machine_group[machine_groups.get(impl.machine,0)].append(v) 549 550process_dependencies(v,impl,arch) 551 552ifclosest_match: 553dummy_impl=_DummyImpl() 554dummy_var=problem.add_variable(ImplInfo(iface,dummy_impl,arch,dummy=True)) 555var_names.append(dummy_var) 556impl_to_var[dummy_impl]=dummy_var 557filtered_impls.append(dummy_impl) 558 559# Only one implementation of this interface can be selected 560ifuri==root_interface: 561ifvar_names: 562clause=problem.at_most_one(var_names) 563problem.add_clause(var_names)# at least one 564else: 565problem.impossible() 566clause=False 567elifvar_names: 568clause=problem.at_most_one(var_names) 569else: 570# Don't need to add to group_clause_for because we should 571# never get a possible selection involving this. 572return 573 574assertclauseisnotTrue 575assertclauseisnotNone 576ifclauseisnotFalse: 577group_clause_for[uri]=clause 578 579defadd_command_iface(uri,arch,command_name): 580"""Add every <command> in interface 'uri' with this name. 581 Each one depends on the corresponding implementation and only 582 one can be selected. If closest_match is on, include a dummy 583 command that can always be selected.""" 584 585# Check whether we've already processed this (interface,command) pair 586existing=group_clause_for_command.get((uri,command_name),None) 587ifexistingisnotNone: 588returnexisting.lits 589 590# First ensure that the interface itself has been processed 591# We'll reuse the ordering of the implementations to order 592# the commands too. 593add_iface(uri,arch) 594 595iface=iface_cache.get_interface(uri) 596filtered_impls=impls_for_iface[iface] 597impl_to_var=iface_to_vars[iface]# Impl -> sat var 598 599var_names=[] 600forimplinfiltered_impls: 601command=impl.commands.get(command_name,None) 602ifnotcommand: 603ifnotisinstance(impl,_DummyImpl): 604# Mark implementation as unselectable 605problem.add_clause([sat.neg(impl_to_var[impl])]) 606continue 607 608# We have a candidate <command>. Require that if it's selected 609# then we select the corresponding <implementation> too. 610command_var=problem.add_variable(CommandInfo(command_name,command,impl,arch)) 611problem.add_clause([impl_to_var[impl],sat.neg(command_var)]) 612 613var_names.append(command_var) 614 615process_dependencies(command_var,command,arch) 616 617# Tell the user why we couldn't use this version 618ifself.detailsisnotFalse: 619defnew_reason(impl,old_reason): 620ifcommand_nameinimpl.commands: 621returnold_reason 622returnold_reasonor(_('No %s command')%command_name) 623self.details[iface]=[(impl,new_reason(impl,reason))for(impl,reason)inself.details[iface]] 624 625ifclosest_match: 626dummy_command=problem.add_variable(None) 627var_names.append(dummy_command) 628 629ifvar_names: 630# Can't select more than one of them. 631assert(uri,command_name)notingroup_clause_for_command 632group_clause_for_command[(uri,command_name)]=problem.at_most_one(var_names) 633 634returnvar_names 635 636ifcommand_nameisNone: 637add_iface(root_interface,root_arch) 638else: 639commands=add_command_iface(root_interface,root_arch,command_name) 640iflen(commands)>int(closest_match): 641# (we have at least one non-dummy command) 642problem.add_clause(commands)# At least one 643else: 644# (note: might be because we haven't cached it yet) 645logger.info("No %s <command> in %s",command_name,root_interface) 646 647problem.impossible() 648 649# Require m<group> to be true if we select an implementation in that group 650m_groups=[] 651formachine_group,implsinimpls_for_machine_group.items(): 652m_group='m%d'%machine_group 653group_var=problem.add_variable(m_group) 654ifimpls: 655forimplinimpls: 656problem.add_clause([group_var,sat.neg(impl)]) 657m_groups.append(group_var) 658ifm_groups: 659m_groups_clause=problem.at_most_one(m_groups) 660else: 661m_groups_clause=None 662 663# Can't select an implementation of an interface and of its replacement 664fororiginal,replacementinreplacement_for.items(): 665iforiginal==replacement: 666logger.warning("Interface %s replaced-by itself!",original) 667continue 668rep_impls=iface_to_vars.get(replacement,None) 669ifrep_implsisNone: 670# We didn't even look at the replacement interface, so no risk here 671continue 672# Must select one implementation out of all candidates from both interface. 673# Dummy implementations don't conflict, though. 674all_impls=[] 675forimpl,varinrep_impls.items(): 676ifnotisinstance(impl,_DummyImpl): 677all_impls.append(var) 678forimpl,variniface_to_vars[original].items(): 679ifnotisinstance(impl,_DummyImpl): 680all_impls.append(var) 681ifall_impls: 682problem.at_most_one(all_impls) 683# else: neither feed has any usable impls anyway 684 685defdecide(): 686"""This is called by the SAT solver when it cannot simplify the problem further. 687 Our job is to find the most-optimal next selection to try. 688 Recurse through the current selections until we get to an interface with 689 no chosen version, then tell the solver to try the best version from that.""" 690 691deffind_undecided_dep(impl_or_command,arch): 692# Check for undecided dependencies of impl_or_command 693fordepindeps_in_use(impl_or_command,arch): 694# Restrictions don't express that we do or don't want the 695# dependency, so skip them here. 696ifdep.importance==model.Dependency.Restricts:continue 697 698forcindep.get_required_commands(): 699dep_lit=find_undecided_command(dep.interface,c) 700ifdep_litisnotNone: 701returndep_lit 702dep_lit=find_undecided(dep.interface) 703ifdep_litisnotNone: 704returndep_lit 705returnNone 706 707seen=set() 708deffind_undecided(uri): 709ifuriinseen: 710return# Break cycles 711seen.add(uri) 712 713group=group_clause_for.get(uri,None) 714 715ifgroupisNone: 716# (can be None if the selected impl has an optional dependency on 717# a feed with no implementations) 718return 719 720#print "Group for %s = %s" % (uri, group) 721lit=group.current 722iflitisNone: 723returngroup.best_undecided() 724# else there was only one choice anyway 725 726# Check for undecided dependencies 727lit_info=problem.get_varinfo_for_lit(lit).obj 728returnfind_undecided_dep(lit_info.impl,lit_info.arch) 729 730deffind_undecided_command(uri,name): 731ifnameisNone:returnfind_undecided(uri) 732 733group=group_clause_for_command[(uri,name)] 734lit=group.current 735iflitisNone: 736returngroup.best_undecided() 737# else we've already chosen which <command> to use 738 739# Check for undecided command-specific dependencies, and then for 740# implementation dependencies. 741lit_info=problem.get_varinfo_for_lit(lit).obj 742iflit_infoisNone: 743assertclosest_match 744returnNone# (a dummy command added for better diagnostics; has no dependencies) 745returnfind_undecided_dep(lit_info.command,lit_info.arch)or \ 746find_undecided_dep(lit_info.impl,lit_info.arch) 747 748best=find_undecided_command(root_interface,command_name) 749ifbestisnotNone: 750returnbest 751 752# If we're chosen everything we need, we can probably 753# set everything else to False. 754forgroupinlist(group_clause_for.values())+list(group_clause_for_command.values())+[m_groups_clause]: 755ifgroup.currentisNone: 756best=group.best_undecided() 757ifbestisnotNone: 758returnsat.neg(best) 759 760returnNone# Failed to find any valid combination 761 762ready=problem.run_solver(decide)isTrue 763 764ifnotreadyandnotclosest_match: 765# We failed while trying to do a real solve. 766# Try a closest match solve to get a better 767# error report for the user. 768self.solve(root_interface,root_arch,command_name=command_name,closest_match=True) 769else: 770self.ready=readyandnotclosest_match 771self.selections=selections.Selections(None) 772self.selections.interface=root_interface 773 774ifnotself.ready: 775# Store some things useful for get_failure_reason() 776self._impls_for_iface=impls_for_iface 777self._iface_to_vars=iface_to_vars 778self._problem=problem 779 780sels=self.selections.selections 781 782commands_needed=[] 783 784# Populate sels with the selected implementations. 785# Also, note down all the commands we need. 786foruri,groupingroup_clause_for.items(): 787ifgroup.currentisnotNone: 788lit_info=problem.get_varinfo_for_lit(group.current).obj 789iflit_info.is_dummy: 790sels[lit_info.iface.uri]=None 791else: 792# We selected an implementation for interface 'uri' 793impl=lit_info.impl 794 795forbinimpl.bindings: 796c=b.command 797ifcisnotNone: 798commands.append((uri,c)) 799 800deps=self.requires[lit_info.iface]=[] 801fordepindeps_in_use(lit_info.impl,lit_info.arch): 802deps.append(dep) 803forcindep.get_required_commands(): 804commands_needed.append((dep.interface,c)) 805 806sel=sels[lit_info.iface.uri]=selections.ImplSelection(lit_info.iface.uri,impl,deps) 807sel.__arch=lit_info.arch 808 809# Now all all the commands in too. 810defadd_command(iface,name): 811sel=sels.get(iface,None) 812ifsel: 813command=sel.impl.commands[name] 814ifnameinsel._used_commands: 815return# Already added 816sel._used_commands[name]=clone_command_for(command,sel.__arch) 817 818fordepincommand.requires: 819fordep_command_nameindep.get_required_commands(): 820add_command(dep.interface,dep_command_name) 821 822# A <command> can depend on another <command> in the same interface 823# (e.g. the tests depending on the main program) 824forbincommand.bindings: 825c=b.command 826ifcisnotNone: 827add_command(iface,c) 828 829foriface,commandincommands_needed: 830add_command(iface,command) 831 832ifcommand_nameisnotNone: 833self.selections.command=command_name 834add_command(root_interface,command_name) 835 836ifroot_interfacenotinsels: 837sels[root_interface]=None# Useful for get_failure_reason() 838
840"""Return an exception explaining why the solve failed. 841 @rtype: L{zeroinstall.SafeException}""" 842assertnotself.ready 843 844sels=self.selections.selections 845 846iface_cache=self.config.iface_cache 847 848problem=self._problem 849impls_for_iface=self._impls_for_iface 850assertimpls_for_iface 851 852defshow(iface_uri): 853# Find all restrictions that are in play and affect this interface 854sel=sels[iface_uri] 855ifsel: 856msg='{version} ({impl})'.format(version=sel.version,impl=sel.id) 857else: 858msg="(problem)" 859 860iface=iface_cache.get_interface(iface_uri) 861 862impls=impls_for_iface[iface_cache.get_interface(iface_uri)] 863impls=[iforiinimplsifnotisinstance(i,_DummyImpl)] 864 865defapply_restrictions(impls,restrictions): 866forrinrestrictions: 867impls=[iforiinimplsifr.meets_restriction(i)] 868returnimpls
869 870# orig_impls is all the implementations passed to the SAT solver (these are the 871# ones with a compatible OS, CPU, etc). They are sorted most desirable first. 872orig_impls=impls 873 874defget_machine_group(impl): 875machine=impl.machine 876ifmachineandmachine!='src': 877returnarch.machine_groups.get(machine,0) 878returnNone 879 880example_machine_impl=None# An example chosen impl with a machine type 881 882our_feed=iface_cache.get_feed(iface_uri) 883our_replacement=our_feed.get_replaced_by()ifour_feedelseNone 884 885# For each selected implementation... 886forother_uri,other_selinsels.items(): 887# Check for interface-level conflicts 888other_iface=iface_cache.get_feed(other_uri) 889ifother_ifaceandother_iface.get_replaced_by()==iface_uri: 890msg+="\n "+_("Replaces (and therefore conflicts with) {old}").format(old=other_uri) 891ifother_sel: 892impls=[] 893 894ifour_replacement==other_uri: 895msg+="\n "+_("Replaced by (and therefore conflicts with) {old}").format(old=other_uri) 896ifother_sel: 897impls=[] 898 899# Otherwise, if we didn't select an implementation then that can't be causing a problem 900ifnotother_sel:continue 901 902ifexample_machine_implisNone: 903required_machine_group=get_machine_group(other_sel.impl) 904ifrequired_machine_groupisnotNone: 905example_machine_impl=other_sel.impl 906 907fordepinother_sel.impl.requires: 908ifnotisinstance(dep,model.InterfaceRestriction):continue 909# If it depends on us and has restrictions... 910ifdep.interface==iface_urianddep.restrictions: 911# Report the restriction 912msg+="\n "+_("{iface} {version} requires {reqs}").format( 913iface=other_uri, 914version=other_sel.version, 915reqs=', '.join(str(r)forrindep.restrictions)) 916 917# Remove implementations incompatible with the other selections 918impls=apply_restrictions(impls,dep.restrictions) 919 920# Check for user-supplied restrictions 921user=self.extra_restrictions.get(iface,[]) 922ifuser: 923msg+="\n "+_("User requested {reqs}").format( 924reqs=', '.join(str(r)forrinuser)) 925impls=apply_restrictions(impls,user) 926 927ifselisNone: 928# Report on available implementations 929all_impls=self.details.get(iface,{}) 930ifnotorig_impls: 931ifnotall_impls: 932msg+="\n "+_("No known implementations at all") 933else: 934# No implementations were passed to the solver. 935msg+="\n "+_("No usable implementations:") 936fori,reasoninall_impls[:5]: 937msg+="\n {impl}: {reason}".format(impl=i,reason=reason) 938iflen(all_impls)>5: 939msg+="\n ..." 940elifnotimpls: 941msg+="\n "+_("No usable implementations satisfy the restrictions") 942else: 943# Might still be unusable e.g. if missing a required command. Show reasons, if any. 944shown=0 945candidate_impls=set(impls) 946fori,reasoninall_impls: 947ifreasonis_ForceImpl.reason: 948# We're doing a justify_decision, and this wasn't the one the user specified 949continue 950 951ifinotincandidate_impls: 952# Skip, as hopefully obvious from above restrictions why not chosen 953continue 954 955ifreasonisNoneandexample_machine_impl: 956# Could be an architecture problem 957this_machine_group=get_machine_group(i) 958ifthis_machine_groupisnotNoneandthis_machine_group!=required_machine_group: 959reason=_("Can't use {this_arch} with selection of {other_name} ({other_arch})").format( 960this_arch=i.machine, 961other_name=example_machine_impl.feed.get_name(), 962other_arch=example_machine_impl.machine) 963 964ifreasonisNone: 965# Check if our requirements conflict with an existing selection 966fordepini.requires: 967ifnotisinstance(dep,model.InterfaceRestriction):continue 968dep_selection=sels.get(dep.interface) 969ifdep_selectionisnotNone: 970forrindep.restrictions: 971ifnotr.meets_restriction(dep_selection.impl): 972reason=_("requires {iface} {reqs}").format( 973iface=dep.interface, 974reqs=', '.join(str(r)forrindep.restrictions)) 975break 976 977ifreasonisNone: 978var=self._iface_to_vars[iface].get(i,None) 979ifvarisNone: 980reason="BUG: no var for impl!" 981else: 982varinfo=problem.get_varinfo_for_lit(var) 983reason="Hard to explain. Internal reason: {reason} => {assignment}".format( 984reason=varinfo.reason, 985assignment=varinfo) 986 987ifreasonisnot_ForceImpl.reason: 988ifshown>=5: 989msg+="\n ..." 990break 991ifshown==0: 992msg+="\n "+_("Rejected candidates:") 993msg+="\n {impl}: {reason}".format(impl=i,reason=reason) 994shown+=1 995 996returnmsg 997 998msg=_("Can't find all required implementations:")+'\n'+ \ 999'\n'.join(["- %s -> %s"%(iface,show(iface))forifaceinsorted(sels)])10001001ifself.config.network_use==model.network_offline:1002msg+="\nNote: 0install is in off-line mode"10031004returnmodel.SafeException(msg)1005
1007"""Run a solve with impl_id forced to be selected, and explain why it wasn't (or was)1008 selected in the normal case.1009 @type requirements: L{zeroinstall.injector.requirements.Requirements}1010 @type iface: L{zeroinstall.injector.model.Interface}1011 @type impl: L{zeroinstall.injector.model.Implementation}1012 @rtype: str"""1013assertisinstance(iface,model.Interface),iface10141015restrictions=self.extra_restrictions.copy()1016restrictions[iface]=restrictions.get(iface,[])+[_ForceImpl(impl)]1017s=SATSolver(self.config,restrictions)1018s.record_details=True1019s.solve_for(requirements)10201021wanted="{iface} {version}".format(iface=iface.get_name(),version=impl.get_version())10221023# Could a selection involving impl even be valid?1024ifnots.readyoriface.urinotins.selections.selections:1025reasons=s.details.get(iface,[])1026for(rid,rstr)inreasons:1027ifrid.id==impl.idandrstrisnotNone:1028return_("{wanted} cannot be used (regardless of other components): {reason}").format(1029wanted=wanted,1030reason=rstr)10311032ifnots.ready:1033return_("There is no possible selection using {wanted}.\n{reason}").format(1034wanted=wanted,1035reason=s.get_failure_reason())10361037actual_selection=self.selections.get(iface,None)1038ifactual_selectionisnotNone:1039# Was impl actually selected anyway?1040ifactual_selection.id==impl.id:1041return_("{wanted} was selected as the preferred version.").format(wanted=wanted)10421043# Was impl ranked below the selected version?1044iface_arch=arch.get_architecture(requirements.os,requirements.cpu)1045ifrequirements.sourceandiface.uri==requirements.interface_uri:1046iface_arch=arch.SourceArchitecture(iface_arch)1047wanted_rating=self.get_rating(iface,impl,arch)1048selected_rating=self.get_rating(iface,actual_selection,arch)10491050ifwanted_rating<selected_rating:1051_ranking_component_reason=[1052_("natural languages we understand are preferred"),1053_("preferred versions come first"),1054_("locally-available versions are preferred when network use is limited"),1055_("packages that don't require admin access to install are preferred"),1056_("more stable versions preferred"),1057_("newer versions are preferred"),1058_("native packages are preferred"),1059_("newer versions are preferred"),1060_("better OS match"),1061_("better CPU match"),1062_("better locale match"),1063_("is locally available"),1064_("better ID (tie-breaker)"),1065]10661067actual=actual_selection.get_version()1068ifimpl.get_version()==actual:1069defdetail(i):1070iflen(i.id)<18:1071return" ("+i.id+")"1072else:1073return" ("+i.id[:16]+"...)"
10741075wanted+=detail(impl)1076actual+=detail(actual_selection)10771078foriinrange(len(wanted_rating)):1079ifwanted_rating[i]<selected_rating[i]:1080return_("{wanted} is ranked lower than {actual}: {why}").format(1081wanted=wanted,1082actual=actual,1083why=_ranking_component_reason[i])10841085used_impl=iface.uriins.selections.selections10861087# Impl is selectable and ranked higher than the selected version. Selecting it would cause1088# a problem elsewhere.1089changes=[]1090forold_iface,old_selinself.selections.selections.items():1091ifold_iface==iface.uriandused_impl:continue1092new_sel=s.selections.selections.get(old_iface,None)1093ifnew_selisNone:1094changes.append(_("{interface}: no longer used").format(interface=old_iface))1095elifold_sel.version!=new_sel.version:1096changes.append(_("{interface}: {old} to {new}").format(interface=old_iface,old=old_sel.version,new=new_sel.version))1097elifold_sel.id!=new_sel.id:1098changes.append(_("{interface}: {old} to {new}").format(interface=old_iface,old=old_sel.id,new=new_sel.id))10991100ifchanges:1101changes_text='\n\n'+_('The changes would be:')+'\n\n'+'\n'.join(changes)1102else:1103changes_text=''11041105ifused_impl:1106return_("{wanted} is selectable, but using it would produce a less optimal solution overall.").format(wanted=wanted)+changes_text1107else:1108return_("If {wanted} were the only option, the best available solution wouldn't use it.").format(wanted=wanted)+changes_text11091110DefaultSolver=SATSolver1111