Resolver.cc

Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
00002 /* Resolver.cc
00003  *
00004  * Copyright (C) 2000-2002 Ximian, Inc.
00005  * Copyright (C) 2005 SUSE Linux Products GmbH
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License,
00009  * version 2, as published by the Free Software Foundation.
00010  *
00011  * This program is distributed in the hope that it will be useful, but
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License
00017  * along with this program; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019  * 02111-1307, USA.
00020  */
00021 
00022 #include "zypp/solver/detail/Resolver.h"
00023 #include "zypp/solver/detail/Helper.h"
00024 
00025 #include "zypp/CapSet.h"
00026 #include "zypp/base/Logger.h"
00027 #include "zypp/base/String.h"
00028 #include "zypp/base/Gettext.h"
00029 
00030 #include "zypp/base/Algorithm.h"
00031 #include "zypp/ResPool.h"
00032 #include "zypp/ResFilters.h"
00033 #include "zypp/CapFilters.h"
00034 #include "zypp/ZYppFactory.h"
00035 #include "zypp/SystemResObject.h"
00036 
00037 
00038 
00040 namespace zypp
00041 { 
00042 
00043   namespace zypp_detail
00044   { 
00045     Arch defaultArchitecture();
00047   } // namespace zypp_detail
00049 
00051   namespace solver
00052   { 
00053 
00054     namespace detail
00055     { 
00056 
00057 using namespace std;
00058 
00059 IMPL_PTR_TYPE(Resolver);
00060 
00061 //---------------------------------------------------------------------------
00062 
00063 std::ostream &
00064 Resolver::dumpOn( std::ostream & os ) const
00065 {
00066     return os << "<resolver/>";
00067 }
00068 
00069 // Generating a system resolvable in the pool in order to trigger
00070 // modaliases and hals
00071 void assertSystemResObjectInPool()
00072 {
00073   ResPool pool( getZYpp()->pool() );
00074   if ( pool.byKindBegin<SystemResObject>()
00075        == pool.byKindEnd<SystemResObject>() )
00076     {
00077       // SystemResObject is missing in the pool ==> insert
00078       ResStore store;
00079       store.insert( SystemResObject::instance() );
00080       getZYpp()->addResolvables( store, true ); // true = is installed
00081     }
00082 
00083   // set lock
00084   if ( ! pool.byKindBegin<SystemResObject>()
00085          ->status().setLock( true, ResStatus::USER ) )
00086     {
00087       WAR << "Unable to set SystemResObject to lock" << endl;
00088     }
00089 }
00090 
00091 //---------------------------------------------------------------------------
00092 
00093 Resolver::Resolver (const ResPool & pool)
00094     : _pool (pool)
00095     , _timeout_seconds (0)
00096     , _verifying (false)
00097     , _testing (false)
00098     , _valid_solution_count (0)
00099     , _best_context (NULL)
00100     , _timed_out (false)
00101     , _architecture( zypp_detail::defaultArchitecture() )
00102     , _forceResolve (false)
00103     , _upgradeMode (false)
00104 {}
00105 
00106 
00107 Resolver::~Resolver()
00108 {
00109 }
00110 
00111 //---------------------------------------------------------------------------
00112 
00113 ResPool
00114 Resolver::pool (void) const
00115 {
00116     return _pool;
00117 }
00118 
00119 void
00120 Resolver::reset (void)
00121 {
00122     _timeout_seconds = 0;
00123     _verifying = false;
00124 
00125     _initial_items.clear();
00126 
00127     _items_to_install.clear();
00128     _items_to_remove.clear();
00129     _items_to_verify.clear();
00130     _items_to_establish.clear();
00131 
00132     _extra_caps.clear();
00133     _extra_conflicts.clear();
00134 
00135     _pending_queues.clear();
00136     _pruned_queues.clear();
00137     _complete_queues.clear();
00138     _deferred_queues.clear();
00139     _invalid_queues.clear();
00140 
00141     _valid_solution_count = 0;
00142 
00143     _best_context = NULL;
00144     _timed_out = false;
00145 }
00146 
00147 
00148 ResolverContext_Ptr
00149 Resolver::context (void) const
00150 {
00151     if (_best_context) return _best_context;
00152     if (_invalid_queues.empty()) return NULL;
00153     ResolverQueue_Ptr invalid = _invalid_queues.front();
00154     return invalid->context();
00155 }
00156 
00157 //---------------------------------------------------------------------------
00158 
00159 void
00160 Resolver::addSubscribedSource (Source_Ref source)
00161 {
00162     _subscribed.insert(source);
00163 }
00164 
00165 void
00166 Resolver::addPoolItemToInstall (PoolItem_Ref item)
00167 {
00168     bool found = false;
00169     for (PoolItemList::const_iterator iter = _items_to_remove.begin();
00170          iter != _items_to_remove.end(); iter++) {
00171         if (*iter == item) {
00172             _items_to_remove.remove(*iter);
00173             found = true;
00174             break;
00175         }
00176     }
00177     if (!found)
00178         _items_to_install.push_back (item);
00179 }
00180 
00181 
00182 void
00183 Resolver::addPoolItemsToInstallFromList (PoolItemList & rl)
00184 {
00185     for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) {
00186         addPoolItemToInstall (*iter);
00187     }
00188 }
00189 
00190 
00191 void
00192 Resolver::addPoolItemToRemove (PoolItem_Ref item)
00193 {
00194     bool found = false;
00195     for (PoolItemList::const_iterator iter = _items_to_install.begin();
00196          iter != _items_to_install.end(); iter++) {
00197         if (*iter == item) {
00198             _items_to_install.remove(*iter);
00199             found = true;
00200             break;
00201         }
00202     }
00203     if (!found)
00204         _items_to_remove.push_back (item);
00205 }
00206 
00207 
00208 void
00209 Resolver::addPoolItemsToRemoveFromList (PoolItemList & rl)
00210 {
00211     for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) {
00212         addPoolItemToRemove (*iter);
00213     }
00214 }
00215 
00216 
00217 void
00218 Resolver::addPoolItemToEstablish (PoolItem_Ref item)
00219 {
00220     _items_to_establish.push_back (item);
00221 }
00222 
00223 
00224 void
00225 Resolver::addPoolItemsToEstablishFromList (PoolItemList & rl)
00226 {
00227     for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) {
00228         addPoolItemToEstablish (*iter);
00229     }
00230 }
00231 
00232 
00233 void
00234 Resolver::addPoolItemToVerify (PoolItem_Ref item)
00235 {
00236 #if 0
00237 
00238   struct {
00240     bool operator()( PoolItem_Ref lhs, PoolItem_Ref rhs ) const
00241     {
00242       int res = lhs->name().compare( rhs->name() );
00243       if ( res )
00244         return res == -1; // lhs < rhs ?
00245       // here: lhs == rhs, so compare edition:
00246       return lhs->edition() < rhs->edition();
00247     }
00248   } order;
00249 #endif
00250 
00251     _items_to_verify.push_back (item);
00252 
00253 #warning Should order by name (and probably edition since with zypp we could have multiple editions installed in parallel)
00254 //    _items_to_verify.sort (order);                    //(GCompareFunc) rc_item_compare_name);
00255 }
00256 
00257 
00258 void
00259 Resolver::addExtraCapability (const Capability & capability)
00260 {
00261     _extra_caps.insert (capability);
00262 }
00263 
00264 
00265 void
00266 Resolver::addExtraConflict (const Capability & capability)
00267 {
00268     _extra_conflicts.insert (capability);
00269 }
00270 
00271 
00272 void
00273 Resolver::addIgnoreConflict (const PoolItem_Ref item,
00274                    const Capability & capability)
00275 {
00276     _ignoreConflicts.insert(make_pair(item, capability));
00277 }
00278 
00279 
00280 void
00281 Resolver::addIgnoreRequires (const PoolItem_Ref item,
00282                              const Capability & capability)
00283 {
00284     _ignoreRequires.insert(make_pair(item, capability));
00285 }
00286 
00287 void
00288 Resolver::addIgnoreObsoletes (const PoolItem_Ref item,
00289                               const Capability & capability)
00290 {
00291     _ignoreObsoletes.insert(make_pair(item, capability));
00292 }
00293 
00294 void
00295 Resolver::addIgnoreInstalledItem (const PoolItem_Ref item)
00296 {
00297     _ignoreInstalledItem.push_back (item);
00298 }
00299 
00300 void
00301 Resolver::addIgnoreArchitectureItem (const PoolItem_Ref item)
00302 {
00303     _ignoreArchitectureItem.push_back (item);
00304 }
00305 
00306 
00307 //---------------------------------------------------------------------------
00308 
00309 struct VerifySystem : public resfilter::PoolItemFilterFunctor
00310 {
00311     Resolver & resolver;
00312 
00313     VerifySystem (Resolver & r)
00314         : resolver (r)
00315     { }
00316 
00317     bool operator()( PoolItem_Ref provider )
00318     {
00319         resolver.addPoolItemToVerify (provider);
00320         return true;
00321     }
00322 };
00323 
00324 
00325 bool
00326 Resolver::verifySystem (void)
00327 {
00328     _DEBUG( "Resolver::verifySystem()" );
00329 
00330     VerifySystem info (*this);
00331 
00332     invokeOnEach( pool().byKindBegin( ResTraits<Package>::kind ),
00333                   pool().byKindEnd( ResTraits<Package>::kind ),
00334                   resfilter::ByInstalled ( ),
00335                   functor::functorRef<bool,PoolItem>(info) );
00336 
00337 
00338     _verifying = true;
00339 
00340     return resolveDependencies ();
00341 }
00342 
00343 
00344 //---------------------------------------------------------------------------
00345 
00346 // copy marked item from solution back to pool
00347 // if data != NULL, set as APPL_LOW (from establishPool())
00348 
00349 static void
00350 solution_to_pool (PoolItem_Ref item, const ResStatus & status, void *data)
00351 {
00352     bool r;
00353 
00354     if (status.isToBeInstalled()) {
00355         r = item.status().setToBeInstalled( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER );
00356         _XDEBUG("solution_to_pool(" << item << ", " << status << ") install !" << r);
00357     }
00358     else if (status.isToBeUninstalledDueToUpgrade()) {
00359         r = item.status().setToBeUninstalledDueToUpgrade( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER );
00360         _XDEBUG("solution_to_pool(" << item << ", " << status << ") upgrade !" << r);
00361     }
00362     else if (status.isToBeUninstalled()) {
00363         r = item.status().setToBeUninstalled( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER );
00364         _XDEBUG("solution_to_pool(" << item << ", " << status << ") remove !" << r);
00365     }
00366     else if (status.isIncomplete()
00367              || status.isNeeded()) {
00368         r = item.status().setIncomplete();
00369         _XDEBUG("solution_to_pool(" << item << ", " << status << ") incomplete !" << r);
00370     }
00371     else if (status.isUnneeded()) {
00372         r = item.status().setUnneeded();
00373         _XDEBUG("solution_to_pool(" << item << ", " << status << ") unneeded !" << r);
00374     }
00375     else if (status.isSatisfied()) {
00376         r = item.status().setSatisfied();
00377         _XDEBUG("solution_to_pool(" << item << ", " << status << ") satisfied !" << r);
00378     } else {
00379         _XDEBUG("solution_to_pool(" << item << ", " << status << ") unchanged !");
00380     }
00381     return;
00382 }
00383 
00384 
00385 //---------------------------------------------------------------------------
00386 // establish state
00387 
00388 struct EstablishState
00389 {
00390     Resolver & resolver;
00391 
00392     EstablishState (Resolver & r)
00393         : resolver (r)
00394     { }
00395 
00396     bool operator()( PoolItem_Ref provider )
00397     {
00398         resolver.addPoolItemToEstablish (provider);
00399         return true;
00400     }
00401 };
00402 
00403 
00404 void
00405 Resolver::establishState( ResolverContext_Ptr context )
00406 {
00407     _DEBUG( "Resolver::establishState ()" );
00408     typedef list<Resolvable::Kind> KindList;
00409     static KindList ordered;
00410     if (ordered.empty()) {
00411         ordered.push_back (ResTraits<zypp::Atom>::kind);
00412         ordered.push_back (ResTraits<zypp::Message>::kind);
00413         ordered.push_back (ResTraits<zypp::Script>::kind);
00414         ordered.push_back (ResTraits<zypp::Patch>::kind);
00415         ordered.push_back (ResTraits<zypp::Pattern>::kind);
00416         ordered.push_back (ResTraits<zypp::Product>::kind);
00417     }
00418 
00419     if (context == NULL)
00420         context = new ResolverContext(_pool, _architecture);
00421 
00422     context->setEstablishing (true);
00423     context->setIgnoreCababilities (_ignoreConflicts,
00424                                     _ignoreRequires,
00425                                     _ignoreObsoletes,
00426                                     _ignoreInstalledItem,
00427                                     _ignoreArchitectureItem);
00428     context->setForceResolve( _forceResolve );
00429     context->setUpgradeMode( _upgradeMode );
00430 
00431     for (KindList::const_iterator iter = ordered.begin(); iter != ordered.end(); iter++) {
00432         const Resolvable::Kind kind = *iter;
00433 
00434         _XDEBUG( "establishing state for kind " << kind.asString() );
00435 
00436         //world()->foreachResItemByKind (kind, trial_establish_cb, this);
00437 
00438         EstablishState info (*this);
00439 
00440         invokeOnEach( pool().byKindBegin( kind ),
00441                       pool().byKindEnd( kind ),
00442                       functor::functorRef<bool,PoolItem>(info) );
00443 
00444         // process the queue
00445         resolveDependencies( context );
00446 
00447         reset();
00448     }
00449 
00450     context->setEstablishing (false);
00451 
00452     _best_context = context;
00453 
00454     return;
00455 }
00456 
00457 
00458 bool
00459 Resolver::establishPool ()
00460 {
00461     MIL << "Resolver::establishPool()" << endl;
00462 
00463     establishState ();                                          // establish !
00464     ResolverContext_Ptr solution = bestContext();
00465 
00466     if (solution) {                                             // copy solution back to pool
00467         solution->foreachMarked (solution_to_pool, (void *)1);  // as APPL_LOW
00468     }
00469     else {
00470         ERR << "establishState did not return a bestContext" << endl;
00471         return false;
00472     }
00473 
00474     return true;
00475 }
00476 
00477 
00478 //---------------------------------------------------------------------------
00479 // freshen state
00480 
00481 typedef map<string, PoolItem_Ref> FreshenMap;
00482 
00483 // add item to itemmap
00484 //  check for item with same name and only keep
00485 //  best architecture, best version
00486 
00487 static void
00488 addToFreshen( PoolItem_Ref item, FreshenMap & itemmap )
00489 {
00490     FreshenMap::iterator it = itemmap.find( item->name() );
00491     if (it != itemmap.end()) {                                  // item with same name found
00492         int cmp = it->second->arch().compare( item->arch() );
00493         if (cmp < 0) {                                          // new item has better arch
00494             it->second = item;
00495         }
00496         else if (cmp == 0) {                                    // new item has equal arch
00497             if (it->second->edition().compare( item->edition() ) < 0) {
00498                 it->second = item;                              // new item has better edition
00499             }
00500         }
00501     }
00502     else {
00503         itemmap[item->name()] = item;
00504     }
00505     return;
00506 }
00507 
00508 
00509 struct FreshenState
00510 {
00511     FreshenMap itemmap;
00512 
00513     FreshenState()
00514     { }
00515 
00516     bool operator()( PoolItem_Ref item)
00517     {
00518         CapSet freshens( item->dep( Dep::FRESHENS ) );
00519         if (!freshens.empty()) {
00520             addToFreshen( item, itemmap );
00521         }
00522         else {                                  // if no freshens, look at supplements
00523             // Also regarding supplements e.g. in order to recognize
00524             // modalias dependencies. Bug #163140
00525             CapSet supplements( item->dep( Dep::SUPPLEMENTS ) );
00526             if (!supplements.empty()) {
00527                 addToFreshen( item, itemmap );
00528             }
00529         }
00530         return true;
00531     }
00532 };
00533 
00534 
00535 void
00536 Resolver::freshenState( ResolverContext_Ptr context )
00537 {
00538     _DEBUG( "Resolver::freshenState ()" );
00539 
00540     if (context == NULL)
00541         context = new ResolverContext( _pool, _architecture );
00542 
00543     context->setEstablishing( true );
00544     context->setIgnoreCababilities( _ignoreConflicts,
00545                                     _ignoreRequires,
00546                                     _ignoreObsoletes,
00547                                     _ignoreInstalledItem,
00548                                     _ignoreArchitectureItem );
00549     context->setForceResolve( _forceResolve );
00550     context->setUpgradeMode( _upgradeMode );
00551 
00552     FreshenState info;
00553 
00554     // collect items to be established
00555 
00556     invokeOnEach( pool().byKindBegin( ResTraits<zypp::Package>::kind ),
00557                       pool().byKindEnd( ResTraits<zypp::Package>::kind ),
00558                       functor::functorRef<bool,PoolItem>(info) );
00559 
00560     // schedule all collected items for establish
00561 
00562     for (FreshenMap::iterator it = info.itemmap.begin(); it != info.itemmap.end(); ++it) {
00563         addPoolItemToEstablish( it->second );
00564     }
00565 
00566     // process the queue
00567     resolveDependencies( context );
00568 
00569     reset();
00570 
00571     context->setEstablishing( false );
00572 
00573     _best_context = context;
00574 
00575     return;
00576 }
00577 
00578 
00579 bool
00580 Resolver::freshenPool ()
00581 {
00582     MIL << "Resolver::freshenPool()" << endl;
00583 
00584     freshenState ();                                            // establish all packages with freshens !
00585     ResolverContext_Ptr solution = bestContext();
00586 
00587     if (solution) {                                             // copy solution back to pool
00588         solution->foreachMarked (solution_to_pool, (void *)1);  // as APPL_LOW
00589     }
00590     else {
00591         ERR << "freshenState did not return a bestContext" << endl;
00592         return false;
00593     }
00594 
00595     return true;
00596 }
00597 
00598 //---------------------------------------------------------------------------
00599 
00600 bool
00601 Resolver::resolveDependencies (const ResolverContext_Ptr context)
00602 {
00603 
00604     time_t t_start, t_now;
00605 
00606     MIL << "Resolver::resolveDependencies()" << endl;
00607 
00608     _pending_queues.clear();
00609     _pruned_queues.clear();
00610     _complete_queues.clear();
00611     _deferred_queues.clear();
00612     _invalid_queues.clear();
00613     _valid_solution_count = 0;
00614     _best_context = NULL;
00615 
00616 #warning local items disabled
00617 #if 0
00618     bool have_local_items = false;
00619 
00620     /* Walk through are list of to-be-installed packages and see if any of them are local. */
00621 
00622     for (PoolItemList::const_iterator iter = _items_to_install.begin(); iter != _items_to_install.end(); iter++) {
00623         if ((*iter)->local()) {
00624             have_local_items = true;
00625             break;
00626         }
00627     }
00628 
00629     World_Ptr the_world = world();
00630     StoreWorld_Ptr local_world = NULL;
00631     MultiWorld_Ptr local_multiworld = NULL;
00632 
00633     Channel_Ptr local_channel = NULL;
00634 
00635     if (have_local_items) {
00636         local_multiworld = new MultiWorld();
00637         local_world = new StoreWorld();
00638 
00639         local_channel = new Channel ("", "Local ResItems", "@local", "");
00640 
00641         local_world->addChannel (local_channel);
00642 
00643         local_multiworld->addSubworld (local_world);
00644         local_multiworld->addSubworld (the_world);
00645 
00646         the_world = local_multiworld;
00647     }
00648 #endif
00649 
00650     // create initial_queue
00651 
00652     ResolverQueue_Ptr initial_queue = new ResolverQueue(_pool, _architecture, context);
00653 
00654     // Initialize all ignoring dependencies
00655     initial_queue->context()->setIgnoreCababilities (_ignoreConflicts,
00656                                     _ignoreRequires,
00657                                     _ignoreObsoletes,
00658                                     _ignoreInstalledItem,
00659                                     _ignoreArchitectureItem);
00660     initial_queue->context()->setForceResolve( _forceResolve );
00661     initial_queue->context()->setUpgradeMode( _upgradeMode );
00662 
00663     /* If this is a verify, we do a "soft resolution" */
00664 
00665     initial_queue->context()->setVerifying( _verifying );
00666 
00667     /* Add extra items. */
00668 
00669     for (QueueItemList::const_iterator iter = _initial_items.begin(); iter != _initial_items.end(); iter++) {
00670         initial_queue->addItem (*iter);
00671     }
00672 
00673     for (PoolItemList::const_iterator iter = _items_to_install.begin(); iter != _items_to_install.end(); iter++) {
00674         PoolItem_Ref r = *iter;
00675 
00676 #warning local items disabled
00677 #if 0
00678         /* Add local packages to our dummy channel. */
00679         if (r->local()) {
00680             assert (local_channel != NULL);
00681             ResItem_Ptr r1 = const_pointer_cast<ResItem>(r);
00682             r1->setChannel (local_channel);
00683             local_world->addPoolItem_Ref (r);
00684         }
00685 #endif
00686         initial_queue->addPoolItemToInstall (r);
00687     }
00688 
00689     for (PoolItemList::const_iterator iter = _items_to_remove.begin(); iter != _items_to_remove.end(); iter++) {
00690         if (!_upgradeMode)
00691             initial_queue->addPoolItemToRemove (*iter, true /* remove-only mode */);
00692         else
00693             //   Checking old dependencies for packages which will be updated.
00694             //   E.g. foo provides a dependecy which foo-new does not provides anymore.
00695             //   So check, if there is a packages installed which requires foo.
00696             //   Testcase exercise-bug150844-test.xml
00697             //   Testcase Bug156439-test.xml
00698             initial_queue->addPoolItemToRemove (*iter, false /* no remove-only mode */);
00699     }
00700 
00701     for (PoolItemList::const_iterator iter = _items_to_verify.begin(); iter != _items_to_verify.end(); iter++) {
00702         initial_queue->addPoolItemToVerify (*iter);
00703     }
00704 
00705     for (PoolItemList::const_iterator iter = _items_to_establish.begin(); iter != _items_to_establish.end(); iter++) {
00706         initial_queue->addPoolItemToEstablish (*iter);
00707     }
00708 
00709     for (CapSet::const_iterator iter = _extra_caps.begin(); iter != _extra_caps.end(); iter++) {
00710         initial_queue->addExtraCapability (*iter);
00711     }
00712 
00713     for (CapSet::const_iterator iter = _extra_conflicts.begin(); iter != _extra_conflicts.end(); iter++) {
00714         initial_queue->addExtraConflict (*iter);
00715     }
00716 
00717     // Adding System resolvable
00718     assertSystemResObjectInPool();
00719 
00720     _XDEBUG( "Initial Queue: [" << *initial_queue << "]" );
00721 
00722     if (initial_queue->isEmpty()) {
00723         INT << "Empty Queue, nothing to resolve" << endl;
00724 
00725         return true;
00726     }
00727 
00728     _best_context = NULL;
00729 
00730     _pending_queues.push_front (initial_queue);
00731 
00732     time (&t_start);
00733 
00734     while (!_pending_queues.empty()) {
00735 
00736         _DEBUG( "Pend " << (long) _pending_queues.size()
00737                               << " / Cmpl " << (long) _complete_queues.size()
00738                               << " / Prun " << (long) _pruned_queues.size()
00739                               << " / Defr " << (long) _deferred_queues.size()
00740                               << " / Invl " << (long) _invalid_queues.size() );
00741 
00742               if (_timeout_seconds > 0) {
00743                     time (&t_now);
00744                     if (difftime (t_now, t_start) > _timeout_seconds) {
00745                         _timed_out = true;
00746                     break;
00747                 }
00748             }
00749 
00750             ResolverQueue_Ptr queue = _pending_queues.front();
00751             _pending_queues.pop_front();
00752             ResolverContext_Ptr context = queue->context();
00753 
00754             queue->process();
00755 
00756         if (queue->isInvalid ()) {
00757 
00758             _XDEBUG( "Invalid Queue\n" );
00759             _invalid_queues.push_back(queue);
00760 
00761         } else if (queue->isEmpty ()) {
00762 
00763             _XDEBUG( "Empty Queue\n" );
00764 
00765             _complete_queues.push_back(queue);
00766 
00767             ++_valid_solution_count;
00768 
00769             /* Compare this solution to our previous favorite.  In the case of a tie,
00770                the first solution wins --- yeah, I know this is lame, but it shouldn't
00771                be an issue too much of the time. */
00772 
00773             if (_best_context == NULL
00774                 || _best_context->compare (context) < 0)
00775             {
00776                 _best_context = context;
00777             }
00778 
00779         } else if (_best_context != NULL
00780                    && _best_context->partialCompare (context) > 0) {
00781 
00782             /* If we aren't currently as good as our previous best complete solution,
00783                this solution gets pruned. */
00784 
00785             _XDEBUG( "PRUNED!" );
00786 
00787             _pruned_queues.push_back(queue);
00788 
00789         } else {
00790 
00791             /* If our queue is isn't empty and isn't invalid, that can only mean
00792                one thing: we are down to nothing but branches. */
00793 
00794             queue->splitFirstBranch (_pending_queues, _deferred_queues);
00795         }
00796 
00797         /* If we have run out of pending queues w/o finding any solutions,
00798            and if we have deferred queues, make the first deferred queue
00799            pending. */
00800 
00801         if (_pending_queues.empty()
00802             && _complete_queues.empty()
00803             && !_deferred_queues.empty()) {
00804             _pending_queues.push_back(_deferred_queues.front());
00805         }
00806     }
00807     _DEBUG("Pend " << (long) _pending_queues.size()
00808                    << " / Cmpl " << (long) _complete_queues.size()
00809                    << " / Prun " << (long) _pruned_queues.size()
00810                    << " / Defr " << (long) _deferred_queues.size()
00811                    << " / Invl " << (long) _invalid_queues.size() );
00812 
00813     return _best_context && _best_context->isValid();
00814 }
00815 
00816 
00817 //----------------------------------------------------------------------------
00818 // undo
00819 
00820 struct UndoTransact : public resfilter::PoolItemFilterFunctor
00821 {
00822     UndoTransact ()
00823     { }
00824 
00825     bool operator()( PoolItem_Ref item )                // only transacts() items go here
00826     {
00827         item.status().resetTransact( ResStatus::APPL_LOW );// clear any solver/establish transactions
00828         return true;
00829     }
00830 };
00831 
00832 void
00833 Resolver::undo(void)
00834 {
00835     UndoTransact info;
00836     MIL << "*** undo ***" << endl;
00837     invokeOnEach ( _pool.begin(), _pool.end(),
00838                    resfilter::ByTransact( ),                    // collect transacts from Pool to resolver queue
00839                    functor::functorRef<bool,PoolItem>(info) );
00840     // These conflict should be ignored of the concering item
00841     _ignoreConflicts.clear();
00842     // These requires should be ignored of the concering item
00843     _ignoreRequires.clear();
00844     // These obsoletes should be ignored of the concering item
00845     _ignoreObsoletes.clear();
00846     // Ignore architecture of the item
00847     _ignoreArchitecture.clear();
00848     // Ignore the status "installed" of the item
00849     _ignoreInstalledItem.clear();
00850     // Ignore the architecture of the item
00851     _ignoreArchitectureItem.clear();
00852 
00853 
00854     return;
00855 }
00856 
00857 //----------------------------------------------------------------------------
00858 // resolvePool
00859 
00860 struct CollectTransact : public resfilter::PoolItemFilterFunctor
00861 {
00862     Resolver & resolver;
00863 
00864     CollectTransact (Resolver & r)
00865         : resolver (r)
00866     { }
00867 
00868     bool operator()( PoolItem_Ref item )                // only transacts() items go here
00869     {
00870         ResStatus status = item.status();
00871         _XDEBUG( "CollectTransact(" << item << ")" );
00872         bool by_solver = (status.isBySolver() || status.isByApplLow());
00873 
00874         if (by_solver) {
00875             item.status().resetTransact( ResStatus::APPL_LOW );// clear any solver/establish transactions
00876             return true;                                // back out here, dont re-queue former solver result
00877         }
00878 
00879         if (status.isToBeInstalled()) {
00880             resolver.addPoolItemToInstall(item);        // -> install!
00881         }
00882         if (status.isToBeUninstalled()) {
00883             resolver.addPoolItemToRemove(item);         // -> remove !
00884         }
00885         if (status.isIncomplete()) {                    // incomplete (re-install needed)
00886             PoolItem_Ref reinstall = Helper::findReinstallItem (resolver.pool(), item);
00887             if (reinstall) {
00888                 MIL << "Reinstall " << reinstall << " for incomplete " << item << endl;
00889                 resolver.addPoolItemToInstall(reinstall);       // -> install!
00890             }
00891             else {
00892                 WAR << "Can't find " << item << " for re-installation" << endl;
00893             }
00894         }
00895         return true;
00896     }
00897 };
00898 
00899 
00900 static void
00901 show_pool( ResPool pool )
00902 {
00903     int count = 1;
00904     static bool full_pool_shown = true;
00905 
00906     _XDEBUG( "---------------------------------------" );
00907     for (ResPool::const_iterator it = pool.begin(); it != pool.end(); ++it, ++count) {
00908 
00909         if (!full_pool_shown                                    // show item if not shown all before
00910             || it->status().transacts()                         // or transacts
00911             || !it->status().isUndetermined())                  // or established status
00912         {
00913             _DEBUG( count << ": " << *it );
00914         }
00915     }
00916     _XDEBUG( "---------------------------------------" );
00917     full_pool_shown = true;
00918 }
00919 
00920 //  This function loops over the pool and grabs
00921 //  all item.status().transacts() and item.status().byUser()
00922 //  It clears all previous bySolver() states also
00923 //
00924 //  Every toBeInstalled is passed to zypp::solver:detail::Resolver.addPoolItemToInstall()
00925 //  Every toBeUninstalled is passed to zypp::solver:detail::Resolver.addPoolItemToRemove()
00926 //
00927 //  Then zypp::solver:detail::Resolver.resolveDependencies() is called.
00928 //
00929 //  zypp::solver:detail::Resolver then returns a ResolverContext via bestContext() which
00930 //  describes the best solution. If bestContext() is NULL, no solution was found.
00931 //
00932 //  ResolverContext has a foreachMarked() iterator function which loops over all
00933 //  items of the solutions. These must be written back to the pool.
00934 
00935 
00936 bool
00937 Resolver::resolvePool ()
00938 {
00939 
00940     CollectTransact info (*this);
00941 
00942     // cleanup before next run
00943     reset();
00944 
00945 #if 1
00946 
00947     MIL << "Resolver::resolvePool()" << endl;
00948     _XDEBUG( "Pool before resolve" );
00949     show_pool( _pool );
00950 
00951 #endif
00952     invokeOnEach ( _pool.begin(), _pool.end(),
00953                    resfilter::ByTransact( ),                    // collect transacts from Pool to resolver queue
00954                    functor::functorRef<bool,PoolItem>(info) );
00955 
00956     bool have_solution = resolveDependencies ();                // resolve !
00957 
00958     if (have_solution) {                                        // copy solution back to pool
00959         MIL << "Have solution, copying back to pool" << endl;
00960         ResolverContext_Ptr solution = bestContext();
00961         solution->foreachMarked (solution_to_pool, NULL);
00962 #if 1
00963         _XDEBUG( "Pool after resolve" );
00964         show_pool( _pool );
00965 #endif
00966     }
00967     else {
00968         MIL << "!!! Have NO solution !!!" << endl;
00969     }
00970     return have_solution;
00971 }
00972 
00973 //-----------------------------------------------------------------------------
00974 
00975 //
00976 // UI Helper
00977 // do a single (install/uninstall) transaction
00978 //  if a previously uninstalled item was just set to-be-installed, return it as 'added'
00979 
00980 static bool
00981 transactItems( PoolItem_Ref installed, PoolItem_Ref uninstalled, bool install, bool soft, PoolItem_Ref & added )
00982 {
00983         if (install) {
00984             if (compareByNVRA (installed.resolvable(), uninstalled.resolvable()) != 0) { // do not update itself Bug 174290
00985                 if (uninstalled
00986                     && !uninstalled.status().isLocked())
00987                 {
00988                     bool adding;        // check if we're succeeding with transaction
00989                     if (soft)
00990                         adding = uninstalled.status().setSoftTransact( true, ResStatus::APPL_LOW );
00991                     else
00992                         adding = uninstalled.status().setTransact( true, ResStatus::APPL_LOW );
00993                     if (adding) // if succeeded, return it as 'just added'
00994                         added = uninstalled;
00995                 }
00996                 if (installed
00997                     && !installed.status().isLocked())
00998                 {
00999                     installed.status().resetTransact( ResStatus::APPL_LOW );
01000                 }
01001             }
01002         } else {
01003             // uninstall
01004             if (uninstalled
01005                 && !uninstalled.status().isLocked())
01006             {
01007                 uninstalled.status().resetTransact( ResStatus::APPL_LOW );
01008             }
01009             if (installed
01010                 && !installed.status().isLocked())
01011             {
01012                 if (soft)
01013                     installed.status().setSoftTransact( true, ResStatus::APPL_LOW );
01014                 else
01015                     installed.status().setTransact( true, ResStatus::APPL_LOW );
01016             }
01017         }
01018         if (!uninstalled
01019             && !installed)
01020         {
01021             return false;
01022         }
01023     return true;
01024 }
01025 
01026 
01027 typedef struct { PoolItem_Ref installed; PoolItem_Ref uninstalled; } IandU;
01028 typedef map<string, IandU> IandUMap;
01029 
01030 // find best available providers for requested capability index
01031 // (use capability index instead of name in order to find e.g. ccb vs. x11)
01032 
01033 struct FindIandU
01034 {
01035     IandUMap iandu;             // install, and best uninstalled
01036 
01037     FindIandU ()
01038     { }
01039 
01040     bool operator()( const CapAndItem & cai )
01041     {
01042         PoolItem item( cai.item );
01043         string idx = cai.cap.index();
01044 
01045         if ( item.status().staysInstalled() ) {
01046             iandu[idx].installed = item;
01047         }
01048         else if ( item.status().isToBeInstalled() ) {                   // prefer already to-be-installed
01049             iandu[idx].uninstalled = item;
01050         }
01051         else if ( item.status().staysUninstalled() ) {                  // only look at uninstalled
01052             IandUMap::iterator it = iandu.find( idx );
01053 
01054             if (it != iandu.end()
01055                 && it->second.uninstalled)
01056             {                                                           // uninstalled with same name found
01057                 int cmp = it->second.uninstalled->arch().compare( item->arch() );
01058                 if (cmp < 0) {                                          // new item has better arch
01059                     it->second.uninstalled = item;
01060                 }
01061                 else if (cmp == 0) {                                    // new item has equal arch
01062                     if (it->second.uninstalled->edition().compare( item->edition() ) < 0) {
01063                         it->second.uninstalled = item;                  // new item has better edition
01064                     }
01065                 }
01066             }
01067             else {
01068                 iandu[idx].uninstalled = item;
01069             }
01070         }
01071         return true;
01072     }
01073 };
01074 
01075 
01076 //
01077 // transact list of capabilities (requires or recommends)
01078 //  return false if one couldn't be matched
01079 //
01080 // see Resolver::transactResObject
01081 //
01082 
01083 static bool
01084 transactCaps( const ResPool & pool, const CapSet & caps, bool install, bool soft, std::list<PoolItem_Ref> & added_items )
01085 {
01086     bool result = true;
01087 
01088     // loop over capabilities and find (best) matching provider
01089 
01090     for (CapSet::const_iterator cit = caps.begin(); cit != caps.end(); ++cit) {
01091 
01092         // find best providers of requested capability
01093 
01094         FindIandU callback;
01095         Dep dep( Dep::PROVIDES );
01096         invokeOnEach( pool.byCapabilityIndexBegin( cit->index(), dep ),
01097                       pool.byCapabilityIndexEnd( cit->index(), dep ),
01098                       resfilter::ByCapMatch( *cit ) ,
01099                       functor::functorRef<bool,CapAndItem>(callback) );
01100 
01101         // loop through providers and transact them accordingly
01102 
01103         for (IandUMap::const_iterator it = callback.iandu.begin(); it !=  callback.iandu.end(); ++it) {
01104             PoolItem_Ref just_added;
01105             just_added = PoolItem_Ref();
01106             if (!transactItems( it->second.installed, it->second.uninstalled, install, soft, just_added )) {
01107                 result = false;
01108             }
01109             else if (just_added) {
01110                 // transactItems just selected an item of the same kind we're currently processing
01111                 // add it to the list and handle it equivalent to the origin item
01112                 added_items.push_back( just_added );
01113             }
01114         }
01115 
01116     }
01117     return result;
01118 }
01119 
01120 
01121 struct TransactSupplements : public resfilter::PoolItemFilterFunctor
01122 {
01123     const Resolvable::Kind &_kind;
01124     bool valid;
01125 
01126     TransactSupplements( const Resolvable::Kind & kind )
01127         : _kind( kind )
01128         , valid( false )
01129     { }
01130 
01131     bool operator()( PoolItem_Ref item )
01132     {
01133 //      MIL << "TransactSupplements(" << item << ")" << endl;
01134         if (item->kind() == _kind
01135             && (item.status().staysInstalled()
01136                 || item.status().isToBeInstalled()))
01137         {
01138             valid = true;
01139             return false;               // end search here
01140         }
01141         return true;
01142     }
01143 };
01144 
01145 //
01146 // transact due to a language dependency
01147 // -> look through the pool and run transactResObject() accordingly
01148 
01149 struct TransactLanguage : public resfilter::PoolItemFilterFunctor
01150 {
01151     Resolver & _resolver;
01152     ResObject::constPtr _langObj;
01153     bool _install;
01154 
01155     TransactLanguage( Resolver & r, ResObject::constPtr langObj, bool install )
01156         : _resolver( r )
01157         , _langObj( langObj )
01158         , _install( install )
01159     { }
01160 
01161     /* item has a freshens on _langObj
01162         _langObj just transacted to _install (true == to-be-installed, false == to-be-uninstalled)
01163     */
01164     bool operator()( const CapAndItem & cai )
01165     {
01166         /* check for supplements, if the item has supplements these also must match  */
01167 
01168         PoolItem_Ref item( cai.item );
01169 //      MIL << "TransactLanguage " << item << ", install " << _install << endl;
01170         CapSet supplements( item->dep( Dep::SUPPLEMENTS ) );
01171         if (!supplements.empty()) {
01172 //          MIL << "has supplements" << endl;
01173             bool valid = false;
01174             for (CapSet::const_iterator it = supplements.begin(); it != supplements.end(); ++it) {
01175 //              MIL << "Checking " << *it << endl;
01176                 TransactSupplements callback( it->refers() );
01177                 invokeOnEach( _resolver.pool().byNameBegin( it->index() ),
01178                               _resolver.pool().byNameEnd( it->index() ),
01179                               functor::functorRef<bool,PoolItem>( callback ) );
01180                 if (callback.valid) {
01181                     valid = true;               // found a supplements match
01182                     break;
01183                 }
01184             }
01185             if (!valid) {
01186 //              MIL << "All supplements false" << endl;
01187                 return true;                    // no supplements matched, we're done
01188             }
01189         }
01190 
01191         PoolItem_Ref dummy;
01192         if (_install) {
01193             if (item.status().staysUninstalled()) {
01194                 transactItems( PoolItem_Ref(), item, _install, true, dummy );
01195             }
01196         }
01197         else {
01198             if (item.status().staysInstalled()) {
01199                 transactItems( item, PoolItem_Ref(), _install, true, dummy );
01200             }
01201         }
01202         return true;
01203     }
01204 };
01205 
01206 
01207 
01208 //
01209 // transact a single object
01210 // -> do a 'single step' resolving either installing or removing
01211 //    required and recommended PoolItems
01212 
01213 bool
01214 Resolver::transactResObject( ResObject::constPtr robj, bool install)
01215 {
01216     if (robj == NULL) {
01217         ERR << "NULL ResObject" << endl;
01218     }
01219     _XDEBUG( "transactResObject(" << *robj << ", " << (install?"install":"remove") << ")" );
01220 
01221     if (robj->kind() == ResTraits<Language>::kind) {
01222         TransactLanguage callback( *this, robj, install );
01223         Dep dep( Dep::FRESHENS );
01224         invokeOnEach( pool().byCapabilityIndexBegin( robj->name(), dep ),
01225                       pool().byCapabilityIndexEnd( robj->name(), dep ),
01226                       functor::functorRef<bool,CapAndItem>( callback ) );
01227 
01228     }
01229     std::list<PoolItem_Ref> added;
01230 
01231     // loop over 'recommends' and 'requires' of this item and collect additional
01232     //  items of the same kind on the way
01233 
01234     transactCaps( _pool, robj->dep( Dep::RECOMMENDS ), install, true, added );
01235     transactCaps( _pool, robj->dep( Dep::REQUIRES ), install, false, added );
01236 
01237     // if any additional items were collected, call this functions again recursively
01238     //   This is guaranteed to finish since additional items are those which were not selected before
01239     //   and this function is only called for already selected items. So added really only contains
01240     //   'new' items.
01241 
01242     for (std::list<PoolItem_Ref>::const_iterator it = added.begin(); it != added.end(); ++it) {
01243         if ((*it)->kind() == robj->kind()) {
01244             transactResObject( it->resolvable(), install );
01245         }
01246     }
01247 
01248     // not used anyway
01249     return true;
01250 }
01251 
01252 //
01253 // helper to transact all objects of a specific kind
01254 //  see Resolver::transactResKind
01255 // item is to-be-installed (install == true) or to-be-uninstalled
01256 // -> run transactResObject() accordingly
01257 
01258 struct TransactKind : public resfilter::PoolItemFilterFunctor
01259 {
01260     Resolver & _resolver;
01261     bool install;               // true if to-be-installed, else to-be-uninstalled
01262     bool result;
01263 
01264     TransactKind( Resolver & r )
01265         : _resolver( r )
01266         , result( true )
01267     { }
01268 
01269     bool operator()( PoolItem_Ref item )
01270     {
01271         result = _resolver.transactResObject( item.resolvable(), install );
01272         return true;
01273     }
01274 };
01275 
01276 
01277 bool
01278 Resolver::transactResKind( Resolvable::Kind kind )
01279 {
01280     TransactKind callback (*this);
01281 
01282     _XDEBUG( "transactResKind(" << kind << ")" );
01283 
01284     // check all uninstalls
01285     callback.install = false;
01286     invokeOnEach( pool().byKindBegin( kind ),
01287                   pool().byKindEnd( kind ),
01288                   functor::chain( resfilter::ByTransact(), resfilter::ByInstalled ()),
01289                   functor::functorRef<bool,PoolItem>( callback ) );
01290 
01291     // check all installs
01292     callback.install = true;
01293     invokeOnEach( pool().byKindBegin( kind ),
01294                   pool().byKindEnd( kind ),
01295                   functor::chain( resfilter::ByTransact(), resfilter::ByUninstalled ()),
01296                   functor::functorRef<bool,PoolItem>( callback ) );
01297 
01298     return callback.result;
01299 }
01300 
01301 
01302 struct TransactReset : public resfilter::PoolItemFilterFunctor
01303 {
01304     ResStatus::TransactByValue _causer;
01305     TransactReset( ResStatus::TransactByValue causer )
01306         : _causer( causer )
01307     { }
01308 
01309     bool operator()( PoolItem_Ref item )                // only transacts() items go here
01310     {
01311         item.status().resetTransact( _causer );
01312         return true;
01313     }
01314 };
01315 
01316 
01317 void
01318 Resolver::transactReset( ResStatus::TransactByValue causer )
01319 {
01320     TransactReset info( causer );
01321     MIL << "transactReset(" << causer << ")" << endl;
01322     invokeOnEach ( _pool.begin(), _pool.end(),
01323                    resfilter::ByTransact( ),
01324                    functor::functorRef<bool,PoolItem>(info) );
01325     return;
01326 }
01327 
01329     };// namespace detail
01332   };// namespace solver
01335 };// namespace zypp
01337 

Generated on Thu Jul 6 00:07:22 2006 for zypp by  doxygen 1.4.6