InstallOrder.cc
Go to the documentation of this file.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/LogTools.h"
00032 #include "zypp/base/Iterator.h"
00033 #include "zypp/base/Algorithm.h"
00034
00035 #include "zypp/solver/detail/SATResolver.h"
00036
00037 #include "zypp/ResFilters.h"
00038 #include "zypp/ResStatus.h"
00039 #include "zypp/sat/Pool.h"
00040 #include <zypp/sat/WhatObsoletes.h>
00041
00043 namespace zypp
00044 {
00045
00046 namespace solver
00047 {
00048
00049 namespace detail
00050 {
00051
00052 using namespace std;
00053 using namespace zypp;
00054
00055 #define ITEMNAME(item) (item)->name()
00056
00057
00058 InstallOrder::InstallOrder( const ResPool & pool, const PoolItemSet & toinstall, const PoolItemSet & installed )
00059 : _pool( pool )
00060 , _toinstall( toinstall )
00061 , _installed( installed )
00062 , _dirty (true)
00063 , _numrun (0)
00064 {
00065 _DEBUG("InstallOrder::InstallOrder(_toinstall " << _toinstall.size() << " items, _installed " << _installed.size() << " items)");
00066 }
00067
00068
00069
00070
00071 void
00072 InstallOrder::printAdj (std::ostream& os, bool reversed) const
00073 {
00074 const Graph& g = (reversed ? _rgraph : _graph);
00075 os << "digraph pkgdeps {" << endl;
00076 for (Graph::const_iterator gcit = g.begin(); gcit != g.end(); ++gcit)
00077 {
00078 Nodes::const_iterator niit = _nodes.find(gcit->first);
00079 int order = niit->second.order;
00080 string name = gcit->first->name();
00081 os << "\"" << name << "\"" << "[label=\"" << name << "\\n" << order << "\"";
00082 os << "] " << endl;
00083 for (PoolItemList::const_iterator scit = gcit->second.begin(); scit != gcit->second.end(); ++scit)
00084 {
00085 os << "\"" << name << "\" -> \"" << (*scit)->name() << "\"" << endl;
00086 }
00087 }
00088 os << "}" << endl;
00089 }
00090
00091
00092
00093
00094
00095 PoolItemList
00096 InstallOrder::computeNextSet()
00097 {
00098 PoolItemList newlist;
00099
00100 if (_dirty) startrdfs();
00101
00102 for (Nodes::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
00103 {
00104 if (it->second.order == 0
00105 && it->second.item)
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 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 item ) const
00157 {
00158 Capabilities::const_iterator pend = item->dep( Dep::PROVIDES ).end();
00159 for( Capabilities::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();
00165 }
00166
00167
00168 PoolItem
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();
00178 }
00179
00180
00181
00182
00183 void
00184 InstallOrder::rdfsvisit (const PoolItem item)
00185 {
00186 typedef list<Capability> CapList;
00187 CapList requires;
00188
00189 XXX << "InstallOrder::rdfsvisit, visiting " << ITEMNAME(item) << endl;
00190
00191 NodeInfo& nodeinfo = _nodes[item];
00192
00193 nodeinfo.visited = true;
00194 nodeinfo.begintime = _rdfstime;
00195 _rdfstime++;
00196
00197
00198 CapabilitySet prq( item->dep(Dep::PREREQUIRES).begin(), item->dep(Dep::PREREQUIRES).end() );
00199
00200 ui::Selectable::Ptr sel( ui::Selectable::get( item ) );
00201 for_( it, sel->installedBegin(), sel->installedEnd() )
00202 {
00203 Capabilities p( it->satSolvable().prerequires() );
00204 prq.insert( p.begin(), p.end() );
00205 }
00206
00207 sat::WhatObsoletes obs( item );
00208 for_( it, obs.begin(), obs.end() )
00209 {
00210 Capabilities p( it->prerequires() );
00211 prq.insert( p.begin(), p.end() );
00212 }
00213
00214
00215 for (CapabilitySet::const_iterator it = prq.begin(); it != prq.end(); ++it)
00216 {
00217 requires.push_back(*it);
00218 }
00219
00220
00221
00222 if ( ! isKind<Product>( item.resolvable() ) )
00223 {
00224 for (Capabilities::const_iterator it = item->dep (Dep::REQUIRES).begin(); it != item->dep (Dep::REQUIRES).end(); ++it)
00225 {
00226 requires.push_back(*it);
00227 }
00228 }
00229
00230 for (CapList::const_iterator iter = requires.begin(); iter != requires.end(); ++iter)
00231 {
00232 bool goBack = false;
00233 const Capability requirement = *iter;
00234 PoolItemList providers;
00235
00236 XXX << "check requirement " << requirement << " of " << ITEMNAME(item) << endl;
00237 SATResolver satResolver(_pool, sat::Pool::instance().get());
00238 PoolItemList tovisit;
00239 sat::WhatProvides possibleProviders(requirement);
00240
00241
00242 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
00243 PoolItem provider = ResPool::instance().find( *iter );
00244 if ( provider == item )
00245 {
00246 goBack = true;
00247 break;
00248 }
00249 if (_installed.find( provider ) != _installed.end())
00250 {
00251 XXX << "tovisit " << ITEMNAME(provider) << endl;
00252 providers.push_back (provider);
00253 }
00254 }
00255
00256 if ( goBack )
00257 continue;
00258
00259
00260
00261 if (providers.empty()) {
00262 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
00263 PoolItem provider = ResPool::instance().find( *iter );
00264 if ((provider.resolvable() != item.resolvable())
00265 && (_toinstall.find( provider ) != _toinstall.end()))
00266 {
00267 XXX << "tovisit " << ITEMNAME(provider) << endl;
00268 tovisit.push_back (provider);
00269 }
00270 }
00271 }
00272
00273 for (PoolItemList::iterator it = tovisit.begin(); it != tovisit.end(); ++it)
00274 {
00275 const PoolItem must_visit = *it;
00276 if (_nodes[must_visit].visited == false)
00277 {
00278 nodeinfo.order++;
00279 _rgraph[must_visit].push_back( item );
00280 _graph[item].push_back( must_visit );
00281 rdfsvisit( must_visit );
00282 }
00283 else if (_nodes[must_visit].endtime == 0)
00284 {
00285 if (must_visit != item)
00286 {
00287
00288 std::string lstr( ITEMNAME(item) );
00289 lstr += " -> ";
00290 lstr += ITEMNAME(must_visit);
00291 if ( _logset.insert( lstr ).second )
00292 {
00293 WAR << "** dependency loop: " << lstr << endl;
00294 }
00295 }
00296 }
00297 else
00298 {
00299
00300 PoolItemList & lrg = _rgraph[must_visit];
00301 if( find( lrg.begin(), lrg.end(), item) == lrg.end() )
00302 {
00303 nodeinfo.order++;
00304 lrg.push_back( item );
00305
00306 PoolItemList & lg = _graph[item];
00307 if( find( lg.begin(), lg.end(), must_visit ) == lg.end() )
00308 lg.push_back( must_visit );
00309 }
00310 }
00311 }
00312 }
00313 _topsorted.push_back(item);
00314 _nodes[item].endtime = _rdfstime;
00315 _rdfstime++;
00316
00317 XXX << ITEMNAME(item) << " done" << endl;
00318 }
00319
00320
00321 void
00322 InstallOrder::startrdfs()
00323 {
00324 _nodes.clear();
00325 _rgraph.clear();
00326 _graph.clear();
00327
00328 _rdfstime = 1;
00329
00330 _topsorted.clear();
00331
00332 _numrun++;
00333 XXX << "run #" << _numrun << endl;
00334
00335
00336 for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
00337 {
00338 PoolItem item = *it;
00339 _nodes[item] = NodeInfo (item);
00340 _rgraph[item] = PoolItemList();
00341 _graph[item] = PoolItemList();
00342 }
00343
00344
00345 for (PoolItemSet::iterator it = _toinstall.begin(); it != _toinstall.end(); ++it)
00346 {
00347 const PoolItem item = *it;
00348 if (_nodes[item].visited == false)
00349 {
00350 XXX << "start recursion on " << ITEMNAME(item) << endl;
00351 rdfsvisit (item);
00352 }
00353 }
00354
00355 _dirty = false;
00356 }
00357
00358
00359
00360
00361 const PoolItemList
00362 InstallOrder::getTopSorted() const
00363 {
00364 return _topsorted;
00365 }
00366
00367
00369 };
00372 };
00375 };