apt-pkg/orderlist.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: orderlist.cc,v 1.13 2001/04/27 04:47:58 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
  77 pkgOrderList *pkgOrderList::Me = 0;
  78
  79 // OrderList::pkgOrderList - Constructor                                /*{{{*/
  80 // ---------------------------------------------------------------------
  81 /* */
  82 pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache)
  83 {
  84    FileList = 0;
  85    Primary = 0;
  86    Secondary = 0;
  87    RevDepends = 0;
  88    Remove = 0;
  89    LoopCount = -1;
  90    Debug = _config->FindB("Debug::pkgOrderList",false);
  91
  92    /* Construct the arrays, egcs 1.0.1 bug requires the package count
  93       hack */
  94    unsigned long Size = Cache.Head().PackageCount;
  95    Flags = new unsigned short[Size];
  96    End = List = new Package *[Size];
  97    memset(Flags,0,sizeof(*Flags)*Size);
  98 }
  99                                                                         /*}}}*/
 100 // OrderList::~pkgOrderList - Destructor                                /*{{{*/
 101 // ---------------------------------------------------------------------
 102 /* */
 103 pkgOrderList::~pkgOrderList()
 104 {
 105    delete [] List;
 106    delete [] Flags;
 107 }
 108                                                                         /*}}}*/
 109 // OrderList::IsMissing - Check if a file is missing                    /*{{{*/
 110 // ---------------------------------------------------------------------
 111 /* */
 112 bool pkgOrderList::IsMissing(PkgIterator Pkg)
 113 {
 114    // Skip packages to erase
 115    if (Cache[Pkg].Delete() == true)
 116       return false;
 117
 118    // Skip Packages that need configure only.
 119    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 120        Cache[Pkg].Keep() == true)
 121       return false;
 122
 123    if (FileList == 0)
 124       return false;
 125
 126    if (FileList[Pkg->ID].empty() == false)
 127       return false;
 128    return true;
 129 }
 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
 285 // OrderList::Score - Score the package for sorting                     /*{{{*/
 286 // ---------------------------------------------------------------------
 287 /* Higher scores order earlier */
 288 int pkgOrderList::Score(PkgIterator Pkg)
 289 {
 290    // Removal is always done first
 291    if (Cache[Pkg].Delete() == true)
 292       return 200;
 293
 294    // This should never happen..
 295    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 296       return -1;
 297
 298    int Score = 0;
 299    if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 300       Score += 100;
 301
 302    if (IsFlag(Pkg,Immediate) == true)
 303       Score += 10;
 304
 305    for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList();
 306         D.end() == false; D++)
 307       if (D->Type == pkgCache::Dep::PreDepends)
 308       {
 309          Score += 50;
 310          break;
 311       }
 312
 313    // Important Required Standard Optional Extra
 314    signed short PrioMap[] = {0,5,4,3,1,0};
 315    if (Cache[Pkg].InstVerIter(Cache)->Priority <= 5)
 316       Score += PrioMap[Cache[Pkg].InstVerIter(Cache)->Priority];
 317    return Score;
 318 }
 319                                                                         /*}}}*/
 320 // OrderList::FileCmp - Compare by package file                         /*{{{*/
 321 // ---------------------------------------------------------------------
 322 /* This compares by the package file that the install version is in. */
 323 int pkgOrderList::FileCmp(PkgIterator A,PkgIterator B)
 324 {
 325    if (Cache[A].Delete() == true && Cache[B].Delete() == true)
 326       return 0;
 327    if (Cache[A].Delete() == true)
 328       return -1;
 329    if (Cache[B].Delete() == true)
 330       return 1;
 331
 332    if (Cache[A].InstVerIter(Cache).FileList().end() == true)
 333       return -1;
 334    if (Cache[B].InstVerIter(Cache).FileList().end() == true)
 335       return 1;
 336
 337    pkgCache::PackageFile *FA = Cache[A].InstVerIter(Cache).FileList().File();
 338    pkgCache::PackageFile *FB = Cache[B].InstVerIter(Cache).FileList().File();
 339    if (FA < FB)
 340       return -1;
 341    if (FA > FB)
 342       return 1;
 343    return 0;
 344 }
 345                                                                         /*}}}*/
 346 // BoolCompare - Comparison function for two booleans                   /*{{{*/
 347 // ---------------------------------------------------------------------
 348 /* */
 349 static int BoolCompare(bool A,bool B)
 350 {
 351    if (A == B)
 352       return 0;
 353    if (A == false)
 354       return -1;
 355    return 1;
 356 }
 357                                                                         /*}}}*/
 358 // OrderList::OrderCompareA - Order the installation by op              /*{{{*/
 359 // ---------------------------------------------------------------------
 360 /* This provides a first-pass sort of the list and gives a decent starting
 361     point for further complete ordering. It is used by OrderUnpack only */
 362 int pkgOrderList::OrderCompareA(const void *a, const void *b)
 363 {
 364    PkgIterator A(Me->Cache,*(Package **)a);
 365    PkgIterator B(Me->Cache,*(Package **)b);
 366
 367    // We order packages with a set state toward the front
 368    int Res;
 369    if ((Res = BoolCompare(Me->IsNow(A),Me->IsNow(B))) != 0)
 370       return -1*Res;
 371
 372    // We order missing files to toward the end
 373 /*   if (Me->FileList != 0)
 374    {
 375       if ((Res = BoolCompare(Me->IsMissing(A),
 376                              Me->IsMissing(B))) != 0)
 377          return Res;
 378    }*/
 379
 380    if (A.State() != pkgCache::PkgIterator::NeedsNothing &&
 381        B.State() == pkgCache::PkgIterator::NeedsNothing)
 382       return -1;
 383
 384    if (A.State() == pkgCache::PkgIterator::NeedsNothing &&
 385        B.State() != pkgCache::PkgIterator::NeedsNothing)
 386       return 1;
 387
 388    int ScoreA = Me->Score(A);
 389    int ScoreB = Me->Score(B);
 390    if (ScoreA > ScoreB)
 391       return -1;
 392
 393    if (ScoreA < ScoreB)
 394       return 1;
 395
 396    return strcmp(A.Name(),B.Name());
 397 }
 398                                                                         /*}}}*/
 399 // OrderList::OrderCompareB - Order the installation by source          /*{{{*/
 400 // ---------------------------------------------------------------------
 401 /* This orders by installation source. This is useful to handle
 402    inter-source breaks */
 403 int pkgOrderList::OrderCompareB(const void *a, const void *b)
 404 {
 405    PkgIterator A(Me->Cache,*(Package **)a);
 406    PkgIterator B(Me->Cache,*(Package **)b);
 407
 408    if (A.State() != pkgCache::PkgIterator::NeedsNothing &&
 409        B.State() == pkgCache::PkgIterator::NeedsNothing)
 410       return -1;
 411
 412    if (A.State() == pkgCache::PkgIterator::NeedsNothing &&
 413        B.State() != pkgCache::PkgIterator::NeedsNothing)
 414       return 1;
 415
 416    int F = Me->FileCmp(A,B);
 417    if (F != 0)
 418    {
 419       if (F > 0)
 420          return -1;
 421       return 1;
 422    }
 423
 424    int ScoreA = Me->Score(A);
 425    int ScoreB = Me->Score(B);
 426    if (ScoreA > ScoreB)
 427       return -1;
 428
 429    if (ScoreA < ScoreB)
 430       return 1;
 431
 432    return strcmp(A.Name(),B.Name());
 433 }
 434                                                                         /*}}}*/
 435
 436 // OrderList::VisitDeps - Visit forward install dependencies            /*{{{*/
 437 // ---------------------------------------------------------------------
 438 /* This calls the dependency function for the normal forwards dependencies
 439    of the package */
 440 bool pkgOrderList::VisitDeps(DepFunc F,PkgIterator Pkg)
 441 {
 442    if (F == 0 || Pkg.end() == true || Cache[Pkg].InstallVer == 0)
 443       return true;
 444
 445    return (this->*F)(Cache[Pkg].InstVerIter(Cache).DependsList());
 446 }
 447                                                                         /*}}}*/
 448 // OrderList::VisitRDeps - Visit reverse dependencies                   /*{{{*/
 449 // ---------------------------------------------------------------------
 450 /* This calls the dependency function for all of the normal reverse depends
 451    of the package */
 452 bool pkgOrderList::VisitRDeps(DepFunc F,PkgIterator Pkg)
 453 {
 454    if (F == 0 || Pkg.end() == true)
 455       return true;
 456
 457    return (this->*F)(Pkg.RevDependsList());
 458 }
 459                                                                         /*}}}*/
 460 // OrderList::VisitRProvides - Visit provides reverse dependencies      /*{{{*/
 461 // ---------------------------------------------------------------------
 462 /* This calls the dependency function for all reverse dependencies
 463    generated by the provides line on the package. */
 464 bool pkgOrderList::VisitRProvides(DepFunc F,VerIterator Ver)
 465 {
 466    if (F == 0 || Ver.end() == true)
 467       return true;
 468
 469    bool Res = true;
 470    for (PrvIterator P = Ver.ProvidesList(); P.end() == false; P++)
 471       Res &= (this->*F)(P.ParentPkg().RevDependsList());
 472    return true;
 473 }
 474                                                                         /*}}}*/
 475 // OrderList::VisitProvides - Visit all of the providing packages       /*{{{*/
 476 // ---------------------------------------------------------------------
 477 /* This routine calls visit on all providing packages. */
 478 bool pkgOrderList::VisitProvides(DepIterator D,bool Critical)
 479 {
 480    SPtrArray<Version *> List = D.AllTargets();
 481    for (Version **I = List; *I != 0; I++)
 482    {
 483       VerIterator Ver(Cache,*I);
 484       PkgIterator Pkg = Ver.ParentPkg();
 485
 486       if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
 487          continue;
 488
 489       if (D->Type != pkgCache::Dep::Conflicts &&
 490           D->Type != pkgCache::Dep::Obsoletes &&
 491           Cache[Pkg].InstallVer != *I)
 492          continue;
 493
 494       if ((D->Type == pkgCache::Dep::Conflicts ||
 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
 591 // OrderList::DepUnPackCrit - Critical UnPacking ordering               /*{{{*/
 592 // ---------------------------------------------------------------------
 593 /* Critical unpacking ordering strives to satisfy Conflicts: and
 594    PreDepends: only. When a prdepends is encountered the Primary
 595    DepFunc is changed to be DepUnPackPreD.
 596
 597    Loops are preprocessed and logged. */
 598 bool pkgOrderList::DepUnPackCrit(DepIterator D)
 599 {
 600    for (; D.end() == false; D++)
 601    {
 602       if (D.Reverse() == true)
 603       {
 604          /* Reverse depenanices are only interested in conflicts,
 605             predepend breakage is ignored here */
 606          if (D->Type != pkgCache::Dep::Conflicts &&
 607              D->Type != pkgCache::Dep::Obsoletes)
 608             continue;
 609
 610          // Duplication elimination, consider only the current version
 611          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 612             continue;
 613
 614          /* For reverse dependencies we wish to check if the
 615             dependency is satisifed in the install state. The
 616             target package (caller) is going to be in the installed
 617             state. */
 618          if (CheckDep(D) == true)
 619             continue;
 620
 621          if (VisitNode(D.ParentPkg()) == false)
 622             return false;
 623       }
 624       else
 625       {
 626          /* Forward critical dependencies MUST be correct before the
 627             package can be unpacked. */
 628          if (D->Type != pkgCache::Dep::Conflicts &&
 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
 674    Loops are preprocessed and logged. */
 675 bool pkgOrderList::DepUnPackPreD(DepIterator D)
 676 {
 677    if (D.Reverse() == true)
 678       return DepUnPackCrit(D);
 679
 680    for (; D.end() == false; D++)
 681    {
 682       if (D.IsCritical() == false)
 683          continue;
 684
 685       /* We wish to check if the dep is okay in the now state of the
 686          target package against the install state of this package. */
 687       if (CheckDep(D) == true)
 688       {
 689          /* We want to catch predepends loops with the code below.
 690             Conflicts loops that are Dep OK are ignored */
 691          if (IsFlag(D.TargetPkg(),AddPending) == false ||
 692              D->Type != pkgCache::Dep::PreDepends)
 693             continue;
 694       }
 695
 696       // This is the loop detection
 697       if (IsFlag(D.TargetPkg(),Added) == true ||
 698           IsFlag(D.TargetPkg(),AddPending) == true)
 699       {
 700          if (IsFlag(D.TargetPkg(),AddPending) == true)
 701             AddLoop(D);
 702          continue;
 703       }
 704
 705       if (VisitProvides(D,true) == false)
 706          return false;
 707    }
 708    return true;
 709 }
 710                                                                         /*}}}*/
 711 // OrderList::DepUnPackPre - Critical Predepends ordering               /*{{{*/
 712 // ---------------------------------------------------------------------
 713 /* Critical PreDepends (also configure immediate and essential) strives to
 714    ensure not only that all conflicts+predepends are met but that this
 715    package will be immediately configurable when it is unpacked.
 716
 717    Loops are preprocessed and logged. All loops will be fatal. */
 718 bool pkgOrderList::DepUnPackPre(DepIterator D)
 719 {
 720    if (D.Reverse() == true)
 721       return true;
 722
 723    for (; D.end() == false; D++)
 724    {
 725       /* Only consider the PreDepends or Depends. Depends are only
 726          considered at the lowest depth or in the case of immediate
 727          configure */
 728       if (D->Type != pkgCache::Dep::PreDepends)
 729       {
 730          if (D->Type == pkgCache::Dep::Depends)
 731          {
 732             if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false)
 733                continue;
 734          }
 735          else
 736             continue;
 737       }
 738
 739       /* We wish to check if the dep is okay in the now state of the
 740          target package against the install state of this package. */
 741       if (CheckDep(D) == true)
 742       {
 743          /* We want to catch predepends loops with the code below.
 744             Conflicts loops that are Dep OK are ignored */
 745          if (IsFlag(D.TargetPkg(),AddPending) == false)
 746             continue;
 747       }
 748
 749       // This is the loop detection
 750       if (IsFlag(D.TargetPkg(),Added) == true ||
 751           IsFlag(D.TargetPkg(),AddPending) == true)
 752       {
 753          if (IsFlag(D.TargetPkg(),AddPending) == true)
 754             AddLoop(D);
 755          continue;
 756       }
 757
 758       if (VisitProvides(D,true) == false)
 759          return false;
 760    }
 761    return true;
 762 }
 763                                                                         /*}}}*/
 764 // OrderList::DepUnPackDep - Reverse dependency considerations          /*{{{*/
 765 // ---------------------------------------------------------------------
 766 /* Reverse dependencies are considered to determine if unpacking this
 767    package will break any existing dependencies. If so then those
 768    packages are ordered before this one so that they are in the
 769    UnPacked state.
 770
 771    The forwards depends loop is designed to bring the packages dependents
 772    close to the package. This helps reduce deconfigure time.
 773
 774    Loops are irrelevent to this. */
 775 bool pkgOrderList::DepUnPackDep(DepIterator D)
 776 {
 777
 778    for (; D.end() == false; D++)
 779       if (D.IsCritical() == true)
 780       {
 781          if (D.Reverse() == true)
 782          {
 783             /* Duplication prevention. We consider rev deps only on
 784                the current version, a not installed package
 785                cannot break */
 786             if (D.ParentPkg()->CurrentVer == 0 ||
 787                 D.ParentPkg().CurrentVer() != D.ParentVer())
 788                continue;
 789
 790             // The dep will not break so it is irrelevent.
 791             if (CheckDep(D) == true)
 792                continue;
 793
 794             // Skip over missing files
 795             if (IsMissing(D.ParentPkg()) == true)
 796                continue;
 797
 798             if (VisitNode(D.ParentPkg()) == false)
 799                return false;
 800          }
 801          else
 802             if (D->Type == pkgCache::Dep::Depends)
 803                if (VisitProvides(D,false) == false)
 804                   return false;
 805       }
 806    return true;
 807 }
 808                                                                         /*}}}*/
 809 // OrderList::DepConfigure - Configuration ordering                     /*{{{*/
 810 // ---------------------------------------------------------------------
 811 /* Configuration only ordering orders by the Depends: line only. It
 812    orders configuration so that when a package comes to be configured it's
 813    dependents are configured.
 814
 815    Loops are ingored. Depends loop entry points are chaotic. */
 816 bool pkgOrderList::DepConfigure(DepIterator D)
 817 {
 818    // Never consider reverse configuration dependencies.
 819    if (D.Reverse() == true)
 820       return true;
 821
 822    for (; D.end() == false; D++)
 823       if (D->Type == pkgCache::Dep::Depends)
 824          if (VisitProvides(D,false) == false)
 825             return false;
 826    return true;
 827 }
 828                                                                         /*}}}*/
 829 // OrderList::DepRemove - Removal ordering                              /*{{{*/
 830 // ---------------------------------------------------------------------
 831 /* Removal visits all reverse depends. It considers if the dependency
 832    of the Now state version to see if it is okay with removing this
 833    package. This check should always fail, but is provided for symetery
 834    with the other critical handlers.
 835
 836    Loops are preprocessed and logged. Removal loops can also be
 837    detected in the critical handler. They are characterized by an
 838    old version of A depending on B but the new version of A conflicting
 839    with B, thus either A or B must break to install. */
 840 bool pkgOrderList::DepRemove(DepIterator D)
 841 {
 842    if (D.Reverse() == false)
 843       return true;
 844    for (; D.end() == false; D++)
 845       if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 846       {
 847          // Duplication elimination, consider the current version only
 848          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 849             continue;
 850
 851          /* We wish to see if the dep on the parent package is okay
 852             in the removed (install) state of the target pkg. */
 853          if (CheckDep(D) == true)
 854          {
 855             // We want to catch loops with the code below.
 856             if (IsFlag(D.ParentPkg(),AddPending) == false)
 857                continue;
 858          }
 859
 860          // This is the loop detection
 861          if (IsFlag(D.ParentPkg(),Added) == true ||
 862              IsFlag(D.ParentPkg(),AddPending) == true)
 863          {
 864             if (IsFlag(D.ParentPkg(),AddPending) == true)
 865                AddLoop(D);
 866             continue;
 867          }
 868
 869          // Skip over missing files
 870          if (IsMissing(D.ParentPkg()) == true)
 871             continue;
 872
 873          if (VisitNode(D.ParentPkg()) == false)
 874             return false;
 875       }
 876
 877    return true;
 878 }
 879                                                                         /*}}}*/
 880
 881 // OrderList::AddLoop - Add a loop to the loop list                     /*{{{*/
 882 // ---------------------------------------------------------------------
 883 /* We record the loops. This is a relic since loop breaking is done
 884    genericaly as part of the safety routines. */
 885 bool pkgOrderList::AddLoop(DepIterator D)
 886 {
 887    if (LoopCount < 0 || LoopCount >= 20)
 888       return false;
 889
 890    // Skip dups
 891    if (LoopCount != 0)
 892    {
 893       if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() ||
 894           Loops[LoopCount - 1].TargetPkg() == D.ParentPkg())
 895          return true;
 896    }
 897
 898    Loops[LoopCount++] = D;
 899
 900    // Mark the packages as being part of a loop.
 901    Flag(D.TargetPkg(),Loop);
 902    Flag(D.ParentPkg(),Loop);
 903    return true;
 904 }
 905                                                                         /*}}}*/
 906 // OrderList::WipeFlags - Unset the given flags from all packages       /*{{{*/
 907 // ---------------------------------------------------------------------
 908 /* */
 909 void pkgOrderList::WipeFlags(unsigned long F)
 910 {
 911    unsigned long Size = Cache.Head().PackageCount;
 912    for (unsigned long I = 0; I != Size; I++)
 913       Flags[I] &= ~F;
 914 }
 915                                                                         /*}}}*/
 916 // OrderList::CheckDep - Check a dependency for truth                   /*{{{*/
 917 // ---------------------------------------------------------------------
 918 /* This performs a complete analysis of the dependency wrt to the
 919    current add list. It returns true if after all events are
 920    performed it is still true. This sort of routine can be approximated
 921    by examining the DepCache, however in convoluted cases of provides
 922    this fails to produce a suitable result. */
 923 bool pkgOrderList::CheckDep(DepIterator D)
 924 {
 925    SPtrArray<Version *> List = D.AllTargets();
 926    bool Hit = false;
 927    for (Version **I = List; *I != 0; I++)
 928    {
 929       VerIterator Ver(Cache,*I);
 930       PkgIterator Pkg = Ver.ParentPkg();
 931
 932       /* The meaning of Added and AddPending is subtle. AddPending is
 933          an indication that the package is looping. Because of the
 934          way ordering works Added means the package will be unpacked
 935          before this one and AddPending means after. It is therefore
 936          correct to ignore AddPending in all cases, but that exposes
 937          reverse-ordering loops which should be ignored. */
 938       if (IsFlag(Pkg,Added) == true ||
 939           (IsFlag(Pkg,AddPending) == true && D.Reverse() == true))
 940       {
 941          if (Cache[Pkg].InstallVer != *I)
 942             continue;
 943       }
 944       else
 945          if ((Version *)Pkg.CurrentVer() != *I ||
 946              Pkg.State() != PkgIterator::NeedsNothing)
 947             continue;
 948
 949       /* Conflicts requires that all versions are not present, depends
 950          just needs one */
 951       if (D->Type != pkgCache::Dep::Conflicts &&
 952           D->Type != pkgCache::Dep::Obsoletes)
 953       {
 954          /* Try to find something that does not have the after flag set
 955             if at all possible */
 956          if (IsFlag(Pkg,After) == true)
 957          {
 958             Hit = true;
 959             continue;
 960          }
 961
 962          return true;
 963       }
 964       else
 965       {
 966          if (IsFlag(Pkg,After) == true)
 967             Flag(D.ParentPkg(),After);
 968
 969          return false;
 970       }
 971    }
 972
 973    // We found a hit, but it had the after flag set
 974    if (Hit == true && D->Type == pkgCache::Dep::PreDepends)
 975    {
 976       Flag(D.ParentPkg(),After);
 977       return true;
 978    }
 979
 980    /* Conflicts requires that all versions are not present, depends
 981       just needs one */
 982    if (D->Type == pkgCache::Dep::Conflicts ||
 983        D->Type == pkgCache::Dep::Obsoletes)
 984       return true;
 985    return false;
 986 }
 987                                                                         /*}}}*/