#include <apt-pkg/orderlist.h>
#include <apt-pkg/depcache.h>
#include <apt-pkg/error.h>
-#include <apt-pkg/version.h>
-#include <apt-pkg/sptr.h>
#include <apt-pkg/configuration.h>
+#include <apt-pkg/cacheiterators.h>
+#include <apt-pkg/pkgcache.h>
+#include <stdlib.h>
+#include <string.h>
+#include <algorithm>
#include <iostream>
/*}}}*/
using namespace std;
-pkgOrderList *pkgOrderList::Me = 0;
-
// OrderList::pkgOrderList - Constructor /*{{{*/
// ---------------------------------------------------------------------
/* */
-pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache)
+pkgOrderList::pkgOrderList(pkgDepCache *pCache) : d(NULL), 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;
{
// Temp list
unsigned long Size = Cache.Head().PackageCount;
- SPtrArray<Package *> NList = new Package *[Size];
- SPtrArray<Package *> AfterList = new Package *[Size];
- AfterEnd = AfterList;
+ std::unique_ptr<Package *[]> NList(new Package *[Size]);
+ std::unique_ptr<Package *[]> AfterList(new Package *[Size]);
+ AfterEnd = AfterList.get();
Depth = 0;
WipeFlags(Added | AddPending | Loop | InList);
// Rebuild the main list into the temp list.
iterator OldEnd = End;
- End = NList;
+ End = NList.get();
for (iterator I = List; I != OldEnd; ++I)
if (VisitNode(PkgIterator(Cache,*I), "DoRun") == false)
{
}
// Copy the after list to the end of the main list
- for (Package **I = AfterList; I != AfterEnd; I++)
+ for (Package **I = AfterList.get(); I != AfterEnd; I++)
*End++ = *I;
// Swap the main list to the new list
delete [] List;
- List = NList.UnGuard();
+ List = NList.release();
return true;
}
/*}}}*/
LoopCount = 0;
// Sort
- Me = this;
- qsort(List,End - List,sizeof(*List),&OrderCompareB);
+ std::sort(List,End, [this](Package *a, Package *b) { return OrderCompareB(a, b) < 0; } );
if (DoRun() == false)
return false;
LoopCount = -1;
// Sort
- Me = this;
- qsort(List,End - List,sizeof(*List),&OrderCompareA);
+ std::sort(List,End, [this](Package *a, Package *b) { return OrderCompareA(a, b) < 0; });
if (Debug == true)
clog << "** Pass A" << endl;
clog << "** Pass C" << endl;
LoopCount = 0;
RevDepends = 0;
- Remove = 0; // Otherwise the libreadline remove problem occures
+ Remove = 0; // Otherwise the libreadline remove problem occurs
if (DoRun() == false)
return false;
/* Higher scores order earlier */
int pkgOrderList::Score(PkgIterator Pkg)
{
- static int const ScoreDelete = _config->FindI("OrderList::Score::Delete", 500);
-
- // 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 ScoreDelete;
break;
}
- // Important Required Standard Optional Extra
- signed short PrioMap[] = {0,5,4,3,1,0};
+ // Required Important Standard Optional Extra
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;
}
/*}}}*/
// ---------------------------------------------------------------------
/* This provides a first-pass sort of the list and gives a decent starting
point for further complete ordering. It is used by OrderUnpack only */
-int pkgOrderList::OrderCompareA(const void *a, const void *b)
+int pkgOrderList::OrderCompareA(Package *a, Package *b)
{
- PkgIterator A(Me->Cache,*(Package **)a);
- PkgIterator B(Me->Cache,*(Package **)b);
+ PkgIterator A(Cache,a);
+ PkgIterator B(Cache,b);
// We order packages with a set state toward the front
int Res;
- if ((Res = BoolCompare(Me->IsNow(A),Me->IsNow(B))) != 0)
+ if ((Res = BoolCompare(IsNow(A),IsNow(B))) != 0)
return -1*Res;
// We order missing files to toward the end
-/* if (Me->FileList != 0)
+/* if (FileList != 0)
{
- if ((Res = BoolCompare(Me->IsMissing(A),
- Me->IsMissing(B))) != 0)
+ if ((Res = BoolCompare(IsMissing(A),
+ IsMissing(B))) != 0)
return Res;
}*/
B.State() != pkgCache::PkgIterator::NeedsNothing)
return 1;
- int ScoreA = Me->Score(A);
- int ScoreB = Me->Score(B);
+ int ScoreA = Score(A);
+ int ScoreB = Score(B);
if (ScoreA > ScoreB)
return -1;
// ---------------------------------------------------------------------
/* This orders by installation source. This is useful to handle
inter-source breaks */
-int pkgOrderList::OrderCompareB(const void *a, const void *b)
+int pkgOrderList::OrderCompareB(Package *a, Package *b)
{
- PkgIterator A(Me->Cache,*(Package **)a);
- PkgIterator B(Me->Cache,*(Package **)b);
+ PkgIterator A(Cache,a);
+ PkgIterator B(Cache,b);
if (A.State() != pkgCache::PkgIterator::NeedsNothing &&
B.State() == pkgCache::PkgIterator::NeedsNothing)
B.State() != pkgCache::PkgIterator::NeedsNothing)
return 1;
- int F = Me->FileCmp(A,B);
+ int F = FileCmp(A,B);
if (F != 0)
{
if (F > 0)
return 1;
}
- int ScoreA = Me->Score(A);
- int ScoreB = Me->Score(B);
+ int ScoreA = Score(A);
+ int ScoreB = Score(B);
if (ScoreA > ScoreB)
return -1;
against it! */
bool pkgOrderList::VisitProvides(DepIterator D,bool Critical)
{
- SPtrArray<Version *> List = D.AllTargets();
- for (Version **I = List; *I != 0; ++I)
+ std::unique_ptr<Version *[]> List(D.AllTargets());
+ for (Version **I = List.get(); *I != 0; ++I)
{
VerIterator Ver(Cache,*I);
PkgIterator Pkg = Ver.ParentPkg();
}
if (D.IsNegative() == false)
return true;
- for (Version **I = List; *I != 0; ++I)
+ for (Version **I = List.get(); *I != 0; ++I)
{
VerIterator Ver(Cache,*I);
PkgIterator Pkg = Ver.ParentPkg();
// ---------------------------------------------------------------------
/* 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. */
+ depth is achieved through the colouring mechinism. */
bool pkgOrderList::VisitNode(PkgIterator Pkg, char const* from)
{
- // Looping or irrelevent.
+ // Looping or irrelevant.
// This should probably trancend not installed packages
if (Pkg.end() == true || IsFlag(Pkg,Added) == true ||
IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false)
The forwards depends loop is designed to bring the packages dependents
close to the package. This helps reduce deconfigure time.
- Loops are irrelevent to this. */
+ Loops are irrelevant to this. */
bool pkgOrderList::DepUnPackDep(DepIterator D)
{
D.ParentPkg().CurrentVer() != D.ParentVer())
continue;
- // The dep will not break so it is irrelevent.
+ // The dep will not break so it is irrelevant.
if (CheckDep(D) == true)
continue;
/*}}}*/
// 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. */
- bool tryFixDeps = false;
- 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;
}
- else
- tryFixDeps = 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;
}
- if (tryFixDeps == true)
+ // something else is ready to take over, do nothing
+ if (readyReplacement == true)
+ continue;
+
+ // see if we can visit a replacement
+ bool visitReplacement = false;
+ for (DepIterator OrMember = Start; OrMember != D && visitReplacement == false; ++OrMember)
{
- for (pkgCache::DepIterator F = D.ParentPkg().CurrentVer().DependsList();
- F.end() == false; ++F)
+ Version ** Replacements = OrMember.AllTargets();
+ for (Version **R = Replacements; *R != 0; ++R)
{
- if (F->Type != pkgCache::Dep::Depends && F->Type != pkgCache::Dep::PreDepends)
+ 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;
- // Check the Providers
- if (F.TargetPkg()->ProvidesList != 0)
- {
- pkgCache::PrvIterator Prov = F.TargetPkg().ProvidesList();
- for (; Prov.end() == false; ++Prov)
- {
- pkgCache::PkgIterator const P = Prov.OwnerPkg();
- if (IsFlag(P, InList) == true &&
- IsFlag(P, AddPending) == true &&
- IsFlag(P, Added) == false &&
- Cache[P].InstallVer == 0)
- break;
- }
- if (Prov.end() == false)
- for (pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList();
- Prv.end() == false; ++Prv)
- {
- pkgCache::PkgIterator const P = Prv.OwnerPkg();
- if (IsFlag(P, InList) == true &&
- IsFlag(P, AddPending) == false &&
- Cache[P].InstallVer != 0 &&
- VisitNode(P, "Remove-P") == true)
- {
- Flag(P, Immediate);
- tryFixDeps = false;
- break;
- }
- }
- if (tryFixDeps == false)
- break;
- }
- // Check for Or groups
- if ((F->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or)
+ if (IsMissing(RPkg) == true)
continue;
- // Lets see if the package is part of the Or group
- pkgCache::DepIterator S = F;
- for (; S.end() == false; ++S)
+
+ visitReplacement = true;
+ if (IsFlag(BrokenPkg, Immediate) == false)
{
- if (S.TargetPkg() == D.TargetPkg())
+ if (VisitNode(RPkg, "Remove-Rep") == true)
break;
- if ((S->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or ||
- CheckDep(S)) // Or group is satisfied by another package
- for (;S.end() == false; ++S);
}
- if (S.end() == true)
- continue;
- // skip to the end of the or group
- for (;S.end() == false && (S->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; ++S);
- ++S;
- // The soon to be removed is part of the Or group
- // start again in the or group and find something which will serve as replacement
- for (; F.end() == false && F != S; ++F)
+ else
{
- if (IsFlag(F.TargetPkg(), InList) == true &&
- IsFlag(F.TargetPkg(), AddPending) == false &&
- Cache[F.TargetPkg()].InstallVer != 0 &&
- VisitNode(F.TargetPkg(), "Remove-Target") == true)
- {
- Flag(F.TargetPkg(), Immediate);
- tryFixDeps = false;
+ Flag(RPkg, Immediate);
+ if (VisitNode(RPkg, "Remove-ImmRep") == true)
break;
- }
- else if (F.TargetPkg()->ProvidesList != 0)
- {
- pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList();
- for (; Prv.end() == false; ++Prv)
- {
- if (IsFlag(Prv.OwnerPkg(), InList) == true &&
- IsFlag(Prv.OwnerPkg(), AddPending) == false &&
- Cache[Prv.OwnerPkg()].InstallVer != 0 &&
- VisitNode(Prv.OwnerPkg(), "Remove-Owner") == true)
- {
- Flag(Prv.OwnerPkg(), Immediate);
- tryFixDeps = false;
- break;
- }
- }
- if (Prv.end() == false)
- break;
- }
}
- if (tryFixDeps == false)
- break;
+ visitReplacement = false;
}
+ delete[] Replacements;
}
-
- // Skip over missing files
- if (IsMissing(D.ParentPkg()) == true)
+ if (visitReplacement == true)
continue;
-
- if (VisitNode(D.ParentPkg(), "Remove-Parent") == false)
+
+ // 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;
}
/*}}}*/
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;
}
/*}}}*/
this fails to produce a suitable result. */
bool pkgOrderList::CheckDep(DepIterator D)
{
- SPtrArray<Version *> List = D.AllTargets();
+ std::unique_ptr<Version *[]> List(D.AllTargets());
bool Hit = false;
- for (Version **I = List; *I != 0; I++)
+ for (Version **I = List.get(); *I != 0; I++)
{
VerIterator Ver(Cache,*I);
PkgIterator Pkg = Ver.ParentPkg();
just needs one */
if (D.IsNegative() == false)
{
- // ignore provides by older versions of this package
+ // 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)
projects / apt.git / blobdiff