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)
55 , _toinstall (toinstall.begin(), toinstall.end())
56 , _installed (installed.begin(), installed.end())
60 _DEBUG("InstallOrder::InstallOrder(_toinstall " << _toinstall.size() << " items, _installed " << _installed.size() << " items)");
64 //-----------------------------------------------------------------------------
67 InstallOrder::printAdj (std::ostream& os, bool reversed) const
69 const Graph& g = (reversed ? _rgraph : _graph);
70 os << "digraph pkgdeps {" << endl;
71 for (Graph::const_iterator gcit = g.begin(); gcit != g.end(); ++gcit)
73 Nodes::const_iterator niit = _nodes.find(gcit->first);
74 int order = niit->second.order;
75 string name = gcit->first.resolvable()->name();
76 os << "\"" << name << "\"" << "[label=\"" << name << "\\n" << order << "\"";
78 for (PoolItemSet::const_iterator scit = gcit->second.begin(); scit != gcit->second.end(); ++scit)
80 os << "\"" << name << "\" -> \"" << (*scit).resolvable()->name() << "\"" << endl;
87 //-----------------------------------------------------------------------------
89 // yea, that stuff is suboptimal. there should be a heap sorted by order
91 InstallOrder::computeNextSet()
95 if (_dirty) startrdfs();
97 for (Nodes::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
99 if (it->second.order == 0
100 && it->second.item) // the default Nodes constructor leaves this empty
102 DBG << "InstallOrder::computeNextSet found " << it->second.item << endl;
104 newlist.push_back(it->second.item);
112 // decrease order of every adjacent node
114 InstallOrder::setInstalled(PoolItem_Ref item )
118 PoolItemSet adj = _rgraph[item];
120 DBG << "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 << "run #" << _numrun << endl;
165 // initialize all nodes
166 for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
168 PoolItem_Ref 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_Ref item = *it;
178 if (_nodes[item].visited == false)
180 DBG << "start recursion on " << item << endl;
191 struct CollectProviders : public resfilter::OnCapMatchCallbackFunctor
193 const PoolItem_Ref requestor;
194 PoolItemSet & tovisit;
195 PoolItemSet & toinstall;
196 PoolItemSet & installed;
198 CollectProviders (const PoolItem_Ref pi, PoolItemSet & tv, PoolItemSet & ti, PoolItemSet i)
206 bool operator()( PoolItem_Ref provider, const Capability & match )
208 // item provides cap which matches a requirement from info->requestor
209 // this function gets _all_ providers and filter out those which are
210 // either installed or in our toinstall input list
213 if ((provider.resolvable() != requestor.resolvable()) // resolvable could provide its own requirement
214 && (!provider.status().staysInstalled()) // only visit if provider is not already installed
215 && (toinstall.find(provider) != toinstall.end() // only look at resolvables
216 || installed.find(provider) != installed.end())) { // we are currently considering anyways
217 tovisit.insert (provider);
227 InstallOrder::rdfsvisit (const PoolItem_Ref item)
229 typedef list<Capability> CapList;
232 DBG << "InstallOrder::rdfsvisit, visiting " << item << endl;
234 NodeInfo& nodeinfo = _nodes[item];
236 nodeinfo.visited = true;
237 nodeinfo.begintime = _rdfstime;
240 // put prerequires first and requires last on list to ensure
241 // that prerequires are processed first
243 for (CapSet::const_iterator it = item->dep (Dep::PREREQUIRES).begin(); it != item->dep (Dep::PREREQUIRES).end(); ++it)
245 const Capability cap = *it;
246 requires.push_back(cap);
249 for (CapSet::const_iterator it = item->dep (Dep::REQUIRES).begin(); it != item->dep (Dep::REQUIRES).end(); ++it)
251 const Capability cap = *it;
252 requires.push_back(cap);
255 for (CapList::const_iterator iter = requires.begin(); iter != requires.end(); ++iter)
257 const Capability requirement = *iter;
258 XXX << "check requirement " << requirement << " of " << item << endl;
261 CollectProviders info ( item, tovisit, _toinstall, _installed );
264 // _world->foreachProvidingResItem (requirement, collect_providers, &info);
266 Dep dep (Dep::PROVIDES);
267 invokeOnEach( _pool.byCapabilityIndexBegin( requirement.index(), dep ),
268 _pool.byCapabilityIndexEnd( requirement.index(), dep ),
269 resfilter::callOnCapMatchIn( dep, requirement, functor::functorRef<bool,PoolItem,Capability>(info) ) );
271 ResPool::const_indexiterator pend = _pool.providesend(requirement.index());
272 for (ResPool::const_indexiterator it = _pool.providesbegin(requirement.index()); it != pend; ++it) {
273 if (it->second.second->arch() == Arch_src)
275 if (requirement.matches (it->second.first) == CapMatch::yes) {
276 if (!info( it->second.second, it->second.first))
281 for (PoolItemSet::iterator it = tovisit.begin(); it != tovisit.end(); ++it)
283 const PoolItem_Ref must_visit = *it;
284 if (_nodes[must_visit].visited == false)
287 _rgraph[must_visit].insert (item);
288 _graph[item].insert (must_visit);
289 rdfsvisit(must_visit);
291 else if (_nodes[must_visit].endtime == 0)
293 if (must_visit != item)
295 ERR << "*************************************************************" << endl;
296 ERR << "** dependency loop: " << item << " -> " << must_visit << endl;
297 ERR << "*************************************************************" << endl;
302 // filter multiple depends on same item (cosmetic)
303 PoolItemSet & lrg = _rgraph[must_visit];
304 if (lrg.find(item) == lrg.end())
309 PoolItemSet & lg = _graph[item];
310 if (lg.find (must_visit) == lg.end())
311 lg.insert (must_visit);
316 _topsorted.push_back(item);
317 _nodes[item].endtime = _rdfstime;
320 DBG << item << " done" << endl;
324 //-----------------------------------------------------------------------------
327 InstallOrder::getTopSorted() const
333 ///////////////////////////////////////////////////////////////////
334 };// namespace detail
335 /////////////////////////////////////////////////////////////////////
336 /////////////////////////////////////////////////////////////////////
337 };// namespace solver
338 ///////////////////////////////////////////////////////////////////////
339 ///////////////////////////////////////////////////////////////////////
341 /////////////////////////////////////////////////////////////////////////