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