apt-pkg/orderlist.cc

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