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 /////////////////////////////////////////////////////////////////////////
52 { ///////////////////////////////////////////////////////////////////////
53 ///////////////////////////////////////////////////////////////////////
55 { /////////////////////////////////////////////////////////////////////
56 /////////////////////////////////////////////////////////////////////
58 { ///////////////////////////////////////////////////////////////////
60 //using namespace std;
62 //---------------------------------------------------------------------------
65 std::ostream & Resolver::dumpOn( std::ostream & os ) const
67 os << "<resolver>" << endl;
68 #define OUTS(t) os << " " << #t << ":\t" << t << endl;
72 OUTS( _onlyRequires );
73 OUTS( _solveSrcPackages );
74 OUTS( _cleandepsOnRemove );
75 OUTS( _ignoreAlreadyRecommended );
77 return os << "<resolver/>";
81 //---------------------------------------------------------------------------
83 Resolver::Resolver (const ResPool & pool)
86 , _poolchanged(_pool.serial() )
87 , _upgradeMode (false)
90 , _onlyRequires ( ZConfig::instance().solver_onlyRequires() )
91 , _solveSrcPackages ( false )
92 , _cleandepsOnRemove ( ZConfig::instance().solver_cleandepsOnRemove() )
93 , _ignoreAlreadyRecommended ( true )
96 sat::Pool satPool( sat::Pool::instance() );
97 _satResolver = new SATResolver(_pool, satPool.get());
101 Resolver::~Resolver()
106 //---------------------------------------------------------------------------
107 // forward flags too SATResolver
108 #define ZOLV_FLAG_TRIBOOL( ZSETTER, ZGETTER, ZVARNAME, ZVARDEFAULT ) \
109 void Resolver::ZSETTER( TriBool state_r ) \
110 { _satResolver->ZVARNAME = indeterminate(state_r) ? ZVARDEFAULT : bool(state_r); } \
111 bool Resolver::ZGETTER() const \
112 { return _satResolver->ZVARNAME; } \
114 // NOTE: ZVARDEFAULT must be in sync with SATResolver ctor
115 ZOLV_FLAG_TRIBOOL( setForceResolve, forceResolve, _allowuninstall, false )
117 ZOLV_FLAG_TRIBOOL( setAllowDowngrade, allowDowngrade, _allowdowngrade, false )
118 ZOLV_FLAG_TRIBOOL( setAllowNameChange, allowNameChange, _allownamechange, false )
119 ZOLV_FLAG_TRIBOOL( setAllowArchChange, allowArchChange, _allowarchchange, false )
120 ZOLV_FLAG_TRIBOOL( setAllowVendorChange, allowVendorChange, _allowvendorchange, ZConfig::instance().solver_allowVendorChange() )
122 ZOLV_FLAG_TRIBOOL( dupSetAllowDowngrade, dupAllowDowngrade, _dup_allowdowngrade, ZConfig::instance().solver_dupAllowDowngrade() )
123 ZOLV_FLAG_TRIBOOL( dupSetAllowNameChange, dupAllowNameChange, _dup_allownamechange, ZConfig::instance().solver_dupAllowNameChange() )
124 ZOLV_FLAG_TRIBOOL( dupSetAllowArchChange, dupAllowArchChange, _dup_allowarchchange, ZConfig::instance().solver_dupAllowArchChange() )
125 ZOLV_FLAG_TRIBOOL( dupSetAllowVendorChange, dupAllowVendorChange, _dup_allowvendorchange, ZConfig::instance().solver_dupAllowVendorChange() )
127 #undef ZOLV_FLAG_TRIBOOL
128 //---------------------------------------------------------------------------
130 void Resolver::setOnlyRequires( TriBool state_r )
132 _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
135 void Resolver::setCleandepsOnRemove( TriBool state_r )
137 _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
140 //---------------------------------------------------------------------------
142 ResPool Resolver::pool() const
145 void Resolver::reset( bool keepExtras )
150 _extra_requires.clear();
151 _extra_conflicts.clear();
154 _isInstalledBy.clear();
156 _satifiedByInstalled.clear();
157 _installedSatisfied.clear();
160 bool Resolver::doUpgrade()
162 // Setting Resolver to upgrade mode. SAT solver will do the update
164 return resolvePool();
167 void Resolver::doUpdate()
170 return _satResolver->doUpdate();
173 PoolItemList Resolver::problematicUpdateItems() const
174 { return _satResolver->problematicUpdateItems(); }
176 void Resolver::addExtraRequire( const Capability & capability )
177 { _extra_requires.insert (capability); }
179 void Resolver::removeExtraRequire( const Capability & capability )
180 { _extra_requires.erase (capability); }
182 void Resolver::addExtraConflict( const Capability & capability )
183 { _extra_conflicts.insert (capability); }
185 void Resolver::removeExtraConflict( const Capability & capability )
186 { _extra_conflicts.erase (capability); }
188 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
191 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
192 iter != _added_queue_items.end(); iter++) {
194 _added_queue_items.remove(*iter);
200 _removed_queue_items.push_back (item);
201 _removed_queue_items.unique ();
205 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
208 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
209 iter != _removed_queue_items.end(); iter++) {
211 _removed_queue_items.remove(*iter);
217 _added_queue_items.push_back (item);
218 _added_queue_items.unique ();
222 void Resolver::addWeak( const PoolItem & item )
223 { _addWeak.push_back( item ); }
225 //---------------------------------------------------------------------------
227 struct UndoTransact : public resfilter::PoolItemFilterFunctor
229 ResStatus::TransactByValue resStatus;
230 UndoTransact ( const ResStatus::TransactByValue &status)
234 bool operator()( PoolItem item ) // only transacts() items go here
236 item.status().resetTransact( resStatus );// clear any solver/establish transactions
242 struct DoTransact : public resfilter::PoolItemFilterFunctor
244 ResStatus::TransactByValue resStatus;
245 DoTransact ( const ResStatus::TransactByValue &status)
249 bool operator()( PoolItem item ) // only transacts() items go here
251 item.status().setTransact( true, resStatus );
257 bool Resolver::verifySystem()
259 UndoTransact resetting (ResStatus::APPL_HIGH);
261 DBG << "Resolver::verifySystem()" << endl;
265 invokeOnEach ( _pool.begin(), _pool.end(),
266 resfilter::ByTransact( ), // Resetting all transcations
267 functor::functorRef<bool,PoolItem>(resetting) );
269 return resolvePool();
273 //----------------------------------------------------------------------------
275 void Resolver::undo()
277 UndoTransact info(ResStatus::APPL_LOW);
278 MIL << "*** undo ***" << endl;
279 invokeOnEach ( _pool.begin(), _pool.end(),
280 resfilter::ByTransact( ), // collect transacts from Pool to resolver queue
281 functor::functorRef<bool,PoolItem>(info) );
282 // Regard dependencies of the item weak onl
285 // Additional QueueItems which has to be regarded by the solver
286 _removed_queue_items.clear();
287 _added_queue_items.clear();
292 void Resolver::solverInit()
294 // Solving with libsolv
295 static bool poolDumped = false;
296 MIL << "-------------- Calling SAT Solver -------------------" << endl;
297 if ( getenv("ZYPP_FULLLOG") ) {
298 Testcase testcase("/var/log/YaST2/autoTestcase");
300 testcase.createTestcase (*this, true, false); // dump pool
303 testcase.createTestcase (*this, false, false); // write control file only
307 _satResolver->setFixsystem ( isVerifyingMode() );
308 _satResolver->setIgnorealreadyrecommended ( ignoreAlreadyRecommended() );
309 _satResolver->setOnlyRequires ( onlyRequires() );
310 _satResolver->setUpdatesystem (_updateMode);
311 _satResolver->setSolveSrcPackages ( solveSrcPackages() );
312 _satResolver->setCleandepsOnRemove ( cleandepsOnRemove() );
314 _satResolver->setDistupgrade (_upgradeMode);
316 // may overwrite some settings
317 _satResolver->setDistupgrade_removeunsupported (false);
320 // Resetting additional solver information
321 _isInstalledBy.clear();
323 _satifiedByInstalled.clear();
324 _installedSatisfied.clear();
327 bool Resolver::resolvePool()
330 return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
333 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
337 // add/remove additional SolverQueueItems
338 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
339 iter != _removed_queue_items.end(); iter++) {
340 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
341 if ( (*iterQueue)->cmp(*iter) == 0) {
342 MIL << "remove from queue" << *iter;
343 queue.remove(*iterQueue);
349 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
350 iter != _added_queue_items.end(); iter++) {
352 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
353 if ( (*iterQueue)->cmp(*iter) == 0) {
359 MIL << "add to queue" << *iter;
360 queue.push_back(*iter);
364 // The application has to take care to write these solutions back to e.g. selectables in order
365 // give the user a chance for changing these decisions again.
366 _removed_queue_items.clear();
367 _added_queue_items.clear();
369 return _satResolver->resolveQueue(queue, _addWeak);
372 sat::Transaction Resolver::getTransaction()
374 // FIXME: That's an ugly way of pushing autoInstalled into the transaction.
375 sat::Transaction ret( sat::Transaction::loadFromPool );
376 ret.autoInstalled( _satResolver->autoInstalled() );
381 //----------------------------------------------------------------------------
382 // Getting more information about the solve results
384 ResolverProblemList Resolver::problems() const
386 MIL << "Resolver::problems()" << endl;
387 return _satResolver->problems();
390 void Resolver::applySolutions( const ProblemSolutionList & solutions )
392 for ( ProblemSolution_Ptr solution : solutions )
394 if ( ! applySolution( *solution ) )
399 bool Resolver::applySolution( const ProblemSolution & solution )
402 DBG << "apply solution " << solution << endl;
403 for ( SolutionAction_Ptr action : solution.actions() )
405 if ( ! action->execute( *this ) )
407 WAR << "apply solution action failed: " << action << endl;
415 //----------------------------------------------------------------------------
417 void Resolver::collectResolverInfo()
420 && _isInstalledBy.empty()
421 && _installs.empty()) {
424 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
426 for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
427 instIter != itemsToInstall.end(); instIter++) {
429 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
431 sat::WhatProvides possibleProviders(*capIt);
432 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
433 PoolItem provider = ResPool::instance().find( *iter );
435 // searching if this provider will already be installed
437 bool alreadySetForInstallation = false;
438 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
439 while (pos != _isInstalledBy.end()
440 && pos->first == provider
442 alreadySetForInstallation = true;
443 ItemCapKind capKind = pos->second;
444 if (capKind.item() == *instIter) found = true;
449 && provider.status().isToBeInstalled()) {
450 if (provider.status().isBySolver()) {
451 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
452 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
454 // no initial installation cause it has been set be e.g. user
455 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
456 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
458 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
459 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
462 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
463 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
464 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
466 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
467 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
472 if (!(_satResolver->onlyRequires())) {
474 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
476 sat::WhatProvides possibleProviders(*capIt);
477 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
478 PoolItem provider = ResPool::instance().find( *iter );
480 // searching if this provider will already be installed
482 bool alreadySetForInstallation = false;
483 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
484 while (pos != _isInstalledBy.end()
485 && pos->first == provider
487 alreadySetForInstallation = true;
488 ItemCapKind capKind = pos->second;
489 if (capKind.item() == *instIter) found = true;
494 && provider.status().isToBeInstalled()) {
495 if (provider.status().isBySolver()) {
496 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
497 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
499 // no initial installation cause it has been set be e.g. user
500 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
501 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
503 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
504 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
507 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
508 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
509 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
511 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
512 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
518 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
520 sat::WhatProvides possibleProviders(*capIt);
521 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
522 PoolItem provider = ResPool::instance().find( *iter );
523 // searching if this item will already be installed
525 bool alreadySetForInstallation = false;
526 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
527 while (pos != _isInstalledBy.end()
528 && pos->first == *instIter
530 alreadySetForInstallation = true;
531 ItemCapKind capKind = pos->second;
532 if (capKind.item() == provider) found = true;
537 && instIter->status().isToBeInstalled()) {
538 if (instIter->status().isBySolver()) {
539 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
540 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
542 // no initial installation cause it has been set be e.g. user
543 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
544 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
546 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
547 _installs.insert (make_pair( provider, capKindisInstalledBy));
550 if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
551 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
552 _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
554 ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
555 _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
565 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
568 collectResolverInfo();
570 for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
571 ItemCapKind info = iter->second;
572 PoolItem iterItem = iter->first;
573 if (iterItem == item) {
578 iter = _isInstalledBy.end();
584 ItemCapKindList Resolver::installs( const PoolItem & item )
587 collectResolverInfo();
589 for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
590 ItemCapKind info = iter->second;
591 PoolItem iterItem = iter->first;
592 if (iterItem == item) {
597 iter = _installs.end();
603 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
606 collectResolverInfo();
608 for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
609 ItemCapKind info = iter->second;
610 PoolItem iterItem = iter->first;
611 if (iterItem == item) {
616 iter = _satifiedByInstalled.end();
622 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
625 collectResolverInfo();
627 for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
628 ItemCapKind info = iter->second;
629 PoolItem iterItem = iter->first;
630 if (iterItem == item) {
635 iter = _installedSatisfied.end();
642 ///////////////////////////////////////////////////////////////////
643 };// namespace detail
644 /////////////////////////////////////////////////////////////////////
645 /////////////////////////////////////////////////////////////////////
646 };// namespace solver
647 ///////////////////////////////////////////////////////////////////////
648 ///////////////////////////////////////////////////////////////////////
650 /////////////////////////////////////////////////////////////////////////