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