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/LogTools.h"
32 #include "zypp/base/Iterator.h"
33 #include "zypp/base/Algorithm.h"
35 #include "zypp/ResFilters.h"
36 #include "zypp/ResStatus.h"
37 #include "zypp/CapAndItem.h"
38 #include "zypp/NameKindProxy.h"
40 /////////////////////////////////////////////////////////////////////////
42 { ///////////////////////////////////////////////////////////////////////
43 ///////////////////////////////////////////////////////////////////////
45 { /////////////////////////////////////////////////////////////////////
46 /////////////////////////////////////////////////////////////////////
48 { ///////////////////////////////////////////////////////////////////
53 #define ITEMNAME(item) (item)->name()
54 //-----------------------------------------------------------------------------
56 InstallOrder::InstallOrder( const ResPool & pool, const PoolItemSet & toinstall, const PoolItemSet & installed )
58 , _toinstall( toinstall )
59 , _installed( installed )
63 _DEBUG("InstallOrder::InstallOrder(_toinstall " << _toinstall.size() << " items, _installed " << _installed.size() << " items)");
67 //-----------------------------------------------------------------------------
70 InstallOrder::printAdj (std::ostream& os, bool reversed) const
72 const Graph& g = (reversed ? _rgraph : _graph);
73 os << "digraph pkgdeps {" << endl;
74 for (Graph::const_iterator gcit = g.begin(); gcit != g.end(); ++gcit)
76 Nodes::const_iterator niit = _nodes.find(gcit->first);
77 int order = niit->second.order;
78 string name = gcit->first->name();
79 os << "\"" << name << "\"" << "[label=\"" << name << "\\n" << order << "\"";
81 for (PoolItemList::const_iterator scit = gcit->second.begin(); scit != gcit->second.end(); ++scit)
83 os << "\"" << name << "\" -> \"" << (*scit)->name() << "\"" << endl;
90 //-----------------------------------------------------------------------------
92 // yea, that stuff is suboptimal. there should be a heap sorted by order
94 InstallOrder::computeNextSet()
98 if (_dirty) startrdfs();
100 for (Nodes::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
102 if (it->second.order == 0
103 && it->second.item) // the default Nodes constructor leaves this empty
105 if (isKind<SystemResObject>( it->second.item.resolvable() ))
108 XXX << "InstallOrder::computeNextSet found " << ITEMNAME(it->second.item) << endl;
110 newlist.push_back(it->second.item);
118 // decrease order of every adjacent node
120 InstallOrder::setInstalled(PoolItem_Ref item )
124 PoolItemList adj = _rgraph[item];
126 XXX << "InstallOrder::setInstalled " << ITEMNAME(item) << endl;
129 _nodes[item].order--;
130 _installed.insert( item );
131 _toinstall.erase( item );
133 for (PoolItemList::iterator it = adj.begin(); it != adj.end(); ++it)
135 NodeInfo& info = _nodes[*it];
139 WAR << "order of node " << (*it) << " is < 0" << endl;
146 InstallOrder::setInstalled( const PoolItemList & rl )
148 for (PoolItemList::const_iterator it = rl.begin(); it != rl.end(); ++it)
154 //-----------------------------------------------------------------------------
157 InstallOrder::doesProvide( const Capability requirement, PoolItem_Ref item ) const
159 CapSet::const_iterator pend = item->dep( Dep::PROVIDES ).end();
160 for( CapSet::const_iterator pit = item->dep( Dep::PROVIDES ).begin(); pit != pend; ++pit) {
161 if( pit->matches( requirement ) == CapMatch::yes ) {
165 return PoolItem_Ref();
170 InstallOrder::findProviderInSet( const Capability requirement, const PoolItemSet & candidates ) const
172 for( PoolItemSet::const_iterator citer = candidates.begin(); citer != candidates.end(); citer++) {
173 if( doesProvide( requirement, *citer ) ) {
178 return PoolItem_Ref();
181 struct CollectProviders
183 const PoolItem_Ref requestor;
185 const PoolItemSet & limitto; // limit search to members of this set
187 CollectProviders (const PoolItem_Ref pi, const PoolItemSet & limit)
193 bool operator()( const CapAndItem & c_and_i )
195 // item provides cap which matches a requirement from info->requestor
196 // this function gets _all_ providers and filter out those which are
197 // either installed or in our toinstall input list
199 XXX << "info(" << c_and_i.item <<")"<< endl;
200 if ((c_and_i.item.resolvable() != requestor.resolvable()) // resolvable could provide its own requirement
201 && (limitto.find( c_and_i.item ) != limitto.end())) // limit to members of 'limitto' set
203 XXX << "tovisit " << ITEMNAME(c_and_i.item) << endl;
204 result.push_back (c_and_i.item);
212 //-----------------------------------------------------------------------------
216 InstallOrder::rdfsvisit (const PoolItem_Ref item)
218 typedef list<Capability> CapList;
221 XXX << "InstallOrder::rdfsvisit, visiting " << ITEMNAME(item) << endl;
223 NodeInfo& nodeinfo = _nodes[item];
225 nodeinfo.visited = true;
226 nodeinfo.begintime = _rdfstime;
230 CapSet prq( item->dep(Dep::PREREQUIRES) );
231 // an installed items prereq (in case they are reqired for uninstall scripts)
232 NameKindProxy nkp( _pool, item->name(), item->kind() );
233 if ( ! nkp.installedEmpty() )
235 prq.insert( (*nkp.installedBegin())->dep(Dep::PREREQUIRES).begin(),
236 (*nkp.installedBegin())->dep(Dep::PREREQUIRES).end() );
238 // put prerequires first and requires last on list to ensure
239 // that prerequires are processed first
240 for (CapSet::const_iterator it = prq.begin(); it != prq.end(); ++it)
242 requires.push_back(*it);
245 // Product requirements are ignored to assert Product gets installed
246 // as early as possible. Some stuff depends on it (e.g. registration).
247 if ( ! isKind<Product>( item.resolvable() ) )
249 for (CapSet::const_iterator it = item->dep (Dep::REQUIRES).begin(); it != item->dep (Dep::REQUIRES).end(); ++it)
251 requires.push_back(*it);
255 for (CapList::const_iterator iter = requires.begin(); iter != requires.end(); ++iter)
257 const Capability requirement = *iter;
258 XXX << "check requirement " << requirement << " of " << ITEMNAME(item) << endl;
259 PoolItemList tovisit;
261 // _world->foreachProvidingResItem (requirement, collect_providers, &info);
262 Dep dep (Dep::PROVIDES);
264 // first, look in _installed
265 CollectProviders info ( item, _installed );
267 invokeOnEach( _pool.byCapabilityIndexBegin( requirement.index(), dep ),
268 _pool.byCapabilityIndexEnd( requirement.index(), dep ),
269 resfilter::ByCapMatch( requirement ),
270 functor::functorRef<bool,CapAndItem>(info) );
272 // if not found in _iustalled, look in _toinstall
274 if (info.result.empty()) {
275 CollectProviders info1 ( item, _toinstall );
277 invokeOnEach( _pool.byCapabilityIndexBegin( requirement.index(), dep ),
278 _pool.byCapabilityIndexEnd( requirement.index(), dep ),
279 resfilter::ByCapMatch( requirement ),
280 functor::functorRef<bool,CapAndItem>(info1) );
282 tovisit = info1.result;
285 for (PoolItemList::iterator it = tovisit.begin(); it != tovisit.end(); ++it)
287 const PoolItem_Ref must_visit = *it;
288 if (_nodes[must_visit].visited == false)
291 _rgraph[must_visit].push_back( item );
292 _graph[item].push_back( must_visit );
293 rdfsvisit( must_visit );
295 else if (_nodes[must_visit].endtime == 0)
297 if (must_visit != item)
299 WAR << "** dependency loop: " << ITEMNAME(item) << " -> " << ITEMNAME(must_visit) << endl;
304 // filter multiple depends on same item (cosmetic)
305 PoolItemList & lrg = _rgraph[must_visit];
306 if( find( lrg.begin(), lrg.end(), item) == lrg.end() )
309 lrg.push_back( item );
311 PoolItemList & lg = _graph[item];
312 if( find( lg.begin(), lg.end(), must_visit ) == lg.end() )
313 lg.push_back( must_visit );
318 _topsorted.push_back(item);
319 _nodes[item].endtime = _rdfstime;
322 XXX << ITEMNAME(item) << " done" << endl;
327 InstallOrder::startrdfs()
338 XXX << "run #" << _numrun << endl;
340 // initialize all nodes
341 for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
343 PoolItem_Ref item = *it;
344 _nodes[item] = NodeInfo (item);
345 _rgraph[item] = PoolItemList();
346 _graph[item] = PoolItemList();
350 for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
352 const PoolItem_Ref item = *it;
353 if (_nodes[item].visited == false)
355 XXX << "start recursion on " << ITEMNAME(item) << endl;
364 //-----------------------------------------------------------------------------
367 InstallOrder::getTopSorted() const
373 ///////////////////////////////////////////////////////////////////
374 };// namespace detail
375 /////////////////////////////////////////////////////////////////////
376 /////////////////////////////////////////////////////////////////////
377 };// namespace solver
378 ///////////////////////////////////////////////////////////////////////
379 ///////////////////////////////////////////////////////////////////////
381 /////////////////////////////////////////////////////////////////////////