a11e65f0400cab101d709d1dd223acc1858f1377
[platform/upstream/libzypp.git] / zypp / solver / detail / ResolverUpgrade.cc
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
2 /*---------------------------------------------------------------------\
3 |                          ____ _   __ __ ___                          |
4 |                         |__  / \ / / . \ . \                         |
5 |                           / / \ V /|  _/  _/                         |
6 |                          / /__ | | | | | |                           |
7 |                         /_____||_| |_| |_|                           |
8 |                                                                      |
9 \---------------------------------------------------------------------*/
10 /* ResolverUpgrade.cc
11  *
12  * Implements the distribution upgrade algorithm.
13  *
14  * Copyright (C) 2005 SUSE Linux Products GmbH
15  *
16  * This program is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU General Public License,
18  * version 2, as published by the Free Software Foundation.
19  *
20  * This program is distributed in the hope that it will be useful, but
21  * WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23  * General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with this program; if not, write to the Free Software
27  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
28  * 02111-1307, USA.
29  */
30
31 /*
32   stolen from PMPackageManager_update.cc
33   original author Michael Andres <ma@suse.de>
34   zypp port by Klaus Kaempf <kkaempf@suse.de>
35
36 /-*/
37
38 #include "zypp/Capabilities.h"
39 #include "zypp/base/Easy.h"
40 #include "zypp/base/LogTools.h"
41 #include "zypp/base/String.h"
42 #include "zypp/base/Gettext.h"
43 #include "zypp/base/Exception.h"
44 #include "zypp/VendorAttr.h"
45 #include "zypp/base/Algorithm.h"
46 #include "zypp/ResPool.h"
47 #include "zypp/ResStatus.h"
48 #include "zypp/ResFilters.h"
49 #include "zypp/Capability.h"
50 #include "zypp/VendorAttr.h"
51 #include "zypp/Package.h"
52 #include "zypp/ZYppFactory.h"
53 #include "zypp/solver/detail/Types.h"
54 #include "zypp/solver/detail/Helper.h"
55 #include "zypp/solver/detail/Resolver.h"
56 #include "zypp/solver/detail/Testcase.h"
57 #include "zypp/solver/detail/SATResolver.h"
58 #include "zypp/ResolverProblem.h"
59 #include "zypp/ProblemSolution.h"
60 #include "zypp/Target.h"
61
62 /////////////////////////////////////////////////////////////////////////
63 namespace zypp
64 { ///////////////////////////////////////////////////////////////////////
65   ///////////////////////////////////////////////////////////////////////
66   namespace solver
67   { /////////////////////////////////////////////////////////////////////
68     /////////////////////////////////////////////////////////////////////
69     namespace detail
70     { ///////////////////////////////////////////////////////////////////
71
72 using namespace std;
73 using namespace zypp;
74
75 /** Order on AvialableItemSet.
76  * \li best Arch
77  * \li best Edition
78  * \li ResObject::constPtr as fallback.
79 */
80 struct AVOrder : public std::binary_function<PoolItem,PoolItem,bool>
81 {
82     // NOTE: operator() provides LESS semantics to order the set.
83     // So LESS means 'prior in set'. We want 'better' archs and
84     // 'better' editions at the beginning of the set. So we return
85     // TRUE if (lhs > rhs)!
86     //
87     bool operator()( const PoolItem lhs, const PoolItem rhs ) const
88         {
89             int res = lhs->arch().compare( rhs->arch() );
90             if ( res )
91                 return res > 0;
92             res = lhs->edition().compare( rhs->edition() );
93             if ( res )
94                 return res > 0;
95
96             // no more criteria, still equal:
97             // use the ResObject::constPtr (the poiner value)
98             // (here it's arbitrary whether < or > )
99             return lhs.resolvable() < rhs.resolvable();
100         }
101 };
102
103 typedef std::set<PoolItem, AVOrder> PoolItemOrderSet;
104
105
106
107 // check if downgrade is allowed
108 // (Invariant on entry: installed.edition >= candidate.edition)
109 //
110 // candidate must have allowed vendor (e.g. 'SuSE', 'Novell', ...) and candidates buildtime must be
111 // newer.
112
113 static bool
114 downgrade_allowed( PoolItem installed, PoolItem candidate, bool silent_downgrades )
115 {
116     if (installed.status().isLocked()) {
117         MIL << "Installed " << installed << " is locked, not upgrading" << endl;
118         return false;
119     }
120
121     Resolvable::constPtr ires = installed.resolvable();
122     Package::constPtr ipkg = asKind<Package>(ires);
123     Resolvable::constPtr cres = candidate.resolvable();
124     Package::constPtr cpkg = asKind<Package>(cres);
125
126     if (ipkg)
127       DBG << "Installed vendor '" << ipkg->vendor() << "'" << endl;
128     if (cpkg)
129       DBG << "Candidate vendor '" << cpkg->vendor() << "'" << endl;
130
131     if (cpkg
132         && VendorAttr::instance().equivalent( ipkg->vendor(), cpkg->vendor() ) )
133     {
134         if ( silent_downgrades )
135             return true;
136         if ( ipkg->buildtime() <= cpkg->buildtime() ) {                 // installed has older or equal buildtime
137             MIL << "allowed downgrade " << installed << " to " << candidate << endl;
138             return true;                                                // see bug #152760
139         }
140     }
141     return false;
142 }
143
144
145 bool
146 Resolver::doesObsoleteItem (PoolItem candidate, PoolItem installed)
147 {
148     return _satResolver->doesObsoleteItem (candidate, installed);
149 }
150
151 //-----------------------------------------------------------------------------
152
153
154 //-----------------------------------------------------------------------------
155
156 // Selecting item for installation
157
158 class LookForSelected : public resfilter::PoolItemFilterFunctor
159 {
160   public:
161     bool found;
162     PoolItem candidate;
163
164     LookForSelected (PoolItem can)
165         : found (false),
166         candidate (can)
167     { }
168
169     bool operator()( PoolItem item )
170     {
171         if (item.status().isToBeInstalled()
172             && item->edition() == candidate->edition()
173             && item->arch() == candidate->arch()) {
174             MIL << item << " is already selected for installation --> ignoring" << endl;
175             found = true;
176             return false; // stop here
177         }
178         return true;
179     }
180 };
181
182 bool setForInstallation (const ResPool &pool, PoolItem item) {
183     LookForSelected info(item);
184
185     invokeOnEach( pool.byIdentBegin (item->kind(),item->name()),
186                   pool.byIdentEnd (item->kind(),item->name()),
187                   resfilter::ByUninstalled (),                  // ByUninstalled
188                   functor::functorRef<bool,PoolItem> (info) );
189     if (info.found) {
190         MIL << "   ---> " << item << " will be ignoring" << endl;
191         return true;
192     } else {
193         return item.status().setToBeInstalled( ResStatus::APPL_HIGH );
194     }
195 }
196
197 //-----------------------------------------------------------------------------
198
199 ///////////////////////////////////////////////////////////////////
200 //
201 //
202 //      METHOD NAME : Resolver::doUpgrade
203 //      METHOD TYPE : bool
204 //
205 //      DESCRIPTION : go through all installed (but not yet touched by user)
206 //              packages and look for update candidates
207 //
208 bool
209 Resolver::doUpgrade( UpgradeStatistics & opt_stats_r )
210 {
211   typedef map<PoolItem,PoolItem> CandidateMap;
212   typedef map<PoolItem,PoolItemOrderSet> TodoMap;
213
214   CandidateMap candidatemap;
215
216   TodoMap     addProvided;
217   TodoMap     addMultiProvided;
218
219   Target_Ptr target;
220   try {
221         target = getZYpp()->target();
222   }
223   catch( const Exception & excpt_r) {
224         ERR << "Huh, no target ?";
225         ZYPP_CAUGHT(excpt_r);
226         if (!_testing) return false;            // can't continue without target
227         MIL << "Running in test mode, continuing without target" << endl;
228   }
229   MIL << "target at " << target << endl;
230
231   MIL << "doUpgrade start... "
232     << "(silent_downgrades:" << (opt_stats_r.silent_downgrades?"yes":"no") << ")"
233     << endl;
234
235   // create a testcase for the updating system
236   PathInfo path ("/mnt/var/log"); // checking if update has been started from instsys
237
238   if ( !path.isExist() ) {
239       Testcase testcase("/var/log/updateTestcase");
240       testcase.createTestcase (*this, true, false); // create pool, do not solve 
241   } else {
242       Testcase testcase("/mnt/var/log/updateTestcase");
243       testcase.createTestcase (*this, true, false); // create pool, do not solve
244   }
245
246   _unmaintained_items.clear();
247   _problem_items.clear();
248   {
249     UpgradeOptions opts( opt_stats_r );
250     opt_stats_r = UpgradeStatistics();
251     (UpgradeOptions&)opt_stats_r = opts;
252   }
253
254   /* Find upgrade candidates for each package.  */
255
256   for ( ResPool::const_iterator it = _pool.begin(); it != _pool.end(); ++it ) {
257     PoolItem item = *it;
258     PoolItem candidate;
259     PoolItem installed;
260
261     if ( item.status().isToBeUninstalled() ) {
262       MIL << "doUpgrade available: SKIP to delete " << item << endl;
263       ++opt_stats_r.pre_todel;
264       continue;
265     }
266     if ( item.status().isLocked() ) {
267       MIL << "doUpgrade available: SKIP locked " << item << endl;
268       if ( item.status().staysInstalled() ) {
269         ++opt_stats_r.pre_nocand;
270       }
271       continue;
272     }
273
274     if ( item.status().staysInstalled() ) {     // installed item
275       installed = item;
276       CandidateMap::const_iterator cand_it = candidatemap.find( installed );
277       if (cand_it != candidatemap.end()) {
278         candidate = cand_it->second;                            // found candidate already
279       }
280       else {
281         candidate = Helper::findUpdateItem( _pool, installed ); // find 'best' upgrade candidate
282       }
283       if (!candidate) {
284         MIL << "doUpgrade available: SKIP no candidate for " << installed << endl;
285         ++opt_stats_r.pre_nocand;
286         continue;
287       }
288       if (candidate.status().isSeen()) {                        // seen already
289         candidate.status().setSeen(true);
290         continue;
291       }
292       candidate.status().setSeen(true);                         // mark as seen
293       candidatemap[installed] = candidate;
294     }
295     else {                                      // assume Uninstalled
296       if (item.status().isSeen()) {                             // seen already
297         item.status().setSeen(true);
298         continue;
299       }
300       candidate = item;
301       candidate.status().setSeen(true);                         // mark as seen
302       installed = Helper::findInstalledItem( _pool, candidate );
303       if (installed) {                                          // check if we already have an installed
304         if ( installed.status().isLocked() ) {
305           MIL << "doUpgrade available: SKIP candidate " << candidate << ", locked " << installed << endl;
306           continue;
307         }
308
309         if ( !VendorAttr::instance().equivalent(installed->vendor(), candidate->vendor()) )
310         {
311             MIL << "Discarding '" << candidate << "' from vendor '"
312                 << candidate->vendor() << "' different to installed '"
313                 << installed->vendor() << "' vendor." << endl;
314             continue;
315         }
316
317         CandidateMap::const_iterator cand_it = candidatemap.find( installed );
318         if (cand_it == candidatemap.end()                                               // not in map yet
319             || (cand_it->second->arch().compare( candidate->arch() ) < 0)               // or the new has better architecture
320             || ((cand_it->second->arch().compare( candidate->arch() ) == 0)             // or the new has the same architecture
321                 && (cand_it->second->edition().compare( candidate->edition() ) < 0))    //   and a better edition (-> 157501)
322             )
323         {
324             candidatemap[installed] = candidate;                                // put it in !
325         }
326       }
327     }
328
329     ++opt_stats_r.pre_avcand;
330   } // iterate over the complete pool
331
332   // reset all seen (for next run)
333   for ( ResPool::const_iterator it = _pool.begin(); it != _pool.end(); ++it ) {
334         it->status().setSeen( false );
335   }
336
337   MIL << "doUpgrade: " << opt_stats_r.pre_todel  << " packages tagged to delete" << endl;
338   MIL << "doUpgrade: " << opt_stats_r.pre_nocand << " packages without candidate (foreign, replaced or dropped)" << endl;
339   MIL << "doUpgrade: " << opt_stats_r.pre_avcand << " packages available for update" << endl;
340
341   ///////////////////////////////////////////////////////////////////
342   // Now iterate installed packages, not selected to delete, and
343   // figure out what might be an appropriate replacement. Current
344   // packages state is changed immediately. Additional packages are
345   // reported but set to install later.
346   ///////////////////////////////////////////////////////////////////
347   MIL << "doUpgrade pass 1..." << endl;
348
349   for ( ResPool::const_iterator it = _pool.begin(); it != _pool.end(); ++it ) {
350
351     PoolItem installed(*it);
352     ResStatus status (installed.status());
353
354     if ( ! status.staysInstalled() ) {
355       continue;
356     }
357     ++opt_stats_r.chk_installed_total;
358
359     if ( status.transacts() ) {                                 // we know its installed, if it transacts also
360       MIL << "SKIP to delete: " << installed.resolvable() << endl;      // it'll be deleted
361       ++opt_stats_r.chk_already_todel;
362       continue;
363     }
364
365     if ( installed.status().isLocked() ) {                      // skip locked
366       MIL << "SKIP taboo: " << installed << endl;
367       ++opt_stats_r.chk_is_taboo;
368       _problem_items.push_back( installed );                    // remember in problem list
369       continue;
370     }
371
372     if ( isKind<Patch>(installed.resolvable())
373          || isKind<Atom>(installed.resolvable())
374          || isKind<Script>(installed.resolvable())
375          || isKind<Message>(installed.resolvable())
376          || isKind<Pattern>(installed.resolvable()))
377     {
378         MIL << "Delete old: " << installed << endl;
379         installed.status().setToBeUninstalled( ResStatus::APPL_HIGH );
380         continue;       
381     }
382
383     CandidateMap::iterator cand_it = candidatemap.find( installed );
384
385     bool can_be_dropped = false;
386
387     MIL << "REPLACEMENT FOR " << installed << endl;
388     ///////////////////////////////////////////////////////////////////
389     // figure out replacement
390     ///////////////////////////////////////////////////////////////////
391     if ( cand_it != candidatemap.end() ) {
392
393       PoolItem candidate (cand_it->second);
394
395       if ( ! candidate.status().isToBeInstalled() ) {
396         int cmp = installed->edition().compare( candidate->edition() );
397         if ( cmp < 0 ) {   // new edition
398           setForInstallation (_pool,candidate);
399           MIL << " ==> INSTALL (new version): " << candidate << endl;
400           ++opt_stats_r.chk_to_update;
401         } else {                                                        // older or equal edition
402           // check whether to downgrade:
403
404           if (cmp == 0                                                  // equal
405               || !downgrade_allowed( installed, candidate,
406                                      opt_stats_r.silent_downgrades) )   //  or downgrade not allowed
407           {
408             MIL << " ==> (keep installed)" << candidate << endl;        // keep installed
409             ++opt_stats_r.chk_to_keep_installed;
410           } else {// older and downgrade allowed
411             setForInstallation (_pool, candidate);
412             MIL << " ==> INSTALL (SuSE version downgrade): " << candidate << endl;
413             ++opt_stats_r.chk_to_downgrade;
414           }
415         }
416       } else {
417         MIL << " ==> INSTALL (preselected): " << candidate << endl;
418         ++opt_stats_r.chk_already_toins;
419       }
420
421     }
422     else {              // no candidate
423
424       // replaced or dropped (anyway there's no candidate for this!)
425       // If unique provides exists check if obsoleted (replaced).
426       // Remember new package for 2nd pass.
427
428       Capability installedCap( installed->name(), Rel::EQ, installed->edition(), installed->kind());
429       
430       // find ALL providers
431       sat::WhatProvides possibleProviders(installedCap);
432
433       // find best available providers for installed name
434       typedef map<string, PoolItem> FindMap;
435       FindMap providersMap;             // the best providers which matched
436       bool otherVendorFound = false;
437       for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
438           PoolItem provider = ResPool::instance().find( *iter );
439           if ( !VendorAttr::instance().equivalent(provider->vendor(), installed->vendor()) )
440           {
441               MIL << "Discarding '" << provider << "' from vendor '"
442                   << provider->vendor() << "' different to uninstalled '"
443                   << installed->vendor() << "' vendor." << endl;
444               otherVendorFound = true;
445           } else if ( provider.status().isToBeUninstalled() ) {
446               MIL << "  IGNORE relation match (package is tagged to delete): " << provider << endl;
447           } else if ( provider.status().isInstalled() ) {
448               if (installed->name() == provider->name()) {
449                   MIL << "  IGNORE relation match (package is installed): " << provider << endl;                  
450               } else {
451                   MIL << "  Take installed package ONLY: " << provider << endl;
452                   providersMap.clear();
453                   break; // exit for
454               }
455           }       
456           else {
457               FindMap::iterator it = providersMap.find( provider->name() );
458
459               if (it != providersMap.end()) {                           // provider with same name found
460                   if (provider.status().isToBeInstalled()
461                       || it->second.status().isToBeInstalled()) {
462
463                       if (provider.status().isToBeInstalled()
464                           && it->second.status().isToBeInstalled()) {
465                           ERR << "only one should be set for installation: " << it->second << "; " << provider << endl;
466                       } else {
467                           if (provider.status().isToBeInstalled()) {
468                               it->second = provider; // take thatone which is already set for installation
469                           }
470                       }
471                   } else {
472                       // not the same --> find better provider
473                       int cmp = it->second->arch().compare( provider->arch() );
474                       if (cmp < 0) {                                            // new provider has better arch
475                           it->second = provider;
476                       }
477                       else if (cmp == 0) {                                      // new provider has equal arch
478                           if (it->second->edition().compare( provider->edition() ) < 0) {
479                               it->second = provider;                            // new provider has better edition
480                           }
481                       }
482                   }
483               }
484               else {
485                   providersMap[provider->name()] = provider;
486               }
487           }
488       }
489
490       _DEBUG("lookup " << providersMap.size() << " provides for installed " << installedCap);
491
492       // copy from map to set
493       PoolItemOrderSet providers;
494       for (FindMap::const_iterator mapit = providersMap.begin(); mapit != providersMap.end(); ++mapit) {
495         providers.insert( mapit->second );
496       }
497
498       switch ( providersMap.size() ) {
499       case 0:
500           if (otherVendorFound) {
501               MIL << " only resolvable with other vendor found ==> do nothing" << endl;
502           } else {
503               MIL << " ==> dropp if it does not fit to the system" << endl;
504               can_be_dropped = true;
505           }
506         break;
507       case 1:
508         addProvided[installed] = providers;
509         MIL << " ==> REPLACED by: " << (*providers.begin()) << endl;
510         // count stats later
511         // check obsoletes later
512         break;
513       default:
514         addMultiProvided[installed] = providers;
515         MIL << " ==> pass 2 (" << providers.size() << " times provided)" << endl;
516         // count stats later
517         // check obsoletes later
518         break;
519       }
520
521     }   // no candidate
522
523
524     ///////////////////////////////////////////////////////////////////
525     // now handle dropped package
526     ///////////////////////////////////////////////////////////////////
527
528     if ( can_be_dropped ) {
529       _unmaintained_items.insert( installed );
530     }
531
532   } // pass 1 end
533
534   ///////////////////////////////////////////////////////////////////
535   // Now check the remembered packages and check non unique provided.
536   // Maybe one of them was somehow selected. Otherwise we have to guess
537   // one.
538   ///////////////////////////////////////////////////////////////////
539   MIL << "doUpgrade pass 2..." << endl;
540
541   // look at the ones with a single provide first
542
543   for ( TodoMap::iterator it = addProvided.begin(); it != addProvided.end(); ++it ) {
544
545     PoolItemOrderSet & tset( it->second );              // these are the providers (well, just one)
546
547     for ( PoolItemOrderSet::iterator sit = tset.begin(); sit != tset.end(); ++sit ) {
548       PoolItem provider (*sit);
549
550       if (setForInstallation (_pool, provider)) {
551         ++opt_stats_r.chk_replaced;
552       }
553
554       // needs installed
555
556       if ( doesObsoleteItem (provider, it->first ) ) {
557         it->first.status().setToBeUninstalled( ResStatus::APPL_HIGH );
558       }
559     }
560
561   }
562
563   // look at the ones with multiple providers
564
565   for ( TodoMap::iterator it = addMultiProvided.begin(); it != addMultiProvided.end(); ++it ) {
566     MIL << "GET ONE OUT OF " << it->second.size() << " for " << it->first << endl;
567
568     PoolItem guess;
569     PoolItemOrderSet & gset( it->second );
570
571     for ( PoolItemOrderSet::iterator git = gset.begin(); git != gset.end(); ++git ) {
572         PoolItem item (*git);
573
574         if (git == gset.begin())                // default to first of set; the set is ordered, first is the best
575             guess = item;
576
577         if ( item.status().isToBeInstalled()) {
578             MIL << " ==> (pass 2: meanwhile set to install): " << item << endl;
579             if ( ! doesObsoleteItem (item, it->first ) ) {
580                 it->first.status().setToBeUninstalled( ResStatus::APPL_HIGH );
581             }
582             guess = PoolItem();
583             break;
584         } else {
585             // Be prepared to guess.
586             // Most common situation for guessing is something like:
587             //   qt-devel
588             //   qt-devel-experimental
589             //   qt-devel-japanese
590             // That's why currently the shortest package name wins.
591             if ( !guess || guess->name().size() > item->name().size() ) {
592                 guess = item;
593             }
594         }
595     }
596
597     if ( guess ) {
598         // Checking if the selected provider depends on language, if yes try to find out the
599         // correct language package
600         if (guess.satSolvable().supportsLocales()) { // is this a language package ?
601             // searching a package which provides one of the requested languages.
602             PoolItemOrderSet & gset( it->second );
603             MIL << "Item " << guess << " provides language support. Look for proper language items." <<  endl;
604             for ( PoolItemOrderSet::iterator git = gset.begin(); git != gset.end(); ++git ) {
605                 PoolItem item (*git);
606
607                 if ( item.status().isToBeInstalled()) {
608                     MIL << " ==> (pass 2: meanwhile set to install): " << item << ". Ignoring preselections." << endl;
609                     if ( ! doesObsoleteItem (item, it->first ) ) {
610                         it->first.status().setToBeUninstalled( ResStatus::APPL_HIGH );
611                     }
612                     guess = PoolItem();
613                     break;
614                 } else {
615                     if (item.satSolvable().supportsRequestedLocales()) {
616                         MIL << item << " provides a requested locale --> take thatone" << endl;
617                         guess = item;
618                         // do not break here cause there could be an item in the list which has been
619                         // already set for installation.
620                     }
621                 }
622             }
623         }
624     }
625
626     if ( guess ) {
627       setForInstallation (_pool, guess);
628       MIL << " ==> REPLACED by: (pass 2: guessed): " << guess << endl;
629       if ( ! doesObsoleteItem (guess, it->first ) ) {
630         it->first.status().setToBeUninstalled( ResStatus::APPL_HIGH );
631       }
632       ++opt_stats_r.chk_replaced_guessed;
633     }
634   }
635
636   ///////////////////////////////////////////////////////////////////
637   // done
638   ///////////////////////////////////////////////////////////////////
639   MIL << opt_stats_r << endl;
640
641   // Setting Resolver to upgrade mode
642   _upgradeMode = true;
643
644   // Unmaintained packages which does not fit to the updated system
645   // (broken dependencies) will be deleted.
646   // Make a solverrun and return it to the calling function
647   return checkUnmaintainedItems ();  
648   
649 }
650
651
652 ///////////////////////////////////////////////////////////////////
653     };// namespace detail
654     /////////////////////////////////////////////////////////////////////
655     /////////////////////////////////////////////////////////////////////
656   };// namespace solver
657   ///////////////////////////////////////////////////////////////////////
658   ///////////////////////////////////////////////////////////////////////
659 };// namespace zypp
660 /////////////////////////////////////////////////////////////////////////
661
662