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");
446 // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
447 // ---------------------------------------------------------------------
449 pkgProblemResolver::pkgProblemResolver(pkgDepCache
*pCache
) : Cache(*pCache
)
452 unsigned long Size
= Cache
.Head().PackageCount
;
453 Scores
= new signed short[Size
];
454 Flags
= new unsigned char[Size
];
455 memset(Flags
,0,sizeof(*Flags
)*Size
);
457 // Set debug to true to see its decision logic
458 Debug
= _config
->FindB("Debug::pkgProblemResolver",false);
461 // ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/
462 // ---------------------------------------------------------------------
464 pkgProblemResolver::~pkgProblemResolver()
470 // ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
471 // ---------------------------------------------------------------------
473 int pkgProblemResolver::ScoreSort(const void *a
,const void *b
)
475 Package
const **A
= (Package
const **)a
;
476 Package
const **B
= (Package
const **)b
;
477 if (This
->Scores
[(*A
)->ID
] > This
->Scores
[(*B
)->ID
])
479 if (This
->Scores
[(*A
)->ID
] < This
->Scores
[(*B
)->ID
])
484 // ProblemResolver::MakeScores - Make the score table /*{{{*/
485 // ---------------------------------------------------------------------
487 void pkgProblemResolver::MakeScores()
489 unsigned long Size
= Cache
.Head().PackageCount
;
490 memset(Scores
,0,sizeof(*Scores
)*Size
);
492 // Important Required Standard Optional Extra
493 signed short PrioMap
[] = {
495 _config
->FindI("pkgProblemResolver::Scores::Important",3),
496 _config
->FindI("pkgProblemResolver::Scores::Required",2),
497 _config
->FindI("pkgProblemResolver::Scores::Standard",1),
498 _config
->FindI("pkgProblemResolver::Scores::Optional",-1),
499 _config
->FindI("pkgProblemResolver::Scores::Extra",-2)
501 signed short PrioEssentials
= _config
->FindI("pkgProblemResolver::Scores::Essentials",100);
502 signed short PrioInstalledAndNotObsolete
= _config
->FindI("pkgProblemResolver::Scores::NotObsolete",1);
503 signed short PrioDepends
= _config
->FindI("pkgProblemResolver::Scores::Depends",1);
504 signed short AddProtected
= _config
->FindI("pkgProblemResolver::Scores::AddProtected",10000);
505 signed short AddEssential
= _config
->FindI("pkgProblemResolver::Scores::AddEssential",5000);
507 if (_config
->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
508 clog
<< "Settings used to calculate pkgProblemResolver::Scores::" << endl
509 << " Important => " << PrioMap
[1] << endl
510 << " Required => " << PrioMap
[2] << endl
511 << " Standard => " << PrioMap
[3] << endl
512 << " Optional => " << PrioMap
[4] << endl
513 << " Extra => " << PrioMap
[5] << endl
514 << " Essentials => " << PrioEssentials
<< endl
515 << " InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete
<< endl
516 << " Depends => " << PrioDepends
<< endl
517 << " AddProtected => " << AddProtected
<< endl
518 << " AddEssential => " << AddEssential
<< endl
;
520 // Generate the base scores for a package based on its properties
521 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
523 if (Cache
[I
].InstallVer
== 0)
526 signed short &Score
= Scores
[I
->ID
];
528 /* This is arbitrary, it should be high enough to elevate an
529 essantial package above most other packages but low enough
530 to allow an obsolete essential packages to be removed by
531 a conflicts on a powerfull normal package (ie libc6) */
532 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
533 Score
+= PrioEssentials
;
535 // We transform the priority
536 if (Cache
[I
].InstVerIter(Cache
)->Priority
<= 5)
537 Score
+= PrioMap
[Cache
[I
].InstVerIter(Cache
)->Priority
];
539 /* This helps to fix oddball problems with conflicting packages
540 on the same level. We enhance the score of installed packages
541 if those are not obsolete
543 if (I
->CurrentVer
!= 0 && Cache
[I
].CandidateVer
!= 0 && Cache
[I
].CandidateVerIter(Cache
).Downloadable())
544 Score
+= PrioInstalledAndNotObsolete
;
547 // Now that we have the base scores we go and propogate dependencies
548 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
550 if (Cache
[I
].InstallVer
== 0)
553 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false; D
++)
555 if (D
->Type
== pkgCache::Dep::Depends
|| D
->Type
== pkgCache::Dep::PreDepends
)
556 Scores
[D
.TargetPkg()->ID
]+= PrioDepends
;
560 // Copy the scores to advoid additive looping
561 SPtrArray
<signed short> OldScores
= new signed short[Size
];
562 memcpy(OldScores
,Scores
,sizeof(*Scores
)*Size
);
564 /* Now we cause 1 level of dependency inheritance, that is we add the
565 score of the packages that depend on the target Package. This
566 fortifies high scoring packages */
567 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
569 if (Cache
[I
].InstallVer
== 0)
572 for (pkgCache::DepIterator D
= I
.RevDependsList(); D
.end() == false; D
++)
574 // Only do it for the install version
575 if ((pkgCache::Version
*)D
.ParentVer() != Cache
[D
.ParentPkg()].InstallVer
||
576 (D
->Type
!= pkgCache::Dep::Depends
&& D
->Type
!= pkgCache::Dep::PreDepends
))
579 Scores
[I
->ID
] += abs(OldScores
[D
.ParentPkg()->ID
]);
583 /* Now we propogate along provides. This makes the packages that
584 provide important packages extremely important */
585 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
587 for (pkgCache::PrvIterator P
= I
.ProvidesList(); P
.end() == false; P
++)
589 // Only do it once per package
590 if ((pkgCache::Version
*)P
.OwnerVer() != Cache
[P
.OwnerPkg()].InstallVer
)
592 Scores
[P
.OwnerPkg()->ID
] += abs(Scores
[I
->ID
] - OldScores
[I
->ID
]);
596 /* Protected things are pushed really high up. This number should put them
597 ahead of everything */
598 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
600 if ((Flags
[I
->ID
] & Protected
) != 0)
601 Scores
[I
->ID
] += AddProtected
;
602 if ((I
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
603 Scores
[I
->ID
] += AddEssential
;
607 // ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
608 // ---------------------------------------------------------------------
609 /* This goes through and tries to reinstall packages to make this package
611 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg
)
613 pkgDepCache::ActionGroup
group(Cache
);
615 if ((Flags
[Pkg
->ID
] & Upgradable
) == 0 || Cache
[Pkg
].Upgradable() == false)
617 if ((Flags
[Pkg
->ID
] & Protected
) == Protected
)
620 Flags
[Pkg
->ID
] &= ~Upgradable
;
622 bool WasKept
= Cache
[Pkg
].Keep();
623 Cache
.MarkInstall(Pkg
, false, 0, false);
625 // This must be a virtual package or something like that.
626 if (Cache
[Pkg
].InstVerIter(Cache
).end() == true)
629 // Isolate the problem dependency
631 for (pkgCache::DepIterator D
= Cache
[Pkg
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
633 // Compute a single dependency element (glob or)
634 pkgCache::DepIterator Start
= D
;
635 pkgCache::DepIterator End
= D
;
636 unsigned char State
= 0;
637 for (bool LastOR
= true; D
.end() == false && LastOR
== true;)
640 LastOR
= (D
->CompareOp
& pkgCache::Dep::Or
) == pkgCache::Dep::Or
;
646 // We only worry about critical deps.
647 if (End
.IsCritical() != true)
650 // Iterate over all the members in the or group
654 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
657 // Do not change protected packages
658 PkgIterator P
= Start
.SmartTargetPkg();
659 if ((Flags
[P
->ID
] & Protected
) == Protected
)
662 clog
<< " Reinst Failed because of protected " << P
.Name() << endl
;
667 // Upgrade the package if the candidate version will fix the problem.
668 if ((Cache
[Start
] & pkgDepCache::DepCVer
) == pkgDepCache::DepCVer
)
670 if (DoUpgrade(P
) == false)
673 clog
<< " Reinst Failed because of " << P
.Name() << endl
;
684 /* We let the algorithm deal with conflicts on its next iteration,
685 it is much smarter than us */
686 if (Start
->Type
== pkgCache::Dep::Conflicts
||
687 Start
->Type
== pkgCache::Dep::DpkgBreaks
||
688 Start
->Type
== pkgCache::Dep::Obsoletes
)
692 clog
<< " Reinst Failed early because of " << Start
.TargetPkg().Name() << endl
;
705 // Undo our operations - it might be smart to undo everything this did..
709 Cache
.MarkKeep(Pkg
, false, false);
711 Cache
.MarkDelete(Pkg
);
716 clog
<< " Re-Instated " << Pkg
.Name() << endl
;
720 // ProblemResolver::Resolve - Run the resolution pass /*{{{*/
721 // ---------------------------------------------------------------------
722 /* This routines works by calculating a score for each package. The score
723 is derived by considering the package's priority and all reverse
724 dependents giving an integer that reflects the amount of breakage that
725 adjusting the package will inflict.
727 It goes from highest score to lowest and corrects all of the breaks by
728 keeping or removing the dependant packages. If that fails then it removes
729 the package itself and goes on. The routine should be able to intelligently
730 go from any broken state to a fixed state.
732 The BrokenFix flag enables a mode where the algorithm tries to
733 upgrade packages to advoid problems. */
734 bool pkgProblemResolver::Resolve(bool BrokenFix
)
736 pkgDepCache::ActionGroup
group(Cache
);
738 unsigned long Size
= Cache
.Head().PackageCount
;
740 // Record which packages are marked for install
745 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
747 if (Cache
[I
].Install() == true)
748 Flags
[I
->ID
] |= PreInstalled
;
751 if (Cache
[I
].InstBroken() == true && BrokenFix
== true)
753 Cache
.MarkInstall(I
, false, 0, false);
754 if (Cache
[I
].Install() == true)
758 Flags
[I
->ID
] &= ~PreInstalled
;
760 Flags
[I
->ID
] |= Upgradable
;
763 while (Again
== true);
766 clog
<< "Starting" << endl
;
770 /* We have to order the packages so that the broken fixing pass
771 operates from highest score to lowest. This prevents problems when
772 high score packages cause the removal of lower score packages that
773 would cause the removal of even lower score packages. */
774 SPtrArray
<pkgCache::Package
*> PList
= new pkgCache::Package
*[Size
];
775 pkgCache::Package
**PEnd
= PList
;
776 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
779 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
781 if (_config
->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
783 clog
<< "Show Scores" << endl
;
784 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
785 if (Scores
[(*K
)->ID
] != 0)
787 pkgCache::PkgIterator
Pkg(Cache
,*K
);
788 clog
<< Scores
[(*K
)->ID
] << ' ' << Pkg
<< std::endl
;
793 clog
<< "Starting 2" << endl
;
795 /* Now consider all broken packages. For each broken package we either
796 remove the package or fix it's problem. We do this once, it should
797 not be possible for a loop to form (that is a < b < c and fixing b by
798 changing a breaks c) */
800 for (int Counter
= 0; Counter
!= 10 && Change
== true; Counter
++)
803 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
805 pkgCache::PkgIterator
I(Cache
,*K
);
807 /* We attempt to install this and see if any breaks result,
808 this takes care of some strange cases */
809 if (Cache
[I
].CandidateVer
!= Cache
[I
].InstallVer
&&
810 I
->CurrentVer
!= 0 && Cache
[I
].InstallVer
!= 0 &&
811 (Flags
[I
->ID
] & PreInstalled
) != 0 &&
812 (Flags
[I
->ID
] & Protected
) == 0 &&
813 (Flags
[I
->ID
] & ReInstateTried
) == 0)
816 clog
<< " Try to Re-Instate " << I
.Name() << endl
;
817 unsigned long OldBreaks
= Cache
.BrokenCount();
818 pkgCache::Version
*OldVer
= Cache
[I
].InstallVer
;
819 Flags
[I
->ID
] &= ReInstateTried
;
821 Cache
.MarkInstall(I
, false, 0, false);
822 if (Cache
[I
].InstBroken() == true ||
823 OldBreaks
< Cache
.BrokenCount())
828 Cache
.MarkKeep(I
, false, false);
832 clog
<< "Re-Instated " << I
.Name() << " (" << OldBreaks
<< " vs " << Cache
.BrokenCount() << ')' << endl
;
835 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
839 clog
<< "Investigating " << I
.Name() << endl
;
841 // Isolate the problem dependency
842 PackageKill KillList
[100];
843 PackageKill
*LEnd
= KillList
;
845 pkgCache::DepIterator Start
;
846 pkgCache::DepIterator End
;
847 PackageKill
*OldEnd
= LEnd
;
849 enum {OrRemove
,OrKeep
} OrOp
= OrRemove
;
850 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList();
851 D
.end() == false || InOr
== true;)
853 // Compute a single dependency element (glob or)
859 if (OldEnd
== LEnd
&& OrOp
== OrRemove
)
861 if ((Flags
[I
->ID
] & Protected
) != Protected
)
864 clog
<< " Or group remove for " << I
.Name() << endl
;
869 if (OldEnd
== LEnd
&& OrOp
== OrKeep
)
872 clog
<< " Or group keep for " << I
.Name() << endl
;
873 Cache
.MarkKeep(I
, false, false);
878 /* We do an extra loop (as above) to finalize the or group
883 if (Start
.end() == true)
886 // We only worry about critical deps.
887 if (End
.IsCritical() != true)
896 // We only worry about critical deps.
897 if (Start
.IsCritical() != true)
902 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
909 clog
<< "Package " << I
.Name() << " has broken " << Start
.DepType() << " on " << Start
.TargetPkg().Name() << endl
;
911 /* Look across the version list. If there are no possible
912 targets then we keep the package and bail. This is necessary
913 if a package has a dep on another package that cant be found */
914 SPtrArray
<pkgCache::Version
*> VList
= Start
.AllTargets();
915 if (*VList
== 0 && (Flags
[I
->ID
] & Protected
) != Protected
&&
916 Start
->Type
!= pkgCache::Dep::Conflicts
&&
917 Start
->Type
!= pkgCache::Dep::DpkgBreaks
&&
918 Start
->Type
!= pkgCache::Dep::Obsoletes
&&
919 Cache
[I
].NowBroken() == false)
923 /* No keep choice because the keep being OK could be the
924 result of another element in the OR group! */
929 Cache
.MarkKeep(I
, false, false);
934 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
936 pkgCache::VerIterator
Ver(Cache
,*V
);
937 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
940 clog
<< " Considering " << Pkg
.Name() << ' ' << (int)Scores
[Pkg
->ID
] <<
941 " as a solution to " << I
.Name() << ' ' << (int)Scores
[I
->ID
] << endl
;
943 /* Try to fix the package under consideration rather than
944 fiddle with the VList package */
945 if (Scores
[I
->ID
] <= Scores
[Pkg
->ID
] ||
946 ((Cache
[Start
] & pkgDepCache::DepNow
) == 0 &&
947 End
->Type
!= pkgCache::Dep::Conflicts
&&
948 End
->Type
!= pkgCache::Dep::DpkgBreaks
&&
949 End
->Type
!= pkgCache::Dep::Obsoletes
))
951 // Try a little harder to fix protected packages..
952 if ((Flags
[I
->ID
] & Protected
) == Protected
)
954 if (DoUpgrade(Pkg
) == true)
956 if (Scores
[Pkg
->ID
] > Scores
[I
->ID
])
957 Scores
[Pkg
->ID
] = Scores
[I
->ID
];
964 /* See if a keep will do, unless the package is protected,
965 then installing it will be necessary */
966 bool Installed
= Cache
[I
].Install();
967 Cache
.MarkKeep(I
, false, false);
968 if (Cache
[I
].InstBroken() == false)
970 // Unwind operation will be keep now
971 if (OrOp
== OrRemove
)
975 if (InOr
== true && Installed
== true)
976 Cache
.MarkInstall(I
, false, 0, false);
979 clog
<< " Holding Back " << I
.Name() << " rather than change " << Start
.TargetPkg().Name() << endl
;
983 if (BrokenFix
== false || DoUpgrade(I
) == false)
985 // Consider other options
988 if (Cache
.IsAutoInstallOk(I
) == true)
991 clog
<< " Removing " << I
.Name() << " rather than change " << Start
.TargetPkg().Name() << endl
;
995 if (Scores
[Pkg
->ID
] > Scores
[I
->ID
])
996 Scores
[I
->ID
] = Scores
[Pkg
->ID
];
999 /* The dependency of the TargetPkg would be satisfiable with I but it is
1000 forbidden to install I automatical, so anything we can do is hold
1004 clog
<< " Hold back " << Start
.TargetPkg().Name() <<
1005 " rather than change denied AutoInstall " << I
.Name() << endl
;
1006 Cache
.MarkKeep(Start
.TargetPkg());
1018 /* This is a conflicts, and the version we are looking
1019 at is not the currently selected version of the
1020 package, which means it is not necessary to
1022 if (Cache
[Pkg
].InstallVer
!= Ver
&&
1023 (Start
->Type
== pkgCache::Dep::Conflicts
||
1024 Start
->Type
== pkgCache::Dep::Obsoletes
))
1027 if (Start
->Type
== pkgCache::Dep::DpkgBreaks
)
1029 // first, try upgradring the package, if that
1030 // does not help, the breaks goes onto the
1032 // FIXME: use DoUpgrade(Pkg) instead?
1033 if (Cache
[End
] & pkgDepCache::DepGCVer
)
1036 clog
<< " Upgrading " << Pkg
.Name() << " due to Breaks field in " << I
.Name() << endl
;
1037 Cache
.MarkInstall(Pkg
, false, 0, false);
1042 // Skip adding to the kill list if it is protected
1043 if ((Flags
[Pkg
->ID
] & Protected
) != 0)
1047 clog
<< " Added " << Pkg
.Name() << " to the remove list" << endl
;
1053 if (Start
->Type
!= pkgCache::Dep::Conflicts
&&
1054 Start
->Type
!= pkgCache::Dep::Obsoletes
)
1059 // Hm, nothing can possibly satisify this dep. Nuke it.
1060 if (VList
[0] == 0 &&
1061 Start
->Type
!= pkgCache::Dep::Conflicts
&&
1062 Start
->Type
!= pkgCache::Dep::DpkgBreaks
&&
1063 Start
->Type
!= pkgCache::Dep::Obsoletes
&&
1064 (Flags
[I
->ID
] & Protected
) != Protected
)
1066 bool Installed
= Cache
[I
].Install();
1068 if (Cache
[I
].InstBroken() == false)
1070 // Unwind operation will be keep now
1071 if (OrOp
== OrRemove
)
1075 if (InOr
== true && Installed
== true)
1076 Cache
.MarkInstall(I
, false, 0, false);
1079 clog
<< " Holding Back " << I
.Name() << " because I can't find " << Start
.TargetPkg().Name() << endl
;
1084 clog
<< " Removing " << I
.Name() << " because I can't find " << Start
.TargetPkg().Name() << endl
;
1086 Cache
.MarkDelete(I
);
1101 // Apply the kill list now
1102 if (Cache
[I
].InstallVer
!= 0)
1104 for (PackageKill
*J
= KillList
; J
!= LEnd
; J
++)
1107 if ((Cache
[J
->Dep
] & pkgDepCache::DepGNow
) == 0)
1109 if (J
->Dep
->Type
== pkgCache::Dep::Conflicts
||
1110 J
->Dep
->Type
== pkgCache::Dep::DpkgBreaks
||
1111 J
->Dep
->Type
== pkgCache::Dep::Obsoletes
)
1114 clog
<< " Fixing " << I
.Name() << " via remove of " << J
->Pkg
.Name() << endl
;
1115 Cache
.MarkDelete(J
->Pkg
);
1121 clog
<< " Fixing " << I
.Name() << " via keep of " << J
->Pkg
.Name() << endl
;
1122 Cache
.MarkKeep(J
->Pkg
, false, false);
1127 if (Scores
[I
->ID
] > Scores
[J
->Pkg
->ID
])
1128 Scores
[J
->Pkg
->ID
] = Scores
[I
->ID
];
1136 clog
<< "Done" << endl
;
1138 if (Cache
.BrokenCount() != 0)
1140 // See if this is the result of a hold
1141 pkgCache::PkgIterator I
= Cache
.PkgBegin();
1142 for (;I
.end() != true; I
++)
1144 if (Cache
[I
].InstBroken() == false)
1146 if ((Flags
[I
->ID
] & Protected
) != Protected
)
1147 return _error
->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1149 return _error
->Error(_("Unable to correct problems, you have held broken packages."));
1152 // set the auto-flags (mvo: I'm not sure if we _really_ need this, but
1154 pkgCache::PkgIterator I
= Cache
.PkgBegin();
1155 for (;I
.end() != true; I
++) {
1156 if (Cache
[I
].NewInstall() && !(Flags
[I
->ID
] & PreInstalled
)) {
1157 if(_config
->FindI("Debug::pkgAutoRemove",false)) {
1158 std::clog
<< "Resolve installed new pkg: " << I
.Name()
1159 << " (now marking it as auto)" << std::endl
;
1161 Cache
[I
].Flags
|= pkgCache::Flag::Auto
;
1169 // ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
1170 // ---------------------------------------------------------------------
1171 /* This is the work horse of the soft upgrade routine. It is very gental
1172 in that it does not install or remove any packages. It is assumed that the
1173 system was non-broken previously. */
1174 bool pkgProblemResolver::ResolveByKeep()
1176 pkgDepCache::ActionGroup
group(Cache
);
1178 unsigned long Size
= Cache
.Head().PackageCount
;
1182 /* We have to order the packages so that the broken fixing pass
1183 operates from highest score to lowest. This prevents problems when
1184 high score packages cause the removal of lower score packages that
1185 would cause the removal of even lower score packages. */
1186 pkgCache::Package
**PList
= new pkgCache::Package
*[Size
];
1187 pkgCache::Package
**PEnd
= PList
;
1188 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
1191 qsort(PList
,PEnd
- PList
,sizeof(*PList
),&ScoreSort
);
1193 if (_config
->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1195 clog
<< "Show Scores" << endl
;
1196 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
1197 if (Scores
[(*K
)->ID
] != 0)
1199 pkgCache::PkgIterator
Pkg(Cache
,*K
);
1200 clog
<< Scores
[(*K
)->ID
] << ' ' << Pkg
<< std::endl
;
1205 clog
<< "Entering ResolveByKeep" << endl
;
1207 // Consider each broken package
1208 pkgCache::Package
**LastStop
= 0;
1209 for (pkgCache::Package
**K
= PList
; K
!= PEnd
; K
++)
1211 pkgCache::PkgIterator
I(Cache
,*K
);
1213 if (Cache
[I
].InstallVer
== 0 || Cache
[I
].InstBroken() == false)
1216 /* Keep the package. If this works then great, otherwise we have
1217 to be significantly more agressive and manipulate its dependencies */
1218 if ((Flags
[I
->ID
] & Protected
) == 0)
1221 clog
<< "Keeping package " << I
.Name() << endl
;
1222 Cache
.MarkKeep(I
, false, false);
1223 if (Cache
[I
].InstBroken() == false)
1230 // Isolate the problem dependencies
1231 for (pkgCache::DepIterator D
= Cache
[I
].InstVerIter(Cache
).DependsList(); D
.end() == false;)
1235 D
.GlobOr(Start
,End
);
1237 // We only worry about critical deps.
1238 if (End
.IsCritical() != true)
1242 if ((Cache
[End
] & pkgDepCache::DepGInstall
) == pkgDepCache::DepGInstall
)
1245 /* Hm, the group is broken.. I suppose the best thing to do is to
1246 is to try every combination of keep/not-keep for the set, but thats
1247 slow, and this never happens, just be conservative and assume the
1248 list of ors is in preference and keep till it starts to work. */
1252 clog
<< "Package " << I
.Name() << " has broken " << Start
.DepType() << " on " << Start
.TargetPkg().Name() << endl
;
1254 // Look at all the possible provides on this package
1255 SPtrArray
<pkgCache::Version
*> VList
= Start
.AllTargets();
1256 for (pkgCache::Version
**V
= VList
; *V
!= 0; V
++)
1258 pkgCache::VerIterator
Ver(Cache
,*V
);
1259 pkgCache::PkgIterator Pkg
= Ver
.ParentPkg();
1261 // It is not keepable
1262 if (Cache
[Pkg
].InstallVer
== 0 ||
1263 Pkg
->CurrentVer
== 0)
1266 if ((Flags
[I
->ID
] & Protected
) == 0)
1269 clog
<< " Keeping Package " << Pkg
.Name() << " due to " << Start
.DepType() << endl
;
1270 Cache
.MarkKeep(Pkg
, false, false);
1273 if (Cache
[I
].InstBroken() == false)
1277 if (Cache
[I
].InstBroken() == false)
1285 if (Cache
[I
].InstBroken() == false)
1289 if (Cache
[I
].InstBroken() == true)
1294 return _error
->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I
.Name());
1302 // ProblemResolver::InstallProtect - Install all protected packages /*{{{*/
1303 // ---------------------------------------------------------------------
1304 /* This is used to make sure protected packages are installed */
1305 void pkgProblemResolver::InstallProtect()
1307 pkgDepCache::ActionGroup
group(Cache
);
1309 for (pkgCache::PkgIterator I
= Cache
.PkgBegin(); I
.end() == false; I
++)
1311 if ((Flags
[I
->ID
] & Protected
) == Protected
)
1313 if ((Flags
[I
->ID
] & ToRemove
) == ToRemove
)
1314 Cache
.MarkDelete(I
);
1317 // preserve the information whether the package was auto
1318 // or manually installed
1319 bool autoInst
= (Cache
[I
].Flags
& pkgCache::Flag::Auto
);
1320 Cache
.MarkInstall(I
, false, 0, !autoInst
);
1327 // PrioSortList - Sort a list of versions by priority /*{{{*/
1328 // ---------------------------------------------------------------------
1329 /* This is ment to be used in conjunction with AllTargets to get a list
1330 of versions ordered by preference. */
1331 static pkgCache
*PrioCache
;
1332 static int PrioComp(const void *A
,const void *B
)
1334 pkgCache::VerIterator
L(*PrioCache
,*(pkgCache::Version
**)A
);
1335 pkgCache::VerIterator
R(*PrioCache
,*(pkgCache::Version
**)B
);
1337 if ((L
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
&&
1338 (R
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) != pkgCache::Flag::Essential
)
1340 if ((L
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) != pkgCache::Flag::Essential
&&
1341 (R
.ParentPkg()->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
1344 if (L
->Priority
!= R
->Priority
)
1345 return R
->Priority
- L
->Priority
;
1346 return strcmp(L
.ParentPkg().Name(),R
.ParentPkg().Name());
1348 void pkgPrioSortList(pkgCache
&Cache
,pkgCache::Version
**List
)
1350 unsigned long Count
= 0;
1352 for (pkgCache::Version
**I
= List
; *I
!= 0; I
++)
1354 qsort(List
,Count
,sizeof(*List
),PrioComp
);
1358 // CacheFile::ListUpdate - update the cache files /*{{{*/
1359 // ---------------------------------------------------------------------
1360 /* This is a simple wrapper to update the cache. it will fetch stuff
1361 * from the network (or any other sources defined in sources.list)
1363 bool ListUpdate(pkgAcquireStatus
&Stat
,
1364 pkgSourceList
&List
,
1367 pkgAcquire::RunResult res
;
1368 pkgAcquire
Fetcher(&Stat
);
1370 // Populate it with the source selection
1371 if (List
.GetIndexes(&Fetcher
) == false)
1375 RunScripts("APT::Update::Pre-Invoke");
1379 res
= Fetcher
.Run(PulseInterval
);
1381 res
= Fetcher
.Run();
1383 if (res
== pkgAcquire::Failed
)
1386 bool Failed
= false;
1387 bool TransientNetworkFailure
= false;
1388 for (pkgAcquire::ItemIterator I
= Fetcher
.ItemsBegin();
1389 I
!= Fetcher
.ItemsEnd(); I
++)
1391 if ((*I
)->Status
== pkgAcquire::Item::StatDone
)
1396 ::URI
uri((*I
)->DescURI());
1398 uri
.Password
.clear();
1399 string descUri
= string(uri
);
1400 _error
->Warning(_("Failed to fetch %s %s\n"), descUri
.c_str(),
1401 (*I
)->ErrorText
.c_str());
1403 if ((*I
)->Status
== pkgAcquire::Item::StatTransientNetworkError
)
1405 TransientNetworkFailure
= true;
1412 // Clean out any old list files
1413 // Keep "APT::Get::List-Cleanup" name for compatibility, but
1414 // this is really a global option for the APT library now
1415 if (!TransientNetworkFailure
&& !Failed
&&
1416 (_config
->FindB("APT::Get::List-Cleanup",true) == true &&
1417 _config
->FindB("APT::List-Cleanup",true) == true))
1419 if (Fetcher
.Clean(_config
->FindDir("Dir::State::lists")) == false ||
1420 Fetcher
.Clean(_config
->FindDir("Dir::State::lists") + "partial/") == false)
1421 // something went wrong with the clean
1425 if (TransientNetworkFailure
== true)
1426 _error
->Warning(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1427 else if (Failed
== true)
1428 return _error
->Error(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1431 // Run the success scripts if all was fine
1432 if(!TransientNetworkFailure
&& !Failed
)
1433 RunScripts("APT::Update::Post-Invoke-Success");
1435 // Run the other scripts
1436 RunScripts("APT::Update::Post-Invoke");