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 /*{{{*/
17 #include <apt-pkg/algorithms.h>
18 #include <apt-pkg/error.h>
19 #include <apt-pkg/configuration.h>
20 #include <apt-pkg/version.h>
21 #include <apt-pkg/sptr.h>
22 #include <apt-pkg/acquire-item.h>
25 #include <sys/types.h>
32 pkgProblemResolver
*pkgProblemResolver::This
= 0;
34 // Simulate::Simulate - Constructor /*{{{*/
35 // ---------------------------------------------------------------------
36 /* The legacy translations here of input Pkg iterators is obsolete,
37 this is not necessary since the pkgCaches are fully shared now. */
38 pkgSimulate::pkgSimulate(pkgDepCache
*Cache
) : pkgPackageManager(Cache
),
40 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 case pkgCache::State::TriggersAwaited
:
262 case pkgCache::State::TriggersPending
:
263 if ((I
->CurrentVer
!= 0 && I
.CurrentVer().Downloadable() == true) ||
264 I
.State() != pkgCache::PkgIterator::NeedsUnpack
)
265 Cache
.MarkKeep(I
, false, false);
268 if (Cache
[I
].CandidateVer
!= 0 &&
269 Cache
[I
].CandidateVerIter(Cache
).Downloadable() == true)
270 Cache
.MarkInstall(I
, true, 0, false);
276 // This means removal failed
277 case pkgCache::State::HalfInstalled
:
282 if (I
->InstState
!= pkgCache::State::Ok
)
283 return _error
->Error("The package %s is not ok and I "
284 "don't know how to fix it!",I
.Name());
290 // FixBroken - Fix broken packages /*{{{*/
291 // ---------------------------------------------------------------------
292 /* This autoinstalls every broken package and then runs the problem resolver
294 bool pkgFixBroken(pkgDepCache
&Cache
)
296 pkgDepCache::ActionGroup
group(Cache
);
298 // Auto upgrade all broken packages
299 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
300 if (Cache
[I
].NowBroken() == true)
301 Cache
.MarkInstall(I
, true, 0, false);
303 /* Fix packages that are in a NeedArchive state but don't have a
304 downloadable install version */
305 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
307 if (I
.State() != pkgCache::PkgIterator::NeedsUnpack
||
308 Cache
[I
].Delete() == true)
311 if (Cache
[I
].InstVerIter(Cache
).Downloadable() == false)
314 Cache
.MarkInstall(I
, true, 0, false);
317 pkgProblemResolver
Fix(&Cache
);
318 return Fix
.Resolve(true);
321 // DistUpgrade - Distribution upgrade /*{{{*/
322 // ---------------------------------------------------------------------
323 /* This autoinstalls every package and then force installs every
324 pre-existing package. This creates the initial set of conditions which
325 most likely contain problems because too many things were installed.
327 The problem resolver is used to resolve the problems.
329 bool pkgDistUpgrade(pkgDepCache
&Cache
)
331 pkgDepCache::ActionGroup
group(Cache
);
333 /* Auto upgrade all installed packages, this provides the basis
334 for the installation */
335 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
336 if (I
->CurrentVer
!= 0)
337 Cache
.MarkInstall(I
, true, 0, false);
339 /* Now, auto upgrade all essential packages - this ensures that
340 the essential packages are present and working */
341 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
342 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
343 Cache
.MarkInstall(I
, true, 0, false);
345 /* We do it again over all previously installed packages to force
346 conflict resolution on them all. */
347 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
348 if (I
->CurrentVer
!= 0)
349 Cache
.MarkInstall(I
, false, 0, false);
351 pkgProblemResolver
Fix(&Cache
);
353 // Hold back held packages.
354 if (_config
->FindB("APT::Ignore-Hold",false) == false)
356 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
358 if (I
->SelectedState
== pkgCache::State::Hold
)
361 Cache
.MarkKeep(I
, false, false);
366 return Fix
.Resolve();
369 // AllUpgrade - Upgrade as many packages as possible /*{{{*/
370 // ---------------------------------------------------------------------
371 /* Right now the system must be consistent before this can be called.
372 It also will not change packages marked for install, it only tries
373 to install packages not marked for install */
374 bool pkgAllUpgrade(pkgDepCache
&Cache
)
376 pkgDepCache::ActionGroup
group(Cache
);
378 pkgProblemResolver
Fix(&Cache
);
380 if (Cache
.BrokenCount() != 0)
383 // Upgrade all installed packages
384 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
386 if (Cache
[I
].Install() == true)
389 if (_config
->FindB("APT::Ignore-Hold",false) == false)
390 if (I
->SelectedState
== pkgCache::State::Hold
)
393 if (I
->CurrentVer
!= 0 && Cache
[I
].InstallVer
!= 0)
394 Cache
.MarkInstall(I
, false, 0, false);
397 return Fix
.ResolveByKeep();
400 // MinimizeUpgrade - Minimizes the set of packages to be upgraded /*{{{*/
401 // ---------------------------------------------------------------------
402 /* This simply goes over the entire set of packages and tries to keep
403 each package marked for upgrade. If a conflict is generated then
404 the package is restored. */
405 bool pkgMinimizeUpgrade(pkgDepCache
&Cache
)
407 pkgDepCache::ActionGroup
group(Cache
);
409 if (Cache
.BrokenCount() != 0)
412 // We loop for 10 tries to get the minimal set size.
414 unsigned int Count
= 0;
418 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
421 if (Cache
[I
].Upgrade() == false || Cache
[I
].NewInstall() == true)
424 // Keep it and see if that is OK
425 Cache
.MarkKeep(I
, false, false);
426 if (Cache
.BrokenCount() != 0)
427 Cache
.MarkInstall(I
, false, 0, false);
430 // If keep didnt actually do anything then there was no change..
431 if (Cache
[I
].Upgrade() == false)
437 while (Change
== true && Count
< 10);
439 if (Cache
.BrokenCount() != 0)
440 return _error
->Error("Internal Error in pkgMinimizeUpgrade");
445 // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
446 // ---------------------------------------------------------------------
448 pkgProblemResolver::pkgProblemResolver(pkgDepCache
*pCache
) : Cache(*pCache
)
451 unsigned long Size
= Cache
.Head().PackageCount
;
452 Scores
= new signed short[Size
];
453 Flags
= new unsigned char[Size
];
454 memset(Flags
,0,sizeof(*Flags
)*Size
);
456 // Set debug to true to see its decision logic
457 Debug
= _config
->FindB("Debug::pkgProblemResolver",false);
460 // ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/
461 // ---------------------------------------------------------------------
463 pkgProblemResolver::~pkgProblemResolver()
469 // ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
470 // ---------------------------------------------------------------------
472 int pkgProblemResolver::ScoreSort(const void *a
,const void *b
)
474 Package
const **A
= (Package
const **)a
;
475 Package
const **B
= (Package
const **)b
;
476 if (This
->Scores
[(*A
)->ID
] > This
->Scores
[(*B
)->ID
])
478 if (This
->Scores
[(*A
)->ID
] < This
->Scores
[(*B
)->ID
])
483 // ProblemResolver::MakeScores - Make the score table /*{{{*/
484 // ---------------------------------------------------------------------
486 void pkgProblemResolver::MakeScores()
488 unsigned long Size
= Cache
.Head().PackageCount
;
489 memset(Scores
,0,sizeof(*Scores
)*Size
);
491 // Important Required Standard Optional Extra
492 signed short PrioMap
[] = {
494 _config
->FindI("pkgProblemResolver::Scores::Important",3),
495 _config
->FindI("pkgProblemResolver::Scores::Required",2),
496 _config
->FindI("pkgProblemResolver::Scores::Standard",1),
497 _config
->FindI("pkgProblemResolver::Scores::Optional",-1),
498 _config
->FindI("pkgProblemResolver::Scores::Extra",-2)
500 signed short PrioEssentials
= _config
->FindI("pkgProblemResolver::Scores::Essentials",100);
501 signed short PrioInstalledAndNotObsolete
= _config
->FindI("pkgProblemResolver::Scores::NotObsolete",1);
502 signed short PrioDepends
= _config
->FindI("pkgProblemResolver::Scores::Depends",1);
503 signed short AddProtected
= _config
->FindI("pkgProblemResolver::Scores::AddProtected",10000);
504 signed short AddEssential
= _config
->FindI("pkgProblemResolver::Scores::AddEssential",5000);
506 if (_config
->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
507 clog
<< "Settings used to calculate pkgProblemResolver::Scores::" << endl
508 << " Important => " << PrioMap
[1] << endl
509 << " Required => " << PrioMap
[2] << endl
510 << " Standard => " << PrioMap
[3] << endl
511 << " Optional => " << PrioMap
[4] << endl
512 << " Extra => " << PrioMap
[5] << endl
513 << " Essentials => " << PrioEssentials
<< endl
514 << " InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete
<< endl
515 << " Depends => " << PrioDepends
<< endl
516 << " AddProtected => " << AddProtected
<< endl
517 << " AddEssential => " << AddEssential
<< endl
;
519 // Generate the base scores for a package based on its properties
520 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
522 if (Cache
[I
].InstallVer
== 0)
525 signed short &Score
= Scores
[I
->ID
];
527 /* This is arbitrary, it should be high enough to elevate an
528 essantial package above most other packages but low enough
529 to allow an obsolete essential packages to be removed by
530 a conflicts on a powerfull normal package (ie libc6) */
531 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
532 Score
+= PrioEssentials
;
534 // We transform the priority
535 if (Cache
[I
].InstVerIter(Cache
)->Priority
<= 5)
536 Score
+= PrioMap
[Cache
[I
].InstVerIter(Cache
)->Priority
];
538 /* This helps to fix oddball problems with conflicting packages
539 on the same level. We enhance the score of installed packages
540 if those are not obsolete
542 if (I
->CurrentVer
!= 0 && Cache
[I
].CandidateVer
!= 0 && Cache
[I
].CandidateVerIter(Cache
).Downloadable())
543 Score
+= PrioInstalledAndNotObsolete
;
546 // Now that we have the base scores we go and propogate dependencies
547 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
549 if (Cache
[I
].InstallVer
== 0)
552 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false; D
++)
554 if (D
->Type
== pkgCache::Dep::Depends
|| D
->Type
== pkgCache::Dep::PreDepends
)
555 Scores
[D
.TargetPkg()->ID
]+= PrioDepends
;
559 // Copy the scores to advoid additive looping
560 SPtrArray
<signed short> OldScores
= new signed short[Size
];
561 memcpy(OldScores
,Scores
,sizeof(*Scores
)*Size
);
563 /* Now we cause 1 level of dependency inheritance, that is we add the
564 score of the packages that depend on the target Package. This
565 fortifies high scoring packages */
566 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
568 if (Cache
[I
].InstallVer
== 0)
571 for (pkgCache::DepIterator D
= I
.RevDependsList(); D
.end() == false; D
++)
573 // Only do it for the install version
574 if ((pkgCache::Version
*)D
.ParentVer() != Cache
[D
.ParentPkg()].InstallVer
||
575 (D
->Type
!= pkgCache::Dep::Depends
&& D
->Type
!= pkgCache::Dep::PreDepends
))
578 Scores
[I
->ID
] += abs(OldScores
[D
.ParentPkg()->ID
]);
582 /* Now we propogate along provides. This makes the packages that
583 provide important packages extremely important */
584 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
586 for (pkgCache::PrvIterator P
= I
.ProvidesList(); P
.end() == false; P
++)
588 // Only do it once per package
589 if ((pkgCache::Version
*)P
.OwnerVer() != Cache
[P
.OwnerPkg()].InstallVer
)
591 Scores
[P
.OwnerPkg()->ID
] += abs(Scores
[I
->ID
] - OldScores
[I
->ID
]);
595 /* Protected things are pushed really high up. This number should put them
596 ahead of everything */
597 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
599 if ((Flags
[I
->ID
] & Protected
) != 0)
600 Scores
[I
->ID
] += AddProtected
;
601 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
602 Scores
[I
->ID
] += AddEssential
;
606 // ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
607 // ---------------------------------------------------------------------
608 /* This goes through and tries to reinstall packages to make this package
610 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg
)
612 pkgDepCache::ActionGroup
group(Cache
);
614 if ((Flags
[Pkg
->ID
] & Upgradable
) == 0 || Cache
[Pkg
].Upgradable() == false)
616 if ((Flags
[Pkg
->ID
] & Protected
) == Protected
)
619 Flags
[Pkg
->ID
] &= ~Upgradable
;
621 bool WasKept
= Cache
[Pkg
].Keep();
622 Cache
.MarkInstall(Pkg
, false, 0, false);
624 // This must be a virtual package or something like that.
625 if (Cache
[Pkg
].InstVerIter(Cache
).end() == true)
628 // Isolate the problem dependency
630 for (pkgCache::DepIterator D
= Cache
[Pkg
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
632 // Compute a single dependency element (glob or)
633 pkgCache::DepIterator Start
= D
;
634 pkgCache::DepIterator End
= D
;
635 unsigned char State
= 0;
636 for (bool LastOR
= true; D
.end() == false && LastOR
== true;)
639 LastOR
= (D
->CompareOp
& pkgCache::Dep::Or
) == pkgCache::Dep::Or
;
645 // We only worry about critical deps.
646 if (End
.IsCritical() != true)
649 // Iterate over all the members in the or group
653 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
656 // Do not change protected packages
657 PkgIterator P
= Start
.SmartTargetPkg();
658 if ((Flags
[P
->ID
] & Protected
) == Protected
)
661 clog
<< " Reinst Failed because of protected " << P
.Name() << endl
;
666 // Upgrade the package if the candidate version will fix the problem.
667 if ((Cache
[Start
] & pkgDepCache::DepCVer
) == pkgDepCache::DepCVer
)
669 if (DoUpgrade(P
) == false)
672 clog
<< " Reinst Failed because of " << P
.Name() << endl
;
683 /* We let the algorithm deal with conflicts on its next iteration,
684 it is much smarter than us */
685 if (Start
->Type
== pkgCache::Dep::Conflicts
||
686 Start
->Type
== pkgCache::Dep::DpkgBreaks
||
687 Start
->Type
== pkgCache::Dep::Obsoletes
)
691 clog
<< " Reinst Failed early because of " << Start
.TargetPkg().Name() << endl
;
704 // Undo our operations - it might be smart to undo everything this did..
708 Cache
.MarkKeep(Pkg
, false, false);
710 Cache
.MarkDelete(Pkg
);
715 clog
<< " Re-Instated " << Pkg
.Name() << endl
;
719 // ProblemResolver::Resolve - Run the resolution pass /*{{{*/
720 // ---------------------------------------------------------------------
721 /* This routines works by calculating a score for each package. The score
722 is derived by considering the package's priority and all reverse
723 dependents giving an integer that reflects the amount of breakage that
724 adjusting the package will inflict.
726 It goes from highest score to lowest and corrects all of the breaks by
727 keeping or removing the dependant packages. If that fails then it removes
728 the package itself and goes on. The routine should be able to intelligently
729 go from any broken state to a fixed state.
731 The BrokenFix flag enables a mode where the algorithm tries to
732 upgrade packages to advoid problems. */
733 bool pkgProblemResolver::Resolve(bool BrokenFix
)
735 pkgDepCache::ActionGroup
group(Cache
);
737 unsigned long Size
= Cache
.Head().PackageCount
;
739 // Record which packages are marked for install
744 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
746 if (Cache
[I
].Install() == true)
747 Flags
[I
->ID
] |= PreInstalled
;
750 if (Cache
[I
].InstBroken() == true && BrokenFix
== true)
752 Cache
.MarkInstall(I
, false, 0, false);
753 if (Cache
[I
].Install() == true)
757 Flags
[I
->ID
] &= ~PreInstalled
;
759 Flags
[I
->ID
] |= Upgradable
;
762 while (Again
== true);
765 clog
<< "Starting" << endl
;
769 /* We have to order the packages so that the broken fixing pass
770 operates from highest score to lowest. This prevents problems when
771 high score packages cause the removal of lower score packages that
772 would cause the removal of even lower score packages. */
773 SPtrArray
<pkgCache::Package
*> PList
= new pkgCache::Package
*[Size
];
774 pkgCache::Package
**PEnd
= PList
;
775 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
778 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
780 if (_config
->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
782 clog
<< "Show Scores" << endl
;
783 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
784 if (Scores
[(*K
)->ID
] != 0)
786 pkgCache::PkgIterator
Pkg(Cache
,*K
);
787 clog
<< Scores
[(*K
)->ID
] << ' ' << Pkg
<< std::endl
;
792 clog
<< "Starting 2" << endl
;
794 /* Now consider all broken packages. For each broken package we either
795 remove the package or fix it's problem. We do this once, it should
796 not be possible for a loop to form (that is a < b < c and fixing b by
797 changing a breaks c) */
799 for (int Counter
= 0; Counter
!= 10 && Change
== true; Counter
++)
802 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
804 pkgCache::PkgIterator
I(Cache
,*K
);
806 /* We attempt to install this and see if any breaks result,
807 this takes care of some strange cases */
808 if (Cache
[I
].CandidateVer
!= Cache
[I
].InstallVer
&&
809 I
->CurrentVer
!= 0 && Cache
[I
].InstallVer
!= 0 &&
810 (Flags
[I
->ID
] & PreInstalled
) != 0 &&
811 (Flags
[I
->ID
] & Protected
) == 0 &&
812 (Flags
[I
->ID
] & ReInstateTried
) == 0)
815 clog
<< " Try to Re-Instate " << I
.Name() << endl
;
816 unsigned long OldBreaks
= Cache
.BrokenCount();
817 pkgCache::Version
*OldVer
= Cache
[I
].InstallVer
;
818 Flags
[I
->ID
] &= ReInstateTried
;
820 Cache
.MarkInstall(I
, false, 0, false);
821 if (Cache
[I
].InstBroken() == true ||
822 OldBreaks
< Cache
.BrokenCount())
827 Cache
.MarkKeep(I
, false, false);
831 clog
<< "Re-Instated " << I
.Name() << " (" << OldBreaks
<< " vs " << Cache
.BrokenCount() << ')' << endl
;
834 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
838 clog
<< "Investigating " << I
.Name() << endl
;
840 // Isolate the problem dependency
841 PackageKill KillList
[100];
842 PackageKill
*LEnd
= KillList
;
844 pkgCache::DepIterator Start
;
845 pkgCache::DepIterator End
;
846 PackageKill
*OldEnd
= LEnd
;
848 enum {OrRemove
,OrKeep
} OrOp
= OrRemove
;
849 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList();
850 D
.end() == false || InOr
== true;)
852 // Compute a single dependency element (glob or)
858 if (OldEnd
== LEnd
&& OrOp
== OrRemove
)
860 if ((Flags
[I
->ID
] & Protected
) != Protected
)
863 clog
<< " Or group remove for " << I
.Name() << endl
;
868 if (OldEnd
== LEnd
&& OrOp
== OrKeep
)
871 clog
<< " Or group keep for " << I
.Name() << endl
;
872 Cache
.MarkKeep(I
, false, false);
877 /* We do an extra loop (as above) to finalize the or group
882 if (Start
.end() == true)
885 // We only worry about critical deps.
886 if (End
.IsCritical() != true)
895 // We only worry about critical deps.
896 if (Start
.IsCritical() != true)
901 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
908 clog
<< "Package " << I
.Name() << " has broken " << Start
.DepType() << " on " << Start
.TargetPkg().Name() << endl
;
910 /* Look across the version list. If there are no possible
911 targets then we keep the package and bail. This is necessary
912 if a package has a dep on another package that cant be found */
913 SPtrArray
<pkgCache::Version
*> VList
= Start
.AllTargets();
914 if (*VList
== 0 && (Flags
[I
->ID
] & Protected
) != Protected
&&
915 Start
->Type
!= pkgCache::Dep::Conflicts
&&
916 Start
->Type
!= pkgCache::Dep::DpkgBreaks
&&
917 Start
->Type
!= pkgCache::Dep::Obsoletes
&&
918 Cache
[I
].NowBroken() == false)
922 /* No keep choice because the keep being OK could be the
923 result of another element in the OR group! */
928 Cache
.MarkKeep(I
, false, false);
933 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
935 pkgCache::VerIterator
Ver(Cache
,*V
);
936 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
939 clog
<< " Considering " << Pkg
.Name() << ' ' << (int)Scores
[Pkg
->ID
] <<
940 " as a solution to " << I
.Name() << ' ' << (int)Scores
[I
->ID
] << endl
;
942 /* Try to fix the package under consideration rather than
943 fiddle with the VList package */
944 if (Scores
[I
->ID
] <= Scores
[Pkg
->ID
] ||
945 ((Cache
[Start
] & pkgDepCache::DepNow
) == 0 &&
946 End
->Type
!= pkgCache::Dep::Conflicts
&&
947 End
->Type
!= pkgCache::Dep::DpkgBreaks
&&
948 End
->Type
!= pkgCache::Dep::Obsoletes
))
950 // Try a little harder to fix protected packages..
951 if ((Flags
[I
->ID
] & Protected
) == Protected
)
953 if (DoUpgrade(Pkg
) == true)
955 if (Scores
[Pkg
->ID
] > Scores
[I
->ID
])
956 Scores
[Pkg
->ID
] = Scores
[I
->ID
];
963 /* See if a keep will do, unless the package is protected,
964 then installing it will be necessary */
965 bool Installed
= Cache
[I
].Install();
966 Cache
.MarkKeep(I
, false, false);
967 if (Cache
[I
].InstBroken() == false)
969 // Unwind operation will be keep now
970 if (OrOp
== OrRemove
)
974 if (InOr
== true && Installed
== true)
975 Cache
.MarkInstall(I
, false, 0, false);
978 clog
<< " Holding Back " << I
.Name() << " rather than change " << Start
.TargetPkg().Name() << endl
;
982 if (BrokenFix
== false || DoUpgrade(I
) == false)
984 // Consider other options
988 clog
<< " Removing " << I
.Name() << " rather than change " << Start
.TargetPkg().Name() << endl
;
990 if (Counter
> 1 && Scores
[Pkg
->ID
] > Scores
[I
->ID
])
991 Scores
[I
->ID
] = Scores
[Pkg
->ID
];
1002 /* This is a conflicts, and the version we are looking
1003 at is not the currently selected version of the
1004 package, which means it is not necessary to
1006 if (Cache
[Pkg
].InstallVer
!= Ver
&&
1007 (Start
->Type
== pkgCache::Dep::Conflicts
||
1008 Start
->Type
== pkgCache::Dep::Obsoletes
))
1011 if (Start
->Type
== pkgCache::Dep::DpkgBreaks
)
1013 // first, try upgradring the package, if that
1014 // does not help, the breaks goes onto the
1016 // FIXME: use DoUpgrade(Pkg) instead?
1017 if (Cache
[End
] & pkgDepCache::DepGCVer
)
1020 clog
<< " Upgrading " << Pkg
.Name() << " due to Breaks field in " << I
.Name() << endl
;
1021 Cache
.MarkInstall(Pkg
, false, 0, false);
1026 // Skip adding to the kill list if it is protected
1027 if ((Flags
[Pkg
->ID
] & Protected
) != 0)
1031 clog
<< " Added " << Pkg
.Name() << " to the remove list" << endl
;
1037 if (Start
->Type
!= pkgCache::Dep::Conflicts
&&
1038 Start
->Type
!= pkgCache::Dep::Obsoletes
)
1043 // Hm, nothing can possibly satisify this dep. Nuke it.
1044 if (VList
[0] == 0 &&
1045 Start
->Type
!= pkgCache::Dep::Conflicts
&&
1046 Start
->Type
!= pkgCache::Dep::DpkgBreaks
&&
1047 Start
->Type
!= pkgCache::Dep::Obsoletes
&&
1048 (Flags
[I
->ID
] & Protected
) != Protected
)
1050 bool Installed
= Cache
[I
].Install();
1052 if (Cache
[I
].InstBroken() == false)
1054 // Unwind operation will be keep now
1055 if (OrOp
== OrRemove
)
1059 if (InOr
== true && Installed
== true)
1060 Cache
.MarkInstall(I
, false, 0, false);
1063 clog
<< " Holding Back " << I
.Name() << " because I can't find " << Start
.TargetPkg().Name() << endl
;
1068 clog
<< " Removing " << I
.Name() << " because I can't find " << Start
.TargetPkg().Name() << endl
;
1070 Cache
.MarkDelete(I
);
1085 // Apply the kill list now
1086 if (Cache
[I
].InstallVer
!= 0)
1088 for (PackageKill
*J
= KillList
; J
!= LEnd
; J
++)
1091 if ((Cache
[J
->Dep
] & pkgDepCache::DepGNow
) == 0)
1093 if (J
->Dep
->Type
== pkgCache::Dep::Conflicts
||
1094 J
->Dep
->Type
== pkgCache::Dep::DpkgBreaks
||
1095 J
->Dep
->Type
== pkgCache::Dep::Obsoletes
)
1098 clog
<< " Fixing " << I
.Name() << " via remove of " << J
->Pkg
.Name() << endl
;
1099 Cache
.MarkDelete(J
->Pkg
);
1105 clog
<< " Fixing " << I
.Name() << " via keep of " << J
->Pkg
.Name() << endl
;
1106 Cache
.MarkKeep(J
->Pkg
, false, false);
1111 if (Scores
[I
->ID
] > Scores
[J
->Pkg
->ID
])
1112 Scores
[J
->Pkg
->ID
] = Scores
[I
->ID
];
1120 clog
<< "Done" << endl
;
1122 if (Cache
.BrokenCount() != 0)
1124 // See if this is the result of a hold
1125 pkgCache::PkgIterator I
= Cache
.PkgBegin();
1126 for (;I
.end() != true; I
++)
1128 if (Cache
[I
].InstBroken() == false)
1130 if ((Flags
[I
->ID
] & Protected
) != Protected
)
1131 return _error
->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1133 return _error
->Error(_("Unable to correct problems, you have held broken packages."));
1136 // set the auto-flags (mvo: I'm not sure if we _really_ need this, but
1138 pkgCache::PkgIterator I
= Cache
.PkgBegin();
1139 for (;I
.end() != true; I
++) {
1140 if (Cache
[I
].NewInstall() && !(Flags
[I
->ID
] & PreInstalled
)) {
1141 if(_config
->FindI("Debug::pkgAutoRemove",false)) {
1142 std::clog
<< "Resolve installed new pkg: " << I
.Name()
1143 << " (now marking it as auto)" << std::endl
;
1145 Cache
[I
].Flags
|= pkgCache::Flag::Auto
;
1153 // ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
1154 // ---------------------------------------------------------------------
1155 /* This is the work horse of the soft upgrade routine. It is very gental
1156 in that it does not install or remove any packages. It is assumed that the
1157 system was non-broken previously. */
1158 bool pkgProblemResolver::ResolveByKeep()
1160 pkgDepCache::ActionGroup
group(Cache
);
1162 unsigned long Size
= Cache
.Head().PackageCount
;
1166 /* We have to order the packages so that the broken fixing pass
1167 operates from highest score to lowest. This prevents problems when
1168 high score packages cause the removal of lower score packages that
1169 would cause the removal of even lower score packages. */
1170 pkgCache::Package
**PList
= new pkgCache::Package
*[Size
];
1171 pkgCache::Package
**PEnd
= PList
;
1172 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
1175 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
1177 if (_config
->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1179 clog
<< "Show Scores" << endl
;
1180 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
1181 if (Scores
[(*K
)->ID
] != 0)
1183 pkgCache::PkgIterator
Pkg(Cache
,*K
);
1184 clog
<< Scores
[(*K
)->ID
] << ' ' << Pkg
<< std::endl
;
1189 clog
<< "Entering ResolveByKeep" << endl
;
1191 // Consider each broken package
1192 pkgCache::Package
**LastStop
= 0;
1193 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
1195 pkgCache::PkgIterator
I(Cache
,*K
);
1197 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
1200 /* Keep the package. If this works then great, otherwise we have
1201 to be significantly more agressive and manipulate its dependencies */
1202 if ((Flags
[I
->ID
] & Protected
) == 0)
1205 clog
<< "Keeping package " << I
.Name() << endl
;
1206 Cache
.MarkKeep(I
, false, false);
1207 if (Cache
[I
].InstBroken() == false)
1214 // Isolate the problem dependencies
1215 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
1219 D
.GlobOr(Start
,End
);
1221 // We only worry about critical deps.
1222 if (End
.IsCritical() != true)
1226 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
1229 /* Hm, the group is broken.. I suppose the best thing to do is to
1230 is to try every combination of keep/not-keep for the set, but thats
1231 slow, and this never happens, just be conservative and assume the
1232 list of ors is in preference and keep till it starts to work. */
1236 clog
<< "Package " << I
.Name() << " has broken " << Start
.DepType() << " on " << Start
.TargetPkg().Name() << endl
;
1238 // Look at all the possible provides on this package
1239 SPtrArray
<pkgCache::Version
*> VList
= Start
.AllTargets();
1240 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
1242 pkgCache::VerIterator
Ver(Cache
,*V
);
1243 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
1245 // It is not keepable
1246 if (Cache
[Pkg
].InstallVer
== 0 ||
1247 Pkg
->CurrentVer
== 0)
1250 if ((Flags
[I
->ID
] & Protected
) == 0)
1253 clog
<< " Keeping Package " << Pkg
.Name() << " due to " << Start
.DepType() << endl
;
1254 Cache
.MarkKeep(Pkg
, false, false);
1257 if (Cache
[I
].InstBroken() == false)
1261 if (Cache
[I
].InstBroken() == false)
1269 if (Cache
[I
].InstBroken() == false)
1273 if (Cache
[I
].InstBroken() == true)
1278 return _error
->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I
.Name());
1286 // ProblemResolver::InstallProtect - Install all protected packages /*{{{*/
1287 // ---------------------------------------------------------------------
1288 /* This is used to make sure protected packages are installed */
1289 void pkgProblemResolver::InstallProtect()
1291 pkgDepCache::ActionGroup
group(Cache
);
1293 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
1295 if ((Flags
[I
->ID
] & Protected
) == Protected
)
1297 if ((Flags
[I
->ID
] & ToRemove
) == ToRemove
)
1298 Cache
.MarkDelete(I
);
1301 // preserve the information whether the package was auto
1302 // or manually installed
1303 bool autoInst
= (Cache
[I
].Flags
& pkgCache::Flag::Auto
);
1304 Cache
.MarkInstall(I
, false, 0, !autoInst
);
1310 // PrioSortList - Sort a list of versions by priority /*{{{*/
1311 // ---------------------------------------------------------------------
1312 /* This is ment to be used in conjunction with AllTargets to get a list
1313 of versions ordered by preference. */
1314 static pkgCache
*PrioCache
;
1315 static int PrioComp(const void *A
,const void *B
)
1317 pkgCache::VerIterator
L(*PrioCache
,*(pkgCache::Version
**)A
);
1318 pkgCache::VerIterator
R(*PrioCache
,*(pkgCache::Version
**)B
);
1320 if ((L
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
&&
1321 (R
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) != pkgCache::Flag::Essential
)
1323 if ((L
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) != pkgCache::Flag::Essential
&&
1324 (R
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
1327 if (L
->Priority
!= R
->Priority
)
1328 return R
->Priority
- L
->Priority
;
1329 return strcmp(L
.ParentPkg().Name(),R
.ParentPkg().Name());
1331 void pkgPrioSortList(pkgCache
&Cache
,pkgCache::Version
**List
)
1333 unsigned long Count
= 0;
1335 for (pkgCache::Version
**I
= List
; *I
!= 0; I
++)
1337 qsort(List
,Count
,sizeof(*List
),PrioComp
);
1340 // CacheFile::ListUpdate - update the cache files /*{{{*/
1341 // ---------------------------------------------------------------------
1342 /* This is a simple wrapper to update the cache. it will fetch stuff
1343 * from the network (or any other sources defined in sources.list)
1345 bool ListUpdate(pkgAcquireStatus
&Stat
,
1346 pkgSourceList
&List
,
1349 pkgAcquire::RunResult res
;
1350 pkgAcquire
Fetcher(&Stat
);
1352 // Populate it with the source selection
1353 if (List
.GetIndexes(&Fetcher
) == false)
1357 RunScripts("APT::Update::Pre-Invoke");
1361 res
= Fetcher
.Run(PulseInterval
);
1363 res
= Fetcher
.Run();
1365 if (res
== pkgAcquire::Failed
)
1368 bool Failed
= false;
1369 bool TransientNetworkFailure
= false;
1370 for (pkgAcquire::ItemIterator I
= Fetcher
.ItemsBegin();
1371 I
!= Fetcher
.ItemsEnd(); I
++)
1373 if ((*I
)->Status
== pkgAcquire::Item::StatDone
)
1378 ::URI
uri((*I
)->DescURI());
1380 uri
.Password
.clear();
1381 string descUri
= string(uri
);
1382 _error
->Warning(_("Failed to fetch %s %s\n"), descUri
.c_str(),
1383 (*I
)->ErrorText
.c_str());
1385 if ((*I
)->Status
== pkgAcquire::Item::StatTransientNetworkError
)
1387 TransientNetworkFailure
= true;
1394 // Clean out any old list files
1395 // Keep "APT::Get::List-Cleanup" name for compatibility, but
1396 // this is really a global option for the APT library now
1397 if (!TransientNetworkFailure
&& !Failed
&&
1398 (_config
->FindB("APT::Get::List-Cleanup",true) == true &&
1399 _config
->FindB("APT::List-Cleanup",true) == true))
1401 if (Fetcher
.Clean(_config
->FindDir("Dir::State::lists")) == false ||
1402 Fetcher
.Clean(_config
->FindDir("Dir::State::lists") + "partial/") == false)
1403 // something went wrong with the clean
1407 if (TransientNetworkFailure
== true)
1408 _error
->Warning(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1409 else if (Failed
== true)
1410 return _error
->Error(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1413 // Run the success scripts if all was fine
1414 if(!TransientNetworkFailure
&& !Failed
)
1415 RunScripts("APT::Update::Post-Invoke-Success");
1417 // Run the other scripts
1418 RunScripts("APT::Update::Post-Invoke");