From 87cdd25a4099e8a9c5b9c4c8f74944a600701f6d Mon Sep 17 00:00:00 2001 From: Stefan Schubert Date: Tue, 6 Mar 2007 16:25:34 +0000 Subject: [PATCH] Using already existing valid solver results for further solver runs. (partiell solving) --- zypp/CMakeLists.txt | 2 + zypp/solver/detail/ContextPool.cc | 329 +++++++++++++++++++++++ zypp/solver/detail/ContextPool.h | 127 +++++++++ zypp/solver/detail/QueueItemConflict.cc | 2 + zypp/solver/detail/Resolver.cc | 446 +++++++------------------------- zypp/solver/detail/Resolver.h | 10 +- zypp/solver/detail/ResolverContext.h | 17 +- zypp/solver/detail/Resolver_problems.cc | 13 +- zypp/solver/detail/Types.h | 2 + 9 files changed, 593 insertions(+), 355 deletions(-) create mode 100644 zypp/solver/detail/ContextPool.cc create mode 100644 zypp/solver/detail/ContextPool.h diff --git a/zypp/CMakeLists.txt b/zypp/CMakeLists.txt index 38037ab..ae039c6 100644 --- a/zypp/CMakeLists.txt +++ b/zypp/CMakeLists.txt @@ -591,6 +591,7 @@ SET( zypp_solver_detail_SRCS solver/detail/Resolver_problems.cc solver/detail/SolutionAction.cc solver/detail/Testcase.cc + solver/detail/ContextPool.cc ) SET( zypp_solver_detail_HEADERS @@ -626,6 +627,7 @@ SET( zypp_solver_detail_HEADERS solver/detail/SolutionAction.h solver/detail/Testcase.h solver/detail/Types.h + solver/detail/ContextPool.h ) INSTALL( FILES diff --git a/zypp/solver/detail/ContextPool.cc b/zypp/solver/detail/ContextPool.cc new file mode 100644 index 0000000..fedea08 --- /dev/null +++ b/zypp/solver/detail/ContextPool.cc @@ -0,0 +1,329 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */ +/* ResolverQueue.cc + * + * Copyright (C) 2007 SUSE Linux Products GmbH + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License, + * version 2, as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#include "zypp/base/Logger.h" +#include "zypp/solver/detail/ContextPool.h" +#include "zypp/solver/detail/ResolverContext.h" + +///////////////////////////////////////////////////////////////////////// +namespace zypp +{ /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////// + namespace solver + { ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + namespace detail + { /////////////////////////////////////////////////////////////////// + +using namespace std; + +IMPL_PTR_TYPE(ContextPool); + +#define MAXCONTEXT 10 + +//--------------------------------------------------------------------------- + +void dumpTaskList(const PoolItemList &list ) +{ + for (PoolItemList::const_iterator iter = list.begin(); + iter != list.end(); iter++) { + DBG << " " << *iter << endl; + } +} + +//--------------------------------------------------------------------------- + +ostream& +operator<<( ostream& os, const ContextPool & contextPool) +{ + os << str::form ("ContextPool [entries: %d]", contextPool.contextListSize()) << endl; + return os; +} + +//--------------------------------------------------------------------------- + +ContextPool::ContextPool (const int maxCount) + : maxContext (maxCount) +{ + _XDEBUG("ContextPool::ContextPool(" << maxContext << ")"); +} + + +ContextPool::ContextPool () + : maxContext (MAXCONTEXT) +{ + _XDEBUG("ContextPool::ContextPool(" << MAXCONTEXT << ")"); +} + +ContextPool::~ContextPool() +{ +} + +//--------------------------------------------------------------------------- +void ContextPool::addContext (ResolverContext_Ptr context, + const PoolItemList & installItems, + const PoolItemList & deleteItems, + const PoolItemList & lockUninstalledItems) +{ + if ((installItems.size() == 0 + && deleteItems.size() == 0) + || context == NULL ) + return; // empty context is useless + + // make an copy + ResolverContext_Ptr new_context = new ResolverContext (context->pool(), context->architecture(), + context); + + new_context->setUserInstallItems (installItems); + new_context->setUserDeleteItems (deleteItems); + new_context->setUserLockUninstalledItems (lockUninstalledItems); + + if (contextList.size() <= 0) { + contextList.push_front (new_context); + } else { + // does context already exists in the list ? + bool exists = false; + + for ( ResolverContextList::iterator it = contextList.begin(); it != contextList.end(); ++it ) { + // checking installed items + PoolItemList left = (*it)->userInstallItems(); + PoolItemList right = context->userInstallItems(); + if (left.size() != right.size()) + continue; + bool found = true; + for (PoolItemList::iterator itleft = left.begin(); + (itleft != left.end()) && found ; ++itleft) { + found = false; + for (PoolItemList::iterator itright = right.begin(); itright != right.end(); ++itright) { + if (*itleft == *itright) { + found = true; + break; + } + } + } + + if (!found ) continue; + + // checking deleted items + left = (*it)->userDeleteItems(); + right = context->userDeleteItems(); + if (left.size() != right.size()) + continue; + found = true; + for (PoolItemList::iterator itleft = left.begin(); + (itleft != left.end()) && found ; ++itleft) { + found = false; + for (PoolItemList::iterator itright = right.begin(); itright != right.end(); ++itright) { + if (*itleft == *itright) { + found = true; + break; + } + } + } + + if (!found ) continue; + + // checking locked items + left = (*it)->userLockUninstalledItems(); + right = context->userLockUninstalledItems(); + if (left.size() != right.size()) + continue; + found = true; + for (PoolItemList::iterator itleft = left.begin(); + (itleft != left.end()) && found ; ++itleft) { + found = false; + for (PoolItemList::iterator itright = right.begin(); itright != right.end(); ++itright) { + if (*itleft == *itright) { + found = true; + break; + } + } + } + + if (found) { + exists = true; + break; + } + } + + if (!exists) { + contextList.push_front (new_context); + } else { + _XDEBUG("----------------------"); + _XDEBUG("ContextPool::addContext Context ALREADY INSERTED "); + _XDEBUG("----------------------"); + } + } + + if (contextList.size() > 0 + && contextList.size() > maxContext) + { + // keep max size + contextList.remove (contextList.back()); + } + + _XDEBUG("----------------------"); + _XDEBUG("ContextPool::addContext latest context with "); + _XDEBUG(" installed:"); + dumpTaskList (new_context->userInstallItems()); + _XDEBUG(" deleted:"); + dumpTaskList (new_context->userDeleteItems()); + _XDEBUG(" locked:"); + dumpTaskList (new_context->userLockUninstalledItems()); +#if 0 + _XDEBUG("CONTEXT : " << endl << *new_context ); +#endif + _XDEBUG("----------------------"); +#if 0 + int count = 0; + for ( ResolverContextList::iterator it = contextList.begin(); it != contextList.end(); ++it ) { + + PoolItemList contextInstall = (*it)->userInstallItems(); + _XDEBUG(" inserted CONTEXT Nr " << count++ << " of " << contextList.size() << " : " << endl << **it ); + _XDEBUG(" with entries"); + dumpTaskList (contextInstall); + _XDEBUG("----------------------"); + } +#endif + +} + +ResolverContext_Ptr ContextPool::findContext (PoolItemList & installItems, + PoolItemList & deleteItems, + const PoolItemList & lockUninstalledItems) +{ + // searching for context with same entries + int counter = 1; + for ( ResolverContextList::iterator it = contextList.begin(); it != contextList.end(); ++it ) { + + PoolItemList contextInstall = (*it)->userInstallItems(); + PoolItemList contextDelete = (*it)->userDeleteItems(); + PoolItemList contextLockUninstalled = (*it)->userLockUninstalledItems(); + + _XDEBUG("ContextPool::findContext() trying " << counter++ << ". of " << contextList.size() ); + _XDEBUG(" comparing"); + _XDEBUG(" installed:"); + dumpTaskList (contextInstall); + _XDEBUG(" deleted:"); + dumpTaskList (contextDelete); + _XDEBUG(" lockedUninstalled:"); + dumpTaskList (contextLockUninstalled); + + _XDEBUG(" with needed"); + _XDEBUG(" installed:"); + dumpTaskList (installItems); + _XDEBUG(" deleted:"); + dumpTaskList (deleteItems); + _XDEBUG(" lockedUninstalled:"); + dumpTaskList (lockUninstalledItems); + + if (contextInstall.size() > installItems.size() + || contextDelete.size() > deleteItems.size() + || contextLockUninstalled.size() != lockUninstalledItems.size()) + continue; // cannot fit at all + + bool found = true; + + found = true; + // check if the lock of unistalled items are the same. + // If not --> try the next context + for (PoolItemList::iterator itContext = contextLockUninstalled.begin(); + (itContext != contextLockUninstalled.end()) && found; ++itContext) { + found = false; + for (PoolItemList::const_iterator itInstall = lockUninstalledItems.begin(); + itInstall != lockUninstalledItems.end(); ++itInstall) { + if (*itContext == *itInstall) { + found = true; + break; + } + } + } + if (!found) continue; + + // checking items which will be installed + PoolItemList addInsItems = installItems; + for (PoolItemList::iterator itContext = contextInstall.begin(); + (itContext != contextInstall.end()) && found; ++itContext) { + found = false; + for (PoolItemList::iterator itInstall = addInsItems.begin(); + itInstall != addInsItems.end(); ++itInstall) { + if (*itContext == *itInstall) { + found = true; + addInsItems.remove (*itInstall); + break; + } + } + } + + PoolItemList addDelItems = deleteItems; + if (found) { + // checking items which will be deleted + PoolItemList addDelItems = deleteItems; + for (PoolItemList::iterator itContext = contextDelete.begin(); + (itContext != contextDelete.end()) && found; ++itContext) { + found = false; + for (PoolItemList::iterator itInstall = addDelItems.begin(); + itInstall != addDelItems.end(); ++itInstall) { + if (*itContext == *itInstall) { + found = true; + addDelItems.remove (*itInstall); + break; + } + } + } + } + + if (found) { + if (addInsItems.size() > 0 + || addDelItems.size() > 0) { + _XDEBUG("ContextPool::findContext() found one with following additional install/delete items: "); + _XDEBUG(" installed:"); + dumpTaskList (addInsItems); + _XDEBUG(" deleted:"); + dumpTaskList (addDelItems); + } else { + _XDEBUG("ContextPool::findContext() found with the SAME selected entries. "); + } + installItems = addInsItems; // Rest of items which has to be installed additionally + deleteItems = addDelItems; // Rest of items which has to be deleted additionally +#if 0 + _XDEBUG("----------------------"); + _XDEBUG(" returned CONTEXT : " << endl << **it ); + _XDEBUG("----------------------"); +#endif + return *it; + } + } + // nothing found + _XDEBUG("ContextPool::findContext() have not found a proper context. Solving completely"); + return NULL; +} + + +/////////////////////////////////////////////////////////////////// + };// namespace detail + ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + };// namespace solver + /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////// +};// namespace zypp +///////////////////////////////////////////////////////////////////////// + diff --git a/zypp/solver/detail/ContextPool.h b/zypp/solver/detail/ContextPool.h new file mode 100644 index 0000000..8dbc1b7 --- /dev/null +++ b/zypp/solver/detail/ContextPool.h @@ -0,0 +1,127 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */ +/* ResolverQueue.h + * + * Copyright (C) 2007 SUSE Linux Products GmbH + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License, + * version 2, as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#ifndef ZYPP_SOLVER_DETAIL_CONTEXTPOOL_H +#define ZYPP_SOLVER_DETAIL_CONTEXTPOOL_H + +#include +#include +#include +#include + +#include "zypp/base/ReferenceCounted.h" +#include "zypp/base/NonCopyable.h" +#include "zypp/base/PtrTypes.h" + +#include "zypp/solver/detail/Types.h" +#include "zypp/solver/detail/QueueItem.h" + +#include "zypp/Capability.h" + +///////////////////////////////////////////////////////////////////////// +namespace zypp +{ /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////// + namespace solver + { ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + namespace detail + { /////////////////////////////////////////////////////////////////// + + +typedef std::list ResolverContextList; + +/////////////////////////////////////////////////////////////////// +// +// CLASS NAME : ContextPool +/** + * Save the last resolver results in a list. + * The next sovler run can search an already existing rusult with which + * he can continue.
+ * + * */ + +class ContextPool : public base::ReferenceCounted, private base::NonCopyable { + + private: + /** maximum stored solver results */ + unsigned maxContext; + /** List of sucessful solver runs */ + ResolverContextList contextList; + + public: + ContextPool (); + /** + * Constructor + * + * @param maxCount maximum stored solver results + * */ + ContextPool (const int maxCount); + virtual ~ContextPool(); + + // ---------------------------------- I/O + + friend std::ostream& operator<<(std::ostream&, const ContextPool & contextPool); + + + // ---------------------------------- methods + /** + * Count of sucessful solver runs + * + * */ + int contextListSize() const { return contextList.size(); } + /** + * Add an additional sucessful solver run. + * + * @param context Solver context + * @param installItems List of items which are selected by the user + * @param deleteItems List of items which are selected by the user + * @param lockUninstalledItems List of items which are selected by the user + * + * */ + void addContext (ResolverContext_Ptr context, + const PoolItemList & installItems, + const PoolItemList & deleteItems, + const PoolItemList & lockUninstalledItems); + /** + * Find a solver result in order to use it for the next solver run. + * + * @param context Solver context + * @param installItems List of items which are selected by the user + * @param deleteItems List of items which are selected by the user + * @param lockUninstalledItems List of items which are selected by the user + * @return solver context + * */ + ResolverContext_Ptr findContext (PoolItemList & installItems, + PoolItemList & deleteItems, + const PoolItemList & lockUninstalledItems); +}; +/////////////////////////////////////////////////////////////////// + };// namespace detail + ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + };// namespace solver + /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////// +};// namespace zypp +///////////////////////////////////////////////////////////////////////// + +#endif // ZYPP_SOLVER_DETAIL_CONTEXTPOOL_H + diff --git a/zypp/solver/detail/QueueItemConflict.cc b/zypp/solver/detail/QueueItemConflict.cc index 22417c8..d39f15d 100644 --- a/zypp/solver/detail/QueueItemConflict.cc +++ b/zypp/solver/detail/QueueItemConflict.cc @@ -59,6 +59,8 @@ using namespace std; IMPL_PTR_TYPE(QueueItemConflict); +#define PHI 1 + //--------------------------------------------------------------------------- std::ostream & diff --git a/zypp/solver/detail/Resolver.cc b/zypp/solver/detail/Resolver.cc index 030fab5..173af66 100644 --- a/zypp/solver/detail/Resolver.cc +++ b/zypp/solver/detail/Resolver.cc @@ -61,8 +61,19 @@ static const unsigned MAX_SECOND_RUNS( 3 ); static const unsigned MAX_VALID_SOLUTIONS( 50 ); static const unsigned TIMOUT_SECOND_RUN( 30 ); +static PoolItemSet triggeredSolution; // only the latest state of an item is interesting + // for the pool. Documents already inserted items. + //--------------------------------------------------------------------------- +class compare_items { +public: + int operator() (PoolItem_Ref p1, + PoolItem_Ref p2) const + { return compareByNVRA(p1.resolvable(),p2.resolvable()) < 0; } +}; + + std::ostream & Resolver::dumpOn( std::ostream & os ) const { @@ -166,6 +177,19 @@ Resolver::context (void) const return invalid->context(); } +void Resolver::dumpTaskList(const PoolItemList &install, const PoolItemList &remove ) +{ + for (PoolItemList::const_iterator iter = install.begin(); + iter != install.end(); iter++) { + DBG << " to_install " << *iter << endl; + } + for (PoolItemList::const_iterator iter = remove.begin(); + iter != remove.end(); iter++) { + DBG << " to_remove " << *iter << endl; + } +} + + //--------------------------------------------------------------------------- void @@ -186,8 +210,10 @@ Resolver::addPoolItemToInstall (PoolItem_Ref item) break; } } - if (!found) + if (!found) { _items_to_install.push_back (item); + _items_to_install.unique (); + } } @@ -212,8 +238,10 @@ Resolver::addPoolItemToRemove (PoolItem_Ref item) break; } } - if (!found) + if (!found) { _items_to_remove.push_back (item); + _items_to_remove.unique (); + } } @@ -225,6 +253,13 @@ Resolver::addPoolItemsToRemoveFromList (PoolItemList & rl) } } +void +Resolver::addPoolItemToLockUninstalled (PoolItem_Ref item) +{ + _items_to_lockUninstalled.push_back (item); + _items_to_lockUninstalled.unique (); +} + void Resolver::addPoolItemToEstablish (PoolItem_Ref item) @@ -417,6 +452,16 @@ Resolver::verifySystem (bool considerNewHardware) static void solution_to_pool (PoolItem_Ref item, const ResStatus & status, void *data) { + if (triggeredSolution.find(item) != triggeredSolution.end()) { + _XDEBUG("solution_to_pool(" << item << ") is already in the pool --> scip"); + return; + } + + triggeredSolution.insert(item); + + // resetting transaction only + item.status().resetTransact((data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER ); + bool r; if (status.isToBeInstalled()) { @@ -535,6 +580,7 @@ Resolver::establishPool () ResolverContext_Ptr solution = bestContext(); if (solution) { // copy solution back to pool + triggeredSolution.clear(); solution->foreachMarked (solution_to_pool, (void *)1); // as APPL_LOW } else { @@ -659,6 +705,7 @@ Resolver::freshenPool (bool resetAfterSolve) ResolverContext_Ptr solution = bestContext(); if (solution) { // copy solution back to pool + triggeredSolution.clear(); solution->foreachMarked (solution_to_pool, (void *)1); // as APPL_LOW } else { @@ -830,7 +877,7 @@ Resolver::resolveDependencies (const ResolverContext_Ptr context) if (initial_queue->isEmpty()) { INT << "Empty Queue, nothing to resolve" << endl; - + _best_context = context; // Taking old context return true; } @@ -984,7 +1031,6 @@ Resolver::resolveDependencies (const ResolverContext_Ptr context) //---------------------------------------------------------------------------- // undo - void Resolver::undo(void) { @@ -1028,6 +1074,7 @@ struct CollectTransact : public resfilter::PoolItemFilterFunctor bool by_solver = (status.isBySolver() || status.isByApplLow()); if (by_solver) { + _XDEBUG("Resetting " << item ); item.status().resetTransact( ResStatus::APPL_LOW );// clear any solver/establish transactions return true; // back out here, dont re-queue former solver result } @@ -1048,6 +1095,14 @@ struct CollectTransact : public resfilter::PoolItemFilterFunctor WAR << "Can't find " << item << " for re-installation" << endl; } } + + if (status.isLocked() + && status.isUninstalled()) { + // This item could be selected by solver in a former run. Now it + // is locked. So we will have to evaluate a new solver run. + resolver.addPoolItemToLockUninstalled (item); + } + return true; } }; @@ -1092,8 +1147,7 @@ show_pool( ResPool pool ) bool Resolver::resolvePool( bool tryAllPossibilities ) { - ResolverContext_Ptr context = NULL; - + ResolverContext_Ptr saveContext = _best_context; CollectTransact info (*this); // cleanup before next run @@ -1101,8 +1155,8 @@ Resolver::resolvePool( bool tryAllPossibilities ) if (tryAllPossibilities) { _tryAllPossibilities = tryAllPossibilities; - context = new ResolverContext( _pool, _architecture ); - context->setTryAllPossibilities( true ); + saveContext = new ResolverContext( _pool, _architecture ); + saveContext->setTryAllPossibilities( true ); } #if 1 @@ -1116,16 +1170,40 @@ Resolver::resolvePool( bool tryAllPossibilities ) resfilter::ByTransact( ), // collect transacts from Pool to resolver queue functor::functorRef(info) ); - bool have_solution = resolveDependencies( context ); // resolve ! + invokeOnEach ( _pool.begin(), _pool.end(), + resfilter::ByLock( ), // collect locks from Pool to resolver queue + functor::functorRef(info) ); + // List of installing/removing items of the complete run (not regarding a recycled solver run) + PoolItemList _completeItems_to_install = _items_to_install; + PoolItemList _completeItems_to_remove = _items_to_remove; + PoolItemList _completeItems_to_lockUninstalled = _items_to_lockUninstalled; + + // We have to find a valid context in order to recycle it. + saveContext = contextPool.findContext (_items_to_install, _items_to_remove, _items_to_lockUninstalled); + // _items_to_install, _items_to_remove contains addition items which has been selected but are + // not solved with that context. They will be solved now. + // If we have not found any former fitting context, saveContext is NULL. So the solver + // make a complete run + + if (saveContext != NULL) { + // create a new context in order not overwriting the old + saveContext = new ResolverContext (saveContext->pool(), saveContext->architecture(), saveContext); + } + + bool have_solution = resolveDependencies (saveContext); // resolve ! if (have_solution) { // copy solution back to pool MIL << "Have solution, copying back to pool" << endl; ResolverContext_Ptr solution = bestContext(); + triggeredSolution.clear(); solution->foreachMarked (solution_to_pool, NULL); #if 1 _XDEBUG( "Pool after resolve" ); show_pool( _pool ); #endif + // insert best_context in ContextPool for further solver runs + contextPool.addContext( solution,_completeItems_to_install, _completeItems_to_remove, _completeItems_to_lockUninstalled); + } else { MIL << "!!! Have NO solution !!! Additional solver information:" << endl; @@ -1164,241 +1242,6 @@ std::list Resolver::problemDescription( void ) const } -//----------------------------------------------------------------------------- - -// -// UI Helper -// do a single (install/uninstall) transaction -// if a previously uninstalled item was just set to-be-installed, return it as 'added' - -static bool -transactItems( PoolItem_Ref installed, PoolItem_Ref uninstalled, bool install, bool soft, PoolItem_Ref & added ) -{ - if (install) { - if (compareByNVRA (installed.resolvable(), uninstalled.resolvable()) != 0) { // do not update itself Bug 174290 - if (uninstalled - && !uninstalled.status().isLocked()) - { - bool adding; // check if we're succeeding with transaction - if (soft) - adding = uninstalled.status().setSoftTransact( true, ResStatus::APPL_LOW ); - else - adding = uninstalled.status().setTransact( true, ResStatus::APPL_LOW ); - if (adding) // if succeeded, return it as 'just added' - added = uninstalled; - } - if (installed - && !installed.status().isLocked()) - { - installed.status().resetTransact( ResStatus::APPL_LOW ); - } - } - } else { - // uninstall - if (uninstalled - && !uninstalled.status().isLocked()) - { - uninstalled.status().resetTransact( ResStatus::APPL_LOW ); - } - if (installed - && !installed.status().isLocked()) - { - if (soft) - installed.status().setSoftTransact( true, ResStatus::APPL_LOW ); - else - installed.status().setTransact( true, ResStatus::APPL_LOW ); - } - } - if (!uninstalled - && !installed) - { - return false; - } - return true; -} - - -typedef struct { PoolItem_Ref installed; PoolItem_Ref uninstalled; } IandU; -typedef map IandUMap; - -// find best available providers for requested capability index -// (use capability index instead of name in order to find e.g. ccb vs. x11) - -struct FindIandU -{ - IandUMap iandu; // install, and best uninstalled - - FindIandU () - { } - - bool operator()( const CapAndItem & cai ) - { - PoolItem item( cai.item ); - string idx = cai.cap.index(); - - if ( item.status().staysInstalled() ) { - iandu[idx].installed = item; - } - else if ( item.status().isToBeInstalled() ) { // prefer already to-be-installed - iandu[idx].uninstalled = item; - } - else if ( item.status().staysUninstalled() ) { // only look at uninstalled - IandUMap::iterator it = iandu.find( idx ); - - if (it != iandu.end() - && it->second.uninstalled) - { // uninstalled with same name found - int cmp = it->second.uninstalled->arch().compare( item->arch() ); - if (cmp < 0) { // new item has better arch - it->second.uninstalled = item; - } - else if (cmp == 0) { // new item has equal arch - if (it->second.uninstalled->edition().compare( item->edition() ) < 0) { - it->second.uninstalled = item; // new item has better edition - } - } - } - else { - iandu[idx].uninstalled = item; - } - } - return true; - } -}; - - -// -// transact list of capabilities (requires or recommends) -// return false if one couldn't be matched -// -// see Resolver::transactResObject -// - -static bool -transactCaps( const ResPool & pool, const CapSet & caps, bool install, bool soft, std::set & added_items ) -{ - bool result = true; - - // loop over capabilities and find (best) matching provider - - for (CapSet::const_iterator cit = caps.begin(); cit != caps.end(); ++cit) { - - // find best providers of requested capability - - FindIandU callback; - Dep dep( Dep::PROVIDES ); - invokeOnEach( pool.byCapabilityIndexBegin( cit->index(), dep ), - pool.byCapabilityIndexEnd( cit->index(), dep ), - resfilter::ByCapMatch( *cit ) , - functor::functorRef(callback) ); - - // loop through providers and transact them accordingly - - for (IandUMap::const_iterator it = callback.iandu.begin(); it != callback.iandu.end(); ++it) { - PoolItem_Ref just_added; - just_added = PoolItem_Ref(); - if (!transactItems( it->second.installed, it->second.uninstalled, install, soft, just_added )) { - result = false; - } - else if (just_added) { - // transactItems just selected an item of the same kind we're currently processing - // add it to the list and handle it equivalent to the origin item - added_items.insert( just_added ); - } - } - - } - return result; -} - - -struct TransactSupplements : public resfilter::PoolItemFilterFunctor -{ - const Resolvable::Kind &_kind; - bool valid; - - TransactSupplements( const Resolvable::Kind & kind ) - : _kind( kind ) - , valid( false ) - { } - - bool operator()( PoolItem_Ref item ) - { -// MIL << "TransactSupplements(" << item << ")" << endl; - if (item->kind() == _kind - && (item.status().staysInstalled() - || item.status().isToBeInstalled())) - { - valid = true; - return false; // end search here - } - return true; - } -}; - -// -// transact due to a language dependency -// -> look through the pool and run transactResObject() accordingly - -struct TransactLanguage : public resfilter::PoolItemFilterFunctor -{ - Resolver & _resolver; - ResObject::constPtr _langObj; - bool _install; - - TransactLanguage( Resolver & r, ResObject::constPtr langObj, bool install ) - : _resolver( r ) - , _langObj( langObj ) - , _install( install ) - { } - - /* item has a freshens on _langObj - _langObj just transacted to _install (true == to-be-installed, false == to-be-uninstalled) - */ - bool operator()( const CapAndItem & cai ) - { - /* check for supplements, if the item has supplements these also must match */ - - PoolItem_Ref item( cai.item ); -// MIL << "TransactLanguage " << item << ", install " << _install << endl; - CapSet supplements( item->dep( Dep::SUPPLEMENTS ) ); - if (!supplements.empty()) { -// MIL << "has supplements" << endl; - bool valid = false; - for (CapSet::const_iterator it = supplements.begin(); it != supplements.end(); ++it) { -// MIL << "Checking " << *it << endl; - TransactSupplements callback( it->refers() ); - invokeOnEach( _resolver.pool().byNameBegin( it->index() ), - _resolver.pool().byNameEnd( it->index() ), - functor::functorRef( callback ) ); - if (callback.valid) { - valid = true; // found a supplements match - break; - } - } - if (!valid) { -// MIL << "All supplements false" << endl; - return true; // no supplements matched, we're done - } - } - - PoolItem_Ref dummy; - if (_install) { - if (item.status().staysUninstalled()) { - transactItems( PoolItem_Ref(), item, _install, true, dummy ); - } - } - else { - if (item.status().staysInstalled()) { - transactItems( item, PoolItem_Ref(), _install, true, dummy ); - } - } - return true; - } -}; - - - // // transact a single object // -> do a 'single step' resolving either installing or removing @@ -1408,128 +1251,29 @@ bool Resolver::transactResObject( ResObject::constPtr robj, bool install, bool recursive) { - static std::set alreadyTransactedObjects; - - if (!recursive) { - alreadyTransactedObjects.clear(); // first call - } + MIL << "transactResObject()" << endl; + MIL << "is obsolete; use resolvePool() instead" << endl; - if (robj == NULL) { - ERR << "NULL ResObject" << endl; - } - _XDEBUG ( "transactResObject(" << *robj << ", " << (install?"install":"remove") << ")"); - - if (robj->kind() == ResTraits::kind) { - TransactLanguage callback( *this, robj, install ); - Dep dep( Dep::FRESHENS ); - invokeOnEach( pool().byCapabilityIndexBegin( robj->name(), dep ), - pool().byCapabilityIndexEnd( robj->name(), dep ), - functor::functorRef( callback ) ); - - } - std::set added; - - // loop over 'recommends' and 'requires' of this item and collect additional - // items of the same kind on the way - - transactCaps( _pool, robj->dep( Dep::RECOMMENDS ), install, true, added ); - transactCaps( _pool, robj->dep( Dep::REQUIRES ), install, false, added ); - - // if any additional items were collected, call this functions again recursively - // This is guaranteed to finish since additional items are those which were not selected before - // and this function is only called for already selected items. So added really only contains - // 'new' items. - - for (std::set::const_iterator it = added.begin(); it != added.end(); ++it) { - if ((*it)->kind() == robj->kind()) { - std::set::const_iterator itCmp = alreadyTransactedObjects.find (*it); - if (itCmp == alreadyTransactedObjects.end()) - { - // not already transacted - alreadyTransactedObjects.insert (*it); - transactResObject( it->resolvable(), install, - true //recursive - ); - } - } - } - - // not used anyway return true; } -// -// helper to transact all objects of a specific kind -// see Resolver::transactResKind -// item is to-be-installed (install == true) or to-be-uninstalled -// -> run transactResObject() accordingly - -struct TransactKind : public resfilter::PoolItemFilterFunctor -{ - Resolver & _resolver; - bool install; // true if to-be-installed, else to-be-uninstalled - bool result; - - TransactKind( Resolver & r ) - : _resolver( r ) - , result( true ) - { } - - bool operator()( PoolItem_Ref item ) - { - result = _resolver.transactResObject( item.resolvable(), install ); - return true; - } -}; - bool Resolver::transactResKind( Resolvable::Kind kind ) { - TransactKind callback (*this); - _XDEBUG( "transactResKind(" << kind << ")" ); - - // check all uninstalls - callback.install = false; - invokeOnEach( pool().byKindBegin( kind ), - pool().byKindEnd( kind ), - functor::chain( resfilter::ByTransact(), resfilter::ByInstalled ()), - functor::functorRef( callback ) ); - - // check all installs - callback.install = true; - invokeOnEach( pool().byKindBegin( kind ), - pool().byKindEnd( kind ), - functor::chain( resfilter::ByTransact(), resfilter::ByUninstalled ()), - functor::functorRef( callback ) ); - - return callback.result; -} - - -struct TransactReset : public resfilter::PoolItemFilterFunctor -{ - ResStatus::TransactByValue _causer; - TransactReset( ResStatus::TransactByValue causer ) - : _causer( causer ) - { } + MIL << "transactResKind(" << kind << ")" << endl; + MIL << "is obsolete; use resolvePool() instead" << endl; - bool operator()( PoolItem_Ref item ) // only transacts() items go here - { - item.status().resetTransact( _causer ); - return true; - } -}; + return true; +} void Resolver::transactReset( ResStatus::TransactByValue causer ) { - TransactReset info( causer ); MIL << "transactReset(" << causer << ")" << endl; - invokeOnEach ( _pool.begin(), _pool.end(), - resfilter::ByTransact( ), - functor::functorRef(info) ); + MIL << "is obsolete; use resolvePool() instead" << endl; + return; } diff --git a/zypp/solver/detail/Resolver.h b/zypp/solver/detail/Resolver.h index c271291..4512181 100644 --- a/zypp/solver/detail/Resolver.h +++ b/zypp/solver/detail/Resolver.h @@ -35,6 +35,7 @@ #include "zypp/solver/detail/Types.h" #include "zypp/solver/detail/ResolverQueue.h" #include "zypp/solver/detail/ResolverContext.h" +#include "zypp/solver/detail/ContextPool.h" #include "zypp/ProblemTypes.h" #include "zypp/ResolverProblem.h" @@ -83,6 +84,10 @@ class Resolver : public base::ReferenceCounted, private base::NonCopyable { PoolItemList _items_to_establish; PoolItemList _items_to_remove; PoolItemList _items_to_verify; + PoolItemList _items_to_lockUninstalled; + + // pool of valid contexts which are "recycled" in order to fasten the solver + ContextPool contextPool; // list of problematic items after doUpgrade() PoolItemList _update_items; @@ -145,7 +150,8 @@ class Resolver : public base::ReferenceCounted, private base::NonCopyable { virtual std::ostream & dumpOn( std::ostream & str ) const; friend std::ostream& operator<<(std::ostream& str, const Resolver & obj) { return obj.dumpOn (str); } - + void dumpTaskList(const PoolItemList &install, const PoolItemList &remove ); + // ---------------------------------- accessors QueueItemList initialItems () const { return _initial_items; } @@ -177,6 +183,8 @@ class Resolver : public base::ReferenceCounted, private base::NonCopyable { void addPoolItemToInstall (PoolItem_Ref item); void addPoolItemsToInstallFromList (PoolItemList & rl); + void addPoolItemToLockUninstalled (PoolItem_Ref item); + void addPoolItemToRemove (PoolItem_Ref item); void addPoolItemsToRemoveFromList (PoolItemList & rl); diff --git a/zypp/solver/detail/ResolverContext.h b/zypp/solver/detail/ResolverContext.h index 4ac32a6..b10e1ef 100644 --- a/zypp/solver/detail/ResolverContext.h +++ b/zypp/solver/detail/ResolverContext.h @@ -99,7 +99,13 @@ class ResolverContext : public base::ReferenceCounted, private base::NonCopyable PoolItemList _ignoreInstalledItem; // Ignore the architecture of the item PoolItemList _ignoreArchitectureItem; - + + // Items which has been selected NOT by the solver + // This will be stored while a solver run in order to save time + // if this information is needed. + PoolItemList _userDeleteItems; + PoolItemList _userInstallItems; + PoolItemList _userLockUninstalledItems; bool _forceResolve; // remove items which are conflicts with others or // have unfulfilled requirements. @@ -183,7 +189,14 @@ class ResolverContext : public base::ReferenceCounted, private base::NonCopyable const bool preferHighestVersion() { return _preferHighestVersion; } void setUpgradeMode (const bool upgrade) { _upgradeMode = upgrade; } - const bool upgradeMode() { return _upgradeMode; } + const bool upgradeMode() { return _upgradeMode; } + + void setUserDeleteItems ( const PoolItemList & deleteItems) { _userDeleteItems = deleteItems; } + void setUserInstallItems ( const PoolItemList& installItems) { _userInstallItems = installItems; } + void setUserLockUninstalledItems ( const PoolItemList& lockItems) { _userLockUninstalledItems = lockItems; } + PoolItemList userDeleteItems () { return _userDeleteItems; } + PoolItemList userInstallItems () { return _userInstallItems; } + PoolItemList userLockUninstalledItems () { return _userLockUninstalledItems; } // ---------------------------------- methods diff --git a/zypp/solver/detail/Resolver_problems.cc b/zypp/solver/detail/Resolver_problems.cc index 38ea658..a3386a7 100644 --- a/zypp/solver/detail/Resolver_problems.cc +++ b/zypp/solver/detail/Resolver_problems.cc @@ -672,7 +672,18 @@ Resolver::problems (const bool ignoreValidSolution) const // TranslatorExplanation %s = name of package, patch, selection ... what = str::form (_("%s will not be uninstalled cause it is still required"), who.c_str()); details = misc_info->message(); - // It is only an info --> no solution is needed + + ResolverProblem_Ptr problem = new ResolverProblem (what, details); + if (item.status().isInstalled()) { + // keep installed + problem->addSolution (new ProblemSolutionKeep (problem, item)); + } else { + // Do install + problem->addSolution (new ProblemSolutionInstall (problem, item)); + } + problems.push_back (problem); + problem_created = true; + } break; case RESOLVER_INFO_TYPE_UNINSTALL_LOCKED: { // cant uninstall, its locked diff --git a/zypp/solver/detail/Types.h b/zypp/solver/detail/Types.h index af87ed8..88b28db 100644 --- a/zypp/solver/detail/Types.h +++ b/zypp/solver/detail/Types.h @@ -75,6 +75,8 @@ DEFINE_PTR_TYPE(QueueItemRequire); DEFINE_PTR_TYPE(QueueItemUninstall); DEFINE_PTR_TYPE(ResolverQueue); + +DEFINE_PTR_TYPE(ContextPool); DEFINE_PTR_TYPE(SolutionAction); typedef std::list SolutionActionList; -- 2.7.4