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 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 )
00209 {
00210 item.status().resetTransact( resStatus );
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 )
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( ),
00241 functor::functorRef<bool,PoolItem>(resetting) );
00242
00243 return resolvePool();
00244 }
00245
00246
00247
00248
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( ),
00256 functor::functorRef<bool,PoolItem>(info) );
00257
00258 _addWeak.clear();
00259
00260
00261 _removed_queue_items.clear();
00262 _added_queue_items.clear();
00263
00264 return;
00265 }
00266
00267 void Resolver::solverInit()
00268 {
00269
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);
00276 poolDumped = true;
00277 } else {
00278 testcase.createTestcase (*this, false, false);
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 if (_upgradeMode) {
00296
00297 _satResolver->setDistupgrade (true);
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
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
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
00351
00352 _removed_queue_items.clear();
00353 _added_queue_items.clear();
00354
00355 return _satResolver->resolveQueue(queue, _addWeak);
00356 }
00357
00358
00359
00360
00361
00362
00363 void Resolver::collectResolverInfo()
00364 {
00365 if ( _satResolver
00366 && _isInstalledBy.empty()
00367 && _installs.empty()) {
00368
00369
00370 PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
00371
00372 for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
00373 instIter != itemsToInstall.end(); instIter++) {
00374
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
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
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()) {
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
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
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
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()) {
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
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
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
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()) {
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
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
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
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
00581 iter = _installedSatisfied.end();
00582 }
00583 }
00584 return ret;
00585 }
00586
00587
00589 };
00592 };
00595 };
00597