00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
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
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)
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
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
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;
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
00195
00196
00197
00198 XXX << "info(" << c_and_i.item <<")"<< endl;
00199 if ((c_and_i.item.resolvable() != requestor.resolvable())
00200 && (limitto.find( c_and_i.item ) != limitto.end()))
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
00229
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
00252 Dep dep (Dep::PROVIDES);
00253
00254
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
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
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
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
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 };
00367 };
00370 };