apt  2.2.4
About: Apt (Advanced Package Tool) is a management system for software packages (Debian/Ubuntu). Release series 2.2.
  Fossies Dox: apt-2.2.4.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

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