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 ( 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 ZOLV_FLAG_TRIBOOL( dupSetAllowDowngrade, dupAllowDowngrade, _dup_allowdowngrade, true )
115 ZOLV_FLAG_TRIBOOL( dupSetAllowNameChange, dupAllowNameChange, _dup_allownamechange, true )
116 ZOLV_FLAG_TRIBOOL( dupSetAllowArchChange, dupAllowArchChange, _dup_allowarchchange, true )
117 ZOLV_FLAG_TRIBOOL( dupSetAllowVendorChange, dupAllowVendorChange, _dup_allowvendorchange, true )
119 #undef ZOLV_FLAG_TRIBOOL
120 //---------------------------------------------------------------------------
122 void Resolver::setAllowVendorChange( TriBool state_r )
124 _allowVendorChange = indeterminate(state_r) ? ZConfig::instance().solver_allowVendorChange() : bool(state_r);
127 void Resolver::setOnlyRequires( TriBool state_r )
129 _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
132 void Resolver::setCleandepsOnRemove( TriBool state_r )
134 _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
137 //---------------------------------------------------------------------------
139 ResPool Resolver::pool() const
142 void Resolver::reset( bool keepExtras )
147 _extra_requires.clear();
148 _extra_conflicts.clear();
151 _isInstalledBy.clear();
153 _satifiedByInstalled.clear();
154 _installedSatisfied.clear();
157 bool Resolver::doUpgrade()
159 // Setting Resolver to upgrade mode. SAT solver will do the update
161 return resolvePool();
164 void Resolver::doUpdate()
167 return _satResolver->doUpdate();
170 PoolItemList Resolver::problematicUpdateItems() const
171 { return _satResolver->problematicUpdateItems(); }
173 void Resolver::addExtraRequire( const Capability & capability )
174 { _extra_requires.insert (capability); }
176 void Resolver::removeExtraRequire( const Capability & capability )
177 { _extra_requires.erase (capability); }
179 void Resolver::addExtraConflict( const Capability & capability )
180 { _extra_conflicts.insert (capability); }
182 void Resolver::removeExtraConflict( const Capability & capability )
183 { _extra_conflicts.erase (capability); }
185 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
188 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
189 iter != _added_queue_items.end(); iter++) {
191 _added_queue_items.remove(*iter);
197 _removed_queue_items.push_back (item);
198 _removed_queue_items.unique ();
202 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
205 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
206 iter != _removed_queue_items.end(); iter++) {
208 _removed_queue_items.remove(*iter);
214 _added_queue_items.push_back (item);
215 _added_queue_items.unique ();
219 void Resolver::addWeak( const PoolItem & item )
220 { _addWeak.push_back( item ); }
222 //---------------------------------------------------------------------------
224 struct UndoTransact : public resfilter::PoolItemFilterFunctor
226 ResStatus::TransactByValue resStatus;
227 UndoTransact ( const ResStatus::TransactByValue &status)
231 bool operator()( PoolItem item ) // only transacts() items go here
233 item.status().resetTransact( resStatus );// clear any solver/establish transactions
239 struct DoTransact : public resfilter::PoolItemFilterFunctor
241 ResStatus::TransactByValue resStatus;
242 DoTransact ( const ResStatus::TransactByValue &status)
246 bool operator()( PoolItem item ) // only transacts() items go here
248 item.status().setTransact( true, resStatus );
254 bool Resolver::verifySystem()
256 UndoTransact resetting (ResStatus::APPL_HIGH);
258 _DEBUG ("Resolver::verifySystem() ");
262 invokeOnEach ( _pool.begin(), _pool.end(),
263 resfilter::ByTransact( ), // Resetting all transcations
264 functor::functorRef<bool,PoolItem>(resetting) );
266 return resolvePool();
270 //----------------------------------------------------------------------------
272 void Resolver::undo()
274 UndoTransact info(ResStatus::APPL_LOW);
275 MIL << "*** undo ***" << endl;
276 invokeOnEach ( _pool.begin(), _pool.end(),
277 resfilter::ByTransact( ), // collect transacts from Pool to resolver queue
278 functor::functorRef<bool,PoolItem>(info) );
279 // Regard dependencies of the item weak onl
282 // Additional QueueItems which has to be regarded by the solver
283 _removed_queue_items.clear();
284 _added_queue_items.clear();
289 void Resolver::solverInit()
291 // Solving with libsolv
292 static bool poolDumped = false;
293 MIL << "-------------- Calling SAT Solver -------------------" << endl;
294 if ( getenv("ZYPP_FULLLOG") ) {
295 Testcase testcase("/var/log/YaST2/autoTestcase");
297 testcase.createTestcase (*this, true, false); // dump pool
300 testcase.createTestcase (*this, false, false); // write control file only
304 _satResolver->setFixsystem ( isVerifyingMode() );
305 _satResolver->setIgnorealreadyrecommended ( ignoreAlreadyRecommended() );
306 _satResolver->setOnlyRequires ( onlyRequires() );
307 _satResolver->setAllowdowngrade (false);
308 _satResolver->setAllowarchchange (false);
309 _satResolver->setAllowvendorchange ( allowVendorChange() );
310 _satResolver->setAllowuninstall ( forceResolve() );
311 _satResolver->setUpdatesystem (false);
312 _satResolver->setNoupdateprovide (false);
313 _satResolver->setDosplitprovides (true);
314 _satResolver->setSolveSrcPackages ( solveSrcPackages() );
315 _satResolver->setCleandepsOnRemove ( cleandepsOnRemove() );
317 _satResolver->setDistupgrade (_upgradeMode);
319 // may overwrite some settings
320 _satResolver->setDistupgrade_removeunsupported (false);
323 // Resetting additional solver information
324 _isInstalledBy.clear();
326 _satifiedByInstalled.clear();
327 _installedSatisfied.clear();
330 bool Resolver::resolvePool()
333 return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
336 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
340 // add/remove additional SolverQueueItems
341 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
342 iter != _removed_queue_items.end(); iter++) {
343 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
344 if ( (*iterQueue)->cmp(*iter) == 0) {
345 MIL << "remove from queue" << *iter;
346 queue.remove(*iterQueue);
352 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
353 iter != _added_queue_items.end(); iter++) {
355 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
356 if ( (*iterQueue)->cmp(*iter) == 0) {
362 MIL << "add to queue" << *iter;
363 queue.push_back(*iter);
367 // The application has to take care to write these solutions back to e.g. selectables in order
368 // give the user a chance for changing these decisions again.
369 _removed_queue_items.clear();
370 _added_queue_items.clear();
372 return _satResolver->resolveQueue(queue, _addWeak);
375 sat::Transaction Resolver::getTransaction()
377 // FIXME: That's an ugly way of pushing autoInstalled into the transaction.
378 sat::Transaction ret( sat::Transaction::loadFromPool );
379 ret.autoInstalled( _satResolver->autoInstalled() );
384 //----------------------------------------------------------------------------
385 // Getting more information about the solve results
387 ResolverProblemList Resolver::problems() const
389 MIL << "Resolver::problems()" << endl;
390 return _satResolver->problems();
393 void Resolver::applySolutions( const ProblemSolutionList & solutions )
395 for_( iter, solutions.begin(), solutions.end() )
397 ProblemSolution_Ptr solution = *iter;
398 if ( !solution->apply( *this ) )
403 void Resolver::collectResolverInfo()
406 && _isInstalledBy.empty()
407 && _installs.empty()) {
410 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
412 for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
413 instIter != itemsToInstall.end(); instIter++) {
415 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
417 sat::WhatProvides possibleProviders(*capIt);
418 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
419 PoolItem provider = ResPool::instance().find( *iter );
421 // searching if this provider will already be installed
423 bool alreadySetForInstallation = false;
424 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
425 while (pos != _isInstalledBy.end()
426 && pos->first == provider
428 alreadySetForInstallation = true;
429 ItemCapKind capKind = pos->second;
430 if (capKind.item == *instIter) found = true;
435 && provider.status().isToBeInstalled()) {
436 if (provider.status().isBySolver()) {
437 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
438 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
440 // no initial installation cause it has been set be e.g. user
441 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
442 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
444 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
445 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
448 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
449 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
450 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
452 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
453 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
458 if (!(_satResolver->onlyRequires())) {
460 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
462 sat::WhatProvides possibleProviders(*capIt);
463 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
464 PoolItem provider = ResPool::instance().find( *iter );
466 // searching if this provider will already be installed
468 bool alreadySetForInstallation = false;
469 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
470 while (pos != _isInstalledBy.end()
471 && pos->first == provider
473 alreadySetForInstallation = true;
474 ItemCapKind capKind = pos->second;
475 if (capKind.item == *instIter) found = true;
480 && provider.status().isToBeInstalled()) {
481 if (provider.status().isBySolver()) {
482 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
483 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
485 // no initial installation cause it has been set be e.g. user
486 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
487 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
489 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
490 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
493 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
494 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
495 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
497 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
498 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
504 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
506 sat::WhatProvides possibleProviders(*capIt);
507 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
508 PoolItem provider = ResPool::instance().find( *iter );
509 // searching if this item will already be installed
511 bool alreadySetForInstallation = false;
512 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
513 while (pos != _isInstalledBy.end()
514 && pos->first == *instIter
516 alreadySetForInstallation = true;
517 ItemCapKind capKind = pos->second;
518 if (capKind.item == provider) found = true;
523 && instIter->status().isToBeInstalled()) {
524 if (instIter->status().isBySolver()) {
525 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
526 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
528 // no initial installation cause it has been set be e.g. user
529 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
530 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
532 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
533 _installs.insert (make_pair( provider, capKindisInstalledBy));
536 if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
537 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
538 _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
540 ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
541 _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
551 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
554 collectResolverInfo();
556 for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
557 ItemCapKind info = iter->second;
558 PoolItem iterItem = iter->first;
559 if (iterItem == item) {
564 iter = _isInstalledBy.end();
570 ItemCapKindList Resolver::installs( const PoolItem & item )
573 collectResolverInfo();
575 for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
576 ItemCapKind info = iter->second;
577 PoolItem iterItem = iter->first;
578 if (iterItem == item) {
583 iter = _installs.end();
589 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
592 collectResolverInfo();
594 for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
595 ItemCapKind info = iter->second;
596 PoolItem iterItem = iter->first;
597 if (iterItem == item) {
602 iter = _satifiedByInstalled.end();
608 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
611 collectResolverInfo();
613 for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
614 ItemCapKind info = iter->second;
615 PoolItem iterItem = iter->first;
616 if (iterItem == item) {
621 iter = _installedSatisfied.end();
628 ///////////////////////////////////////////////////////////////////
629 };// namespace detail
630 /////////////////////////////////////////////////////////////////////
631 /////////////////////////////////////////////////////////////////////
632 };// namespace solver
633 ///////////////////////////////////////////////////////////////////////
634 ///////////////////////////////////////////////////////////////////////
636 /////////////////////////////////////////////////////////////////////////