]> git.saurik.com Git - apt.git/blob - apt-pkg/algorithms.cc
projects / apt.git / blob
? search:


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