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