1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
4 * Copyright (C) 2000-2002 Ximian, Inc.
5 * Copyright (C) 2005 SUSE Linux Products GmbH
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License,
9 * version 2, as published by the Free Software Foundation.
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 #include <boost/static_assert.hpp>
23 #define ZYPP_USE_RESOLVER_INTERNALS
25 #include "zypp/solver/detail/Resolver.h"
26 #include "zypp/solver/detail/Testcase.h"
27 #include "zypp/solver/detail/SATResolver.h"
28 #include "zypp/solver/detail/ItemCapKind.h"
29 #include "zypp/solver/detail/SolutionAction.h"
30 #include "zypp/solver/detail/SolverQueueItem.h"
32 #include "zypp/Capabilities.h"
33 #include "zypp/ZConfig.h"
34 #include "zypp/base/Logger.h"
35 #include "zypp/base/String.h"
36 #include "zypp/base/Gettext.h"
37 #include "zypp/base/Algorithm.h"
38 #include "zypp/ResPool.h"
39 #include "zypp/ResFilters.h"
40 #include "zypp/sat/Pool.h"
41 #include "zypp/sat/Solvable.h"
42 #include "zypp/sat/Transaction.h"
43 #include "zypp/ResolverProblem.h"
45 #define MAXSOLVERRUNS 5
50 #undef ZYPP_BASE_LOGGER_LOGGROUP
51 #define ZYPP_BASE_LOGGER_LOGGROUP "zypp::solver"
53 /////////////////////////////////////////////////////////////////////////
55 { ///////////////////////////////////////////////////////////////////////
56 ///////////////////////////////////////////////////////////////////////
58 { /////////////////////////////////////////////////////////////////////
59 /////////////////////////////////////////////////////////////////////
61 { ///////////////////////////////////////////////////////////////////
63 //using namespace std;
65 //---------------------------------------------------------------------------
68 std::ostream & Resolver::dumpOn( std::ostream & os ) const
70 os << "<resolver>" << endl;
71 #define OUTS(t) os << " " << #t << ":\t" << t << endl;
75 OUTS( _onlyRequires );
76 OUTS( _solveSrcPackages );
77 OUTS( _cleandepsOnRemove );
78 OUTS( _ignoreAlreadyRecommended );
81 return os << "<resolver/>";
85 //---------------------------------------------------------------------------
87 Resolver::Resolver (const ResPool & pool)
90 , _poolchanged(_pool.serial() )
91 , _upgradeMode (false)
94 , _onlyRequires ( ZConfig::instance().solver_onlyRequires() )
95 , _solveSrcPackages ( false )
96 , _cleandepsOnRemove ( ZConfig::instance().solver_cleandepsOnRemove() )
97 , _ignoreAlreadyRecommended ( true )
98 // _inr defaults to ResolverNamespaces()
101 sat::Pool satPool( sat::Pool::instance() );
102 _satResolver = new SATResolver(_pool, satPool.get());
106 Resolver::~Resolver()
111 //---------------------------------------------------------------------------
112 // forward flags too SATResolver
113 #define ZOLV_FLAG_TRIBOOL( ZSETTER, ZGETTER, ZVARNAME, ZVARDEFAULT ) \
114 void Resolver::ZSETTER( TriBool state_r ) \
115 { _satResolver->ZVARNAME = indeterminate(state_r) ? ZVARDEFAULT : bool(state_r); } \
116 bool Resolver::ZGETTER() const \
117 { return _satResolver->ZVARNAME; } \
119 // NOTE: ZVARDEFAULT must be in sync with SATResolver ctor
120 ZOLV_FLAG_TRIBOOL( setForceResolve, forceResolve, _allowuninstall, false )
122 ZOLV_FLAG_TRIBOOL( setAllowDowngrade, allowDowngrade, _allowdowngrade, false )
123 ZOLV_FLAG_TRIBOOL( setAllowNameChange, allowNameChange, _allownamechange, true ) // bsc#1071466
124 ZOLV_FLAG_TRIBOOL( setAllowArchChange, allowArchChange, _allowarchchange, false )
125 ZOLV_FLAG_TRIBOOL( setAllowVendorChange, allowVendorChange, _allowvendorchange, ZConfig::instance().solver_allowVendorChange() )
127 ZOLV_FLAG_TRIBOOL( dupSetAllowDowngrade, dupAllowDowngrade, _dup_allowdowngrade, ZConfig::instance().solver_dupAllowDowngrade() )
128 ZOLV_FLAG_TRIBOOL( dupSetAllowNameChange, dupAllowNameChange, _dup_allownamechange, ZConfig::instance().solver_dupAllowNameChange() )
129 ZOLV_FLAG_TRIBOOL( dupSetAllowArchChange, dupAllowArchChange, _dup_allowarchchange, ZConfig::instance().solver_dupAllowArchChange() )
130 ZOLV_FLAG_TRIBOOL( dupSetAllowVendorChange, dupAllowVendorChange, _dup_allowvendorchange, ZConfig::instance().solver_dupAllowVendorChange() )
132 #undef ZOLV_FLAG_TRIBOOL
133 //---------------------------------------------------------------------------
135 void Resolver::setOnlyRequires( TriBool state_r )
137 _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
140 void Resolver::setCleandepsOnRemove( TriBool state_r )
142 _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
145 //---------------------------------------------------------------------------
147 ResPool Resolver::pool() const
150 void Resolver::reset( bool keepExtras )
155 _extra_requires.clear();
156 _extra_conflicts.clear();
159 _isInstalledBy.clear();
161 _satifiedByInstalled.clear();
162 _installedSatisfied.clear();
165 bool Resolver::doUpgrade()
167 // Setting Resolver to upgrade mode. SAT solver will do the update
169 return resolvePool();
172 void Resolver::doUpdate()
175 return _satResolver->doUpdate();
178 PoolItemList Resolver::problematicUpdateItems() const
179 { return _satResolver->problematicUpdateItems(); }
181 void Resolver::addExtraRequire( const Capability & capability )
182 { _extra_requires.insert (capability); }
184 void Resolver::removeExtraRequire( const Capability & capability )
185 { _extra_requires.erase (capability); }
187 void Resolver::addExtraConflict( const Capability & capability )
188 { _extra_conflicts.insert (capability); }
190 void Resolver::removeExtraConflict( const Capability & capability )
191 { _extra_conflicts.erase (capability); }
193 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
196 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
197 iter != _added_queue_items.end(); iter++) {
199 _added_queue_items.remove(*iter);
205 _removed_queue_items.push_back (item);
206 _removed_queue_items.unique ();
210 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
213 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
214 iter != _removed_queue_items.end(); iter++) {
216 _removed_queue_items.remove(*iter);
222 _added_queue_items.push_back (item);
223 _added_queue_items.unique ();
227 void Resolver::addWeak( const PoolItem & item )
228 { _addWeak.push_back( item ); }
230 //---------------------------------------------------------------------------
232 struct UndoTransact : public resfilter::PoolItemFilterFunctor
234 ResStatus::TransactByValue resStatus;
235 UndoTransact ( const ResStatus::TransactByValue &status)
239 bool operator()( PoolItem item ) // only transacts() items go here
241 item.status().resetTransact( resStatus );// clear any solver/establish transactions
247 struct DoTransact : public resfilter::PoolItemFilterFunctor
249 ResStatus::TransactByValue resStatus;
250 DoTransact ( const ResStatus::TransactByValue &status)
254 bool operator()( PoolItem item ) // only transacts() items go here
256 item.status().setTransact( true, resStatus );
262 bool Resolver::verifySystem()
264 UndoTransact resetting (ResStatus::APPL_HIGH);
266 DBG << "Resolver::verifySystem()" << endl;
270 invokeOnEach ( _pool.begin(), _pool.end(),
271 resfilter::ByTransact( ), // Resetting all transcations
272 functor::functorRef<bool,PoolItem>(resetting) );
274 return resolvePool();
278 //----------------------------------------------------------------------------
280 void Resolver::undo()
282 UndoTransact info(ResStatus::APPL_LOW);
283 MIL << "*** undo ***" << endl;
284 invokeOnEach ( _pool.begin(), _pool.end(),
285 resfilter::ByTransact( ), // collect transacts from Pool to resolver queue
286 functor::functorRef<bool,PoolItem>(info) );
287 // Regard dependencies of the item weak onl
290 // Additional QueueItems which has to be regarded by the solver
291 _removed_queue_items.clear();
292 _added_queue_items.clear();
297 void Resolver::solverInit()
299 // Solving with libsolv
300 static bool poolDumped = false;
301 MIL << "-------------- Calling SAT Solver -------------------" << endl;
302 if ( getenv("ZYPP_FULLLOG") ) {
303 Testcase testcase("/var/log/YaST2/autoTestcase");
305 testcase.createTestcase (*this, true, false); // dump pool
308 testcase.createTestcase (*this, false, false); // write control file only
312 _satResolver->setFixsystem ( isVerifyingMode() );
313 _satResolver->setIgnorealreadyrecommended ( ignoreAlreadyRecommended() );
314 _satResolver->setInr ( inr() );
315 _satResolver->setOnlyRequires ( onlyRequires() );
316 _satResolver->setUpdatesystem (_updateMode);
317 _satResolver->setSolveSrcPackages ( solveSrcPackages() );
318 _satResolver->setCleandepsOnRemove ( cleandepsOnRemove() );
320 _satResolver->setDistupgrade (_upgradeMode);
322 // may overwrite some settings
323 _satResolver->setDistupgrade_removeunsupported (false);
326 // Resetting additional solver information
327 _isInstalledBy.clear();
329 _satifiedByInstalled.clear();
330 _installedSatisfied.clear();
333 bool Resolver::resolvePool()
336 return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
339 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
343 // add/remove additional SolverQueueItems
344 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
345 iter != _removed_queue_items.end(); iter++) {
346 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
347 if ( (*iterQueue)->cmp(*iter) == 0) {
348 MIL << "remove from queue" << *iter;
349 queue.remove(*iterQueue);
355 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
356 iter != _added_queue_items.end(); iter++) {
358 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
359 if ( (*iterQueue)->cmp(*iter) == 0) {
365 MIL << "add to queue" << *iter;
366 queue.push_back(*iter);
370 // The application has to take care to write these solutions back to e.g. selectables in order
371 // give the user a chance for changing these decisions again.
372 _removed_queue_items.clear();
373 _added_queue_items.clear();
375 return _satResolver->resolveQueue(queue, _addWeak);
378 sat::Transaction Resolver::getTransaction()
380 // FIXME: That's an ugly way of pushing autoInstalled into the transaction.
381 sat::Transaction ret( sat::Transaction::loadFromPool );
382 ret.autoInstalled( _satResolver->autoInstalled() );
387 //----------------------------------------------------------------------------
388 // Getting more information about the solve results
390 ResolverProblemList Resolver::problems() const
392 MIL << "Resolver::problems()" << endl;
393 return _satResolver->problems();
396 void Resolver::applySolutions( const ProblemSolutionList & solutions )
398 for ( ProblemSolution_Ptr solution : solutions )
400 if ( ! applySolution( *solution ) )
405 bool Resolver::applySolution( const ProblemSolution & solution )
408 DBG << "apply solution " << solution << endl;
409 for ( SolutionAction_Ptr action : solution.actions() )
411 if ( ! action->execute( *this ) )
413 WAR << "apply solution action failed: " << action << endl;
421 //----------------------------------------------------------------------------
423 void Resolver::collectResolverInfo()
426 && _isInstalledBy.empty()
427 && _installs.empty()) {
430 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
432 for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
433 instIter != itemsToInstall.end(); instIter++) {
435 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
437 sat::WhatProvides possibleProviders(*capIt);
438 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
439 PoolItem provider = ResPool::instance().find( *iter );
441 // searching if this provider will already be installed
443 bool alreadySetForInstallation = false;
444 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
445 while (pos != _isInstalledBy.end()
446 && pos->first == provider
448 alreadySetForInstallation = true;
449 ItemCapKind capKind = pos->second;
450 if (capKind.item() == *instIter) found = true;
455 && provider.status().isToBeInstalled()) {
456 if (provider.status().isBySolver()) {
457 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
458 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
460 // no initial installation cause it has been set be e.g. user
461 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
462 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
464 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
465 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
468 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
469 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
470 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
472 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
473 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
478 if (!(_satResolver->onlyRequires())) {
480 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
482 sat::WhatProvides possibleProviders(*capIt);
483 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
484 PoolItem provider = ResPool::instance().find( *iter );
486 // searching if this provider will already be installed
488 bool alreadySetForInstallation = false;
489 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
490 while (pos != _isInstalledBy.end()
491 && pos->first == provider
493 alreadySetForInstallation = true;
494 ItemCapKind capKind = pos->second;
495 if (capKind.item() == *instIter) found = true;
500 && provider.status().isToBeInstalled()) {
501 if (provider.status().isBySolver()) {
502 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
503 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
505 // no initial installation cause it has been set be e.g. user
506 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
507 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
509 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
510 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
513 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
514 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
515 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
517 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
518 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
524 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
526 sat::WhatProvides possibleProviders(*capIt);
527 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
528 PoolItem provider = ResPool::instance().find( *iter );
529 // searching if this item will already be installed
531 bool alreadySetForInstallation = false;
532 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
533 while (pos != _isInstalledBy.end()
534 && pos->first == *instIter
536 alreadySetForInstallation = true;
537 ItemCapKind capKind = pos->second;
538 if (capKind.item() == provider) found = true;
543 && instIter->status().isToBeInstalled()) {
544 if (instIter->status().isBySolver()) {
545 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
546 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
548 // no initial installation cause it has been set be e.g. user
549 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
550 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
552 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
553 _installs.insert (make_pair( provider, capKindisInstalledBy));
556 if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
557 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
558 _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
560 ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
561 _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
571 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
574 collectResolverInfo();
576 for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
577 ItemCapKind info = iter->second;
578 PoolItem iterItem = iter->first;
579 if (iterItem == item) {
584 iter = _isInstalledBy.end();
590 ItemCapKindList Resolver::installs( const PoolItem & item )
593 collectResolverInfo();
595 for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
596 ItemCapKind info = iter->second;
597 PoolItem iterItem = iter->first;
598 if (iterItem == item) {
603 iter = _installs.end();
609 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
612 collectResolverInfo();
614 for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
615 ItemCapKind info = iter->second;
616 PoolItem iterItem = iter->first;
617 if (iterItem == item) {
622 iter = _satifiedByInstalled.end();
628 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
631 collectResolverInfo();
633 for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
634 ItemCapKind info = iter->second;
635 PoolItem iterItem = iter->first;
636 if (iterItem == item) {
641 iter = _installedSatisfied.end();
648 ///////////////////////////////////////////////////////////////////
649 };// namespace detail
650 /////////////////////////////////////////////////////////////////////
651 /////////////////////////////////////////////////////////////////////
652 };// namespace solver
653 ///////////////////////////////////////////////////////////////////////
654 ///////////////////////////////////////////////////////////////////////
656 /////////////////////////////////////////////////////////////////////////