]>
git.saurik.com Git - apt.git/blob - apt-pkg/orderlist.cc
1 // -*- mode: cpp; mode: fold -*-
3 // $Id: orderlist.cc,v 1.14 2001/05/07 05:49:43 jgg Exp $
4 /* ######################################################################
6 Order List - Represents and Manipulates an ordered list of packages.
8 A list of packages can be ordered by a number of conflicting criteria
9 each given a specific priority. Each package also has a set of flags
10 indicating some useful things about it that are derived in the
11 course of sorting. The pkgPackageManager class uses this class for
12 all of it's installation ordering needs.
14 This is a modified version of Manoj's Routine B. It consists of four
15 independent ordering algorithms that can be applied at for different
16 points in the ordering. By appling progressivly fewer ordering
17 operations it is possible to give each consideration it's own
18 priority and create an order that satisfies the lowest applicable
21 The rules for unpacking ordering are:
22 1) Unpacking ignores Depends: on all packages
23 2) Unpacking requires Conflicts: on -ALL- packages to be satisfied
24 3) Unpacking requires PreDepends: on this package only to be satisfied
25 4) Removing requires that no packages depend on the package to be
28 And the rule for configuration ordering is:
29 1) Configuring requires that the Depends: of the package be satisfied
30 Conflicts+PreDepends are ignored because unpacking says they are
31 already correct [exageration, it does check but we need not be
34 And some features that are valuable for unpacking ordering.
35 f1) Unpacking a new package should advoid breaking dependencies of
37 f2) Removal should not require a force, corrolory of f1
38 f3) Unpacking should order by depends rather than fall back to random
41 Each of the features can be enabled in the sorting routine at an
42 arbitrary priority to give quite abit of control over the final unpacking
45 The rules listed above may never be violated and are called Critical.
46 When a critical rule is violated then a loop condition is recorded
47 and will have to be delt with in the caller.
49 The ordering keeps two lists, the main list and the 'After List'. The
50 purpose of the after list is to allow packages to be delayed. This is done
51 by setting the after flag on the package. Any package which requires this
52 package to be ordered before will inherit the after flag and so on. This
53 is used for CD swap ordering where all packages on a second CD have the
54 after flag set. This forces them and all their dependents to be ordered
57 There are complications in this algorithm when presented with cycles.
58 For all known practical cases it works, all cases where it doesn't work
59 is fixable by tweaking the package descriptions. However, it should be
60 possible to impove this further to make some better choices when
61 presented with cycles.
63 ##################################################################### */
65 // Include Files /*{{{*/
68 #include <apt-pkg/orderlist.h>
69 #include <apt-pkg/depcache.h>
70 #include <apt-pkg/error.h>
71 #include <apt-pkg/version.h>
72 #include <apt-pkg/sptr.h>
73 #include <apt-pkg/configuration.h>
80 pkgOrderList
*pkgOrderList::Me
= 0;
82 // OrderList::pkgOrderList - Constructor /*{{{*/
83 // ---------------------------------------------------------------------
85 pkgOrderList::pkgOrderList(pkgDepCache
*pCache
) : Cache(*pCache
),
86 Primary(NULL
), Secondary(NULL
),
87 RevDepends(NULL
), Remove(NULL
),
88 AfterEnd(NULL
), FileList(NULL
),
89 LoopCount(-1), Depth(0)
91 Debug
= _config
->FindB("Debug::pkgOrderList",false);
93 /* Construct the arrays, egcs 1.0.1 bug requires the package count
95 unsigned long Size
= Cache
.Head().PackageCount
;
96 Flags
= new unsigned short[Size
];
97 End
= List
= new Package
*[Size
];
98 memset(Flags
,0,sizeof(*Flags
)*Size
);
101 // OrderList::~pkgOrderList - Destructor /*{{{*/
102 // ---------------------------------------------------------------------
104 pkgOrderList::~pkgOrderList()
110 // OrderList::IsMissing - Check if a file is missing /*{{{*/
111 // ---------------------------------------------------------------------
113 bool pkgOrderList::IsMissing(PkgIterator Pkg
)
115 // Skip packages to erase
116 if (Cache
[Pkg
].Delete() == true)
119 // Skip Packages that need configure only.
120 if ((Pkg
.State() == pkgCache::PkgIterator::NeedsConfigure
||
121 Pkg
.State() == pkgCache::PkgIterator::NeedsNothing
) &&
122 Cache
[Pkg
].Keep() == true)
128 if (FileList
[Pkg
->ID
].empty() == false)
134 // OrderList::DoRun - Does an order run /*{{{*/
135 // ---------------------------------------------------------------------
136 /* The caller is expeted to have setup the desired probe state */
137 bool pkgOrderList::DoRun()
140 unsigned long Size
= Cache
.Head().PackageCount
;
141 SPtrArray
<Package
*> NList
= new Package
*[Size
];
142 SPtrArray
<Package
*> AfterList
= new Package
*[Size
];
143 AfterEnd
= AfterList
;
146 WipeFlags(Added
| AddPending
| Loop
| InList
);
148 for (iterator I
= List
; I
!= End
; ++I
)
151 // Rebuild the main list into the temp list.
152 iterator OldEnd
= End
;
154 for (iterator I
= List
; I
!= OldEnd
; ++I
)
155 if (VisitNode(PkgIterator(Cache
,*I
), "DoRun") == false)
161 // Copy the after list to the end of the main list
162 for (Package
**I
= AfterList
; I
!= AfterEnd
; I
++)
165 // Swap the main list to the new list
167 List
= NList
.UnGuard();
171 // OrderList::OrderCritical - Perform critical unpacking ordering /*{{{*/
172 // ---------------------------------------------------------------------
173 /* This performs predepends and immediate configuration ordering only.
174 This is termed critical unpacking ordering. Any loops that form are
175 fatal and indicate that the packages cannot be installed. */
176 bool pkgOrderList::OrderCritical()
180 Primary
= &pkgOrderList::DepUnPackPreD
;
188 qsort(List
,End
- List
,sizeof(*List
),&OrderCompareB
);
190 if (DoRun() == false)
194 return _error
->Error("Fatal, predepends looping detected");
198 clog
<< "** Critical Unpack ordering done" << endl
;
200 for (iterator I
= List
; I
!= End
; ++I
)
202 PkgIterator
P(Cache
,*I
);
203 if (IsNow(P
) == true)
204 clog
<< " " << P
.FullName() << ' ' << IsMissing(P
) << ',' << IsFlag(P
,After
) << endl
;
211 // OrderList::OrderUnpack - Perform complete unpacking ordering /*{{{*/
212 // ---------------------------------------------------------------------
213 /* This performs complete unpacking ordering and creates an order that is
214 suitable for unpacking */
215 bool pkgOrderList::OrderUnpack(string
*FileList
)
217 this->FileList
= FileList
;
219 // Setup the after flags
224 // Set the inlist flag
225 for (iterator I
= List
; I
!= End
; ++I
)
227 PkgIterator
P(Cache
,*I
);
228 if (IsMissing(P
) == true && IsNow(P
) == true)
233 Primary
= &pkgOrderList::DepUnPackCrit
;
234 Secondary
= &pkgOrderList::DepConfigure
;
235 RevDepends
= &pkgOrderList::DepUnPackDep
;
236 Remove
= &pkgOrderList::DepRemove
;
241 qsort(List
,End
- List
,sizeof(*List
),&OrderCompareA
);
244 clog
<< "** Pass A" << endl
;
245 if (DoRun() == false)
249 clog
<< "** Pass B" << endl
;
251 if (DoRun() == false)
255 clog
<< "** Pass C" << endl
;
258 Remove
= 0; // Otherwise the libreadline remove problem occures
259 if (DoRun() == false)
263 clog
<< "** Pass D" << endl
;
265 Primary
= &pkgOrderList::DepUnPackPre
;
266 if (DoRun() == false)
271 clog
<< "** Unpack ordering done" << endl
;
273 for (iterator I
= List
; I
!= End
; ++I
)
275 PkgIterator
P(Cache
,*I
);
276 if (IsNow(P
) == true)
277 clog
<< " " << P
.FullName() << ' ' << IsMissing(P
) << ',' << IsFlag(P
,After
) << endl
;
284 // OrderList::OrderConfigure - Perform configuration ordering /*{{{*/
285 // ---------------------------------------------------------------------
286 /* This orders by depends only and produces an order which is suitable
288 bool pkgOrderList::OrderConfigure()
291 Primary
= &pkgOrderList::DepConfigure
;
299 // OrderList::Score - Score the package for sorting /*{{{*/
300 // ---------------------------------------------------------------------
301 /* Higher scores order earlier */
302 int pkgOrderList::Score(PkgIterator Pkg
)
304 static int const ScoreDelete
= _config
->FindI("OrderList::Score::Delete", 500);
306 // Removal is always done first
307 if (Cache
[Pkg
].Delete() == true)
310 // This should never happen..
311 if (Cache
[Pkg
].InstVerIter(Cache
).end() == true)
314 static int const ScoreEssential
= _config
->FindI("OrderList::Score::Essential", 200);
315 static int const ScoreImmediate
= _config
->FindI("OrderList::Score::Immediate", 10);
316 static int const ScorePreDepends
= _config
->FindI("OrderList::Score::PreDepends", 50);
319 if ((Pkg
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
320 Score
+= ScoreEssential
;
322 if (IsFlag(Pkg
,Immediate
) == true)
323 Score
+= ScoreImmediate
;
325 for (DepIterator D
= Cache
[Pkg
].InstVerIter(Cache
).DependsList();
326 D
.end() == false; ++D
)
327 if (D
->Type
== pkgCache::Dep::PreDepends
)
329 Score
+= ScorePreDepends
;
333 // Important Required Standard Optional Extra
334 signed short PrioMap
[] = {0,5,4,3,1,0};
335 if (Cache
[Pkg
].InstVerIter(Cache
)->Priority
<= 5)
336 Score
+= PrioMap
[Cache
[Pkg
].InstVerIter(Cache
)->Priority
];
340 // OrderList::FileCmp - Compare by package file /*{{{*/
341 // ---------------------------------------------------------------------
342 /* This compares by the package file that the install version is in. */
343 int pkgOrderList::FileCmp(PkgIterator A
,PkgIterator B
)
345 if (Cache
[A
].Delete() == true && Cache
[B
].Delete() == true)
347 if (Cache
[A
].Delete() == true)
349 if (Cache
[B
].Delete() == true)
352 if (Cache
[A
].InstVerIter(Cache
).FileList().end() == true)
354 if (Cache
[B
].InstVerIter(Cache
).FileList().end() == true)
357 pkgCache::PackageFile
*FA
= Cache
[A
].InstVerIter(Cache
).FileList().File();
358 pkgCache::PackageFile
*FB
= Cache
[B
].InstVerIter(Cache
).FileList().File();
366 // BoolCompare - Comparison function for two booleans /*{{{*/
367 // ---------------------------------------------------------------------
369 static int BoolCompare(bool A
,bool B
)
378 // OrderList::OrderCompareA - Order the installation by op /*{{{*/
379 // ---------------------------------------------------------------------
380 /* This provides a first-pass sort of the list and gives a decent starting
381 point for further complete ordering. It is used by OrderUnpack only */
382 int pkgOrderList::OrderCompareA(const void *a
, const void *b
)
384 PkgIterator
A(Me
->Cache
,*(Package
**)a
);
385 PkgIterator
B(Me
->Cache
,*(Package
**)b
);
387 // We order packages with a set state toward the front
389 if ((Res
= BoolCompare(Me
->IsNow(A
),Me
->IsNow(B
))) != 0)
392 // We order missing files to toward the end
393 /* if (Me->FileList != 0)
395 if ((Res = BoolCompare(Me->IsMissing(A),
396 Me->IsMissing(B))) != 0)
400 if (A
.State() != pkgCache::PkgIterator::NeedsNothing
&&
401 B
.State() == pkgCache::PkgIterator::NeedsNothing
)
404 if (A
.State() == pkgCache::PkgIterator::NeedsNothing
&&
405 B
.State() != pkgCache::PkgIterator::NeedsNothing
)
408 int ScoreA
= Me
->Score(A
);
409 int ScoreB
= Me
->Score(B
);
417 return strcmp(A
.Name(),B
.Name());
420 // OrderList::OrderCompareB - Order the installation by source /*{{{*/
421 // ---------------------------------------------------------------------
422 /* This orders by installation source. This is useful to handle
423 inter-source breaks */
424 int pkgOrderList::OrderCompareB(const void *a
, const void *b
)
426 PkgIterator
A(Me
->Cache
,*(Package
**)a
);
427 PkgIterator
B(Me
->Cache
,*(Package
**)b
);
429 if (A
.State() != pkgCache::PkgIterator::NeedsNothing
&&
430 B
.State() == pkgCache::PkgIterator::NeedsNothing
)
433 if (A
.State() == pkgCache::PkgIterator::NeedsNothing
&&
434 B
.State() != pkgCache::PkgIterator::NeedsNothing
)
437 int F
= Me
->FileCmp(A
,B
);
445 int ScoreA
= Me
->Score(A
);
446 int ScoreB
= Me
->Score(B
);
454 return strcmp(A
.Name(),B
.Name());
457 // OrderList::VisitDeps - Visit forward install dependencies /*{{{*/
458 // ---------------------------------------------------------------------
459 /* This calls the dependency function for the normal forwards dependencies
461 bool pkgOrderList::VisitDeps(DepFunc F
,PkgIterator Pkg
)
463 if (F
== 0 || Pkg
.end() == true || Cache
[Pkg
].InstallVer
== 0)
466 return (this->*F
)(Cache
[Pkg
].InstVerIter(Cache
).DependsList());
469 // OrderList::VisitRDeps - Visit reverse dependencies /*{{{*/
470 // ---------------------------------------------------------------------
471 /* This calls the dependency function for all of the normal reverse depends
473 bool pkgOrderList::VisitRDeps(DepFunc F
,PkgIterator Pkg
)
475 if (F
== 0 || Pkg
.end() == true)
478 return (this->*F
)(Pkg
.RevDependsList());
481 // OrderList::VisitRProvides - Visit provides reverse dependencies /*{{{*/
482 // ---------------------------------------------------------------------
483 /* This calls the dependency function for all reverse dependencies
484 generated by the provides line on the package. */
485 bool pkgOrderList::VisitRProvides(DepFunc F
,VerIterator Ver
)
487 if (F
== 0 || Ver
.end() == true)
491 for (PrvIterator P
= Ver
.ProvidesList(); P
.end() == false; ++P
)
492 Res
&= (this->*F
)(P
.ParentPkg().RevDependsList());
496 // OrderList::VisitProvides - Visit all of the providing packages /*{{{*/
497 // ---------------------------------------------------------------------
498 /* This routine calls visit on all providing packages.
500 If the dependency is negative it first visits packages which are
501 intended to be removed and after that all other packages.
502 It does so to avoid situations in which this package is used to
503 satisfy a (or-group/provides) dependency of another package which
504 could have been satisfied also by upgrading another package -
505 otherwise we have more broken packages dpkg needs to auto-
506 deconfigure and in very complicated situations it even decides
508 bool pkgOrderList::VisitProvides(DepIterator D
,bool Critical
)
510 SPtrArray
<Version
*> List
= D
.AllTargets();
511 for (Version
**I
= List
; *I
!= 0; ++I
)
513 VerIterator
Ver(Cache
,*I
);
514 PkgIterator Pkg
= Ver
.ParentPkg();
516 if (D
.IsNegative() == true && Cache
[Pkg
].Delete() == false)
519 if (Cache
[Pkg
].Keep() == true && Pkg
.State() == PkgIterator::NeedsNothing
)
522 if (D
.IsNegative() == false &&
523 Cache
[Pkg
].InstallVer
!= *I
)
526 if (D
.IsNegative() == true &&
527 (Version
*)Pkg
.CurrentVer() != *I
)
530 // Skip over missing files
531 if (Critical
== false && IsMissing(D
.ParentPkg()) == true)
534 if (VisitNode(Pkg
, "Provides-1") == false)
537 if (D
.IsNegative() == false)
539 for (Version
**I
= List
; *I
!= 0; ++I
)
541 VerIterator
Ver(Cache
,*I
);
542 PkgIterator Pkg
= Ver
.ParentPkg();
544 if (Cache
[Pkg
].Delete() == true)
547 if (Cache
[Pkg
].Keep() == true && Pkg
.State() == PkgIterator::NeedsNothing
)
550 if ((Version
*)Pkg
.CurrentVer() != *I
)
553 // Skip over missing files
554 if (Critical
== false && IsMissing(D
.ParentPkg()) == true)
557 if (VisitNode(Pkg
, "Provides-2") == false)
564 // OrderList::VisitNode - Recursive ordering director /*{{{*/
565 // ---------------------------------------------------------------------
566 /* This is the core ordering routine. It calls the set dependency
567 consideration functions which then potentialy call this again. Finite
568 depth is achived through the colouring mechinism. */
569 bool pkgOrderList::VisitNode(PkgIterator Pkg
, char const* from
)
571 // Looping or irrelevent.
572 // This should probably trancend not installed packages
573 if (Pkg
.end() == true || IsFlag(Pkg
,Added
) == true ||
574 IsFlag(Pkg
,AddPending
) == true || IsFlag(Pkg
,InList
) == false)
579 for (int j
= 0; j
!= Depth
; j
++) clog
<< ' ';
580 clog
<< "Visit " << Pkg
.FullName() << " from " << from
<< endl
;
586 Flag(Pkg
,AddPending
);
588 DepFunc Old
= Primary
;
590 // Perform immedate configuration of the package if so flagged.
591 if (IsFlag(Pkg
,Immediate
) == true && Primary
!= &pkgOrderList::DepUnPackPre
)
592 Primary
= &pkgOrderList::DepUnPackPreD
;
594 if (IsNow(Pkg
) == true)
597 if (Cache
[Pkg
].Delete() == false)
600 Res
&= Res
&& VisitDeps(Primary
,Pkg
);
601 Res
&= Res
&& VisitRDeps(Primary
,Pkg
);
602 Res
&= Res
&& VisitRProvides(Primary
,Pkg
.CurrentVer());
603 Res
&= Res
&& VisitRProvides(Primary
,Cache
[Pkg
].InstVerIter(Cache
));
606 Res
&= Res
&& VisitRDeps(RevDepends
,Pkg
);
607 Res
&= Res
&& VisitRProvides(RevDepends
,Pkg
.CurrentVer());
608 Res
&= Res
&& VisitRProvides(RevDepends
,Cache
[Pkg
].InstVerIter(Cache
));
611 Res
&= Res
&& VisitDeps(Secondary
,Pkg
);
612 Res
&= Res
&& VisitRDeps(Secondary
,Pkg
);
613 Res
&= Res
&& VisitRProvides(Secondary
,Pkg
.CurrentVer());
614 Res
&= Res
&& VisitRProvides(Secondary
,Cache
[Pkg
].InstVerIter(Cache
));
619 Res
&= Res
&& VisitRDeps(Remove
,Pkg
);
620 Res
&= Res
&& VisitRProvides(Remove
,Pkg
.CurrentVer());
624 if (IsFlag(Pkg
,Added
) == false)
626 Flag(Pkg
,Added
,Added
| AddPending
);
627 if (IsFlag(Pkg
,After
) == true)
638 for (int j
= 0; j
!= Depth
; j
++) clog
<< ' ';
639 clog
<< "Leave " << Pkg
.FullName() << ' ' << IsFlag(Pkg
,Added
) << ',' << IsFlag(Pkg
,AddPending
) << endl
;
645 // OrderList::DepUnPackCrit - Critical UnPacking ordering /*{{{*/
646 // ---------------------------------------------------------------------
647 /* Critical unpacking ordering strives to satisfy Conflicts: and
648 PreDepends: only. When a prdepends is encountered the Primary
649 DepFunc is changed to be DepUnPackPreD.
651 Loops are preprocessed and logged. */
652 bool pkgOrderList::DepUnPackCrit(DepIterator D
)
654 for (; D
.end() == false; ++D
)
656 if (D
.Reverse() == true)
658 /* Reverse depenanices are only interested in conflicts,
659 predepend breakage is ignored here */
660 if (D
->Type
!= pkgCache::Dep::Conflicts
&&
661 D
->Type
!= pkgCache::Dep::Obsoletes
)
664 // Duplication elimination, consider only the current version
665 if (D
.ParentPkg().CurrentVer() != D
.ParentVer())
668 /* For reverse dependencies we wish to check if the
669 dependency is satisifed in the install state. The
670 target package (caller) is going to be in the installed
672 if (CheckDep(D
) == true)
675 if (VisitNode(D
.ParentPkg(), "UnPackCrit") == false)
680 /* Forward critical dependencies MUST be correct before the
681 package can be unpacked. */
682 if (D
.IsNegative() == false &&
683 D
->Type
!= pkgCache::Dep::PreDepends
)
686 /* We wish to check if the dep is okay in the now state of the
687 target package against the install state of this package. */
688 if (CheckDep(D
) == true)
690 /* We want to catch predepends loops with the code below.
691 Conflicts loops that are Dep OK are ignored */
692 if (IsFlag(D
.TargetPkg(),AddPending
) == false ||
693 D
->Type
!= pkgCache::Dep::PreDepends
)
697 // This is the loop detection
698 if (IsFlag(D
.TargetPkg(),Added
) == true ||
699 IsFlag(D
.TargetPkg(),AddPending
) == true)
701 if (IsFlag(D
.TargetPkg(),AddPending
) == true)
706 /* Predepends require a special ordering stage, they must have
707 all dependents installed as well */
708 DepFunc Old
= Primary
;
710 if (D
->Type
== pkgCache::Dep::PreDepends
)
711 Primary
= &pkgOrderList::DepUnPackPreD
;
712 Res
= VisitProvides(D
,true);
721 // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends /*{{{*/
722 // ---------------------------------------------------------------------
723 /* Critical PreDepends (also configure immediate and essential) strives to
724 ensure not only that all conflicts+predepends are met but that this
725 package will be immediately configurable when it is unpacked.
726 Loops are preprocessed and logged. */
727 bool pkgOrderList::DepUnPackPreD(DepIterator D
)
729 if (D
.Reverse() == true)
730 return DepUnPackCrit(D
);
732 for (; D
.end() == false; ++D
)
734 if (D
.IsCritical() == false)
737 /* We wish to check if the dep is okay in the now state of the
738 target package against the install state of this package. */
739 if (CheckDep(D
) == true)
741 /* We want to catch predepends loops with the code below.
742 Conflicts loops that are Dep OK are ignored */
743 if (IsFlag(D
.TargetPkg(),AddPending
) == false ||
744 D
->Type
!= pkgCache::Dep::PreDepends
)
748 // This is the loop detection
749 if (IsFlag(D
.TargetPkg(),Added
) == true ||
750 IsFlag(D
.TargetPkg(),AddPending
) == true)
752 if (IsFlag(D
.TargetPkg(),AddPending
) == true)
757 if (VisitProvides(D
,true) == false)
763 // OrderList::DepUnPackPre - Critical Predepends ordering /*{{{*/
764 // ---------------------------------------------------------------------
765 /* Critical PreDepends (also configure immediate and essential) strives to
766 ensure not only that all conflicts+predepends are met but that this
767 package will be immediately configurable when it is unpacked.
769 Loops are preprocessed and logged. All loops will be fatal. */
770 bool pkgOrderList::DepUnPackPre(DepIterator D
)
772 if (D
.Reverse() == true)
775 for (; D
.end() == false; ++D
)
777 /* Only consider the PreDepends or Depends. Depends are only
778 considered at the lowest depth or in the case of immediate
780 if (D
->Type
!= pkgCache::Dep::PreDepends
)
782 if (D
->Type
== pkgCache::Dep::Depends
)
784 if (Depth
== 1 && IsFlag(D
.ParentPkg(),Immediate
) == false)
791 /* We wish to check if the dep is okay in the now state of the
792 target package against the install state of this package. */
793 if (CheckDep(D
) == true)
795 /* We want to catch predepends loops with the code below.
796 Conflicts loops that are Dep OK are ignored */
797 if (IsFlag(D
.TargetPkg(),AddPending
) == false)
801 // This is the loop detection
802 if (IsFlag(D
.TargetPkg(),Added
) == true ||
803 IsFlag(D
.TargetPkg(),AddPending
) == true)
805 if (IsFlag(D
.TargetPkg(),AddPending
) == true)
810 if (VisitProvides(D
,true) == false)
816 // OrderList::DepUnPackDep - Reverse dependency considerations /*{{{*/
817 // ---------------------------------------------------------------------
818 /* Reverse dependencies are considered to determine if unpacking this
819 package will break any existing dependencies. If so then those
820 packages are ordered before this one so that they are in the
823 The forwards depends loop is designed to bring the packages dependents
824 close to the package. This helps reduce deconfigure time.
826 Loops are irrelevent to this. */
827 bool pkgOrderList::DepUnPackDep(DepIterator D
)
830 for (; D
.end() == false; ++D
)
831 if (D
.IsCritical() == true)
833 if (D
.Reverse() == true)
835 /* Duplication prevention. We consider rev deps only on
836 the current version, a not installed package
838 if (D
.ParentPkg()->CurrentVer
== 0 ||
839 D
.ParentPkg().CurrentVer() != D
.ParentVer())
842 // The dep will not break so it is irrelevent.
843 if (CheckDep(D
) == true)
846 // Skip over missing files
847 if (IsMissing(D
.ParentPkg()) == true)
850 if (VisitNode(D
.ParentPkg(), "UnPackDep-Parent") == false)
855 if (D
->Type
== pkgCache::Dep::Depends
)
856 if (VisitProvides(D
,false) == false)
859 if (D
->Type
== pkgCache::Dep::DpkgBreaks
)
861 if (CheckDep(D
) == true)
864 if (VisitNode(D
.TargetPkg(), "UnPackDep-Target") == false)
872 // OrderList::DepConfigure - Configuration ordering /*{{{*/
873 // ---------------------------------------------------------------------
874 /* Configuration only ordering orders by the Depends: line only. It
875 orders configuration so that when a package comes to be configured it's
876 dependents are configured.
878 Loops are ingored. Depends loop entry points are chaotic. */
879 bool pkgOrderList::DepConfigure(DepIterator D
)
881 // Never consider reverse configuration dependencies.
882 if (D
.Reverse() == true)
885 for (; D
.end() == false; ++D
)
886 if (D
->Type
== pkgCache::Dep::Depends
)
887 if (VisitProvides(D
,false) == false)
892 // OrderList::DepRemove - Removal ordering /*{{{*/
893 // ---------------------------------------------------------------------
894 /* Removal visits all reverse depends. It considers if the dependency
895 of the Now state version to see if it is okay with removing this
896 package. This check should always fail, but is provided for symetery
897 with the other critical handlers.
899 Loops are preprocessed and logged. Removal loops can also be
900 detected in the critical handler. They are characterized by an
901 old version of A depending on B but the new version of A conflicting
902 with B, thus either A or B must break to install. */
903 bool pkgOrderList::DepRemove(DepIterator D
)
905 if (D
.Reverse() == false)
907 for (; D
.end() == false; ++D
)
908 if (D
->Type
== pkgCache::Dep::Depends
|| D
->Type
== pkgCache::Dep::PreDepends
)
910 // Duplication elimination, consider the current version only
911 if (D
.ParentPkg().CurrentVer() != D
.ParentVer())
914 /* We wish to see if the dep on the parent package is okay
915 in the removed (install) state of the target pkg. */
916 bool tryFixDeps
= false;
917 if (CheckDep(D
) == true)
919 // We want to catch loops with the code below.
920 if (IsFlag(D
.ParentPkg(),AddPending
) == false)
926 // This is the loop detection
927 if (IsFlag(D
.ParentPkg(),Added
) == true ||
928 IsFlag(D
.ParentPkg(),AddPending
) == true)
930 if (IsFlag(D
.ParentPkg(),AddPending
) == true)
935 if (tryFixDeps
== true)
937 for (pkgCache::DepIterator F
= D
.ParentPkg().CurrentVer().DependsList();
938 F
.end() == false; ++F
)
940 if (F
->Type
!= pkgCache::Dep::Depends
&& F
->Type
!= pkgCache::Dep::PreDepends
)
942 // Check the Providers
943 if (F
.TargetPkg()->ProvidesList
!= 0)
945 pkgCache::PrvIterator Prov
= F
.TargetPkg().ProvidesList();
946 for (; Prov
.end() == false; ++Prov
)
948 pkgCache::PkgIterator
const P
= Prov
.OwnerPkg();
949 if (IsFlag(P
, InList
) == true &&
950 IsFlag(P
, AddPending
) == true &&
951 IsFlag(P
, Added
) == false &&
952 Cache
[P
].InstallVer
== 0)
955 if (Prov
.end() == false)
956 for (pkgCache::PrvIterator Prv
= F
.TargetPkg().ProvidesList();
957 Prv
.end() == false; ++Prv
)
959 pkgCache::PkgIterator
const P
= Prv
.OwnerPkg();
960 if (IsFlag(P
, InList
) == true &&
961 IsFlag(P
, AddPending
) == false &&
962 Cache
[P
].InstallVer
!= 0 &&
963 VisitNode(P
, "Remove-P") == true)
970 if (tryFixDeps
== false)
974 // Check for Or groups
975 if ((F
->CompareOp
& pkgCache::Dep::Or
) != pkgCache::Dep::Or
)
977 // Lets see if the package is part of the Or group
978 pkgCache::DepIterator S
= F
;
979 for (; S
.end() == false; ++S
)
981 if (S
.TargetPkg() == D
.TargetPkg())
983 if ((S
->CompareOp
& pkgCache::Dep::Or
) != pkgCache::Dep::Or
||
984 CheckDep(S
)) // Or group is satisfied by another package
985 for (;S
.end() == false; ++S
);
989 // skip to the end of the or group
990 for (;S
.end() == false && (S
->CompareOp
& pkgCache::Dep::Or
) == pkgCache::Dep::Or
; ++S
);
992 // The soon to be removed is part of the Or group
993 // start again in the or group and find something which will serve as replacement
994 for (; F
.end() == false && F
!= S
; ++F
)
996 if (IsFlag(F
.TargetPkg(), InList
) == true &&
997 IsFlag(F
.TargetPkg(), AddPending
) == false &&
998 Cache
[F
.TargetPkg()].InstallVer
!= 0 &&
999 VisitNode(F
.TargetPkg(), "Remove-Target") == true)
1001 Flag(F
.TargetPkg(), Immediate
);
1005 else if (F
.TargetPkg()->ProvidesList
!= 0)
1007 pkgCache::PrvIterator Prv
= F
.TargetPkg().ProvidesList();
1008 for (; Prv
.end() == false; ++Prv
)
1010 if (IsFlag(Prv
.OwnerPkg(), InList
) == true &&
1011 IsFlag(Prv
.OwnerPkg(), AddPending
) == false &&
1012 Cache
[Prv
.OwnerPkg()].InstallVer
!= 0 &&
1013 VisitNode(Prv
.OwnerPkg(), "Remove-Owner") == true)
1015 Flag(Prv
.OwnerPkg(), Immediate
);
1020 if (Prv
.end() == false)
1024 if (tryFixDeps
== false)
1029 // Skip over missing files
1030 if (IsMissing(D
.ParentPkg()) == true)
1033 if (VisitNode(D
.ParentPkg(), "Remove-Parent") == false)
1040 // OrderList::AddLoop - Add a loop to the loop list /*{{{*/
1041 // ---------------------------------------------------------------------
1042 /* We record the loops. This is a relic since loop breaking is done
1043 genericaly as part of the safety routines. */
1044 bool pkgOrderList::AddLoop(DepIterator D
)
1046 if (LoopCount
< 0 || LoopCount
>= 20)
1052 if (Loops
[LoopCount
- 1].ParentPkg() == D
.ParentPkg() ||
1053 Loops
[LoopCount
- 1].TargetPkg() == D
.ParentPkg())
1057 Loops
[LoopCount
++] = D
;
1059 // Mark the packages as being part of a loop.
1060 //Flag(D.TargetPkg(),Loop);
1061 //Flag(D.ParentPkg(),Loop);
1062 /* This is currently disabled because the Loop flag is being used for
1063 loop management in the package manager. Check the orderlist.h file for more info */
1067 // OrderList::WipeFlags - Unset the given flags from all packages /*{{{*/
1068 // ---------------------------------------------------------------------
1070 void pkgOrderList::WipeFlags(unsigned long F
)
1072 unsigned long Size
= Cache
.Head().PackageCount
;
1073 for (unsigned long I
= 0; I
!= Size
; I
++)
1077 // OrderList::CheckDep - Check a dependency for truth /*{{{*/
1078 // ---------------------------------------------------------------------
1079 /* This performs a complete analysis of the dependency wrt to the
1080 current add list. It returns true if after all events are
1081 performed it is still true. This sort of routine can be approximated
1082 by examining the DepCache, however in convoluted cases of provides
1083 this fails to produce a suitable result. */
1084 bool pkgOrderList::CheckDep(DepIterator D
)
1086 SPtrArray
<Version
*> List
= D
.AllTargets();
1088 for (Version
**I
= List
; *I
!= 0; I
++)
1090 VerIterator
Ver(Cache
,*I
);
1091 PkgIterator Pkg
= Ver
.ParentPkg();
1093 /* The meaning of Added and AddPending is subtle. AddPending is
1094 an indication that the package is looping. Because of the
1095 way ordering works Added means the package will be unpacked
1096 before this one and AddPending means after. It is therefore
1097 correct to ignore AddPending in all cases, but that exposes
1098 reverse-ordering loops which should be ignored. */
1099 if (IsFlag(Pkg
,Added
) == true ||
1100 (IsFlag(Pkg
,AddPending
) == true && D
.Reverse() == true))
1102 if (Cache
[Pkg
].InstallVer
!= *I
)
1106 if ((Version
*)Pkg
.CurrentVer() != *I
||
1107 Pkg
.State() != PkgIterator::NeedsNothing
)
1110 /* Conflicts requires that all versions are not present, depends
1112 if (D
.IsNegative() == false)
1114 // ignore provides by older versions of this package
1115 if (((D
.Reverse() == false && Pkg
== D
.ParentPkg()) ||
1116 (D
.Reverse() == true && Pkg
== D
.TargetPkg())) &&
1117 Cache
[Pkg
].InstallVer
!= *I
)
1120 /* Try to find something that does not have the after flag set
1121 if at all possible */
1122 if (IsFlag(Pkg
,After
) == true)
1132 if (IsFlag(Pkg
,After
) == true)
1133 Flag(D
.ParentPkg(),After
);
1139 // We found a hit, but it had the after flag set
1140 if (Hit
== true && D
->Type
== pkgCache::Dep::PreDepends
)
1142 Flag(D
.ParentPkg(),After
);
1146 /* Conflicts requires that all versions are not present, depends
1148 if (D
->Type
== pkgCache::Dep::Conflicts
||
1149 D
->Type
== pkgCache::Dep::Obsoletes
)