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 #include "zypp/solver/detail/Resolver.h"
24 #include "zypp/solver/detail/Helper.h"
25 #include "zypp/solver/detail/Testcase.h"
26 #include "zypp/solver/detail/SATResolver.h"
28 #include "zypp/Capabilities.h"
29 #include "zypp/ZConfig.h"
30 #include "zypp/base/Logger.h"
31 #include "zypp/base/String.h"
32 #include "zypp/base/Gettext.h"
33 #include "zypp/base/Algorithm.h"
34 #include "zypp/ResPool.h"
35 #include "zypp/ResFilters.h"
36 #include "zypp/sat/Pool.h"
37 #include "zypp/sat/Solvable.h"
38 #include "zypp/sat/Transaction.h"
39 #include "zypp/ResolverProblem.h"
41 #define MAXSOLVERRUNS 5
43 /////////////////////////////////////////////////////////////////////////
45 { ///////////////////////////////////////////////////////////////////////
46 ///////////////////////////////////////////////////////////////////////
48 { /////////////////////////////////////////////////////////////////////
49 /////////////////////////////////////////////////////////////////////
51 { ///////////////////////////////////////////////////////////////////
55 IMPL_PTR_TYPE(Resolver);
58 //---------------------------------------------------------------------------
61 std::ostream & Resolver::dumpOn( std::ostream & os ) const
63 os << "<resolver>" << endl;
64 #define OUTS(t) os << " " << #t << ":\t" << t << endl;
65 OUTS( _forceResolve );
69 OUTS( _onlyRequires );
70 OUTS( _allowVendorChange );
71 OUTS( _solveSrcPackages );
72 OUTS( _cleandepsOnRemove );
73 OUTS( _ignoreAlreadyRecommended );
75 return os << "<resolver/>";
79 //---------------------------------------------------------------------------
81 Resolver::Resolver (const ResPool & pool)
84 , _poolchanged(_pool.serial() )
85 , _forceResolve (false)
86 , _upgradeMode (false)
89 , _onlyRequires ( ZConfig::instance().solver_onlyRequires() )
90 , _allowVendorChange ( ZConfig::instance().solver_allowVendorChange() )
91 , _solveSrcPackages ( false )
92 , _cleandepsOnRemove ( ZConfig::instance().solver_cleandepsOnRemove() )
93 , _ignoreAlreadyRecommended ( false )
96 sat::Pool satPool( sat::Pool::instance() );
97 _satResolver = new SATResolver(_pool, satPool.get());
101 Resolver::~Resolver()
106 //---------------------------------------------------------------------------
108 void Resolver::setAllowVendorChange( TriBool state_r )
110 _allowVendorChange = indeterminate(state_r) ? ZConfig::instance().solver_allowVendorChange() : bool(state_r);
113 void Resolver::setOnlyRequires( TriBool state_r )
115 _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
118 void Resolver::setCleandepsOnRemove( TriBool state_r )
120 _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
123 //---------------------------------------------------------------------------
125 ResPool Resolver::pool() const
128 void Resolver::reset( bool keepExtras )
133 _extra_requires.clear();
134 _extra_conflicts.clear();
137 _isInstalledBy.clear();
139 _satifiedByInstalled.clear();
140 _installedSatisfied.clear();
143 bool Resolver::doUpgrade()
145 // Setting Resolver to upgrade mode. SAT solver will do the update
147 return resolvePool();
150 void Resolver::doUpdate()
153 return _satResolver->doUpdate();
156 PoolItemList Resolver::problematicUpdateItems() const
157 { return _satResolver->problematicUpdateItems(); }
159 void Resolver::addExtraRequire( const Capability & capability )
160 { _extra_requires.insert (capability); }
162 void Resolver::removeExtraRequire( const Capability & capability )
163 { _extra_requires.erase (capability); }
165 void Resolver::addExtraConflict( const Capability & capability )
166 { _extra_conflicts.insert (capability); }
168 void Resolver::removeExtraConflict( const Capability & capability )
169 { _extra_conflicts.erase (capability); }
171 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
174 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
175 iter != _added_queue_items.end(); iter++) {
177 _added_queue_items.remove(*iter);
183 _removed_queue_items.push_back (item);
184 _removed_queue_items.unique ();
188 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
191 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
192 iter != _removed_queue_items.end(); iter++) {
194 _removed_queue_items.remove(*iter);
200 _added_queue_items.push_back (item);
201 _added_queue_items.unique ();
205 void Resolver::addWeak( const PoolItem & item )
206 { _addWeak.push_back( item ); }
208 //---------------------------------------------------------------------------
210 struct UndoTransact : public resfilter::PoolItemFilterFunctor
212 ResStatus::TransactByValue resStatus;
213 UndoTransact ( const ResStatus::TransactByValue &status)
217 bool operator()( PoolItem item ) // only transacts() items go here
219 item.status().resetTransact( resStatus );// clear any solver/establish transactions
225 struct DoTransact : public resfilter::PoolItemFilterFunctor
227 ResStatus::TransactByValue resStatus;
228 DoTransact ( const ResStatus::TransactByValue &status)
232 bool operator()( PoolItem item ) // only transacts() items go here
234 item.status().setTransact( true, resStatus );
240 bool Resolver::verifySystem()
242 UndoTransact resetting (ResStatus::APPL_HIGH);
244 _DEBUG ("Resolver::verifySystem() ");
248 invokeOnEach ( _pool.begin(), _pool.end(),
249 resfilter::ByTransact( ), // Resetting all transcations
250 functor::functorRef<bool,PoolItem>(resetting) );
252 return resolvePool();
256 //----------------------------------------------------------------------------
259 void Resolver::undo()
261 UndoTransact info(ResStatus::APPL_LOW);
262 MIL << "*** undo ***" << endl;
263 invokeOnEach ( _pool.begin(), _pool.end(),
264 resfilter::ByTransact( ), // collect transacts from Pool to resolver queue
265 functor::functorRef<bool,PoolItem>(info) );
266 // Regard dependencies of the item weak onl
269 // Additional QueueItems which has to be regarded by the solver
270 _removed_queue_items.clear();
271 _added_queue_items.clear();
276 void Resolver::solverInit()
278 // Solving with libsolv
279 static bool poolDumped = false;
280 MIL << "-------------- Calling SAT Solver -------------------" << endl;
281 if ( getenv("ZYPP_FULLLOG") ) {
282 Testcase testcase("/var/log/YaST2/autoTestcase");
284 testcase.createTestcase (*this, true, false); // dump pool
287 testcase.createTestcase (*this, false, false); // write control file only
291 _satResolver->setFixsystem ( isVerifyingMode() );
292 _satResolver->setIgnorealreadyrecommended ( ignoreAlreadyRecommended() );
293 _satResolver->setOnlyRequires ( onlyRequires() );
294 _satResolver->setAllowdowngrade (false);
295 _satResolver->setAllowarchchange (false);
296 _satResolver->setAllowvendorchange ( allowVendorChange() );
297 _satResolver->setAllowuninstall ( forceResolve() );
298 _satResolver->setUpdatesystem (false);
299 _satResolver->setNoupdateprovide (false);
300 _satResolver->setDosplitprovides (false);
301 _satResolver->setSolveSrcPackages ( solveSrcPackages() );
302 _satResolver->setCleandepsOnRemove ( cleandepsOnRemove() );
304 _satResolver->setDistupgrade (_upgradeMode);
306 // may overwrite some settings
307 _satResolver->setDistupgrade_removeunsupported (false);
308 _satResolver->setUpdatesystem (true);
309 _satResolver->setAllowdowngrade (true);
310 _satResolver->setAllowarchchange (true);
311 _satResolver->setAllowvendorchange (true);
312 _satResolver->setDosplitprovides (true);
315 // Resetting additional solver information
316 _isInstalledBy.clear();
318 _satifiedByInstalled.clear();
319 _installedSatisfied.clear();
322 bool Resolver::resolvePool()
325 return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
328 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
332 // add/remove additional SolverQueueItems
333 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
334 iter != _removed_queue_items.end(); iter++) {
335 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
336 if ( (*iterQueue)->cmp(*iter) == 0) {
337 MIL << "remove from queue" << *iter;
338 queue.remove(*iterQueue);
344 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
345 iter != _added_queue_items.end(); iter++) {
347 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
348 if ( (*iterQueue)->cmp(*iter) == 0) {
354 MIL << "add to queue" << *iter;
355 queue.push_back(*iter);
359 // The application has to take care to write these solutions back to e.g. selectables in order
360 // give the user a chance for changing these decisions again.
361 _removed_queue_items.clear();
362 _added_queue_items.clear();
364 return _satResolver->resolveQueue(queue, _addWeak);
367 sat::Transaction Resolver::getTransaction()
368 { return _satResolver->getTransaction(); }
370 //----------------------------------------------------------------------------
371 // Getting more information about the solve results
373 ResolverProblemList Resolver::problems() const
375 MIL << "Resolver::problems()" << endl;
376 return _satResolver->problems();
379 void Resolver::applySolutions( const ProblemSolutionList & solutions )
381 for_( iter, solutions.begin(), solutions.end() )
383 ProblemSolution_Ptr solution = *iter;
384 if ( !solution->apply( *this ) )
389 void Resolver::collectResolverInfo()
392 && _isInstalledBy.empty()
393 && _installs.empty()) {
396 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
398 for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
399 instIter != itemsToInstall.end(); instIter++) {
401 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
403 sat::WhatProvides possibleProviders(*capIt);
404 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
405 PoolItem provider = ResPool::instance().find( *iter );
407 // searching if this provider will already be installed
409 bool alreadySetForInstallation = false;
410 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
411 while (pos != _isInstalledBy.end()
412 && pos->first == provider
414 alreadySetForInstallation = true;
415 ItemCapKind capKind = pos->second;
416 if (capKind.item == *instIter) found = true;
421 && provider.status().isToBeInstalled()) {
422 if (provider.status().isBySolver()) {
423 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
424 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
426 // no initial installation cause it has been set be e.g. user
427 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
428 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
430 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
431 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
434 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
435 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
436 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
438 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
439 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
444 if (!(_satResolver->onlyRequires())) {
446 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
448 sat::WhatProvides possibleProviders(*capIt);
449 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
450 PoolItem provider = ResPool::instance().find( *iter );
452 // searching if this provider will already be installed
454 bool alreadySetForInstallation = false;
455 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
456 while (pos != _isInstalledBy.end()
457 && pos->first == provider
459 alreadySetForInstallation = true;
460 ItemCapKind capKind = pos->second;
461 if (capKind.item == *instIter) found = true;
466 && provider.status().isToBeInstalled()) {
467 if (provider.status().isBySolver()) {
468 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
469 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
471 // no initial installation cause it has been set be e.g. user
472 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
473 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
475 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
476 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
479 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
480 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
481 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
483 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
484 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
490 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
492 sat::WhatProvides possibleProviders(*capIt);
493 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
494 PoolItem provider = ResPool::instance().find( *iter );
495 // searching if this item will already be installed
497 bool alreadySetForInstallation = false;
498 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
499 while (pos != _isInstalledBy.end()
500 && pos->first == *instIter
502 alreadySetForInstallation = true;
503 ItemCapKind capKind = pos->second;
504 if (capKind.item == provider) found = true;
509 && instIter->status().isToBeInstalled()) {
510 if (instIter->status().isBySolver()) {
511 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
512 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
514 // no initial installation cause it has been set be e.g. user
515 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
516 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
518 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
519 _installs.insert (make_pair( provider, capKindisInstalledBy));
522 if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
523 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
524 _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
526 ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
527 _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
537 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
540 collectResolverInfo();
542 for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
543 ItemCapKind info = iter->second;
544 PoolItem iterItem = iter->first;
545 if (iterItem == item) {
550 iter = _isInstalledBy.end();
556 ItemCapKindList Resolver::installs( const PoolItem & item )
559 collectResolverInfo();
561 for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
562 ItemCapKind info = iter->second;
563 PoolItem iterItem = iter->first;
564 if (iterItem == item) {
569 iter = _installs.end();
575 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
578 collectResolverInfo();
580 for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
581 ItemCapKind info = iter->second;
582 PoolItem iterItem = iter->first;
583 if (iterItem == item) {
588 iter = _satifiedByInstalled.end();
594 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
597 collectResolverInfo();
599 for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
600 ItemCapKind info = iter->second;
601 PoolItem iterItem = iter->first;
602 if (iterItem == item) {
607 iter = _installedSatisfied.end();
614 ///////////////////////////////////////////////////////////////////
615 };// namespace detail
616 /////////////////////////////////////////////////////////////////////
617 /////////////////////////////////////////////////////////////////////
618 };// namespace solver
619 ///////////////////////////////////////////////////////////////////////
620 ///////////////////////////////////////////////////////////////////////
622 /////////////////////////////////////////////////////////////////////////