]>
git.saurik.com Git - apt.git/blob - apt-pkg/algorithms.cc
1 // -*- mode: cpp; mode: fold -*-
3 // $Id: algorithms.cc,v 1.19 1999/06/28 03:11:24 jgg Exp $
4 /* ######################################################################
6 Algorithms - A set of misc algorithms
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.
14 ##################################################################### */
16 // Include Files /*{{{*/
18 #pragma implementation "apt-pkg/algorithms.h"
20 #include <apt-pkg/algorithms.h>
21 #include <apt-pkg/error.h>
22 #include <apt-pkg/configuration.h>
26 pkgProblemResolver
*pkgProblemResolver::This
= 0;
28 // Simulate::Simulate - Constructor /*{{{*/
29 // ---------------------------------------------------------------------
31 pkgSimulate::pkgSimulate(pkgDepCache
&Cache
) : pkgPackageManager(Cache
),
34 Flags
= new unsigned char[Cache
.HeaderP
->PackageCount
];
35 memset(Flags
,0,sizeof(*Flags
)*Cache
.HeaderP
->PackageCount
);
38 // Simulate::Install - Simulate unpacking of a package /*{{{*/
39 // ---------------------------------------------------------------------
41 bool pkgSimulate::Install(PkgIterator iPkg
,string
/*File*/)
44 PkgIterator Pkg
= Sim
.FindPkg(iPkg
.Name());
47 cout
<< "Inst " << Pkg
.Name();
48 Sim
.MarkInstall(Pkg
,false);
50 // Look for broken conflicts+predepends.
51 for (PkgIterator I
= Sim
.PkgBegin(); I
.end() == false; I
++)
53 if (Sim
[I
].InstallVer
== 0)
56 for (DepIterator D
= Sim
[I
].InstVerIter(Sim
).DependsList(); D
.end() == false; D
++)
57 if (D
->Type
== pkgCache::Dep::Conflicts
|| D
->Type
== pkgCache::Dep::PreDepends
)
59 if ((Sim
[D
] & pkgDepCache::DepInstall
) == 0)
61 cout
<< " [" << I
.Name() << " on " << D
.TargetPkg().Name() << ']';
62 if (D
->Type
== pkgCache::Dep::Conflicts
)
63 _error
->Error("Fatal, conflicts violated %s",I
.Name());
68 if (Sim
.BrokenCount() != 0)
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
80 bool pkgSimulate::Configure(PkgIterator iPkg
)
83 PkgIterator Pkg
= Sim
.FindPkg(iPkg
.Name());
86 // Sim.MarkInstall(Pkg,false);
87 if (Sim
[Pkg
].InstBroken() == true)
89 cout
<< "Conf " << Pkg
.Name() << " broken" << endl
;
93 // Print out each package and the failed dependencies
94 for (pkgCache::DepIterator D
= Sim
[Pkg
].InstVerIter(Sim
).DependsList(); D
.end() == false; D
++)
96 if (Sim
.IsImportantDep(D
) == false ||
97 (Sim
[D
] & pkgDepCache::DepInstall
) != 0)
100 if (D
->Type
== pkgCache::Dep::Conflicts
)
101 cout
<< " Conflicts:" << D
.TargetPkg().Name();
103 cout
<< " Depends:" << D
.TargetPkg().Name();
107 _error
->Error("Conf Broken %s",Pkg
.Name());
110 cout
<< "Conf " << Pkg
.Name();
112 if (Sim
.BrokenCount() != 0)
120 // Simulate::Remove - Simulate the removal of a package /*{{{*/
121 // ---------------------------------------------------------------------
123 bool pkgSimulate::Remove(PkgIterator iPkg
)
125 // Adapt the iterator
126 PkgIterator Pkg
= Sim
.FindPkg(iPkg
.Name());
130 cout
<< "Remv " << Pkg
.Name();
132 if (Sim
.BrokenCount() != 0)
140 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
141 // ---------------------------------------------------------------------
143 void pkgSimulate::ShortBreaks()
146 for (PkgIterator I
= Sim
.PkgBegin(); I
.end() == false; I
++)
148 if (Sim
[I
].InstBroken() == true)
150 if (Flags
[I
->ID
] == 0)
151 cout
<< I
.Name() << ' ';
153 cout << I.Name() << "! ";*/
159 // ApplyStatus - Adjust for non-ok packages /*{{{*/
160 // ---------------------------------------------------------------------
161 /* We attempt to change the state of the all packages that have failed
162 installation toward their real state. The ordering code will perform
163 the necessary calculations to deal with the problems. */
164 bool pkgApplyStatus(pkgDepCache
&Cache
)
166 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
168 // Only choice for a ReInstReq package is to reinstall
169 if (I
->InstState
== pkgCache::State::ReInstReq
||
170 I
->InstState
== pkgCache::State::HoldReInstReq
)
172 if (I
.CurrentVer().Downloadable() == true)
176 // Is this right? Will dpkg choke on an upgrade?
177 if (Cache
[I
].CandidateVerIter(Cache
).Downloadable() == true)
178 Cache
.MarkInstall(I
);
180 return _error
->Error("The package %s needs to be reinstalled, "
181 "but I can't find an archive for it.",I
.Name());
187 switch (I
->CurrentState
)
189 /* This means installation failed somehow - it does not need to be
190 re-unpacked (probably) */
191 case pkgCache::State::UnPacked
:
192 case pkgCache::State::HalfConfigured
:
193 if (I
.CurrentVer().Downloadable() == true ||
194 I
.State() != pkgCache::PkgIterator::NeedsUnpack
)
198 if (Cache
[I
].CandidateVerIter(Cache
).Downloadable() == true)
199 Cache
.MarkInstall(I
);
205 // This means removal failed
206 case pkgCache::State::HalfInstalled
:
211 if (I
->InstState
!= pkgCache::State::Ok
)
212 return _error
->Error("The package %s is not ok and I "
213 "don't know how to fix it!",I
.Name());
219 // FixBroken - Fix broken packages /*{{{*/
220 // ---------------------------------------------------------------------
221 /* This autoinstalls every broken package and then runs the problem resolver
223 bool pkgFixBroken(pkgDepCache
&Cache
)
225 // Auto upgrade all broken packages
226 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
227 if (Cache
[I
].NowBroken() == true)
228 Cache
.MarkInstall(I
,true);
230 /* Fix packages that are in a NeedArchive state but don't have a
231 downloadable install version */
232 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
234 if (I
.State() != pkgCache::PkgIterator::NeedsUnpack
||
235 Cache
[I
].Delete() == true)
238 if (Cache
[I
].InstVerIter(Cache
).Downloadable() == false)
241 Cache
.MarkInstall(I
,true);
244 pkgProblemResolver
Fix(Cache
);
245 return Fix
.Resolve(true);
248 // DistUpgrade - Distribution upgrade /*{{{*/
249 // ---------------------------------------------------------------------
250 /* This autoinstalls every package and then force installs every
251 pre-existing package. This creates the initial set of conditions which
252 most likely contain problems because too many things were installed.
254 The problem resolver is used to resolve the problems.
256 bool pkgDistUpgrade(pkgDepCache
&Cache
)
258 /* Auto upgrade all installed packages, this provides the basis
259 for the installation */
260 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
261 if (I
->CurrentVer
!= 0)
262 Cache
.MarkInstall(I
,true);
264 /* Now, auto upgrade all essential packages - this ensures that
265 the essential packages are present and working */
266 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
267 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
268 Cache
.MarkInstall(I
,true);
270 /* We do it again over all previously installed packages to force
271 conflict resolution on them all. */
272 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
273 if (I
->CurrentVer
!= 0)
274 Cache
.MarkInstall(I
,false);
276 pkgProblemResolver
Fix(Cache
);
278 // Hold back held packages.
279 if (_config
->FindB("APT::Ingore-Hold",false) == false)
281 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
283 if (I
->SelectedState
== pkgCache::State::Hold
)
291 return Fix
.Resolve();
294 // AllUpgrade - Upgrade as many packages as possible /*{{{*/
295 // ---------------------------------------------------------------------
296 /* Right now the system must be consistent before this can be called.
297 It also will not change packages marked for install, it only tries
298 to install packages not marked for install */
299 bool pkgAllUpgrade(pkgDepCache
&Cache
)
301 pkgProblemResolver
Fix(Cache
);
303 if (Cache
.BrokenCount() != 0)
306 // Upgrade all installed packages
307 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
309 if (Cache
[I
].Install() == true)
312 if (_config
->FindB("APT::Ingore-Hold",false) == false)
313 if (I
->SelectedState
== pkgCache::State::Hold
)
316 if (I
->CurrentVer
!= 0 && Cache
[I
].InstallVer
!= 0)
317 Cache
.MarkInstall(I
,false);
320 return Fix
.ResolveByKeep();
323 // MinimizeUpgrade - Minimizes the set of packages to be upgraded /*{{{*/
324 // ---------------------------------------------------------------------
325 /* This simply goes over the entire set of packages and tries to keep
326 each package marked for upgrade. If a conflict is generated then
327 the package is restored. */
328 bool pkgMinimizeUpgrade(pkgDepCache
&Cache
)
330 if (Cache
.BrokenCount() != 0)
333 // We loop indefinately to get the minimal set size.
338 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
341 if (Cache
[I
].Upgrade() == false || Cache
[I
].NewInstall() == true)
344 // Keep it and see if that is OK
346 if (Cache
.BrokenCount() != 0)
347 Cache
.MarkInstall(I
,false);
352 while (Change
== true);
354 if (Cache
.BrokenCount() != 0)
355 return _error
->Error("Internal Error in pkgMinimizeUpgrade");
361 // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
362 // ---------------------------------------------------------------------
364 pkgProblemResolver::pkgProblemResolver(pkgDepCache
&Cache
) : Cache(Cache
)
367 unsigned long Size
= Cache
.HeaderP
->PackageCount
;
368 Scores
= new signed short[Size
];
369 Flags
= new unsigned char[Size
];
370 memset(Flags
,0,sizeof(*Flags
)*Size
);
372 // Set debug to true to see its decision logic
373 Debug
= _config
->FindB("Debug::pkgProblemResolver",false);
376 // ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
377 // ---------------------------------------------------------------------
379 int pkgProblemResolver::ScoreSort(const void *a
,const void *b
)
381 Package
const **A
= (Package
const **)a
;
382 Package
const **B
= (Package
const **)b
;
383 if (This
->Scores
[(*A
)->ID
] > This
->Scores
[(*B
)->ID
])
385 if (This
->Scores
[(*A
)->ID
] < This
->Scores
[(*B
)->ID
])
390 // ProblemResolver::MakeScores - Make the score table /*{{{*/
391 // ---------------------------------------------------------------------
393 void pkgProblemResolver::MakeScores()
395 unsigned long Size
= Cache
.HeaderP
->PackageCount
;
396 memset(Scores
,0,sizeof(*Scores
)*Size
);
398 // Generate the base scores for a package based on its properties
399 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
401 if (Cache
[I
].InstallVer
== 0)
404 signed short &Score
= Scores
[I
->ID
];
406 /* This is arbitary, it should be high enough to elevate an
407 essantial package above most other packages but low enough
408 to allow an obsolete essential packages to be removed by
409 a conflicts on a powerfull normal package (ie libc6) */
410 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
413 // We transform the priority
414 // Important Required Standard Optional Extra
415 signed short PrioMap
[] = {0,3,2,1,-1,-2};
416 if (Cache
[I
].InstVerIter(Cache
)->Priority
<= 5)
417 Score
+= PrioMap
[Cache
[I
].InstVerIter(Cache
)->Priority
];
419 /* This helps to fix oddball problems with conflicting packages
420 on the same level. We enhance the score of installed packages */
421 if (I
->CurrentVer
!= 0)
425 // Now that we have the base scores we go and propogate dependencies
426 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
428 if (Cache
[I
].InstallVer
== 0)
431 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false; D
++)
433 if (D
->Type
== pkgCache::Dep::Depends
|| D
->Type
== pkgCache::Dep::PreDepends
)
434 Scores
[D
.TargetPkg()->ID
]++;
438 // Copy the scores to advoid additive looping
439 signed short *OldScores
= new signed short[Size
];
440 memcpy(OldScores
,Scores
,sizeof(*Scores
)*Size
);
442 /* Now we cause 1 level of dependency inheritance, that is we add the
443 score of the packages that depend on the target Package. This
444 fortifies high scoring packages */
445 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
447 if (Cache
[I
].InstallVer
== 0)
450 for (pkgCache::DepIterator D
= I
.RevDependsList(); D
.end() == false; D
++)
452 // Only do it for the install version
453 if ((pkgCache::Version
*)D
.ParentVer() != Cache
[D
.ParentPkg()].InstallVer
||
454 (D
->Type
!= pkgCache::Dep::Depends
&& D
->Type
!= pkgCache::Dep::PreDepends
))
457 Scores
[I
->ID
] += abs(OldScores
[D
.ParentPkg()->ID
]);
461 /* Now we propogate along provides. This makes the packages that
462 provide important packages extremely important */
463 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
465 for (pkgCache::PrvIterator P
= I
.ProvidesList(); P
.end() == false; P
++)
467 // Only do it once per package
468 if ((pkgCache::Version
*)P
.OwnerVer() != Cache
[P
.OwnerPkg()].InstallVer
)
470 Scores
[P
.OwnerPkg()->ID
] += abs(Scores
[I
->ID
] - OldScores
[I
->ID
]);
474 /* Protected things are pushed really high up. This number should put them
475 ahead of everything */
476 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
478 if ((Flags
[I
->ID
] & Protected
) != 0)
479 Scores
[I
->ID
] += 10000;
480 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
481 Scores
[I
->ID
] += 5000;
487 // ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
488 // ---------------------------------------------------------------------
489 /* This goes through and tries to reinstall packages to make this package
491 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg
)
493 if ((Flags
[Pkg
->ID
] & Upgradable
) == 0 || Cache
[Pkg
].Upgradable() == false)
496 Flags
[Pkg
->ID
] &= ~Upgradable
;
498 bool WasKept
= Cache
[Pkg
].Keep();
499 Cache
.MarkInstall(Pkg
,false);
501 // This must be a virtual package or something like that.
502 if (Cache
[Pkg
].InstVerIter(Cache
).end() == true)
505 // Isolate the problem dependency
507 for (pkgCache::DepIterator D
= Cache
[Pkg
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
509 // Compute a single dependency element (glob or)
510 pkgCache::DepIterator Start
= D
;
511 pkgCache::DepIterator End
= D
;
512 unsigned char State
= 0;
513 for (bool LastOR
= true; D
.end() == false && LastOR
== true; D
++)
516 LastOR
= (D
->CompareOp
& pkgCache::Dep::Or
) == pkgCache::Dep::Or
;
521 // We only worry about critical deps.
522 if (End
.IsCritical() != true)
526 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
529 // Hm, the group is broken.. I have no idea how to handle this
532 clog
<< "Note, a broken or group was found in " << Pkg
.Name() << "." << endl
;
537 // Do not change protected packages
538 PkgIterator P
= Start
.SmartTargetPkg();
539 if ((Flags
[P
->ID
] & Protected
) == Protected
)
542 clog
<< " Reinet Failed because of protected " << P
.Name() << endl
;
547 // Upgrade the package if the candidate version will fix the problem.
548 if ((Cache
[Start
] & pkgDepCache::DepCVer
) == pkgDepCache::DepCVer
)
550 if (DoUpgrade(P
) == false)
553 clog
<< " Reinst Failed because of " << P
.Name() << endl
;
560 /* We let the algorithm deal with conflicts on its next iteration,
561 it is much smarter than us */
562 if (End
->Type
== pkgCache::Dep::Conflicts
)
566 clog
<< " Reinst Failed early because of " << Start
.TargetPkg().Name() << endl
;
572 // Undo our operations - it might be smart to undo everything this did..
578 Cache
.MarkDelete(Pkg
);
583 clog
<< " Re-Instated " << Pkg
.Name() << endl
;
587 // ProblemResolver::Resolve - Run the resolution pass /*{{{*/
588 // ---------------------------------------------------------------------
589 /* This routines works by calculating a score for each package. The score
590 is derived by considering the package's priority and all reverse
591 dependents giving an integer that reflects the amount of breakage that
592 adjusting the package will inflict.
594 It goes from highest score to lowest and corrects all of the breaks by
595 keeping or removing the dependant packages. If that fails then it removes
596 the package itself and goes on. The routine should be able to intelligently
597 go from any broken state to a fixed state.
599 The BrokenFix flag enables a mode where the algorithm tries to
600 upgrade packages to advoid problems. */
601 bool pkgProblemResolver::Resolve(bool BrokenFix
)
603 unsigned long Size
= Cache
.HeaderP
->PackageCount
;
605 // Record which packages are marked for install
610 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
612 if (Cache
[I
].Install() == true)
613 Flags
[I
->ID
] |= PreInstalled
;
616 if (Cache
[I
].InstBroken() == true && BrokenFix
== true)
618 Cache
.MarkInstall(I
,false);
619 if (Cache
[I
].Install() == true)
623 Flags
[I
->ID
] &= ~PreInstalled
;
625 Flags
[I
->ID
] |= Upgradable
;
628 while (Again
== true);
631 clog
<< "Starting" << endl
;
635 /* We have to order the packages so that the broken fixing pass
636 operates from highest score to lowest. This prevents problems when
637 high score packages cause the removal of lower score packages that
638 would cause the removal of even lower score packages. */
639 pkgCache::Package
**PList
= new pkgCache::Package
*[Size
];
640 pkgCache::Package
**PEnd
= PList
;
641 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
644 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
646 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
647 if (Scores[(*K)->ID] != 0)
649 pkgCache::PkgIterator Pkg(Cache,*K);
650 clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
651 ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
652 Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
656 clog
<< "Starting 2" << endl
;
658 /* Now consider all broken packages. For each broken package we either
659 remove the package or fix it's problem. We do this once, it should
660 not be possible for a loop to form (that is a < b < c and fixing b by
661 changing a breaks c) */
663 for (int Counter
= 0; Counter
!= 10 && Change
== true; Counter
++)
666 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
668 pkgCache::PkgIterator
I(Cache
,*K
);
670 /* We attempt to install this and see if any breaks result,
671 this takes care of some strange cases */
672 if (Cache
[I
].CandidateVer
!= Cache
[I
].InstallVer
&&
673 I
->CurrentVer
!= 0 && Cache
[I
].InstallVer
!= 0 &&
674 (Flags
[I
->ID
] & PreInstalled
) != 0 &&
675 (Flags
[I
->ID
] & Protected
) == 0 &&
676 (Flags
[I
->ID
] & ReInstateTried
) == 0)
679 clog
<< " Try to Re-Instate " << I
.Name() << endl
;
680 unsigned long OldBreaks
= Cache
.BrokenCount();
681 pkgCache::Version
*OldVer
= Cache
[I
].InstallVer
;
682 Flags
[I
->ID
] &= ReInstateTried
;
684 Cache
.MarkInstall(I
,false);
685 if (Cache
[I
].InstBroken() == true ||
686 OldBreaks
< Cache
.BrokenCount())
695 clog
<< "Re-Instated " << I
.Name() << " (" << OldBreaks
<< " vs " << Cache
.BrokenCount() << ')' << endl
;
698 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
701 // Isolate the problem dependency
702 PackageKill KillList
[100];
703 PackageKill
*LEnd
= KillList
;
704 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
706 // Compute a single dependency element (glob or)
707 pkgCache::DepIterator Start
;
708 pkgCache::DepIterator End
;
711 // We only worry about critical deps.
712 if (End
.IsCritical() != true)
716 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
719 // Hm, the group is broken.. I have no idea how to handle this
723 clog
<< "Note, a broken or group was found in " << I
.Name() << "." << endl
;
724 if ((Flags
[I
->ID
] & Protected
) != Protected
)
730 clog
<< "Package " << I
.Name() << " has broken dep on " << End
.TargetPkg().Name() << endl
;
732 /* Look across the version list. If there are no possible
733 targets then we keep the package and bail. This is necessary
734 if a package has a dep on another package that cant be found */
735 pkgCache::Version
**VList
= End
.AllTargets();
736 if (*VList
== 0 && (Flags
[I
->ID
] & Protected
) != Protected
&&
737 End
->Type
!= pkgCache::Dep::Conflicts
&&
738 Cache
[I
].NowBroken() == false)
746 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
748 pkgCache::VerIterator
Ver(Cache
,*V
);
749 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
752 clog
<< " Considering " << Pkg
.Name() << ' ' << (int)Scores
[Pkg
->ID
] <<
753 " as a solution to " << I
.Name() << ' ' << (int)Scores
[I
->ID
] << endl
;
754 if (Scores
[I
->ID
] <= Scores
[Pkg
->ID
] ||
755 ((Cache
[End
] & pkgDepCache::DepGNow
) == 0 &&
756 End
->Type
!= pkgCache::Dep::Conflicts
))
758 // Try a little harder to fix protected packages..
759 if ((Flags
[I
->ID
] & Protected
) == Protected
)
761 if (DoUpgrade(Pkg
) == true)
762 Scores
[Pkg
->ID
] = Scores
[I
->ID
];
766 /* See if a keep will do, unless the package is protected,
767 then installing it will be necessary */
769 if (Cache
[I
].InstBroken() == false)
772 clog
<< " Holding Back " << I
.Name() << " rather than change " << End
.TargetPkg().Name() << endl
;
776 if (BrokenFix
== false || DoUpgrade(I
) == false)
779 clog
<< " Removing " << I
.Name() << " rather than change " << End
.TargetPkg().Name() << endl
;
782 Scores
[I
->ID
] = Scores
[Pkg
->ID
];
792 // Skip this if it is protected
793 if ((Flags
[Pkg
->ID
] & Protected
) != 0)
800 if (End
->Type
!= pkgCache::Dep::Conflicts
)
805 // Hm, nothing can possibly satisify this dep. Nuke it.
806 if (VList
[0] == 0 && End
->Type
!= pkgCache::Dep::Conflicts
&&
807 (Flags
[I
->ID
] & Protected
) != Protected
)
810 if (Cache
[I
].InstBroken() == false)
813 clog
<< " Holding Back " << I
.Name() << " because I can't find " << End
.TargetPkg().Name() << endl
;
818 clog
<< " Removing " << I
.Name() << " because I can't find " << End
.TargetPkg().Name() << endl
;
831 // Apply the kill list now
832 if (Cache
[I
].InstallVer
!= 0)
833 for (PackageKill
*J
= KillList
; J
!= LEnd
; J
++)
836 if ((Cache
[J
->Dep
] & pkgDepCache::DepGNow
) == 0)
838 if (J
->Dep
->Type
== pkgCache::Dep::Conflicts
)
841 clog
<< " Fixing " << I
.Name() << " via remove of " << J
->Pkg
.Name() << endl
;
842 Cache
.MarkDelete(J
->Pkg
);
848 clog
<< " Fixing " << I
.Name() << " via keep of " << J
->Pkg
.Name() << endl
;
849 Cache
.MarkKeep(J
->Pkg
);
853 Scores
[J
->Pkg
->ID
] = Scores
[I
->ID
];
859 clog
<< "Done" << endl
;
864 if (Cache
.BrokenCount() != 0)
866 // See if this is the result of a hold
867 pkgCache::PkgIterator I
= Cache
.PkgBegin();
868 for (;I
.end() != true; I
++)
870 if (Cache
[I
].InstBroken() == false)
872 if ((Flags
[I
->ID
] & Protected
) != Protected
)
873 return _error
->Error("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.");
875 return _error
->Error("Unable to correct problems, you have held broken packages.");
881 // ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
882 // ---------------------------------------------------------------------
883 /* This is the work horse of the soft upgrade routine. It is very gental
884 in that it does not install or remove any packages. It is assumed that the
885 system was non-broken previously. */
886 bool pkgProblemResolver::ResolveByKeep()
888 unsigned long Size
= Cache
.HeaderP
->PackageCount
;
891 clog
<< "Entering ResolveByKeep" << endl
;
895 /* We have to order the packages so that the broken fixing pass
896 operates from highest score to lowest. This prevents problems when
897 high score packages cause the removal of lower score packages that
898 would cause the removal of even lower score packages. */
899 pkgCache::Package
**PList
= new pkgCache::Package
*[Size
];
900 pkgCache::Package
**PEnd
= PList
;
901 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
904 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
906 // Consider each broken package
907 pkgCache::Package
**LastStop
= 0;
908 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
910 pkgCache::PkgIterator
I(Cache
,*K
);
912 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
915 /* Keep the package. If this works then great, otherwise we have
916 to be significantly more agressive and manipulate its dependencies */
917 if ((Flags
[I
->ID
] & Protected
) == 0)
920 clog
<< "Keeping package " << I
.Name() << endl
;
922 if (Cache
[I
].InstBroken() == false)
929 // Isolate the problem dependencies
930 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
932 // Compute a single dependency element (glob or)
933 pkgCache::DepIterator Start
= D
;
934 pkgCache::DepIterator End
= D
;
935 unsigned char State
= 0;
936 for (bool LastOR
= true; D
.end() == false && LastOR
== true; D
++)
939 LastOR
= (D
->CompareOp
& pkgCache::Dep::Or
) == pkgCache::Dep::Or
;
944 // We only worry about critical deps.
945 if (End
.IsCritical() != true)
949 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
952 // Hm, the group is broken.. I have no idea how to handle this
955 clog
<< "Note, a broken or group was found in " << I
.Name() << "." << endl
;
956 if ((Flags
[I
->ID
] & Protected
) == 0)
962 clog
<< "Package " << I
.Name() << " has broken dep on " << End
.TargetPkg().Name() << endl
;
964 // Look at all the possible provides on this package
965 pkgCache::Version
**VList
= End
.AllTargets();
966 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
968 pkgCache::VerIterator
Ver(Cache
,*V
);
969 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
971 // It is not keepable
972 if (Cache
[Pkg
].InstallVer
== 0 ||
973 Pkg
->CurrentVer
== 0)
976 if ((Flags
[I
->ID
] & Protected
) == 0)
979 clog
<< " Keeping Package " << Pkg
.Name() << " due to dep" << endl
;
983 if (Cache
[I
].InstBroken() == false)
987 if (Cache
[I
].InstBroken() == false)
991 if (Cache
[I
].InstBroken() == true)
996 return _error
->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I
.Name());
1004 // ProblemResolver::InstallProtect - Install all protected packages /*{{{*/
1005 // ---------------------------------------------------------------------
1006 /* This is used to make sure protected packages are installed */
1007 void pkgProblemResolver::InstallProtect()
1009 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
1011 if ((Flags
[I
->ID
] & Protected
) == Protected
)
1013 if ((Flags
[I
->ID
] & ToRemove
) == ToRemove
)
1014 Cache
.MarkDelete(I
);
1016 Cache
.MarkInstall(I
,false);