ResolverQueue.cc

Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
00002 /* ResolverQueue.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 <map>
00023 
00024 #include "zypp/base/String.h"
00025 #include "zypp/solver/detail/ResolverQueue.h"
00026 #include "zypp/solver/detail/QueueItemBranch.h"
00027 #include "zypp/solver/detail/QueueItemConflict.h"
00028 #include "zypp/solver/detail/QueueItemEstablish.h"
00029 #include "zypp/solver/detail/QueueItemGroup.h"
00030 #include "zypp/solver/detail/QueueItemInstall.h"
00031 #include "zypp/solver/detail/QueueItemRequire.h"
00032 #include "zypp/solver/detail/QueueItemUninstall.h"
00033 #include "zypp/solver/detail/ResolverContext.h"
00034 #include "zypp/CapSet.h"
00035 #include "zypp/base/Logger.h"
00036 
00038 namespace zypp
00039 { 
00040 
00041   namespace solver
00042   { 
00043 
00044     namespace detail
00045     { 
00046 
00047 using namespace std;
00048 
00049 IMPL_PTR_TYPE(ResolverQueue);
00050 
00051 //---------------------------------------------------------------------------
00052 
00053 
00054 //---------------------------------------------------------------------------
00055 
00056 ostream&
00057 operator<<( ostream& os, const ResolverQueue & resolverqueue)
00058 {
00059     os << str::form ("Context [%p]", (const void *)resolverqueue._context.get());
00060     os <<  ", " << resolverqueue._qitems.size() << " Items:" << endl << "\t";
00061     os << resolverqueue._qitems;
00062     return os;
00063 }
00064 
00065 //---------------------------------------------------------------------------
00066 
00067 ResolverQueue::ResolverQueue (const ResPool & pool, const Arch & arch, ResolverContext_Ptr context)
00068     : _context (context)
00069 {
00070     _XDEBUG("ResolverQueue::ResolverQueue(pool, " << context << ")");
00071     if (context == NULL)
00072         _context = new ResolverContext(pool, arch);
00073 }
00074 
00075 
00076 ResolverQueue::~ResolverQueue()
00077 {
00078 }
00079 
00080 //---------------------------------------------------------------------------
00081 
00082 void
00083 ResolverQueue::addPoolItemToInstall (PoolItem_Ref poolItem)
00084 {
00085     QueueItemInstall_Ptr qitem;
00086 
00087     if (_context->isPresent (poolItem)
00088         && poolItem.status().staysInstalled()) {
00089         WAR << poolItem << " is already installed" << endl;
00090         return;
00091     }
00092 
00093     qitem = new QueueItemInstall (_context->pool(), poolItem, poolItem.status().isSoftInstall());
00094     poolItem.status().setSoftInstall(false);
00095     qitem->setExplicitlyRequested ();
00096 
00097     addItem (qitem);
00098 }
00099 
00100 
00101 void
00102 ResolverQueue::addPoolItemToEstablish (PoolItem_Ref poolItem)
00103 {
00104     QueueItemEstablish_Ptr qitem;
00105 
00106     qitem = new QueueItemEstablish (_context->pool(), poolItem);
00107     qitem->setExplicitlyRequested ();
00108 
00109     addItem (qitem);
00110 }
00111 
00112 
00113 void
00114 ResolverQueue::addPoolItemToRemove (PoolItem_Ref poolItem, bool remove_only_mode)
00115 {
00116     QueueItemUninstall_Ptr qitem;
00117 
00118     if (_context->isAbsent (poolItem))
00119         return;
00120 
00121     qitem = new QueueItemUninstall (_context->pool(), poolItem, QueueItemUninstall::EXPLICIT, poolItem.status().isSoftUninstall());
00122     poolItem.status().setSoftUninstall(false);
00123     if (remove_only_mode)
00124         qitem->setRemoveOnly ();
00125 
00126     qitem->setExplicitlyRequested ();
00127 
00128     addItem (qitem);
00129 }
00130 
00131 
00132 void
00133 ResolverQueue::addPoolItemToVerify (PoolItem_Ref poolItem)
00134 {
00135     CapSet requires = poolItem->dep (Dep::REQUIRES);
00136     for (CapSet::const_iterator iter = requires.begin(); iter != requires.end(); ++iter) {
00137         QueueItemRequire_Ptr qitem = new QueueItemRequire (_context->pool(), *iter);
00138         qitem->addPoolItem (poolItem);
00139         addItem (qitem);
00140     }
00141 
00142     CapSet conflicts = poolItem->dep (Dep::CONFLICTS);
00143     for (CapSet::const_iterator iter = conflicts.begin(); iter != conflicts.end(); ++iter) {
00144         QueueItemConflict_Ptr qitem = new QueueItemConflict (_context->pool(), *iter, poolItem);
00145         addItem (qitem);
00146     }
00147 }
00148 
00149 
00150 void
00151 ResolverQueue::addExtraCapability (const Capability & dep)
00152 {
00153     QueueItemRequire_Ptr qitem = new QueueItemRequire (_context->pool(), dep);
00154     addItem (qitem);
00155 }
00156 
00157 
00158 void
00159 ResolverQueue::addExtraConflict (const Capability & dep)
00160 {
00161     QueueItemConflict_Ptr qitem = new QueueItemConflict (_context->pool(), dep, PoolItem_Ref());
00162     addItem (qitem);
00163 }
00164 
00165 
00166 void
00167 ResolverQueue::addItem (QueueItem_Ptr qitem)
00168 {
00169     _qitems.push_back(qitem);
00170 }
00171 
00172 
00173 bool
00174 ResolverQueue::isInvalid ()
00175 {
00176     return _context->isInvalid() || _context->askUser();
00177 }
00178 
00179 
00180 bool
00181 ResolverQueue::containsOnlyBranches ()
00182 {
00183     for (QueueItemList::const_iterator iter = _qitems.begin(); iter != _qitems.end(); ++iter) {
00184         if (!(*iter)->isBranch())
00185             return false;
00186     }
00187 
00188     return true;
00189 }
00190 
00191 //---------------------------------------------------------------------------
00192 
00193 static int
00194 qitemlist_max_priority (const QueueItemList & qil)
00195 {
00196     int max_priority = -1;
00197     for (QueueItemList::const_iterator iter = qil.begin(); iter != qil.end(); ++iter) {
00198         if ((*iter)->priority() > max_priority) {
00199             max_priority = (*iter)->priority();
00200         }
00201     }
00202 
00203     return max_priority;
00204 }
00205 
00206 
00207 
00208 bool
00209 ResolverQueue::processOnce ()
00210 {
00211     QueueItemList new_qitems;
00212     int max_priority;
00213     bool did_something = false;
00214 
00215     _XDEBUG("ResolverQueue::processOnce()" << (int) _qitems.size() << " items");
00216     while ( (max_priority = qitemlist_max_priority (_qitems)) >= 0
00217             && _context->isValid () ) {
00218 
00219         bool did_something_recently = false;
00220 
00221         for (QueueItemList::iterator iter = _qitems.begin(); iter != _qitems.end() && _context->isValid();) {
00222             QueueItem_Ptr qitem = *iter;
00223             _XDEBUG( "=====> 1st pass: [" << *qitem << "]");
00224             QueueItemList::iterator next = iter; ++next;
00225             if (qitem && qitem->priority() == max_priority) {
00226                 if (qitem->process (_context, new_qitems)) {
00227                     did_something_recently = true;
00228                 }
00229                 _qitems.erase (iter);
00230             }
00231             iter = next;
00232         }
00233 
00234         if (did_something_recently) {
00235             did_something = true;
00236         }
00237     }
00238 
00239     _qitems = new_qitems;
00240     _XDEBUG(_qitems.size() << " qitems after first pass");
00241 
00242     /*
00243        Now make a second pass over the queue, removing any super-branches.
00244        (If one branch contains all of the possible items of another branch,
00245        the larger branch can be dropped.
00246     */
00247 
00248     for (QueueItemList::iterator iter = _qitems.begin(); iter != _qitems.end();) {
00249         QueueItemList::iterator next = iter; ++next;
00250         QueueItem_Ptr qitem = *iter;
00251 
00252         _XDEBUG( "=====> 2nd pass: [" << *qitem << "]");
00253         if (qitem->isBranch()) {
00254             _XDEBUG("ResolverQueue::processOnce() is branch");
00255             QueueItemBranch_Ptr branch = dynamic_pointer_cast<QueueItemBranch>(qitem);
00256             for (QueueItemList::const_iterator iter2 = _qitems.begin(); iter2 != _qitems.end(); ++iter2) {
00257                 _XDEBUG("Compare branch with [" << *(*iter2) << "]");
00258                 if (iter != iter2
00259                     && branch->contains (*iter2)) {
00260                     _XDEBUG("Contained within, removing");
00261                     _qitems.erase (iter);
00262                     break;
00263                 }
00264             }
00265         }
00266         iter = next;
00267     }
00268     if (did_something) {
00269       _XDEBUG( "did something: " << _qitems.size() << " qitems");
00270     }
00271     else {
00272       _XDEBUG( "did nothing: " << _qitems.size() << " qitems"); 
00273     }
00274 
00275     return did_something;
00276 }
00277 
00278 
00279 void
00280 ResolverQueue::process ()
00281 {
00282     _XDEBUG("----- Processing -----");
00283     spew ();
00284 
00285     while (_context->isValid ()
00286                  && ! isEmpty ()
00287                  && processOnce ()) {
00288               /* all of the work is in the conditional! */
00289               spew ();
00290     }
00291 }
00292 
00293 
00294 //---------------------------------------------------------------------------
00295 
00296 ResolverQueue_Ptr
00297 ResolverQueue::copy_queue_except_for_branch (QueueItem_Ptr branch_qitem, QueueItem_Ptr subqitem) const
00298 {
00299     ResolverContext_Ptr new_context;
00300     ResolverQueue_Ptr new_queue;
00301     _XDEBUG("copy_queue_except_for_branch");
00302     new_context = new ResolverContext (_context->pool(), _context->architecture(), _context);
00303       
00304     new_queue = new ResolverQueue (new_context->pool(), new_context->architecture(), new_context);
00305 
00306     QueueItemList qil = _qitems;
00307     for (QueueItemList::const_iterator iter = qil.begin(); iter != qil.end(); ++iter) {
00308         QueueItem_Ptr qitem = *iter;
00309         QueueItem_Ptr new_qitem;
00310 
00311         if (qitem == branch_qitem) {
00312             new_qitem = subqitem->copy ();
00313 
00314             if (new_qitem->isInstall()) {
00315                 QueueItemInstall_Ptr install_qitem = dynamic_pointer_cast<QueueItemInstall>(new_qitem);
00316 
00317                 /* Penalties are negative priorities */
00318                 int penalty;
00319                 Source_Ref src = install_qitem->item()->source();
00320                 penalty = - src.priority();
00321 
00322                 install_qitem->setOtherPenalty (penalty);
00323             }
00324 
00325         } else {
00326 
00327             new_qitem = qitem->copy ();
00328 
00329         }
00330 
00331         new_queue->addItem (new_qitem);
00332     }
00333 
00334     return new_queue;
00335 }
00336 
00337 
00338 void
00339 ResolverQueue::splitFirstBranch (ResolverQueueList & new_queues, ResolverQueueList & deferred_queues)
00340 {
00341     QueueItemBranch_Ptr first_branch = NULL;
00342     typedef std::map <QueueItem_Ptr, QueueItem_Ptr> DeferTable;
00343     DeferTable to_defer;
00344 
00345     for (QueueItemList::const_iterator iter = _qitems.begin(); iter != _qitems.end() && first_branch == NULL; ++iter) {
00346         QueueItem_Ptr qitem = *iter;
00347         if (qitem->isBranch()) {
00348             first_branch = dynamic_pointer_cast<QueueItemBranch>(qitem);
00349         }
00350     }
00351 
00352     if (first_branch == NULL)
00353         return;
00354 
00355     QueueItemList possible_qitems = first_branch->possibleQItems();
00356 
00357     /*
00358        Check for deferrable qitems: if we have two install qitems where the to-be-installed
00359        poolItems have the same name, then we will defer the lower-priority install if
00360        one of the following is true:
00361        (1) Both poolItems have the same version
00362        (2) The lower-priority channel is a previous version.
00363     */
00364 
00365     for (QueueItemList::const_iterator iter = possible_qitems.begin(); iter != possible_qitems.end(); ++iter) {
00366         QueueItemList::const_iterator iter2 = iter;
00367         for (iter2++; iter2 != possible_qitems.end(); iter2++) {
00368             QueueItem_Ptr qitem = *iter;
00369             QueueItem_Ptr qitem2 = *iter2;
00370 
00371             if (qitem->isInstall() && qitem2->isInstall()) {
00372                 PoolItem_Ref r = (dynamic_pointer_cast<QueueItemInstall>(qitem))->item();
00373                 PoolItem_Ref r2 = (dynamic_pointer_cast<QueueItemInstall>(qitem2))->item();
00374                 Source_Ref source = r->source();
00375                 Source_Ref source2 = r2->source();
00376                 int priority, priority2;
00377 
00378                 priority = _context->getSourcePriority( source );
00379                 priority2 = _context->getSourcePriority( source2 );
00380 
00381                 if (priority != priority2 && r->name() == r2->name()) {
00382                     if (r->edition().compare(r2->edition()) == 0
00383                         || (priority < priority2 && r->edition().compare(r2->edition()) < 0)
00384                         || (priority > priority2 && r->edition().compare(r2->edition()) > 0))
00385                     {
00386                         if (priority < priority2)
00387                             to_defer[qitem] = qitem;
00388                         else /* if (priority > priority2) */
00389                             to_defer[qitem2] = qitem2;
00390                     }
00391                 }
00392             }
00393         }
00394     }
00395 
00396     for (QueueItemList::const_iterator iter = possible_qitems.begin(); iter != possible_qitems.end(); ++iter) {
00397         ResolverQueue_Ptr new_queue;
00398         QueueItem_Ptr new_qitem = *iter;
00399 
00400         new_queue = copy_queue_except_for_branch ((QueueItem_Ptr) first_branch, new_qitem);
00401 
00402         DeferTable::const_iterator pos = to_defer.find (new_qitem);
00403         if (pos != to_defer.end()) {
00404             deferred_queues.push_back(new_queue);
00405         } else {
00406             new_queues.push_back(new_queue);
00407         }
00408     }
00409 
00410 }
00411 
00412 
00413 void
00414 ResolverQueue::spew ()
00415 {
00416     _XDEBUG( "Resolver Queue: " << (_context->isInvalid() ? "INVALID" : "") );
00417 
00418     if (_qitems.empty()) {
00419 
00420         _XDEBUG( "  (empty)" );
00421 
00422     } else {
00423         for (QueueItemList::const_iterator iter = _qitems.begin(); iter != _qitems.end(); ++iter) {
00424             _XDEBUG( "  " << *(*iter) );
00425         }
00426 
00427     }
00428 }
00429 
00431     };// namespace detail
00434   };// namespace solver
00437 };// namespace zypp
00439 

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