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