Join with aliencode
[ntk/apt.git] / apt-pkg / orderlist.cc
... / ...
CommitLineData
1// -*- mode: cpp; mode: fold -*-
2// Description /*{{{*/
3// $Id: orderlist.cc,v 1.12 2001/02/20 07:03:17 jgg 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
77pkgOrderList *pkgOrderList::Me = 0;
78
79// OrderList::pkgOrderList - Constructor /*{{{*/
80// ---------------------------------------------------------------------
81/* */
82pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache)
83{
84 FileList = 0;
85 Primary = 0;
86 Secondary = 0;
87 RevDepends = 0;
88 Remove = 0;
89 LoopCount = -1;
90 Debug = _config->FindB("Debug::pkgOrderList",false);
91
92 /* Construct the arrays, egcs 1.0.1 bug requires the package count
93 hack */
94 unsigned long Size = Cache.Head().PackageCount;
95 Flags = new unsigned short[Size];
96 End = List = new Package *[Size];
97 memset(Flags,0,sizeof(*Flags)*Size);
98}
99 /*}}}*/
100// OrderList::~pkgOrderList - Destructor /*{{{*/
101// ---------------------------------------------------------------------
102/* */
103pkgOrderList::~pkgOrderList()
104{
105 delete [] List;
106 delete [] Flags;
107}
108 /*}}}*/
109// OrderList::IsMissing - Check if a file is missing /*{{{*/
110// ---------------------------------------------------------------------
111/* */
112bool pkgOrderList::IsMissing(PkgIterator Pkg)
113{
114 // Skip packages to erase
115 if (Cache[Pkg].Delete() == true)
116 return false;
117
118 // Skip Packages that need configure only.
119 if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
120 Cache[Pkg].Keep() == true)
121 return false;
122
123 if (FileList != 0 && FileList[Pkg->ID].empty() == false)
124 return false;
125 return true;
126}
127 /*}}}*/
128
129// OrderList::DoRun - Does an order run /*{{{*/
130// ---------------------------------------------------------------------
131/* The caller is expeted to have setup the desired probe state */
132bool pkgOrderList::DoRun()
133{
134 // Temp list
135 unsigned long Size = Cache.Head().PackageCount;
136 SPtrArray<Package *> NList = new Package *[Size];
137 SPtrArray<Package *> AfterList = new Package *[Size];
138 AfterEnd = AfterList;
139
140 Depth = 0;
141 WipeFlags(Added | AddPending | Loop | InList);
142
143 for (iterator I = List; I != End; I++)
144 Flag(*I,InList);
145
146 // Rebuild the main list into the temp list.
147 iterator OldEnd = End;
148 End = NList;
149 for (iterator I = List; I != OldEnd; I++)
150 if (VisitNode(PkgIterator(Cache,*I)) == false)
151 {
152 End = OldEnd;
153 return false;
154 }
155
156 // Copy the after list to the end of the main list
157 for (Package **I = AfterList; I != AfterEnd; I++)
158 *End++ = *I;
159
160 // Swap the main list to the new list
161 delete [] List;
162 List = NList.UnGuard();
163 return true;
164}
165 /*}}}*/
166// OrderList::OrderCritical - Perform critical unpacking ordering /*{{{*/
167// ---------------------------------------------------------------------
168/* This performs predepends and immediate configuration ordering only.
169 This is termed critical unpacking ordering. Any loops that form are
170 fatal and indicate that the packages cannot be installed. */
171bool pkgOrderList::OrderCritical()
172{
173 FileList = 0;
174
175 Primary = &pkgOrderList::DepUnPackPre;
176 Secondary = 0;
177 RevDepends = 0;
178 Remove = 0;
179 LoopCount = 0;
180
181 // Sort
182 Me = this;
183 qsort(List,End - List,sizeof(*List),&OrderCompareB);
184
185 if (DoRun() == false)
186 return false;
187
188 if (LoopCount != 0)
189 return _error->Error("Fatal, predepends looping detected");
190 return true;
191}
192 /*}}}*/
193// OrderList::OrderUnpack - Perform complete unpacking ordering /*{{{*/
194// ---------------------------------------------------------------------
195/* This performs complete unpacking ordering and creates an order that is
196 suitable for unpacking */
197bool pkgOrderList::OrderUnpack(string *FileList)
198{
199 this->FileList = FileList;
200
201 // Setup the after flags
202 if (FileList != 0)
203 {
204 WipeFlags(After);
205
206 // Set the inlist flag
207 for (iterator I = List; I != End; I++)
208 {
209 PkgIterator P(Cache,*I);
210 if (IsMissing(P) == true && IsNow(P) == true)
211 Flag(*I,After);
212 }
213 }
214
215 Primary = &pkgOrderList::DepUnPackCrit;
216 Secondary = &pkgOrderList::DepConfigure;
217 RevDepends = &pkgOrderList::DepUnPackDep;
218 Remove = &pkgOrderList::DepRemove;
219 LoopCount = -1;
220
221 // Sort
222 Me = this;
223 qsort(List,End - List,sizeof(*List),&OrderCompareA);
224
225 if (Debug == true)
226 clog << "** Pass A" << endl;
227 if (DoRun() == false)
228 return false;
229
230 if (Debug == true)
231 clog << "** Pass B" << endl;
232 Secondary = 0;
233 if (DoRun() == false)
234 return false;
235
236 if (Debug == true)
237 clog << "** Pass C" << endl;
238 LoopCount = 0;
239 RevDepends = 0;
240 Remove = 0; // Otherwise the libreadline remove problem occures
241 if (DoRun() == false)
242 return false;
243
244 if (Debug == true)
245 clog << "** Pass D" << endl;
246 LoopCount = 0;
247 Primary = &pkgOrderList::DepUnPackPre;
248 if (DoRun() == false)
249 return false;
250
251 if (Debug == true)
252 {
253 clog << "** Unpack ordering done" << endl;
254
255 for (iterator I = List; I != End; I++)
256 {
257 PkgIterator P(Cache,*I);
258 if (IsNow(P) == true)
259 clog << P.Name() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl;
260 }
261 }
262
263 return true;
264}
265 /*}}}*/
266// OrderList::OrderConfigure - Perform configuration ordering /*{{{*/
267// ---------------------------------------------------------------------
268/* This orders by depends only and produces an order which is suitable
269 for configuration */
270bool pkgOrderList::OrderConfigure()
271{
272 FileList = 0;
273 Primary = &pkgOrderList::DepConfigure;
274 Secondary = 0;
275 RevDepends = 0;
276 Remove = 0;
277 LoopCount = -1;
278 return DoRun();
279}
280 /*}}}*/
281
282// OrderList::Score - Score the package for sorting /*{{{*/
283// ---------------------------------------------------------------------
284/* Higher scores order earlier */
285int pkgOrderList::Score(PkgIterator Pkg)
286{
287 // Removal is always done first
288 if (Cache[Pkg].Delete() == true)
289 return 200;
290
291 // This should never happen..
292 if (Cache[Pkg].InstVerIter(Cache).end() == true)
293 return -1;
294
295 int Score = 0;
296 if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
297 Score += 100;
298
299 if (IsFlag(Pkg,Immediate) == true)
300 Score += 10;
301
302 for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList();
303 D.end() == false; D++)
304 if (D->Type == pkgCache::Dep::PreDepends)
305 {
306 Score += 50;
307 break;
308 }
309
310 // Important Required Standard Optional Extra
311 signed short PrioMap[] = {0,5,4,3,1,0};
312 if (Cache[Pkg].InstVerIter(Cache)->Priority <= 5)
313 Score += PrioMap[Cache[Pkg].InstVerIter(Cache)->Priority];
314 return Score;
315}
316 /*}}}*/
317// OrderList::FileCmp - Compare by package file /*{{{*/
318// ---------------------------------------------------------------------
319/* This compares by the package file that the install version is in. */
320int pkgOrderList::FileCmp(PkgIterator A,PkgIterator B)
321{
322 if (Cache[A].Delete() == true && Cache[B].Delete() == true)
323 return 0;
324 if (Cache[A].Delete() == true)
325 return -1;
326 if (Cache[B].Delete() == true)
327 return 1;
328
329 if (Cache[A].InstVerIter(Cache).FileList().end() == true)
330 return -1;
331 if (Cache[B].InstVerIter(Cache).FileList().end() == true)
332 return 1;
333
334 pkgCache::PackageFile *FA = Cache[A].InstVerIter(Cache).FileList().File();
335 pkgCache::PackageFile *FB = Cache[B].InstVerIter(Cache).FileList().File();
336 if (FA < FB)
337 return -1;
338 if (FA > FB)
339 return 1;
340 return 0;
341}
342 /*}}}*/
343// BoolCompare - Comparison function for two booleans /*{{{*/
344// ---------------------------------------------------------------------
345/* */
346static int BoolCompare(bool A,bool B)
347{
348 if (A == B)
349 return 0;
350 if (A == false)
351 return -1;
352 return 1;
353}
354 /*}}}*/
355// OrderList::OrderCompareA - Order the installation by op /*{{{*/
356// ---------------------------------------------------------------------
357/* This provides a first-pass sort of the list and gives a decent starting
358 point for further complete ordering. It is used by OrderUnpack only */
359int pkgOrderList::OrderCompareA(const void *a, const void *b)
360{
361 PkgIterator A(Me->Cache,*(Package **)a);
362 PkgIterator B(Me->Cache,*(Package **)b);
363
364 // We order packages with a set state toward the front
365 int Res;
366 if ((Res = BoolCompare(Me->IsNow(A),Me->IsNow(B))) != 0)
367 return -1*Res;
368
369 // We order missing files to toward the end
370/* if (Me->FileList != 0)
371 {
372 if ((Res = BoolCompare(Me->IsMissing(A),
373 Me->IsMissing(B))) != 0)
374 return Res;
375 }*/
376
377 if (A.State() != pkgCache::PkgIterator::NeedsNothing &&
378 B.State() == pkgCache::PkgIterator::NeedsNothing)
379 return -1;
380
381 if (A.State() == pkgCache::PkgIterator::NeedsNothing &&
382 B.State() != pkgCache::PkgIterator::NeedsNothing)
383 return 1;
384
385 int ScoreA = Me->Score(A);
386 int ScoreB = Me->Score(B);
387 if (ScoreA > ScoreB)
388 return -1;
389
390 if (ScoreA < ScoreB)
391 return 1;
392
393 return strcmp(A.Name(),B.Name());
394}
395 /*}}}*/
396// OrderList::OrderCompareB - Order the installation by source /*{{{*/
397// ---------------------------------------------------------------------
398/* This orders by installation source. This is useful to handle
399 inter-source breaks */
400int pkgOrderList::OrderCompareB(const void *a, const void *b)
401{
402 PkgIterator A(Me->Cache,*(Package **)a);
403 PkgIterator B(Me->Cache,*(Package **)b);
404
405 if (A.State() != pkgCache::PkgIterator::NeedsNothing &&
406 B.State() == pkgCache::PkgIterator::NeedsNothing)
407 return -1;
408
409 if (A.State() == pkgCache::PkgIterator::NeedsNothing &&
410 B.State() != pkgCache::PkgIterator::NeedsNothing)
411 return 1;
412
413 int F = Me->FileCmp(A,B);
414 if (F != 0)
415 {
416 if (F > 0)
417 return -1;
418 return 1;
419 }
420
421 int ScoreA = Me->Score(A);
422 int ScoreB = Me->Score(B);
423 if (ScoreA > ScoreB)
424 return -1;
425
426 if (ScoreA < ScoreB)
427 return 1;
428
429 return strcmp(A.Name(),B.Name());
430}
431 /*}}}*/
432
433// OrderList::VisitDeps - Visit forward install dependencies /*{{{*/
434// ---------------------------------------------------------------------
435/* This calls the dependency function for the normal forwards dependencies
436 of the package */
437bool pkgOrderList::VisitDeps(DepFunc F,PkgIterator Pkg)
438{
439 if (F == 0 || Pkg.end() == true || Cache[Pkg].InstallVer == 0)
440 return true;
441
442 return (this->*F)(Cache[Pkg].InstVerIter(Cache).DependsList());
443}
444 /*}}}*/
445// OrderList::VisitRDeps - Visit reverse dependencies /*{{{*/
446// ---------------------------------------------------------------------
447/* This calls the dependency function for all of the normal reverse depends
448 of the package */
449bool pkgOrderList::VisitRDeps(DepFunc F,PkgIterator Pkg)
450{
451 if (F == 0 || Pkg.end() == true)
452 return true;
453
454 return (this->*F)(Pkg.RevDependsList());
455}
456 /*}}}*/
457// OrderList::VisitRProvides - Visit provides reverse dependencies /*{{{*/
458// ---------------------------------------------------------------------
459/* This calls the dependency function for all reverse dependencies
460 generated by the provides line on the package. */
461bool pkgOrderList::VisitRProvides(DepFunc F,VerIterator Ver)
462{
463 if (F == 0 || Ver.end() == true)
464 return true;
465
466 bool Res = true;
467 for (PrvIterator P = Ver.ProvidesList(); P.end() == false; P++)
468 Res &= (this->*F)(P.ParentPkg().RevDependsList());
469 return true;
470}
471 /*}}}*/
472// OrderList::VisitProvides - Visit all of the providing packages /*{{{*/
473// ---------------------------------------------------------------------
474/* This routine calls visit on all providing packages. */
475bool pkgOrderList::VisitProvides(DepIterator D,bool Critical)
476{
477 SPtrArray<Version *> List = D.AllTargets();
478 for (Version **I = List; *I != 0; I++)
479 {
480 VerIterator Ver(Cache,*I);
481 PkgIterator Pkg = Ver.ParentPkg();
482
483 if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
484 continue;
485
486 if (D->Type != pkgCache::Dep::Conflicts &&
487 D->Type != pkgCache::Dep::Obsoletes &&
488 Cache[Pkg].InstallVer != *I)
489 continue;
490
491 if ((D->Type == pkgCache::Dep::Conflicts ||
492 D->Type == pkgCache::Dep::Obsoletes) &&
493 (Version *)Pkg.CurrentVer() != *I)
494 continue;
495
496 // Skip over missing files
497 if (Critical == false && IsMissing(D.ParentPkg()) == true)
498 continue;
499
500 if (VisitNode(Pkg) == false)
501 return false;
502 }
503 return true;
504}
505 /*}}}*/
506// OrderList::VisitNode - Recursive ordering director /*{{{*/
507// ---------------------------------------------------------------------
508/* This is the core ordering routine. It calls the set dependency
509 consideration functions which then potentialy call this again. Finite
510 depth is achived through the colouring mechinism. */
511bool pkgOrderList::VisitNode(PkgIterator Pkg)
512{
513 // Looping or irrelevent.
514 // This should probably trancend not installed packages
515 if (Pkg.end() == true || IsFlag(Pkg,Added) == true ||
516 IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false)
517 return true;
518
519 if (Debug == true)
520 {
521 for (int j = 0; j != Depth; j++) clog << ' ';
522 clog << "Visit " << Pkg.Name() << endl;
523 }
524
525 Depth++;
526
527 // Color grey
528 Flag(Pkg,AddPending);
529
530 DepFunc Old = Primary;
531
532 // Perform immedate configuration of the package if so flagged.
533 if (IsFlag(Pkg,Immediate) == true && Primary != &pkgOrderList::DepUnPackPre)
534 Primary = &pkgOrderList::DepUnPackPreD;
535
536 if (IsNow(Pkg) == true)
537 {
538 bool Res = true;
539 if (Cache[Pkg].Delete() == false)
540 {
541 // Primary
542 Res &= Res && VisitDeps(Primary,Pkg);
543 Res &= Res && VisitRDeps(Primary,Pkg);
544 Res &= Res && VisitRProvides(Primary,Pkg.CurrentVer());
545 Res &= Res && VisitRProvides(Primary,Cache[Pkg].InstVerIter(Cache));
546
547 // RevDep
548 Res &= Res && VisitRDeps(RevDepends,Pkg);
549 Res &= Res && VisitRProvides(RevDepends,Pkg.CurrentVer());
550 Res &= Res && VisitRProvides(RevDepends,Cache[Pkg].InstVerIter(Cache));
551
552 // Secondary
553 Res &= Res && VisitDeps(Secondary,Pkg);
554 Res &= Res && VisitRDeps(Secondary,Pkg);
555 Res &= Res && VisitRProvides(Secondary,Pkg.CurrentVer());
556 Res &= Res && VisitRProvides(Secondary,Cache[Pkg].InstVerIter(Cache));
557 }
558 else
559 {
560 // RevDep
561 Res &= Res && VisitRDeps(Remove,Pkg);
562 Res &= Res && VisitRProvides(Remove,Pkg.CurrentVer());
563 }
564 }
565
566 if (IsFlag(Pkg,Added) == false)
567 {
568 Flag(Pkg,Added,Added | AddPending);
569 if (IsFlag(Pkg,After) == true)
570 *AfterEnd++ = Pkg;
571 else
572 *End++ = Pkg;
573 }
574
575 Primary = Old;
576 Depth--;
577
578 if (Debug == true)
579 {
580 for (int j = 0; j != Depth; j++) clog << ' ';
581 clog << "Leave " << Pkg.Name() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;
582 }
583
584 return true;
585}
586 /*}}}*/
587
588// OrderList::DepUnPackCrit - Critical UnPacking ordering /*{{{*/
589// ---------------------------------------------------------------------
590/* Critical unpacking ordering strives to satisfy Conflicts: and
591 PreDepends: only. When a prdepends is encountered the Primary
592 DepFunc is changed to be DepUnPackPreD.
593
594 Loops are preprocessed and logged. */
595bool pkgOrderList::DepUnPackCrit(DepIterator D)
596{
597 for (; D.end() == false; D++)
598 {
599 if (D.Reverse() == true)
600 {
601 /* Reverse depenanices are only interested in conflicts,
602 predepend breakage is ignored here */
603 if (D->Type != pkgCache::Dep::Conflicts &&
604 D->Type != pkgCache::Dep::Obsoletes)
605 continue;
606
607 // Duplication elimination, consider only the current version
608 if (D.ParentPkg().CurrentVer() != D.ParentVer())
609 continue;
610
611 /* For reverse dependencies we wish to check if the
612 dependency is satisifed in the install state. The
613 target package (caller) is going to be in the installed
614 state. */
615 if (CheckDep(D) == true)
616 continue;
617
618 if (VisitNode(D.ParentPkg()) == false)
619 return false;
620 }
621 else
622 {
623 /* Forward critical dependencies MUST be correct before the
624 package can be unpacked. */
625 if (D->Type != pkgCache::Dep::Conflicts &&
626 D->Type != pkgCache::Dep::Obsoletes &&
627 D->Type != pkgCache::Dep::PreDepends)
628 continue;
629
630 /* We wish to check if the dep is okay in the now state of the
631 target package against the install state of this package. */
632 if (CheckDep(D) == true)
633 {
634 /* We want to catch predepends loops with the code below.
635 Conflicts loops that are Dep OK are ignored */
636 if (IsFlag(D.TargetPkg(),AddPending) == false ||
637 D->Type != pkgCache::Dep::PreDepends)
638 continue;
639 }
640
641 // This is the loop detection
642 if (IsFlag(D.TargetPkg(),Added) == true ||
643 IsFlag(D.TargetPkg(),AddPending) == true)
644 {
645 if (IsFlag(D.TargetPkg(),AddPending) == true)
646 AddLoop(D);
647 continue;
648 }
649
650 /* Predepends require a special ordering stage, they must have
651 all dependents installed as well */
652 DepFunc Old = Primary;
653 bool Res = false;
654 if (D->Type == pkgCache::Dep::PreDepends)
655 Primary = &pkgOrderList::DepUnPackPreD;
656 Res = VisitProvides(D,true);
657 Primary = Old;
658 if (Res == false)
659 return false;
660 }
661 }
662 return true;
663}
664 /*}}}*/
665// OrderList::DepUnPackPreD - Critical UnPacking ordering with depends /*{{{*/
666// ---------------------------------------------------------------------
667/* Critical PreDepends (also configure immediate and essential) strives to
668 ensure not only that all conflicts+predepends are met but that this
669 package will be immediately configurable when it is unpacked.
670
671 Loops are preprocessed and logged. */
672bool pkgOrderList::DepUnPackPreD(DepIterator D)
673{
674 if (D.Reverse() == true)
675 return DepUnPackCrit(D);
676
677 for (; D.end() == false; D++)
678 {
679 if (D.IsCritical() == false)
680 continue;
681
682 /* We wish to check if the dep is okay in the now state of the
683 target package against the install state of this package. */
684 if (CheckDep(D) == true)
685 {
686 /* We want to catch predepends loops with the code below.
687 Conflicts loops that are Dep OK are ignored */
688 if (IsFlag(D.TargetPkg(),AddPending) == false ||
689 D->Type != pkgCache::Dep::PreDepends)
690 continue;
691 }
692
693 // This is the loop detection
694 if (IsFlag(D.TargetPkg(),Added) == true ||
695 IsFlag(D.TargetPkg(),AddPending) == true)
696 {
697 if (IsFlag(D.TargetPkg(),AddPending) == true)
698 AddLoop(D);
699 continue;
700 }
701
702 if (VisitProvides(D,true) == false)
703 return false;
704 }
705 return true;
706}
707 /*}}}*/
708// OrderList::DepUnPackPre - Critical Predepends ordering /*{{{*/
709// ---------------------------------------------------------------------
710/* Critical PreDepends (also configure immediate and essential) strives to
711 ensure not only that all conflicts+predepends are met but that this
712 package will be immediately configurable when it is unpacked.
713
714 Loops are preprocessed and logged. All loops will be fatal. */
715bool pkgOrderList::DepUnPackPre(DepIterator D)
716{
717 if (D.Reverse() == true)
718 return true;
719
720 for (; D.end() == false; D++)
721 {
722 /* Only consider the PreDepends or Depends. Depends are only
723 considered at the lowest depth or in the case of immediate
724 configure */
725 if (D->Type != pkgCache::Dep::PreDepends)
726 {
727 if (D->Type == pkgCache::Dep::Depends)
728 {
729 if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false)
730 continue;
731 }
732 else
733 continue;
734 }
735
736 /* We wish to check if the dep is okay in the now state of the
737 target package against the install state of this package. */
738 if (CheckDep(D) == true)
739 {
740 /* We want to catch predepends loops with the code below.
741 Conflicts loops that are Dep OK are ignored */
742 if (IsFlag(D.TargetPkg(),AddPending) == false)
743 continue;
744 }
745
746 // This is the loop detection
747 if (IsFlag(D.TargetPkg(),Added) == true ||
748 IsFlag(D.TargetPkg(),AddPending) == true)
749 {
750 if (IsFlag(D.TargetPkg(),AddPending) == true)
751 AddLoop(D);
752 continue;
753 }
754
755 if (VisitProvides(D,true) == false)
756 return false;
757 }
758 return true;
759}
760 /*}}}*/
761// OrderList::DepUnPackDep - Reverse dependency considerations /*{{{*/
762// ---------------------------------------------------------------------
763/* Reverse dependencies are considered to determine if unpacking this
764 package will break any existing dependencies. If so then those
765 packages are ordered before this one so that they are in the
766 UnPacked state.
767
768 The forwards depends loop is designed to bring the packages dependents
769 close to the package. This helps reduce deconfigure time.
770
771 Loops are irrelevent to this. */
772bool pkgOrderList::DepUnPackDep(DepIterator D)
773{
774
775 for (; D.end() == false; D++)
776 if (D.IsCritical() == true)
777 {
778 if (D.Reverse() == true)
779 {
780 /* Duplication prevention. We consider rev deps only on
781 the current version, a not installed package
782 cannot break */
783 if (D.ParentPkg()->CurrentVer == 0 ||
784 D.ParentPkg().CurrentVer() != D.ParentVer())
785 continue;
786
787 // The dep will not break so it is irrelevent.
788 if (CheckDep(D) == true)
789 continue;
790
791 // Skip over missing files
792 if (IsMissing(D.ParentPkg()) == true)
793 continue;
794
795 if (VisitNode(D.ParentPkg()) == false)
796 return false;
797 }
798 else
799 if (D->Type == pkgCache::Dep::Depends)
800 if (VisitProvides(D,false) == false)
801 return false;
802 }
803 return true;
804}
805 /*}}}*/
806// OrderList::DepConfigure - Configuration ordering /*{{{*/
807// ---------------------------------------------------------------------
808/* Configuration only ordering orders by the Depends: line only. It
809 orders configuration so that when a package comes to be configured it's
810 dependents are configured.
811
812 Loops are ingored. Depends loop entry points are chaotic. */
813bool pkgOrderList::DepConfigure(DepIterator D)
814{
815 // Never consider reverse configuration dependencies.
816 if (D.Reverse() == true)
817 return true;
818
819 for (; D.end() == false; D++)
820 if (D->Type == pkgCache::Dep::Depends)
821 if (VisitProvides(D,false) == false)
822 return false;
823 return true;
824}
825 /*}}}*/
826// OrderList::DepRemove - Removal ordering /*{{{*/
827// ---------------------------------------------------------------------
828/* Removal visits all reverse depends. It considers if the dependency
829 of the Now state version to see if it is okay with removing this
830 package. This check should always fail, but is provided for symetery
831 with the other critical handlers.
832
833 Loops are preprocessed and logged. Removal loops can also be
834 detected in the critical handler. They are characterized by an
835 old version of A depending on B but the new version of A conflicting
836 with B, thus either A or B must break to install. */
837bool pkgOrderList::DepRemove(DepIterator D)
838{
839 if (D.Reverse() == false)
840 return true;
841 for (; D.end() == false; D++)
842 if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
843 {
844 // Duplication elimination, consider the current version only
845 if (D.ParentPkg().CurrentVer() != D.ParentVer())
846 continue;
847
848 /* We wish to see if the dep on the parent package is okay
849 in the removed (install) state of the target pkg. */
850 if (CheckDep(D) == true)
851 {
852 // We want to catch loops with the code below.
853 if (IsFlag(D.ParentPkg(),AddPending) == false)
854 continue;
855 }
856
857 // This is the loop detection
858 if (IsFlag(D.ParentPkg(),Added) == true ||
859 IsFlag(D.ParentPkg(),AddPending) == true)
860 {
861 if (IsFlag(D.ParentPkg(),AddPending) == true)
862 AddLoop(D);
863 continue;
864 }
865
866 // Skip over missing files
867 if (IsMissing(D.ParentPkg()) == true)
868 continue;
869
870 if (VisitNode(D.ParentPkg()) == false)
871 return false;
872 }
873
874 return true;
875}
876 /*}}}*/
877
878// OrderList::AddLoop - Add a loop to the loop list /*{{{*/
879// ---------------------------------------------------------------------
880/* We record the loops. This is a relic since loop breaking is done
881 genericaly as part of the safety routines. */
882bool pkgOrderList::AddLoop(DepIterator D)
883{
884 if (LoopCount < 0 || LoopCount >= 20)
885 return false;
886
887 // Skip dups
888 if (LoopCount != 0)
889 {
890 if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() ||
891 Loops[LoopCount - 1].TargetPkg() == D.ParentPkg())
892 return true;
893 }
894
895 Loops[LoopCount++] = D;
896
897 // Mark the packages as being part of a loop.
898 Flag(D.TargetPkg(),Loop);
899 Flag(D.ParentPkg(),Loop);
900 return true;
901}
902 /*}}}*/
903// OrderList::WipeFlags - Unset the given flags from all packages /*{{{*/
904// ---------------------------------------------------------------------
905/* */
906void pkgOrderList::WipeFlags(unsigned long F)
907{
908 unsigned long Size = Cache.Head().PackageCount;
909 for (unsigned long I = 0; I != Size; I++)
910 Flags[I] &= ~F;
911}
912 /*}}}*/
913// OrderList::CheckDep - Check a dependency for truth /*{{{*/
914// ---------------------------------------------------------------------
915/* This performs a complete analysis of the dependency wrt to the
916 current add list. It returns true if after all events are
917 performed it is still true. This sort of routine can be approximated
918 by examining the DepCache, however in convoluted cases of provides
919 this fails to produce a suitable result. */
920bool pkgOrderList::CheckDep(DepIterator D)
921{
922 SPtrArray<Version *> List = D.AllTargets();
923 bool Hit = false;
924 for (Version **I = List; *I != 0; I++)
925 {
926 VerIterator Ver(Cache,*I);
927 PkgIterator Pkg = Ver.ParentPkg();
928
929 /* The meaning of Added and AddPending is subtle. AddPending is
930 an indication that the package is looping. Because of the
931 way ordering works Added means the package will be unpacked
932 before this one and AddPending means after. It is therefore
933 correct to ignore AddPending in all cases, but that exposes
934 reverse-ordering loops which should be ignored. */
935 if (IsFlag(Pkg,Added) == true ||
936 (IsFlag(Pkg,AddPending) == true && D.Reverse() == true))
937 {
938 if (Cache[Pkg].InstallVer != *I)
939 continue;
940 }
941 else
942 if ((Version *)Pkg.CurrentVer() != *I ||
943 Pkg.State() != PkgIterator::NeedsNothing)
944 continue;
945
946 /* Conflicts requires that all versions are not present, depends
947 just needs one */
948 if (D->Type != pkgCache::Dep::Conflicts &&
949 D->Type != pkgCache::Dep::Obsoletes)
950 {
951 /* Try to find something that does not have the after flag set
952 if at all possible */
953 if (IsFlag(Pkg,After) == true)
954 {
955 Hit = true;
956 continue;
957 }
958
959 return true;
960 }
961 else
962 {
963 if (IsFlag(Pkg,After) == true)
964 Flag(D.ParentPkg(),After);
965
966 return false;
967 }
968 }
969
970 // We found a hit, but it had the after flag set
971 if (Hit == true && D->Type == pkgCache::Dep::PreDepends)
972 {
973 Flag(D.ParentPkg(),After);
974 return true;
975 }
976
977 /* Conflicts requires that all versions are not present, depends
978 just needs one */
979 if (D->Type == pkgCache::Dep::Conflicts ||
980 D->Type == pkgCache::Dep::Obsoletes)
981 return true;
982 return false;
983}
984 /*}}}*/