1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
4 * Copyright (C) 2005 SUSE Linux Products GmbH
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License,
8 * version 2, as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 // stolen from yast2-packagemanager
24 Purpose: Determine order for installing packages
25 Author: Ludwig Nussel <lnussel@suse.de>
26 Maintainer: Ludwig Nussel <lnussel@suse.de>
30 #include "zypp/solver/detail/InstallOrder.h"
31 #include "zypp/base/Logger.h"
32 #include "zypp/base/Iterator.h"
33 #include "zypp/base/Algorithm.h"
35 #include "zypp/ResFilters.h"
36 #include "zypp/ResStatus.h"
38 /////////////////////////////////////////////////////////////////////////
40 { ///////////////////////////////////////////////////////////////////////
41 ///////////////////////////////////////////////////////////////////////
43 { /////////////////////////////////////////////////////////////////////
44 /////////////////////////////////////////////////////////////////////
46 { ///////////////////////////////////////////////////////////////////
51 //-----------------------------------------------------------------------------
53 InstallOrder::InstallOrder(const ResPool *pool, const PoolItemList & toinstall, const PoolItemList & installed)
58 for (PoolItemList::const_iterator iter = toinstall.begin(); iter != toinstall.end(); ++iter)
59 _toinstall.insert (*iter);
60 for (PoolItemList::const_iterator iter = installed.begin(); iter != installed.end(); ++iter)
61 _installed.insert (*iter);
65 //-----------------------------------------------------------------------------
68 InstallOrder::printAdj (std::ostream& os, bool reversed) const
70 const Graph& g = (reversed ? _rgraph : _graph);
71 os << "digraph pkgdeps {" << endl;
72 for (Graph::const_iterator gcit = g.begin(); gcit != g.end(); ++gcit)
74 Nodes::const_iterator niit = _nodes.find(gcit->first);
75 int order = niit->second.order;
76 string name = gcit->first.resolvable()->name();
77 os << "\"" << name << "\"" << "[label=\"" << name << "\\n" << order << "\"";
79 for (PoolItemSet::const_iterator scit = gcit->second.begin(); scit != gcit->second.end(); ++scit)
81 os << "\"" << name << "\" -> \"" << (*scit).resolvable()->name() << "\"" << endl;
88 //-----------------------------------------------------------------------------
90 // yea, that stuff is suboptimal. there should be a heap sorted by order
92 InstallOrder::computeNextSet()
96 if (_dirty) startrdfs();
98 for (Nodes::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
100 if (it->second.order == 0)
102 _DBG("RC_SPEW") << "InstallOrder::computeNextSet found " << it->second.item << endl;
104 newlist.push_back(it->second.item);
112 // decrease order of every adjacent node
114 InstallOrder::setInstalled(const PoolItem item )
118 PoolItemSet & adj = _rgraph[item];
120 _DBG("RC_SPEW") << "InstallOrder::setInstalled " << item << endl;
123 _nodes[item].order--;
124 _installed.insert (item);
125 _toinstall.erase (item);
127 for (PoolItemSet::iterator it = adj.begin(); it != adj.end(); ++it)
129 NodeInfo& info = _nodes[*it];
133 DBG << "order of node " << (*it) << " is < 0" << endl;
140 InstallOrder::setInstalled( const PoolItemList & rl )
142 for (PoolItemList::const_iterator it = rl.begin(); it != rl.end(); ++it)
148 //-----------------------------------------------------------------------------
152 InstallOrder::startrdfs()
163 _DBG("RC_SPEW") << "run #" << _numrun << endl;
165 // initialize all nodes
166 for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
168 const PoolItem item = *it;
169 _nodes[item] = NodeInfo (item);
170 _rgraph[item] = PoolItemSet();
171 _graph[item] = PoolItemSet();
175 for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
177 const PoolItem item = *it;
178 if (_nodes[item].visited == false)
180 _DBG("RC_SPEW") << "start recursion on " << item << endl;
191 struct CollectProviders : public resfilter::OnCapMatchCallbackFunctor
193 const PoolItem requestor;
194 PoolItemSet & tovisit;
195 PoolItemSet & toinstall;
196 PoolItemSet & installed;
198 CollectProviders info (const PoolItem pi, PoolItemSet & tv, PoolItemSet & ti, PoolItemSet i)
206 bool operator()( PoolItem provider, const Capability & match ) const
208 // Untill we can pass the functor by reference to algorithms.
209 return const_cast<RequireProcess&>(*this).fake( provider, match );
211 bool fake( PoolItem provider, const Capability & match )
213 // item provides cap which matches a requirement from info->requestor
214 // this function gets _all_ providers and filter out those which are
215 // either installed or in our toinstall input list
218 if ((provider != requestor) // package could provide its own requirement
220 // && (!(item->status().isInstalled()) // only visit if provider is not already installed
221 && (toinstall->find(provider) != toinstall->end() // only look at packages
222 || installed->find(provider) != installed->end())) { // we are currently considering anyways
223 tovisit->insert (provider);
233 InstallOrder::rdfsvisit (const PoolItem item)
235 typedef list<Capability> CapList;
238 _DBG ("RC_SPEW") << "InstallOrder::rdfsvisit, visiting " << item << endl;
240 NodeInfo& nodeinfo = _nodes[item];
242 nodeinfo.visited = true;
243 nodeinfo.begintime = _rdfstime;
246 // put prerequires first and requires last on list to ensure
247 // that prerequires are processed first
249 for (CapSet::const_iterator it = item->dep (Dep::PREREQUIRES).begin(); it != item->dep (Dep::PREREQUIRES).end(); ++it)
251 const Capability cap = *it;
252 requires.push_back(cap);
255 for (CapSet::const_iterator it = item->dep (Dep::REQUIRES).begin(); it != item->dep (Dep::REQUIRES).end(); ++it)
257 const Capability cap = *it;
258 requires.push_back(cap);
261 for (CapList::const_iterator iter = requires.begin(); iter != requires.end(); ++iter)
263 const Capability requirement = *iter;
264 _DBG("RC_SPEW") << "check requirement " << requirement << " of " << item << endl;
267 CollectProviders info ( item, tovisit, _toinstall, _installed );
270 // _world->foreachProvidingResItem (requirement, collect_providers, &info);
272 Dep dep (Dep::PROVIDES);
273 invokeOnEach( _pool->byCapabilityIndexBegin( requirement.index(), dep ),
274 _pool->byCapabilityIndexEnd( requirement.index(), dep ),
275 resfilter::callOnCapMatchIn( dep, requirement, info ) );
277 for (PoolItemSet::iterator it = tovisit.begin(); it != tovisit.end(); ++it)
279 const PoolItem must_visit = *it;
280 if (_nodes[must_visit].visited == false)
283 _rgraph[must_visit].insert (item);
284 _graph[item].insert (must_visit);
285 rdfsvisit(must_visit);
287 else if (_nodes[must_visit].endtime == 0)
289 if (must_visit != item)
291 DBG << "dependency loop: " << item << " -> " << must_visit << endl;
296 // filter multiple depends on same item (cosmetic)
297 PoolItemSet & lrg = _rgraph[must_visit];
298 if (lrg.find(item) == lrg.end())
303 PoolItemSet & lg = _graph[item];
304 if (lg.find (must_visit) == lg.end())
305 lg.insert (must_visit);
310 _topsorted.push_back(item);
311 _nodes[item].endtime = _rdfstime;
314 _DBG("RC_SPEW") << item << " done" << endl;
318 //-----------------------------------------------------------------------------
321 InstallOrder::getTopSorted() const
327 ///////////////////////////////////////////////////////////////////
328 };// namespace detail
329 /////////////////////////////////////////////////////////////////////
330 /////////////////////////////////////////////////////////////////////
331 };// namespace solver
332 ///////////////////////////////////////////////////////////////////////
333 ///////////////////////////////////////////////////////////////////////
335 /////////////////////////////////////////////////////////////////////////