Use libsolv includes and adjust documentation
[platform/upstream/libzypp.git] / zypp / solver / detail / Resolver.cc
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
2 /* Resolver.cc
3  *
4  * Copyright (C) 2000-2002 Ximian, Inc.
5  * Copyright (C) 2005 SUSE Linux Products GmbH
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License,
9  * version 2, as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19  * 02111-1307, USA.
20  */
21 #include <boost/static_assert.hpp>
22
23 #include "zypp/solver/detail/Resolver.h"
24 #include "zypp/solver/detail/Helper.h"
25 #include "zypp/solver/detail/Testcase.h"
26 #include "zypp/solver/detail/SATResolver.h"
27
28 #include "zypp/Capabilities.h"
29 #include "zypp/ZConfig.h"
30 #include "zypp/base/Logger.h"
31 #include "zypp/base/String.h"
32 #include "zypp/base/Gettext.h"
33 #include "zypp/base/Algorithm.h"
34 #include "zypp/ResPool.h"
35 #include "zypp/ResFilters.h"
36 #include "zypp/sat/Pool.h"
37 #include "zypp/sat/Solvable.h"
38 #include "zypp/sat/Transaction.h"
39 #include "zypp/ResolverProblem.h"
40
41 #define MAXSOLVERRUNS 5
42
43 /////////////////////////////////////////////////////////////////////////
44 namespace zypp
45 { ///////////////////////////////////////////////////////////////////////
46   ///////////////////////////////////////////////////////////////////////
47   namespace solver
48   { /////////////////////////////////////////////////////////////////////
49     /////////////////////////////////////////////////////////////////////
50     namespace detail
51     { ///////////////////////////////////////////////////////////////////
52
53 using namespace std;
54
55 IMPL_PTR_TYPE(Resolver);
56
57
58 //---------------------------------------------------------------------------
59
60
61 std::ostream & Resolver::dumpOn( std::ostream & os ) const
62 {
63   os << "<resolver>" << endl;
64   #define OUTS(t) os << "  " << #t << ":\t" << t << endl;
65   OUTS( _forceResolve );
66   OUTS( _upgradeMode );
67   OUTS( _updateMode );
68   OUTS( _verifying );
69   OUTS( _onlyRequires );
70   OUTS( _allowVendorChange );
71   OUTS( _solveSrcPackages );
72   OUTS( _cleandepsOnRemove );
73   OUTS( _ignoreAlreadyRecommended );
74   #undef OUT
75   return os << "<resolver/>";
76 }
77
78
79 //---------------------------------------------------------------------------
80
81 Resolver::Resolver (const ResPool & pool)
82     : _pool(pool)
83     , _satResolver(NULL)
84     , _poolchanged(_pool.serial() )
85     , _forceResolve             (false)
86     , _upgradeMode              (false)
87     , _updateMode               (false)
88     , _verifying                (false)
89     , _onlyRequires             ( ZConfig::instance().solver_onlyRequires() )
90     , _allowVendorChange        ( ZConfig::instance().solver_allowVendorChange() )
91     , _solveSrcPackages         ( false )
92     , _cleandepsOnRemove        ( ZConfig::instance().solver_cleandepsOnRemove() )
93     , _ignoreAlreadyRecommended ( false )
94
95 {
96     sat::Pool satPool( sat::Pool::instance() );
97     _satResolver = new SATResolver(_pool, satPool.get());
98 }
99
100
101 Resolver::~Resolver()
102 {
103   delete _satResolver;
104 }
105
106 //---------------------------------------------------------------------------
107
108 void Resolver::setAllowVendorChange( TriBool state_r )
109 {
110   _allowVendorChange = indeterminate(state_r) ? ZConfig::instance().solver_allowVendorChange() : bool(state_r);
111 }
112
113 void Resolver::setOnlyRequires( TriBool state_r )
114 {
115   _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
116 }
117
118 void Resolver::setCleandepsOnRemove( TriBool state_r )
119 {
120   _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
121 }
122
123 //---------------------------------------------------------------------------
124
125 ResPool Resolver::pool() const
126 { return _pool; }
127
128 void Resolver::reset( bool keepExtras )
129 {
130     _verifying = false;
131
132     if (!keepExtras) {
133       _extra_requires.clear();
134       _extra_conflicts.clear();
135     }
136
137     _isInstalledBy.clear();
138     _installs.clear();
139     _satifiedByInstalled.clear();
140     _installedSatisfied.clear();
141 }
142
143 bool Resolver::doUpgrade()
144 {
145   // Setting Resolver to upgrade mode. SAT solver will do the update
146   _upgradeMode = true;
147   return resolvePool();
148 }
149
150 void Resolver::doUpdate()
151 {
152     _updateMode = true;
153     return _satResolver->doUpdate();
154 }
155
156 PoolItemList Resolver::problematicUpdateItems() const
157 { return _satResolver->problematicUpdateItems(); }
158
159 void Resolver::addExtraRequire( const Capability & capability )
160 { _extra_requires.insert (capability); }
161
162 void Resolver::removeExtraRequire( const Capability & capability )
163 { _extra_requires.erase (capability); }
164
165 void Resolver::addExtraConflict( const Capability & capability )
166 { _extra_conflicts.insert (capability); }
167
168 void Resolver::removeExtraConflict( const Capability & capability )
169 { _extra_conflicts.erase (capability); }
170
171 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
172 {
173     bool found = false;
174     for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
175          iter != _added_queue_items.end(); iter++) {
176         if (*iter == item) {
177             _added_queue_items.remove(*iter);
178             found = true;
179             break;
180         }
181     }
182     if (!found) {
183         _removed_queue_items.push_back (item);
184         _removed_queue_items.unique ();
185     }
186 }
187
188 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
189 {
190     bool found = false;
191     for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
192          iter != _removed_queue_items.end(); iter++) {
193         if (*iter == item) {
194             _removed_queue_items.remove(*iter);
195             found = true;
196             break;
197         }
198     }
199     if (!found) {
200         _added_queue_items.push_back (item);
201         _added_queue_items.unique ();
202     }
203 }
204
205 void Resolver::addWeak( const PoolItem & item )
206 { _addWeak.push_back( item ); }
207
208 //---------------------------------------------------------------------------
209
210 struct UndoTransact : public resfilter::PoolItemFilterFunctor
211 {
212     ResStatus::TransactByValue resStatus;
213     UndoTransact ( const ResStatus::TransactByValue &status)
214         :resStatus(status)
215     { }
216
217     bool operator()( PoolItem item )            // only transacts() items go here
218     {
219         item.status().resetTransact( resStatus );// clear any solver/establish transactions
220         return true;
221     }
222 };
223
224
225 struct DoTransact : public resfilter::PoolItemFilterFunctor
226 {
227     ResStatus::TransactByValue resStatus;
228     DoTransact ( const ResStatus::TransactByValue &status)
229         :resStatus(status)
230     { }
231
232     bool operator()( PoolItem item )            // only transacts() items go here
233     {
234         item.status().setTransact( true, resStatus );
235         return true;
236     }
237 };
238
239
240 bool Resolver::verifySystem()
241 {
242     UndoTransact resetting (ResStatus::APPL_HIGH);
243
244     _DEBUG ("Resolver::verifySystem() ");
245
246     _verifying = true;
247
248     invokeOnEach ( _pool.begin(), _pool.end(),
249                    resfilter::ByTransact( ),                    // Resetting all transcations
250                    functor::functorRef<bool,PoolItem>(resetting) );
251
252     return resolvePool();
253 }
254
255
256 //----------------------------------------------------------------------------
257 // undo
258
259 void Resolver::undo()
260 {
261     UndoTransact info(ResStatus::APPL_LOW);
262     MIL << "*** undo ***" << endl;
263     invokeOnEach ( _pool.begin(), _pool.end(),
264                    resfilter::ByTransact( ),                    // collect transacts from Pool to resolver queue
265                    functor::functorRef<bool,PoolItem>(info) );
266     //  Regard dependencies of the item weak onl
267     _addWeak.clear();
268
269     // Additional QueueItems which has to be regarded by the solver
270     _removed_queue_items.clear();
271     _added_queue_items.clear();
272
273     return;
274 }
275
276 void Resolver::solverInit()
277 {
278     // Solving with libsolv
279     static bool poolDumped = false;
280     MIL << "-------------- Calling SAT Solver -------------------" << endl;
281     if ( getenv("ZYPP_FULLLOG") ) {
282         Testcase testcase("/var/log/YaST2/autoTestcase");
283         if (!poolDumped) {
284             testcase.createTestcase (*this, true, false); // dump pool
285             poolDumped = true;
286         } else {
287             testcase.createTestcase (*this, false, false); // write control file only
288         }
289     }
290
291     _satResolver->setFixsystem                  ( isVerifyingMode() );
292     _satResolver->setIgnorealreadyrecommended   ( ignoreAlreadyRecommended() );
293     _satResolver->setOnlyRequires               ( onlyRequires() );
294     _satResolver->setAllowdowngrade             (false);
295     _satResolver->setAllowarchchange            (false);
296     _satResolver->setAllowvendorchange          ( allowVendorChange() );
297     _satResolver->setAllowuninstall             ( forceResolve() );
298     _satResolver->setUpdatesystem               (false);
299     _satResolver->setNoupdateprovide            (false);
300     _satResolver->setDosplitprovides            (false);
301     _satResolver->setSolveSrcPackages           ( solveSrcPackages() );
302     _satResolver->setCleandepsOnRemove          ( cleandepsOnRemove() );
303
304     _satResolver->setDistupgrade                (_upgradeMode);
305     if (_upgradeMode) {
306       // may overwrite some settings
307       _satResolver->setDistupgrade_removeunsupported    (false);
308       _satResolver->setUpdatesystem                     (true);
309       _satResolver->setAllowdowngrade                   (true);
310       _satResolver->setAllowarchchange                  (true);
311       _satResolver->setAllowvendorchange                (true);
312       _satResolver->setDosplitprovides                  (true);
313     }
314
315     // Resetting additional solver information
316     _isInstalledBy.clear();
317     _installs.clear();
318     _satifiedByInstalled.clear();
319     _installedSatisfied.clear();
320 }
321
322 bool Resolver::resolvePool()
323 {
324     solverInit();
325     return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
326 }
327
328 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
329 {
330     solverInit();
331
332     // add/remove additional SolverQueueItems
333     for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
334          iter != _removed_queue_items.end(); iter++) {
335         for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
336             if ( (*iterQueue)->cmp(*iter) == 0) {
337                 MIL << "remove from queue" << *iter;
338                 queue.remove(*iterQueue);
339                 break;
340             }
341         }
342     }
343
344     for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
345          iter != _added_queue_items.end(); iter++) {
346         bool found = false;
347         for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
348             if ( (*iterQueue)->cmp(*iter) == 0) {
349                 found = true;
350                 break;
351             }
352         }
353         if (!found) {
354             MIL << "add to queue" << *iter;
355             queue.push_back(*iter);
356         }
357     }
358
359     // The application has to take care to write these solutions back to e.g. selectables in order
360     // give the user a chance for changing these decisions again.
361     _removed_queue_items.clear();
362     _added_queue_items.clear();
363
364     return _satResolver->resolveQueue(queue, _addWeak);
365 }
366
367 sat::Transaction Resolver::getTransaction()
368 { return _satResolver->getTransaction(); }
369
370 //----------------------------------------------------------------------------
371 // Getting more information about the solve results
372
373 ResolverProblemList Resolver::problems() const
374 {
375   MIL << "Resolver::problems()" << endl;
376   return _satResolver->problems();
377 }
378
379 void Resolver::applySolutions( const ProblemSolutionList & solutions )
380 {
381   for_( iter, solutions.begin(), solutions.end() )
382   {
383     ProblemSolution_Ptr solution = *iter;
384     if ( !solution->apply( *this ) )
385       break;
386   }
387 }
388
389 void Resolver::collectResolverInfo()
390 {
391     if ( _satResolver
392          && _isInstalledBy.empty()
393          && _installs.empty()) {
394
395         // generating new
396         PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
397
398         for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
399              instIter != itemsToInstall.end(); instIter++) {
400             // Requires
401             for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
402             {
403                 sat::WhatProvides possibleProviders(*capIt);
404                 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
405                     PoolItem provider = ResPool::instance().find( *iter );
406
407                     // searching if this provider will already be installed
408                     bool found = false;
409                     bool alreadySetForInstallation = false;
410                     ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
411                     while (pos != _isInstalledBy.end()
412                            && pos->first == provider
413                            && !found) {
414                         alreadySetForInstallation = true;
415                         ItemCapKind capKind = pos->second;
416                         if (capKind.item == *instIter)  found = true;
417                         pos++;
418                     }
419
420                     if (!found
421                         && provider.status().isToBeInstalled()) {
422                         if (provider.status().isBySolver()) {
423                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
424                             _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
425                         } else {
426                             // no initial installation cause it has been set be e.g. user
427                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
428                             _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
429                         }
430                         ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
431                         _installs.insert (make_pair( *instIter, capKindisInstalledBy));
432                     }
433
434                     if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
435                         ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
436                         _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
437
438                         ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
439                         _installedSatisfied.insert (make_pair( provider, installedSatisfied));
440                     }
441                 }
442             }
443
444             if (!(_satResolver->onlyRequires())) {
445                 //Recommends
446                 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
447                 {
448                     sat::WhatProvides possibleProviders(*capIt);
449                     for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
450                         PoolItem provider = ResPool::instance().find( *iter );
451
452                         // searching if this provider will already be installed
453                         bool found = false;
454                         bool alreadySetForInstallation = false;
455                         ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
456                         while (pos != _isInstalledBy.end()
457                                && pos->first == provider
458                                && !found) {
459                             alreadySetForInstallation = true;
460                             ItemCapKind capKind = pos->second;
461                             if (capKind.item == *instIter)  found = true;
462                             pos++;
463                         }
464
465                         if (!found
466                             && provider.status().isToBeInstalled()) {
467                             if (provider.status().isBySolver()) {
468                                 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
469                                 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
470                             } else {
471                                 // no initial installation cause it has been set be e.g. user
472                                 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
473                                 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
474                             }
475                             ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
476                             _installs.insert (make_pair( *instIter, capKindisInstalledBy));
477                         }
478
479                         if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
480                             ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
481                             _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
482
483                             ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
484                             _installedSatisfied.insert (make_pair( provider, installedSatisfied));
485                         }
486                     }
487                 }
488
489                 //Supplements
490                 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
491                 {
492                     sat::WhatProvides possibleProviders(*capIt);
493                     for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
494                         PoolItem provider = ResPool::instance().find( *iter );
495                         // searching if this item will already be installed
496                         bool found = false;
497                         bool alreadySetForInstallation = false;
498                         ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
499                         while (pos != _isInstalledBy.end()
500                                && pos->first == *instIter
501                                && !found) {
502                             alreadySetForInstallation = true;
503                             ItemCapKind capKind = pos->second;
504                             if (capKind.item == provider)  found = true;
505                             pos++;
506                         }
507
508                         if (!found
509                             && instIter->status().isToBeInstalled()) {
510                             if (instIter->status().isBySolver()) {
511                                 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
512                                 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
513                             } else {
514                                 // no initial installation cause it has been set be e.g. user
515                                 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
516                                 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
517                             }
518                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
519                             _installs.insert (make_pair( provider, capKindisInstalledBy));
520                         }
521
522                         if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
523                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
524                             _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
525
526                             ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
527                             _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
528                         }
529                     }
530                 }
531             }
532         }
533     }
534 }
535
536
537 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
538 {
539     ItemCapKindList ret;
540     collectResolverInfo();
541
542     for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
543         ItemCapKind info = iter->second;
544         PoolItem iterItem = iter->first;
545         if (iterItem == item) {
546             ret.push_back(info);
547             iter++;
548         } else {
549             // exit
550             iter = _isInstalledBy.end();
551         }
552     }
553     return ret;
554 }
555
556 ItemCapKindList Resolver::installs( const PoolItem & item )
557 {
558     ItemCapKindList ret;
559     collectResolverInfo();
560
561     for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
562         ItemCapKind info = iter->second;
563         PoolItem iterItem = iter->first;
564         if (iterItem == item) {
565             ret.push_back(info);
566             iter++;
567         } else {
568             // exit
569             iter = _installs.end();
570         }
571     }
572     return ret;
573 }
574
575 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
576 {
577     ItemCapKindList ret;
578     collectResolverInfo();
579
580     for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
581         ItemCapKind info = iter->second;
582         PoolItem iterItem = iter->first;
583         if (iterItem == item) {
584             ret.push_back(info);
585             iter++;
586         } else {
587             // exit
588             iter = _satifiedByInstalled.end();
589         }
590     }
591     return ret;
592 }
593
594 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
595 {
596     ItemCapKindList ret;
597     collectResolverInfo();
598
599     for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
600         ItemCapKind info = iter->second;
601         PoolItem iterItem = iter->first;
602         if (iterItem == item) {
603             ret.push_back(info);
604             iter++;
605         } else {
606             // exit
607             iter = _installedSatisfied.end();
608         }
609     }
610     return ret;
611 }
612
613
614 ///////////////////////////////////////////////////////////////////
615     };// namespace detail
616     /////////////////////////////////////////////////////////////////////
617     /////////////////////////////////////////////////////////////////////
618   };// namespace solver
619   ///////////////////////////////////////////////////////////////////////
620   ///////////////////////////////////////////////////////////////////////
621 };// namespace zypp
622 /////////////////////////////////////////////////////////////////////////
623