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