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
  22 #include "zypp/solver/detail/Resolver.h"
  23 #include "zypp/solver/detail/Helper.h"
  24
  25 #include "zypp/CapSet.h"
  26 #include "zypp/base/Logger.h"
  27 #include "zypp/base/String.h"
  28 #include "zypp/base/Gettext.h"
  29
  30 #include "zypp/base/Algorithm.h"
  31 #include "zypp/ResPool.h"
  32 #include "zypp/ResFilters.h"
  33 #include "zypp/CapFilters.h"
  34 #include "zypp/ZYppFactory.h"
  35 #include "zypp/SystemResObject.h"
  36
  37
  38 /////////////////////////////////////////////////////////////////////////
  39 namespace zypp
  40 { ///////////////////////////////////////////////////////////////////////
  41   ///////////////////////////////////////////////////////////////////
  42   namespace zypp_detail
  43   { /////////////////////////////////////////////////////////////////
  44     Arch defaultArchitecture();
  45     /////////////////////////////////////////////////////////////////
  46   } // namespace zypp_detail
  47   ///////////////////////////////////////////////////////////////////
  48
  49   ///////////////////////////////////////////////////////////////////////
  50   namespace solver
  51   { /////////////////////////////////////////////////////////////////////
  52     /////////////////////////////////////////////////////////////////////
  53     namespace detail
  54     { ///////////////////////////////////////////////////////////////////
  55
  56 using namespace std;
  57
  58 IMPL_PTR_TYPE(Resolver);
  59
  60 static const unsigned MAX_SECOND_RUNS( 3 );
  61 static const unsigned MAX_VALID_SOLUTIONS( 50 );
  62 static const unsigned TIMOUT_SECOND_RUN( 30 );
  63
  64 static PoolItemSet triggeredSolution;   // only the latest state of an item is interesting
  65                                         // for the pool. Documents already inserted items.
  66
  67 //---------------------------------------------------------------------------
  68
  69 class compare_items {
  70 public:
  71     int operator() (PoolItem_Ref p1,
  72                     PoolItem_Ref p2) const
  73         { return compareByNVRA(p1.resolvable(),p2.resolvable()) < 0; }
  74 };
  75
  76
  77 std::ostream &
  78 Resolver::dumpOn( std::ostream & os ) const
  79 {
  80     return os << "<resolver/>";
  81 }
  82
  83 // Generating a system resolvable in the pool in order to trigger
  84 // modaliases and hals
  85 void assertSystemResObjectInPool()
  86 {
  87   ResPool pool( getZYpp()->pool() );
  88   if ( pool.byKindBegin<SystemResObject>()
  89        == pool.byKindEnd<SystemResObject>() )
  90     {
  91       // SystemResObject is missing in the pool ==> insert
  92       ResStore store;
  93       store.insert( SystemResObject::instance() );
  94       getZYpp()->addResolvables( store, true ); // true = is installed
  95     }
  96
  97   // set lock
  98   if ( ! pool.byKindBegin<SystemResObject>()
  99          ->status().setLock( true, ResStatus::USER ) )
 100     {
 101       WAR << "Unable to set SystemResObject to lock" << endl;
 102     }
 103 }
 104
 105 //---------------------------------------------------------------------------
 106
 107 Resolver::Resolver (const ResPool & pool)
 108     : _pool (pool)
 109     , _timeout_seconds (0)
 110     , _maxSolverPasses (0)
 111     , _verifying (false)
 112     , _testing (false)
 113     , _tryAllPossibilities (false)
 114     , _valid_solution_count (0)
 115     , _best_context (NULL)
 116     , _establish_context (NULL)
 117     , _timed_out (false)
 118     , _architecture( zypp_detail::defaultArchitecture() )
 119     , _forceResolve (false)
 120     , _upgradeMode (false)
 121     , _preferHighestVersion (true)
 122
 123 {}
 124
 125
 126 Resolver::~Resolver()
 127 {
 128 }
 129
 130 //---------------------------------------------------------------------------
 131
 132 ResPool
 133 Resolver::pool (void) const
 134 {
 135     return _pool;
 136 }
 137
 138 void
 139 Resolver::reset (void)
 140 {
 141     _verifying = false;
 142
 143     _initial_items.clear();
 144
 145     _items_to_install.clear();
 146     _items_to_remove.clear();
 147     _items_to_verify.clear();
 148     _items_to_establish.clear();
 149
 150     _extra_caps.clear();
 151     _extra_conflicts.clear();
 152
 153     _pending_queues.clear();
 154     _pruned_queues.clear();
 155     _complete_queues.clear();
 156     _deferred_queues.clear();
 157     _invalid_queues.clear();
 158
 159     _valid_solution_count = 0;
 160
 161     _best_context = NULL;
 162     _timed_out = false;
 163
 164 }
 165
 166
 167 ResolverContext_Ptr
 168 Resolver::context (void) const
 169 {
 170     if (_best_context) return _best_context;
 171     if (_invalid_queues.empty()) return NULL;
 172     ResolverQueue_Ptr invalid = _invalid_queues.front();
 173     return invalid->context();
 174 }
 175
 176 void  Resolver::dumpTaskList(const PoolItemList &install, const PoolItemList &remove )
 177 {
 178     for (PoolItemList::const_iterator iter = install.begin();
 179          iter != install.end(); iter++) {
 180         DBG << "    to_install " << *iter << endl;
 181     }
 182     for (PoolItemList::const_iterator iter = remove.begin();
 183          iter != remove.end(); iter++) {
 184         DBG << "    to_remove " << *iter << endl;
 185     }
 186 }
 187
 188
 189 //---------------------------------------------------------------------------
 190
 191 void
 192 Resolver::addSubscribedSource (Source_Ref source)
 193 {
 194     _subscribed.insert(source);
 195 }
 196
 197 void
 198 Resolver::addPoolItemToInstall (PoolItem_Ref item)
 199 {
 200     bool found = false;
 201     for (PoolItemList::const_iterator iter = _items_to_remove.begin();
 202          iter != _items_to_remove.end(); iter++) {
 203         if (*iter == item) {
 204             _items_to_remove.remove(*iter);
 205             found = true;
 206             break;
 207         }
 208     }
 209     if (!found) {
 210         _items_to_install.push_back (item);
 211         _items_to_install.unique ();
 212     }
 213 }
 214
 215
 216 void
 217 Resolver::addPoolItemsToInstallFromList (PoolItemList & rl)
 218 {
 219     for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) {
 220         addPoolItemToInstall (*iter);
 221     }
 222 }
 223
 224
 225 void
 226 Resolver::addPoolItemToRemove (PoolItem_Ref item)
 227 {
 228     bool found = false;
 229     for (PoolItemList::const_iterator iter = _items_to_install.begin();
 230          iter != _items_to_install.end(); iter++) {
 231         if (*iter == item) {
 232             _items_to_install.remove(*iter);
 233             found = true;
 234             break;
 235         }
 236     }
 237     if (!found) {
 238         _items_to_remove.push_back (item);
 239         _items_to_remove.unique ();
 240     }
 241 }
 242
 243
 244 void
 245 Resolver::addPoolItemsToRemoveFromList (PoolItemList & rl)
 246 {
 247     for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) {
 248         addPoolItemToRemove (*iter);
 249     }
 250 }
 251
 252 void
 253 Resolver::addPoolItemToLockUninstalled (PoolItem_Ref item)
 254 {
 255     _items_to_lockUninstalled.push_back (item);
 256     _items_to_lockUninstalled.unique ();
 257 }
 258
 259
 260 void
 261 Resolver::addPoolItemToEstablish (PoolItem_Ref item)
 262 {
 263     _items_to_establish.push_back (item);
 264 }
 265
 266
 267 void
 268 Resolver::addPoolItemsToEstablishFromList (PoolItemList & rl)
 269 {
 270     for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) {
 271         addPoolItemToEstablish (*iter);
 272     }
 273 }
 274
 275
 276 void
 277 Resolver::addPoolItemToVerify (PoolItem_Ref item)
 278 {
 279 #if 0
 280   /** Order PoolItems based on name and edition only. */
 281   struct {
 282     /** 'less then' based on name and edition */
 283     bool operator()( PoolItem_Ref lhs, PoolItem_Ref rhs ) const
 284     {
 285       int res = lhs->name().compare( rhs->name() );
 286       if ( res )
 287         return res == -1; // lhs < rhs ?
 288       // here: lhs == rhs, so compare edition:
 289       return lhs->edition() < rhs->edition();
 290     }
 291   } order;
 292 #endif
 293
 294     _items_to_verify.push_back (item);
 295
 296 #warning Should order by name (and probably edition since with zypp we could have multiple editions installed in parallel)
 297 //    _items_to_verify.sort (order);                    //(GCompareFunc) rc_item_compare_name);
 298 }
 299
 300
 301 void
 302 Resolver::addExtraCapability (const Capability & capability)
 303 {
 304     _extra_caps.insert (capability);
 305 }
 306
 307
 308 void
 309 Resolver::addExtraConflict (const Capability & capability)
 310 {
 311     _extra_conflicts.insert (capability);
 312 }
 313
 314
 315 void
 316 Resolver::addIgnoreConflict (const PoolItem_Ref item,
 317                    const Capability & capability)
 318 {
 319     _ignoreConflicts.insert(make_pair(item, capability));
 320 }
 321
 322
 323 void
 324 Resolver::addIgnoreRequires (const PoolItem_Ref item,
 325                              const Capability & capability)
 326 {
 327     _ignoreRequires.insert(make_pair(item, capability));
 328 }
 329
 330 void
 331 Resolver::addIgnoreObsoletes (const PoolItem_Ref item,
 332                               const Capability & capability)
 333 {
 334     _ignoreObsoletes.insert(make_pair(item, capability));
 335 }
 336
 337 void
 338 Resolver::addIgnoreInstalledItem (const PoolItem_Ref item)
 339 {
 340     _ignoreInstalledItem.push_back (item);
 341 }
 342
 343 void
 344 Resolver::addIgnoreArchitectureItem (const PoolItem_Ref item)
 345 {
 346     _ignoreArchitectureItem.push_back (item);
 347 }
 348
 349
 350 //---------------------------------------------------------------------------
 351
 352 struct UndoTransact : public resfilter::PoolItemFilterFunctor
 353 {
 354     ResStatus::TransactByValue resStatus;
 355     UndoTransact ( const ResStatus::TransactByValue &status)
 356         :resStatus(status)
 357     { }
 358
 359     bool operator()( PoolItem_Ref item )                // only transacts() items go here
 360     {
 361         item.status().resetTransact( resStatus );// clear any solver/establish transactions
 362         return true;
 363     }
 364 };
 365
 366
 367 struct DoTransact : public resfilter::PoolItemFilterFunctor
 368 {
 369     ResStatus::TransactByValue resStatus;
 370     DoTransact ( const ResStatus::TransactByValue &status)
 371         :resStatus(status)
 372     { }
 373
 374     bool operator()( PoolItem_Ref item )                // only transacts() items go here
 375     {
 376         item.status().setTransact( true, resStatus );
 377         return true;
 378     }
 379 };
 380
 381
 382 struct VerifySystem : public resfilter::PoolItemFilterFunctor
 383 {
 384     Resolver & resolver;
 385
 386     VerifySystem (Resolver & r)
 387         : resolver (r)
 388     { }
 389
 390     bool operator()( PoolItem_Ref provider )
 391     {
 392         resolver.addPoolItemToVerify (provider);
 393         return true;
 394     }
 395 };
 396
 397 bool
 398 Resolver::verifySystem (bool considerNewHardware)
 399 {
 400     UndoTransact resetting (ResStatus::APPL_HIGH);
 401
 402     _DEBUG ("Resolver::verifySystem() " << (considerNewHardware ? "consider new hardware":""));
 403
 404     invokeOnEach ( _pool.begin(), _pool.end(),
 405                    resfilter::ByTransact( ),                    // Resetting all transcations
 406                    functor::functorRef<bool,PoolItem>(resetting) );
 407
 408     VerifySystem info (*this);
 409
 410     invokeOnEach( pool().byKindBegin( ResTraits<Package>::kind ),
 411                   pool().byKindEnd( ResTraits<Package>::kind ),
 412                   resfilter::ByInstalled ( ),
 413                   functor::functorRef<bool,PoolItem>(info) );
 414
 415     invokeOnEach( pool().byKindBegin( ResTraits<Pattern>::kind ),
 416                   pool().byKindEnd( ResTraits<Pattern>::kind ),
 417                   resfilter::ByInstalled ( ),
 418                   functor::functorRef<bool,PoolItem>(info) );
 419
 420
 421     _verifying = true;
 422
 423     bool success = false;
 424
 425     if (considerNewHardware) {
 426         // evaluate all Freshens/Supplements and solve
 427         success = freshenPool(false) && bestContext() && bestContext()->isValid();
 428     }
 429     else {
 430         success = resolveDependencies (); // do solve only
 431     }
 432
 433     DoTransact setting (ResStatus::APPL_HIGH);
 434
 435     invokeOnEach ( _pool.begin(), _pool.end(),
 436                    resfilter::ByTransact( ),
 437                    functor::functorRef<bool,PoolItem>(setting) );
 438
 439     return success;
 440 }
 441
 442
 443 //---------------------------------------------------------------------------
 444
 445 // copy marked item from solution back to pool
 446 // if data != NULL, set as APPL_LOW (from establishPool())
 447
 448 static void
 449 solution_to_pool (PoolItem_Ref item, const ResStatus & status, void *data)
 450 {
 451     if (triggeredSolution.find(item) != triggeredSolution.end()) {
 452         _XDEBUG("solution_to_pool(" << item << ") is already in the pool --> skip");
 453         return;
 454     }
 455
 456     triggeredSolution.insert(item);
 457
 458     // resetting transaction only
 459     item.status().resetTransact((data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER );
 460
 461     bool r;
 462
 463     if (status.isToBeInstalled()) {
 464         r = item.status().setToBeInstalled( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER );
 465         _XDEBUG("solution_to_pool(" << item << ", " << status << ") install !" << r);
 466     }
 467     else if (status.isToBeUninstalledDueToUpgrade()) {
 468         r = item.status().setToBeUninstalledDueToUpgrade( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER );
 469         _XDEBUG("solution_to_pool(" << item << ", " << status << ") upgrade !" << r);
 470     }
 471     else if (status.isToBeUninstalled()) {
 472         r = item.status().setToBeUninstalled( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER );
 473         _XDEBUG("solution_to_pool(" << item << ", " << status << ") remove !" << r);
 474     }
 475     else if (status.isIncomplete()
 476              || status.isNeeded()) {
 477         r = item.status().setIncomplete();
 478         _XDEBUG("solution_to_pool(" << item << ", " << status << ") incomplete !" << r);
 479     }
 480     else if (status.isUnneeded()) {
 481         r = item.status().setUnneeded();
 482         _XDEBUG("solution_to_pool(" << item << ", " << status << ") unneeded !" << r);
 483     }
 484     else if (status.isSatisfied()) {
 485         r = item.status().setSatisfied();
 486         _XDEBUG("solution_to_pool(" << item << ", " << status << ") satisfied !" << r);
 487     } else {
 488         _XDEBUG("solution_to_pool(" << item << ", " << status << ") unchanged !");
 489     }
 490     return;
 491 }
 492
 493
 494 //---------------------------------------------------------------------------
 495 // establish state
 496
 497 struct EstablishState
 498 {
 499     Resolver & resolver;
 500
 501     EstablishState (Resolver & r)
 502         : resolver (r)
 503     { }
 504
 505     bool operator()( PoolItem_Ref provider )
 506     {
 507         resolver.addPoolItemToEstablish (provider);
 508         return true;
 509     }
 510 };
 511
 512
 513 void
 514 Resolver::establishState( ResolverContext_Ptr context )
 515 {
 516     _DEBUG( "Resolver::establishState ()" );
 517     typedef list<Resolvable::Kind> KindList;
 518     static KindList ordered;
 519     if (ordered.empty()) {
 520         ordered.push_back (ResTraits<zypp::Atom>::kind);
 521         ordered.push_back (ResTraits<zypp::Message>::kind);
 522         ordered.push_back (ResTraits<zypp::Script>::kind);
 523         ordered.push_back (ResTraits<zypp::Patch>::kind);
 524         ordered.push_back (ResTraits<zypp::Pattern>::kind);
 525         ordered.push_back (ResTraits<zypp::Product>::kind);
 526     }
 527
 528     if (context == NULL)
 529         context = new ResolverContext(_pool, _architecture);
 530
 531     context->setEstablishing (true);
 532     context->setIgnoreCababilities (_ignoreConflicts,
 533                                     _ignoreRequires,
 534                                     _ignoreObsoletes,
 535                                     _ignoreInstalledItem,
 536                                     _ignoreArchitectureItem);
 537     context->setForceResolve( _forceResolve );
 538     context->setEstablishContext( _establish_context );
 539     context->setPreferHighestVersion ( _preferHighestVersion );
 540     context->setUpgradeMode( _upgradeMode );
 541
 542     for (KindList::const_iterator iter = ordered.begin(); iter != ordered.end(); iter++) {
 543         const Resolvable::Kind kind = *iter;
 544
 545         _XDEBUG( "establishing state for kind " << kind.asString() );
 546
 547         //world()->foreachResItemByKind (kind, trial_establish_cb, this);
 548
 549         EstablishState info (*this);
 550
 551         invokeOnEach( pool().byKindBegin( kind ),
 552                       pool().byKindEnd( kind ),
 553                       functor::functorRef<bool,PoolItem>(info) );
 554
 555         // process the queue
 556         resolveDependencies( context );
 557
 558         reset();
 559     }
 560
 561     context->setEstablishing (false);
 562
 563     _best_context = context;
 564     _establish_context = context;
 565
 566     return;
 567 }
 568
 569
 570 bool
 571 Resolver::establishPool ()
 572 {
 573     MIL << "Resolver::establishPool()" << endl;
 574
 575     establishState ();                                          // establish !
 576     ResolverContext_Ptr solution = bestContext();
 577
 578     if (solution) {                                             // copy solution back to pool
 579         triggeredSolution.clear();
 580         solution->foreachMarked (solution_to_pool, (void *)1);  // as APPL_LOW
 581     }
 582     else {
 583         ERR << "establishState did not return a bestContext" << endl;
 584         return false;
 585     }
 586
 587     return true;
 588 }
 589
 590
 591 //---------------------------------------------------------------------------
 592 // freshen state
 593
 594 typedef map<string, PoolItem_Ref> FreshenMap;
 595
 596 // add item to itemmap
 597 //  check for item with same name and only keep
 598 //  best architecture, best version
 599
 600 static void
 601 addToFreshen( PoolItem_Ref item, FreshenMap & itemmap )
 602 {
 603     FreshenMap::iterator it = itemmap.find( item->name() );
 604     if (it != itemmap.end()) {                                  // item with same name found
 605         int cmp = it->second->arch().compare( item->arch() );
 606         if (cmp < 0) {                                          // new item has better arch
 607             it->second = item;
 608         }
 609         else if (cmp == 0) {                                    // new item has equal arch
 610             if (it->second->edition().compare( item->edition() ) < 0) {
 611                 it->second = item;                              // new item has better edition
 612             }
 613         }
 614     }
 615     else {
 616         itemmap[item->name()] = item;
 617     }
 618     return;
 619 }
 620
 621
 622 struct FreshenState
 623 {
 624     FreshenMap itemmap;
 625
 626     FreshenState()
 627     { }
 628
 629     bool operator()( PoolItem_Ref item)
 630     {
 631         CapSet freshens( item->dep( Dep::FRESHENS ) );
 632         if (!freshens.empty()) {
 633             addToFreshen( item, itemmap );
 634         }
 635         else {                                  // if no freshens, look at supplements
 636             // Also regarding supplements e.g. in order to recognize
 637             // modalias dependencies. Bug #163140
 638             CapSet supplements( item->dep( Dep::SUPPLEMENTS ) );
 639             if (!supplements.empty()) {
 640                 addToFreshen( item, itemmap );
 641             }
 642         }
 643         return true;
 644     }
 645 };
 646
 647
 648 void
 649 Resolver::freshenState( ResolverContext_Ptr context,
 650                         bool resetAfterSolve )
 651 {
 652     _DEBUG( "Resolver::freshenState ()" );
 653
 654     if (context == NULL)
 655         context = new ResolverContext( _pool, _architecture );
 656
 657     context->setEstablishing( true );
 658     context->setIgnoreCababilities( _ignoreConflicts,
 659                                     _ignoreRequires,
 660                                     _ignoreObsoletes,
 661                                     _ignoreInstalledItem,
 662                                     _ignoreArchitectureItem );
 663     context->setForceResolve( _forceResolve );
 664     context->setEstablishContext( _establish_context );
 665     context->setPreferHighestVersion( _preferHighestVersion );
 666     context->setUpgradeMode( _upgradeMode );
 667
 668     FreshenState info;
 669
 670     // collect items to be established
 671
 672     invokeOnEach( pool().byKindBegin( ResTraits<zypp::Package>::kind ),
 673                       pool().byKindEnd( ResTraits<zypp::Package>::kind ),
 674                       functor::functorRef<bool,PoolItem>(info) );
 675
 676     // schedule all collected items for establish
 677
 678     for (FreshenMap::iterator it = info.itemmap.begin(); it != info.itemmap.end(); ++it) {
 679         addPoolItemToEstablish( it->second );
 680     }
 681
 682     // process the queue
 683     resolveDependencies( context );
 684
 685     if (resetAfterSolve) {
 686         reset();
 687         context->setEstablishing( false );
 688         _best_context = context;
 689     }
 690
 691     return;
 692 }
 693
 694
 695 bool
 696 Resolver::freshenPool (bool resetAfterSolve)
 697 {
 698     MIL << "Resolver::freshenPool()" << endl;
 699
 700     freshenState (NULL, resetAfterSolve);       // establish all packages with freshens; (NULL)= no initial context
 701     ResolverContext_Ptr solution = bestContext();
 702
 703     if (solution) {                                             // copy solution back to pool
 704         triggeredSolution.clear();
 705         solution->foreachMarked (solution_to_pool, (void *)1);  // as APPL_LOW
 706     }
 707     else {
 708         ERR << "freshenState did not return a bestContext" << endl;
 709         return false;
 710     }
 711
 712     return true;
 713 }
 714
 715 //---------------------------------------------------------------------------
 716
 717 bool
 718 Resolver::resolveDependencies (const ResolverContext_Ptr context)
 719 {
 720
 721     time_t t_start, t_now;
 722
 723     MIL << "Resolver::resolveDependencies()" << endl;
 724
 725     _pending_queues.clear();
 726     _pruned_queues.clear();
 727     _complete_queues.clear();
 728     _deferred_queues.clear();
 729     _invalid_queues.clear();
 730     _valid_solution_count = 0;
 731     _best_context = NULL;
 732
 733 #warning local items disabled
 734 #if 0
 735     bool have_local_items = false;
 736
 737     /* Walk through are list of to-be-installed packages and see if any of them are local. */
 738
 739     for (PoolItemList::const_iterator iter = _items_to_install.begin(); iter != _items_to_install.end(); iter++) {
 740         if ((*iter)->local()) {
 741             have_local_items = true;
 742             break;
 743         }
 744     }
 745
 746     World_Ptr the_world = world();
 747     StoreWorld_Ptr local_world = NULL;
 748     MultiWorld_Ptr local_multiworld = NULL;
 749
 750     Channel_Ptr local_channel = NULL;
 751
 752     if (have_local_items) {
 753         local_multiworld = new MultiWorld();
 754         local_world = new StoreWorld();
 755
 756         local_channel = new Channel ("", "Local ResItems", "@local", "");
 757
 758         local_world->addChannel (local_channel);
 759
 760         local_multiworld->addSubworld (local_world);
 761         local_multiworld->addSubworld (the_world);
 762
 763         the_world = local_multiworld;
 764     }
 765 #endif
 766
 767     // create initial_queue
 768
 769     ResolverQueue_Ptr initial_queue = new ResolverQueue(_pool, _architecture, context);
 770
 771     // adding "external" provides, the the requirements will be ignored
 772     IgnoreMap ignoreRequires = _ignoreRequires;
 773     ResPool::AdditionalCapSet additionalCapSet = pool().additionaProvide();
 774     for (ResPool::AdditionalCapSet::const_iterator it = additionalCapSet.begin();
 775          it != additionalCapSet.end(); it++) {
 776         CapSet cset = it->second;
 777         for (CapSet::const_iterator cit = cset.begin(); cit != cset.end(); ++cit) {
 778             ignoreRequires.insert(make_pair(PoolItem_Ref(), *cit));
 779         }
 780     }
 781
 782     // Initialize all ignoring dependencies
 783     initial_queue->context()->setIgnoreCababilities (_ignoreConflicts,
 784                                                      ignoreRequires,
 785                                                      _ignoreObsoletes,
 786                                                      _ignoreInstalledItem,
 787                                                      _ignoreArchitectureItem);
 788     initial_queue->context()->setForceResolve( _forceResolve );
 789     initial_queue->context()->setEstablishContext( _establish_context );
 790     initial_queue->context()->setPreferHighestVersion( _preferHighestVersion );
 791     initial_queue->context()->setUpgradeMode( _upgradeMode );
 792     initial_queue->context()->setTryAllPossibilities( _tryAllPossibilities );
 793
 794     /* If this is a verify, we do a "soft resolution" */
 795
 796     initial_queue->context()->setVerifying( _verifying );
 797
 798     /* Add extra items. */
 799
 800     for (QueueItemList::const_iterator iter = _initial_items.begin(); iter != _initial_items.end(); iter++) {
 801         initial_queue->addItem (*iter);
 802     }
 803
 804     for (PoolItemList::const_iterator iter = _items_to_install.begin(); iter != _items_to_install.end(); iter++) {
 805         PoolItem_Ref r = *iter;
 806
 807 #warning local items disabled
 808 #if 0
 809         /* Add local packages to our dummy channel. */
 810         if (r->local()) {
 811             assert (local_channel != NULL);
 812             ResItem_Ptr r1 = const_pointer_cast<ResItem>(r);
 813             r1->setChannel (local_channel);
 814             local_world->addPoolItem_Ref (r);
 815         }
 816 #endif
 817         initial_queue->addPoolItemToInstall (r);
 818     }
 819
 820     for (PoolItemList::const_iterator iter = _items_to_remove.begin(); iter != _items_to_remove.end(); iter++) {
 821         if (!_upgradeMode)
 822             initial_queue->addPoolItemToRemove (*iter, true /* remove-only mode */);
 823         else
 824             //   Checking old dependencies for packages which will be updated.
 825             //   E.g. foo provides a dependecy which foo-new does not provides anymore.
 826             //   So check, if there is a packages installed which requires foo.
 827             //   Testcase exercise-bug150844-test.xml
 828             //   Testcase Bug156439-test.xml
 829             initial_queue->addPoolItemToRemove (*iter, false /* no remove-only mode */);
 830     }
 831
 832     for (PoolItemList::const_iterator iter = _items_to_verify.begin(); iter != _items_to_verify.end(); iter++) {
 833         initial_queue->addPoolItemToVerify (*iter);
 834     }
 835
 836     for (PoolItemList::const_iterator iter = _items_to_establish.begin(); iter != _items_to_establish.end(); iter++) {
 837         initial_queue->addPoolItemToEstablish (*iter);
 838     }
 839
 840     for (CapSet::const_iterator iter = _extra_caps.begin(); iter != _extra_caps.end(); iter++) {
 841         initial_queue->addExtraCapability (*iter);
 842     }
 843
 844     // adding "external" requires
 845     additionalCapSet = pool().additionalRequire();
 846     for (ResPool::AdditionalCapSet::const_iterator it = additionalCapSet.begin();
 847          it != additionalCapSet.end(); it++) {
 848         CapSet cset = it->second;
 849         for (CapSet::const_iterator cit = cset.begin(); cit != cset.end(); ++cit) {
 850             initial_queue->addExtraCapability (*cit);
 851         }
 852     }
 853
 854     for (CapSet::const_iterator iter = _extra_conflicts.begin(); iter != _extra_conflicts.end(); iter++) {
 855         initial_queue->addExtraConflict (*iter);
 856     }
 857
 858     // adding "external" conflicts
 859     additionalCapSet = pool().additionaConflict();
 860     for (ResPool::AdditionalCapSet::const_iterator it = additionalCapSet.begin();
 861          it != additionalCapSet.end(); it++) {
 862         CapSet cset = it->second;
 863         for (CapSet::const_iterator cit = cset.begin(); cit != cset.end(); ++cit) {
 864             initial_queue->addExtraConflict (*cit);
 865         }
 866     }
 867
 868     // Adding System resolvable
 869     assertSystemResObjectInPool();
 870
 871     _XDEBUG( "Initial Queue: [" << *initial_queue << "]" );
 872
 873     if (initial_queue->isEmpty()) {
 874         INT << "Empty Queue, nothing to resolve" << endl;
 875         _best_context = context; // Taking old context
 876         return true;
 877     }
 878
 879     _best_context = NULL;
 880
 881     _pending_queues.push_front (initial_queue);
 882
 883     time (&t_start);
 884
 885     while (!_pending_queues.empty()) {
 886
 887         _DEBUG( "Pend " << (long) _pending_queues.size()
 888                 << " / Cmpl " << (long) _complete_queues.size()
 889                 << " / Prun " << (long) _pruned_queues.size()
 890                 << " / Defr " << (long) _deferred_queues.size()
 891                 << " / Invl " << (long) _invalid_queues.size() );
 892
 893         if (_timeout_seconds > 0) {
 894             time (&t_now);
 895             if (difftime (t_now, t_start) > _timeout_seconds) {
 896                 _timed_out = true;
 897                 MIL << "Timeout " << _timeout_seconds << " seconds reached"
 898                     << " -> exit" << endl;
 899                 break;
 900             }
 901         }
 902         if (_maxSolverPasses > 0) {
 903             if (_maxSolverPasses <= _complete_queues.size() +
 904                 _pruned_queues.size() +
 905                 _deferred_queues.size() +
 906                 _invalid_queues.size()) {
 907                 _timed_out = true;
 908                 MIL << "Max solver runs ( " << _maxSolverPasses
 909                     << " ) reached -> exit" << endl;
 910                 break;
 911             }
 912         }
 913
 914         if (_best_context != NULL
 915             && _complete_queues.size() >= MAX_VALID_SOLUTIONS) {
 916                 MIL << "Max VALID solver runs ( " << MAX_VALID_SOLUTIONS
 917                     << " ) reached -> exit" << endl;
 918                 break;
 919         }
 920
 921         ResolverQueue_Ptr queue = _pending_queues.front();
 922         _pending_queues.pop_front();
 923         ResolverContext_Ptr context = queue->context();
 924
 925         queue->process();
 926
 927         if (queue->isInvalid ()) {
 928
 929             _XDEBUG( "Invalid Queue\n" );
 930             _invalid_queues.push_back(queue);
 931
 932         } else if (queue->isEmpty ()) {
 933
 934             _XDEBUG( "Empty Queue\n" );
 935
 936             _complete_queues.push_back(queue);
 937
 938             ++_valid_solution_count;
 939
 940             /* Compare this solution to our previous favorite.  In the case of a tie,
 941                the first solution wins --- yeah, I know this is lame, but it shouldn't
 942                be an issue too much of the time. */
 943
 944             if (_best_context == NULL
 945                 || _best_context->compare (context) < 0)
 946             {
 947                 _best_context = context;
 948             }
 949
 950         } else if (_best_context != NULL
 951                    && _best_context->partialCompare (context) > 0) {
 952
 953             /* If we aren't currently as good as our previous best complete solution,
 954                this solution gets pruned. */
 955
 956             _XDEBUG( "PRUNED!" );
 957
 958             _pruned_queues.push_back(queue);
 959
 960         } else {
 961
 962             /* If our queue is isn't empty and isn't invalid, that can only mean
 963                one thing: we are down to nothing but branches. */
 964
 965             queue->splitFirstBranch (_pending_queues, _deferred_queues);
 966         }
 967
 968         /* If we have run out of pending queues w/o finding any solutions,
 969            and if we have deferred queues, make the first deferred queue
 970            pending. */
 971
 972         if (_pending_queues.empty()
 973             && _complete_queues.empty()
 974             && !_deferred_queues.empty()) {
 975             _pending_queues.push_back(_deferred_queues.front());
 976         }
 977     }
 978     _DEBUG("Pend " << (long) _pending_queues.size()
 979            << " / Cmpl " << (long) _complete_queues.size()
 980            << " / Prun " << (long) _pruned_queues.size()
 981            << " / Defr " << (long) _deferred_queues.size()
 982            << " / Invl " << (long) _invalid_queues.size() );
 983
 984     return _best_context && _best_context->isValid();
 985 }
 986
 987
 988 //----------------------------------------------------------------------------
 989 // undo
 990
 991 void
 992 Resolver::undo(void)
 993 {
 994     UndoTransact info(ResStatus::APPL_LOW);
 995     MIL << "*** undo ***" << endl;
 996     invokeOnEach ( _pool.begin(), _pool.end(),
 997                    resfilter::ByTransact( ),                    // collect transacts from Pool to resolver queue
 998                    functor::functorRef<bool,PoolItem>(info) );
 999     // These conflict should be ignored of the concering item
1000     _ignoreConflicts.clear();
1001     // These requires should be ignored of the concering item
1002     _ignoreRequires.clear();
1003     // These obsoletes should be ignored of the concering item
1004     _ignoreObsoletes.clear();
1005     // Ignore architecture of the item
1006     _ignoreArchitecture.clear();
1007     // Ignore the status "installed" of the item
1008     _ignoreInstalledItem.clear();
1009     // Ignore the architecture of the item
1010     _ignoreArchitectureItem.clear();
1011
1012
1013     return;
1014 }
1015
1016 //----------------------------------------------------------------------------
1017 // resolvePool
1018
1019 struct CollectTransact : public resfilter::PoolItemFilterFunctor
1020 {
1021     Resolver & resolver;
1022
1023     CollectTransact (Resolver & r)
1024         : resolver (r)
1025     { }
1026
1027     bool operator()( PoolItem_Ref item )                // only transacts() items go here
1028     {
1029         ResStatus status = item.status();
1030         _XDEBUG( "CollectTransact(" << item << ")" );
1031         bool by_solver = (status.isBySolver() || status.isByApplLow());
1032
1033         if (by_solver) {
1034             _XDEBUG("Resetting " << item );
1035             item.status().resetTransact( ResStatus::APPL_LOW );// clear any solver/establish transactions
1036             return true;                                // back out here, dont re-queue former solver result
1037         }
1038
1039         if (status.isToBeInstalled()) {
1040             resolver.addPoolItemToInstall(item);        // -> install!
1041         }
1042         if (status.isToBeUninstalled()) {
1043             resolver.addPoolItemToRemove(item);         // -> remove !
1044         }
1045         if (status.isIncomplete()) {                    // incomplete (re-install needed)
1046             PoolItem_Ref reinstall = Helper::findReinstallItem (resolver.pool(), item);
1047             if (reinstall) {
1048                 MIL << "Reinstall " << reinstall << " for incomplete " << item << endl;
1049                 resolver.addPoolItemToInstall(reinstall);       // -> install!
1050             }
1051             else {
1052                 WAR << "Can't find " << item << " for re-installation" << endl;
1053             }
1054         }
1055
1056         if (status.isLocked()
1057             && status.isUninstalled()) {
1058             // This item could be selected by solver in a former run. Now it
1059             // is locked. So we will have to evaluate a new solver run.
1060             resolver.addPoolItemToLockUninstalled (item);
1061         }
1062
1063         return true;
1064     }
1065 };
1066
1067
1068 static void
1069 show_pool( ResPool pool )
1070 {
1071     int count = 1;
1072     static bool full_pool_shown = true;
1073
1074     _XDEBUG( "---------------------------------------" );
1075     for (ResPool::const_iterator it = pool.begin(); it != pool.end(); ++it, ++count) {
1076
1077         if (!full_pool_shown                                    // show item if not shown all before
1078             || it->status().transacts()                         // or transacts
1079             || !it->status().isUndetermined())                  // or established status
1080         {
1081             _DEBUG( count << ": " << *it );
1082         }
1083     }
1084     _XDEBUG( "---------------------------------------" );
1085     full_pool_shown = true;
1086 }
1087
1088 //  This function loops over the pool and grabs
1089 //  all item.status().transacts() and item.status().byUser()
1090 //  It clears all previous bySolver() states also
1091 //
1092 //  Every toBeInstalled is passed to zypp::solver:detail::Resolver.addPoolItemToInstall()
1093 //  Every toBeUninstalled is passed to zypp::solver:detail::Resolver.addPoolItemToRemove()
1094 //
1095 //  Then zypp::solver:detail::Resolver.resolveDependencies() is called.
1096 //
1097 //  zypp::solver:detail::Resolver then returns a ResolverContext via bestContext() which
1098 //  describes the best solution. If bestContext() is NULL, no solution was found.
1099 //
1100 //  ResolverContext has a foreachMarked() iterator function which loops over all
1101 //  items of the solutions. These must be written back to the pool.
1102
1103
1104 bool
1105 Resolver::resolvePool( bool tryAllPossibilities )
1106 {
1107     ResolverContext_Ptr saveContext = _best_context;
1108     CollectTransact info (*this);
1109
1110     // cleanup before next run
1111     reset();
1112
1113     bool saveTryAllPossibilities = _tryAllPossibilities;
1114
1115     if (tryAllPossibilities) {
1116         _tryAllPossibilities = tryAllPossibilities;
1117     }
1118
1119     if (_tryAllPossibilities) {
1120         MIL << "================================================================"
1121             << endl;
1122         MIL << "Solver run with ALL possibilities"
1123             << endl;
1124         if (_maxSolverPasses <= 0)
1125             _maxSolverPasses = MAX_SECOND_RUNS;
1126         if (_timeout_seconds <= 0)
1127             _timeout_seconds = TIMOUT_SECOND_RUN;
1128
1129         MIL << "But no longer than " << MAX_SECOND_RUNS << " runs or "
1130             << TIMOUT_SECOND_RUN << " seconds" << endl;
1131         MIL << "================================================================" << endl;
1132     }
1133
1134 #if 1
1135
1136     MIL << "Resolver::resolvePool()" << endl;
1137     _XDEBUG( "Pool before resolve" );
1138     show_pool( _pool );
1139
1140 #endif
1141     invokeOnEach ( _pool.begin(), _pool.end(),
1142                    resfilter::ByTransact( ),                    // collect transacts from Pool to resolver queue
1143                    functor::functorRef<bool,PoolItem>(info) );
1144
1145     invokeOnEach ( _pool.begin(), _pool.end(),
1146                    resfilter::ByLock( ),                        // collect locks from Pool to resolver queue
1147                    functor::functorRef<bool,PoolItem>(info) );
1148     // List of installing/removing items of the complete run (not regarding a recycled solver run)
1149     PoolItemList _completeItems_to_install = _items_to_install;
1150     PoolItemList _completeItems_to_remove = _items_to_remove;
1151     PoolItemList _completeItems_to_lockUninstalled = _items_to_lockUninstalled;
1152
1153     // We have to find a valid context in order to recycle it.
1154     saveContext = contextPool.findContext (_items_to_install, _items_to_remove, _items_to_lockUninstalled);
1155     // _items_to_install, _items_to_remove contains addition items which has been selected but are
1156     // not solved with that context. They will be solved now.
1157     // If we have not found any former fitting context, saveContext is NULL. So the solver
1158     // make a complete run
1159
1160     if (saveContext != NULL) {
1161         // create a new context in order not overwriting the old
1162         saveContext = new ResolverContext (saveContext->pool(), saveContext->architecture(), saveContext);
1163         saveContext->setTryAllPossibilities( true );
1164     }
1165
1166     bool have_solution = resolveDependencies (saveContext);             // resolve !
1167
1168     if (have_solution) {                                        // copy solution back to pool
1169         MIL << "Have solution, copying back to pool" << endl;
1170         ResolverContext_Ptr solution = bestContext();
1171         triggeredSolution.clear();
1172         solution->foreachMarked (solution_to_pool, NULL);
1173 #if 1
1174         _XDEBUG( "Pool after resolve" );
1175         show_pool( _pool );
1176 #endif
1177         // insert best_context in ContextPool for further solver runs
1178         contextPool.addContext( solution,_completeItems_to_install, _completeItems_to_remove, _completeItems_to_lockUninstalled);
1179
1180     }
1181     else {
1182         MIL << "!!! Have NO solution !!! Additional solver information:" << endl;
1183         int counter = 0;
1184         for (ResolverQueueList::iterator iter = _invalid_queues.begin();
1185              iter != _invalid_queues.end(); iter++) {
1186             counter++;
1187             MIL << "-----------------------------------------------------------------" << endl;
1188             MIL << counter++ << ". failed queue:" << endl;
1189             ResolverQueue_Ptr invalid = *iter;
1190             invalid->context()->spewInfo ();
1191             MIL << *invalid->context() << endl;
1192             MIL << "-----------------------------------------------------------------" << endl;
1193         }
1194     }
1195
1196     if (tryAllPossibilities) {
1197         _tryAllPossibilities = saveTryAllPossibilities; // reset to old value
1198     }
1199
1200     return have_solution;
1201 }
1202
1203
1204 static void
1205 get_info_foreach_cb (ResolverInfo_Ptr info, void *data)
1206 {
1207     list<string> *stringList = (list<string> *)data;
1208     stringList->push_back (info->message());
1209 }
1210
1211
1212 // returns a string list of ResolverInfo of the LAST not valid solution
1213 std::list<std::string> Resolver::problemDescription( void ) const
1214 {
1215     list<string> retList;
1216     if (_invalid_queues.empty()) return retList;
1217     ResolverQueue_Ptr invalid = _invalid_queues.front();
1218     invalid->context()->foreachInfo (PoolItem_Ref(), -1, get_info_foreach_cb, (void *)&retList);;
1219     return retList;
1220 }
1221
1222
1223 //
1224 // transact a single object
1225 // -> do a 'single step' resolving either installing or removing
1226 //    required and recommended PoolItems
1227
1228 bool
1229 Resolver::transactResObject( ResObject::constPtr robj, bool install,
1230                              bool recursive)
1231 {
1232     MIL << "transactResObject()" << endl;
1233     MIL << "is obsolete; use resolvePool() instead" << endl;
1234
1235     return true;
1236 }
1237
1238
1239 bool
1240 Resolver::transactResKind( Resolvable::Kind kind )
1241 {
1242     MIL << "transactResKind(" << kind << ")" << endl;
1243     MIL << "is obsolete; use resolvePool() instead" << endl;
1244
1245     return true;
1246 }
1247
1248
1249 void
1250 Resolver::transactReset( ResStatus::TransactByValue causer )
1251 {
1252     MIL << "transactReset(" << causer << ")" << endl;
1253     MIL << "is obsolete; use resolvePool() instead" << endl;
1254
1255     return;
1256 }
1257
1258 ///////////////////////////////////////////////////////////////////
1259     };// namespace detail
1260     /////////////////////////////////////////////////////////////////////
1261     /////////////////////////////////////////////////////////////////////
1262   };// namespace solver
1263   ///////////////////////////////////////////////////////////////////////
1264   ///////////////////////////////////////////////////////////////////////
1265 };// namespace zypp
1266 /////////////////////////////////////////////////////////////////////////
1267