ordering.
Each of the features can be enabled in the sorting routine at an
- arbitary priority to give quite abit of control over the final unpacking
+ arbitrary priority to give quite abit of control over the final unpacking
order.
The rules listed above may never be violated and are called Critical.
##################################################################### */
/*}}}*/
// Include Files /*{{{*/
+#include<config.h>
+
#include <apt-pkg/orderlist.h>
#include <apt-pkg/depcache.h>
#include <apt-pkg/error.h>
// OrderList::pkgOrderList - Constructor /*{{{*/
// ---------------------------------------------------------------------
/* */
-pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache)
+pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache),
+ Primary(NULL), Secondary(NULL),
+ RevDepends(NULL), Remove(NULL),
+ AfterEnd(NULL), FileList(NULL),
+ LoopCount(-1), Depth(0)
{
- FileList = 0;
- Primary = 0;
- Secondary = 0;
- RevDepends = 0;
- Remove = 0;
- LoopCount = -1;
Debug = _config->FindB("Debug::pkgOrderList",false);
-
+
/* Construct the arrays, egcs 1.0.1 bug requires the package count
hack */
unsigned long Size = Cache.Head().PackageCount;
return false;
// Skip Packages that need configure only.
- if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
+ if ((Pkg.State() == pkgCache::PkgIterator::NeedsConfigure ||
+ Pkg.State() == pkgCache::PkgIterator::NeedsNothing) &&
Cache[Pkg].Keep() == true)
return false;
if (FileList[Pkg->ID].empty() == false)
return false;
+
return true;
}
/*}}}*/
-
// OrderList::DoRun - Does an order run /*{{{*/
// ---------------------------------------------------------------------
/* The caller is expeted to have setup the desired probe state */
Depth = 0;
WipeFlags(Added | AddPending | Loop | InList);
- for (iterator I = List; I != End; I++)
+ for (iterator I = List; I != End; ++I)
Flag(*I,InList);
// Rebuild the main list into the temp list.
iterator OldEnd = End;
End = NList;
- for (iterator I = List; I != OldEnd; I++)
- if (VisitNode(PkgIterator(Cache,*I)) == false)
+ for (iterator I = List; I != OldEnd; ++I)
+ if (VisitNode(PkgIterator(Cache,*I), "DoRun") == false)
{
End = OldEnd;
return false;
bool pkgOrderList::OrderCritical()
{
FileList = 0;
-
- Primary = &pkgOrderList::DepUnPackPre;
+
+ Primary = &pkgOrderList::DepUnPackPreD;
Secondary = 0;
RevDepends = 0;
Remove = 0;
LoopCount = 0;
-
+
// Sort
Me = this;
- qsort(List,End - List,sizeof(*List),&OrderCompareB);
-
+ qsort(List,End - List,sizeof(*List),&OrderCompareB);
+
if (DoRun() == false)
return false;
-
+
if (LoopCount != 0)
return _error->Error("Fatal, predepends looping detected");
+
+ if (Debug == true)
+ {
+ clog << "** Critical Unpack ordering done" << endl;
+
+ for (iterator I = List; I != End; ++I)
+ {
+ PkgIterator P(Cache,*I);
+ if (IsNow(P) == true)
+ clog << " " << P.FullName() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl;
+ }
+ }
+
return true;
}
/*}}}*/
if (FileList != 0)
{
WipeFlags(After);
-
+
// Set the inlist flag
- for (iterator I = List; I != End; I++)
+ for (iterator I = List; I != End; ++I)
{
PkgIterator P(Cache,*I);
if (IsMissing(P) == true && IsNow(P) == true)
Flag(*I,After);
}
}
-
+
Primary = &pkgOrderList::DepUnPackCrit;
Secondary = &pkgOrderList::DepConfigure;
RevDepends = &pkgOrderList::DepUnPackDep;
clog << "** Pass A" << endl;
if (DoRun() == false)
return false;
-
+
if (Debug == true)
clog << "** Pass B" << endl;
Secondary = 0;
Remove = 0; // Otherwise the libreadline remove problem occures
if (DoRun() == false)
return false;
-
+
if (Debug == true)
clog << "** Pass D" << endl;
LoopCount = 0;
{
clog << "** Unpack ordering done" << endl;
- for (iterator I = List; I != End; I++)
+ for (iterator I = List; I != End; ++I)
{
PkgIterator P(Cache,*I);
if (IsNow(P) == true)
- clog << P.Name() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl;
+ clog << " " << P.FullName() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl;
}
- }
+ }
return true;
}
return DoRun();
}
/*}}}*/
-
// OrderList::Score - Score the package for sorting /*{{{*/
// ---------------------------------------------------------------------
/* Higher scores order earlier */
int pkgOrderList::Score(PkgIterator Pkg)
{
- // Removal is always done first
+ // Removals should be done after we dealt with essentials
+ static int const ScoreDelete = _config->FindI("OrderList::Score::Delete", 100);
if (Cache[Pkg].Delete() == true)
- return 200;
-
+ return ScoreDelete;
+
// This should never happen..
if (Cache[Pkg].InstVerIter(Cache).end() == true)
return -1;
-
+
+ static int const ScoreEssential = _config->FindI("OrderList::Score::Essential", 200);
+ static int const ScoreImmediate = _config->FindI("OrderList::Score::Immediate", 10);
+ static int const ScorePreDepends = _config->FindI("OrderList::Score::PreDepends", 50);
+
int Score = 0;
if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
- Score += 100;
+ Score += ScoreEssential;
if (IsFlag(Pkg,Immediate) == true)
- Score += 10;
-
- for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList();
- D.end() == false; D++)
+ Score += ScoreImmediate;
+
+ for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList();
+ D.end() == false; ++D)
if (D->Type == pkgCache::Dep::PreDepends)
{
- Score += 50;
+ Score += ScorePreDepends;
break;
}
-
+
// Important Required Standard Optional Extra
- signed short PrioMap[] = {0,5,4,3,1,0};
if (Cache[Pkg].InstVerIter(Cache)->Priority <= 5)
+ {
+ signed short PrioMap[] = {0,5,4,3,1,0};
Score += PrioMap[Cache[Pkg].InstVerIter(Cache)->Priority];
+ }
return Score;
}
/*}}}*/
int ScoreA = Me->Score(A);
int ScoreB = Me->Score(B);
+
if (ScoreA > ScoreB)
return -1;
int ScoreA = Me->Score(A);
int ScoreB = Me->Score(B);
+
if (ScoreA > ScoreB)
return -1;
return strcmp(A.Name(),B.Name());
}
/*}}}*/
-
// OrderList::VisitDeps - Visit forward install dependencies /*{{{*/
// ---------------------------------------------------------------------
/* This calls the dependency function for the normal forwards dependencies
return true;
bool Res = true;
- for (PrvIterator P = Ver.ProvidesList(); P.end() == false; P++)
+ for (PrvIterator P = Ver.ProvidesList(); P.end() == false; ++P)
Res &= (this->*F)(P.ParentPkg().RevDependsList());
- return true;
+ return Res;
}
/*}}}*/
// OrderList::VisitProvides - Visit all of the providing packages /*{{{*/
// ---------------------------------------------------------------------
-/* This routine calls visit on all providing packages. */
+/* This routine calls visit on all providing packages.
+
+ If the dependency is negative it first visits packages which are
+ intended to be removed and after that all other packages.
+ It does so to avoid situations in which this package is used to
+ satisfy a (or-group/provides) dependency of another package which
+ could have been satisfied also by upgrading another package -
+ otherwise we have more broken packages dpkg needs to auto-
+ deconfigure and in very complicated situations it even decides
+ against it! */
bool pkgOrderList::VisitProvides(DepIterator D,bool Critical)
-{
+{
SPtrArray<Version *> List = D.AllTargets();
- for (Version **I = List; *I != 0; I++)
+ for (Version **I = List; *I != 0; ++I)
{
VerIterator Ver(Cache,*I);
PkgIterator Pkg = Ver.ParentPkg();
+ if (D.IsNegative() == true && Cache[Pkg].Delete() == false)
+ continue;
+
if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
continue;
-
- if (D->Type != pkgCache::Dep::Conflicts &&
- D->Type != pkgCache::Dep::DpkgBreaks &&
- D->Type != pkgCache::Dep::Obsoletes &&
+
+ if (D.IsNegative() == false &&
Cache[Pkg].InstallVer != *I)
continue;
-
- if ((D->Type == pkgCache::Dep::Conflicts ||
- D->Type == pkgCache::Dep::DpkgBreaks ||
- D->Type == pkgCache::Dep::Obsoletes) &&
+
+ if (D.IsNegative() == true &&
(Version *)Pkg.CurrentVer() != *I)
continue;
-
+
// Skip over missing files
if (Critical == false && IsMissing(D.ParentPkg()) == true)
continue;
- if (VisitNode(Pkg) == false)
+ if (VisitNode(Pkg, "Provides-1") == false)
return false;
}
+ if (D.IsNegative() == false)
+ return true;
+ for (Version **I = List; *I != 0; ++I)
+ {
+ VerIterator Ver(Cache,*I);
+ PkgIterator Pkg = Ver.ParentPkg();
+
+ if (Cache[Pkg].Delete() == true)
+ continue;
+
+ if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
+ continue;
+
+ if ((Version *)Pkg.CurrentVer() != *I)
+ continue;
+
+ // Skip over missing files
+ if (Critical == false && IsMissing(D.ParentPkg()) == true)
+ continue;
+
+ if (VisitNode(Pkg, "Provides-2") == false)
+ return false;
+ }
+
return true;
}
/*}}}*/
/* This is the core ordering routine. It calls the set dependency
consideration functions which then potentialy call this again. Finite
depth is achived through the colouring mechinism. */
-bool pkgOrderList::VisitNode(PkgIterator Pkg)
+bool pkgOrderList::VisitNode(PkgIterator Pkg, char const* from)
{
// Looping or irrelevent.
// This should probably trancend not installed packages
if (Debug == true)
{
for (int j = 0; j != Depth; j++) clog << ' ';
- clog << "Visit " << Pkg.Name() << endl;
+ clog << "Visit " << Pkg.FullName() << " from " << from << endl;
}
Depth++;
if (Debug == true)
{
for (int j = 0; j != Depth; j++) clog << ' ';
- clog << "Leave " << Pkg.Name() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;
+ clog << "Leave " << Pkg.FullName() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;
}
return true;
}
/*}}}*/
-
// OrderList::DepUnPackCrit - Critical UnPacking ordering /*{{{*/
// ---------------------------------------------------------------------
/* Critical unpacking ordering strives to satisfy Conflicts: and
Loops are preprocessed and logged. */
bool pkgOrderList::DepUnPackCrit(DepIterator D)
{
- for (; D.end() == false; D++)
+ for (; D.end() == false; ++D)
{
if (D.Reverse() == true)
{
if (CheckDep(D) == true)
continue;
- if (VisitNode(D.ParentPkg()) == false)
+ if (VisitNode(D.ParentPkg(), "UnPackCrit") == false)
return false;
}
else
{
/* Forward critical dependencies MUST be correct before the
package can be unpacked. */
- if (D->Type != pkgCache::Dep::Conflicts &&
- D->Type != pkgCache::Dep::DpkgBreaks &&
- D->Type != pkgCache::Dep::Obsoletes &&
+ if (D.IsNegative() == false &&
D->Type != pkgCache::Dep::PreDepends)
continue;
}
return true;
}
-
+ /*}}}*/
// OrderList::DepUnPackPreD - Critical UnPacking ordering with depends /*{{{*/
// ---------------------------------------------------------------------
/* Critical PreDepends (also configure immediate and essential) strives to
ensure not only that all conflicts+predepends are met but that this
- package will be immediately configurable when it is unpacked.
-
+ package will be immediately configurable when it is unpacked.
Loops are preprocessed and logged. */
bool pkgOrderList::DepUnPackPreD(DepIterator D)
{
if (D.Reverse() == true)
return DepUnPackCrit(D);
- for (; D.end() == false; D++)
+ for (; D.end() == false; ++D)
{
if (D.IsCritical() == false)
continue;
if (D.Reverse() == true)
return true;
- for (; D.end() == false; D++)
+ for (; D.end() == false; ++D)
{
/* Only consider the PreDepends or Depends. Depends are only
considered at the lowest depth or in the case of immediate
bool pkgOrderList::DepUnPackDep(DepIterator D)
{
- for (; D.end() == false; D++)
+ for (; D.end() == false; ++D)
if (D.IsCritical() == true)
{
if (D.Reverse() == true)
if (IsMissing(D.ParentPkg()) == true)
continue;
- if (VisitNode(D.ParentPkg()) == false)
+ if (VisitNode(D.ParentPkg(), "UnPackDep-Parent") == false)
return false;
}
else
if (CheckDep(D) == true)
continue;
- if (VisitNode(D.TargetPkg()) == false)
+ if (VisitNode(D.TargetPkg(), "UnPackDep-Target") == false)
return false;
}
}
if (D.Reverse() == true)
return true;
- for (; D.end() == false; D++)
+ for (; D.end() == false; ++D)
if (D->Type == pkgCache::Dep::Depends)
if (VisitProvides(D,false) == false)
return false;
/*}}}*/
// OrderList::DepRemove - Removal ordering /*{{{*/
// ---------------------------------------------------------------------
-/* Removal visits all reverse depends. It considers if the dependency
- of the Now state version to see if it is okay with removing this
- package. This check should always fail, but is provided for symetery
- with the other critical handlers.
-
- Loops are preprocessed and logged. Removal loops can also be
- detected in the critical handler. They are characterized by an
- old version of A depending on B but the new version of A conflicting
- with B, thus either A or B must break to install. */
-bool pkgOrderList::DepRemove(DepIterator D)
+/* Checks all given dependencies if they are broken by the remove of a
+ package and if so fix it by visiting another provider or or-group
+ member to ensure that the dependee keeps working which is especially
+ important for Immediate packages like e.g. those depending on an
+ awk implementation. If the dependency can't be fixed with another
+ package this means an upgrade of the package will solve the problem. */
+bool pkgOrderList::DepRemove(DepIterator Broken)
{
- if (D.Reverse() == false)
+ if (Broken.Reverse() == false)
return true;
- for (; D.end() == false; D++)
- if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
+
+ for (; Broken.end() == false; ++Broken)
+ {
+ if (Broken->Type != pkgCache::Dep::Depends &&
+ Broken->Type != pkgCache::Dep::PreDepends)
+ continue;
+
+ PkgIterator BrokenPkg = Broken.ParentPkg();
+ // uninstalled packages can't break via a remove
+ if (BrokenPkg->CurrentVer == 0)
+ continue;
+
+ // if its already added, we can't do anything useful
+ if (IsFlag(BrokenPkg, AddPending) == true || IsFlag(BrokenPkg, Added) == true)
+ continue;
+
+ // if the dependee is going to be removed, visit it now
+ if (Cache[BrokenPkg].Delete() == true)
+ return VisitNode(BrokenPkg, "Remove-Dependee");
+
+ // The package stays around, so find out how this is possible
+ for (DepIterator D = BrokenPkg.CurrentVer().DependsList(); D.end() == false;)
{
- // Duplication elimination, consider the current version only
- if (D.ParentPkg().CurrentVer() != D.ParentVer())
+ // only important or-groups need fixing
+ if (D->Type != pkgCache::Dep::Depends &&
+ D->Type != pkgCache::Dep::PreDepends)
+ {
+ ++D;
continue;
+ }
- /* We wish to see if the dep on the parent package is okay
- in the removed (install) state of the target pkg. */
- if (CheckDep(D) == true)
+ // Start is the beginning of the or-group, D is the first one after or
+ DepIterator Start = D;
+ bool foundBroken = false;
+ for (bool LastOR = true; D.end() == false && LastOR == true; ++D)
{
- // We want to catch loops with the code below.
- if (IsFlag(D.ParentPkg(),AddPending) == false)
- continue;
+ LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
+ if (D == Broken)
+ foundBroken = true;
}
- // This is the loop detection
- if (IsFlag(D.ParentPkg(),Added) == true ||
- IsFlag(D.ParentPkg(),AddPending) == true)
- {
- if (IsFlag(D.ParentPkg(),AddPending) == true)
- AddLoop(D);
+ // this or-group isn't the broken one: keep searching
+ if (foundBroken == false)
continue;
+
+ // iterate over all members of the or-group searching for a ready replacement
+ bool readyReplacement = false;
+ for (DepIterator OrMember = Start; OrMember != D && readyReplacement == false; ++OrMember)
+ {
+ Version ** Replacements = OrMember.AllTargets();
+ for (Version **R = Replacements; *R != 0; ++R)
+ {
+ VerIterator Ver(Cache,*R);
+ // only currently installed packages can be a replacement
+ PkgIterator RPkg = Ver.ParentPkg();
+ if (RPkg.CurrentVer() != Ver)
+ continue;
+
+ // packages going to be removed can't be a replacement
+ if (Cache[RPkg].Delete() == true)
+ continue;
+
+ readyReplacement = true;
+ break;
+ }
+ delete[] Replacements;
}
- // Skip over missing files
- if (IsMissing(D.ParentPkg()) == true)
+ // something else is ready to take over, do nothing
+ if (readyReplacement == true)
continue;
-
- if (VisitNode(D.ParentPkg()) == false)
+
+ // see if we can visit a replacement
+ bool visitReplacement = false;
+ for (DepIterator OrMember = Start; OrMember != D && visitReplacement == false; ++OrMember)
+ {
+ Version ** Replacements = OrMember.AllTargets();
+ for (Version **R = Replacements; *R != 0; ++R)
+ {
+ VerIterator Ver(Cache,*R);
+ // consider only versions we plan to install
+ PkgIterator RPkg = Ver.ParentPkg();
+ if (Cache[RPkg].Install() == false || Cache[RPkg].InstallVer != Ver)
+ continue;
+
+ // loops are not going to help us, so don't create them
+ if (IsFlag(RPkg, AddPending) == true)
+ continue;
+
+ if (IsMissing(RPkg) == true)
+ continue;
+
+ visitReplacement = true;
+ if (IsFlag(BrokenPkg, Immediate) == false)
+ {
+ if (VisitNode(RPkg, "Remove-Rep") == true)
+ break;
+ }
+ else
+ {
+ Flag(RPkg, Immediate);
+ if (VisitNode(RPkg, "Remove-ImmRep") == true)
+ break;
+ }
+ visitReplacement = false;
+ }
+ delete[] Replacements;
+ }
+ if (visitReplacement == true)
+ continue;
+
+ // the broken package in current version can't be fixed, so install new version
+ if (IsMissing(BrokenPkg) == true)
+ break;
+
+ if (VisitNode(BrokenPkg, "Remove-Upgrade") == false)
return false;
}
-
+ }
+
return true;
}
/*}}}*/
-
// OrderList::AddLoop - Add a loop to the loop list /*{{{*/
// ---------------------------------------------------------------------
/* We record the loops. This is a relic since loop breaking is done
Loops[LoopCount++] = D;
// Mark the packages as being part of a loop.
- Flag(D.TargetPkg(),Loop);
- Flag(D.ParentPkg(),Loop);
+ //Flag(D.TargetPkg(),Loop);
+ //Flag(D.ParentPkg(),Loop);
+ /* This is currently disabled because the Loop flag is being used for
+ loop management in the package manager. Check the orderlist.h file for more info */
return true;
}
/*}}}*/
/* Conflicts requires that all versions are not present, depends
just needs one */
- if (D->Type != pkgCache::Dep::Conflicts &&
- D->Type != pkgCache::Dep::DpkgBreaks &&
- D->Type != pkgCache::Dep::Obsoletes)
+ if (D.IsNegative() == false)
{
+ // ignore provides by older versions of this package
+ if (((D.Reverse() == false && Pkg == D.ParentPkg()) ||
+ (D.Reverse() == true && Pkg == D.TargetPkg())) &&
+ Cache[Pkg].InstallVer != *I)
+ continue;
+
/* Try to find something that does not have the after flag set
if at all possible */
if (IsFlag(Pkg,After) == true)
projects / apt.git / blobdiff