// -*- mode: cpp; mode: fold -*-
// Description /*{{{*/
-// $Id: algorithms.cc,v 1.2 1998/07/12 01:25:59 jgg Exp $
+// $Id: algorithms.cc,v 1.44 2002/11/28 18:49:16 jgg Exp $
/* ######################################################################
Algorithms - A set of misc algorithms
+ The pkgProblemResolver class has become insanely complex and
+ very sophisticated, it handles every test case I have thrown at it
+ to my satisfaction. Understanding exactly why all the steps the class
+ does are required is difficult and changing though not very risky
+ may result in other cases not working.
+
##################################################################### */
/*}}}*/
// Include Files /*{{{*/
#ifdef __GNUG__
-#pragma implementation "pkglib/algorithms.h"
+#pragma implementation "apt-pkg/algorithms.h"
#endif
-#include <pkglib/algorithms.h>
-#include <pkglib/error.h>
-#include <iostream.h>
+#include <apt-pkg/algorithms.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-pkg/version.h>
+#include <apt-pkg/sptr.h>
+
+
+#include <apti18n.h>
+#include <sys/types.h>
+#include <regex.h>
+#include <iostream>
/*}}}*/
+using namespace std;
pkgProblemResolver *pkgProblemResolver::This = 0;
// Simulate::Simulate - Constructor /*{{{*/
// ---------------------------------------------------------------------
-/* */
-pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache),
- Sim(Cache)
+/* The legacy translations here of input Pkg iterators is obsolete,
+ this is not necessary since the pkgCaches are fully shared now. */
+pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache),
+ iPolicy(Cache),
+ Sim(&Cache->GetCache(),&iPolicy)
{
- Flags = new unsigned char[Cache.HeaderP->PackageCount];
- memset(Flags,0,sizeof(*Flags)*Cache.HeaderP->PackageCount);
+ Sim.Init(0);
+ Flags = new unsigned char[Cache->Head().PackageCount];
+ memset(Flags,0,sizeof(*Flags)*Cache->Head().PackageCount);
+
+ // Fake a filename so as not to activate the media swapping
+ string Jnk = "SIMULATE";
+ for (unsigned int I = 0; I != Cache->Head().PackageCount; I++)
+ FileNames[I] = Jnk;
+}
+ /*}}}*/
+// Simulate::Describe - Describe a package /*{{{*/
+// ---------------------------------------------------------------------
+/* Parameter Current == true displays the current package version,
+ Parameter Candidate == true displays the candidate package version */
+void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Current,bool Candidate)
+{
+ VerIterator Ver(Sim);
+
+ out << Pkg.Name();
+
+ if (Current == true)
+ {
+ Ver = Pkg.CurrentVer();
+ if (Ver.end() == false)
+ out << " [" << Ver.VerStr() << ']';
+ }
+
+ if (Candidate == true)
+ {
+ Ver = Sim[Pkg].CandidateVerIter(Sim);
+ if (Ver.end() == true)
+ return;
+
+ out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
+ }
}
/*}}}*/
// Simulate::Install - Simulate unpacking of a package /*{{{*/
PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
Flags[Pkg->ID] = 1;
- cout << "Inst " << Pkg.Name();
+ cout << "Inst ";
+ Describe(Pkg,cout,true,true);
Sim.MarkInstall(Pkg,false);
// Look for broken conflicts+predepends.
if (Sim[I].InstallVer == 0)
continue;
- for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false; D++)
- if (D->Type == pkgCache::Dep::Conflicts || D->Type == pkgCache::Dep::PreDepends)
+ for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
+ {
+ DepIterator Start;
+ DepIterator End;
+ D.GlobOr(Start,End);
+ if (Start->Type == pkgCache::Dep::Conflicts ||
+ Start->Type == pkgCache::Dep::Obsoletes ||
+ End->Type == pkgCache::Dep::PreDepends)
{
- if ((Sim[D] & pkgDepCache::DepInstall) == 0)
+ if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
{
- cout << " [" << I.Name() << " on " << D.TargetPkg().Name() << ']';
- if (D->Type == pkgCache::Dep::Conflicts)
+ cout << " [" << I.Name() << " on " << Start.TargetPkg().Name() << ']';
+ if (Start->Type == pkgCache::Dep::Conflicts)
_error->Error("Fatal, conflicts violated %s",I.Name());
}
- }
+ }
+ }
}
if (Sim.BrokenCount() != 0)
(Sim[D] & pkgDepCache::DepInstall) != 0)
continue;
- if (D->Type == pkgCache::Dep::Conflicts)
+ if (D->Type == pkgCache::Dep::Obsoletes)
+ cout << " Obsoletes:" << D.TargetPkg().Name();
+ else if (D->Type == pkgCache::Dep::Conflicts)
cout << " Conflicts:" << D.TargetPkg().Name();
else
cout << " Depends:" << D.TargetPkg().Name();
_error->Error("Conf Broken %s",Pkg.Name());
}
else
- cout << "Conf " << Pkg.Name();
+ {
+ cout << "Conf ";
+ Describe(Pkg,cout,false,true);
+ }
if (Sim.BrokenCount() != 0)
ShortBreaks();
// Simulate::Remove - Simulate the removal of a package /*{{{*/
// ---------------------------------------------------------------------
/* */
-bool pkgSimulate::Remove(PkgIterator iPkg)
+bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
{
// Adapt the iterator
PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
Flags[Pkg->ID] = 3;
Sim.MarkDelete(Pkg);
- cout << "Remv " << Pkg.Name();
+ if (Purge == true)
+ cout << "Purg ";
+ else
+ cout << "Remv ";
+ Describe(Pkg,cout,true,false);
if (Sim.BrokenCount() != 0)
ShortBreaks();
{
for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
{
+ if (I->VersionList == 0)
+ continue;
+
+ // Only choice for a ReInstReq package is to reinstall
+ if (I->InstState == pkgCache::State::ReInstReq ||
+ I->InstState == pkgCache::State::HoldReInstReq)
+ {
+ if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
+ Cache.MarkKeep(I);
+ else
+ {
+ // Is this right? Will dpkg choke on an upgrade?
+ if (Cache[I].CandidateVer != 0 &&
+ Cache[I].CandidateVerIter(Cache).Downloadable() == true)
+ Cache.MarkInstall(I);
+ else
+ return _error->Error(_("The package %s needs to be reinstalled, "
+ "but I can't find an archive for it."),I.Name());
+ }
+
+ continue;
+ }
+
switch (I->CurrentState)
{
- // This means installation failed somehow
+ /* This means installation failed somehow - it does not need to be
+ re-unpacked (probably) */
case pkgCache::State::UnPacked:
case pkgCache::State::HalfConfigured:
- Cache.MarkKeep(I);
+ if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
+ I.State() != pkgCache::PkgIterator::NeedsUnpack)
+ Cache.MarkKeep(I);
+ else
+ {
+ if (Cache[I].CandidateVer != 0 &&
+ Cache[I].CandidateVerIter(Cache).Downloadable() == true)
+ Cache.MarkInstall(I);
+ else
+ Cache.MarkDelete(I);
+ }
break;
// This means removal failed
/*}}}*/
// FixBroken - Fix broken packages /*{{{*/
// ---------------------------------------------------------------------
-/* This autoinstalls every broken package and then runs ScoredFix on the
- result. */
+/* This autoinstalls every broken package and then runs the problem resolver
+ on the result. */
bool pkgFixBroken(pkgDepCache &Cache)
{
// Auto upgrade all broken packages
for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
if (Cache[I].NowBroken() == true)
Cache.MarkInstall(I,true);
-
+
/* Fix packages that are in a NeedArchive state but don't have a
downloadable install version */
for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
if (Cache[I].InstVerIter(Cache).Downloadable() == false)
continue;
- Cache.MarkInstall(I,true);
+ Cache.MarkInstall(I,true);
}
- pkgProblemResolver Fix(Cache);
+ pkgProblemResolver Fix(&Cache);
return Fix.Resolve(true);
}
/*}}}*/
pre-existing package. This creates the initial set of conditions which
most likely contain problems because too many things were installed.
- ScoredFix is used to resolve the problems.
+ The problem resolver is used to resolve the problems.
*/
bool pkgDistUpgrade(pkgDepCache &Cache)
{
if (I->CurrentVer != 0)
Cache.MarkInstall(I,false);
- pkgProblemResolver Fix(Cache);
-
+ pkgProblemResolver Fix(&Cache);
+
// Hold back held packages.
- for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
+ if (_config->FindB("APT::Ignore-Hold",false) == false)
{
- if (I->SelectedState == pkgCache::State::Hold)
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
{
- Fix.Protect(I);
- Cache.MarkKeep(I);
+ if (I->SelectedState == pkgCache::State::Hold)
+ {
+ Fix.Protect(I);
+ Cache.MarkKeep(I);
+ }
}
}
return Fix.Resolve();
}
/*}}}*/
+// AllUpgrade - Upgrade as many packages as possible /*{{{*/
+// ---------------------------------------------------------------------
+/* Right now the system must be consistent before this can be called.
+ It also will not change packages marked for install, it only tries
+ to install packages not marked for install */
+bool pkgAllUpgrade(pkgDepCache &Cache)
+{
+ pkgProblemResolver Fix(&Cache);
+
+ if (Cache.BrokenCount() != 0)
+ return false;
+
+ // Upgrade all installed packages
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
+ {
+ if (Cache[I].Install() == true)
+ Fix.Protect(I);
+
+ if (_config->FindB("APT::Ignore-Hold",false) == false)
+ if (I->SelectedState == pkgCache::State::Hold)
+ continue;
+
+ if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
+ Cache.MarkInstall(I,false);
+ }
+
+ return Fix.ResolveByKeep();
+}
+ /*}}}*/
+// MinimizeUpgrade - Minimizes the set of packages to be upgraded /*{{{*/
+// ---------------------------------------------------------------------
+/* This simply goes over the entire set of packages and tries to keep
+ each package marked for upgrade. If a conflict is generated then
+ the package is restored. */
+bool pkgMinimizeUpgrade(pkgDepCache &Cache)
+{
+ if (Cache.BrokenCount() != 0)
+ return false;
+
+ // We loop for 10 tries to get the minimal set size.
+ bool Change = false;
+ unsigned int Count = 0;
+ do
+ {
+ Change = false;
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
+ {
+ // Not interesting
+ if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
+ continue;
+
+ // Keep it and see if that is OK
+ Cache.MarkKeep(I);
+ if (Cache.BrokenCount() != 0)
+ Cache.MarkInstall(I,false);
+ else
+ {
+ // If keep didnt actually do anything then there was no change..
+ if (Cache[I].Upgrade() == false)
+ Change = true;
+ }
+ }
+ Count++;
+ }
+ while (Change == true && Count < 10);
+
+ if (Cache.BrokenCount() != 0)
+ return _error->Error("Internal Error in pkgMinimizeUpgrade");
+
+ return true;
+}
+ /*}}}*/
// ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
// ---------------------------------------------------------------------
/* */
-pkgProblemResolver::pkgProblemResolver(pkgDepCache &Cache) : Cache(Cache)
+pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : Cache(*pCache)
{
// Allocate memory
- unsigned long Size = Cache.HeaderP->PackageCount;
+ unsigned long Size = Cache.Head().PackageCount;
Scores = new signed short[Size];
Flags = new unsigned char[Size];
memset(Flags,0,sizeof(*Flags)*Size);
// Set debug to true to see its decision logic
- Debug = false;
+ Debug = _config->FindB("Debug::pkgProblemResolver",false);
+}
+ /*}}}*/
+// ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+pkgProblemResolver::~pkgProblemResolver()
+{
+ delete [] Scores;
+ delete [] Flags;
}
/*}}}*/
// ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
/* */
void pkgProblemResolver::MakeScores()
{
- unsigned long Size = Cache.HeaderP->PackageCount;
+ unsigned long Size = Cache.Head().PackageCount;
memset(Scores,0,sizeof(*Scores)*Size);
// Generate the base scores for a package based on its properties
}
// Copy the scores to advoid additive looping
- signed short *OldScores = new signed short[Size];
+ SPtrArray<signed short> OldScores = new signed short[Size];
memcpy(OldScores,Scores,sizeof(*Scores)*Size);
/* Now we cause 1 level of dependency inheritance, that is we add the
/* Protected things are pushed really high up. This number should put them
ahead of everything */
for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
+ {
if ((Flags[I->ID] & Protected) != 0)
Scores[I->ID] += 10000;
-
- delete [] OldScores;
+ if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+ Scores[I->ID] += 5000;
+ }
}
/*}}}*/
// ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
{
if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
return false;
+ if ((Flags[Pkg->ID] & Protected) == Protected)
+ return false;
+
Flags[Pkg->ID] &= ~Upgradable;
bool WasKept = Cache[Pkg].Keep();
Cache.MarkInstall(Pkg,false);
+ // This must be a virtual package or something like that.
+ if (Cache[Pkg].InstVerIter(Cache).end() == true)
+ return false;
+
// Isolate the problem dependency
bool Fail = false;
for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
pkgCache::DepIterator Start = D;
pkgCache::DepIterator End = D;
unsigned char State = 0;
- for (bool LastOR = true; D.end() == false && LastOR == true; D++)
+ for (bool LastOR = true; D.end() == false && LastOR == true;)
{
State |= Cache[D];
LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
+ D++;
if (LastOR == true)
End = D;
}
// We only worry about critical deps.
if (End.IsCritical() != true)
continue;
-
- // Dep is ok
- if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
- continue;
-
- // Hm, the group is broken.. I have no idea how to handle this
- if (Start != End)
- {
- cout << "Note, a broken or group was found in " << Pkg.Name() << "." << endl;
- Fail = true;
- break;
- }
- // Upgrade the package if the candidate version will fix the problem.
- if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
+ // Iterate over all the members in the or group
+ while (1)
{
+ // Dep is ok now
+ if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
+ break;
+
+ // Do not change protected packages
PkgIterator P = Start.SmartTargetPkg();
- if (DoUpgrade(P) == false)
+ if ((Flags[P->ID] & Protected) == Protected)
{
if (Debug == true)
- cout << " Reinst Failed because of " << P.Name() << endl;
+ clog << " Reinst Failed because of protected " << P.Name() << endl;
Fail = true;
+ }
+ else
+ {
+ // Upgrade the package if the candidate version will fix the problem.
+ if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
+ {
+ if (DoUpgrade(P) == false)
+ {
+ if (Debug == true)
+ clog << " Reinst Failed because of " << P.Name() << endl;
+ Fail = true;
+ }
+ else
+ {
+ Fail = false;
+ break;
+ }
+ }
+ else
+ {
+ /* We let the algorithm deal with conflicts on its next iteration,
+ it is much smarter than us */
+ if (Start->Type == pkgCache::Dep::Conflicts ||
+ Start->Type == pkgCache::Dep::Obsoletes)
+ break;
+
+ if (Debug == true)
+ clog << " Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
+ Fail = true;
+ }
+ }
+
+ if (Start == End)
break;
- }
+ Start++;
}
- else
- {
- /* We let the algorithm deal with conflicts on its next iteration,
- it is much smarter than us */
- if (End->Type == pkgCache::Dep::Conflicts)
- continue;
-
- if (Debug == true)
- cout << " Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
- Fail = true;
+ if (Fail == true)
break;
- }
}
// Undo our operations - it might be smart to undo everything this did..
}
if (Debug == true)
- cout << " Re-Instated " << Pkg.Name() << endl;
+ clog << " Re-Instated " << Pkg.Name() << endl;
return true;
}
/*}}}*/
upgrade packages to advoid problems. */
bool pkgProblemResolver::Resolve(bool BrokenFix)
{
- unsigned long Size = Cache.HeaderP->PackageCount;
+ unsigned long Size = Cache.Head().PackageCount;
// Record which packages are marked for install
bool Again = false;
while (Again == true);
if (Debug == true)
- cout << "Starting" << endl;
+ clog << "Starting" << endl;
MakeScores();
operates from highest score to lowest. This prevents problems when
high score packages cause the removal of lower score packages that
would cause the removal of even lower score packages. */
- pkgCache::Package **PList = new pkgCache::Package *[Size];
+ SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
pkgCache::Package **PEnd = PList;
for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
*PEnd++ = I;
if (Scores[(*K)->ID] != 0)
{
pkgCache::PkgIterator Pkg(Cache,*K);
- cout << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
+ clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
} */
if (Debug == true)
- cout << "Starting 2" << endl;
+ clog << "Starting 2" << endl;
/* Now consider all broken packages. For each broken package we either
remove the package or fix it's problem. We do this once, it should
if (Cache[I].CandidateVer != Cache[I].InstallVer &&
I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
(Flags[I->ID] & PreInstalled) != 0 &&
- (Flags[I->ID] & Protected) == 0)
+ (Flags[I->ID] & Protected) == 0 &&
+ (Flags[I->ID] & ReInstateTried) == 0)
{
if (Debug == true)
- cout << " Try to Re-Instate " << I.Name() << endl;
- int OldBreaks = Cache.BrokenCount();
+ clog << " Try to Re-Instate " << I.Name() << endl;
+ unsigned long OldBreaks = Cache.BrokenCount();
pkgCache::Version *OldVer = Cache[I].InstallVer;
-
+ Flags[I->ID] &= ReInstateTried;
+
Cache.MarkInstall(I,false);
if (Cache[I].InstBroken() == true ||
OldBreaks < Cache.BrokenCount())
}
else
if (Debug == true)
- cout << "Re-Instated " << I.Name() << endl;
+ clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
}
if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
continue;
+ if (Debug == true)
+ cout << "Investigating " << I.Name() << endl;
+
// Isolate the problem dependency
PackageKill KillList[100];
PackageKill *LEnd = KillList;
- for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
+ bool InOr = false;
+ pkgCache::DepIterator Start;
+ pkgCache::DepIterator End;
+ PackageKill *OldEnd = LEnd;
+
+ enum {OrRemove,OrKeep} OrOp = OrRemove;
+ for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
+ D.end() == false || InOr == true;)
{
// Compute a single dependency element (glob or)
- pkgCache::DepIterator Start = D;
- pkgCache::DepIterator End = D;
- unsigned char State = 0;
- for (bool LastOR = true; D.end() == false && LastOR == true; D++)
+ if (Start == End)
{
- State |= Cache[D];
- LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
- if (LastOR == true)
- End = D;
+ // Decide what to do
+ if (InOr == true)
+ {
+ if (OldEnd == LEnd && OrOp == OrRemove)
+ {
+ if ((Flags[I->ID] & Protected) != Protected)
+ {
+ if (Debug == true)
+ clog << " Or group remove for " << I.Name() << endl;
+ Cache.MarkDelete(I);
+ Change = true;
+ }
+ }
+ if (OldEnd == LEnd && OrOp == OrKeep)
+ {
+ if (Debug == true)
+ clog << " Or group keep for " << I.Name() << endl;
+ Cache.MarkKeep(I);
+ Change = true;
+ }
+ }
+
+ /* We do an extra loop (as above) to finalize the or group
+ processing */
+ InOr = false;
+ OrOp = OrRemove;
+ D.GlobOr(Start,End);
+ if (Start.end() == true)
+ break;
+
+ // We only worry about critical deps.
+ if (End.IsCritical() != true)
+ continue;
+
+ InOr = Start != End;
+ OldEnd = LEnd;
}
-
- // We only worry about critical deps.
- if (End.IsCritical() != true)
- continue;
-
+ else
+ Start++;
+
// Dep is ok
if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
+ {
+ InOr = false;
continue;
+ }
- // Hm, the group is broken.. I have no idea how to handle this
- if (Start != End)
- {
- cout << "Note, a broken or group was found in " << I.Name() << "." << endl;
- Cache.MarkDelete(I);
+ if (Debug == true)
+ clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
+
+ /* Look across the version list. If there are no possible
+ targets then we keep the package and bail. This is necessary
+ if a package has a dep on another package that cant be found */
+ SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
+ if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
+ Start->Type != pkgCache::Dep::Conflicts &&
+ Start->Type != pkgCache::Dep::Obsoletes &&
+ Cache[I].NowBroken() == false)
+ {
+ if (InOr == true)
+ {
+ /* No keep choice because the keep being OK could be the
+ result of another element in the OR group! */
+ continue;
+ }
+
+ Change = true;
+ Cache.MarkKeep(I);
break;
}
-
- if (Debug == true)
- cout << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
- /* Conflicts is simple, decide if we should remove this package
- or the conflicted one */
- pkgCache::Version **VList = End.AllTargets();
bool Done = false;
for (pkgCache::Version **V = VList; *V != 0; V++)
{
pkgCache::VerIterator Ver(Cache,*V);
pkgCache::PkgIterator Pkg = Ver.ParentPkg();
-
+
if (Debug == true)
- cout << " Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
+ clog << " Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
" as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
+
+ /* Try to fix the package under consideration rather than
+ fiddle with the VList package */
if (Scores[I->ID] <= Scores[Pkg->ID] ||
- ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
- End->Type != pkgCache::Dep::Conflicts))
+ ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
+ End->Type != pkgCache::Dep::Conflicts &&
+ End->Type != pkgCache::Dep::Obsoletes))
{
- if ((Flags[I->ID] & Protected) != 0)
+ // Try a little harder to fix protected packages..
+ if ((Flags[I->ID] & Protected) == Protected)
+ {
+ if (DoUpgrade(Pkg) == true)
+ {
+ if (Scores[Pkg->ID] > Scores[I->ID])
+ Scores[Pkg->ID] = Scores[I->ID];
+ break;
+ }
+
continue;
+ }
- // See if a keep will do
+ /* See if a keep will do, unless the package is protected,
+ then installing it will be necessary */
+ bool Installed = Cache[I].Install();
Cache.MarkKeep(I);
if (Cache[I].InstBroken() == false)
{
+ // Unwind operation will be keep now
+ if (OrOp == OrRemove)
+ OrOp = OrKeep;
+
+ // Restore
+ if (InOr == true && Installed == true)
+ Cache.MarkInstall(I,false);
+
if (Debug == true)
- cout << " Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
+ clog << " Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
}
else
- {
+ {
if (BrokenFix == false || DoUpgrade(I) == false)
{
- if (Debug == true)
- cout << " Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
- Cache.MarkDelete(I);
- if (Counter > 1)
- Scores[I->ID] = Scores[Pkg->ID];
- }
+ // Consider other options
+ if (InOr == false)
+ {
+ if (Debug == true)
+ clog << " Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
+ Cache.MarkDelete(I);
+ if (Counter > 1)
+ {
+ if (Scores[Pkg->ID] > Scores[I->ID])
+ Scores[I->ID] = Scores[Pkg->ID];
+ }
+ }
+ }
}
-
+
Change = true;
Done = true;
break;
}
else
{
- // Skip this if it is protected
+ /* This is a conflicts, and the version we are looking
+ at is not the currently selected version of the
+ package, which means it is not necessary to
+ remove/keep */
+ if (Cache[Pkg].InstallVer != Ver &&
+ (Start->Type == pkgCache::Dep::Conflicts ||
+ Start->Type == pkgCache::Dep::Obsoletes))
+ continue;
+
+ // Skip adding to the kill list if it is protected
if ((Flags[Pkg->ID] & Protected) != 0)
continue;
+
+ if (Debug == true)
+ clog << " Added " << Pkg.Name() << " to the remove list" << endl;
LEnd->Pkg = Pkg;
LEnd->Dep = End;
LEnd++;
- if (End->Type != pkgCache::Dep::Conflicts)
+
+ if (Start->Type != pkgCache::Dep::Conflicts &&
+ Start->Type != pkgCache::Dep::Obsoletes)
break;
}
}
// Hm, nothing can possibly satisify this dep. Nuke it.
- if (VList[0] == 0 && End->Type != pkgCache::Dep::Conflicts)
+ if (VList[0] == 0 &&
+ Start->Type != pkgCache::Dep::Conflicts &&
+ Start->Type != pkgCache::Dep::Obsoletes &&
+ (Flags[I->ID] & Protected) != Protected)
{
+ bool Installed = Cache[I].Install();
Cache.MarkKeep(I);
if (Cache[I].InstBroken() == false)
{
+ // Unwind operation will be keep now
+ if (OrOp == OrRemove)
+ OrOp = OrKeep;
+
+ // Restore
+ if (InOr == true && Installed == true)
+ Cache.MarkInstall(I,false);
+
if (Debug == true)
- cout << " Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
+ clog << " Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
}
else
{
if (Debug == true)
- cout << " Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
- Cache.MarkDelete(I);
+ clog << " Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
+ if (InOr == false)
+ Cache.MarkDelete(I);
}
Change = true;
Done = true;
}
- delete [] VList;
+ // Try some more
+ if (InOr == true)
+ continue;
+
if (Done == true)
break;
}
// Apply the kill list now
if (Cache[I].InstallVer != 0)
+ {
for (PackageKill *J = KillList; J != LEnd; J++)
- {
- Change = true;
- if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
{
- if (J->Dep->Type == pkgCache::Dep::Conflicts)
+ Change = true;
+ if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
+ {
+ if (J->Dep->Type == pkgCache::Dep::Conflicts ||
+ J->Dep->Type == pkgCache::Dep::Obsoletes)
+ {
+ if (Debug == true)
+ clog << " Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
+ Cache.MarkDelete(J->Pkg);
+ }
+ }
+ else
{
if (Debug == true)
- cout << " Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
- Cache.MarkDelete(J->Pkg);
+ clog << " Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
+ Cache.MarkKeep(J->Pkg);
}
- }
- else
+
+ if (Counter > 1)
+ {
+ if (Scores[I->ID] > Scores[J->Pkg->ID])
+ Scores[J->Pkg->ID] = Scores[I->ID];
+ }
+ }
+ }
+ }
+ }
+
+ if (Debug == true)
+ clog << "Done" << endl;
+
+ if (Cache.BrokenCount() != 0)
+ {
+ // See if this is the result of a hold
+ pkgCache::PkgIterator I = Cache.PkgBegin();
+ for (;I.end() != true; I++)
+ {
+ if (Cache[I].InstBroken() == false)
+ continue;
+ if ((Flags[I->ID] & Protected) != Protected)
+ return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
+ }
+ return _error->Error(_("Unable to correct problems, you have held broken packages."));
+ }
+
+ // set the auto-flags (mvo: I'm not sure if we _really_ need this, but
+ // I didn't managed
+ pkgCache::PkgIterator I = Cache.PkgBegin();
+ for (;I.end() != true; I++) {
+ if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
+ if(_config->FindI("Debug::pkgAutoRemove",false)) {
+ std::clog << "Resolve installed new pkg: " << I.Name()
+ << " (now marking it as auto)" << std::endl;
+ }
+ Cache[I].Flags |= pkgCache::Flag::Auto;
+ }
+ }
+
+
+ return true;
+}
+ /*}}}*/
+// ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
+// ---------------------------------------------------------------------
+/* This is the work horse of the soft upgrade routine. It is very gental
+ in that it does not install or remove any packages. It is assumed that the
+ system was non-broken previously. */
+bool pkgProblemResolver::ResolveByKeep()
+{
+ unsigned long Size = Cache.Head().PackageCount;
+
+ if (Debug == true)
+ clog << "Entering ResolveByKeep" << endl;
+
+ MakeScores();
+
+ /* We have to order the packages so that the broken fixing pass
+ operates from highest score to lowest. This prevents problems when
+ high score packages cause the removal of lower score packages that
+ would cause the removal of even lower score packages. */
+ pkgCache::Package **PList = new pkgCache::Package *[Size];
+ pkgCache::Package **PEnd = PList;
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
+ *PEnd++ = I;
+ This = this;
+ qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
+
+ // Consider each broken package
+ pkgCache::Package **LastStop = 0;
+ for (pkgCache::Package **K = PList; K != PEnd; K++)
+ {
+ pkgCache::PkgIterator I(Cache,*K);
+
+ if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
+ continue;
+
+ /* Keep the package. If this works then great, otherwise we have
+ to be significantly more agressive and manipulate its dependencies */
+ if ((Flags[I->ID] & Protected) == 0)
+ {
+ if (Debug == true)
+ clog << "Keeping package " << I.Name() << endl;
+ Cache.MarkKeep(I);
+ if (Cache[I].InstBroken() == false)
+ {
+ K = PList - 1;
+ continue;
+ }
+ }
+
+ // Isolate the problem dependencies
+ for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
+ {
+ DepIterator Start;
+ DepIterator End;
+ D.GlobOr(Start,End);
+
+ // We only worry about critical deps.
+ if (End.IsCritical() != true)
+ continue;
+
+ // Dep is ok
+ if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
+ continue;
+
+ /* Hm, the group is broken.. I suppose the best thing to do is to
+ is to try every combination of keep/not-keep for the set, but thats
+ slow, and this never happens, just be conservative and assume the
+ list of ors is in preference and keep till it starts to work. */
+ while (true)
+ {
+ if (Debug == true)
+ clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
+
+ // Look at all the possible provides on this package
+ SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
+ for (pkgCache::Version **V = VList; *V != 0; V++)
{
- if (Debug == true)
- cout << " Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
- Cache.MarkKeep(J->Pkg);
+ pkgCache::VerIterator Ver(Cache,*V);
+ pkgCache::PkgIterator Pkg = Ver.ParentPkg();
+
+ // It is not keepable
+ if (Cache[Pkg].InstallVer == 0 ||
+ Pkg->CurrentVer == 0)
+ continue;
+
+ if ((Flags[I->ID] & Protected) == 0)
+ {
+ if (Debug == true)
+ clog << " Keeping Package " << Pkg.Name() << " due to dep" << endl;
+ Cache.MarkKeep(Pkg);
+ }
+
+ if (Cache[I].InstBroken() == false)
+ break;
}
- if (Counter > 1)
- Scores[J->Pkg->ID] = Scores[I->ID];
- }
+ if (Cache[I].InstBroken() == false)
+ break;
+
+ if (Start == End)
+ break;
+ Start++;
+ }
+
+ if (Cache[I].InstBroken() == false)
+ break;
}
- }
- if (Debug == true)
- cout << "Done" << endl;
+ if (Cache[I].InstBroken() == true)
+ continue;
+
+ // Restart again.
+ if (K == LastStop)
+ return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
+ LastStop = K;
+ K = PList - 1;
+ }
+
+ return true;
+}
+ /*}}}*/
+// ProblemResolver::InstallProtect - Install all protected packages /*{{{*/
+// ---------------------------------------------------------------------
+/* This is used to make sure protected packages are installed */
+void pkgProblemResolver::InstallProtect()
+{
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
+ {
+ if ((Flags[I->ID] & Protected) == Protected)
+ {
+ if ((Flags[I->ID] & ToRemove) == ToRemove)
+ Cache.MarkDelete(I);
+ else
+ Cache.MarkInstall(I,false);
+ }
+ }
+}
+ /*}}}*/
+
+// PrioSortList - Sort a list of versions by priority /*{{{*/
+// ---------------------------------------------------------------------
+/* This is ment to be used in conjunction with AllTargets to get a list
+ of versions ordered by preference. */
+static pkgCache *PrioCache;
+static int PrioComp(const void *A,const void *B)
+{
+ pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
+ pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
- delete [] Scores;
- delete [] PList;
+ if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
+ (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
+ return 1;
+ if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
+ (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+ return -1;
+
+ if (L->Priority != R->Priority)
+ return R->Priority - L->Priority;
+ return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
+}
+void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
+{
+ unsigned long Count = 0;
+ PrioCache = &Cache;
+ for (pkgCache::Version **I = List; *I != 0; I++)
+ Count++;
+ qsort(List,Count,sizeof(*List),PrioComp);
+}
+ /*}}}*/
+
+
+// mark a single package in Mark-and-Sweep
+void pkgMarkPackage(pkgDepCache &Cache,
+ const pkgCache::PkgIterator &pkg,
+ const pkgCache::VerIterator &ver,
+ bool follow_recommends,
+ bool follow_suggests)
+{
+ pkgDepCache::StateCache &state=Cache[pkg];
+ pkgCache::VerIterator candver=state.CandidateVerIter(Cache);
+ pkgCache::VerIterator instver=state.InstVerIter(Cache);
+
+#if 0
+ // If a package was garbage-collected but is now being marked, we
+ // should re-select it
+ // For cases when a pkg is set to upgrade and this trigger the
+ // removal of a no-longer used dependency. if the pkg is set to
+ // keep again later it will result in broken deps
+ if(state.Delete() && state.RemoveReason=pkgDepCache::Unused)
+ {
+ if(ver==candver)
+ mark_install(pkg, false, false, NULL);
+ else if(ver==pkg.CurrentVer())
+ MarkKeep(pkg);
+
+ instver=state.InstVerIter(*this);
+ }
+#endif
+
+ // Ignore versions other than the InstVer, and ignore packages
+ // that are already going to be removed or just left uninstalled.
+ if(!(ver==instver && !instver.end()))
+ return;
+
+ // if we are marked already we are done
+ if(state.Marked)
+ return;
+
+ //std::cout << "Setting Marked for: " << pkg.Name() << std::endl;
+ state.Marked=true;
+
+ if(!ver.end())
+ {
+ for(pkgCache::DepIterator d=ver.DependsList(); !d.end(); ++d)
+ {
+ if(d->Type==pkgCache::Dep::Depends ||
+ d->Type==pkgCache::Dep::PreDepends ||
+ (follow_recommends &&
+ d->Type==pkgCache::Dep::Recommends) ||
+ (follow_suggests &&
+ d->Type==pkgCache::Dep::Suggests))
+ {
+ // Try all versions of this package.
+ for(pkgCache::VerIterator V=d.TargetPkg().VersionList();
+ !V.end(); ++V)
+ {
+ if(_system->VS->CheckDep(V.VerStr(),d->CompareOp, d.TargetVer()))
+ {
+ pkgMarkPackage(Cache, V.ParentPkg(), V,
+ follow_recommends, follow_suggests);
+ }
+ }
+ // Now try virtual packages
+ for(pkgCache::PrvIterator prv=d.TargetPkg().ProvidesList();
+ !prv.end(); ++prv)
+ {
+ if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
+ d.TargetVer()))
+ {
+ pkgMarkPackage(Cache, prv.OwnerPkg(), prv.OwnerVer(),
+ follow_recommends, follow_suggests);
+ }
+ }
+ }
+ }
+ }
+}
+
+
+// Helper for APT::NeverAutoRemove, always include the packages matching
+// this regexp into the root-set
+inline bool
+pkgMarkAlwaysInclude(pkgCache::PkgIterator p, vector<regex_t*> alwaysMark)
+{
+ for(unsigned int i=0;i<alwaysMark.size();i++)
+ if (regexec(alwaysMark[i],p.Name(),0,0,0) == 0)
+ return true;
+
+ return false;
+}
+
+// the main mark algorithm
+bool pkgMarkUsed(pkgDepCache &Cache, InRootSetFunc func)
+{
+ bool follow_recommends;
+ bool follow_suggests;
+
+ // init the states
+ for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p)
+ {
+ Cache[p].Marked=false;
+ Cache[p].Garbage=false;
+
+ // debug output
+ if(_config->FindB("Debug::pkgAutoRemove",false)
+ && Cache[p].Flags & pkgCache::Flag::Auto)
+ std::clog << "AutoDep: " << p.Name() << std::endl;
+ }
+
+ // init vars
+ follow_recommends=_config->FindB("APT::AutoRemove::RecommendsImportant",false);
+ follow_suggests=_config->FindB("APT::AutoRemove::SuggestsImportant", false);
+
+
+ // init the "NeverAutoRemove" variable
+ vector<regex_t *> neverAutoRemoveRegexp;
+ Configuration::Item const *Opts;
+ Opts = _config->Tree("APT::NeverAutoRemove");
+ if (Opts != 0 && Opts->Child != 0)
+ {
+ Opts = Opts->Child;
+ for (; Opts != 0; Opts = Opts->Next)
+ {
+ if (Opts->Value.empty() == true)
+ continue;
+
+ regex_t *p = new regex_t;
+ if(regcomp(p,Opts->Value.c_str(),
+ REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
+ {
+ regfree(p);
+ for(unsigned int i=0;i<neverAutoRemoveRegexp.size();i++)
+ regfree(neverAutoRemoveRegexp[i]);
+ return _error->Error("Regex compilation error for APT::NeverAutoRemove");
+ }
+ neverAutoRemoveRegexp.push_back(p);
+ }
+ }
+
+
+ // do the mark part, this is the core bit of the algorithm
+ for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p)
+ {
+ if( (func != NULL ? (*func)(p) : false) ||
+ pkgMarkAlwaysInclude(p, neverAutoRemoveRegexp) ||
+ !(Cache[p].Flags & pkgCache::Flag::Auto) ||
+ (p->Flags & pkgCache::Flag::Essential))
+
+ {
+ // the package is installed (and set to keep)
+ if(Cache[p].Keep() && !p.CurrentVer().end())
+ pkgMarkPackage(Cache, p, p.CurrentVer(),
+ follow_recommends, follow_suggests);
+ // the package is to be installed
+ else if(Cache[p].Install())
+ pkgMarkPackage(Cache, p, Cache[p].InstVerIter(Cache),
+ follow_recommends, follow_suggests);
+ }
+ }
+
+
+ // do the sweep
+ for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p)
+ {
+ pkgDepCache::StateCache &state=Cache[p];
+
+ // if it is not marked and it is installed, it's garbage
+ if(!state.Marked && !p.CurrentVer().end())
+ {
+ state.Garbage=true;
+ if(_config->FindB("Debug::pkgAutoRemove",false))
+ std::cout << "Garbage: " << p.Name() << std::endl;
+
+#if 0 // mvo: the below bits still needs to be ported
+
+ // Be sure not to re-delete already deleted packages.
+ if(delete_unused && (!p.CurrentVer().end() || state.Install()) &&
+ !state.Delete())
+ {
+ bool do_delete=true;
+
+ // If the package is being upgraded, check if we're
+ // losing a versioned dep. If the dependency matches
+ // the previous version and not the new version, keep
+ // the package back instead of removing it.
+ if(!p.CurrentVer().end() && state.Install())
+ {
+ const char *vs=p.CurrentVer().VerStr();
+
+ // Check direct revdeps only. THIS ASSUMES NO
+ // VERSIONED PROVIDES, but Debian probably won't
+ // have them for ages if ever.
+ for(pkgCache::DepIterator revdep=p.RevDependsList();
+ !revdep.end(); ++revdep)
+ {
+ pkgCache::PkgIterator depender=revdep.ParentPkg();
+ // Find which version of the depending package
+ // will be installed.
+ pkgCache::VerIterator instver=(*this)[depender].InstVerIter(*this);
+
+ // Only pay attention to strong positive
+ // dependencies whose parents will be installed.
+ if(revdep.ParentVer()==instver &&
+ (revdep->Type==pkgCache::Dep::Depends ||
+ revdep->Type==pkgCache::Dep::PreDepends ||
+ (revdep->Type==pkgCache::Dep::Recommends &&
+ follow_recommends)))
+ {
+ // If the previous version matched, cancel the
+ // deletion. (note that I assume that the new
+ // version does NOT match; otherwise it would
+ // not be unused!)
+ if(_system->VS->CheckDep(vs,
+ revdep->CompareOp,
+ revdep.TargetVer()))
+ {
+ mark_keep(p, false, false, undo);
+ do_delete=false;
+ break;
+ }
+ }
+ }
+ }
+
+ if(do_delete)
+ mark_delete(p, false, true, undo);
+ }
+#endif
+ }
+ }
+
+ // cleanup
+ for(unsigned int i=0;i<neverAutoRemoveRegexp.size();i++)
+ regfree(neverAutoRemoveRegexp[i]);
- if (Cache.BrokenCount() != 0)
- return _error->Error("Internal error, ScoredFix generated breaks.");
return true;
}
- /*}}}*/
projects / apt.git / blobdiff