- initial import of revision 374 from cnc
[apt.git] / apt-pkg / algorithms.cc
1 // -*- mode: cpp; mode: fold -*-
2 // Description                                                          /*{{{*/
3 // $Id: algorithms.cc,v 1.11 2003/01/29 18:43:48 niemeyer Exp $
4 /* ######################################################################
5
6    Algorithms - A set of misc algorithms
7
8    The pkgProblemResolver class has become insanely complex and
9    very sophisticated, it handles every test case I have thrown at it
10    to my satisfaction. Understanding exactly why all the steps the class
11    does are required is difficult and changing though not very risky
12    may result in other cases not working.
13    
14    ##################################################################### */
15                                                                         /*}}}*/
16 // Include Files                                                        /*{{{*/
17 #ifdef __GNUG__
18 #pragma implementation "apt-pkg/algorithms.h"
19 #endif 
20 #include <apt-pkg/algorithms.h>
21 #include <apt-pkg/error.h>
22 #include <apt-pkg/configuration.h>
23 #include <apt-pkg/sptr.h>
24
25 // CNC:2002-07-04
26 #include <apt-pkg/pkgsystem.h>
27 #include <apt-pkg/version.h>
28     
29 #include <apti18n.h>
30     
31 #include <iostream>
32                                                                         /*}}}*/
33 using namespace std;
34
35 pkgProblemResolver *pkgProblemResolver::This = 0;
36
37 // Simulate::Simulate - Constructor                                     /*{{{*/
38 // ---------------------------------------------------------------------
39 /* The legacy translations here of input Pkg iterators is obsolete, 
40    this is not necessary since the pkgCaches are fully shared now. */
41 pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache),
42                             iPolicy(Cache),
43                             Sim(&Cache->GetCache(),&iPolicy)
44 {
45    Sim.Init(0);
46    Flags = new unsigned char[Cache->Head().PackageCount];
47    memset(Flags,0,sizeof(*Flags)*Cache->Head().PackageCount);
48
49    // Fake a filename so as not to activate the media swapping
50    string Jnk = "SIMULATE";
51    for (unsigned int I = 0; I != Cache->Head().PackageCount; I++)
52       FileNames[I] = Jnk;
53 }
54                                                                         /*}}}*/
55 // Simulate::Describe - Describe a package                              /*{{{*/
56 // ---------------------------------------------------------------------
57 /* Parameter Now == true gives both current and available varsion,
58    Parameter Now == false gives only the available package version */
59 void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Now)
60 {
61    VerIterator Ver(Sim);
62  
63    out << Pkg.Name();
64
65    if (Now == true)
66    {
67       Ver = Pkg.CurrentVer();
68       if (Ver.end() == false)
69          out << " [" << Ver.VerStr() << ']';
70    }
71
72    Ver = Sim[Pkg].CandidateVerIter(Sim);
73    if (Ver.end() == true)
74       return;
75    
76    out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
77 }
78                                                                         /*}}}*/
79 // Simulate::Install - Simulate unpacking of a package                  /*{{{*/
80 // ---------------------------------------------------------------------
81 /* */
82 bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
83 {
84    // Adapt the iterator
85    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
86    Flags[Pkg->ID] = 1;
87    
88    cout << "Inst ";
89    Describe(Pkg,cout,true);
90    Sim.MarkInstall(Pkg,false);
91    
92    // Look for broken conflicts+predepends.
93    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
94    {
95       if (Sim[I].InstallVer == 0)
96          continue;
97       
98       for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
99       {
100          DepIterator Start;
101          DepIterator End;
102          D.GlobOr(Start,End);
103          if (Start->Type == pkgCache::Dep::Conflicts ||
104              Start->Type == pkgCache::Dep::Obsoletes ||
105              End->Type == pkgCache::Dep::PreDepends)
106          {
107             if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
108             {
109                cout << " [" << I.Name() << " on " << Start.TargetPkg().Name() << ']';
110                if (Start->Type == pkgCache::Dep::Conflicts)
111                   _error->Error("Fatal, conflicts violated %s",I.Name());
112             }       
113          }
114       }      
115    }
116
117    if (Sim.BrokenCount() != 0)
118       ShortBreaks();
119    else
120       cout << endl;
121    return true;
122 }
123                                                                         /*}}}*/
124 // Simulate::Configure - Simulate configuration of a Package            /*{{{*/
125 // ---------------------------------------------------------------------
126 /* This is not an acurate simulation of relatity, we should really not
127    install the package.. For some investigations it may be necessary 
128    however. */
129 bool pkgSimulate::Configure(PkgIterator iPkg)
130 {
131    // Adapt the iterator
132    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
133    
134    Flags[Pkg->ID] = 2;
135 //   Sim.MarkInstall(Pkg,false);
136    if (Sim[Pkg].InstBroken() == true)
137    {
138       cout << "Conf " << Pkg.Name() << " broken" << endl;
139
140       Sim.Update();
141       
142       // Print out each package and the failed dependencies
143       for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
144       {
145          // CNC:2003-02-17 - IsImportantDep() currently calls IsCritical(), so
146          //                  these two are currently doing the same thing. Check
147          //                  comments in IsImportantDep() definition.
148 #if 0
149          if (Sim.IsImportantDep(D) == false || 
150              (Sim[D] & pkgDepCache::DepInstall) != 0)
151             continue;
152 #else
153          if (D.IsCritical() == false || 
154              (Sim[D] & pkgDepCache::DepInstall) != 0)
155             continue;
156 #endif
157          
158          if (D->Type == pkgCache::Dep::Obsoletes)
159             cout << " Obsoletes:" << D.TargetPkg().Name();
160          else if (D->Type == pkgCache::Dep::Conflicts)
161             cout << " Conflicts:" << D.TargetPkg().Name();
162          else
163             cout << " Depends:" << D.TargetPkg().Name();
164       }     
165       cout << endl;
166
167       _error->Error("Conf Broken %s",Pkg.Name());
168    }   
169    else
170    {
171       cout << "Conf "; 
172       Describe(Pkg,cout,false);
173    }
174
175    if (Sim.BrokenCount() != 0)
176       ShortBreaks();
177    else
178       cout << endl;
179    
180    return true;
181 }
182                                                                         /*}}}*/
183 // Simulate::Remove - Simulate the removal of a package                 /*{{{*/
184 // ---------------------------------------------------------------------
185 /* */
186 bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
187 {
188    // Adapt the iterator
189    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
190
191    Flags[Pkg->ID] = 3;
192    Sim.MarkDelete(Pkg);
193    if (Purge == true)
194       cout << "Purg ";
195    else
196       cout << "Remv ";
197    Describe(Pkg,cout,false);
198
199    if (Sim.BrokenCount() != 0)
200       ShortBreaks();
201    else
202       cout << endl;
203
204    return true;
205 }
206                                                                         /*}}}*/
207 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
208 // ---------------------------------------------------------------------
209 /* */
210 void pkgSimulate::ShortBreaks()
211 {
212    cout << " [";
213    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
214    {
215       if (Sim[I].InstBroken() == true)
216       {
217          if (Flags[I->ID] == 0)
218             cout << I.Name() << ' ';
219 /*       else
220             cout << I.Name() << "! ";*/
221       }      
222    }
223    cout << ']' << endl;
224 }
225                                                                         /*}}}*/
226 // ApplyStatus - Adjust for non-ok packages                             /*{{{*/
227 // ---------------------------------------------------------------------
228 /* We attempt to change the state of the all packages that have failed
229    installation toward their real state. The ordering code will perform 
230    the necessary calculations to deal with the problems. */
231 bool pkgApplyStatus(pkgDepCache &Cache)
232 {
233    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
234    {
235       if (I->VersionList == 0)
236          continue;
237          
238       // Only choice for a ReInstReq package is to reinstall
239       if (I->InstState == pkgCache::State::ReInstReq ||
240           I->InstState == pkgCache::State::HoldReInstReq)
241       {
242          if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
243             Cache.MarkKeep(I);
244          else
245          {
246             // Is this right? Will dpkg choke on an upgrade?
247             if (Cache[I].CandidateVer != 0 &&
248                  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
249                Cache.MarkInstall(I);
250             else
251                return _error->Error(_("The package %s needs to be reinstalled, "
252                                     "but I can't find an archive for it."),I.Name());
253          }
254          
255          continue;
256       }
257       
258       switch (I->CurrentState)
259       {
260          /* This means installation failed somehow - it does not need to be
261             re-unpacked (probably) */
262          case pkgCache::State::UnPacked:
263          case pkgCache::State::HalfConfigured:
264          if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
265              I.State() != pkgCache::PkgIterator::NeedsUnpack)
266             Cache.MarkKeep(I);
267          else
268          {
269             if (Cache[I].CandidateVer != 0 &&
270                  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
271                Cache.MarkInstall(I);
272             else
273                Cache.MarkDelete(I);
274          }
275          break;
276
277          // This means removal failed
278          case pkgCache::State::HalfInstalled:
279          Cache.MarkDelete(I);
280          break;
281          
282          default:
283          if (I->InstState != pkgCache::State::Ok)
284             return _error->Error("The package %s is not ok and I "
285                                  "don't know how to fix it!",I.Name());
286       }
287    }
288    return true;
289 }
290                                                                         /*}}}*/
291 // FixBroken - Fix broken packages                                      /*{{{*/
292 // ---------------------------------------------------------------------
293 /* This autoinstalls every broken package and then runs the problem resolver
294    on the result. */
295 bool pkgFixBroken(pkgDepCache &Cache)
296 {
297    // Auto upgrade all broken packages
298    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
299       if (Cache[I].NowBroken() == true)
300          Cache.MarkInstall(I,true);
301    
302    /* Fix packages that are in a NeedArchive state but don't have a
303       downloadable install version */
304    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
305    {
306       if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
307           Cache[I].Delete() == true)
308          continue;
309       
310       if (Cache[I].InstVerIter(Cache).Downloadable() == false)
311          continue;
312
313       Cache.MarkInstall(I,true);      
314    }
315    
316    pkgProblemResolver Fix(&Cache);
317    
318    // CNC:2002-07-04
319    _system->ProcessCache(Cache,Fix);
320
321    // CNC:2002-08-08
322    if (_config->FindB("APT::Remove-Depends",false) == true)
323       Fix.RemoveDepends();
324    
325    return Fix.Resolve(true);
326 }
327                                                                         /*}}}*/
328 // DistUpgrade - Distribution upgrade                                   /*{{{*/
329 // ---------------------------------------------------------------------
330 /* This autoinstalls every package and then force installs every 
331    pre-existing package. This creates the initial set of conditions which 
332    most likely contain problems because too many things were installed.
333    
334    The problem resolver is used to resolve the problems.
335  */
336 bool pkgDistUpgrade(pkgDepCache &Cache)
337 {
338    /* Auto upgrade all installed packages, this provides the basis 
339       for the installation */
340    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
341    {
342       // CNC:2002-07-23
343       if (I->CurrentVer != 0)
344       {
345          // Was it obsoleted?
346          bool Obsoleted = false;
347          for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
348          {
349             if (D->Type == pkgCache::Dep::Obsoletes &&
350                 Cache[D.ParentPkg()].CandidateVer != 0 &&
351                 Cache[D.ParentPkg()].CandidateVerIter(Cache).Downloadable() == true &&
352                 (pkgCache::Version*)D.ParentVer() == Cache[D.ParentPkg()].CandidateVer &&
353                 Cache.VS().CheckDep(I.CurrentVer().VerStr(), D) == true &&
354                 Cache.GetPkgPriority(D.ParentPkg()) >= Cache.GetPkgPriority(I))
355             {
356                Cache.MarkInstall(D.ParentPkg(),true);
357                Obsoleted = true;
358                break;
359             }
360          }
361          if (Obsoleted == false)
362             Cache.MarkInstall(I,true);
363       }
364    }
365
366    /* Now, auto upgrade all essential packages - this ensures that
367       the essential packages are present and working */
368    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
369       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
370          Cache.MarkInstall(I,true);
371    
372    /* We do it again over all previously installed packages to force 
373       conflict resolution on them all. */
374    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
375    {
376       // CNC:2002-07-23
377       if (I->CurrentVer != 0)
378       {
379          // Was it obsoleted?
380          bool Obsoleted = false;
381          for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
382          {
383             if (D->Type == pkgCache::Dep::Obsoletes &&
384                 Cache[D.ParentPkg()].CandidateVer != 0 &&
385                 Cache[D.ParentPkg()].CandidateVerIter(Cache).Downloadable() == true &&
386                 (pkgCache::Version*)D.ParentVer() == Cache[D.ParentPkg()].CandidateVer &&
387                 Cache.VS().CheckDep(I.CurrentVer().VerStr(), D) == true &&
388                 Cache.GetPkgPriority(D.ParentPkg()) >= Cache.GetPkgPriority(I))
389             {
390                Cache.MarkInstall(D.ParentPkg(),false);
391                Obsoleted = true;
392                break;
393             }
394          }
395          if (Obsoleted == false)
396             Cache.MarkInstall(I,false);
397       }
398    }
399
400    pkgProblemResolver Fix(&Cache);
401
402    // CNC:2002-07-04
403    _system->ProcessCache(Cache,Fix);
404
405    // Hold back held packages.
406    if (_config->FindB("APT::Ignore-Hold",false) == false)
407    {
408       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
409       {
410          if (I->SelectedState == pkgCache::State::Hold)
411          {
412             Fix.Protect(I);
413             Cache.MarkKeep(I);
414          }
415       }
416    }
417
418    // CNC:2002-08-08
419    if (_config->FindB("APT::Remove-Depends",false) == true)
420       Fix.RemoveDepends();
421    
422    // CNC:2003-03-22
423    return Fix.Resolve(true);
424 }
425                                                                         /*}}}*/
426 // AllUpgrade - Upgrade as many packages as possible                    /*{{{*/
427 // ---------------------------------------------------------------------
428 /* Right now the system must be consistent before this can be called.
429    It also will not change packages marked for install, it only tries
430    to install packages not marked for install */
431 bool pkgAllUpgrade(pkgDepCache &Cache)
432 {
433    pkgProblemResolver Fix(&Cache);
434
435    if (Cache.BrokenCount() != 0)
436       return false;
437    
438    // Upgrade all installed packages
439    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
440    {
441       if (Cache[I].Install() == true)
442          Fix.Protect(I);
443           
444       if (_config->FindB("APT::Ignore-Hold",false) == false)
445          if (I->SelectedState == pkgCache::State::Hold)
446             continue;
447       
448       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
449          Cache.MarkInstall(I,false);
450    }
451
452    // CNC:2002-07-04
453    _system->ProcessCache(Cache,Fix);
454       
455    return Fix.ResolveByKeep();
456 }
457                                                                         /*}}}*/
458 // MinimizeUpgrade - Minimizes the set of packages to be upgraded       /*{{{*/
459 // ---------------------------------------------------------------------
460 /* This simply goes over the entire set of packages and tries to keep 
461    each package marked for upgrade. If a conflict is generated then 
462    the package is restored. */
463 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
464 {   
465    if (Cache.BrokenCount() != 0)
466       return false;
467    
468    // We loop for 10 tries to get the minimal set size.
469    bool Change = false;
470    unsigned int Count = 0;
471    do
472    {
473       Change = false;
474       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
475       {
476          // Not interesting
477          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
478             continue;
479
480          // Keep it and see if that is OK
481          Cache.MarkKeep(I);
482          if (Cache.BrokenCount() != 0)
483             Cache.MarkInstall(I,false);
484          else
485          {
486             // If keep didnt actually do anything then there was no change..
487             if (Cache[I].Upgrade() == false)
488                Change = true;
489          }       
490       }      
491       Count++;
492    }
493    while (Change == true && Count < 10);
494
495    if (Cache.BrokenCount() != 0)
496       return _error->Error("Internal Error in pkgMinimizeUpgrade");
497    
498    return true;
499 }
500                                                                         /*}}}*/
501
502 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
503 // ---------------------------------------------------------------------
504 /* */
505 pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : Cache(*pCache)
506 {
507    // Allocate memory
508    unsigned long Size = Cache.Head().PackageCount;
509    Scores = new signed short[Size];
510    Flags = new unsigned char[Size];
511    memset(Flags,0,sizeof(*Flags)*Size);
512    
513    // Set debug to true to see its decision logic
514    Debug = _config->FindB("Debug::pkgProblemResolver",false);
515 }
516                                                                         /*}}}*/
517 // ProblemResolver::~pkgProblemResolver - Destructor                    /*{{{*/
518 // ---------------------------------------------------------------------
519 /* */
520 pkgProblemResolver::~pkgProblemResolver()
521 {
522    delete [] Scores;
523    delete [] Flags;
524 }
525                                                                         /*}}}*/
526 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
527 // ---------------------------------------------------------------------
528 /* */
529 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
530 {
531    Package const **A = (Package const **)a;
532    Package const **B = (Package const **)b;
533    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
534       return -1;
535    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
536       return 1;
537    return 0;
538 }
539                                                                         /*}}}*/
540 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
541 // ---------------------------------------------------------------------
542 /* */
543 void pkgProblemResolver::MakeScores()
544 {
545    unsigned long Size = Cache.Head().PackageCount;
546    memset(Scores,0,sizeof(*Scores)*Size);
547
548    // Generate the base scores for a package based on its properties
549    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
550    {
551       if (Cache[I].InstallVer == 0)
552          continue;
553       
554       signed short &Score = Scores[I->ID];
555       
556       /* This is arbitary, it should be high enough to elevate an
557          essantial package above most other packages but low enough
558          to allow an obsolete essential packages to be removed by
559          a conflicts on a powerfull normal package (ie libc6) */
560       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
561          Score += 100;
562
563       // We transform the priority
564       // Important Required Standard Optional Extra
565       signed short PrioMap[] = {0,3,2,1,-1,-2};
566       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
567          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
568       
569       /* This helps to fix oddball problems with conflicting packages
570          on the same level. We enhance the score of installed packages */
571       if (I->CurrentVer != 0)
572          Score += 1;
573    }
574
575    // Now that we have the base scores we go and propogate dependencies
576    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
577    {
578       if (Cache[I].InstallVer == 0)
579          continue;
580       
581       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
582       {
583          if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
584             Scores[D.TargetPkg()->ID]++;
585       }
586    }   
587    
588    // Copy the scores to advoid additive looping
589    SPtrArray<signed short> OldScores = new signed short[Size];
590    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
591       
592    /* Now we cause 1 level of dependency inheritance, that is we add the 
593       score of the packages that depend on the target Package. This 
594       fortifies high scoring packages */
595    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
596    {
597       if (Cache[I].InstallVer == 0)
598          continue;
599       
600       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
601       {
602          // Only do it for the install version
603          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
604              (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends))
605             continue;    
606          
607          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
608       }      
609    }
610
611    /* Now we propogate along provides. This makes the packages that 
612       provide important packages extremely important */
613    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
614    {
615       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
616       {
617          // Only do it once per package
618          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
619             continue;
620          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
621       }
622    }
623
624    /* Protected things are pushed really high up. This number should put them
625       ahead of everything */
626    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
627    {
628       if ((Flags[I->ID] & Protected) != 0)
629          Scores[I->ID] += 10000;
630       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
631          Scores[I->ID] += 5000;
632    }   
633 }
634                                                                         /*}}}*/
635 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
636 // ---------------------------------------------------------------------
637 /* This goes through and tries to reinstall packages to make this package
638    installable */
639 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
640 {
641    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
642       return false;
643    if ((Flags[Pkg->ID] & Protected) == Protected)
644       return false;
645    
646    Flags[Pkg->ID] &= ~Upgradable;
647    
648    bool WasKept = Cache[Pkg].Keep();
649    Cache.MarkInstall(Pkg,false);
650
651    // This must be a virtual package or something like that.
652    if (Cache[Pkg].InstVerIter(Cache).end() == true)
653       return false;
654    
655    // Isolate the problem dependency
656    bool Fail = false;
657    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
658    {
659       // Compute a single dependency element (glob or)
660       pkgCache::DepIterator Start = D;
661       pkgCache::DepIterator End = D;
662       unsigned char State = 0;
663       for (bool LastOR = true; D.end() == false && LastOR == true;)
664       {
665          State |= Cache[D];
666          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
667          D++;
668          if (LastOR == true)
669             End = D;
670       }
671       
672       // We only worry about critical deps.
673       if (End.IsCritical() != true)
674          continue;
675             
676       // Iterate over all the members in the or group
677       while (1)
678       {
679          // Dep is ok now
680          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
681             break;
682          
683          // Do not change protected packages
684          PkgIterator P = Start.SmartTargetPkg();
685          if ((Flags[P->ID] & Protected) == Protected)
686          {
687             if (Debug == true)
688                clog << "    Reinst Failed because of protected " << P.Name() << endl;
689             Fail = true;
690          }      
691          else
692          {
693             // Upgrade the package if the candidate version will fix the problem.
694             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
695             {
696                if (DoUpgrade(P) == false)
697                {
698                   if (Debug == true)
699                      clog << "    Reinst Failed because of " << P.Name() << endl;
700                   Fail = true;
701                }
702                else
703                {
704                   Fail = false;
705                   break;
706                }            
707             }
708             else
709             {
710                /* We let the algorithm deal with conflicts on its next iteration,
711                 it is much smarter than us */
712                if (Start->Type == pkgCache::Dep::Conflicts || 
713                    Start->Type == pkgCache::Dep::Obsoletes)
714                    break;
715                
716                if (Debug == true)
717                   clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
718                Fail = true;
719             }     
720          }
721          
722          if (Start == End)
723             break;
724          Start++;
725       }
726       if (Fail == true)
727          break;
728    }
729    
730    // Undo our operations - it might be smart to undo everything this did..
731    if (Fail == true)
732    {
733       if (WasKept == true)
734          Cache.MarkKeep(Pkg);
735       else
736          Cache.MarkDelete(Pkg);
737       return false;
738    }     
739    
740    if (Debug == true)
741       clog << "  Re-Instated " << Pkg.Name() << endl;
742    return true;
743 }
744                                                                         /*}}}*/
745 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
746 // ---------------------------------------------------------------------
747 /* This routines works by calculating a score for each package. The score
748    is derived by considering the package's priority and all reverse 
749    dependents giving an integer that reflects the amount of breakage that
750    adjusting the package will inflict. 
751       
752    It goes from highest score to lowest and corrects all of the breaks by 
753    keeping or removing the dependant packages. If that fails then it removes
754    the package itself and goes on. The routine should be able to intelligently
755    go from any broken state to a fixed state. 
756  
757    The BrokenFix flag enables a mode where the algorithm tries to 
758    upgrade packages to advoid problems. */
759 bool pkgProblemResolver::Resolve(bool BrokenFix)
760 {
761    unsigned long Size = Cache.Head().PackageCount;
762
763    // Record which packages are marked for install
764    bool Again = false;
765    do
766    {
767       Again = false;
768       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
769       {
770          if (Cache[I].Install() == true)
771             Flags[I->ID] |= PreInstalled;
772          else
773          {
774             if (Cache[I].InstBroken() == true && BrokenFix == true)
775             {
776                Cache.MarkInstall(I,false);
777                if (Cache[I].Install() == true)
778                   Again = true;
779             }
780             
781             Flags[I->ID] &= ~PreInstalled;
782          }
783          Flags[I->ID] |= Upgradable;
784       }
785    }
786    while (Again == true);
787
788    if (Debug == true)
789       clog << "Starting" << endl;
790    
791    MakeScores();
792    
793    /* We have to order the packages so that the broken fixing pass 
794       operates from highest score to lowest. This prevents problems when
795       high score packages cause the removal of lower score packages that
796       would cause the removal of even lower score packages. */
797    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
798    pkgCache::Package **PEnd = PList;
799    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
800       *PEnd++ = I;
801    This = this;
802    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
803    
804 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
805       if (Scores[(*K)->ID] != 0)
806       {
807          pkgCache::PkgIterator Pkg(Cache,*K);
808          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
809             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' << 
810             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
811       } */
812
813    if (Debug == true)
814       clog << "Starting 2" << endl;
815    
816    /* Now consider all broken packages. For each broken package we either
817       remove the package or fix it's problem. We do this once, it should
818       not be possible for a loop to form (that is a < b < c and fixing b by
819       changing a breaks c) */
820    bool Change = true;
821    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
822    {
823       Change = false;
824       for (pkgCache::Package **K = PList; K != PEnd; K++)
825       {
826          pkgCache::PkgIterator I(Cache,*K);
827
828          /* We attempt to install this and see if any breaks result,
829             this takes care of some strange cases */
830          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
831              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
832              (Flags[I->ID] & PreInstalled) != 0 &&
833              (Flags[I->ID] & Protected) == 0 &&
834              (Flags[I->ID] & ReInstateTried) == 0)
835          {
836             if (Debug == true)
837                clog << " Try to Re-Instate " << I.Name() << endl;
838             unsigned long OldBreaks = Cache.BrokenCount();
839             pkgCache::Version *OldVer = Cache[I].InstallVer;
840             Flags[I->ID] &= ReInstateTried;
841             
842             Cache.MarkInstall(I,false);
843             if (Cache[I].InstBroken() == true || 
844                 OldBreaks < Cache.BrokenCount())
845             {
846                if (OldVer == 0)
847                   Cache.MarkDelete(I);
848                else
849                   Cache.MarkKeep(I);
850             }       
851             else
852                if (Debug == true)
853                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
854          }
855             
856          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
857             continue;
858          
859          if (Debug == true)
860             cout << "Investigating " << I.Name() << endl;
861          
862          // Isolate the problem dependency
863          PackageKill KillList[100];
864          PackageKill *LEnd = KillList;
865          bool InOr = false;
866          pkgCache::DepIterator Start;
867          pkgCache::DepIterator End;
868          PackageKill *OldEnd = LEnd;
869          
870          enum {OrRemove,OrKeep} OrOp = OrRemove;
871          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
872               D.end() == false || InOr == true;)
873          {
874             // Compute a single dependency element (glob or)
875             if (Start == End)
876             {
877                // Decide what to do
878                if (InOr == true)
879                {
880                   if (OldEnd == LEnd && OrOp == OrRemove)
881                   {
882                      if ((Flags[I->ID] & Protected) != Protected)
883                      {
884                         if (Debug == true)
885                            clog << "  Or group remove for " << I.Name() << endl;
886                         Cache.MarkDelete(I);
887                         Change = true;
888                      }               
889                   }               
890                   if (OldEnd == LEnd && OrOp == OrKeep)
891                   {
892                      if (Debug == true)
893                         clog << "  Or group keep for " << I.Name() << endl;
894                      Cache.MarkKeep(I);
895                      Change = true;
896                   }
897                }
898                
899                /* We do an extra loop (as above) to finalize the or group
900                   processing */
901                InOr = false;
902                OrOp = OrRemove;
903                D.GlobOr(Start,End);
904                if (Start.end() == true)
905                   break;
906
907                // We only worry about critical deps.
908                if (End.IsCritical() != true)
909                   continue;
910
911                InOr = Start != End;
912                OldEnd = LEnd;
913             }
914             else
915                Start++;
916
917             // Dep is ok
918             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
919             {
920                InOr = false;
921                continue;
922             }
923             
924             if (Debug == true)
925                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
926
927             /* Look across the version list. If there are no possible
928                targets then we keep the package and bail. This is necessary
929                if a package has a dep on another package that cant be found */
930             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
931             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
932                 Start->Type != pkgCache::Dep::Conflicts &&
933                 Start->Type != pkgCache::Dep::Obsoletes &&
934                 Cache[I].NowBroken() == false)
935             {          
936                if (InOr == true)
937                {
938                   /* No keep choice because the keep being OK could be the
939                      result of another element in the OR group! */
940                   continue;
941                }
942                
943                Change = true;
944                Cache.MarkKeep(I);                 
945                break;
946             }
947             
948             bool Done = false;
949             for (pkgCache::Version **V = VList; *V != 0; V++)
950             {
951                pkgCache::VerIterator Ver(Cache,*V);
952                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
953
954                if (Debug == true)
955                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
956                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
957
958                /* Try to fix the package under consideration rather than
959                   fiddle with the VList package */
960                if (Scores[I->ID] <= Scores[Pkg->ID] ||
961                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
962                     End->Type != pkgCache::Dep::Conflicts &&
963                     End->Type != pkgCache::Dep::Obsoletes))
964                {
965                   // Try a little harder to fix protected packages..
966                   if ((Flags[I->ID] & Protected) == Protected)
967                   {
968                      if (DoUpgrade(Pkg) == true)
969                      {
970                         if (Scores[Pkg->ID] > Scores[I->ID])
971                            Scores[Pkg->ID] = Scores[I->ID];
972                         break;
973                      }
974                      
975                      continue;
976                   }
977                   
978                   /* See if a keep will do, unless the package is protected,
979                      then installing it will be necessary */
980                   bool Installed = Cache[I].Install();
981                   Cache.MarkKeep(I);
982                   if (Cache[I].InstBroken() == false)
983                   {
984                      // Unwind operation will be keep now
985                      if (OrOp == OrRemove)
986                         OrOp = OrKeep;
987                      
988                      // Restore
989                      if (InOr == true && Installed == true)
990                         Cache.MarkInstall(I,false);
991                      
992                      if (Debug == true)
993                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
994                   }               
995                   else
996                   {                  
997                      if (BrokenFix == false || DoUpgrade(I) == false)
998                      {
999                         // Consider other options
1000                         if (InOr == false)
1001                         {
1002                            if (Debug == true)
1003                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
1004                            Cache.MarkDelete(I);
1005                            if (Counter > 1)
1006                            {
1007                               if (Scores[Pkg->ID] > Scores[I->ID])
1008                                  Scores[I->ID] = Scores[Pkg->ID];
1009                            }                       
1010                         }                       
1011                      }
1012                   }
1013                                   
1014                   Change = true;
1015                   Done = true;
1016                   break;
1017                }
1018                else
1019                {
1020                   /* This is a conflicts, and the version we are looking
1021                      at is not the currently selected version of the 
1022                      package, which means it is not necessary to 
1023                      remove/keep */
1024                   if (Cache[Pkg].InstallVer != Ver &&
1025                       (Start->Type == pkgCache::Dep::Conflicts ||
1026                        Start->Type == pkgCache::Dep::Obsoletes))
1027                      continue;
1028                   
1029                   // Skip adding to the kill list if it is protected
1030                   if ((Flags[Pkg->ID] & Protected) != 0)
1031                      continue;
1032                 
1033                   // CNC:2003-03-22
1034                   pkgDepCache::State State(&Cache);
1035                   if (BrokenFix == true && DoUpgrade(Pkg) == true)
1036                   {
1037                      if (Cache[I].InstBroken() == false &&
1038                          State.BrokenCount() >= Cache.BrokenCount())
1039                      {
1040                         if (Debug == true)
1041                            clog << "  Installing " << Pkg.Name() << endl;
1042                         Change = true;
1043                         break;
1044                      }
1045                      else
1046                         State.Restore();
1047                   }
1048
1049                   if (Debug == true)
1050                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
1051                   
1052                   // CNC:2002-07-09
1053                   if (*(V+1) != 0) //XXX Look for other solutions?
1054                       continue;
1055
1056                   LEnd->Pkg = Pkg;
1057                   LEnd->Dep = End;
1058                   LEnd++;
1059                   
1060                   if (Start->Type != pkgCache::Dep::Conflicts &&
1061                       Start->Type != pkgCache::Dep::Obsoletes)
1062                      break;
1063                }
1064             }
1065
1066             // Hm, nothing can possibly satisify this dep. Nuke it.
1067             if (VList[0] == 0 && 
1068                 Start->Type != pkgCache::Dep::Conflicts &&
1069                 Start->Type != pkgCache::Dep::Obsoletes &&
1070                 (Flags[I->ID] & Protected) != Protected)
1071             {
1072                bool Installed = Cache[I].Install();
1073                Cache.MarkKeep(I);
1074                if (Cache[I].InstBroken() == false)
1075                {
1076                   // Unwind operation will be keep now
1077                   if (OrOp == OrRemove)
1078                      OrOp = OrKeep;
1079                   
1080                   // Restore
1081                   if (InOr == true && Installed == true)
1082                      Cache.MarkInstall(I,false);
1083                   
1084                   if (Debug == true)
1085                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1086                }               
1087                else
1088                {
1089                   if (Debug == true)
1090                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1091                   if (InOr == false)
1092                      Cache.MarkDelete(I);
1093                }
1094
1095                Change = true;
1096                Done = true;
1097             }
1098             
1099             // Try some more
1100             if (InOr == true)
1101                continue;
1102             
1103             if (Done == true)
1104                break;
1105          }
1106          
1107          // Apply the kill list now
1108          if (Cache[I].InstallVer != 0)
1109          {
1110             for (PackageKill *J = KillList; J != LEnd; J++)
1111             {
1112                Change = true;
1113                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1114                {
1115                   if (J->Dep->Type == pkgCache::Dep::Conflicts || 
1116                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1117                   {
1118                      if (Debug == true)
1119                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
1120                      Cache.MarkDelete(J->Pkg);
1121                   }
1122                }
1123                else
1124                {
1125                   if (Debug == true)
1126                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1127                   Cache.MarkKeep(J->Pkg);
1128                }
1129
1130                if (Counter > 1)
1131                {
1132                   if (Scores[I->ID] > Scores[J->Pkg->ID])                 
1133                      Scores[J->Pkg->ID] = Scores[I->ID];
1134                }               
1135             }      
1136          }
1137       }      
1138    }
1139
1140    if (Debug == true)
1141       clog << "Done" << endl;
1142       
1143    if (Cache.BrokenCount() != 0)
1144    {
1145       // See if this is the result of a hold
1146       pkgCache::PkgIterator I = Cache.PkgBegin();
1147       for (;I.end() != true; I++)
1148       {
1149          if (Cache[I].InstBroken() == false)
1150             continue;
1151          if ((Flags[I->ID] & Protected) != Protected)
1152             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1153       }
1154       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1155    }
1156    
1157    return true;
1158 }
1159                                                                         /*}}}*/
1160 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1161 // ---------------------------------------------------------------------
1162 /* This is the work horse of the soft upgrade routine. It is very gental 
1163    in that it does not install or remove any packages. It is assumed that the
1164    system was non-broken previously. */
1165 bool pkgProblemResolver::ResolveByKeep()
1166 {
1167    unsigned long Size = Cache.Head().PackageCount;
1168
1169    if (Debug == true)      
1170       clog << "Entering ResolveByKeep" << endl;
1171    
1172    MakeScores();
1173    
1174    /* We have to order the packages so that the broken fixing pass 
1175       operates from highest score to lowest. This prevents problems when
1176       high score packages cause the removal of lower score packages that
1177       would cause the removal of even lower score packages. */
1178    pkgCache::Package **PList = new pkgCache::Package *[Size];
1179    pkgCache::Package **PEnd = PList;
1180    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1181       *PEnd++ = I;
1182    This = this;
1183    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1184    
1185    // Consider each broken package 
1186    pkgCache::Package **LastStop = 0;
1187    for (pkgCache::Package **K = PList; K != PEnd; K++)
1188    {
1189       pkgCache::PkgIterator I(Cache,*K);
1190
1191       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1192          continue;
1193
1194       /* Keep the package. If this works then great, otherwise we have
1195          to be significantly more agressive and manipulate its dependencies */
1196       if ((Flags[I->ID] & Protected) == 0)
1197       {
1198          if (Debug == true)
1199             clog << "Keeping package " << I.Name() << endl;
1200          Cache.MarkKeep(I);
1201          if (Cache[I].InstBroken() == false)
1202          {
1203             K = PList - 1;
1204             continue;
1205          }
1206       }
1207       
1208       // Isolate the problem dependencies
1209       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1210       {
1211          DepIterator Start;
1212          DepIterator End;
1213          D.GlobOr(Start,End);
1214
1215          // We only worry about critical deps.
1216          if (End.IsCritical() != true)
1217             continue;
1218          
1219          // Dep is ok
1220          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1221             continue;
1222
1223          /* Hm, the group is broken.. I suppose the best thing to do is to
1224             is to try every combination of keep/not-keep for the set, but thats
1225             slow, and this never happens, just be conservative and assume the
1226             list of ors is in preference and keep till it starts to work. */
1227          while (true)
1228          {
1229             if (Debug == true)
1230                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
1231             
1232             // Look at all the possible provides on this package
1233             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1234             for (pkgCache::Version **V = VList; *V != 0; V++)
1235             {
1236                pkgCache::VerIterator Ver(Cache,*V);
1237                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1238                
1239                // It is not keepable
1240                if (Cache[Pkg].InstallVer == 0 ||
1241                    Pkg->CurrentVer == 0)
1242                   continue;
1243                
1244                // CNC:2002-08-05
1245                if ((Flags[Pkg->ID] & Protected) == 0)
1246                {
1247                   if (Debug == true)
1248                      clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1249                   Cache.MarkKeep(Pkg);
1250                }
1251                
1252                if (Cache[I].InstBroken() == false)
1253                   break;
1254             }
1255             
1256             if (Cache[I].InstBroken() == false)
1257                break;
1258
1259             if (Start == End)
1260                break;
1261             Start++;
1262          }
1263               
1264          if (Cache[I].InstBroken() == false)
1265             break;
1266       }
1267
1268       if (Cache[I].InstBroken() == true)
1269          continue;
1270       
1271       // Restart again.
1272       if (K == LastStop)
1273          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1274       LastStop = K;
1275       K = PList - 1;
1276    }   
1277
1278    return true;
1279 }
1280                                                                         /*}}}*/
1281 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1282 // ---------------------------------------------------------------------
1283 /* This is used to make sure protected packages are installed */
1284 void pkgProblemResolver::InstallProtect()
1285 {
1286    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1287    {
1288       if ((Flags[I->ID] & Protected) == Protected)
1289       {
1290          if ((Flags[I->ID] & ToRemove) == ToRemove)
1291             Cache.MarkDelete(I);
1292          else
1293             Cache.MarkInstall(I,false);
1294       }
1295    }   
1296 }
1297                                                                         /*}}}*/
1298 // CNC:2002-08-01
1299 // ProblemSolver::RemoveDepends - Remove dependencies selectively       /*{{{*/
1300 // ---------------------------------------------------------------------
1301 // This will remove every dependency which is required only by packages
1302 // already being removed. This will allow one to reverse the effect a
1303 // task package, for example.
1304 bool pkgProblemResolver::RemoveDepends()
1305
1306    bool Debug = _config->FindB("Debug::pkgRemoveDepends",false);
1307    bool MoreSteps = true;
1308    while (MoreSteps == true)
1309    {
1310       MoreSteps = false;
1311       for (pkgCache::PkgIterator Pkg = Cache.PkgBegin();
1312            Pkg.end() == false; Pkg++)
1313       {
1314          if (Cache[Pkg].Delete() == false)
1315             continue;
1316          for (pkgCache::DepIterator D = Pkg.CurrentVer().DependsList();
1317               D.end() == false; D++)
1318          {
1319             if (D->Type != pkgCache::Dep::Depends &&
1320                 D->Type != pkgCache::Dep::PreDepends)
1321                continue;
1322             
1323             pkgCache::PkgIterator DPkg = D.TargetPkg();
1324             if (DPkg->CurrentVer == 0 || Cache[DPkg].Delete() == true)
1325                continue;
1326             if ((Flags[DPkg->ID] & Protected) == Protected)
1327                continue;
1328             
1329             bool Remove = true;
1330
1331             // Check if another package not being removed or being
1332             // installed requires this dependency.
1333             for (pkgCache::DepIterator R = DPkg.RevDependsList();
1334                  R.end() == false; R++)
1335             {
1336                pkgCache::PkgIterator RPkg = R.ParentPkg();
1337
1338                if (R->Type != pkgCache::Dep::Depends &&
1339                    R->Type != pkgCache::Dep::PreDepends)
1340                   continue;
1341
1342                if ((Cache[RPkg].Install() &&
1343                     (pkgCache::Version*)R.ParentVer() == Cache[RPkg].InstallVer &&
1344                     Cache.VS().CheckDep(DPkg.CurrentVer().VerStr(), R) == true) ||
1345                    (RPkg->CurrentVer != 0 &&
1346                     Cache[RPkg].Install() == false &&
1347                     Cache[RPkg].Delete() == false &&
1348                     Cache.VS().CheckDep(DPkg.CurrentVer().VerStr(), R) == true))
1349                {
1350                   Remove = false;
1351                   break;
1352                }
1353             }
1354
1355             if (Remove == false)
1356                continue;
1357
1358             // Also check every virtual package provided by this
1359             // dependency is required by packages not being removed,
1360             // or being installed.
1361             for (pkgCache::PrvIterator P = DPkg.CurrentVer().ProvidesList();
1362                  P.end() == false; P++)
1363             {
1364                pkgCache::PkgIterator PPkg = P.ParentPkg();
1365                for (pkgCache::DepIterator R = PPkg.RevDependsList();
1366                     R.end() == false; R++)
1367                {
1368                   pkgCache::PkgIterator RPkg = R.ParentPkg();
1369                
1370                   if (R->Type != pkgCache::Dep::Depends &&
1371                       R->Type != pkgCache::Dep::PreDepends)
1372                      continue;
1373
1374                   if ((Cache[RPkg].Install() &&
1375                        (pkgCache::Version*)R.ParentVer() == Cache[RPkg].InstallVer &&
1376                        Cache.VS().CheckDep(P.ProvideVersion(), R) == true) ||
1377                       (RPkg->CurrentVer != 0 &&
1378                        Cache[RPkg].Install() == false &&
1379                        Cache[RPkg].Delete() == false &&
1380                        Cache.VS().CheckDep(P.ProvideVersion(), R) == true))
1381                   {
1382                      Remove = false;
1383                      break;
1384                   }
1385                }
1386             }
1387
1388             if (Remove == false)
1389                continue;
1390
1391             if (Debug == true)
1392                clog << "Marking " << DPkg.Name() << " as a removable dependency of " << Pkg.Name() << endl;
1393
1394             Cache.MarkDelete(DPkg);
1395
1396             // Do at least one more step, to ensure that packages which
1397             // were being hold because of this one also get removed.
1398             MoreSteps = true;
1399          }
1400       }
1401    }
1402    return true;
1403 }
1404                                                                         /*}}}*/
1405
1406 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1407 // ---------------------------------------------------------------------
1408 /* This is ment to be used in conjunction with AllTargets to get a list 
1409    of versions ordered by preference. */
1410 static pkgCache *PrioCache;
1411 static int PrioComp(const void *A,const void *B)
1412 {
1413    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1414    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1415    
1416    // CNC:2002-11-27
1417    if ((R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1418        (L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1419    return 1;
1420    if ((R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1421        (L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1422    return -1;
1423    
1424    if (L->Priority != R->Priority)
1425       return L->Priority - R->Priority;
1426    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1427 }
1428 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1429 {
1430    unsigned long Count = 0;
1431    PrioCache = &Cache;
1432    for (pkgCache::Version **I = List; *I != 0; I++)
1433       Count++;
1434    qsort(List,Count,sizeof(*List),PrioComp);
1435 }
1436                                                                         /*}}}*/
1437 // vim:sts=3:sw=3