Author: schubi2 Date: Tue Oct 23 15:34:40 2007 New Revision: 7611 URL: http://svn.opensuse.org/viewcvs/zypp?rev=7611&view=rev Log: mainframe for SAT-sovler Added: trunk/libzypp/zypp/sat/SATResolver.cc trunk/libzypp/zypp/sat/SATResolver.h Modified: trunk/libzypp/zypp/CMakeLists.txt Modified: trunk/libzypp/zypp/CMakeLists.txt URL: http://svn.opensuse.org/viewcvs/zypp/trunk/libzypp/zypp/CMakeLists.txt?rev=7611&r1=7610&r2=7611&view=diff ============================================================================== --- trunk/libzypp/zypp/CMakeLists.txt (original) +++ trunk/libzypp/zypp/CMakeLists.txt Tue Oct 23 15:34:40 2007 @@ -673,6 +673,19 @@ DESTINATION ${CMAKE_INSTALL_PREFIX}/include/zypp/solver/detail ) +SET( zypp_sat_SRCS + sat/SATResolver.cc +) + +SET( zypp_sat_HEADERS + sat/SATResolver.cc +) + +INSTALL( FILES + ${zypp_sat_HEADERS} + DESTINATION ${CMAKE_INSTALL_PREFIX}/include/zypp/sat +) + SET( zypp_target_SRCS target/CommitLog.cc target/CommitPackageCache.cc @@ -1057,6 +1070,7 @@ ${zypp_target_modalias_SRCS} ${zypp_target_SRCS} ${zypp_solver_detail_SRCS} +${zypp_sat_SRCS} ${zypp_ui_SRCS} ${zypp_zypp_detail_SRCS} ${zypp_thread_SRCS} @@ -1084,6 +1098,7 @@ ${zypp_media_proxyinfo_HEADERS} ${zypp_base_HEADERS} ${zypp_solver_detail_HEADERS} +${zypp_sat_HEADERS} ${zypp_target_store_HEADERS} ${zypp_url_HEADERS} ${zypp_HEADERS} @@ -1126,6 +1141,7 @@ #SET_LOGGROUP( "group" ${zypp_source_yum_SRCS} ) #SET_LOGGROUP( "group" ${zypp_base_SRCS} ) #SET_LOGGROUP( "group" ${zypp_solver_detail_SRCS} ) +#SET_LOGGROUP( "group" ${zypp_sat_SRCS} ) #SET_LOGGROUP( "group" ${zypp_target_store_SRCS} ) #SET_LOGGROUP( "group" ${zypp_url_SRCS} ) #SET_LOGGROUP( "group" ${zypp_source_SRCS} ) Added: trunk/libzypp/zypp/sat/SATResolver.cc URL: http://svn.opensuse.org/viewcvs/zypp/trunk/libzypp/zypp/sat/SATResolver.cc?rev=7611&view=auto ============================================================================== --- trunk/libzypp/zypp/sat/SATResolver.cc (added) +++ trunk/libzypp/zypp/sat/SATResolver.cc Tue Oct 23 15:34:40 2007 @@ -0,0 +1,345 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */ +/* SATResolver.cc + * + * Copyright (C) 2000-2002 Ximian, Inc. + * Copyright (C) 2005 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/solver/detail/Helper.h" + +#include "zypp/CapSet.h" +#include "zypp/base/Logger.h" +#include "zypp/base/String.h" +#include "zypp/base/Gettext.h" +#include "zypp/base/Algorithm.h" +#include "zypp/ResPool.h" +#include "zypp/ResFilters.h" +#include "zypp/CapFilters.h" +#include "zypp/sat/SATResolver.h" + + +///////////////////////////////////////////////////////////////////////// +namespace zypp +{ /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////// + namespace zypp_detail + { ///////////////////////////////////////////////////////////////// + Arch defaultArchitecture(); + ///////////////////////////////////////////////////////////////// + } // namespace zypp_detail + /////////////////////////////////////////////////////////////////// + + /////////////////////////////////////////////////////////////////////// + namespace solver + { ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + namespace detail + { /////////////////////////////////////////////////////////////////// + +using namespace std; + +IMPL_PTR_TYPE(SATResolver); + +static const unsigned MAX_SECOND_RUNS( 3 ); +static const unsigned MAX_VALID_SOLUTIONS( 10 ); +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. + +//--------------------------------------------------------------------------- + + +std::ostream & +SATResolver::dumpOn( std::ostream & os ) const +{ + return os << "<resolver/>"; +} + + +//--------------------------------------------------------------------------- + +SATResolver::SATResolver (const ResPool & pool) + : _pool (pool) + , _timeout_seconds (0) + , _maxSolverPasses (0) + , _testing (false) + , _valid_solution_count (0) + , _timed_out (false) + , _architecture( zypp_detail::defaultArchitecture() ) + +{ + +} + + +SATResolver::~SATResolver() +{ +} + +//--------------------------------------------------------------------------- + +ResPool +SATResolver::pool (void) const +{ + return _pool; +} + + +void +SATResolver::addPoolItemToInstall (PoolItem_Ref item) +{ + bool found = false; + for (PoolItemList::const_iterator iter = _items_to_remove.begin(); + iter != _items_to_remove.end(); iter++) { + if (*iter == item) { + _items_to_remove.remove(*iter); + found = true; + break; + } + } + if (!found) { + _items_to_install.push_back (item); + _items_to_install.unique (); + } +} + + +void +SATResolver::addPoolItemsToInstallFromList (PoolItemList & rl) +{ + for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) { + addPoolItemToInstall (*iter); + } +} + + +void +SATResolver::addPoolItemToRemove (PoolItem_Ref item) +{ + bool found = false; + for (PoolItemList::const_iterator iter = _items_to_install.begin(); + iter != _items_to_install.end(); iter++) { + if (*iter == item) { + _items_to_install.remove(*iter); + found = true; + break; + } + } + if (!found) { + _items_to_remove.push_back (item); + _items_to_remove.unique (); + } +} + + +void +SATResolver::addPoolItemsToRemoveFromList (PoolItemList & rl) +{ + for (PoolItemList::const_iterator iter = rl.begin(); iter != rl.end(); iter++) { + addPoolItemToRemove (*iter); + } +} + +void +SATResolver::addPoolItemToLockUninstalled (PoolItem_Ref item) +{ + _items_to_lockUninstalled.push_back (item); + _items_to_lockUninstalled.unique (); +} + +void +SATResolver::addPoolItemToKepp (PoolItem_Ref item) +{ + _items_to_keep.push_back (item); + _items_to_keep.unique (); +} + + +//--------------------------------------------------------------------------- + +// copy marked item from solution back to pool +// if data != NULL, set as APPL_LOW (from establishPool()) + +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 --> skip"); + return; + } + + triggeredSolution.insert(item); + + // resetting transaction only + item.status().resetTransact((data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER ); + + bool r; + + if (status.isToBeInstalled()) { + r = item.status().setToBeInstalled( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER ); + _XDEBUG("solution_to_pool(" << item << ", " << status << ") install !" << r); + } + else if (status.isToBeUninstalledDueToUpgrade()) { + r = item.status().setToBeUninstalledDueToUpgrade( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER ); + _XDEBUG("solution_to_pool(" << item << ", " << status << ") upgrade !" << r); + } + else if (status.isToBeUninstalled()) { + r = item.status().setToBeUninstalled( (data != NULL) ? ResStatus::APPL_LOW : ResStatus::SOLVER ); + _XDEBUG("solution_to_pool(" << item << ", " << status << ") remove !" << r); + } + else if (status.isIncomplete() + || status.isNeeded()) { + r = item.status().setIncomplete(); + _XDEBUG("solution_to_pool(" << item << ", " << status << ") incomplete !" << r); + } + else if (status.isUnneeded()) { + r = item.status().setUnneeded(); + _XDEBUG("solution_to_pool(" << item << ", " << status << ") unneeded !" << r); + } + else if (status.isSatisfied()) { + r = item.status().setSatisfied(); + _XDEBUG("solution_to_pool(" << item << ", " << status << ") satisfied !" << r); + } else { + _XDEBUG("solution_to_pool(" << item << ", " << status << ") unchanged !"); + } + return; +} + + +//---------------------------------------------------------------------------- +// resolvePool + +struct CollectTransact : public resfilter::PoolItemFilterFunctor +{ + SATResolver & resolver; + + CollectTransact (SATResolver & r) + : resolver (r) + { } + + bool operator()( PoolItem_Ref item ) // only transacts() items go here + { + ResStatus status = item.status(); + _XDEBUG( "CollectTransact(" << item << ")" ); + 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 + } + + if (status.isToBeInstalled()) { + resolver.addPoolItemToInstall(item); // -> install! + } + if (status.isToBeUninstalled()) { + resolver.addPoolItemToRemove(item); // -> remove ! + } + if (status.isIncomplete()) { // incomplete (re-install needed) + PoolItem_Ref reinstall = Helper::findReinstallItem (resolver.pool(), item); + if (reinstall) { + MIL << "Reinstall " << reinstall << " for incomplete " << item << endl; + resolver.addPoolItemToInstall(reinstall); // -> install! + } + else { + 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); + } + + if (status.isKept() + && !by_solver) { + // collecting all keep states + resolver.addPoolItemToKepp (item); + } + + return true; + } +}; + + + +// This function loops over the pool and grabs +// all item.status().transacts() and item.status().byUser() +// It clears all previous bySolver() states also +// +// Every toBeInstalled is passed to zypp::solver:detail::Resolver.addPoolItemToInstall() +// Every toBeUninstalled is passed to zypp::solver:detail::Resolver.addPoolItemToRemove() +// +// Solver results must be written back to the pool. + + +bool +SATResolver::resolvePool() +{ + CollectTransact info (*this); + + MIL << "SATResolver::resolvePool()" << endl; + + invokeOnEach ( _pool.begin(), _pool.end(), + resfilter::ByTransact( ), // collect transacts from Pool to resolver queue + functor::functorRef(info) ); + + invokeOnEach ( _pool.begin(), _pool.end(), + resfilter::ByLock( ), // collect locks from Pool to resolver queue + functor::functorRef(info) ); + + invokeOnEach ( _pool.begin(), _pool.end(), + resfilter::ByKeep( ), // collect keeps from Pool to resolver queue + functor::functorRef(info) ); + + + for (PoolItemList::const_iterator iter = _items_to_install.begin(); iter != _items_to_install.end(); iter++) { + PoolItem_Ref r = *iter; + + } + + for (PoolItemList::const_iterator iter = _items_to_remove.begin(); iter != _items_to_remove.end(); iter++) { + + } + + + bool have_solution;// = resolveDependencies (saveContext); // resolve ! + + if (have_solution) { // copy solution back to pool + MIL << "Have solution, copying back to pool" << endl; +// solution->foreachMarked (solution_to_pool, NULL); + } else { + MIL << "!!! Have NO solution !!!" << endl; + } + + return have_solution; +} + + +/////////////////////////////////////////////////////////////////// + };// namespace detail + ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + };// namespace solver + /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////// +};// namespace zypp +///////////////////////////////////////////////////////////////////////// + Added: trunk/libzypp/zypp/sat/SATResolver.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/libzypp/zypp/sat/SATResolver.h?rev=7611&view=auto ============================================================================== --- trunk/libzypp/zypp/sat/SATResolver.h (added) +++ trunk/libzypp/zypp/sat/SATResolver.h Tue Oct 23 15:34:40 2007 @@ -0,0 +1,128 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */ +/* SATResolver.h + * + * Copyright (C) 2000-2002 Ximian, Inc. + * Copyright (C) 2005 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_SAT_RESOLVER_H +#define ZYPP_SOLVER_DETAIL_SAT_RESOLVER_H + +#include <iosfwd> +#include <list> +#include <map> +#include <string> + +#include "zypp/base/ReferenceCounted.h" +#include "zypp/base/PtrTypes.h" +#include "zypp/ResPool.h" +#include "zypp/base/SerialNumber.h" +#include "zypp/ProblemTypes.h" +#include "zypp/ResolverProblem.h" +#include "zypp/ProblemSolution.h" +extern "C" { +#include "satsolver/solver.h" +} + + +///////////////////////////////////////////////////////////////////////// +namespace zypp +{ /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////// + namespace solver + { ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + namespace detail + { /////////////////////////////////////////////////////////////////// + + +/////////////////////////////////////////////////////////////////// +// +// CLASS NAME : SATResolver + +class SATResolver : public base::ReferenceCounted, private base::NonCopyable { + + private: + ResPool _pool; + + unsigned _timeout_seconds; + unsigned _maxSolverPasses; + bool _testing; + int _valid_solution_count; + bool _timed_out; + Arch _architecture; + + // list populated by calls to addPoolItemTo*() + PoolItemList _items_to_install; + PoolItemList _items_to_remove; + PoolItemList _items_to_lockUninstalled; + PoolItemList _items_to_keep; + + public: + + SATResolver (const ResPool & pool); + virtual ~SATResolver(); + + // ---------------------------------- I/O + + virtual std::ostream & dumpOn( std::ostream & str ) const; + friend std::ostream& operator<<(std::ostream& str, const SATResolver & obj) + { return obj.dumpOn (str); } + + + // ---------------------------------- methods + + void setTimeout (int seconds) { _timeout_seconds = seconds; } + void setMaxSolverPasses (int count) { _maxSolverPasses = count; } + int timeout () const { return _timeout_seconds; } + int maxSolverPasses () const { return _maxSolverPasses; } + ResPool pool (void) const; + void setPool (const ResPool & pool) { _pool = pool; } + + bool resolvePool(); + +// ResolverProblemList problems () const; +// void applySolutions (const ProblemSolutionList &solutions); + + Arch architecture() const { return _architecture; } + void setArchitecture( const Arch & arch) { _architecture = arch; } + + bool testing(void) const { return _testing; } + void setTesting( bool testing ) { _testing = testing; } + + void addPoolItemToInstall (PoolItem_Ref item); + void addPoolItemsToInstallFromList (PoolItemList & rl); + + void addPoolItemToLockUninstalled (PoolItem_Ref item); + void addPoolItemToKepp (PoolItem_Ref item); + + void addPoolItemToRemove (PoolItem_Ref item); + void addPoolItemsToRemoveFromList (PoolItemList & rl); + +}; + +/////////////////////////////////////////////////////////////////// + };// namespace detail + ///////////////////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////////////////// + };// namespace solver + /////////////////////////////////////////////////////////////////////// + /////////////////////////////////////////////////////////////////////// +};// namespace zypp +///////////////////////////////////////////////////////////////////////// + +#endif // ZYPP_SOLVER_DETAIL_SAT_RESOLVER_H -- To unsubscribe, e-mail: zypp-commit+unsubscribe@opensuse.org For additional commands, e-mail: zypp-commit+help@opensuse.org