apt-pkg/orderlist.cc

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