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 arbitary 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 /*{{{*/
67 #pragma implementation "apt-pkg/orderlist.h"
69 #include <apt-pkg/orderlist.h>
70 #include <apt-pkg/depcache.h>
71 #include <apt-pkg/error.h>
72 #include <apt-pkg/version.h>
73 #include <apt-pkg/sptr.h>
74 #include <apt-pkg/configuration.h>
81 pkgOrderList
*pkgOrderList::Me
= 0;
83 // OrderList::pkgOrderList - Constructor /*{{{*/
84 // ---------------------------------------------------------------------
86 pkgOrderList::pkgOrderList(pkgDepCache
*pCache
) : Cache(*pCache
)
94 Debug
= _config
->FindB("Debug::pkgOrderList",false);
96 /* Construct the arrays, egcs 1.0.1 bug requires the package count
98 unsigned long Size
= Cache
.Head().PackageCount
;
99 Flags
= new unsigned short[Size
];
100 End
= List
= new Package
*[Size
];
101 memset(Flags
,0,sizeof(*Flags
)*Size
);
104 // OrderList::~pkgOrderList - Destructor /*{{{*/
105 // ---------------------------------------------------------------------
107 pkgOrderList::~pkgOrderList()
113 // OrderList::IsMissing - Check if a file is missing /*{{{*/
114 // ---------------------------------------------------------------------
116 bool pkgOrderList::IsMissing(PkgIterator Pkg
)
118 // Skip packages to erase
119 if (Cache
[Pkg
].Delete() == true)
122 // Skip Packages that need configure only.
123 if (Pkg
.State() == pkgCache::PkgIterator::NeedsConfigure
&&
124 Cache
[Pkg
].Keep() == true)
130 if (FileList
[Pkg
->ID
].empty() == false)
136 // OrderList::DoRun - Does an order run /*{{{*/
137 // ---------------------------------------------------------------------
138 /* The caller is expeted to have setup the desired probe state */
139 bool pkgOrderList::DoRun()
142 unsigned long Size
= Cache
.Head().PackageCount
;
143 SPtrArray
<Package
*> NList
= new Package
*[Size
];
144 SPtrArray
<Package
*> AfterList
= new Package
*[Size
];
145 AfterEnd
= AfterList
;
148 WipeFlags(Added
| AddPending
| Loop
| InList
);
150 for (iterator I
= List
; I
!= End
; I
++)
153 // Rebuild the main list into the temp list.
154 iterator OldEnd
= End
;
156 for (iterator I
= List
; I
!= OldEnd
; I
++)
157 if (VisitNode(PkgIterator(Cache
,*I
)) == false)
163 // Copy the after list to the end of the main list
164 for (Package
**I
= AfterList
; I
!= AfterEnd
; I
++)
167 // Swap the main list to the new list
169 List
= NList
.UnGuard();
173 // OrderList::OrderCritical - Perform critical unpacking ordering /*{{{*/
174 // ---------------------------------------------------------------------
175 /* This performs predepends and immediate configuration ordering only.
176 This is termed critical unpacking ordering. Any loops that form are
177 fatal and indicate that the packages cannot be installed. */
178 bool pkgOrderList::OrderCritical()
182 Primary
= &pkgOrderList::DepUnPackPre
;
190 qsort(List
,End
- List
,sizeof(*List
),&OrderCompareB
);
192 if (DoRun() == false)
196 return _error
->Error("Fatal, predepends looping detected");
200 // OrderList::OrderUnpack - Perform complete unpacking ordering /*{{{*/
201 // ---------------------------------------------------------------------
202 /* This performs complete unpacking ordering and creates an order that is
203 suitable for unpacking */
204 bool pkgOrderList::OrderUnpack(string
*FileList
)
206 this->FileList
= FileList
;
208 // Setup the after flags
213 // Set the inlist flag
214 for (iterator I
= List
; I
!= End
; I
++)
216 PkgIterator
P(Cache
,*I
);
217 if (IsMissing(P
) == true && IsNow(P
) == true)
222 Primary
= &pkgOrderList::DepUnPackCrit
;
223 Secondary
= &pkgOrderList::DepConfigure
;
224 RevDepends
= &pkgOrderList::DepUnPackDep
;
225 Remove
= &pkgOrderList::DepRemove
;
230 qsort(List
,End
- List
,sizeof(*List
),&OrderCompareA
);
233 clog
<< "** Pass A" << endl
;
234 if (DoRun() == false)
238 clog
<< "** Pass B" << endl
;
240 if (DoRun() == false)
244 clog
<< "** Pass C" << endl
;
247 Remove
= 0; // Otherwise the libreadline remove problem occures
248 if (DoRun() == false)
252 clog
<< "** Pass D" << endl
;
254 Primary
= &pkgOrderList::DepUnPackPre
;
255 if (DoRun() == false)
260 clog
<< "** Unpack ordering done" << endl
;
262 for (iterator I
= List
; I
!= End
; I
++)
264 PkgIterator
P(Cache
,*I
);
265 if (IsNow(P
) == true)
266 clog
<< P
.Name() << ' ' << IsMissing(P
) << ',' << IsFlag(P
,After
) << endl
;
273 // OrderList::OrderConfigure - Perform configuration ordering /*{{{*/
274 // ---------------------------------------------------------------------
275 /* This orders by depends only and produces an order which is suitable
277 bool pkgOrderList::OrderConfigure()
280 Primary
= &pkgOrderList::DepConfigure
;
289 // OrderList::Score - Score the package for sorting /*{{{*/
290 // ---------------------------------------------------------------------
291 /* Higher scores order earlier */
292 int pkgOrderList::Score(PkgIterator Pkg
)
294 // Removal is always done first
295 if (Cache
[Pkg
].Delete() == true)
298 // This should never happen..
299 if (Cache
[Pkg
].InstVerIter(Cache
).end() == true)
303 if ((Pkg
->Flags
& pkgCache::Flag::Essential
) == pkgCache::Flag::Essential
)
306 if (IsFlag(Pkg
,Immediate
) == true)
309 for (DepIterator D
= Cache
[Pkg
].InstVerIter(Cache
).DependsList();
310 D
.end() == false; D
++)
311 if (D
->Type
== pkgCache::Dep::PreDepends
)
317 // Important Required Standard Optional Extra
318 signed short PrioMap
[] = {0,5,4,3,1,0};
319 if (Cache
[Pkg
].InstVerIter(Cache
)->Priority
<= 5)
320 Score
+= PrioMap
[Cache
[Pkg
].InstVerIter(Cache
)->Priority
];
324 // OrderList::FileCmp - Compare by package file /*{{{*/
325 // ---------------------------------------------------------------------
326 /* This compares by the package file that the install version is in. */
327 int pkgOrderList::FileCmp(PkgIterator A
,PkgIterator B
)
329 if (Cache
[A
].Delete() == true && Cache
[B
].Delete() == true)
331 if (Cache
[A
].Delete() == true)
333 if (Cache
[B
].Delete() == true)
336 if (Cache
[A
].InstVerIter(Cache
).FileList().end() == true)
338 if (Cache
[B
].InstVerIter(Cache
).FileList().end() == true)
341 pkgCache::PackageFile
*FA
= Cache
[A
].InstVerIter(Cache
).FileList().File();
342 pkgCache::PackageFile
*FB
= Cache
[B
].InstVerIter(Cache
).FileList().File();
350 // BoolCompare - Comparison function for two booleans /*{{{*/
351 // ---------------------------------------------------------------------
353 static int BoolCompare(bool A
,bool B
)
362 // OrderList::OrderCompareA - Order the installation by op /*{{{*/
363 // ---------------------------------------------------------------------
364 /* This provides a first-pass sort of the list and gives a decent starting
365 point for further complete ordering. It is used by OrderUnpack only */
366 int pkgOrderList::OrderCompareA(const void *a
, const void *b
)
368 PkgIterator
A(Me
->Cache
,*(Package
**)a
);
369 PkgIterator
B(Me
->Cache
,*(Package
**)b
);
371 // We order packages with a set state toward the front
373 if ((Res
= BoolCompare(Me
->IsNow(A
),Me
->IsNow(B
))) != 0)
376 // We order missing files to toward the end
377 /* if (Me->FileList != 0)
379 if ((Res = BoolCompare(Me->IsMissing(A),
380 Me->IsMissing(B))) != 0)
384 if (A
.State() != pkgCache::PkgIterator::NeedsNothing
&&
385 B
.State() == pkgCache::PkgIterator::NeedsNothing
)
388 if (A
.State() == pkgCache::PkgIterator::NeedsNothing
&&
389 B
.State() != pkgCache::PkgIterator::NeedsNothing
)
392 int ScoreA
= Me
->Score(A
);
393 int ScoreB
= Me
->Score(B
);
400 return strcmp(A
.Name(),B
.Name());
403 // OrderList::OrderCompareB - Order the installation by source /*{{{*/
404 // ---------------------------------------------------------------------
405 /* This orders by installation source. This is useful to handle
406 inter-source breaks */
407 int pkgOrderList::OrderCompareB(const void *a
, const void *b
)
409 PkgIterator
A(Me
->Cache
,*(Package
**)a
);
410 PkgIterator
B(Me
->Cache
,*(Package
**)b
);
412 if (A
.State() != pkgCache::PkgIterator::NeedsNothing
&&
413 B
.State() == pkgCache::PkgIterator::NeedsNothing
)
416 if (A
.State() == pkgCache::PkgIterator::NeedsNothing
&&
417 B
.State() != pkgCache::PkgIterator::NeedsNothing
)
420 int F
= Me
->FileCmp(A
,B
);
428 int ScoreA
= Me
->Score(A
);
429 int ScoreB
= Me
->Score(B
);
436 return strcmp(A
.Name(),B
.Name());
440 // OrderList::VisitDeps - Visit forward install dependencies /*{{{*/
441 // ---------------------------------------------------------------------
442 /* This calls the dependency function for the normal forwards dependencies
444 bool pkgOrderList::VisitDeps(DepFunc F
,PkgIterator Pkg
)
446 if (F
== 0 || Pkg
.end() == true || Cache
[Pkg
].InstallVer
== 0)
449 return (this->*F
)(Cache
[Pkg
].InstVerIter(Cache
).DependsList());
452 // OrderList::VisitRDeps - Visit reverse dependencies /*{{{*/
453 // ---------------------------------------------------------------------
454 /* This calls the dependency function for all of the normal reverse depends
456 bool pkgOrderList::VisitRDeps(DepFunc F
,PkgIterator Pkg
)
458 if (F
== 0 || Pkg
.end() == true)
461 return (this->*F
)(Pkg
.RevDependsList());
464 // OrderList::VisitRProvides - Visit provides reverse dependencies /*{{{*/
465 // ---------------------------------------------------------------------
466 /* This calls the dependency function for all reverse dependencies
467 generated by the provides line on the package. */
468 bool pkgOrderList::VisitRProvides(DepFunc F
,VerIterator Ver
)
470 if (F
== 0 || Ver
.end() == true)
474 for (PrvIterator P
= Ver
.ProvidesList(); P
.end() == false; P
++)
475 Res
&= (this->*F
)(P
.ParentPkg().RevDependsList());
479 // OrderList::VisitProvides - Visit all of the providing packages /*{{{*/
480 // ---------------------------------------------------------------------
481 /* This routine calls visit on all providing packages. */
482 bool pkgOrderList::VisitProvides(DepIterator D
,bool Critical
)
484 SPtrArray
<Version
*> List
= D
.AllTargets();
485 for (Version
**I
= List
; *I
!= 0; I
++)
487 VerIterator
Ver(Cache
,*I
);
488 PkgIterator Pkg
= Ver
.ParentPkg();
490 if (Cache
[Pkg
].Keep() == true && Pkg
.State() == PkgIterator::NeedsNothing
)
493 if (D
->Type
!= pkgCache::Dep::Conflicts
&&
494 D
->Type
!= pkgCache::Dep::Obsoletes
&&
495 Cache
[Pkg
].InstallVer
!= *I
)
498 if ((D
->Type
== pkgCache::Dep::Conflicts
||
499 D
->Type
== pkgCache::Dep::Obsoletes
) &&
500 (Version
*)Pkg
.CurrentVer() != *I
)
503 // Skip over missing files
504 if (Critical
== false && IsMissing(D
.ParentPkg()) == true)
507 if (VisitNode(Pkg
) == false)
513 // OrderList::VisitNode - Recursive ordering director /*{{{*/
514 // ---------------------------------------------------------------------
515 /* This is the core ordering routine. It calls the set dependency
516 consideration functions which then potentialy call this again. Finite
517 depth is achived through the colouring mechinism. */
518 bool pkgOrderList::VisitNode(PkgIterator Pkg
)
520 // Looping or irrelevent.
521 // This should probably trancend not installed packages
522 if (Pkg
.end() == true || IsFlag(Pkg
,Added
) == true ||
523 IsFlag(Pkg
,AddPending
) == true || IsFlag(Pkg
,InList
) == false)
528 for (int j
= 0; j
!= Depth
; j
++) clog
<< ' ';
529 clog
<< "Visit " << Pkg
.Name() << endl
;
535 Flag(Pkg
,AddPending
);
537 DepFunc Old
= Primary
;
539 // Perform immedate configuration of the package if so flagged.
540 if (IsFlag(Pkg
,Immediate
) == true && Primary
!= &pkgOrderList::DepUnPackPre
)
541 Primary
= &pkgOrderList::DepUnPackPreD
;
543 if (IsNow(Pkg
) == true)
546 if (Cache
[Pkg
].Delete() == false)
549 Res
&= Res
&& VisitDeps(Primary
,Pkg
);
550 Res
&= Res
&& VisitRDeps(Primary
,Pkg
);
551 Res
&= Res
&& VisitRProvides(Primary
,Pkg
.CurrentVer());
552 Res
&= Res
&& VisitRProvides(Primary
,Cache
[Pkg
].InstVerIter(Cache
));
555 Res
&= Res
&& VisitRDeps(RevDepends
,Pkg
);
556 Res
&= Res
&& VisitRProvides(RevDepends
,Pkg
.CurrentVer());
557 Res
&= Res
&& VisitRProvides(RevDepends
,Cache
[Pkg
].InstVerIter(Cache
));
560 Res
&= Res
&& VisitDeps(Secondary
,Pkg
);
561 Res
&= Res
&& VisitRDeps(Secondary
,Pkg
);
562 Res
&= Res
&& VisitRProvides(Secondary
,Pkg
.CurrentVer());
563 Res
&= Res
&& VisitRProvides(Secondary
,Cache
[Pkg
].InstVerIter(Cache
));
568 Res
&= Res
&& VisitRDeps(Remove
,Pkg
);
569 Res
&= Res
&& VisitRProvides(Remove
,Pkg
.CurrentVer());
573 if (IsFlag(Pkg
,Added
) == false)
575 Flag(Pkg
,Added
,Added
| AddPending
);
576 if (IsFlag(Pkg
,After
) == true)
587 for (int j
= 0; j
!= Depth
; j
++) clog
<< ' ';
588 clog
<< "Leave " << Pkg
.Name() << ' ' << IsFlag(Pkg
,Added
) << ',' << IsFlag(Pkg
,AddPending
) << endl
;
595 // OrderList::DepUnPackCrit - Critical UnPacking ordering /*{{{*/
596 // ---------------------------------------------------------------------
597 /* Critical unpacking ordering strives to satisfy Conflicts: and
598 PreDepends: only. When a prdepends is encountered the Primary
599 DepFunc is changed to be DepUnPackPreD.
601 Loops are preprocessed and logged. */
602 bool pkgOrderList::DepUnPackCrit(DepIterator D
)
604 for (; D
.end() == false; D
++)
606 if (D
.Reverse() == true)
608 /* Reverse depenanices are only interested in conflicts,
609 predepend breakage is ignored here */
610 if (D
->Type
!= pkgCache::Dep::Conflicts
&&
611 D
->Type
!= pkgCache::Dep::Obsoletes
)
614 // Duplication elimination, consider only the current version
615 if (D
.ParentPkg().CurrentVer() != D
.ParentVer())
618 /* For reverse dependencies we wish to check if the
619 dependency is satisifed in the install state. The
620 target package (caller) is going to be in the installed
622 if (CheckDep(D
) == true)
625 if (VisitNode(D
.ParentPkg()) == false)
630 /* Forward critical dependencies MUST be correct before the
631 package can be unpacked. */
632 if (D
->Type
!= pkgCache::Dep::Conflicts
&&
633 D
->Type
!= pkgCache::Dep::Obsoletes
&&
634 D
->Type
!= pkgCache::Dep::PreDepends
)
637 /* We wish to check if the dep is okay in the now state of the
638 target package against the install state of this package. */
639 if (CheckDep(D
) == true)
641 /* We want to catch predepends loops with the code below.
642 Conflicts loops that are Dep OK are ignored */
643 if (IsFlag(D
.TargetPkg(),AddPending
) == false ||
644 D
->Type
!= pkgCache::Dep::PreDepends
)
648 // This is the loop detection
649 if (IsFlag(D
.TargetPkg(),Added
) == true ||
650 IsFlag(D
.TargetPkg(),AddPending
) == true)
652 if (IsFlag(D
.TargetPkg(),AddPending
) == true)
657 /* Predepends require a special ordering stage, they must have
658 all dependents installed as well */
659 DepFunc Old
= Primary
;
661 if (D
->Type
== pkgCache::Dep::PreDepends
)
662 Primary
= &pkgOrderList::DepUnPackPreD
;
663 Res
= VisitProvides(D
,true);
672 // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends /*{{{*/
673 // ---------------------------------------------------------------------
674 /* Critical PreDepends (also configure immediate and essential) strives to
675 ensure not only that all conflicts+predepends are met but that this
676 package will be immediately configurable when it is unpacked.
678 Loops are preprocessed and logged. */
679 bool pkgOrderList::DepUnPackPreD(DepIterator D
)
681 if (D
.Reverse() == true)
682 return DepUnPackCrit(D
);
684 for (; D
.end() == false; D
++)
686 if (D
.IsCritical() == false)
689 /* We wish to check if the dep is okay in the now state of the
690 target package against the install state of this package. */
691 if (CheckDep(D
) == true)
693 /* We want to catch predepends loops with the code below.
694 Conflicts loops that are Dep OK are ignored */
695 if (IsFlag(D
.TargetPkg(),AddPending
) == false ||
696 D
->Type
!= pkgCache::Dep::PreDepends
)
700 // This is the loop detection
701 if (IsFlag(D
.TargetPkg(),Added
) == true ||
702 IsFlag(D
.TargetPkg(),AddPending
) == true)
704 if (IsFlag(D
.TargetPkg(),AddPending
) == true)
709 if (VisitProvides(D
,true) == false)
715 // OrderList::DepUnPackPre - Critical Predepends ordering /*{{{*/
716 // ---------------------------------------------------------------------
717 /* Critical PreDepends (also configure immediate and essential) strives to
718 ensure not only that all conflicts+predepends are met but that this
719 package will be immediately configurable when it is unpacked.
721 Loops are preprocessed and logged. All loops will be fatal. */
722 bool pkgOrderList::DepUnPackPre(DepIterator D
)
724 if (D
.Reverse() == true)
727 for (; D
.end() == false; D
++)
729 /* Only consider the PreDepends or Depends. Depends are only
730 considered at the lowest depth or in the case of immediate
732 if (D
->Type
!= pkgCache::Dep::PreDepends
)
734 if (D
->Type
== pkgCache::Dep::Depends
)
736 if (Depth
== 1 && IsFlag(D
.ParentPkg(),Immediate
) == false)
743 /* We wish to check if the dep is okay in the now state of the
744 target package against the install state of this package. */
745 if (CheckDep(D
) == true)
747 /* We want to catch predepends loops with the code below.
748 Conflicts loops that are Dep OK are ignored */
749 if (IsFlag(D
.TargetPkg(),AddPending
) == false)
753 // This is the loop detection
754 if (IsFlag(D
.TargetPkg(),Added
) == true ||
755 IsFlag(D
.TargetPkg(),AddPending
) == true)
757 if (IsFlag(D
.TargetPkg(),AddPending
) == true)
762 if (VisitProvides(D
,true) == false)
768 // OrderList::DepUnPackDep - Reverse dependency considerations /*{{{*/
769 // ---------------------------------------------------------------------
770 /* Reverse dependencies are considered to determine if unpacking this
771 package will break any existing dependencies. If so then those
772 packages are ordered before this one so that they are in the
775 The forwards depends loop is designed to bring the packages dependents
776 close to the package. This helps reduce deconfigure time.
778 Loops are irrelevent to this. */
779 bool pkgOrderList::DepUnPackDep(DepIterator D
)
782 for (; D
.end() == false; D
++)
783 if (D
.IsCritical() == true)
785 if (D
.Reverse() == true)
787 /* Duplication prevention. We consider rev deps only on
788 the current version, a not installed package
790 if (D
.ParentPkg()->CurrentVer
== 0 ||
791 D
.ParentPkg().CurrentVer() != D
.ParentVer())
794 // The dep will not break so it is irrelevent.
795 if (CheckDep(D
) == true)
798 // Skip over missing files
799 if (IsMissing(D
.ParentPkg()) == true)
802 if (VisitNode(D
.ParentPkg()) == false)
806 if (D
->Type
== pkgCache::Dep::Depends
)
807 if (VisitProvides(D
,false) == false)
813 // OrderList::DepConfigure - Configuration ordering /*{{{*/
814 // ---------------------------------------------------------------------
815 /* Configuration only ordering orders by the Depends: line only. It
816 orders configuration so that when a package comes to be configured it's
817 dependents are configured.
819 Loops are ingored. Depends loop entry points are chaotic. */
820 bool pkgOrderList::DepConfigure(DepIterator D
)
822 // Never consider reverse configuration dependencies.
823 if (D
.Reverse() == true)
826 for (; D
.end() == false; D
++)
827 if (D
->Type
== pkgCache::Dep::Depends
)
828 if (VisitProvides(D
,false) == false)
833 // OrderList::DepRemove - Removal ordering /*{{{*/
834 // ---------------------------------------------------------------------
835 /* Removal visits all reverse depends. It considers if the dependency
836 of the Now state version to see if it is okay with removing this
837 package. This check should always fail, but is provided for symetery
838 with the other critical handlers.
840 Loops are preprocessed and logged. Removal loops can also be
841 detected in the critical handler. They are characterized by an
842 old version of A depending on B but the new version of A conflicting
843 with B, thus either A or B must break to install. */
844 bool pkgOrderList::DepRemove(DepIterator D
)
846 if (D
.Reverse() == false)
848 for (; D
.end() == false; D
++)
849 if (D
->Type
== pkgCache::Dep::Depends
|| D
->Type
== pkgCache::Dep::PreDepends
)
851 // Duplication elimination, consider the current version only
852 if (D
.ParentPkg().CurrentVer() != D
.ParentVer())
855 /* We wish to see if the dep on the parent package is okay
856 in the removed (install) state of the target pkg. */
857 if (CheckDep(D
) == true)
859 // We want to catch loops with the code below.
860 if (IsFlag(D
.ParentPkg(),AddPending
) == false)
864 // This is the loop detection
865 if (IsFlag(D
.ParentPkg(),Added
) == true ||
866 IsFlag(D
.ParentPkg(),AddPending
) == true)
868 if (IsFlag(D
.ParentPkg(),AddPending
) == true)
873 // Skip over missing files
874 if (IsMissing(D
.ParentPkg()) == true)
877 if (VisitNode(D
.ParentPkg()) == false)
885 // OrderList::AddLoop - Add a loop to the loop list /*{{{*/
886 // ---------------------------------------------------------------------
887 /* We record the loops. This is a relic since loop breaking is done
888 genericaly as part of the safety routines. */
889 bool pkgOrderList::AddLoop(DepIterator D
)
891 if (LoopCount
< 0 || LoopCount
>= 20)
897 if (Loops
[LoopCount
- 1].ParentPkg() == D
.ParentPkg() ||
898 Loops
[LoopCount
- 1].TargetPkg() == D
.ParentPkg())
902 Loops
[LoopCount
++] = D
;
904 // Mark the packages as being part of a loop.
905 Flag(D
.TargetPkg(),Loop
);
906 Flag(D
.ParentPkg(),Loop
);
910 // OrderList::WipeFlags - Unset the given flags from all packages /*{{{*/
911 // ---------------------------------------------------------------------
913 void pkgOrderList::WipeFlags(unsigned long F
)
915 unsigned long Size
= Cache
.Head().PackageCount
;
916 for (unsigned long I
= 0; I
!= Size
; I
++)
920 // OrderList::CheckDep - Check a dependency for truth /*{{{*/
921 // ---------------------------------------------------------------------
922 /* This performs a complete analysis of the dependency wrt to the
923 current add list. It returns true if after all events are
924 performed it is still true. This sort of routine can be approximated
925 by examining the DepCache, however in convoluted cases of provides
926 this fails to produce a suitable result. */
927 bool pkgOrderList::CheckDep(DepIterator D
)
929 SPtrArray
<Version
*> List
= D
.AllTargets();
931 for (Version
**I
= List
; *I
!= 0; I
++)
933 VerIterator
Ver(Cache
,*I
);
934 PkgIterator Pkg
= Ver
.ParentPkg();
936 /* The meaning of Added and AddPending is subtle. AddPending is
937 an indication that the package is looping. Because of the
938 way ordering works Added means the package will be unpacked
939 before this one and AddPending means after. It is therefore
940 correct to ignore AddPending in all cases, but that exposes
941 reverse-ordering loops which should be ignored. */
942 if (IsFlag(Pkg
,Added
) == true ||
943 (IsFlag(Pkg
,AddPending
) == true && D
.Reverse() == true))
945 if (Cache
[Pkg
].InstallVer
!= *I
)
949 if ((Version
*)Pkg
.CurrentVer() != *I
||
950 Pkg
.State() != PkgIterator::NeedsNothing
)
953 /* Conflicts requires that all versions are not present, depends
955 if (D
->Type
!= pkgCache::Dep::Conflicts
&&
956 D
->Type
!= pkgCache::Dep::Obsoletes
)
958 /* Try to find something that does not have the after flag set
959 if at all possible */
960 if (IsFlag(Pkg
,After
) == true)
970 if (IsFlag(Pkg
,After
) == true)
971 Flag(D
.ParentPkg(),After
);
977 // We found a hit, but it had the after flag set
978 if (Hit
== true && D
->Type
== pkgCache::Dep::PreDepends
)
980 Flag(D
.ParentPkg(),After
);
984 /* Conflicts requires that all versions are not present, depends
986 if (D
->Type
== pkgCache::Dep::Conflicts
||
987 D
->Type
== pkgCache::Dep::Obsoletes
)