/-*/
#include "zypp/solver/detail/InstallOrder.h"
-#include "zypp/base/Logger.h"
+#include "zypp/base/LogTools.h"
+#include "zypp/base/Iterator.h"
+#include "zypp/base/Algorithm.h"
+
+#include "zypp/solver/detail/SATResolver.h"
+
+#include "zypp/ResFilters.h"
+#include "zypp/ResStatus.h"
+#include "zypp/NameKindProxy.h"
+#include "zypp/sat/Pool.h"
+#include <zypp/sat/WhatObsoletes.h>
/////////////////////////////////////////////////////////////////////////
namespace zypp
{ ///////////////////////////////////////////////////////////////////
using namespace std;
+using namespace zypp;
+#define ITEMNAME(item) (item)->name()
//-----------------------------------------------------------------------------
-InstallOrder::InstallOrder(World_Ptr world, const CResItemList& toinstall, const CResItemList& installed)
- : _world (world)
+InstallOrder::InstallOrder( const ResPool & pool, const PoolItemSet & toinstall, const PoolItemSet & installed )
+ : _pool( pool )
+ , _toinstall( toinstall )
+ , _installed( installed )
, _dirty (true)
, _numrun (0)
{
- for (CResItemList::const_iterator iter = toinstall.begin(); iter != toinstall.end(); ++iter)
- _toinstall.insert (*iter);
- for (CResItemList::const_iterator iter = installed.begin(); iter != installed.end(); ++iter)
- _installed.insert (*iter);
+ _DEBUG("InstallOrder::InstallOrder(_toinstall " << _toinstall.size() << " items, _installed " << _installed.size() << " items)");
}
//-----------------------------------------------------------------------------
-const void
+void
InstallOrder::printAdj (std::ostream& os, bool reversed) const
{
const Graph& g = (reversed ? _rgraph : _graph);
string name = gcit->first->name();
os << "\"" << name << "\"" << "[label=\"" << name << "\\n" << order << "\"";
os << "] " << endl;
- for (CResItemSet::const_iterator scit = gcit->second.begin(); scit != gcit->second.end(); ++scit)
+ for (PoolItemList::const_iterator scit = gcit->second.begin(); scit != gcit->second.end(); ++scit)
{
os << "\"" << name << "\" -> \"" << (*scit)->name() << "\"" << endl;
}
//-----------------------------------------------------------------------------
// yea, that stuff is suboptimal. there should be a heap sorted by order
-CResItemList
+PoolItemList
InstallOrder::computeNextSet()
{
- CResItemList newlist;
+ PoolItemList newlist;
if (_dirty) startrdfs();
for (Nodes::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
{
- if (it->second.order == 0)
+ if (it->second.order == 0
+ && it->second.item) // the default Nodes constructor leaves this empty
{
- _DBG("RC_SPEW") << "InstallOrder::computeNextSet found " << it->second.resItem->asString() << endl;
+ XXX << "InstallOrder::computeNextSet found " << ITEMNAME(it->second.item) << endl;
- newlist.push_back(it->second.resItem);
+ newlist.push_back(it->second.item);
}
}
// decrease order of every adjacent node
void
-InstallOrder::setInstalled( ResItem_constPtr resItem )
+InstallOrder::setInstalled(PoolItem item )
{
_dirty = true;
- CResItemSet& adj = _rgraph[resItem];
+ PoolItemList adj = _rgraph[item];
- _DBG("RC_SPEW") << "InstallOrder::setInstalled " << resItem->asString() << endl;
+ XXX << "InstallOrder::setInstalled " << ITEMNAME(item) << endl;
// order will be < 0
- _nodes[resItem].order--;
- _installed.insert (resItem);
- _toinstall.erase (resItem);
+ _nodes[item].order--;
+ _installed.insert( item );
+ _toinstall.erase( item );
- for (CResItemSet::iterator it = adj.begin(); it != adj.end(); ++it)
+ for (PoolItemList::iterator it = adj.begin(); it != adj.end(); ++it)
{
NodeInfo& info = _nodes[*it];
info.order--;
if (info.order < 0)
{
- cerr << "order of node " << (*it)->asString() << " is < 0" << endl;
+ WAR << "order of node " << (*it) << " is < 0" << endl;
}
}
}
void
-InstallOrder::setInstalled( const CResItemList& rl )
+InstallOrder::setInstalled( const PoolItemList & rl )
{
- for (CResItemList::const_iterator it = rl.begin(); it != rl.end(); ++it)
+ for (PoolItemList::const_iterator it = rl.begin(); it != rl.end(); ++it)
{
setInstalled(*it);
}
//-----------------------------------------------------------------------------
-
-void
-InstallOrder::startrdfs()
+bool
+InstallOrder::doesProvide( const Capability requirement, PoolItem item ) const
{
- _nodes.clear();
- _rgraph.clear();
- _graph.clear();
-
- _rdfstime = 1;
-
- _topsorted.clear();
-
- _numrun++;
- _DBG("RC_SPEW") << "run #" << _numrun << endl;
-
- // initialize all nodes
- for (CResItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
- {
- ResItem_constPtr resItem = *it;
- _nodes[resItem] = NodeInfo (resItem);
- _rgraph[resItem] = CResItemSet();
- _graph[resItem] = CResItemSet();
- }
-
- // visit all nodes
- for (CResItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
- {
- ResItem_constPtr resItem = *it;
- if (_nodes[resItem].visited == false)
- {
- _DBG("RC_SPEW") << "start recursion on " << resItem->asString() << endl;
- rdfsvisit (resItem);
+ Capabilities::const_iterator pend = item->dep( Dep::PROVIDES ).end();
+ for( Capabilities::const_iterator pit = item->dep( Dep::PROVIDES ).begin(); pit != pend; ++pit) {
+ if( pit->matches( requirement ) == CapMatch::yes ) {
+ return item;
}
}
-
- _dirty = false;
+ return PoolItem();
}
-typedef struct {
- ResItem_constPtr requestor;
- CResItemSet *tovisit;
- CResItemSet *toinstall;
- CResItemSet *installed;
-} CollectProvidersInfo;
-
-// resItem provides cap which matches a requirement from info->requestor
-
-static bool
-collect_providers (ResItem_constPtr resItem, const Capability & cap, void *data)
+PoolItem
+InstallOrder::findProviderInSet( const Capability requirement, const PoolItemSet & candidates ) const
{
- CollectProvidersInfo *info = (CollectProvidersInfo *)data;
-
- if ((resItem != info->requestor) // package could provide its own requirement
- && (!resItem->isInstalled()) // only visit if provider is not already installed
- && (info->toinstall->find(resItem) != info->toinstall->end() // only look at packages
- || info->installed->find(resItem) != info->installed->end())) { // we are currently considering anyways
- info->tovisit->insert (resItem);
+ for( PoolItemSet::const_iterator citer = candidates.begin(); citer != candidates.end(); citer++) {
+ if( doesProvide( requirement, *citer ) ) {
+ return *citer;
+ }
}
- return true;
+ return PoolItem();
}
+//-----------------------------------------------------------------------------
+
void
-InstallOrder::rdfsvisit(ResItem_constPtr resItem)
+InstallOrder::rdfsvisit (const PoolItem item)
{
typedef list<Capability> CapList;
CapList requires;
- _DBG ("RC_SPEW") << "InstallOrder::rdfsvisit, visiting " << resItem->asString() << endl;
+ XXX << "InstallOrder::rdfsvisit, visiting " << ITEMNAME(item) << endl;
- NodeInfo& nodeinfo = _nodes[resItem];
+ NodeInfo& nodeinfo = _nodes[item];
nodeinfo.visited = true;
nodeinfo.begintime = _rdfstime;
_rdfstime++;
+ // items prereq
+ CapabilitySet prq( item->dep(Dep::PREREQUIRES).begin(), item->dep(Dep::PREREQUIRES).end() );
+ // any obsoleted items prereq (in case they are reqired for uninstall scripts)
+ sat::WhatObsoletes obs( item );
+ for_( it, obs.begin(), obs.end() )
+ {
+ Capabilities p( it->prerequires() );
+ prq.insert( p.begin(), p.end() );
+ }
// put prerequires first and requires last on list to ensure
// that prerequires are processed first
-
- for (CapSet::const_iterator it = resItem->prerequires().begin(); it != resItem->prerequires().end(); ++it)
+ for (CapabilitySet::const_iterator it = prq.begin(); it != prq.end(); ++it)
{
- const Capability cap = *it;
- requires.push_back(cap);
+ requires.push_back(*it);
}
- for (CapSet::const_iterator it = resItem->requires().begin(); it != resItem->requires().end(); ++it)
- {
- const Capability cap = *it;
- requires.push_back(cap);
- }
+ // Product requirements are ignored to assert Product gets installed
+ // as early as possible. Some stuff depends on it (e.g. registration).
+ if ( ! isKind<Product>( item.resolvable() ) )
+ {
+ for (Capabilities::const_iterator it = item->dep (Dep::REQUIRES).begin(); it != item->dep (Dep::REQUIRES).end(); ++it)
+ {
+ requires.push_back(*it);
+ }
+ }
for (CapList::const_iterator iter = requires.begin(); iter != requires.end(); ++iter)
{
+ bool goBack = false;
const Capability requirement = *iter;
- _DBG("RC_SPEW") << "check requirement " << requirement.asString() << " of " << resItem->asString() << endl;
- CResItemSet tovisit;
-
- CollectProvidersInfo info = { resItem, &tovisit, &_toinstall, &_installed };
- _world->foreachProvidingResItem (requirement, collect_providers, &info);
+ PoolItemList providers;
+
+ XXX << "check requirement " << requirement << " of " << ITEMNAME(item) << endl;
+ SATResolver satResolver(_pool, sat::Pool::instance().get());
+ PoolItemList tovisit;
+ sat::WhatProvides possibleProviders(requirement);
+
+ // first, look in _installed
+ for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
+ PoolItem provider = ResPool::instance().find( *iter );
+ if ( provider == item )
+ {
+ goBack = true;
+ break;
+ }
+ if (_installed.find( provider ) != _installed.end()) // and is not installed
+ {
+ XXX << "tovisit " << ITEMNAME(provider) << endl;
+ providers.push_back (provider);
+ }
+ }
+
+ if ( goBack )
+ continue;
+
+ // if not found in _installed, look in _toinstall
+
+ if (providers.empty()) {
+ for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
+ PoolItem provider = ResPool::instance().find( *iter );
+ if ((provider.resolvable() != item.resolvable()) // resolvable could provide its own requirement
+ && (_toinstall.find( provider ) != _toinstall.end())) // and is not to be installed
+ {
+ XXX << "tovisit " << ITEMNAME(provider) << endl;
+ tovisit.push_back (provider);
+ }
+ }
+ }
- for (CResItemSet::iterator it = tovisit.begin(); it != tovisit.end(); ++it)
+ for (PoolItemList::iterator it = tovisit.begin(); it != tovisit.end(); ++it)
{
- ResItem_constPtr must_visit = *it;
+ const PoolItem must_visit = *it;
if (_nodes[must_visit].visited == false)
{
nodeinfo.order++;
- _rgraph[must_visit].insert (resItem);
- _graph[resItem].insert (must_visit);
- rdfsvisit(must_visit);
+ _rgraph[must_visit].push_back( item );
+ _graph[item].push_back( must_visit );
+ rdfsvisit( must_visit );
}
else if (_nodes[must_visit].endtime == 0)
{
- if (must_visit != resItem)
+ if (must_visit != item)
{
- cerr << "dependency loop: " << resItem->asString() << " -> " << must_visit->asString() << endl;
+ // log only the 1st occurrence.
+ std::string lstr( ITEMNAME(item) );
+ lstr += " -> ";
+ lstr += ITEMNAME(must_visit);
+ if ( _logset.insert( lstr ).second )
+ {
+ WAR << "** dependency loop: " << lstr << endl;
+ }
}
}
else
{
- // filter multiple depends on same resItem (cosmetic)
- CResItemSet & lrg = _rgraph[must_visit];
- if (lrg.find(resItem) == lrg.end())
+ // filter multiple depends on same item (cosmetic)
+ PoolItemList & lrg = _rgraph[must_visit];
+ if( find( lrg.begin(), lrg.end(), item) == lrg.end() )
{
nodeinfo.order++;
- lrg.insert(resItem);
+ lrg.push_back( item );
- CResItemSet& lg = _graph[resItem];
- if (lg.find (must_visit) == lg.end())
- lg.insert (must_visit);
+ PoolItemList & lg = _graph[item];
+ if( find( lg.begin(), lg.end(), must_visit ) == lg.end() )
+ lg.push_back( must_visit );
}
}
}
}
- _topsorted.push_back(resItem);
- _nodes[resItem].endtime = _rdfstime;
+ _topsorted.push_back(item);
+ _nodes[item].endtime = _rdfstime;
_rdfstime++;
- _DBG("RC_SPEW") << resItem->asString() << " done" << endl;
+ XXX << ITEMNAME(item) << " done" << endl;
+}
+
+
+void
+InstallOrder::startrdfs()
+{
+ _nodes.clear();
+ _rgraph.clear();
+ _graph.clear();
+
+ _rdfstime = 1;
+
+ _topsorted.clear();
+
+ _numrun++;
+ XXX << "run #" << _numrun << endl;
+
+ // initialize all nodes
+ for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
+ {
+ PoolItem item = *it;
+ _nodes[item] = NodeInfo (item);
+ _rgraph[item] = PoolItemList();
+ _graph[item] = PoolItemList();
+ }
+
+ // visit all nodes
+ for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
+ {
+ const PoolItem item = *it;
+ if (_nodes[item].visited == false)
+ {
+ XXX << "start recursion on " << ITEMNAME(item) << endl;
+ rdfsvisit (item);
+ }
+ }
+
+ _dirty = false;
}
//-----------------------------------------------------------------------------
-const CResItemList&
+const PoolItemList
InstallOrder::getTopSorted() const
{
return _topsorted;
projects / platform / upstream / libzypp.git / blobdiff