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