- initial import of revision 374 from cnc
[apt.git] / apt-pkg / orderlist.cc
1 // -*- mode: cpp; mode: fold -*-
2 // Description                                                          /*{{{*/
3 // $Id: orderlist.cc,v 1.1 2002/07/23 17:54:50 niemeyer Exp $
4 /* ######################################################################
5
6    Order List - Represents and Manipulates an ordered list of packages.
7    
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.
13
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
19    consideration.
20    
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
26        removed.
27    
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 
32        concerned]
33
34    And some features that are valuable for unpacking ordering.
35      f1) Unpacking a new package should advoid breaking dependencies of
36          configured packages
37      f2) Removal should not require a force, corrolory of f1
38      f3) Unpacking should order by depends rather than fall back to random
39          ordering.  
40    
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
43    order.
44
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.
48
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
55    toward the end.
56    
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. 
62    
63    ##################################################################### */
64                                                                         /*}}}*/
65 // Include Files                                                        /*{{{*/
66 #ifdef __GNUG__
67 #pragma implementation "apt-pkg/orderlist.h"
68 #endif 
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>
75
76 #include <iostream>
77                                                                         /*}}}*/
78
79 using namespace std;
80
81 pkgOrderList *pkgOrderList::Me = 0;
82
83 // OrderList::pkgOrderList - Constructor                                /*{{{*/
84 // ---------------------------------------------------------------------
85 /* */
86 pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache)
87 {
88    FileList = 0;
89    Primary = 0;
90    Secondary = 0;
91    RevDepends = 0;
92    Remove = 0;
93    LoopCount = -1;
94    Debug = _config->FindB("Debug::pkgOrderList",false);
95    
96    /* Construct the arrays, egcs 1.0.1 bug requires the package count
97       hack */
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);
102 }
103                                                                         /*}}}*/
104 // OrderList::~pkgOrderList - Destructor                                /*{{{*/
105 // ---------------------------------------------------------------------
106 /* */
107 pkgOrderList::~pkgOrderList()
108 {
109    delete [] List;
110    delete [] Flags;
111 }
112                                                                         /*}}}*/
113 // OrderList::IsMissing - Check if a file is missing                    /*{{{*/
114 // ---------------------------------------------------------------------
115 /* */
116 bool pkgOrderList::IsMissing(PkgIterator Pkg) 
117 {
118    // Skip packages to erase
119    if (Cache[Pkg].Delete() == true)
120       return false;
121
122    // Skip Packages that need configure only.
123    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure && 
124        Cache[Pkg].Keep() == true)
125       return false;
126
127    if (FileList == 0)
128       return false;
129    
130    if (FileList[Pkg->ID].empty() == false)
131       return false;
132    return true;
133 }
134                                                                         /*}}}*/
135
136 // OrderList::DoRun - Does an order run                                 /*{{{*/
137 // ---------------------------------------------------------------------
138 /* The caller is expeted to have setup the desired probe state */
139 bool pkgOrderList::DoRun()
140 {   
141    // Temp list
142    unsigned long Size = Cache.Head().PackageCount;
143    SPtrArray<Package *> NList = new Package *[Size];
144    SPtrArray<Package *> AfterList = new Package *[Size];
145    AfterEnd = AfterList;
146    
147    Depth = 0;
148    WipeFlags(Added | AddPending | Loop | InList);
149
150    for (iterator I = List; I != End; I++)
151       Flag(*I,InList);
152
153    // Rebuild the main list into the temp list.
154    iterator OldEnd = End;
155    End = NList;
156    for (iterator I = List; I != OldEnd; I++)
157       if (VisitNode(PkgIterator(Cache,*I)) == false)
158       {
159          End = OldEnd;
160          return false;
161       }
162    
163    // Copy the after list to the end of the main list
164    for (Package **I = AfterList; I != AfterEnd; I++)
165       *End++ = *I;
166    
167    // Swap the main list to the new list
168    delete [] List;
169    List = NList.UnGuard();
170    return true;
171 }
172                                                                         /*}}}*/
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()
179 {
180    FileList = 0;
181    
182    Primary = &pkgOrderList::DepUnPackPre;
183    Secondary = 0;
184    RevDepends = 0;
185    Remove = 0;
186    LoopCount = 0;
187    
188    // Sort
189    Me = this;
190    qsort(List,End - List,sizeof(*List),&OrderCompareB);   
191    
192    if (DoRun() == false)
193       return false;
194    
195    if (LoopCount != 0)
196       return _error->Error("Fatal, predepends looping detected");
197    return true;
198 }
199                                                                         /*}}}*/
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)
205 {
206    this->FileList = FileList;
207
208    // Setup the after flags
209    if (FileList != 0)
210    {
211       WipeFlags(After);
212       
213       // Set the inlist flag
214       for (iterator I = List; I != End; I++)
215       {
216          PkgIterator P(Cache,*I);
217          if (IsMissing(P) == true && IsNow(P) == true)
218              Flag(*I,After);
219       }
220    }
221    
222    Primary = &pkgOrderList::DepUnPackCrit;
223    Secondary = &pkgOrderList::DepConfigure;
224    RevDepends = &pkgOrderList::DepUnPackDep;
225    Remove = &pkgOrderList::DepRemove;
226    LoopCount = -1;
227
228    // Sort
229    Me = this;
230    qsort(List,End - List,sizeof(*List),&OrderCompareA);
231
232    if (Debug == true)
233       clog << "** Pass A" << endl;
234    if (DoRun() == false)
235       return false;
236    
237    if (Debug == true)
238       clog << "** Pass B" << endl;
239    Secondary = 0;
240    if (DoRun() == false)
241       return false;
242
243    if (Debug == true)
244       clog << "** Pass C" << endl;
245    LoopCount = 0;
246    RevDepends = 0;
247    Remove = 0;             // Otherwise the libreadline remove problem occures
248    if (DoRun() == false)
249       return false;
250       
251    if (Debug == true)
252       clog << "** Pass D" << endl;
253    LoopCount = 0;
254    Primary = &pkgOrderList::DepUnPackPre;
255    if (DoRun() == false)
256       return false;
257
258    if (Debug == true)
259    {
260       clog << "** Unpack ordering done" << endl;
261
262       for (iterator I = List; I != End; I++)
263       {
264          PkgIterator P(Cache,*I);
265          if (IsNow(P) == true)
266             clog << P.Name() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl;
267       }
268    }   
269
270    return true;
271 }
272                                                                         /*}}}*/
273 // OrderList::OrderConfigure - Perform configuration ordering           /*{{{*/
274 // ---------------------------------------------------------------------
275 /* This orders by depends only and produces an order which is suitable
276    for configuration */
277 bool pkgOrderList::OrderConfigure()
278 {
279    FileList = 0;
280    Primary = &pkgOrderList::DepConfigure;
281    Secondary = 0;
282    RevDepends = 0;
283    Remove = 0;
284    LoopCount = -1;
285    return DoRun();
286 }
287                                                                         /*}}}*/
288
289 // OrderList::Score - Score the package for sorting                     /*{{{*/
290 // ---------------------------------------------------------------------
291 /* Higher scores order earlier */
292 int pkgOrderList::Score(PkgIterator Pkg)
293 {
294    // Removal is always done first
295    if (Cache[Pkg].Delete() == true)
296       return 200;
297    
298    // This should never happen..
299    if (Cache[Pkg].InstVerIter(Cache).end() == true)
300       return -1;
301    
302    int Score = 0;
303    if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
304       Score += 100;
305
306    if (IsFlag(Pkg,Immediate) == true)
307       Score += 10;
308    
309    for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); 
310         D.end() == false; D++)
311       if (D->Type == pkgCache::Dep::PreDepends)
312       {
313          Score += 50;
314          break;
315       }
316       
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];
321    return Score;
322 }
323                                                                         /*}}}*/
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)
328 {
329    if (Cache[A].Delete() == true && Cache[B].Delete() == true)
330       return 0;
331    if (Cache[A].Delete() == true)
332       return -1;
333    if (Cache[B].Delete() == true)
334       return 1;
335    
336    if (Cache[A].InstVerIter(Cache).FileList().end() == true)
337       return -1;
338    if (Cache[B].InstVerIter(Cache).FileList().end() == true)
339       return 1;
340    
341    pkgCache::PackageFile *FA = Cache[A].InstVerIter(Cache).FileList().File();
342    pkgCache::PackageFile *FB = Cache[B].InstVerIter(Cache).FileList().File();
343    if (FA < FB)
344       return -1;
345    if (FA > FB)
346       return 1;
347    return 0;
348 }
349                                                                         /*}}}*/
350 // BoolCompare - Comparison function for two booleans                   /*{{{*/
351 // ---------------------------------------------------------------------
352 /* */
353 static int BoolCompare(bool A,bool B)
354 {
355    if (A == B)
356       return 0;
357    if (A == false)
358       return -1;
359    return 1;
360 }
361                                                                         /*}}}*/
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)
367 {
368    PkgIterator A(Me->Cache,*(Package **)a);
369    PkgIterator B(Me->Cache,*(Package **)b);
370
371    // We order packages with a set state toward the front
372    int Res;
373    if ((Res = BoolCompare(Me->IsNow(A),Me->IsNow(B))) != 0)
374       return -1*Res;
375    
376    // We order missing files to toward the end
377 /*   if (Me->FileList != 0)
378    {
379       if ((Res = BoolCompare(Me->IsMissing(A),
380                              Me->IsMissing(B))) != 0)
381          return Res;
382    }*/
383    
384    if (A.State() != pkgCache::PkgIterator::NeedsNothing && 
385        B.State() == pkgCache::PkgIterator::NeedsNothing)
386       return -1;
387
388    if (A.State() == pkgCache::PkgIterator::NeedsNothing && 
389        B.State() != pkgCache::PkgIterator::NeedsNothing)
390       return 1;
391    
392    int ScoreA = Me->Score(A);
393    int ScoreB = Me->Score(B);
394    if (ScoreA > ScoreB)
395       return -1;
396    
397    if (ScoreA < ScoreB)
398       return 1;
399
400    return strcmp(A.Name(),B.Name());
401 }
402                                                                         /*}}}*/
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)
408 {
409    PkgIterator A(Me->Cache,*(Package **)a);
410    PkgIterator B(Me->Cache,*(Package **)b);
411
412    if (A.State() != pkgCache::PkgIterator::NeedsNothing && 
413        B.State() == pkgCache::PkgIterator::NeedsNothing)
414       return -1;
415
416    if (A.State() == pkgCache::PkgIterator::NeedsNothing && 
417        B.State() != pkgCache::PkgIterator::NeedsNothing)
418       return 1;
419    
420    int F = Me->FileCmp(A,B);
421    if (F != 0)
422    {
423       if (F > 0)
424          return -1;
425       return 1;
426    }
427    
428    int ScoreA = Me->Score(A);
429    int ScoreB = Me->Score(B);
430    if (ScoreA > ScoreB)
431       return -1;
432    
433    if (ScoreA < ScoreB)
434       return 1;
435
436    return strcmp(A.Name(),B.Name());
437 }
438                                                                         /*}}}*/
439
440 // OrderList::VisitDeps - Visit forward install dependencies            /*{{{*/
441 // ---------------------------------------------------------------------
442 /* This calls the dependency function for the normal forwards dependencies
443    of the package */
444 bool pkgOrderList::VisitDeps(DepFunc F,PkgIterator Pkg)
445 {
446    if (F == 0 || Pkg.end() == true || Cache[Pkg].InstallVer == 0)
447       return true;
448    
449    return (this->*F)(Cache[Pkg].InstVerIter(Cache).DependsList());
450 }
451                                                                         /*}}}*/
452 // OrderList::VisitRDeps - Visit reverse dependencies                   /*{{{*/
453 // ---------------------------------------------------------------------
454 /* This calls the dependency function for all of the normal reverse depends
455    of the package */
456 bool pkgOrderList::VisitRDeps(DepFunc F,PkgIterator Pkg)
457 {
458    if (F == 0 || Pkg.end() == true)
459       return true;
460    
461    return (this->*F)(Pkg.RevDependsList());
462 }
463                                                                         /*}}}*/
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)
469 {
470    if (F == 0 || Ver.end() == true)
471       return true;
472    
473    bool Res = true;
474    for (PrvIterator P = Ver.ProvidesList(); P.end() == false; P++)
475       Res &= (this->*F)(P.ParentPkg().RevDependsList());
476    return true;
477 }
478                                                                         /*}}}*/
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)
483 {   
484    SPtrArray<Version *> List = D.AllTargets();
485    for (Version **I = List; *I != 0; I++)
486    {
487       VerIterator Ver(Cache,*I);
488       PkgIterator Pkg = Ver.ParentPkg();
489
490       if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
491          continue;
492       
493       if (D->Type != pkgCache::Dep::Conflicts &&
494           D->Type != pkgCache::Dep::Obsoletes &&
495           Cache[Pkg].InstallVer != *I)
496          continue;
497       
498       if ((D->Type == pkgCache::Dep::Conflicts ||
499            D->Type == pkgCache::Dep::Obsoletes) &&
500           (Version *)Pkg.CurrentVer() != *I)
501          continue;
502       
503       // Skip over missing files
504       if (Critical == false && IsMissing(D.ParentPkg()) == true)
505          continue;
506
507       if (VisitNode(Pkg) == false)
508          return false;
509    }
510    return true;
511 }
512                                                                         /*}}}*/
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)
519 {
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)
524       return true;
525
526    if (Debug == true)
527    {
528       for (int j = 0; j != Depth; j++) clog << ' ';
529       clog << "Visit " << Pkg.Name() << endl;
530    }
531    
532    Depth++;
533    
534    // Color grey
535    Flag(Pkg,AddPending);
536
537    DepFunc Old = Primary;
538    
539    // Perform immedate configuration of the package if so flagged.
540    if (IsFlag(Pkg,Immediate) == true && Primary != &pkgOrderList::DepUnPackPre)
541       Primary = &pkgOrderList::DepUnPackPreD;
542
543    if (IsNow(Pkg) == true)
544    {
545       bool Res = true;
546       if (Cache[Pkg].Delete() == false)
547       {
548          // Primary
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));
553          
554          // RevDep
555          Res &= Res && VisitRDeps(RevDepends,Pkg);
556          Res &= Res && VisitRProvides(RevDepends,Pkg.CurrentVer());
557          Res &= Res && VisitRProvides(RevDepends,Cache[Pkg].InstVerIter(Cache));
558          
559          // Secondary
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));
564       }
565       else
566       { 
567          // RevDep
568          Res &= Res && VisitRDeps(Remove,Pkg);
569          Res &= Res && VisitRProvides(Remove,Pkg.CurrentVer());
570       }
571    }
572    
573    if (IsFlag(Pkg,Added) == false)
574    {
575       Flag(Pkg,Added,Added | AddPending);
576       if (IsFlag(Pkg,After) == true)
577          *AfterEnd++ = Pkg;
578       else
579          *End++ = Pkg;
580    }
581    
582    Primary = Old;
583    Depth--;
584
585    if (Debug == true)
586    {
587       for (int j = 0; j != Depth; j++) clog << ' ';
588       clog << "Leave " << Pkg.Name() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;
589    }
590    
591    return true;
592 }
593                                                                         /*}}}*/
594
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. 
600
601    Loops are preprocessed and logged. */
602 bool pkgOrderList::DepUnPackCrit(DepIterator D)
603 {
604    for (; D.end() == false; D++)
605    {
606       if (D.Reverse() == true)
607       {
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)
612             continue;
613
614          // Duplication elimination, consider only the current version
615          if (D.ParentPkg().CurrentVer() != D.ParentVer())
616             continue;
617          
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
621             state. */
622          if (CheckDep(D) == true)
623             continue;
624
625          if (VisitNode(D.ParentPkg()) == false)
626             return false;
627       }
628       else
629       {
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)
635             continue;
636                                  
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)
640          {
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)
645                continue;
646          }
647
648          // This is the loop detection
649          if (IsFlag(D.TargetPkg(),Added) == true || 
650              IsFlag(D.TargetPkg(),AddPending) == true)
651          {
652             if (IsFlag(D.TargetPkg(),AddPending) == true)
653                AddLoop(D);
654             continue;
655          }
656
657          /* Predepends require a special ordering stage, they must have
658             all dependents installed as well */
659          DepFunc Old = Primary;
660          bool Res = false;
661          if (D->Type == pkgCache::Dep::PreDepends)
662             Primary = &pkgOrderList::DepUnPackPreD;
663          Res = VisitProvides(D,true);
664          Primary = Old;
665          if (Res == false)
666             return false;
667       }  
668    }   
669    return true;
670 }
671                                                                         /*}}}*/
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. 
677
678    Loops are preprocessed and logged. */
679 bool pkgOrderList::DepUnPackPreD(DepIterator D)
680 {
681    if (D.Reverse() == true)
682       return DepUnPackCrit(D);
683    
684    for (; D.end() == false; D++)
685    {
686       if (D.IsCritical() == false)
687          continue;
688
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)
692       {
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)
697             continue;
698       }
699       
700       // This is the loop detection
701       if (IsFlag(D.TargetPkg(),Added) == true || 
702           IsFlag(D.TargetPkg(),AddPending) == true)
703       {
704          if (IsFlag(D.TargetPkg(),AddPending) == true)
705             AddLoop(D);
706          continue;
707       }
708       
709       if (VisitProvides(D,true) == false)
710          return false;
711    }   
712    return true;
713 }
714                                                                         /*}}}*/
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. 
720
721    Loops are preprocessed and logged. All loops will be fatal. */
722 bool pkgOrderList::DepUnPackPre(DepIterator D)
723 {
724    if (D.Reverse() == true)
725       return true;
726    
727    for (; D.end() == false; D++)
728    {
729       /* Only consider the PreDepends or Depends. Depends are only
730          considered at the lowest depth or in the case of immediate
731          configure */
732       if (D->Type != pkgCache::Dep::PreDepends)
733       {
734          if (D->Type == pkgCache::Dep::Depends)
735          {
736             if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false)
737                continue;
738          }
739          else
740             continue;
741       }
742       
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)
746       {
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)
750             continue;
751       }
752
753       // This is the loop detection
754       if (IsFlag(D.TargetPkg(),Added) == true || 
755           IsFlag(D.TargetPkg(),AddPending) == true)
756       {
757          if (IsFlag(D.TargetPkg(),AddPending) == true)
758             AddLoop(D);
759          continue;
760       }
761       
762       if (VisitProvides(D,true) == false)
763          return false;
764    }   
765    return true;
766 }
767                                                                         /*}}}*/
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
773    UnPacked state. 
774  
775    The forwards depends loop is designed to bring the packages dependents
776    close to the package. This helps reduce deconfigure time. 
777    
778    Loops are irrelevent to this. */
779 bool pkgOrderList::DepUnPackDep(DepIterator D)
780 {
781    
782    for (; D.end() == false; D++)
783       if (D.IsCritical() == true)
784       {
785          if (D.Reverse() == true)
786          {
787             /* Duplication prevention. We consider rev deps only on
788                the current version, a not installed package
789                cannot break */
790             if (D.ParentPkg()->CurrentVer == 0 ||
791                 D.ParentPkg().CurrentVer() != D.ParentVer())
792                continue;
793
794             // The dep will not break so it is irrelevent.
795             if (CheckDep(D) == true)
796                continue;
797             
798             // Skip over missing files
799             if (IsMissing(D.ParentPkg()) == true)
800                continue;
801             
802             if (VisitNode(D.ParentPkg()) == false)
803                return false;
804          }
805          else
806             if (D->Type == pkgCache::Dep::Depends)
807                if (VisitProvides(D,false) == false)
808                   return false;
809       }
810    return true;
811 }
812                                                                         /*}}}*/
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. 
818  
819    Loops are ingored. Depends loop entry points are chaotic. */
820 bool pkgOrderList::DepConfigure(DepIterator D)
821 {
822    // Never consider reverse configuration dependencies.
823    if (D.Reverse() == true)
824       return true;
825    
826    for (; D.end() == false; D++)
827       if (D->Type == pkgCache::Dep::Depends)
828          if (VisitProvides(D,false) == false)
829             return false;
830    return true;
831 }
832                                                                         /*}}}*/
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.
839  
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)
845 {
846    if (D.Reverse() == false)
847       return true;
848    for (; D.end() == false; D++)
849       if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
850       {
851          // Duplication elimination, consider the current version only
852          if (D.ParentPkg().CurrentVer() != D.ParentVer())
853             continue;
854
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)
858          {
859             // We want to catch loops with the code below.
860             if (IsFlag(D.ParentPkg(),AddPending) == false)
861                continue;
862          }
863
864          // This is the loop detection
865          if (IsFlag(D.ParentPkg(),Added) == true || 
866              IsFlag(D.ParentPkg(),AddPending) == true)
867          {
868             if (IsFlag(D.ParentPkg(),AddPending) == true)
869                AddLoop(D);
870             continue;
871          }
872
873          // Skip over missing files
874          if (IsMissing(D.ParentPkg()) == true)
875             continue;
876          
877          if (VisitNode(D.ParentPkg()) == false)
878             return false;
879       }
880    
881    return true;
882 }
883                                                                         /*}}}*/
884
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)
890 {
891    if (LoopCount < 0 || LoopCount >= 20)
892       return false;  
893    
894    // Skip dups
895    if (LoopCount != 0)
896    {
897       if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() ||
898           Loops[LoopCount - 1].TargetPkg() == D.ParentPkg())
899          return true;
900    }
901    
902    Loops[LoopCount++] = D;
903    
904    // Mark the packages as being part of a loop.
905    Flag(D.TargetPkg(),Loop);
906    Flag(D.ParentPkg(),Loop);
907    return true;
908 }
909                                                                         /*}}}*/
910 // OrderList::WipeFlags - Unset the given flags from all packages       /*{{{*/
911 // ---------------------------------------------------------------------
912 /* */
913 void pkgOrderList::WipeFlags(unsigned long F)
914 {
915    unsigned long Size = Cache.Head().PackageCount;
916    for (unsigned long I = 0; I != Size; I++)
917       Flags[I] &= ~F;
918 }
919                                                                         /*}}}*/
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)
928 {
929    SPtrArray<Version *> List = D.AllTargets();
930    bool Hit = false;
931    for (Version **I = List; *I != 0; I++)
932    {
933       VerIterator Ver(Cache,*I);
934       PkgIterator Pkg = Ver.ParentPkg();
935       
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))
944       {
945          if (Cache[Pkg].InstallVer != *I)
946             continue;
947       }
948       else
949          if ((Version *)Pkg.CurrentVer() != *I || 
950              Pkg.State() != PkgIterator::NeedsNothing)
951             continue;
952       
953       /* Conflicts requires that all versions are not present, depends
954          just needs one */
955       if (D->Type != pkgCache::Dep::Conflicts && 
956           D->Type != pkgCache::Dep::Obsoletes)
957       {
958          /* Try to find something that does not have the after flag set
959             if at all possible */
960          if (IsFlag(Pkg,After) == true)
961          {
962             Hit = true;
963             continue;
964          }
965       
966          return true;
967       }
968       else
969       {
970          if (IsFlag(Pkg,After) == true)
971             Flag(D.ParentPkg(),After);
972          
973          return false;
974       }      
975    }
976
977    // We found a hit, but it had the after flag set
978    if (Hit == true && D->Type == pkgCache::Dep::PreDepends)
979    {
980       Flag(D.ParentPkg(),After);
981       return true;
982    }
983    
984    /* Conflicts requires that all versions are not present, depends
985       just needs one */
986    if (D->Type == pkgCache::Dep::Conflicts ||
987        D->Type == pkgCache::Dep::Obsoletes)
988       return true;
989    return false;
990 }
991                                                                         /*}}}*/