]>
git.saurik.com Git - apt.git/blob - apt-pkg/algorithms.cc
1 // -*- mode: cpp; mode: fold -*-
3 // $Id: algorithms.cc,v 1.44 2002/11/28 18:49:16 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>
23 #include <apt-pkg/version.h>
24 #include <apt-pkg/sptr.h>
28 #include <sys/types.h>
33 pkgProblemResolver
*pkgProblemResolver::This
= 0;
35 // Simulate::Simulate - Constructor /*{{{*/
36 // ---------------------------------------------------------------------
37 /* The legacy translations here of input Pkg iterators is obsolete,
38 this is not necessary since the pkgCaches are fully shared now. */
39 pkgSimulate::pkgSimulate(pkgDepCache
*Cache
) : pkgPackageManager(Cache
),
41 Sim(&Cache
->GetCache(),&iPolicy
)
44 Flags
= new unsigned char[Cache
->Head().PackageCount
];
45 memset(Flags
,0,sizeof(*Flags
)*Cache
->Head().PackageCount
);
47 // Fake a filename so as not to activate the media swapping
48 string Jnk
= "SIMULATE";
49 for (unsigned int I
= 0; I
!= Cache
->Head().PackageCount
; I
++)
53 // Simulate::Describe - Describe a package /*{{{*/
54 // ---------------------------------------------------------------------
55 /* Parameter Current == true displays the current package version,
56 Parameter Candidate == true displays the candidate package version */
57 void pkgSimulate::Describe(PkgIterator Pkg
,ostream
&out
,bool Current
,bool Candidate
)
65 Ver
= Pkg
.CurrentVer();
66 if (Ver
.end() == false)
67 out
<< " [" << Ver
.VerStr() << ']';
70 if (Candidate
== true)
72 Ver
= Sim
[Pkg
].CandidateVerIter(Sim
);
73 if (Ver
.end() == true)
76 out
<< " (" << Ver
.VerStr() << ' ' << Ver
.RelStr() << ')';
80 // Simulate::Install - Simulate unpacking of a package /*{{{*/
81 // ---------------------------------------------------------------------
83 bool pkgSimulate::Install(PkgIterator iPkg
,string
/*File*/)
86 PkgIterator Pkg
= Sim
.FindPkg(iPkg
.Name());
90 Describe(Pkg
,cout
,true,true);
91 Sim
.MarkInstall(Pkg
,false);
93 // Look for broken conflicts+predepends.
94 for (PkgIterator I
= Sim
.PkgBegin(); I
.end() == false; I
++)
96 if (Sim
[I
].InstallVer
== 0)
99 for (DepIterator D
= Sim
[I
].InstVerIter(Sim
).DependsList(); D
.end() == false;)
104 if (Start
->Type
== pkgCache::Dep::Conflicts
||
105 Start
->Type
== pkgCache::Dep::DpkgBreaks
||
106 Start
->Type
== pkgCache::Dep::Obsoletes
||
107 End
->Type
== pkgCache::Dep::PreDepends
)
109 if ((Sim
[End
] & pkgDepCache::DepGInstall
) == 0)
111 cout
<< " [" << I
.Name() << " on " << Start
.TargetPkg().Name() << ']';
112 if (Start
->Type
== pkgCache::Dep::Conflicts
)
113 _error
->Error("Fatal, conflicts violated %s",I
.Name());
119 if (Sim
.BrokenCount() != 0)
126 // Simulate::Configure - Simulate configuration of a Package /*{{{*/
127 // ---------------------------------------------------------------------
128 /* This is not an acurate simulation of relatity, we should really not
129 install the package.. For some investigations it may be necessary
131 bool pkgSimulate::Configure(PkgIterator iPkg
)
133 // Adapt the iterator
134 PkgIterator Pkg
= Sim
.FindPkg(iPkg
.Name());
137 // Sim.MarkInstall(Pkg,false);
138 if (Sim
[Pkg
].InstBroken() == true)
140 cout
<< "Conf " << Pkg
.Name() << " broken" << endl
;
144 // Print out each package and the failed dependencies
145 for (pkgCache::DepIterator D
= Sim
[Pkg
].InstVerIter(Sim
).DependsList(); D
.end() == false; D
++)
147 if (Sim
.IsImportantDep(D
) == false ||
148 (Sim
[D
] & pkgDepCache::DepInstall
) != 0)
151 if (D
->Type
== pkgCache::Dep::Obsoletes
)
152 cout
<< " Obsoletes:" << D
.TargetPkg().Name();
153 else if (D
->Type
== pkgCache::Dep::Conflicts
)
154 cout
<< " Conflicts:" << D
.TargetPkg().Name();
155 else if (D
->Type
== pkgCache::Dep::DpkgBreaks
)
156 cout
<< " Breaks:" << D
.TargetPkg().Name();
158 cout
<< " Depends:" << D
.TargetPkg().Name();
162 _error
->Error("Conf Broken %s",Pkg
.Name());
167 Describe(Pkg
,cout
,false,true);
170 if (Sim
.BrokenCount() != 0)
178 // Simulate::Remove - Simulate the removal of a package /*{{{*/
179 // ---------------------------------------------------------------------
181 bool pkgSimulate::Remove(PkgIterator iPkg
,bool Purge
)
183 // Adapt the iterator
184 PkgIterator Pkg
= Sim
.FindPkg(iPkg
.Name());
192 Describe(Pkg
,cout
,true,false);
194 if (Sim
.BrokenCount() != 0)
202 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
203 // ---------------------------------------------------------------------
205 void pkgSimulate::ShortBreaks()
208 for (PkgIterator I
= Sim
.PkgBegin(); I
.end() == false; I
++)
210 if (Sim
[I
].InstBroken() == true)
212 if (Flags
[I
->ID
] == 0)
213 cout
<< I
.Name() << ' ';
215 cout << I.Name() << "! ";*/
221 // ApplyStatus - Adjust for non-ok packages /*{{{*/
222 // ---------------------------------------------------------------------
223 /* We attempt to change the state of the all packages that have failed
224 installation toward their real state. The ordering code will perform
225 the necessary calculations to deal with the problems. */
226 bool pkgApplyStatus(pkgDepCache
&Cache
)
228 pkgDepCache::ActionGroup
group(Cache
);
230 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
232 if (I
->VersionList
== 0)
235 // Only choice for a ReInstReq package is to reinstall
236 if (I
->InstState
== pkgCache::State::ReInstReq
||
237 I
->InstState
== pkgCache::State::HoldReInstReq
)
239 if (I
->CurrentVer
!= 0 && I
.CurrentVer().Downloadable() == true)
240 Cache
.MarkKeep(I
, false, false);
243 // Is this right? Will dpkg choke on an upgrade?
244 if (Cache
[I
].CandidateVer
!= 0 &&
245 Cache
[I
].CandidateVerIter(Cache
).Downloadable() == true)
246 Cache
.MarkInstall(I
, false, 0, false);
248 return _error
->Error(_("The package %s needs to be reinstalled, "
249 "but I can't find an archive for it."),I
.Name());
255 switch (I
->CurrentState
)
257 /* This means installation failed somehow - it does not need to be
258 re-unpacked (probably) */
259 case pkgCache::State::UnPacked
:
260 case pkgCache::State::HalfConfigured
:
261 if ((I
->CurrentVer
!= 0 && I
.CurrentVer().Downloadable() == true) ||
262 I
.State() != pkgCache::PkgIterator::NeedsUnpack
)
263 Cache
.MarkKeep(I
, false, false);
266 if (Cache
[I
].CandidateVer
!= 0 &&
267 Cache
[I
].CandidateVerIter(Cache
).Downloadable() == true)
268 Cache
.MarkInstall(I
, true, 0, false);
274 // This means removal failed
275 case pkgCache::State::HalfInstalled
:
280 if (I
->InstState
!= pkgCache::State::Ok
)
281 return _error
->Error("The package %s is not ok and I "
282 "don't know how to fix it!",I
.Name());
288 // FixBroken - Fix broken packages /*{{{*/
289 // ---------------------------------------------------------------------
290 /* This autoinstalls every broken package and then runs the problem resolver
292 bool pkgFixBroken(pkgDepCache
&Cache
)
294 pkgDepCache::ActionGroup
group(Cache
);
296 // Auto upgrade all broken packages
297 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
298 if (Cache
[I
].NowBroken() == true)
299 Cache
.MarkInstall(I
, true, 0, false);
301 /* Fix packages that are in a NeedArchive state but don't have a
302 downloadable install version */
303 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
305 if (I
.State() != pkgCache::PkgIterator::NeedsUnpack
||
306 Cache
[I
].Delete() == true)
309 if (Cache
[I
].InstVerIter(Cache
).Downloadable() == false)
312 Cache
.MarkInstall(I
, true, 0, false);
315 pkgProblemResolver
Fix(&Cache
);
316 return Fix
.Resolve(true);
319 // DistUpgrade - Distribution upgrade /*{{{*/
320 // ---------------------------------------------------------------------
321 /* This autoinstalls every package and then force installs every
322 pre-existing package. This creates the initial set of conditions which
323 most likely contain problems because too many things were installed.
325 The problem resolver is used to resolve the problems.
327 bool pkgDistUpgrade(pkgDepCache
&Cache
)
329 pkgDepCache::ActionGroup
group(Cache
);
331 /* Auto upgrade all installed packages, this provides the basis
332 for the installation */
333 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
334 if (I
->CurrentVer
!= 0)
335 Cache
.MarkInstall(I
, true, 0, false);
337 /* Now, auto upgrade all essential packages - this ensures that
338 the essential packages are present and working */
339 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
340 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
341 Cache
.MarkInstall(I
, true, 0, false);
343 /* We do it again over all previously installed packages to force
344 conflict resolution on them all. */
345 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
346 if (I
->CurrentVer
!= 0)
347 Cache
.MarkInstall(I
, false, 0, false);
349 pkgProblemResolver
Fix(&Cache
);
351 // Hold back held packages.
352 if (_config
->FindB("APT::Ignore-Hold",false) == false)
354 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
356 if (I
->SelectedState
== pkgCache::State::Hold
)
359 Cache
.MarkKeep(I
, false, false);
364 return Fix
.Resolve();
367 // AllUpgrade - Upgrade as many packages as possible /*{{{*/
368 // ---------------------------------------------------------------------
369 /* Right now the system must be consistent before this can be called.
370 It also will not change packages marked for install, it only tries
371 to install packages not marked for install */
372 bool pkgAllUpgrade(pkgDepCache
&Cache
)
374 pkgDepCache::ActionGroup
group(Cache
);
376 pkgProblemResolver
Fix(&Cache
);
378 if (Cache
.BrokenCount() != 0)
381 // Upgrade all installed packages
382 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
384 if (Cache
[I
].Install() == true)
387 if (_config
->FindB("APT::Ignore-Hold",false) == false)
388 if (I
->SelectedState
== pkgCache::State::Hold
)
391 if (I
->CurrentVer
!= 0 && Cache
[I
].InstallVer
!= 0)
392 Cache
.MarkInstall(I
, false, 0, false);
395 return Fix
.ResolveByKeep();
398 // MinimizeUpgrade - Minimizes the set of packages to be upgraded /*{{{*/
399 // ---------------------------------------------------------------------
400 /* This simply goes over the entire set of packages and tries to keep
401 each package marked for upgrade. If a conflict is generated then
402 the package is restored. */
403 bool pkgMinimizeUpgrade(pkgDepCache
&Cache
)
405 pkgDepCache::ActionGroup
group(Cache
);
407 if (Cache
.BrokenCount() != 0)
410 // We loop for 10 tries to get the minimal set size.
412 unsigned int Count
= 0;
416 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
419 if (Cache
[I
].Upgrade() == false || Cache
[I
].NewInstall() == true)
422 // Keep it and see if that is OK
423 Cache
.MarkKeep(I
, false, false);
424 if (Cache
.BrokenCount() != 0)
425 Cache
.MarkInstall(I
, false, 0, false);
428 // If keep didnt actually do anything then there was no change..
429 if (Cache
[I
].Upgrade() == false)
435 while (Change
== true && Count
< 10);
437 if (Cache
.BrokenCount() != 0)
438 return _error
->Error("Internal Error in pkgMinimizeUpgrade");
444 // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
445 // ---------------------------------------------------------------------
447 pkgProblemResolver::pkgProblemResolver(pkgDepCache
*pCache
) : Cache(*pCache
)
450 unsigned long Size
= Cache
.Head().PackageCount
;
451 Scores
= new signed short[Size
];
452 Flags
= new unsigned char[Size
];
453 memset(Flags
,0,sizeof(*Flags
)*Size
);
455 // Set debug to true to see its decision logic
456 Debug
= _config
->FindB("Debug::pkgProblemResolver",false);
459 // ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/
460 // ---------------------------------------------------------------------
462 pkgProblemResolver::~pkgProblemResolver()
468 // ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
469 // ---------------------------------------------------------------------
471 int pkgProblemResolver::ScoreSort(const void *a
,const void *b
)
473 Package
const **A
= (Package
const **)a
;
474 Package
const **B
= (Package
const **)b
;
475 if (This
->Scores
[(*A
)->ID
] > This
->Scores
[(*B
)->ID
])
477 if (This
->Scores
[(*A
)->ID
] < This
->Scores
[(*B
)->ID
])
482 // ProblemResolver::MakeScores - Make the score table /*{{{*/
483 // ---------------------------------------------------------------------
485 void pkgProblemResolver::MakeScores()
487 unsigned long Size
= Cache
.Head().PackageCount
;
488 memset(Scores
,0,sizeof(*Scores
)*Size
);
490 // Generate the base scores for a package based on its properties
491 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
493 if (Cache
[I
].InstallVer
== 0)
496 signed short &Score
= Scores
[I
->ID
];
498 /* This is arbitary, it should be high enough to elevate an
499 essantial package above most other packages but low enough
500 to allow an obsolete essential packages to be removed by
501 a conflicts on a powerfull normal package (ie libc6) */
502 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
505 // We transform the priority
506 // Important Required Standard Optional Extra
507 signed short PrioMap
[] = {0,3,2,1,-1,-2};
508 if (Cache
[I
].InstVerIter(Cache
)->Priority
<= 5)
509 Score
+= PrioMap
[Cache
[I
].InstVerIter(Cache
)->Priority
];
511 /* This helps to fix oddball problems with conflicting packages
512 on the same level. We enhance the score of installed packages
513 if those are not obsolete
515 if (I
->CurrentVer
!= 0 && Cache
[I
].CandidateVerIter(Cache
).Downloadable())
519 // Now that we have the base scores we go and propogate dependencies
520 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
522 if (Cache
[I
].InstallVer
== 0)
525 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false; D
++)
527 if (D
->Type
== pkgCache::Dep::Depends
|| D
->Type
== pkgCache::Dep::PreDepends
)
528 Scores
[D
.TargetPkg()->ID
]++;
532 // Copy the scores to advoid additive looping
533 SPtrArray
<signed short> OldScores
= new signed short[Size
];
534 memcpy(OldScores
,Scores
,sizeof(*Scores
)*Size
);
536 /* Now we cause 1 level of dependency inheritance, that is we add the
537 score of the packages that depend on the target Package. This
538 fortifies high scoring packages */
539 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
541 if (Cache
[I
].InstallVer
== 0)
544 for (pkgCache::DepIterator D
= I
.RevDependsList(); D
.end() == false; D
++)
546 // Only do it for the install version
547 if ((pkgCache::Version
*)D
.ParentVer() != Cache
[D
.ParentPkg()].InstallVer
||
548 (D
->Type
!= pkgCache::Dep::Depends
&& D
->Type
!= pkgCache::Dep::PreDepends
))
551 Scores
[I
->ID
] += abs(OldScores
[D
.ParentPkg()->ID
]);
555 /* Now we propogate along provides. This makes the packages that
556 provide important packages extremely important */
557 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
559 for (pkgCache::PrvIterator P
= I
.ProvidesList(); P
.end() == false; P
++)
561 // Only do it once per package
562 if ((pkgCache::Version
*)P
.OwnerVer() != Cache
[P
.OwnerPkg()].InstallVer
)
564 Scores
[P
.OwnerPkg()->ID
] += abs(Scores
[I
->ID
] - OldScores
[I
->ID
]);
568 /* Protected things are pushed really high up. This number should put them
569 ahead of everything */
570 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
572 if ((Flags
[I
->ID
] & Protected
) != 0)
573 Scores
[I
->ID
] += 10000;
574 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
575 Scores
[I
->ID
] += 5000;
579 // ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
580 // ---------------------------------------------------------------------
581 /* This goes through and tries to reinstall packages to make this package
583 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg
)
585 pkgDepCache::ActionGroup
group(Cache
);
587 if ((Flags
[Pkg
->ID
] & Upgradable
) == 0 || Cache
[Pkg
].Upgradable() == false)
589 if ((Flags
[Pkg
->ID
] & Protected
) == Protected
)
592 Flags
[Pkg
->ID
] &= ~Upgradable
;
594 bool WasKept
= Cache
[Pkg
].Keep();
595 Cache
.MarkInstall(Pkg
, false, 0, false);
597 // This must be a virtual package or something like that.
598 if (Cache
[Pkg
].InstVerIter(Cache
).end() == true)
601 // Isolate the problem dependency
603 for (pkgCache::DepIterator D
= Cache
[Pkg
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
605 // Compute a single dependency element (glob or)
606 pkgCache::DepIterator Start
= D
;
607 pkgCache::DepIterator End
= D
;
608 unsigned char State
= 0;
609 for (bool LastOR
= true; D
.end() == false && LastOR
== true;)
612 LastOR
= (D
->CompareOp
& pkgCache::Dep::Or
) == pkgCache::Dep::Or
;
618 // We only worry about critical deps.
619 if (End
.IsCritical() != true)
622 // Iterate over all the members in the or group
626 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
629 // Do not change protected packages
630 PkgIterator P
= Start
.SmartTargetPkg();
631 if ((Flags
[P
->ID
] & Protected
) == Protected
)
634 clog
<< " Reinst Failed because of protected " << P
.Name() << endl
;
639 // Upgrade the package if the candidate version will fix the problem.
640 if ((Cache
[Start
] & pkgDepCache::DepCVer
) == pkgDepCache::DepCVer
)
642 if (DoUpgrade(P
) == false)
645 clog
<< " Reinst Failed because of " << P
.Name() << endl
;
656 /* We let the algorithm deal with conflicts on its next iteration,
657 it is much smarter than us */
658 if (Start
->Type
== pkgCache::Dep::Conflicts
||
659 Start
->Type
== pkgCache::Dep::DpkgBreaks
||
660 Start
->Type
== pkgCache::Dep::Obsoletes
)
664 clog
<< " Reinst Failed early because of " << Start
.TargetPkg().Name() << endl
;
677 // Undo our operations - it might be smart to undo everything this did..
681 Cache
.MarkKeep(Pkg
, false, false);
683 Cache
.MarkDelete(Pkg
);
688 clog
<< " Re-Instated " << Pkg
.Name() << endl
;
692 // ProblemResolver::Resolve - Run the resolution pass /*{{{*/
693 // ---------------------------------------------------------------------
694 /* This routines works by calculating a score for each package. The score
695 is derived by considering the package's priority and all reverse
696 dependents giving an integer that reflects the amount of breakage that
697 adjusting the package will inflict.
699 It goes from highest score to lowest and corrects all of the breaks by
700 keeping or removing the dependant packages. If that fails then it removes
701 the package itself and goes on. The routine should be able to intelligently
702 go from any broken state to a fixed state.
704 The BrokenFix flag enables a mode where the algorithm tries to
705 upgrade packages to advoid problems. */
706 bool pkgProblemResolver::Resolve(bool BrokenFix
)
708 pkgDepCache::ActionGroup
group(Cache
);
710 unsigned long Size
= Cache
.Head().PackageCount
;
712 // Record which packages are marked for install
717 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
719 if (Cache
[I
].Install() == true)
720 Flags
[I
->ID
] |= PreInstalled
;
723 if (Cache
[I
].InstBroken() == true && BrokenFix
== true)
725 Cache
.MarkInstall(I
, false, 0, false);
726 if (Cache
[I
].Install() == true)
730 Flags
[I
->ID
] &= ~PreInstalled
;
732 Flags
[I
->ID
] |= Upgradable
;
735 while (Again
== true);
738 clog
<< "Starting" << endl
;
742 /* We have to order the packages so that the broken fixing pass
743 operates from highest score to lowest. This prevents problems when
744 high score packages cause the removal of lower score packages that
745 would cause the removal of even lower score packages. */
746 SPtrArray
<pkgCache::Package
*> PList
= new pkgCache::Package
*[Size
];
747 pkgCache::Package
**PEnd
= PList
;
748 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
751 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
753 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
754 if (Scores[(*K)->ID] != 0)
756 pkgCache::PkgIterator Pkg(Cache,*K);
757 clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
758 ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
759 Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
763 clog
<< "Starting 2" << endl
;
765 /* Now consider all broken packages. For each broken package we either
766 remove the package or fix it's problem. We do this once, it should
767 not be possible for a loop to form (that is a < b < c and fixing b by
768 changing a breaks c) */
770 for (int Counter
= 0; Counter
!= 10 && Change
== true; Counter
++)
773 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
775 pkgCache::PkgIterator
I(Cache
,*K
);
777 /* We attempt to install this and see if any breaks result,
778 this takes care of some strange cases */
779 if (Cache
[I
].CandidateVer
!= Cache
[I
].InstallVer
&&
780 I
->CurrentVer
!= 0 && Cache
[I
].InstallVer
!= 0 &&
781 (Flags
[I
->ID
] & PreInstalled
) != 0 &&
782 (Flags
[I
->ID
] & Protected
) == 0 &&
783 (Flags
[I
->ID
] & ReInstateTried
) == 0)
786 clog
<< " Try to Re-Instate " << I
.Name() << endl
;
787 unsigned long OldBreaks
= Cache
.BrokenCount();
788 pkgCache::Version
*OldVer
= Cache
[I
].InstallVer
;
789 Flags
[I
->ID
] &= ReInstateTried
;
791 Cache
.MarkInstall(I
, false, 0, false);
792 if (Cache
[I
].InstBroken() == true ||
793 OldBreaks
< Cache
.BrokenCount())
798 Cache
.MarkKeep(I
, false, false);
802 clog
<< "Re-Instated " << I
.Name() << " (" << OldBreaks
<< " vs " << Cache
.BrokenCount() << ')' << endl
;
805 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
809 clog
<< "Investigating " << I
.Name() << endl
;
811 // Isolate the problem dependency
812 PackageKill KillList
[100];
813 PackageKill
*LEnd
= KillList
;
815 pkgCache::DepIterator Start
;
816 pkgCache::DepIterator End
;
817 PackageKill
*OldEnd
= LEnd
;
819 enum {OrRemove
,OrKeep
} OrOp
= OrRemove
;
820 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList();
821 D
.end() == false || InOr
== true;)
823 // Compute a single dependency element (glob or)
829 if (OldEnd
== LEnd
&& OrOp
== OrRemove
)
831 if ((Flags
[I
->ID
] & Protected
) != Protected
)
834 clog
<< " Or group remove for " << I
.Name() << endl
;
839 if (OldEnd
== LEnd
&& OrOp
== OrKeep
)
842 clog
<< " Or group keep for " << I
.Name() << endl
;
843 Cache
.MarkKeep(I
, false, false);
848 /* We do an extra loop (as above) to finalize the or group
853 if (Start
.end() == true)
856 // We only worry about critical deps.
857 if (End
.IsCritical() != true)
867 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
874 clog
<< "Package " << I
.Name() << " has broken dep on " << Start
.TargetPkg().Name() << endl
;
876 /* Look across the version list. If there are no possible
877 targets then we keep the package and bail. This is necessary
878 if a package has a dep on another package that cant be found */
879 SPtrArray
<pkgCache::Version
*> VList
= Start
.AllTargets();
880 if (*VList
== 0 && (Flags
[I
->ID
] & Protected
) != Protected
&&
881 Start
->Type
!= pkgCache::Dep::Conflicts
&&
882 Start
->Type
!= pkgCache::Dep::DpkgBreaks
&&
883 Start
->Type
!= pkgCache::Dep::Obsoletes
&&
884 Cache
[I
].NowBroken() == false)
888 /* No keep choice because the keep being OK could be the
889 result of another element in the OR group! */
894 Cache
.MarkKeep(I
, false, false);
899 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
901 pkgCache::VerIterator
Ver(Cache
,*V
);
902 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
905 clog
<< " Considering " << Pkg
.Name() << ' ' << (int)Scores
[Pkg
->ID
] <<
906 " as a solution to " << I
.Name() << ' ' << (int)Scores
[I
->ID
] << endl
;
908 /* Try to fix the package under consideration rather than
909 fiddle with the VList package */
910 if (Scores
[I
->ID
] <= Scores
[Pkg
->ID
] ||
911 ((Cache
[Start
] & pkgDepCache::DepNow
) == 0 &&
912 End
->Type
!= pkgCache::Dep::Conflicts
&&
913 End
->Type
!= pkgCache::Dep::DpkgBreaks
&&
914 End
->Type
!= pkgCache::Dep::Obsoletes
))
916 // Try a little harder to fix protected packages..
917 if ((Flags
[I
->ID
] & Protected
) == Protected
)
919 if (DoUpgrade(Pkg
) == true)
921 if (Scores
[Pkg
->ID
] > Scores
[I
->ID
])
922 Scores
[Pkg
->ID
] = Scores
[I
->ID
];
929 /* See if a keep will do, unless the package is protected,
930 then installing it will be necessary */
931 bool Installed
= Cache
[I
].Install();
932 Cache
.MarkKeep(I
, false, false);
933 if (Cache
[I
].InstBroken() == false)
935 // Unwind operation will be keep now
936 if (OrOp
== OrRemove
)
940 if (InOr
== true && Installed
== true)
941 Cache
.MarkInstall(I
, false, 0, false);
944 clog
<< " Holding Back " << I
.Name() << " rather than change " << Start
.TargetPkg().Name() << endl
;
948 if (BrokenFix
== false || DoUpgrade(I
) == false)
950 // Consider other options
954 clog
<< " Removing " << I
.Name() << " rather than change " << Start
.TargetPkg().Name() << endl
;
958 if (Scores
[Pkg
->ID
] > Scores
[I
->ID
])
959 Scores
[I
->ID
] = Scores
[Pkg
->ID
];
971 /* This is a conflicts, and the version we are looking
972 at is not the currently selected version of the
973 package, which means it is not necessary to
975 if (Cache
[Pkg
].InstallVer
!= Ver
&&
976 (Start
->Type
== pkgCache::Dep::Conflicts
||
977 Start
->Type
== pkgCache::Dep::Obsoletes
))
980 if (Start
->Type
== pkgCache::Dep::DpkgBreaks
)
982 /* Would it help if we upgraded? */
983 if (Cache
[End
] & pkgDepCache::DepGCVer
) {
985 clog
<< " Upgrading " << Pkg
.Name() << " due to Breaks field in " << I
.Name() << endl
;
986 Cache
.MarkInstall(Pkg
, false, 0, false);
990 clog
<< " Will not break " << Pkg
.Name() << " as stated in Breaks field in " << I
.Name() <<endl
;
991 Cache
.MarkKeep(I
, false, false);
995 // Skip adding to the kill list if it is protected
996 if ((Flags
[Pkg
->ID
] & Protected
) != 0)
1000 clog
<< " Added " << Pkg
.Name() << " to the remove list" << endl
;
1006 if (Start
->Type
!= pkgCache::Dep::Conflicts
&&
1007 Start
->Type
!= pkgCache::Dep::Obsoletes
)
1012 // Hm, nothing can possibly satisify this dep. Nuke it.
1013 if (VList
[0] == 0 &&
1014 Start
->Type
!= pkgCache::Dep::Conflicts
&&
1015 Start
->Type
!= pkgCache::Dep::DpkgBreaks
&&
1016 Start
->Type
!= pkgCache::Dep::Obsoletes
&&
1017 (Flags
[I
->ID
] & Protected
) != Protected
)
1019 bool Installed
= Cache
[I
].Install();
1021 if (Cache
[I
].InstBroken() == false)
1023 // Unwind operation will be keep now
1024 if (OrOp
== OrRemove
)
1028 if (InOr
== true && Installed
== true)
1029 Cache
.MarkInstall(I
, false, 0, false);
1032 clog
<< " Holding Back " << I
.Name() << " because I can't find " << Start
.TargetPkg().Name() << endl
;
1037 clog
<< " Removing " << I
.Name() << " because I can't find " << Start
.TargetPkg().Name() << endl
;
1039 Cache
.MarkDelete(I
);
1054 // Apply the kill list now
1055 if (Cache
[I
].InstallVer
!= 0)
1057 for (PackageKill
*J
= KillList
; J
!= LEnd
; J
++)
1060 if ((Cache
[J
->Dep
] & pkgDepCache::DepGNow
) == 0)
1062 if (J
->Dep
->Type
== pkgCache::Dep::Conflicts
||
1063 J
->Dep
->Type
== pkgCache::Dep::Obsoletes
)
1066 clog
<< " Fixing " << I
.Name() << " via remove of " << J
->Pkg
.Name() << endl
;
1067 Cache
.MarkDelete(J
->Pkg
);
1073 clog
<< " Fixing " << I
.Name() << " via keep of " << J
->Pkg
.Name() << endl
;
1074 Cache
.MarkKeep(J
->Pkg
, false, false);
1079 if (Scores
[I
->ID
] > Scores
[J
->Pkg
->ID
])
1080 Scores
[J
->Pkg
->ID
] = Scores
[I
->ID
];
1088 clog
<< "Done" << endl
;
1090 if (Cache
.BrokenCount() != 0)
1092 // See if this is the result of a hold
1093 pkgCache::PkgIterator I
= Cache
.PkgBegin();
1094 for (;I
.end() != true; I
++)
1096 if (Cache
[I
].InstBroken() == false)
1098 if ((Flags
[I
->ID
] & Protected
) != Protected
)
1099 return _error
->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1101 return _error
->Error(_("Unable to correct problems, you have held broken packages."));
1104 // set the auto-flags (mvo: I'm not sure if we _really_ need this, but
1106 pkgCache::PkgIterator I
= Cache
.PkgBegin();
1107 for (;I
.end() != true; I
++) {
1108 if (Cache
[I
].NewInstall() && !(Flags
[I
->ID
] & PreInstalled
)) {
1109 if(_config
->FindI("Debug::pkgAutoRemove",false)) {
1110 std::clog
<< "Resolve installed new pkg: " << I
.Name()
1111 << " (now marking it as auto)" << std::endl
;
1113 Cache
[I
].Flags
|= pkgCache::Flag::Auto
;
1121 // ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
1122 // ---------------------------------------------------------------------
1123 /* This is the work horse of the soft upgrade routine. It is very gental
1124 in that it does not install or remove any packages. It is assumed that the
1125 system was non-broken previously. */
1126 bool pkgProblemResolver::ResolveByKeep()
1128 pkgDepCache::ActionGroup
group(Cache
);
1130 unsigned long Size
= Cache
.Head().PackageCount
;
1133 clog
<< "Entering ResolveByKeep" << endl
;
1137 /* We have to order the packages so that the broken fixing pass
1138 operates from highest score to lowest. This prevents problems when
1139 high score packages cause the removal of lower score packages that
1140 would cause the removal of even lower score packages. */
1141 pkgCache::Package
**PList
= new pkgCache::Package
*[Size
];
1142 pkgCache::Package
**PEnd
= PList
;
1143 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
1146 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
1148 // Consider each broken package
1149 pkgCache::Package
**LastStop
= 0;
1150 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
1152 pkgCache::PkgIterator
I(Cache
,*K
);
1154 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
1157 /* Keep the package. If this works then great, otherwise we have
1158 to be significantly more agressive and manipulate its dependencies */
1159 if ((Flags
[I
->ID
] & Protected
) == 0)
1162 clog
<< "Keeping package " << I
.Name() << endl
;
1163 Cache
.MarkKeep(I
, false, false);
1164 if (Cache
[I
].InstBroken() == false)
1171 // Isolate the problem dependencies
1172 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
1176 D
.GlobOr(Start
,End
);
1178 // We only worry about critical deps.
1179 if (End
.IsCritical() != true)
1183 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
1186 /* Hm, the group is broken.. I suppose the best thing to do is to
1187 is to try every combination of keep/not-keep for the set, but thats
1188 slow, and this never happens, just be conservative and assume the
1189 list of ors is in preference and keep till it starts to work. */
1193 clog
<< "Package " << I
.Name() << " has broken dep on " << Start
.TargetPkg().Name() << endl
;
1195 // Look at all the possible provides on this package
1196 SPtrArray
<pkgCache::Version
*> VList
= Start
.AllTargets();
1197 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
1199 pkgCache::VerIterator
Ver(Cache
,*V
);
1200 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
1202 // It is not keepable
1203 if (Cache
[Pkg
].InstallVer
== 0 ||
1204 Pkg
->CurrentVer
== 0)
1207 if ((Flags
[I
->ID
] & Protected
) == 0)
1210 clog
<< " Keeping Package " << Pkg
.Name() << " due to dep" << endl
;
1211 Cache
.MarkKeep(Pkg
, false, false);
1214 if (Cache
[I
].InstBroken() == false)
1218 if (Cache
[I
].InstBroken() == false)
1226 if (Cache
[I
].InstBroken() == false)
1230 if (Cache
[I
].InstBroken() == true)
1235 return _error
->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I
.Name());
1243 // ProblemResolver::InstallProtect - Install all protected packages /*{{{*/
1244 // ---------------------------------------------------------------------
1245 /* This is used to make sure protected packages are installed */
1246 void pkgProblemResolver::InstallProtect()
1248 pkgDepCache::ActionGroup
group(Cache
);
1250 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
1252 if ((Flags
[I
->ID
] & Protected
) == Protected
)
1254 if ((Flags
[I
->ID
] & ToRemove
) == ToRemove
)
1255 Cache
.MarkDelete(I
);
1258 // preserver the information if the package was auto
1259 // or manual installed
1260 bool autoInst
= (Cache
[I
].Flags
& pkgCache::Flag::Auto
);
1261 Cache
.MarkInstall(I
, false, 0, !autoInst
);
1268 // PrioSortList - Sort a list of versions by priority /*{{{*/
1269 // ---------------------------------------------------------------------
1270 /* This is ment to be used in conjunction with AllTargets to get a list
1271 of versions ordered by preference. */
1272 static pkgCache
*PrioCache
;
1273 static int PrioComp(const void *A
,const void *B
)
1275 pkgCache::VerIterator
L(*PrioCache
,*(pkgCache::Version
**)A
);
1276 pkgCache::VerIterator
R(*PrioCache
,*(pkgCache::Version
**)B
);
1278 if ((L
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
&&
1279 (R
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) != pkgCache::Flag::Essential
)
1281 if ((L
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) != pkgCache::Flag::Essential
&&
1282 (R
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
1285 if (L
->Priority
!= R
->Priority
)
1286 return R
->Priority
- L
->Priority
;
1287 return strcmp(L
.ParentPkg().Name(),R
.ParentPkg().Name());
1289 void pkgPrioSortList(pkgCache
&Cache
,pkgCache::Version
**List
)
1291 unsigned long Count
= 0;
1293 for (pkgCache::Version
**I
= List
; *I
!= 0; I
++)
1295 qsort(List
,Count
,sizeof(*List
),PrioComp
);