apt-pkg/orderlist.cc

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