InstallOrder.cc

Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 /* InstallOrder.cc
00003  *
00004  * Copyright (C) 2005 SUSE Linux Products GmbH
00005  *
00006  * This program is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU General Public License,
00008  * version 2, as published by the Free Software Foundation.
00009  *
00010  * This program is distributed in the hope that it will be useful, but
00011  * WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU General Public License
00016  * along with this program; if not, write to the Free Software
00017  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00018  * 02111-1307, USA.
00019  */
00020 
00021 // stolen from yast2-packagemanager
00022 /*
00023    File:       InstallOrder.h
00024    Purpose:    Determine order for installing packages
00025    Author:     Ludwig Nussel <lnussel@suse.de>
00026    Maintainer: Ludwig Nussel <lnussel@suse.de>
00027 
00028 /-*/
00029 
00030 #include "zypp/solver/detail/InstallOrder.h"
00031 #include "zypp/base/Logger.h"
00032 #include "zypp/base/Iterator.h"
00033 #include "zypp/base/Algorithm.h"
00034 
00035 #include "zypp/ResFilters.h"
00036 #include "zypp/ResStatus.h"
00037 #include "zypp/CapAndItem.h"
00038 
00040 namespace zypp
00041 { 
00042 
00043   namespace solver
00044   { 
00045 
00046     namespace detail
00047     { 
00048 
00049 using namespace std;
00050 using namespace zypp;
00051 
00052 #define ITEMNAME(item) (item)->name()
00053 //-----------------------------------------------------------------------------
00054 
00055 InstallOrder::InstallOrder( const ResPool & pool, const PoolItemSet & toinstall, const PoolItemSet & installed )
00056     : _pool( pool )
00057     , _toinstall( toinstall )
00058     , _installed( installed )
00059     , _dirty (true)
00060     , _numrun (0)
00061 {
00062     _DEBUG("InstallOrder::InstallOrder(_toinstall " << _toinstall.size() << " items, _installed " << _installed.size() << " items)");
00063 }
00064 
00065 
00066 //-----------------------------------------------------------------------------
00067 
00068 const void
00069 InstallOrder::printAdj (std::ostream& os, bool reversed) const
00070 {
00071     const Graph& g = (reversed ? _rgraph : _graph);
00072     os << "digraph pkgdeps {" << endl;
00073     for (Graph::const_iterator gcit = g.begin(); gcit != g.end(); ++gcit)
00074     {
00075         Nodes::const_iterator niit = _nodes.find(gcit->first);
00076         int order = niit->second.order;
00077         string name = gcit->first->name();
00078         os << "\"" << name << "\"" << "[label=\"" << name << "\\n" << order << "\"";
00079         os << "] " << endl;
00080         for (PoolItemList::const_iterator scit = gcit->second.begin(); scit != gcit->second.end(); ++scit)
00081         {
00082             os << "\"" << name << "\" -> \"" << (*scit)->name() << "\"" << endl;
00083         }
00084     }
00085     os << "}" << endl;
00086 }
00087 
00088 
00089 //-----------------------------------------------------------------------------
00090 
00091 // yea, that stuff is suboptimal. there should be a heap sorted by order
00092 PoolItemList
00093 InstallOrder::computeNextSet()
00094 {
00095     PoolItemList newlist;
00096 
00097     if (_dirty) startrdfs();
00098 
00099     for (Nodes::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
00100     {
00101         if (it->second.order == 0
00102             && it->second.item)                 // the default Nodes constructor leaves this empty
00103         {
00104             if (isKind<SystemResObject>( it->second.item.resolvable() ))
00105                 continue;
00106 
00107             XXX << "InstallOrder::computeNextSet found " << ITEMNAME(it->second.item) << endl;
00108 
00109             newlist.push_back(it->second.item);
00110         }
00111     }
00112 
00113     return newlist;
00114 }
00115 
00116 
00117 // decrease order of every adjacent node
00118 void
00119 InstallOrder::setInstalled(PoolItem_Ref item )
00120 {
00121     _dirty = true;
00122 
00123     PoolItemList adj = _rgraph[item];
00124 
00125     XXX << "InstallOrder::setInstalled " << ITEMNAME(item) << endl;
00126 
00127     // order will be < 0
00128     _nodes[item].order--;
00129     _installed.insert( item );
00130     _toinstall.erase( item );
00131 
00132     for (PoolItemList::iterator it = adj.begin(); it != adj.end(); ++it)
00133     {
00134         NodeInfo& info = _nodes[*it];
00135         info.order--;
00136         if (info.order < 0)
00137         {
00138             WAR << "order of node " << (*it) << " is < 0" << endl;
00139         }
00140     }
00141 }
00142 
00143 
00144 void
00145 InstallOrder::setInstalled( const PoolItemList & rl )
00146 {
00147     for (PoolItemList::const_iterator it = rl.begin(); it != rl.end(); ++it)
00148     {
00149         setInstalled(*it);
00150     }
00151 }
00152 
00153 //-----------------------------------------------------------------------------
00154 
00155 bool
00156 InstallOrder::doesProvide( const Capability requirement, PoolItem_Ref item ) const
00157 {
00158     CapSet::const_iterator pend = item->dep( Dep::PROVIDES ).end();
00159     for( CapSet::const_iterator pit = item->dep( Dep::PROVIDES ).begin(); pit != pend; ++pit) {
00160         if( pit->matches( requirement ) == CapMatch::yes ) {
00161             return item;
00162         }
00163     }
00164     return PoolItem_Ref();
00165 }
00166 
00167 
00168 PoolItem_Ref
00169 InstallOrder::findProviderInSet( const Capability requirement, const PoolItemSet & candidates ) const
00170 {
00171     for( PoolItemSet::const_iterator citer = candidates.begin(); citer != candidates.end(); citer++) {
00172         if( doesProvide( requirement, *citer ) ) {
00173             return *citer;
00174         }
00175     }
00176 
00177     return PoolItem_Ref();
00178 }
00179 
00180 struct CollectProviders
00181 {
00182     const PoolItem_Ref requestor;
00183     PoolItemList result;
00184     const PoolItemSet & limitto;                // limit search to members of this set
00185 
00186     CollectProviders (const PoolItem_Ref pi, const PoolItemSet & limit)
00187         : requestor (pi)
00188         , limitto (limit)
00189     { }
00190 
00191 
00192     bool operator()( const CapAndItem & c_and_i )
00193     {
00194         // item provides cap which matches a requirement from info->requestor
00195         //   this function gets _all_ providers and filter out those which are
00196         //   either installed or in our toinstall input list
00197         //
00198 XXX << "info(" << c_and_i.item <<")"<< endl;
00199         if ((c_and_i.item.resolvable() != requestor.resolvable())       // resolvable could provide its own requirement
00200             && (limitto.find( c_and_i.item ) != limitto.end()))         // limit to members of 'limitto' set
00201         {
00202             XXX << "tovisit " << ITEMNAME(c_and_i.item) << endl;
00203             result.push_back (c_and_i.item);
00204         }
00205 
00206         return true;
00207     }
00208 
00209 };
00210 
00211 //-----------------------------------------------------------------------------
00212 
00213 
00214 void
00215 InstallOrder::rdfsvisit (const PoolItem_Ref item)
00216 {
00217     typedef list<Capability> CapList;
00218     CapList requires;
00219 
00220     XXX << "InstallOrder::rdfsvisit, visiting " << ITEMNAME(item) << endl;
00221 
00222     NodeInfo& nodeinfo = _nodes[item];
00223 
00224     nodeinfo.visited = true;
00225     nodeinfo.begintime = _rdfstime;
00226     _rdfstime++;
00227 
00228     // put prerequires first and requires last on list to ensure
00229     // that prerequires are processed first
00230     for (CapSet::const_iterator it = item->dep (Dep::PREREQUIRES).begin(); it != item->dep (Dep::PREREQUIRES).end(); ++it)
00231     {
00232         const Capability cap = *it;
00233         requires.push_back(cap);
00234     }
00235 
00236     if ( ! isKind<Product>( item.resolvable() ) )
00237       {
00238         for (CapSet::const_iterator it = item->dep (Dep::REQUIRES).begin(); it != item->dep (Dep::REQUIRES).end(); ++it)
00239           {
00240             const Capability cap = *it;
00241             requires.push_back(cap);
00242           }
00243       }
00244 
00245     for (CapList::const_iterator iter = requires.begin(); iter != requires.end(); ++iter)
00246     {
00247         const Capability requirement = *iter;
00248         XXX << "check requirement " << requirement << " of " << ITEMNAME(item) << endl;
00249         PoolItemList tovisit;
00250 
00251         // _world->foreachProvidingResItem (requirement, collect_providers, &info);
00252         Dep dep (Dep::PROVIDES);
00253 
00254         // first, look in _installed
00255         CollectProviders info ( item, _installed );
00256 
00257         invokeOnEach( _pool.byCapabilityIndexBegin( requirement.index(), dep ),
00258                       _pool.byCapabilityIndexEnd( requirement.index(), dep ),
00259                       resfilter::ByCapMatch( requirement ),
00260                       functor::functorRef<bool,CapAndItem>(info) );
00261 
00262         // if not found in _iustalled, look in _toinstall
00263 
00264         if (info.result.empty()) {
00265             CollectProviders info1 ( item, _toinstall );
00266 
00267             invokeOnEach( _pool.byCapabilityIndexBegin( requirement.index(), dep ),
00268                           _pool.byCapabilityIndexEnd( requirement.index(), dep ),
00269                           resfilter::ByCapMatch( requirement ),
00270                           functor::functorRef<bool,CapAndItem>(info1) );
00271 
00272             tovisit = info1.result;
00273         }
00274 
00275         for (PoolItemList::iterator it = tovisit.begin(); it != tovisit.end(); ++it)
00276         {
00277             const PoolItem_Ref must_visit = *it;
00278             if (_nodes[must_visit].visited == false)
00279             {
00280                 nodeinfo.order++;
00281                 _rgraph[must_visit].push_back( item );
00282                 _graph[item].push_back( must_visit );
00283                 rdfsvisit( must_visit );
00284             }
00285             else if (_nodes[must_visit].endtime == 0)
00286             {
00287                 if (must_visit != item)
00288                 {
00289                     WAR << "** dependency loop: " << ITEMNAME(item) << " -> " << ITEMNAME(must_visit) << endl;
00290                 }
00291             }
00292             else
00293             {
00294                 // filter multiple depends on same item (cosmetic)
00295                 PoolItemList & lrg = _rgraph[must_visit];
00296                 if( find( lrg.begin(), lrg.end(), item) == lrg.end() )
00297                 {
00298                     nodeinfo.order++;
00299                     lrg.push_back( item );
00300 
00301                     PoolItemList & lg = _graph[item];
00302                     if( find( lg.begin(), lg.end(), must_visit ) == lg.end() )
00303                         lg.push_back( must_visit );
00304                 }
00305             }
00306         }
00307     }
00308     _topsorted.push_back(item);
00309     _nodes[item].endtime = _rdfstime;
00310     _rdfstime++;
00311 
00312     XXX << ITEMNAME(item) << " done" << endl;
00313 }
00314 
00315 
00316 void
00317 InstallOrder::startrdfs()
00318 {
00319     _nodes.clear();
00320     _rgraph.clear();
00321     _graph.clear();
00322 
00323     _rdfstime = 1;
00324 
00325     _topsorted.clear();
00326 
00327     _numrun++;
00328     XXX << "run #" << _numrun << endl;
00329 
00330     // initialize all nodes
00331     for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
00332     {
00333         PoolItem_Ref item = *it;
00334         _nodes[item] = NodeInfo (item);
00335         _rgraph[item] = PoolItemList();
00336         _graph[item] = PoolItemList();
00337     }
00338 
00339     // visit all nodes
00340     for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
00341     {
00342         const PoolItem_Ref item = *it;
00343         if (_nodes[item].visited == false)
00344         {
00345             XXX << "start recursion on " << ITEMNAME(item) << endl;
00346             rdfsvisit (item);
00347         }
00348     }
00349 
00350     _dirty = false;
00351 }
00352 
00353 
00354 //-----------------------------------------------------------------------------
00355 
00356 const PoolItemList
00357 InstallOrder::getTopSorted() const
00358 {
00359     return _topsorted;
00360 }
00361 
00362 
00364     };// namespace detail
00367   };// namespace solver
00370 };// namespace zypp

Generated on Thu Jul 6 00:07:23 2006 for zypp by  doxygen 1.4.6