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