zypp/solver/detail/Resolver.cc

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
   2 /* Resolver.cc
   3  *
   4  * Copyright (C) 2000-2002 Ximian, Inc.
   5  * Copyright (C) 2005 SUSE Linux Products GmbH
   6  *
   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.
  10  *
  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.
  15  *
  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
  19  * 02111-1307, USA.
  20  */
  21 #include <boost/static_assert.hpp>
  22
  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"
  27
  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
  40 #define MAXSOLVERRUNS 5
  41
  42 /////////////////////////////////////////////////////////////////////////
  43 namespace zypp
  44 { ///////////////////////////////////////////////////////////////////////
  45   ///////////////////////////////////////////////////////////////////////
  46   namespace solver
  47   { /////////////////////////////////////////////////////////////////////
  48     /////////////////////////////////////////////////////////////////////
  49     namespace detail
  50     { ///////////////////////////////////////////////////////////////////
  51
  52 using namespace std;
  53
  54 IMPL_PTR_TYPE(Resolver);
  55
  56
  57 //---------------------------------------------------------------------------
  58
  59
  60 std::ostream & Resolver::dumpOn( std::ostream & os ) const
  61 {
  62   os << "<resolver>" << endl;
  63   #define OUTS(t) os << "  " << #t << ":\t" << t << endl;
  64   OUTS( _forceResolve );
  65   OUTS( _upgradeMode );
  66   OUTS( _updateMode );
  67   OUTS( _verifying );
  68   OUTS( _onlyRequires );
  69   OUTS( _allowVendorChange );
  70   OUTS( _solveSrcPackages );
  71   OUTS( _cleandepsOnRemove );
  72   OUTS( _ignoreAlreadyRecommended );
  73   #undef OUT
  74   return os << "<resolver/>";
  75 }
  76
  77
  78 //---------------------------------------------------------------------------
  79
  80 Resolver::Resolver (const ResPool & pool)
  81     : _pool(pool)
  82     , _satResolver(NULL)
  83     , _poolchanged(_pool.serial() )
  84     , _forceResolve             (false)
  85     , _upgradeMode              (false)
  86     , _updateMode               (false)
  87     , _verifying                (false)
  88     , _onlyRequires             ( ZConfig::instance().solver_onlyRequires() )
  89     , _allowVendorChange        ( ZConfig::instance().solver_allowVendorChange() )
  90     , _solveSrcPackages         ( false )
  91     , _cleandepsOnRemove        ( ZConfig::instance().solver_cleandepsOnRemove() )
  92     , _ignoreAlreadyRecommended ( false )
  93
  94 {
  95     sat::Pool satPool( sat::Pool::instance() );
  96     _satResolver = new SATResolver(_pool, satPool.get());
  97 }
  98
  99
 100 Resolver::~Resolver()
 101 {
 102   delete _satResolver;
 103 }
 104
 105 //---------------------------------------------------------------------------
 106
 107 void Resolver::setAllowVendorChange( TriBool state_r )
 108 {
 109   _allowVendorChange = indeterminate(state_r) ? ZConfig::instance().solver_allowVendorChange() : bool(state_r);
 110 }
 111
 112 void Resolver::setOnlyRequires( TriBool state_r )
 113 {
 114   _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
 115 }
 116
 117 void Resolver::setCleandepsOnRemove( TriBool state_r )
 118 {
 119   _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
 120 }
 121
 122 //---------------------------------------------------------------------------
 123
 124 ResPool Resolver::pool() const
 125 { return _pool; }
 126
 127 void Resolver::reset( bool keepExtras )
 128 {
 129     _verifying = false;
 130
 131     if (!keepExtras) {
 132       _extra_requires.clear();
 133       _extra_conflicts.clear();
 134     }
 135
 136     _isInstalledBy.clear();
 137     _installs.clear();
 138     _satifiedByInstalled.clear();
 139     _installedSatisfied.clear();
 140 }
 141
 142 void Resolver::doUpdate()
 143 {
 144     _updateMode = true;
 145     return _satResolver->doUpdate();
 146 }
 147
 148 PoolItemList Resolver::problematicUpdateItems() const
 149 { return _satResolver->problematicUpdateItems(); }
 150
 151 void Resolver::addExtraRequire( const Capability & capability )
 152 { _extra_requires.insert (capability); }
 153
 154 void Resolver::removeExtraRequire( const Capability & capability )
 155 { _extra_requires.erase (capability); }
 156
 157 void Resolver::addExtraConflict( const Capability & capability )
 158 { _extra_conflicts.insert (capability); }
 159
 160 void Resolver::removeExtraConflict( const Capability & capability )
 161 { _extra_conflicts.erase (capability); }
 162
 163 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
 164 {
 165     bool found = false;
 166     for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
 167          iter != _added_queue_items.end(); iter++) {
 168         if (*iter == item) {
 169             _added_queue_items.remove(*iter);
 170             found = true;
 171             break;
 172         }
 173     }
 174     if (!found) {
 175         _removed_queue_items.push_back (item);
 176         _removed_queue_items.unique ();
 177     }
 178 }
 179
 180 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
 181 {
 182     bool found = false;
 183     for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
 184          iter != _removed_queue_items.end(); iter++) {
 185         if (*iter == item) {
 186             _removed_queue_items.remove(*iter);
 187             found = true;
 188             break;
 189         }
 190     }
 191     if (!found) {
 192         _added_queue_items.push_back (item);
 193         _added_queue_items.unique ();
 194     }
 195 }
 196
 197 void Resolver::addWeak( const PoolItem & item )
 198 { _addWeak.push_back( item ); }
 199
 200 //---------------------------------------------------------------------------
 201
 202 struct UndoTransact : public resfilter::PoolItemFilterFunctor
 203 {
 204     ResStatus::TransactByValue resStatus;
 205     UndoTransact ( const ResStatus::TransactByValue &status)
 206         :resStatus(status)
 207     { }
 208
 209     bool operator()( PoolItem item )            // only transacts() items go here
 210     {
 211         item.status().resetTransact( resStatus );// clear any solver/establish transactions
 212         return true;
 213     }
 214 };
 215
 216
 217 struct DoTransact : public resfilter::PoolItemFilterFunctor
 218 {
 219     ResStatus::TransactByValue resStatus;
 220     DoTransact ( const ResStatus::TransactByValue &status)
 221         :resStatus(status)
 222     { }
 223
 224     bool operator()( PoolItem item )            // only transacts() items go here
 225     {
 226         item.status().setTransact( true, resStatus );
 227         return true;
 228     }
 229 };
 230
 231
 232 bool Resolver::verifySystem()
 233 {
 234     UndoTransact resetting (ResStatus::APPL_HIGH);
 235
 236     _DEBUG ("Resolver::verifySystem() ");
 237
 238     _verifying = true;
 239
 240     invokeOnEach ( _pool.begin(), _pool.end(),
 241                    resfilter::ByTransact( ),                    // Resetting all transcations
 242                    functor::functorRef<bool,PoolItem>(resetting) );
 243
 244     return resolvePool();
 245 }
 246
 247
 248 //----------------------------------------------------------------------------
 249 // undo
 250
 251 void Resolver::undo()
 252 {
 253     UndoTransact info(ResStatus::APPL_LOW);
 254     MIL << "*** undo ***" << endl;
 255     invokeOnEach ( _pool.begin(), _pool.end(),
 256                    resfilter::ByTransact( ),                    // collect transacts from Pool to resolver queue
 257                    functor::functorRef<bool,PoolItem>(info) );
 258     //  Regard dependencies of the item weak onl
 259     _addWeak.clear();
 260
 261     // Additional QueueItems which has to be regarded by the solver
 262     _removed_queue_items.clear();
 263     _added_queue_items.clear();
 264
 265     return;
 266 }
 267
 268 void Resolver::solverInit()
 269 {
 270     // Solving with the satsolver
 271     static bool poolDumped = false;
 272     MIL << "-------------- Calling SAT Solver -------------------" << endl;
 273     if ( getenv("ZYPP_FULLLOG") ) {
 274         Testcase testcase("/var/log/YaST2/autoTestcase");
 275         if (!poolDumped) {
 276             testcase.createTestcase (*this, true, false); // dump pool
 277             poolDumped = true;
 278         } else {
 279             testcase.createTestcase (*this, false, false); // write control file only
 280         }
 281     }
 282
 283     _satResolver->setFixsystem                  ( isVerifyingMode() );
 284     _satResolver->setIgnorealreadyrecommended   ( ignoreAlreadyRecommended() );
 285     _satResolver->setOnlyRequires               ( onlyRequires() );
 286     _satResolver->setAllowdowngrade             (false);
 287     _satResolver->setAllowarchchange            (false);
 288     _satResolver->setAllowvendorchange          ( allowVendorChange() );
 289     _satResolver->setAllowuninstall             ( forceResolve() );
 290     _satResolver->setUpdatesystem               (false);
 291     _satResolver->setNoupdateprovide            (false);
 292     _satResolver->setDosplitprovides            (false);
 293     _satResolver->setSolveSrcPackages           ( solveSrcPackages() );
 294     _satResolver->setCleandepsOnRemove          ( cleandepsOnRemove() );
 295
 296     if (_upgradeMode) {
 297       // may overwrite some settings
 298       _satResolver->setDistupgrade                      (true);
 299       _satResolver->setDistupgrade_removeunsupported    (false);
 300       _satResolver->setUpdatesystem                     (true);
 301       _satResolver->setAllowdowngrade                   (true);
 302       _satResolver->setAllowarchchange                  (true);
 303       _satResolver->setAllowvendorchange                (true);
 304       _satResolver->setDosplitprovides                  (true);
 305     }
 306
 307     // Resetting additional solver information
 308     _isInstalledBy.clear();
 309     _installs.clear();
 310     _satifiedByInstalled.clear();
 311     _installedSatisfied.clear();
 312 }
 313
 314 bool Resolver::resolvePool()
 315 {
 316     solverInit();
 317     return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
 318 }
 319
 320 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
 321 {
 322     solverInit();
 323
 324     // add/remove additional SolverQueueItems
 325     for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
 326          iter != _removed_queue_items.end(); iter++) {
 327         for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
 328             if ( (*iterQueue)->cmp(*iter) == 0) {
 329                 MIL << "remove from queue" << *iter;
 330                 queue.remove(*iterQueue);
 331                 break;
 332             }
 333         }
 334     }
 335
 336     for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
 337          iter != _added_queue_items.end(); iter++) {
 338         bool found = false;
 339         for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
 340             if ( (*iterQueue)->cmp(*iter) == 0) {
 341                 found = true;
 342                 break;
 343             }
 344         }
 345         if (!found) {
 346             MIL << "add to queue" << *iter;
 347             queue.push_back(*iter);
 348         }
 349     }
 350
 351     // The application has to take care to write these solutions back to e.g. selectables in order
 352     // give the user a chance for changing these decisions again.
 353     _removed_queue_items.clear();
 354     _added_queue_items.clear();
 355
 356     return _satResolver->resolveQueue(queue, _addWeak);
 357 }
 358
 359 sat::Transaction Resolver::getTransaction()
 360 { return _satResolver->getTransaction(); }
 361
 362 //----------------------------------------------------------------------------
 363 // Getting more information about the solve results
 364
 365
 366 void Resolver::collectResolverInfo()
 367 {
 368     if ( _satResolver
 369          && _isInstalledBy.empty()
 370          && _installs.empty()) {
 371
 372         // generating new
 373         PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
 374
 375         for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
 376              instIter != itemsToInstall.end(); instIter++) {
 377             // Requires
 378             for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
 379             {
 380                 sat::WhatProvides possibleProviders(*capIt);
 381                 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
 382                     PoolItem provider = ResPool::instance().find( *iter );
 383
 384                     // searching if this provider will already be installed
 385                     bool found = false;
 386                     bool alreadySetForInstallation = false;
 387                     ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
 388                     while (pos != _isInstalledBy.end()
 389                            && pos->first == provider
 390                            && !found) {
 391                         alreadySetForInstallation = true;
 392                         ItemCapKind capKind = pos->second;
 393                         if (capKind.item == *instIter)  found = true;
 394                         pos++;
 395                     }
 396
 397                     if (!found
 398                         && provider.status().isToBeInstalled()) {
 399                         if (provider.status().isBySolver()) {
 400                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
 401                             _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 402                         } else {
 403                             // no initial installation cause it has been set be e.g. user
 404                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
 405                             _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 406                         }
 407                         ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
 408                         _installs.insert (make_pair( *instIter, capKindisInstalledBy));
 409                     }
 410
 411                     if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
 412                         ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
 413                         _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
 414
 415                         ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
 416                         _installedSatisfied.insert (make_pair( provider, installedSatisfied));
 417                     }
 418                 }
 419             }
 420
 421             if (!(_satResolver->onlyRequires())) {
 422                 //Recommends
 423                 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
 424                 {
 425                     sat::WhatProvides possibleProviders(*capIt);
 426                     for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
 427                         PoolItem provider = ResPool::instance().find( *iter );
 428
 429                         // searching if this provider will already be installed
 430                         bool found = false;
 431                         bool alreadySetForInstallation = false;
 432                         ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
 433                         while (pos != _isInstalledBy.end()
 434                                && pos->first == provider
 435                                && !found) {
 436                             alreadySetForInstallation = true;
 437                             ItemCapKind capKind = pos->second;
 438                             if (capKind.item == *instIter)  found = true;
 439                             pos++;
 440                         }
 441
 442                         if (!found
 443                             && provider.status().isToBeInstalled()) {
 444                             if (provider.status().isBySolver()) {
 445                                 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
 446                                 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 447                             } else {
 448                                 // no initial installation cause it has been set be e.g. user
 449                                 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
 450                                 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 451                             }
 452                             ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
 453                             _installs.insert (make_pair( *instIter, capKindisInstalledBy));
 454                         }
 455
 456                         if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
 457                             ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
 458                             _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
 459
 460                             ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
 461                             _installedSatisfied.insert (make_pair( provider, installedSatisfied));
 462                         }
 463                     }
 464                 }
 465
 466                 //Supplements
 467                 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
 468                 {
 469                     sat::WhatProvides possibleProviders(*capIt);
 470                     for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
 471                         PoolItem provider = ResPool::instance().find( *iter );
 472                         // searching if this item will already be installed
 473                         bool found = false;
 474                         bool alreadySetForInstallation = false;
 475                         ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
 476                         while (pos != _isInstalledBy.end()
 477                                && pos->first == *instIter
 478                                && !found) {
 479                             alreadySetForInstallation = true;
 480                             ItemCapKind capKind = pos->second;
 481                             if (capKind.item == provider)  found = true;
 482                             pos++;
 483                         }
 484
 485                         if (!found
 486                             && instIter->status().isToBeInstalled()) {
 487                             if (instIter->status().isBySolver()) {
 488                                 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
 489                                 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
 490                             } else {
 491                                 // no initial installation cause it has been set be e.g. user
 492                                 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
 493                                 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
 494                             }
 495                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
 496                             _installs.insert (make_pair( provider, capKindisInstalledBy));
 497                         }
 498
 499                         if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
 500                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
 501                             _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
 502
 503                             ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
 504                             _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
 505                         }
 506                     }
 507                 }
 508             }
 509         }
 510     }
 511 }
 512
 513
 514 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
 515 {
 516     ItemCapKindList ret;
 517     collectResolverInfo();
 518
 519     for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
 520         ItemCapKind info = iter->second;
 521         PoolItem iterItem = iter->first;
 522         if (iterItem == item) {
 523             ret.push_back(info);
 524             iter++;
 525         } else {
 526             // exit
 527             iter = _isInstalledBy.end();
 528         }
 529     }
 530     return ret;
 531 }
 532
 533 ItemCapKindList Resolver::installs( const PoolItem & item )
 534 {
 535     ItemCapKindList ret;
 536     collectResolverInfo();
 537
 538     for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
 539         ItemCapKind info = iter->second;
 540         PoolItem iterItem = iter->first;
 541         if (iterItem == item) {
 542             ret.push_back(info);
 543             iter++;
 544         } else {
 545             // exit
 546             iter = _installs.end();
 547         }
 548     }
 549     return ret;
 550 }
 551
 552 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
 553 {
 554     ItemCapKindList ret;
 555     collectResolverInfo();
 556
 557     for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
 558         ItemCapKind info = iter->second;
 559         PoolItem iterItem = iter->first;
 560         if (iterItem == item) {
 561             ret.push_back(info);
 562             iter++;
 563         } else {
 564             // exit
 565             iter = _satifiedByInstalled.end();
 566         }
 567     }
 568     return ret;
 569 }
 570
 571 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
 572 {
 573     ItemCapKindList ret;
 574     collectResolverInfo();
 575
 576     for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
 577         ItemCapKind info = iter->second;
 578         PoolItem iterItem = iter->first;
 579         if (iterItem == item) {
 580             ret.push_back(info);
 581             iter++;
 582         } else {
 583             // exit
 584             iter = _installedSatisfied.end();
 585         }
 586     }
 587     return ret;
 588 }
 589
 590
 591 ///////////////////////////////////////////////////////////////////
 592     };// namespace detail
 593     /////////////////////////////////////////////////////////////////////
 594     /////////////////////////////////////////////////////////////////////
 595   };// namespace solver
 596   ///////////////////////////////////////////////////////////////////////
 597   ///////////////////////////////////////////////////////////////////////
 598 };// namespace zypp
 599 /////////////////////////////////////////////////////////////////////////
 600