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/base/LogTools.h>
26 #include <zypp/base/Algorithm.h>
28 #include <zypp/solver/detail/Resolver.h>
29 #include <zypp/solver/detail/Testcase.h>
30 #include <zypp/solver/detail/SATResolver.h>
31 #include <zypp/solver/detail/ItemCapKind.h>
32 #include <zypp/solver/detail/SolutionAction.h>
33 #include <zypp/solver/detail/SolverQueueItem.h>
35 #include <zypp/ZConfig.h>
36 #include <zypp/sat/Transaction.h>
38 #define MAXSOLVERRUNS 5
43 #undef ZYPP_BASE_LOGGER_LOGGROUP
44 #define ZYPP_BASE_LOGGER_LOGGROUP "zypp::solver"
46 /////////////////////////////////////////////////////////////////////////
48 { ///////////////////////////////////////////////////////////////////////
49 ///////////////////////////////////////////////////////////////////////
51 { /////////////////////////////////////////////////////////////////////
52 /////////////////////////////////////////////////////////////////////
54 { ///////////////////////////////////////////////////////////////////
57 //---------------------------------------------------------------------------
60 std::ostream & Resolver::dumpOn( std::ostream & os ) const
62 os << "<resolver>" << endl;
63 #define OUTS(t) os << " " << #t << ":\t" << t << endl;
67 OUTS( _onlyRequires );
68 OUTS( _solveSrcPackages );
69 OUTS( _cleandepsOnRemove );
70 OUTS( _ignoreAlreadyRecommended );
72 return os << "<resolver/>";
76 //---------------------------------------------------------------------------
78 Resolver::Resolver (const ResPool & pool)
81 , _poolchanged(_pool.serial() )
82 , _upgradeMode (false)
85 , _onlyRequires ( ZConfig::instance().solver_onlyRequires() )
86 , _solveSrcPackages ( false )
87 , _cleandepsOnRemove ( ZConfig::instance().solver_cleandepsOnRemove() )
88 , _ignoreAlreadyRecommended ( true )
90 sat::Pool satPool( sat::Pool::instance() );
91 _satResolver = new SATResolver(_pool, satPool.get());
100 //---------------------------------------------------------------------------
101 // forward flags too SATResolver
103 void Resolver::setFocus( ResolverFocus focus_r ) { _satResolver->_focus = ( focus_r == ResolverFocus::Default ) ? ZConfig::instance().solver_focus() : focus_r; }
104 ResolverFocus Resolver::focus() const { return _satResolver->_focus; }
106 #define ZOLV_FLAG_TRIBOOL( ZSETTER, ZGETTER, ZVARNAME, ZVARDEFAULT ) \
107 void Resolver::ZSETTER( TriBool state_r ) \
108 { _satResolver->ZVARNAME = indeterminate(state_r) ? ZVARDEFAULT : bool(state_r); } \
109 bool Resolver::ZGETTER() const \
110 { return _satResolver->ZVARNAME; } \
112 // NOTE: ZVARDEFAULT must be in sync with SATResolver ctor
113 ZOLV_FLAG_TRIBOOL( setForceResolve, forceResolve, _allowuninstall, false )
115 ZOLV_FLAG_TRIBOOL( setAllowDowngrade, allowDowngrade, _allowdowngrade, false )
116 ZOLV_FLAG_TRIBOOL( setAllowNameChange, allowNameChange, _allownamechange, true ) // bsc#1071466
117 ZOLV_FLAG_TRIBOOL( setAllowArchChange, allowArchChange, _allowarchchange, false )
118 ZOLV_FLAG_TRIBOOL( setAllowVendorChange, allowVendorChange, _allowvendorchange, ZConfig::instance().solver_allowVendorChange() )
120 ZOLV_FLAG_TRIBOOL( dupSetAllowDowngrade, dupAllowDowngrade, _dup_allowdowngrade, ZConfig::instance().solver_dupAllowDowngrade() )
121 ZOLV_FLAG_TRIBOOL( dupSetAllowNameChange, dupAllowNameChange, _dup_allownamechange, ZConfig::instance().solver_dupAllowNameChange() )
122 ZOLV_FLAG_TRIBOOL( dupSetAllowArchChange, dupAllowArchChange, _dup_allowarchchange, ZConfig::instance().solver_dupAllowArchChange() )
123 ZOLV_FLAG_TRIBOOL( dupSetAllowVendorChange, dupAllowVendorChange, _dup_allowvendorchange, ZConfig::instance().solver_dupAllowVendorChange() )
125 #undef ZOLV_FLAG_TRIBOOL
126 //---------------------------------------------------------------------------
128 void Resolver::setOnlyRequires( TriBool state_r )
130 _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
133 void Resolver::setCleandepsOnRemove( TriBool state_r )
135 _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
138 //---------------------------------------------------------------------------
140 ResPool Resolver::pool() const
143 void Resolver::reset( bool keepExtras )
148 _extra_requires.clear();
149 _extra_conflicts.clear();
152 _isInstalledBy.clear();
154 _satifiedByInstalled.clear();
155 _installedSatisfied.clear();
158 bool Resolver::doUpgrade()
160 // Setting Resolver to upgrade mode. SAT solver will do the update
162 return resolvePool();
165 void Resolver::doUpdate()
168 return _satResolver->doUpdate();
171 PoolItemList Resolver::problematicUpdateItems() const
172 { return _satResolver->problematicUpdateItems(); }
174 void Resolver::addExtraRequire( const Capability & capability )
175 { _extra_requires.insert (capability); }
177 void Resolver::removeExtraRequire( const Capability & capability )
178 { _extra_requires.erase (capability); }
180 void Resolver::addExtraConflict( const Capability & capability )
181 { _extra_conflicts.insert (capability); }
183 void Resolver::removeExtraConflict( const Capability & capability )
184 { _extra_conflicts.erase (capability); }
186 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
189 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
190 iter != _added_queue_items.end(); iter++) {
192 _added_queue_items.remove(*iter);
198 _removed_queue_items.push_back (item);
199 _removed_queue_items.unique ();
203 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
206 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
207 iter != _removed_queue_items.end(); iter++) {
209 _removed_queue_items.remove(*iter);
215 _added_queue_items.push_back (item);
216 _added_queue_items.unique ();
220 void Resolver::addWeak( const PoolItem & item )
221 { _addWeak.push_back( item ); }
223 //---------------------------------------------------------------------------
225 struct UndoTransact : public resfilter::PoolItemFilterFunctor
227 ResStatus::TransactByValue resStatus;
228 UndoTransact ( const ResStatus::TransactByValue &status)
232 bool operator()( PoolItem item ) // only transacts() items go here
234 item.status().resetTransact( resStatus );// clear any solver/establish transactions
240 struct DoTransact : public resfilter::PoolItemFilterFunctor
242 ResStatus::TransactByValue resStatus;
243 DoTransact ( const ResStatus::TransactByValue &status)
247 bool operator()( PoolItem item ) // only transacts() items go here
249 item.status().setTransact( true, resStatus );
255 bool Resolver::verifySystem()
257 UndoTransact resetting (ResStatus::APPL_HIGH);
259 DBG << "Resolver::verifySystem()" << endl;
263 invokeOnEach ( _pool.begin(), _pool.end(),
264 resfilter::ByTransact( ), // Resetting all transcations
265 functor::functorRef<bool,PoolItem>(resetting) );
267 return resolvePool();
271 //----------------------------------------------------------------------------
273 void Resolver::undo()
275 UndoTransact info(ResStatus::APPL_LOW);
276 MIL << "*** undo ***" << endl;
277 invokeOnEach ( _pool.begin(), _pool.end(),
278 resfilter::ByTransact( ), // collect transacts from Pool to resolver queue
279 functor::functorRef<bool,PoolItem>(info) );
280 // Regard dependencies of the item weak onl
283 // Additional QueueItems which has to be regarded by the solver
284 _removed_queue_items.clear();
285 _added_queue_items.clear();
290 void Resolver::solverInit()
292 // Solving with libsolv
293 static bool poolDumped = false;
294 MIL << "-------------- Calling SAT Solver -------------------" << endl;
295 if ( getenv("ZYPP_FULLLOG") ) {
296 Testcase testcase("/var/log/YaST2/autoTestcase");
298 testcase.createTestcase (*this, true, false); // dump pool
301 testcase.createTestcase (*this, false, false); // write control file only
305 _satResolver->setFixsystem ( isVerifyingMode() );
306 _satResolver->setIgnorealreadyrecommended ( ignoreAlreadyRecommended() );
307 _satResolver->setOnlyRequires ( onlyRequires() );
308 _satResolver->setUpdatesystem (_updateMode);
309 _satResolver->setSolveSrcPackages ( solveSrcPackages() );
310 _satResolver->setCleandepsOnRemove ( cleandepsOnRemove() );
312 _satResolver->setDistupgrade (_upgradeMode);
314 // may overwrite some settings
315 _satResolver->setDistupgrade_removeunsupported (false);
318 // Resetting additional solver information
319 _isInstalledBy.clear();
321 _satifiedByInstalled.clear();
322 _installedSatisfied.clear();
325 bool Resolver::resolvePool()
328 return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
331 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
335 // add/remove additional SolverQueueItems
336 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
337 iter != _removed_queue_items.end(); iter++) {
338 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
339 if ( (*iterQueue)->cmp(*iter) == 0) {
340 MIL << "remove from queue" << *iter;
341 queue.remove(*iterQueue);
347 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
348 iter != _added_queue_items.end(); iter++) {
350 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
351 if ( (*iterQueue)->cmp(*iter) == 0) {
357 MIL << "add to queue" << *iter;
358 queue.push_back(*iter);
362 // The application has to take care to write these solutions back to e.g. selectables in order
363 // give the user a chance for changing these decisions again.
364 _removed_queue_items.clear();
365 _added_queue_items.clear();
367 return _satResolver->resolveQueue(queue, _addWeak);
370 sat::Transaction Resolver::getTransaction()
372 // FIXME: That's an ugly way of pushing autoInstalled into the transaction.
373 sat::Transaction ret( sat::Transaction::loadFromPool );
374 ret.autoInstalled( _satResolver->autoInstalled() );
379 //----------------------------------------------------------------------------
380 // Getting more information about the solve results
382 ResolverProblemList Resolver::problems() const
384 MIL << "Resolver::problems()" << endl;
385 return _satResolver->problems();
388 void Resolver::applySolutions( const ProblemSolutionList & solutions )
390 for ( ProblemSolution_Ptr solution : solutions )
392 if ( ! applySolution( *solution ) )
397 bool Resolver::applySolution( const ProblemSolution & solution )
400 DBG << "apply solution " << solution << endl;
401 for ( SolutionAction_Ptr action : solution.actions() )
403 if ( ! action->execute( *this ) )
405 WAR << "apply solution action failed: " << action << endl;
413 //----------------------------------------------------------------------------
415 void Resolver::collectResolverInfo()
418 && _isInstalledBy.empty()
419 && _installs.empty()) {
422 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
424 for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
425 instIter != itemsToInstall.end(); instIter++) {
427 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
429 sat::WhatProvides possibleProviders(*capIt);
430 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
431 PoolItem provider = ResPool::instance().find( *iter );
433 // searching if this provider will already be installed
435 bool alreadySetForInstallation = false;
436 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
437 while (pos != _isInstalledBy.end()
438 && pos->first == provider
440 alreadySetForInstallation = true;
441 ItemCapKind capKind = pos->second;
442 if (capKind.item() == *instIter) found = true;
447 && provider.status().isToBeInstalled()) {
448 if (provider.status().isBySolver()) {
449 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
450 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
452 // no initial installation cause it has been set be e.g. user
453 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
454 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
456 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
457 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
460 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
461 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
462 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
464 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
465 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
470 if (!(_satResolver->onlyRequires())) {
472 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
474 sat::WhatProvides possibleProviders(*capIt);
475 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
476 PoolItem provider = ResPool::instance().find( *iter );
478 // searching if this provider will already be installed
480 bool alreadySetForInstallation = false;
481 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
482 while (pos != _isInstalledBy.end()
483 && pos->first == provider
485 alreadySetForInstallation = true;
486 ItemCapKind capKind = pos->second;
487 if (capKind.item() == *instIter) found = true;
492 && provider.status().isToBeInstalled()) {
493 if (provider.status().isBySolver()) {
494 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
495 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
497 // no initial installation cause it has been set be e.g. user
498 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
499 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
501 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
502 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
505 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
506 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
507 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
509 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
510 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
516 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
518 sat::WhatProvides possibleProviders(*capIt);
519 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
520 PoolItem provider = ResPool::instance().find( *iter );
521 // searching if this item will already be installed
523 bool alreadySetForInstallation = false;
524 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
525 while (pos != _isInstalledBy.end()
526 && pos->first == *instIter
528 alreadySetForInstallation = true;
529 ItemCapKind capKind = pos->second;
530 if (capKind.item() == provider) found = true;
535 && instIter->status().isToBeInstalled()) {
536 if (instIter->status().isBySolver()) {
537 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
538 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
540 // no initial installation cause it has been set be e.g. user
541 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
542 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
544 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
545 _installs.insert (make_pair( provider, capKindisInstalledBy));
548 if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
549 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
550 _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
552 ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
553 _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
563 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
566 collectResolverInfo();
568 for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
569 ItemCapKind info = iter->second;
570 PoolItem iterItem = iter->first;
571 if (iterItem == item) {
576 iter = _isInstalledBy.end();
582 ItemCapKindList Resolver::installs( const PoolItem & item )
585 collectResolverInfo();
587 for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
588 ItemCapKind info = iter->second;
589 PoolItem iterItem = iter->first;
590 if (iterItem == item) {
595 iter = _installs.end();
601 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
604 collectResolverInfo();
606 for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
607 ItemCapKind info = iter->second;
608 PoolItem iterItem = iter->first;
609 if (iterItem == item) {
614 iter = _satifiedByInstalled.end();
620 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
623 collectResolverInfo();
625 for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
626 ItemCapKind info = iter->second;
627 PoolItem iterItem = iter->first;
628 if (iterItem == item) {
633 iter = _installedSatisfied.end();
640 ///////////////////////////////////////////////////////////////////
641 };// namespace detail
642 /////////////////////////////////////////////////////////////////////
643 /////////////////////////////////////////////////////////////////////
644 };// namespace solver
645 ///////////////////////////////////////////////////////////////////////
646 ///////////////////////////////////////////////////////////////////////
648 /////////////////////////////////////////////////////////////////////////