libzypp 9.41.1
|
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */ 00002 /* Resolver.cc 00003 * 00004 * Copyright (C) 2000-2002 Ximian, Inc. 00005 * Copyright (C) 2005 SUSE Linux Products GmbH 00006 * 00007 * This program is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU General Public License, 00009 * version 2, as published by the Free Software Foundation. 00010 * 00011 * This program is distributed in the hope that it will be useful, but 00012 * WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 * General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License 00017 * along with this program; if not, write to the Free Software 00018 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 00019 * 02111-1307, USA. 00020 */ 00021 #include <boost/static_assert.hpp> 00022 00023 #include "zypp/solver/detail/Resolver.h" 00024 #include "zypp/solver/detail/Helper.h" 00025 #include "zypp/solver/detail/Testcase.h" 00026 #include "zypp/solver/detail/SATResolver.h" 00027 00028 #include "zypp/Capabilities.h" 00029 #include "zypp/ZConfig.h" 00030 #include "zypp/base/Logger.h" 00031 #include "zypp/base/String.h" 00032 #include "zypp/base/Gettext.h" 00033 #include "zypp/base/Algorithm.h" 00034 #include "zypp/ResPool.h" 00035 #include "zypp/ResFilters.h" 00036 #include "zypp/sat/Pool.h" 00037 #include "zypp/sat/Solvable.h" 00038 #include "zypp/sat/Transaction.h" 00039 #include "zypp/ResolverProblem.h" 00040 00041 #define MAXSOLVERRUNS 5 00042 00044 namespace zypp 00045 { 00046 00047 namespace solver 00048 { 00049 00050 namespace detail 00051 { 00052 00053 using namespace std; 00054 00055 IMPL_PTR_TYPE(Resolver); 00056 00057 00058 //--------------------------------------------------------------------------- 00059 00060 00061 std::ostream & Resolver::dumpOn( std::ostream & os ) const 00062 { 00063 os << "<resolver>" << endl; 00064 #define OUTS(t) os << " " << #t << ":\t" << t << endl; 00065 OUTS( _forceResolve ); 00066 OUTS( _upgradeMode ); 00067 OUTS( _updateMode ); 00068 OUTS( _verifying ); 00069 OUTS( _onlyRequires ); 00070 OUTS( _allowVendorChange ); 00071 OUTS( _solveSrcPackages ); 00072 OUTS( _cleandepsOnRemove ); 00073 OUTS( _ignoreAlreadyRecommended ); 00074 #undef OUT 00075 return os << "<resolver/>"; 00076 } 00077 00078 00079 //--------------------------------------------------------------------------- 00080 00081 Resolver::Resolver (const ResPool & pool) 00082 : _pool(pool) 00083 , _satResolver(NULL) 00084 , _poolchanged(_pool.serial() ) 00085 , _forceResolve (false) 00086 , _upgradeMode (false) 00087 , _updateMode (false) 00088 , _verifying (false) 00089 , _onlyRequires ( ZConfig::instance().solver_onlyRequires() ) 00090 , _allowVendorChange ( ZConfig::instance().solver_allowVendorChange() ) 00091 , _solveSrcPackages ( false ) 00092 , _cleandepsOnRemove ( ZConfig::instance().solver_cleandepsOnRemove() ) 00093 , _ignoreAlreadyRecommended ( false ) 00094 00095 { 00096 sat::Pool satPool( sat::Pool::instance() ); 00097 _satResolver = new SATResolver(_pool, satPool.get()); 00098 } 00099 00100 00101 Resolver::~Resolver() 00102 { 00103 delete _satResolver; 00104 } 00105 00106 //--------------------------------------------------------------------------- 00107 00108 void Resolver::setAllowVendorChange( TriBool state_r ) 00109 { 00110 _allowVendorChange = indeterminate(state_r) ? ZConfig::instance().solver_allowVendorChange() : bool(state_r); 00111 } 00112 00113 void Resolver::setOnlyRequires( TriBool state_r ) 00114 { 00115 _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r); 00116 } 00117 00118 void Resolver::setCleandepsOnRemove( TriBool state_r ) 00119 { 00120 _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r); 00121 } 00122 00123 //--------------------------------------------------------------------------- 00124 00125 ResPool Resolver::pool() const 00126 { return _pool; } 00127 00128 void Resolver::reset( bool keepExtras ) 00129 { 00130 _verifying = false; 00131 00132 if (!keepExtras) { 00133 _extra_requires.clear(); 00134 _extra_conflicts.clear(); 00135 } 00136 00137 _isInstalledBy.clear(); 00138 _installs.clear(); 00139 _satifiedByInstalled.clear(); 00140 _installedSatisfied.clear(); 00141 } 00142 00143 bool Resolver::doUpgrade() 00144 { 00145 // Setting Resolver to upgrade mode. SAT solver will do the update 00146 _upgradeMode = true; 00147 return resolvePool(); 00148 } 00149 00150 void Resolver::doUpdate() 00151 { 00152 _updateMode = true; 00153 return _satResolver->doUpdate(); 00154 } 00155 00156 PoolItemList Resolver::problematicUpdateItems() const 00157 { return _satResolver->problematicUpdateItems(); } 00158 00159 void Resolver::addExtraRequire( const Capability & capability ) 00160 { _extra_requires.insert (capability); } 00161 00162 void Resolver::removeExtraRequire( const Capability & capability ) 00163 { _extra_requires.erase (capability); } 00164 00165 void Resolver::addExtraConflict( const Capability & capability ) 00166 { _extra_conflicts.insert (capability); } 00167 00168 void Resolver::removeExtraConflict( const Capability & capability ) 00169 { _extra_conflicts.erase (capability); } 00170 00171 void Resolver::removeQueueItem( SolverQueueItem_Ptr item ) 00172 { 00173 bool found = false; 00174 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin(); 00175 iter != _added_queue_items.end(); iter++) { 00176 if (*iter == item) { 00177 _added_queue_items.remove(*iter); 00178 found = true; 00179 break; 00180 } 00181 } 00182 if (!found) { 00183 _removed_queue_items.push_back (item); 00184 _removed_queue_items.unique (); 00185 } 00186 } 00187 00188 void Resolver::addQueueItem( SolverQueueItem_Ptr item ) 00189 { 00190 bool found = false; 00191 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin(); 00192 iter != _removed_queue_items.end(); iter++) { 00193 if (*iter == item) { 00194 _removed_queue_items.remove(*iter); 00195 found = true; 00196 break; 00197 } 00198 } 00199 if (!found) { 00200 _added_queue_items.push_back (item); 00201 _added_queue_items.unique (); 00202 } 00203 } 00204 00205 void Resolver::addWeak( const PoolItem & item ) 00206 { _addWeak.push_back( item ); } 00207 00208 //--------------------------------------------------------------------------- 00209 00210 struct UndoTransact : public resfilter::PoolItemFilterFunctor 00211 { 00212 ResStatus::TransactByValue resStatus; 00213 UndoTransact ( const ResStatus::TransactByValue &status) 00214 :resStatus(status) 00215 { } 00216 00217 bool operator()( PoolItem item ) // only transacts() items go here 00218 { 00219 item.status().resetTransact( resStatus );// clear any solver/establish transactions 00220 return true; 00221 } 00222 }; 00223 00224 00225 struct DoTransact : public resfilter::PoolItemFilterFunctor 00226 { 00227 ResStatus::TransactByValue resStatus; 00228 DoTransact ( const ResStatus::TransactByValue &status) 00229 :resStatus(status) 00230 { } 00231 00232 bool operator()( PoolItem item ) // only transacts() items go here 00233 { 00234 item.status().setTransact( true, resStatus ); 00235 return true; 00236 } 00237 }; 00238 00239 00240 bool Resolver::verifySystem() 00241 { 00242 UndoTransact resetting (ResStatus::APPL_HIGH); 00243 00244 _DEBUG ("Resolver::verifySystem() "); 00245 00246 _verifying = true; 00247 00248 invokeOnEach ( _pool.begin(), _pool.end(), 00249 resfilter::ByTransact( ), // Resetting all transcations 00250 functor::functorRef<bool,PoolItem>(resetting) ); 00251 00252 return resolvePool(); 00253 } 00254 00255 00256 //---------------------------------------------------------------------------- 00257 // undo 00258 00259 void Resolver::undo() 00260 { 00261 UndoTransact info(ResStatus::APPL_LOW); 00262 MIL << "*** undo ***" << endl; 00263 invokeOnEach ( _pool.begin(), _pool.end(), 00264 resfilter::ByTransact( ), // collect transacts from Pool to resolver queue 00265 functor::functorRef<bool,PoolItem>(info) ); 00266 // Regard dependencies of the item weak onl 00267 _addWeak.clear(); 00268 00269 // Additional QueueItems which has to be regarded by the solver 00270 _removed_queue_items.clear(); 00271 _added_queue_items.clear(); 00272 00273 return; 00274 } 00275 00276 void Resolver::solverInit() 00277 { 00278 // Solving with the satsolver 00279 static bool poolDumped = false; 00280 MIL << "-------------- Calling SAT Solver -------------------" << endl; 00281 if ( getenv("ZYPP_FULLLOG") ) { 00282 Testcase testcase("/var/log/YaST2/autoTestcase"); 00283 if (!poolDumped) { 00284 testcase.createTestcase (*this, true, false); // dump pool 00285 poolDumped = true; 00286 } else { 00287 testcase.createTestcase (*this, false, false); // write control file only 00288 } 00289 } 00290 00291 _satResolver->setFixsystem ( isVerifyingMode() ); 00292 _satResolver->setIgnorealreadyrecommended ( ignoreAlreadyRecommended() ); 00293 _satResolver->setOnlyRequires ( onlyRequires() ); 00294 _satResolver->setAllowdowngrade (false); 00295 _satResolver->setAllowarchchange (false); 00296 _satResolver->setAllowvendorchange ( allowVendorChange() ); 00297 _satResolver->setAllowuninstall ( forceResolve() ); 00298 _satResolver->setUpdatesystem (false); 00299 _satResolver->setNoupdateprovide (false); 00300 _satResolver->setDosplitprovides (true); 00301 _satResolver->setSolveSrcPackages ( solveSrcPackages() ); 00302 _satResolver->setCleandepsOnRemove ( cleandepsOnRemove() ); 00303 00304 _satResolver->setDistupgrade (_upgradeMode); 00305 if (_upgradeMode) { 00306 // may overwrite some settings 00307 _satResolver->setDistupgrade_removeunsupported (false); 00308 _satResolver->setUpdatesystem (true); 00309 _satResolver->setAllowdowngrade (true); 00310 _satResolver->setAllowarchchange (true); 00311 _satResolver->setAllowvendorchange (true); 00312 } 00313 00314 // Resetting additional solver information 00315 _isInstalledBy.clear(); 00316 _installs.clear(); 00317 _satifiedByInstalled.clear(); 00318 _installedSatisfied.clear(); 00319 } 00320 00321 bool Resolver::resolvePool() 00322 { 00323 solverInit(); 00324 return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos ); 00325 } 00326 00327 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue ) 00328 { 00329 solverInit(); 00330 00331 // add/remove additional SolverQueueItems 00332 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin(); 00333 iter != _removed_queue_items.end(); iter++) { 00334 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) { 00335 if ( (*iterQueue)->cmp(*iter) == 0) { 00336 MIL << "remove from queue" << *iter; 00337 queue.remove(*iterQueue); 00338 break; 00339 } 00340 } 00341 } 00342 00343 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin(); 00344 iter != _added_queue_items.end(); iter++) { 00345 bool found = false; 00346 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) { 00347 if ( (*iterQueue)->cmp(*iter) == 0) { 00348 found = true; 00349 break; 00350 } 00351 } 00352 if (!found) { 00353 MIL << "add to queue" << *iter; 00354 queue.push_back(*iter); 00355 } 00356 } 00357 00358 // The application has to take care to write these solutions back to e.g. selectables in order 00359 // give the user a chance for changing these decisions again. 00360 _removed_queue_items.clear(); 00361 _added_queue_items.clear(); 00362 00363 return _satResolver->resolveQueue(queue, _addWeak); 00364 } 00365 00366 sat::Transaction Resolver::getTransaction() 00367 { return _satResolver->getTransaction(); } 00368 00369 //---------------------------------------------------------------------------- 00370 // Getting more information about the solve results 00371 00372 ResolverProblemList Resolver::problems() const 00373 { 00374 MIL << "Resolver::problems()" << endl; 00375 return _satResolver->problems(); 00376 } 00377 00378 void Resolver::applySolutions( const ProblemSolutionList & solutions ) 00379 { 00380 for_( iter, solutions.begin(), solutions.end() ) 00381 { 00382 ProblemSolution_Ptr solution = *iter; 00383 if ( !solution->apply( *this ) ) 00384 break; 00385 } 00386 } 00387 00388 void Resolver::collectResolverInfo() 00389 { 00390 if ( _satResolver 00391 && _isInstalledBy.empty() 00392 && _installs.empty()) { 00393 00394 // generating new 00395 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall(); 00396 00397 for (PoolItemList::const_iterator instIter = itemsToInstall.begin(); 00398 instIter != itemsToInstall.end(); instIter++) { 00399 // Requires 00400 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt) 00401 { 00402 sat::WhatProvides possibleProviders(*capIt); 00403 for_( iter, possibleProviders.begin(), possibleProviders.end() ) { 00404 PoolItem provider = ResPool::instance().find( *iter ); 00405 00406 // searching if this provider will already be installed 00407 bool found = false; 00408 bool alreadySetForInstallation = false; 00409 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider); 00410 while (pos != _isInstalledBy.end() 00411 && pos->first == provider 00412 && !found) { 00413 alreadySetForInstallation = true; 00414 ItemCapKind capKind = pos->second; 00415 if (capKind.item == *instIter) found = true; 00416 pos++; 00417 } 00418 00419 if (!found 00420 && provider.status().isToBeInstalled()) { 00421 if (provider.status().isBySolver()) { 00422 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation ); 00423 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy)); 00424 } else { 00425 // no initial installation cause it has been set be e.g. user 00426 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false ); 00427 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy)); 00428 } 00429 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation ); 00430 _installs.insert (make_pair( *instIter, capKindisInstalledBy)); 00431 } 00432 00433 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed 00434 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false ); 00435 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy)); 00436 00437 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false ); 00438 _installedSatisfied.insert (make_pair( provider, installedSatisfied)); 00439 } 00440 } 00441 } 00442 00443 if (!(_satResolver->onlyRequires())) { 00444 //Recommends 00445 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt) 00446 { 00447 sat::WhatProvides possibleProviders(*capIt); 00448 for_( iter, possibleProviders.begin(), possibleProviders.end() ) { 00449 PoolItem provider = ResPool::instance().find( *iter ); 00450 00451 // searching if this provider will already be installed 00452 bool found = false; 00453 bool alreadySetForInstallation = false; 00454 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider); 00455 while (pos != _isInstalledBy.end() 00456 && pos->first == provider 00457 && !found) { 00458 alreadySetForInstallation = true; 00459 ItemCapKind capKind = pos->second; 00460 if (capKind.item == *instIter) found = true; 00461 pos++; 00462 } 00463 00464 if (!found 00465 && provider.status().isToBeInstalled()) { 00466 if (provider.status().isBySolver()) { 00467 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation ); 00468 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy)); 00469 } else { 00470 // no initial installation cause it has been set be e.g. user 00471 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false ); 00472 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy)); 00473 } 00474 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation ); 00475 _installs.insert (make_pair( *instIter, capKindisInstalledBy)); 00476 } 00477 00478 if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed 00479 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false ); 00480 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy)); 00481 00482 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false ); 00483 _installedSatisfied.insert (make_pair( provider, installedSatisfied)); 00484 } 00485 } 00486 } 00487 00488 //Supplements 00489 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt) 00490 { 00491 sat::WhatProvides possibleProviders(*capIt); 00492 for_( iter, possibleProviders.begin(), possibleProviders.end() ) { 00493 PoolItem provider = ResPool::instance().find( *iter ); 00494 // searching if this item will already be installed 00495 bool found = false; 00496 bool alreadySetForInstallation = false; 00497 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter); 00498 while (pos != _isInstalledBy.end() 00499 && pos->first == *instIter 00500 && !found) { 00501 alreadySetForInstallation = true; 00502 ItemCapKind capKind = pos->second; 00503 if (capKind.item == provider) found = true; 00504 pos++; 00505 } 00506 00507 if (!found 00508 && instIter->status().isToBeInstalled()) { 00509 if (instIter->status().isBySolver()) { 00510 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation ); 00511 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy)); 00512 } else { 00513 // no initial installation cause it has been set be e.g. user 00514 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false ); 00515 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy)); 00516 } 00517 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation ); 00518 _installs.insert (make_pair( provider, capKindisInstalledBy)); 00519 } 00520 00521 if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed 00522 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation ); 00523 _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy)); 00524 00525 ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false ); 00526 _installedSatisfied.insert (make_pair( *instIter, installedSatisfied)); 00527 } 00528 } 00529 } 00530 } 00531 } 00532 } 00533 } 00534 00535 00536 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item ) 00537 { 00538 ItemCapKindList ret; 00539 collectResolverInfo(); 00540 00541 for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) { 00542 ItemCapKind info = iter->second; 00543 PoolItem iterItem = iter->first; 00544 if (iterItem == item) { 00545 ret.push_back(info); 00546 iter++; 00547 } else { 00548 // exit 00549 iter = _isInstalledBy.end(); 00550 } 00551 } 00552 return ret; 00553 } 00554 00555 ItemCapKindList Resolver::installs( const PoolItem & item ) 00556 { 00557 ItemCapKindList ret; 00558 collectResolverInfo(); 00559 00560 for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) { 00561 ItemCapKind info = iter->second; 00562 PoolItem iterItem = iter->first; 00563 if (iterItem == item) { 00564 ret.push_back(info); 00565 iter++; 00566 } else { 00567 // exit 00568 iter = _installs.end(); 00569 } 00570 } 00571 return ret; 00572 } 00573 00574 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item ) 00575 { 00576 ItemCapKindList ret; 00577 collectResolverInfo(); 00578 00579 for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) { 00580 ItemCapKind info = iter->second; 00581 PoolItem iterItem = iter->first; 00582 if (iterItem == item) { 00583 ret.push_back(info); 00584 iter++; 00585 } else { 00586 // exit 00587 iter = _satifiedByInstalled.end(); 00588 } 00589 } 00590 return ret; 00591 } 00592 00593 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item ) 00594 { 00595 ItemCapKindList ret; 00596 collectResolverInfo(); 00597 00598 for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) { 00599 ItemCapKind info = iter->second; 00600 PoolItem iterItem = iter->first; 00601 if (iterItem == item) { 00602 ret.push_back(info); 00603 iter++; 00604 } else { 00605 // exit 00606 iter = _installedSatisfied.end(); 00607 } 00608 } 00609 return ret; 00610 } 00611 00612 00614 };// namespace detail 00617 };// namespace solver 00620 };// namespace zypp 00622