Upgraded to eg++ 1.1 and libstdc++2.9
[ntk/apt.git] / apt-pkg / algorithms.cc
1 // -*- mode: cpp; mode: fold -*-
2 // Description /*{{{*/
3 // $Id: algorithms.cc,v 1.7 1998/10/20 04:33:13 jgg 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 <iostream.h>
24 /*}}}*/
25
26 pkgProblemResolver *pkgProblemResolver::This = 0;
27
28 // Simulate::Simulate - Constructor /*{{{*/
29 // ---------------------------------------------------------------------
30 /* */
31 pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache),
32 Sim(Cache)
33 {
34 Flags = new unsigned char[Cache.HeaderP->PackageCount];
35 memset(Flags,0,sizeof(*Flags)*Cache.HeaderP->PackageCount);
36 }
37 /*}}}*/
38 // Simulate::Install - Simulate unpacking of a package /*{{{*/
39 // ---------------------------------------------------------------------
40 /* */
41 bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
42 {
43 // Adapt the iterator
44 PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
45 Flags[Pkg->ID] = 1;
46
47 clog << "Inst " << Pkg.Name();
48 Sim.MarkInstall(Pkg,false);
49
50 // Look for broken conflicts+predepends.
51 for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
52 {
53 if (Sim[I].InstallVer == 0)
54 continue;
55
56 for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false; D++)
57 if (D->Type == pkgCache::Dep::Conflicts || D->Type == pkgCache::Dep::PreDepends)
58 {
59 if ((Sim[D] & pkgDepCache::DepInstall) == 0)
60 {
61 clog << " [" << I.Name() << " on " << D.TargetPkg().Name() << ']';
62 if (D->Type == pkgCache::Dep::Conflicts)
63 _error->Error("Fatal, conflicts violated %s",I.Name());
64 }
65 }
66 }
67
68 if (Sim.BrokenCount() != 0)
69 ShortBreaks();
70 else
71 clog << endl;
72 return true;
73 }
74 /*}}}*/
75 // Simulate::Configure - Simulate configuration of a Package /*{{{*/
76 // ---------------------------------------------------------------------
77 /* This is not an acurate simulation of relatity, we should really not
78 install the package.. For some investigations it may be necessary
79 however. */
80 bool pkgSimulate::Configure(PkgIterator iPkg)
81 {
82 // Adapt the iterator
83 PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
84
85 Flags[Pkg->ID] = 2;
86 // Sim.MarkInstall(Pkg,false);
87 if (Sim[Pkg].InstBroken() == true)
88 {
89 clog << "Conf " << Pkg.Name() << " broken" << endl;
90
91 Sim.Update();
92
93 // Print out each package and the failed dependencies
94 for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
95 {
96 if (Sim.IsImportantDep(D) == false ||
97 (Sim[D] & pkgDepCache::DepInstall) != 0)
98 continue;
99
100 if (D->Type == pkgCache::Dep::Conflicts)
101 clog << " Conflicts:" << D.TargetPkg().Name();
102 else
103 clog << " Depends:" << D.TargetPkg().Name();
104 }
105 clog << endl;
106
107 _error->Error("Conf Broken %s",Pkg.Name());
108 }
109 else
110 clog << "Conf " << Pkg.Name();
111
112 if (Sim.BrokenCount() != 0)
113 ShortBreaks();
114 else
115 clog << endl;
116
117 return true;
118 }
119 /*}}}*/
120 // Simulate::Remove - Simulate the removal of a package /*{{{*/
121 // ---------------------------------------------------------------------
122 /* */
123 bool pkgSimulate::Remove(PkgIterator iPkg)
124 {
125 // Adapt the iterator
126 PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
127
128 Flags[Pkg->ID] = 3;
129 Sim.MarkDelete(Pkg);
130 clog << "Remv " << Pkg.Name();
131
132 if (Sim.BrokenCount() != 0)
133 ShortBreaks();
134 else
135 clog << endl;
136
137 return true;
138 }
139 /*}}}*/
140 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
141 // ---------------------------------------------------------------------
142 /* */
143 void pkgSimulate::ShortBreaks()
144 {
145 clog << " [";
146 for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
147 {
148 if (Sim[I].InstBroken() == true)
149 {
150 if (Flags[I->ID] == 0)
151 clog << I.Name() << ' ';
152 /* else
153 clog << I.Name() << "! ";*/
154 }
155 }
156 clog << ']' << endl;
157 }
158 /*}}}*/
159 // ApplyStatus - Adjust for non-ok packages /*{{{*/
160 // ---------------------------------------------------------------------
161 /* We attempt to change the state of the all packages that have failed
162 installation toward their real state. The ordering code will perform
163 the necessary calculations to deal with the problems. */
164 bool pkgApplyStatus(pkgDepCache &Cache)
165 {
166 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
167 {
168 switch (I->CurrentState)
169 {
170 // This means installation failed somehow
171 case pkgCache::State::UnPacked:
172 case pkgCache::State::HalfConfigured:
173 Cache.MarkKeep(I);
174 break;
175
176 // This means removal failed
177 case pkgCache::State::HalfInstalled:
178 Cache.MarkDelete(I);
179 break;
180
181 default:
182 if (I->InstState != pkgCache::State::Ok)
183 return _error->Error("The package %s is not ok and I "
184 "don't know how to fix it!",I.Name());
185 }
186 }
187 return true;
188 }
189 /*}}}*/
190 // FixBroken - Fix broken packages /*{{{*/
191 // ---------------------------------------------------------------------
192 /* This autoinstalls every broken package and then runs the problem resolver
193 on the result. */
194 bool pkgFixBroken(pkgDepCache &Cache)
195 {
196 // Auto upgrade all broken packages
197 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
198 if (Cache[I].NowBroken() == true)
199 Cache.MarkInstall(I,true);
200
201 /* Fix packages that are in a NeedArchive state but don't have a
202 downloadable install version */
203 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
204 {
205 if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
206 Cache[I].Delete() == true)
207 continue;
208
209 if (Cache[I].InstVerIter(Cache).Downloadable() == false)
210 continue;
211
212 Cache.MarkInstall(I,true);
213 }
214
215 pkgProblemResolver Fix(Cache);
216 return Fix.Resolve(true);
217 }
218 /*}}}*/
219 // DistUpgrade - Distribution upgrade /*{{{*/
220 // ---------------------------------------------------------------------
221 /* This autoinstalls every package and then force installs every
222 pre-existing package. This creates the initial set of conditions which
223 most likely contain problems because too many things were installed.
224
225 The problem resolver is used to resolve the problems.
226 */
227 bool pkgDistUpgrade(pkgDepCache &Cache)
228 {
229 /* Auto upgrade all installed packages, this provides the basis
230 for the installation */
231 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
232 if (I->CurrentVer != 0)
233 Cache.MarkInstall(I,true);
234
235 /* Now, auto upgrade all essential packages - this ensures that
236 the essential packages are present and working */
237 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
238 if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
239 Cache.MarkInstall(I,true);
240
241 /* We do it again over all previously installed packages to force
242 conflict resolution on them all. */
243 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
244 if (I->CurrentVer != 0)
245 Cache.MarkInstall(I,false);
246
247 pkgProblemResolver Fix(Cache);
248
249 // Hold back held packages.
250 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
251 {
252 if (I->SelectedState == pkgCache::State::Hold)
253 {
254 Fix.Protect(I);
255 Cache.MarkKeep(I);
256 }
257 }
258
259 return Fix.Resolve();
260 }
261 /*}}}*/
262 // AllUpgrade - Upgrade as many packages as possible /*{{{*/
263 // ---------------------------------------------------------------------
264 /* Right now the system must be consistent before this can be called.
265 It also will not change packages marked for install, it only tries
266 to install packages not marked for install */
267 bool pkgAllUpgrade(pkgDepCache &Cache)
268 {
269 pkgProblemResolver Fix(Cache);
270
271 if (Cache.BrokenCount() != 0)
272 return false;
273
274 // Upgrade all installed packages
275 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
276 {
277 if (Cache[I].Install() == true)
278 Fix.Protect(I);
279
280 if (I->SelectedState == pkgCache::State::Hold)
281 continue;
282
283 if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
284 Cache.MarkInstall(I,false);
285 }
286
287 return Fix.ResolveByKeep();
288 }
289 /*}}}*/
290 // MinimizeUpgrade - Minimizes the set of packages to be upgraded /*{{{*/
291 // ---------------------------------------------------------------------
292 /* This simply goes over the entire set of packages and tries to keep
293 each package marked for upgrade. If a conflict is generated then
294 the package is restored. */
295 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
296 {
297 if (Cache.BrokenCount() != 0)
298 return false;
299
300 // We loop indefinately to get the minimal set size.
301 bool Change = false;
302 do
303 {
304 Change = false;
305 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
306 {
307 // Not interesting
308 if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
309 continue;
310
311 // Keep it and see if that is OK
312 Cache.MarkKeep(I);
313 if (Cache.BrokenCount() != 0)
314 Cache.MarkInstall(I,false);
315 else
316 Change = true;
317 }
318 }
319 while (Change == true);
320
321 if (Cache.BrokenCount() != 0)
322 return _error->Error("Internal Error in pkgMinimizeUpgrade");
323
324 return true;
325 }
326 /*}}}*/
327
328 // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
329 // ---------------------------------------------------------------------
330 /* */
331 pkgProblemResolver::pkgProblemResolver(pkgDepCache &Cache) : Cache(Cache)
332 {
333 // Allocate memory
334 unsigned long Size = Cache.HeaderP->PackageCount;
335 Scores = new signed short[Size];
336 Flags = new unsigned char[Size];
337 memset(Flags,0,sizeof(*Flags)*Size);
338
339 // Set debug to true to see its decision logic
340 Debug = _config->FindB("Debug::pkgProblemResolver",false);
341 }
342 /*}}}*/
343 // ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
344 // ---------------------------------------------------------------------
345 /* */
346 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
347 {
348 Package const **A = (Package const **)a;
349 Package const **B = (Package const **)b;
350 if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
351 return -1;
352 if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
353 return 1;
354 return 0;
355 }
356 /*}}}*/
357 // ProblemResolver::MakeScores - Make the score table /*{{{*/
358 // ---------------------------------------------------------------------
359 /* */
360 void pkgProblemResolver::MakeScores()
361 {
362 unsigned long Size = Cache.HeaderP->PackageCount;
363 memset(Scores,0,sizeof(*Scores)*Size);
364
365 // Generate the base scores for a package based on its properties
366 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
367 {
368 if (Cache[I].InstallVer == 0)
369 continue;
370
371 signed short &Score = Scores[I->ID];
372
373 /* This is arbitary, it should be high enough to elevate an
374 essantial package above most other packages but low enough
375 to allow an obsolete essential packages to be removed by
376 a conflicts on a powerfull normal package (ie libc6) */
377 if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
378 Score += 100;
379
380 // We transform the priority
381 // Important Required Standard Optional Extra
382 signed short PrioMap[] = {0,3,2,1,-1,-2};
383 if (Cache[I].InstVerIter(Cache)->Priority <= 5)
384 Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
385
386 /* This helps to fix oddball problems with conflicting packages
387 on the same level. We enhance the score of installed packages */
388 if (I->CurrentVer != 0)
389 Score += 1;
390 }
391
392 // Now that we have the base scores we go and propogate dependencies
393 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
394 {
395 if (Cache[I].InstallVer == 0)
396 continue;
397
398 for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
399 {
400 if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
401 Scores[D.TargetPkg()->ID]++;
402 }
403 }
404
405 // Copy the scores to advoid additive looping
406 signed short *OldScores = new signed short[Size];
407 memcpy(OldScores,Scores,sizeof(*Scores)*Size);
408
409 /* Now we cause 1 level of dependency inheritance, that is we add the
410 score of the packages that depend on the target Package. This
411 fortifies high scoring packages */
412 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
413 {
414 if (Cache[I].InstallVer == 0)
415 continue;
416
417 for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
418 {
419 // Only do it for the install version
420 if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
421 (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends))
422 continue;
423
424 Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
425 }
426 }
427
428 /* Now we propogate along provides. This makes the packages that
429 provide important packages extremely important */
430 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
431 {
432 for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
433 {
434 // Only do it once per package
435 if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
436 continue;
437 Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
438 }
439 }
440
441 /* Protected things are pushed really high up. This number should put them
442 ahead of everything */
443 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
444 if ((Flags[I->ID] & Protected) != 0)
445 Scores[I->ID] += 10000;
446
447 delete [] OldScores;
448 }
449 /*}}}*/
450 // ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
451 // ---------------------------------------------------------------------
452 /* This goes through and tries to reinstall packages to make this package
453 installable */
454 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
455 {
456 if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
457 return false;
458
459 Flags[Pkg->ID] &= ~Upgradable;
460
461 bool WasKept = Cache[Pkg].Keep();
462 Cache.MarkInstall(Pkg,false);
463
464 // This must be a virtual package or something like that.
465 if (Cache[Pkg].InstVerIter(Cache).end() == true)
466 return false;
467
468 // Isolate the problem dependency
469 bool Fail = false;
470 for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
471 {
472 // Compute a single dependency element (glob or)
473 pkgCache::DepIterator Start = D;
474 pkgCache::DepIterator End = D;
475 unsigned char State = 0;
476 for (bool LastOR = true; D.end() == false && LastOR == true; D++)
477 {
478 State |= Cache[D];
479 LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
480 if (LastOR == true)
481 End = D;
482 }
483
484 // We only worry about critical deps.
485 if (End.IsCritical() != true)
486 continue;
487
488 // Dep is ok
489 if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
490 continue;
491
492 // Hm, the group is broken.. I have no idea how to handle this
493 if (Start != End)
494 {
495 clog << "Note, a broken or group was found in " << Pkg.Name() << "." << endl;
496 Fail = true;
497 break;
498 }
499
500 // Do not change protected packages
501 PkgIterator P = Start.SmartTargetPkg();
502 if ((Flags[P->ID] & Protected) == Protected)
503 {
504 if (Debug == true)
505 clog << " Reinet Failed because of protected " << P.Name() << endl;
506 Fail = true;
507 break;
508 }
509
510 // Upgrade the package if the candidate version will fix the problem.
511 if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
512 {
513 if (DoUpgrade(P) == false)
514 {
515 if (Debug == true)
516 clog << " Reinst Failed because of " << P.Name() << endl;
517 Fail = true;
518 break;
519 }
520 }
521 else
522 {
523 /* We let the algorithm deal with conflicts on its next iteration,
524 it is much smarter than us */
525 if (End->Type == pkgCache::Dep::Conflicts)
526 continue;
527
528 if (Debug == true)
529 clog << " Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
530 Fail = true;
531 break;
532 }
533 }
534
535 // Undo our operations - it might be smart to undo everything this did..
536 if (Fail == true)
537 {
538 if (WasKept == true)
539 Cache.MarkKeep(Pkg);
540 else
541 Cache.MarkDelete(Pkg);
542 return false;
543 }
544
545 if (Debug == true)
546 clog << " Re-Instated " << Pkg.Name() << endl;
547 return true;
548 }
549 /*}}}*/
550 // ProblemResolver::Resolve - Run the resolution pass /*{{{*/
551 // ---------------------------------------------------------------------
552 /* This routines works by calculating a score for each package. The score
553 is derived by considering the package's priority and all reverse
554 dependents giving an integer that reflects the amount of breakage that
555 adjusting the package will inflict.
556
557 It goes from highest score to lowest and corrects all of the breaks by
558 keeping or removing the dependant packages. If that fails then it removes
559 the package itself and goes on. The routine should be able to intelligently
560 go from any broken state to a fixed state.
561
562 The BrokenFix flag enables a mode where the algorithm tries to
563 upgrade packages to advoid problems. */
564 bool pkgProblemResolver::Resolve(bool BrokenFix)
565 {
566 unsigned long Size = Cache.HeaderP->PackageCount;
567
568 // Record which packages are marked for install
569 bool Again = false;
570 do
571 {
572 Again = false;
573 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
574 {
575 if (Cache[I].Install() == true)
576 Flags[I->ID] |= PreInstalled;
577 else
578 {
579 if (Cache[I].InstBroken() == true && BrokenFix == true)
580 {
581 Cache.MarkInstall(I,false);
582 if (Cache[I].Install() == true)
583 Again = true;
584 }
585
586 Flags[I->ID] &= ~PreInstalled;
587 }
588 Flags[I->ID] |= Upgradable;
589 }
590 }
591 while (Again == true);
592
593 if (Debug == true)
594 clog << "Starting" << endl;
595
596 MakeScores();
597
598 /* We have to order the packages so that the broken fixing pass
599 operates from highest score to lowest. This prevents problems when
600 high score packages cause the removal of lower score packages that
601 would cause the removal of even lower score packages. */
602 pkgCache::Package **PList = new pkgCache::Package *[Size];
603 pkgCache::Package **PEnd = PList;
604 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
605 *PEnd++ = I;
606 This = this;
607 qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
608
609 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
610 if (Scores[(*K)->ID] != 0)
611 {
612 pkgCache::PkgIterator Pkg(Cache,*K);
613 clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
614 ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
615 Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
616 } */
617
618 if (Debug == true)
619 clog << "Starting 2" << endl;
620
621 /* Now consider all broken packages. For each broken package we either
622 remove the package or fix it's problem. We do this once, it should
623 not be possible for a loop to form (that is a < b < c and fixing b by
624 changing a breaks c) */
625 bool Change = true;
626 for (int Counter = 0; Counter != 10 && Change == true; Counter++)
627 {
628 Change = false;
629 for (pkgCache::Package **K = PList; K != PEnd; K++)
630 {
631 pkgCache::PkgIterator I(Cache,*K);
632
633 /* We attempt to install this and see if any breaks result,
634 this takes care of some strange cases */
635 if (Cache[I].CandidateVer != Cache[I].InstallVer &&
636 I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
637 (Flags[I->ID] & PreInstalled) != 0 &&
638 (Flags[I->ID] & Protected) == 0 &&
639 (Flags[I->ID] & ReInstateTried) == 0)
640 {
641 if (Debug == true)
642 clog << " Try to Re-Instate " << I.Name() << endl;
643 int OldBreaks = Cache.BrokenCount();
644 pkgCache::Version *OldVer = Cache[I].InstallVer;
645 Flags[I->ID] &= ReInstateTried;
646
647 Cache.MarkInstall(I,false);
648 if (Cache[I].InstBroken() == true ||
649 OldBreaks < Cache.BrokenCount())
650 {
651 if (OldVer == 0)
652 Cache.MarkDelete(I);
653 else
654 Cache.MarkKeep(I);
655 }
656 else
657 if (Debug == true)
658 clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
659 }
660
661 if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
662 continue;
663
664 // Isolate the problem dependency
665 PackageKill KillList[100];
666 PackageKill *LEnd = KillList;
667 for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
668 {
669 // Compute a single dependency element (glob or)
670 pkgCache::DepIterator Start = D;
671 pkgCache::DepIterator End = D;
672 unsigned char State = 0;
673 for (bool LastOR = true; D.end() == false && LastOR == true; D++)
674 {
675 State |= Cache[D];
676 LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
677 if (LastOR == true)
678 End = D;
679 }
680
681 // We only worry about critical deps.
682 if (End.IsCritical() != true)
683 continue;
684
685 // Dep is ok
686 if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
687 continue;
688
689 // Hm, the group is broken.. I have no idea how to handle this
690 if (Start != End)
691 {
692 clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
693 Cache.MarkDelete(I);
694 break;
695 }
696
697 if (Debug == true)
698 clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
699
700 /* Conflicts is simple, decide if we should remove this package
701 or the conflicted one */
702 pkgCache::Version **VList = End.AllTargets();
703 bool Done = false;
704 for (pkgCache::Version **V = VList; *V != 0; V++)
705 {
706 pkgCache::VerIterator Ver(Cache,*V);
707 pkgCache::PkgIterator Pkg = Ver.ParentPkg();
708
709 if (Debug == true)
710 clog << " Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
711 " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
712 if (Scores[I->ID] <= Scores[Pkg->ID] ||
713 ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
714 End->Type != pkgCache::Dep::Conflicts))
715 {
716 if ((Flags[I->ID] & Protected) == Protected)
717 continue;
718
719 // See if a keep will do
720 Cache.MarkKeep(I);
721 if (Cache[I].InstBroken() == false)
722 {
723 if (Debug == true)
724 clog << " Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
725 }
726 else
727 {
728 if (BrokenFix == false || DoUpgrade(I) == false)
729 {
730 if (Debug == true)
731 clog << " Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
732 Cache.MarkDelete(I);
733 if (Counter > 1)
734 Scores[I->ID] = Scores[Pkg->ID];
735 }
736 }
737
738 Change = true;
739 Done = true;
740 break;
741 }
742 else
743 {
744 // Skip this if it is protected
745 if ((Flags[Pkg->ID] & Protected) != 0)
746 continue;
747
748 LEnd->Pkg = Pkg;
749 LEnd->Dep = End;
750 LEnd++;
751
752 if (End->Type != pkgCache::Dep::Conflicts)
753 break;
754 }
755 }
756
757 // Hm, nothing can possibly satisify this dep. Nuke it.
758 if (VList[0] == 0 && End->Type != pkgCache::Dep::Conflicts &&
759 (Flags[I->ID] & Protected) != Protected)
760 {
761 Cache.MarkKeep(I);
762 if (Cache[I].InstBroken() == false)
763 {
764 if (Debug == true)
765 clog << " Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
766 }
767 else
768 {
769 if (Debug == true)
770 clog << " Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
771 Cache.MarkDelete(I);
772 }
773
774 Change = true;
775 Done = true;
776 }
777
778 delete [] VList;
779 if (Done == true)
780 break;
781 }
782
783 // Apply the kill list now
784 if (Cache[I].InstallVer != 0)
785 for (PackageKill *J = KillList; J != LEnd; J++)
786 {
787 Change = true;
788 if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
789 {
790 if (J->Dep->Type == pkgCache::Dep::Conflicts)
791 {
792 if (Debug == true)
793 clog << " Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
794 Cache.MarkDelete(J->Pkg);
795 }
796 }
797 else
798 {
799 if (Debug == true)
800 clog << " Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
801 Cache.MarkKeep(J->Pkg);
802 }
803
804 if (Counter > 1)
805 Scores[J->Pkg->ID] = Scores[I->ID];
806 }
807 }
808 }
809
810 if (Debug == true)
811 clog << "Done" << endl;
812
813 delete [] Scores;
814 delete [] PList;
815
816 if (Cache.BrokenCount() != 0)
817 return _error->Error("Internal error, pkgProblemResolver::Resolve generated breaks.");
818
819 return true;
820 }
821 /*}}}*/
822 // ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
823 // ---------------------------------------------------------------------
824 /* This is the work horse of the soft upgrade routine. It is very gental
825 in that it does not install or remove any packages. It is assumed that the
826 system was non-broken previously. */
827 bool pkgProblemResolver::ResolveByKeep()
828 {
829 unsigned long Size = Cache.HeaderP->PackageCount;
830
831 if (Debug == true)
832 clog << "Entering ResolveByKeep" << endl;
833
834 MakeScores();
835
836 /* We have to order the packages so that the broken fixing pass
837 operates from highest score to lowest. This prevents problems when
838 high score packages cause the removal of lower score packages that
839 would cause the removal of even lower score packages. */
840 pkgCache::Package **PList = new pkgCache::Package *[Size];
841 pkgCache::Package **PEnd = PList;
842 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
843 *PEnd++ = I;
844 This = this;
845 qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
846
847 // Consider each broken package
848 pkgCache::Package **LastStop = 0;
849 for (pkgCache::Package **K = PList; K != PEnd; K++)
850 {
851 pkgCache::PkgIterator I(Cache,*K);
852
853 if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
854 continue;
855
856 /* Keep the package. If this works then great, otherwise we have
857 to be significantly more agressive and manipulate its dependencies */
858 if ((Flags[I->ID] & Protected) == 0)
859 {
860 if (Debug == true)
861 clog << "Keeping package " << I.Name() << endl;
862 Cache.MarkKeep(I);
863 if (Cache[I].InstBroken() == false)
864 {
865 K = PList;
866 continue;
867 }
868 }
869
870 // Isolate the problem dependencies
871 for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
872 {
873 // Compute a single dependency element (glob or)
874 pkgCache::DepIterator Start = D;
875 pkgCache::DepIterator End = D;
876 unsigned char State = 0;
877 for (bool LastOR = true; D.end() == false && LastOR == true; D++)
878 {
879 State |= Cache[D];
880 LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
881 if (LastOR == true)
882 End = D;
883 }
884
885 // We only worry about critical deps.
886 if (End.IsCritical() != true)
887 continue;
888
889 // Dep is ok
890 if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
891 continue;
892
893 // Hm, the group is broken.. I have no idea how to handle this
894 if (Start != End)
895 {
896 clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
897 if ((Flags[I->ID] & Protected) == 0)
898 Cache.MarkKeep(I);
899 break;
900 }
901
902 if (Debug == true)
903 clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
904
905 // Look at all the possible provides on this package
906 pkgCache::Version **VList = End.AllTargets();
907 for (pkgCache::Version **V = VList; *V != 0; V++)
908 {
909 pkgCache::VerIterator Ver(Cache,*V);
910 pkgCache::PkgIterator Pkg = Ver.ParentPkg();
911
912 // It is not keepable
913 if (Cache[Pkg].InstallVer == 0 ||
914 Pkg->CurrentVer == 0)
915 continue;
916
917 if ((Flags[I->ID] & Protected) == 0)
918 {
919 if (Debug == true)
920 clog << " Keeping Package " << Pkg.Name() << " due to dep" << endl;
921 Cache.MarkKeep(Pkg);
922 }
923
924 if (Cache[I].InstBroken() == false)
925 break;
926 }
927
928 if (Cache[I].InstBroken() == false)
929 break;
930 }
931
932 if (Cache[I].InstBroken() == true)
933 continue;
934
935 // Restart again.
936 if (K == LastStop)
937 return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
938 LastStop = K;
939 K = PList;
940 }
941
942 return true;
943 }
944 /*}}}*/
945 // ProblemResolver::InstallProtect - Install all protected packages /*{{{*/
946 // ---------------------------------------------------------------------
947 /* This is used to make sure protected packages are installed */
948 void pkgProblemResolver::InstallProtect()
949 {
950 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
951 {
952 if ((Flags[I->ID] & Protected) == Protected)
953 {
954 if ((Flags[I->ID] & ToRemove) == ToRemove)
955 Cache.MarkDelete(I);
956 else
957 Cache.MarkInstall(I,false);
958 }
959 }
960 }
961 /*}}}*/