00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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 return os << "<resolver/>";
00062 }
00063
00064
00065
00066
00067 Resolver::Resolver (const ResPool & pool)
00068 : _pool(pool)
00069 , _satResolver(NULL)
00070 , _poolchanged(_pool.serial() )
00071 , _forceResolve (false)
00072 , _upgradeMode (false)
00073 , _updateMode (false)
00074 , _verifying (false)
00075 , _onlyRequires ( ZConfig::instance().solver_onlyRequires() )
00076 , _allowVendorChange ( ZConfig::instance().solver_allowVendorChange() )
00077 , _solveSrcPackages ( false )
00078 , _ignoreAlreadyRecommended (false)
00079
00080 {
00081 sat::Pool satPool( sat::Pool::instance() );
00082 _satResolver = new SATResolver(_pool, satPool.get());
00083 }
00084
00085
00086 Resolver::~Resolver()
00087 {
00088 delete _satResolver;
00089 }
00090
00091
00092
00093 void Resolver::setAllowVendorChange( TriBool state_r )
00094 {
00095 _allowVendorChange = indeterminate(state_r) ? ZConfig::instance().solver_allowVendorChange() : bool(state_r);
00096 }
00097
00098 void Resolver::setOnlyRequires( TriBool state_r )
00099 {
00100 _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
00101 }
00102
00103
00104
00105 ResPool Resolver::pool() const
00106 { return _pool; }
00107
00108 void Resolver::reset( bool keepExtras )
00109 {
00110 _verifying = false;
00111
00112 if (!keepExtras) {
00113 _extra_requires.clear();
00114 _extra_conflicts.clear();
00115 }
00116
00117 _isInstalledBy.clear();
00118 _installs.clear();
00119 _satifiedByInstalled.clear();
00120 _installedSatisfied.clear();
00121 }
00122
00123 void Resolver::doUpdate()
00124 {
00125 _updateMode = true;
00126 return _satResolver->doUpdate();
00127 }
00128
00129 PoolItemList Resolver::problematicUpdateItems() const
00130 { return _satResolver->problematicUpdateItems(); }
00131
00132 void Resolver::addExtraRequire( const Capability & capability )
00133 { _extra_requires.insert (capability); }
00134
00135 void Resolver::removeExtraRequire( const Capability & capability )
00136 { _extra_requires.erase (capability); }
00137
00138 void Resolver::addExtraConflict( const Capability & capability )
00139 { _extra_conflicts.insert (capability); }
00140
00141 void Resolver::removeExtraConflict( const Capability & capability )
00142 { _extra_conflicts.erase (capability); }
00143
00144 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
00145 {
00146 bool found = false;
00147 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
00148 iter != _added_queue_items.end(); iter++) {
00149 if (*iter == item) {
00150 _added_queue_items.remove(*iter);
00151 found = true;
00152 break;
00153 }
00154 }
00155 if (!found) {
00156 _removed_queue_items.push_back (item);
00157 _removed_queue_items.unique ();
00158 }
00159 }
00160
00161 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
00162 {
00163 bool found = false;
00164 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
00165 iter != _removed_queue_items.end(); iter++) {
00166 if (*iter == item) {
00167 _removed_queue_items.remove(*iter);
00168 found = true;
00169 break;
00170 }
00171 }
00172 if (!found) {
00173 _added_queue_items.push_back (item);
00174 _added_queue_items.unique ();
00175 }
00176 }
00177
00178 void Resolver::addWeak( const PoolItem & item )
00179 { _addWeak.push_back( item ); }
00180
00181
00182
00183 struct UndoTransact : public resfilter::PoolItemFilterFunctor
00184 {
00185 ResStatus::TransactByValue resStatus;
00186 UndoTransact ( const ResStatus::TransactByValue &status)
00187 :resStatus(status)
00188 { }
00189
00190 bool operator()( PoolItem item )
00191 {
00192 item.status().resetTransact( resStatus );
00193 return true;
00194 }
00195 };
00196
00197
00198 struct DoTransact : public resfilter::PoolItemFilterFunctor
00199 {
00200 ResStatus::TransactByValue resStatus;
00201 DoTransact ( const ResStatus::TransactByValue &status)
00202 :resStatus(status)
00203 { }
00204
00205 bool operator()( PoolItem item )
00206 {
00207 item.status().setTransact( true, resStatus );
00208 return true;
00209 }
00210 };
00211
00212
00213 bool Resolver::verifySystem()
00214 {
00215 UndoTransact resetting (ResStatus::APPL_HIGH);
00216
00217 _DEBUG ("Resolver::verifySystem() ");
00218
00219 _verifying = true;
00220
00221 invokeOnEach ( _pool.begin(), _pool.end(),
00222 resfilter::ByTransact( ),
00223 functor::functorRef<bool,PoolItem>(resetting) );
00224
00225 return resolvePool();
00226 }
00227
00228
00229
00230
00231
00232 void Resolver::undo()
00233 {
00234 UndoTransact info(ResStatus::APPL_LOW);
00235 MIL << "*** undo ***" << endl;
00236 invokeOnEach ( _pool.begin(), _pool.end(),
00237 resfilter::ByTransact( ),
00238 functor::functorRef<bool,PoolItem>(info) );
00239
00240 _addWeak.clear();
00241
00242
00243 _removed_queue_items.clear();
00244 _added_queue_items.clear();
00245
00246 return;
00247 }
00248
00249 void Resolver::solverInit()
00250 {
00251
00252 static bool poolDumped = false;
00253 MIL << "-------------- Calling SAT Solver -------------------" << endl;
00254 if ( getenv("ZYPP_FULLLOG") ) {
00255 Testcase testcase("/var/log/YaST2/autoTestcase");
00256 if (!poolDumped) {
00257 testcase.createTestcase (*this, true, false);
00258 poolDumped = true;
00259 } else {
00260 testcase.createTestcase (*this, false, false);
00261 }
00262 }
00263
00264 _satResolver->setFixsystem ( isVerifyingMode() );
00265 _satResolver->setIgnorealreadyrecommended ( ignoreAlreadyRecommended() );
00266 _satResolver->setOnlyRequires ( onlyRequires() );
00267 _satResolver->setAllowdowngrade (false);
00268 _satResolver->setAllowarchchange (false);
00269 _satResolver->setAllowvendorchange ( allowVendorChange() );
00270 _satResolver->setAllowuninstall ( forceResolve() );
00271 _satResolver->setUpdatesystem (false);
00272 _satResolver->setNoupdateprovide (false);
00273 _satResolver->setDosplitprovides (true);
00274 _satResolver->setSolveSrcPackages ( solveSrcPackages() );
00275
00276 _satResolver->setDistupgrade (_upgradeMode);
00277 if (_upgradeMode) {
00278
00279 _satResolver->setDistupgrade_removeunsupported (false);
00280 _satResolver->setUpdatesystem (true);
00281 _satResolver->setAllowdowngrade (true);
00282 _satResolver->setAllowarchchange (true);
00283 _satResolver->setAllowvendorchange (true);
00284 }
00285
00286
00287 _isInstalledBy.clear();
00288 _installs.clear();
00289 _satifiedByInstalled.clear();
00290 _installedSatisfied.clear();
00291 }
00292
00293 bool Resolver::resolvePool()
00294 {
00295 solverInit();
00296 return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
00297 }
00298
00299 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
00300 {
00301 solverInit();
00302
00303
00304 for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
00305 iter != _removed_queue_items.end(); iter++) {
00306 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
00307 if ( (*iterQueue)->cmp(*iter) == 0) {
00308 MIL << "remove from queue" << *iter;
00309 queue.remove(*iterQueue);
00310 break;
00311 }
00312 }
00313 }
00314
00315 for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
00316 iter != _added_queue_items.end(); iter++) {
00317 bool found = false;
00318 for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
00319 if ( (*iterQueue)->cmp(*iter) == 0) {
00320 found = true;
00321 break;
00322 }
00323 }
00324 if (!found) {
00325 MIL << "add to queue" << *iter;
00326 queue.push_back(*iter);
00327 }
00328 }
00329
00330
00331
00332 _removed_queue_items.clear();
00333 _added_queue_items.clear();
00334
00335 return _satResolver->resolveQueue(queue, _addWeak);
00336 }
00337
00338
00339
00340
00341
00342
00343 void Resolver::collectResolverInfo()
00344 {
00345 if ( _satResolver
00346 && _isInstalledBy.empty()
00347 && _installs.empty()) {
00348
00349
00350 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
00351
00352 for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
00353 instIter != itemsToInstall.end(); instIter++) {
00354
00355 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
00356 {
00357 sat::WhatProvides possibleProviders(*capIt);
00358 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
00359 PoolItem provider = ResPool::instance().find( *iter );
00360
00361
00362 bool found = false;
00363 bool alreadySetForInstallation = false;
00364 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
00365 while (pos != _isInstalledBy.end()
00366 && pos->first == provider
00367 && !found) {
00368 alreadySetForInstallation = true;
00369 ItemCapKind capKind = pos->second;
00370 if (capKind.item == *instIter) found = true;
00371 pos++;
00372 }
00373
00374 if (!found
00375 && provider.status().isToBeInstalled()) {
00376 if (provider.status().isBySolver()) {
00377 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
00378 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
00379 } else {
00380
00381 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
00382 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
00383 }
00384 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
00385 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
00386 }
00387
00388 if (provider.status().staysInstalled()) {
00389 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
00390 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
00391
00392 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
00393 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
00394 }
00395 }
00396 }
00397
00398 if (!(_satResolver->onlyRequires())) {
00399
00400 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
00401 {
00402 sat::WhatProvides possibleProviders(*capIt);
00403 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
00404 PoolItem provider = ResPool::instance().find( *iter );
00405
00406
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::RECOMMENDS, !alreadySetForInstallation );
00423 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
00424 } else {
00425
00426 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
00427 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
00428 }
00429 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
00430 _installs.insert (make_pair( *instIter, capKindisInstalledBy));
00431 }
00432
00433 if (provider.status().staysInstalled()) {
00434 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
00435 _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
00436
00437 ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
00438 _installedSatisfied.insert (make_pair( provider, installedSatisfied));
00439 }
00440 }
00441 }
00442
00443
00444 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
00445 {
00446 sat::WhatProvides possibleProviders(*capIt);
00447 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
00448 PoolItem provider = ResPool::instance().find( *iter );
00449
00450 bool found = false;
00451 bool alreadySetForInstallation = false;
00452 ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
00453 while (pos != _isInstalledBy.end()
00454 && pos->first == *instIter
00455 && !found) {
00456 alreadySetForInstallation = true;
00457 ItemCapKind capKind = pos->second;
00458 if (capKind.item == provider) found = true;
00459 pos++;
00460 }
00461
00462 if (!found
00463 && instIter->status().isToBeInstalled()) {
00464 if (instIter->status().isBySolver()) {
00465 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
00466 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
00467 } else {
00468
00469 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
00470 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
00471 }
00472 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
00473 _installs.insert (make_pair( provider, capKindisInstalledBy));
00474 }
00475
00476 if (instIter->status().staysInstalled()) {
00477 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
00478 _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
00479
00480 ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
00481 _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
00482 }
00483 }
00484 }
00485 }
00486 }
00487 }
00488 }
00489
00490
00491 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
00492 {
00493 ItemCapKindList ret;
00494 collectResolverInfo();
00495
00496 for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
00497 ItemCapKind info = iter->second;
00498 PoolItem iterItem = iter->first;
00499 if (iterItem == item) {
00500 ret.push_back(info);
00501 iter++;
00502 } else {
00503
00504 iter = _isInstalledBy.end();
00505 }
00506 }
00507 return ret;
00508 }
00509
00510 ItemCapKindList Resolver::installs( const PoolItem & item )
00511 {
00512 ItemCapKindList ret;
00513 collectResolverInfo();
00514
00515 for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
00516 ItemCapKind info = iter->second;
00517 PoolItem iterItem = iter->first;
00518 if (iterItem == item) {
00519 ret.push_back(info);
00520 iter++;
00521 } else {
00522
00523 iter = _installs.end();
00524 }
00525 }
00526 return ret;
00527 }
00528
00529 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
00530 {
00531 ItemCapKindList ret;
00532 collectResolverInfo();
00533
00534 for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
00535 ItemCapKind info = iter->second;
00536 PoolItem iterItem = iter->first;
00537 if (iterItem == item) {
00538 ret.push_back(info);
00539 iter++;
00540 } else {
00541
00542 iter = _satifiedByInstalled.end();
00543 }
00544 }
00545 return ret;
00546 }
00547
00548 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
00549 {
00550 ItemCapKindList ret;
00551 collectResolverInfo();
00552
00553 for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
00554 ItemCapKind info = iter->second;
00555 PoolItem iterItem = iter->first;
00556 if (iterItem == item) {
00557 ret.push_back(info);
00558 iter++;
00559 } else {
00560
00561 iter = _installedSatisfied.end();
00562 }
00563 }
00564 return ret;
00565 }
00566
00567
00569 };
00572 };
00575 };
00577