00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
00244
00245
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
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
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
00359
00360
00361
00362
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
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 };
00434 };
00437 };
00439