apt-pkg/orderlist.cc

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