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