* merged from main
[apt.git] / apt-pkg / orderlist.cc
1 // -*- mode: cpp; mode: fold -*-
2 // Description /*{{{*/
3 // $Id: orderlist.cc,v 1.14 2001/05/07 05:49:43 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 #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 /*}}}*/