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<config.h>
  67
  68 #include <apt-pkg/orderlist.h>
  69 #include <apt-pkg/depcache.h>
  70 #include <apt-pkg/error.h>
  71 #include <apt-pkg/version.h>
  72 #include <apt-pkg/sptr.h>
  73 #include <apt-pkg/configuration.h>
  74
  75 #include <iostream>
  76                                                                         /*}}}*/
  77
  78 using namespace std;
  79
  80 pkgOrderList *pkgOrderList::Me = 0;
  81
  82 // OrderList::pkgOrderList - Constructor                                /*{{{*/
  83 // ---------------------------------------------------------------------
  84 /* */
  85 pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache)
  86 {
  87    FileList = 0;
  88    Primary = 0;
  89    Secondary = 0;
  90    RevDepends = 0;
  91    Remove = 0;
  92    LoopCount = -1;
  93    Debug = _config->FindB("Debug::pkgOrderList",false);
  94
  95    /* Construct the arrays, egcs 1.0.1 bug requires the package count
  96       hack */
  97    unsigned long Size = Cache.Head().PackageCount;
  98    Flags = new unsigned short[Size];
  99    End = List = new Package *[Size];
 100    memset(Flags,0,sizeof(*Flags)*Size);
 101 }
 102                                                                         /*}}}*/
 103 // OrderList::~pkgOrderList - Destructor                                /*{{{*/
 104 // ---------------------------------------------------------------------
 105 /* */
 106 pkgOrderList::~pkgOrderList()
 107 {
 108    delete [] List;
 109    delete [] Flags;
 110 }
 111                                                                         /*}}}*/
 112 // OrderList::IsMissing - Check if a file is missing                    /*{{{*/
 113 // ---------------------------------------------------------------------
 114 /* */
 115 bool pkgOrderList::IsMissing(PkgIterator Pkg)
 116 {
 117    // Skip packages to erase
 118    if (Cache[Pkg].Delete() == true)
 119       return false;
 120
 121    // Skip Packages that need configure only.
 122    if ((Pkg.State() == pkgCache::PkgIterator::NeedsConfigure ||
 123         Pkg.State() == pkgCache::PkgIterator::NeedsNothing) &&
 124        Cache[Pkg].Keep() == true)
 125       return false;
 126
 127    if (FileList == 0)
 128       return false;
 129
 130    if (FileList[Pkg->ID].empty() == false)
 131       return false;
 132
 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), "DoRun") == 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.FullName() << ' ' << 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.FullName() << ' ' << 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 Res;
 496 }
 497                                                                         /*}}}*/
 498 // OrderList::VisitProvides - Visit all of the providing packages       /*{{{*/
 499 // ---------------------------------------------------------------------
 500 /* This routine calls visit on all providing packages.
 501
 502    If the dependency is negative it first visits packages which are
 503    intended to be removed and after that all other packages.
 504    It does so to avoid situations in which this package is used to
 505    satisfy a (or-group/provides) dependency of another package which
 506    could have been satisfied also by upgrading another package -
 507    otherwise we have more broken packages dpkg needs to auto-
 508    deconfigure and in very complicated situations it even decides
 509    against it! */
 510 bool pkgOrderList::VisitProvides(DepIterator D,bool Critical)
 511 {
 512    SPtrArray<Version *> List = D.AllTargets();
 513    for (Version **I = List; *I != 0; ++I)
 514    {
 515       VerIterator Ver(Cache,*I);
 516       PkgIterator Pkg = Ver.ParentPkg();
 517
 518       if (D.IsNegative() == true && Cache[Pkg].Delete() == false)
 519          continue;
 520
 521       if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
 522          continue;
 523
 524       if (D.IsNegative() == false &&
 525           Cache[Pkg].InstallVer != *I)
 526          continue;
 527
 528       if (D.IsNegative() == true &&
 529           (Version *)Pkg.CurrentVer() != *I)
 530          continue;
 531
 532       // Skip over missing files
 533       if (Critical == false && IsMissing(D.ParentPkg()) == true)
 534          continue;
 535
 536       if (VisitNode(Pkg, "Provides-1") == false)
 537          return false;
 538    }
 539    if (D.IsNegative() == false)
 540       return true;
 541    for (Version **I = List; *I != 0; ++I)
 542    {
 543       VerIterator Ver(Cache,*I);
 544       PkgIterator Pkg = Ver.ParentPkg();
 545
 546       if (Cache[Pkg].Delete() == true)
 547          continue;
 548
 549       if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
 550          continue;
 551
 552       if ((Version *)Pkg.CurrentVer() != *I)
 553          continue;
 554
 555       // Skip over missing files
 556       if (Critical == false && IsMissing(D.ParentPkg()) == true)
 557          continue;
 558
 559       if (VisitNode(Pkg, "Provides-2") == false)
 560          return false;
 561    }
 562
 563    return true;
 564 }
 565                                                                         /*}}}*/
 566 // OrderList::VisitNode - Recursive ordering director                   /*{{{*/
 567 // ---------------------------------------------------------------------
 568 /* This is the core ordering routine. It calls the set dependency
 569    consideration functions which then potentialy call this again. Finite
 570    depth is achived through the colouring mechinism. */
 571 bool pkgOrderList::VisitNode(PkgIterator Pkg, char const* from)
 572 {
 573    // Looping or irrelevent.
 574    // This should probably trancend not installed packages
 575    if (Pkg.end() == true || IsFlag(Pkg,Added) == true ||
 576        IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false)
 577       return true;
 578
 579    if (Debug == true)
 580    {
 581       for (int j = 0; j != Depth; j++) clog << ' ';
 582       clog << "Visit " << Pkg.FullName() << " from " << from << endl;
 583    }
 584
 585    Depth++;
 586
 587    // Color grey
 588    Flag(Pkg,AddPending);
 589
 590    DepFunc Old = Primary;
 591
 592    // Perform immedate configuration of the package if so flagged.
 593    if (IsFlag(Pkg,Immediate) == true && Primary != &pkgOrderList::DepUnPackPre)
 594       Primary = &pkgOrderList::DepUnPackPreD;
 595
 596    if (IsNow(Pkg) == true)
 597    {
 598       bool Res = true;
 599       if (Cache[Pkg].Delete() == false)
 600       {
 601          // Primary
 602          Res &= Res && VisitDeps(Primary,Pkg);
 603          Res &= Res && VisitRDeps(Primary,Pkg);
 604          Res &= Res && VisitRProvides(Primary,Pkg.CurrentVer());
 605          Res &= Res && VisitRProvides(Primary,Cache[Pkg].InstVerIter(Cache));
 606
 607          // RevDep
 608          Res &= Res && VisitRDeps(RevDepends,Pkg);
 609          Res &= Res && VisitRProvides(RevDepends,Pkg.CurrentVer());
 610          Res &= Res && VisitRProvides(RevDepends,Cache[Pkg].InstVerIter(Cache));
 611
 612          // Secondary
 613          Res &= Res && VisitDeps(Secondary,Pkg);
 614          Res &= Res && VisitRDeps(Secondary,Pkg);
 615          Res &= Res && VisitRProvides(Secondary,Pkg.CurrentVer());
 616          Res &= Res && VisitRProvides(Secondary,Cache[Pkg].InstVerIter(Cache));
 617       }
 618       else
 619       {
 620          // RevDep
 621          Res &= Res && VisitRDeps(Remove,Pkg);
 622          Res &= Res && VisitRProvides(Remove,Pkg.CurrentVer());
 623       }
 624    }
 625
 626    if (IsFlag(Pkg,Added) == false)
 627    {
 628       Flag(Pkg,Added,Added | AddPending);
 629       if (IsFlag(Pkg,After) == true)
 630          *AfterEnd++ = Pkg;
 631       else
 632          *End++ = Pkg;
 633    }
 634
 635    Primary = Old;
 636    Depth--;
 637
 638    if (Debug == true)
 639    {
 640       for (int j = 0; j != Depth; j++) clog << ' ';
 641       clog << "Leave " << Pkg.FullName() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;
 642    }
 643
 644    return true;
 645 }
 646                                                                         /*}}}*/
 647 // OrderList::DepUnPackCrit - Critical UnPacking ordering               /*{{{*/
 648 // ---------------------------------------------------------------------
 649 /* Critical unpacking ordering strives to satisfy Conflicts: and
 650    PreDepends: only. When a prdepends is encountered the Primary
 651    DepFunc is changed to be DepUnPackPreD.
 652
 653    Loops are preprocessed and logged. */
 654 bool pkgOrderList::DepUnPackCrit(DepIterator D)
 655 {
 656    for (; D.end() == false; ++D)
 657    {
 658       if (D.Reverse() == true)
 659       {
 660          /* Reverse depenanices are only interested in conflicts,
 661             predepend breakage is ignored here */
 662          if (D->Type != pkgCache::Dep::Conflicts &&
 663              D->Type != pkgCache::Dep::Obsoletes)
 664             continue;
 665
 666          // Duplication elimination, consider only the current version
 667          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 668             continue;
 669
 670          /* For reverse dependencies we wish to check if the
 671             dependency is satisifed in the install state. The
 672             target package (caller) is going to be in the installed
 673             state. */
 674          if (CheckDep(D) == true)
 675             continue;
 676
 677          if (VisitNode(D.ParentPkg(), "UnPackCrit") == false)
 678             return false;
 679       }
 680       else
 681       {
 682          /* Forward critical dependencies MUST be correct before the
 683             package can be unpacked. */
 684          if (D.IsNegative() == false &&
 685              D->Type != pkgCache::Dep::PreDepends)
 686             continue;
 687
 688          /* We wish to check if the dep is okay in the now state of the
 689             target package against the install state of this package. */
 690          if (CheckDep(D) == true)
 691          {
 692             /* We want to catch predepends loops with the code below.
 693                Conflicts loops that are Dep OK are ignored */
 694             if (IsFlag(D.TargetPkg(),AddPending) == false ||
 695                 D->Type != pkgCache::Dep::PreDepends)
 696                continue;
 697          }
 698
 699          // This is the loop detection
 700          if (IsFlag(D.TargetPkg(),Added) == true ||
 701              IsFlag(D.TargetPkg(),AddPending) == true)
 702          {
 703             if (IsFlag(D.TargetPkg(),AddPending) == true)
 704                AddLoop(D);
 705             continue;
 706          }
 707
 708          /* Predepends require a special ordering stage, they must have
 709             all dependents installed as well */
 710          DepFunc Old = Primary;
 711          bool Res = false;
 712          if (D->Type == pkgCache::Dep::PreDepends)
 713             Primary = &pkgOrderList::DepUnPackPreD;
 714          Res = VisitProvides(D,true);
 715          Primary = Old;
 716          if (Res == false)
 717             return false;
 718       }
 719    }
 720    return true;
 721 }
 722                                                                         /*}}}*/
 723 // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends  /*{{{*/
 724 // ---------------------------------------------------------------------
 725 /* Critical PreDepends (also configure immediate and essential) strives to
 726    ensure not only that all conflicts+predepends are met but that this
 727    package will be immediately configurable when it is unpacked.
 728    Loops are preprocessed and logged. */
 729 bool pkgOrderList::DepUnPackPreD(DepIterator D)
 730 {
 731    if (D.Reverse() == true)
 732       return DepUnPackCrit(D);
 733
 734    for (; D.end() == false; ++D)
 735    {
 736       if (D.IsCritical() == false)
 737          continue;
 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              D->Type != pkgCache::Dep::PreDepends)
 747             continue;
 748       }
 749
 750       // This is the loop detection
 751       if (IsFlag(D.TargetPkg(),Added) == true ||
 752           IsFlag(D.TargetPkg(),AddPending) == true)
 753       {
 754          if (IsFlag(D.TargetPkg(),AddPending) == true)
 755             AddLoop(D);
 756          continue;
 757       }
 758
 759       if (VisitProvides(D,true) == false)
 760          return false;
 761    }
 762    return true;
 763 }
 764                                                                         /*}}}*/
 765 // OrderList::DepUnPackPre - Critical Predepends ordering               /*{{{*/
 766 // ---------------------------------------------------------------------
 767 /* Critical PreDepends (also configure immediate and essential) strives to
 768    ensure not only that all conflicts+predepends are met but that this
 769    package will be immediately configurable when it is unpacked.
 770
 771    Loops are preprocessed and logged. All loops will be fatal. */
 772 bool pkgOrderList::DepUnPackPre(DepIterator D)
 773 {
 774    if (D.Reverse() == true)
 775       return true;
 776
 777    for (; D.end() == false; ++D)
 778    {
 779       /* Only consider the PreDepends or Depends. Depends are only
 780          considered at the lowest depth or in the case of immediate
 781          configure */
 782       if (D->Type != pkgCache::Dep::PreDepends)
 783       {
 784          if (D->Type == pkgCache::Dep::Depends)
 785          {
 786             if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false)
 787                continue;
 788          }
 789          else
 790             continue;
 791       }
 792
 793       /* We wish to check if the dep is okay in the now state of the
 794          target package against the install state of this package. */
 795       if (CheckDep(D) == true)
 796       {
 797          /* We want to catch predepends loops with the code below.
 798             Conflicts loops that are Dep OK are ignored */
 799          if (IsFlag(D.TargetPkg(),AddPending) == false)
 800             continue;
 801       }
 802
 803       // This is the loop detection
 804       if (IsFlag(D.TargetPkg(),Added) == true ||
 805           IsFlag(D.TargetPkg(),AddPending) == true)
 806       {
 807          if (IsFlag(D.TargetPkg(),AddPending) == true)
 808             AddLoop(D);
 809          continue;
 810       }
 811
 812       if (VisitProvides(D,true) == false)
 813          return false;
 814    }
 815    return true;
 816 }
 817                                                                         /*}}}*/
 818 // OrderList::DepUnPackDep - Reverse dependency considerations          /*{{{*/
 819 // ---------------------------------------------------------------------
 820 /* Reverse dependencies are considered to determine if unpacking this
 821    package will break any existing dependencies. If so then those
 822    packages are ordered before this one so that they are in the
 823    UnPacked state.
 824
 825    The forwards depends loop is designed to bring the packages dependents
 826    close to the package. This helps reduce deconfigure time.
 827
 828    Loops are irrelevent to this. */
 829 bool pkgOrderList::DepUnPackDep(DepIterator D)
 830 {
 831
 832    for (; D.end() == false; ++D)
 833       if (D.IsCritical() == true)
 834       {
 835          if (D.Reverse() == true)
 836          {
 837             /* Duplication prevention. We consider rev deps only on
 838                the current version, a not installed package
 839                cannot break */
 840             if (D.ParentPkg()->CurrentVer == 0 ||
 841                 D.ParentPkg().CurrentVer() != D.ParentVer())
 842                continue;
 843
 844             // The dep will not break so it is irrelevent.
 845             if (CheckDep(D) == true)
 846                continue;
 847
 848             // Skip over missing files
 849             if (IsMissing(D.ParentPkg()) == true)
 850                continue;
 851
 852             if (VisitNode(D.ParentPkg(), "UnPackDep-Parent") == false)
 853                return false;
 854          }
 855          else
 856          {
 857             if (D->Type == pkgCache::Dep::Depends)
 858                if (VisitProvides(D,false) == false)
 859                   return false;
 860
 861             if (D->Type == pkgCache::Dep::DpkgBreaks)
 862             {
 863                if (CheckDep(D) == true)
 864                  continue;
 865
 866                if (VisitNode(D.TargetPkg(), "UnPackDep-Target") == false)
 867                  return false;
 868             }
 869          }
 870       }
 871    return true;
 872 }
 873                                                                         /*}}}*/
 874 // OrderList::DepConfigure - Configuration ordering                     /*{{{*/
 875 // ---------------------------------------------------------------------
 876 /* Configuration only ordering orders by the Depends: line only. It
 877    orders configuration so that when a package comes to be configured it's
 878    dependents are configured.
 879
 880    Loops are ingored. Depends loop entry points are chaotic. */
 881 bool pkgOrderList::DepConfigure(DepIterator D)
 882 {
 883    // Never consider reverse configuration dependencies.
 884    if (D.Reverse() == true)
 885       return true;
 886
 887    for (; D.end() == false; ++D)
 888       if (D->Type == pkgCache::Dep::Depends)
 889          if (VisitProvides(D,false) == false)
 890             return false;
 891    return true;
 892 }
 893                                                                         /*}}}*/
 894 // OrderList::DepRemove - Removal ordering                              /*{{{*/
 895 // ---------------------------------------------------------------------
 896 /* Removal visits all reverse depends. It considers if the dependency
 897    of the Now state version to see if it is okay with removing this
 898    package. This check should always fail, but is provided for symetery
 899    with the other critical handlers.
 900
 901    Loops are preprocessed and logged. Removal loops can also be
 902    detected in the critical handler. They are characterized by an
 903    old version of A depending on B but the new version of A conflicting
 904    with B, thus either A or B must break to install. */
 905 bool pkgOrderList::DepRemove(DepIterator D)
 906 {
 907    if (D.Reverse() == false)
 908       return true;
 909    for (; D.end() == false; ++D)
 910       if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 911       {
 912          // Duplication elimination, consider the current version only
 913          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 914             continue;
 915
 916          /* We wish to see if the dep on the parent package is okay
 917             in the removed (install) state of the target pkg. */
 918          bool tryFixDeps = false;
 919          if (CheckDep(D) == true)
 920          {
 921             // We want to catch loops with the code below.
 922             if (IsFlag(D.ParentPkg(),AddPending) == false)
 923                continue;
 924          }
 925          else
 926             tryFixDeps = true;
 927
 928          // This is the loop detection
 929          if (IsFlag(D.ParentPkg(),Added) == true ||
 930              IsFlag(D.ParentPkg(),AddPending) == true)
 931          {
 932             if (IsFlag(D.ParentPkg(),AddPending) == true)
 933                AddLoop(D);
 934             continue;
 935          }
 936
 937          if (tryFixDeps == true)
 938          {
 939             for (pkgCache::DepIterator F = D.ParentPkg().CurrentVer().DependsList();
 940                  F.end() == false; ++F)
 941             {
 942                if (F->Type != pkgCache::Dep::Depends && F->Type != pkgCache::Dep::PreDepends)
 943                   continue;
 944                // Check the Providers
 945                if (F.TargetPkg()->ProvidesList != 0)
 946                {
 947                   pkgCache::PrvIterator Prov = F.TargetPkg().ProvidesList();
 948                   for (; Prov.end() == false; ++Prov)
 949                   {
 950                      pkgCache::PkgIterator const P = Prov.OwnerPkg();
 951                      if (IsFlag(P, InList) == true &&
 952                          IsFlag(P, AddPending) == true &&
 953                          IsFlag(P, Added) == false &&
 954                          Cache[P].InstallVer == 0)
 955                         break;
 956                   }
 957                   if (Prov.end() == false)
 958                      for (pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList();
 959                           Prv.end() == false; ++Prv)
 960                      {
 961                         pkgCache::PkgIterator const P = Prv.OwnerPkg();
 962                         if (IsFlag(P, InList) == true &&
 963                             IsFlag(P, AddPending) == false &&
 964                             Cache[P].InstallVer != 0 &&
 965                             VisitNode(P, "Remove-P") == true)
 966                         {
 967                            Flag(P, Immediate);
 968                            tryFixDeps = false;
 969                            break;
 970                         }
 971                      }
 972                   if (tryFixDeps == false)
 973                      break;
 974                }
 975
 976                // Check for Or groups
 977                if ((F->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or)
 978                   continue;
 979                // Lets see if the package is part of the Or group
 980                pkgCache::DepIterator S = F;
 981                for (; S.end() == false; ++S)
 982                {
 983                   if (S.TargetPkg() == D.TargetPkg())
 984                      break;
 985                   if ((S->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or ||
 986                       CheckDep(S)) // Or group is satisfied by another package
 987                      for (;S.end() == false; ++S);
 988                }
 989                if (S.end() == true)
 990                   continue;
 991                // skip to the end of the or group
 992                for (;S.end() == false && (S->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; ++S);
 993                ++S;
 994                // The soon to be removed is part of the Or group
 995                // start again in the or group and find something which will serve as replacement
 996                for (; F.end() == false && F != S; ++F)
 997                {
 998                   if (IsFlag(F.TargetPkg(), InList) == true &&
 999                       IsFlag(F.TargetPkg(), AddPending) == false &&
1000                       Cache[F.TargetPkg()].InstallVer != 0 &&
1001                       VisitNode(F.TargetPkg(), "Remove-Target") == true)
1002                   {
1003                      Flag(F.TargetPkg(), Immediate);
1004                      tryFixDeps = false;
1005                      break;
1006                   }
1007                   else if (F.TargetPkg()->ProvidesList != 0)
1008                   {
1009                      pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList();
1010                      for (; Prv.end() == false; ++Prv)
1011                      {
1012                         if (IsFlag(Prv.OwnerPkg(), InList) == true &&
1013                             IsFlag(Prv.OwnerPkg(), AddPending) == false &&
1014                             Cache[Prv.OwnerPkg()].InstallVer != 0 &&
1015                             VisitNode(Prv.OwnerPkg(), "Remove-Owner") == true)
1016                         {
1017                            Flag(Prv.OwnerPkg(), Immediate);
1018                            tryFixDeps = false;
1019                            break;
1020                         }
1021                      }
1022                      if (Prv.end() == false)
1023                         break;
1024                   }
1025                }
1026                if (tryFixDeps == false)
1027                   break;
1028             }
1029          }
1030
1031          // Skip over missing files
1032          if (IsMissing(D.ParentPkg()) == true)
1033             continue;
1034
1035          if (VisitNode(D.ParentPkg(), "Remove-Parent") == false)
1036             return false;
1037       }
1038
1039    return true;
1040 }
1041                                                                         /*}}}*/
1042 // OrderList::AddLoop - Add a loop to the loop list                     /*{{{*/
1043 // ---------------------------------------------------------------------
1044 /* We record the loops. This is a relic since loop breaking is done
1045    genericaly as part of the safety routines. */
1046 bool pkgOrderList::AddLoop(DepIterator D)
1047 {
1048    if (LoopCount < 0 || LoopCount >= 20)
1049       return false;
1050
1051    // Skip dups
1052    if (LoopCount != 0)
1053    {
1054       if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() ||
1055           Loops[LoopCount - 1].TargetPkg() == D.ParentPkg())
1056          return true;
1057    }
1058
1059    Loops[LoopCount++] = D;
1060
1061    // Mark the packages as being part of a loop.
1062    //Flag(D.TargetPkg(),Loop);
1063    //Flag(D.ParentPkg(),Loop);
1064    /* This is currently disabled because the Loop flag is being used for
1065       loop management in the package manager. Check the orderlist.h file for more info */
1066    return true;
1067 }
1068                                                                         /*}}}*/
1069 // OrderList::WipeFlags - Unset the given flags from all packages       /*{{{*/
1070 // ---------------------------------------------------------------------
1071 /* */
1072 void pkgOrderList::WipeFlags(unsigned long F)
1073 {
1074    unsigned long Size = Cache.Head().PackageCount;
1075    for (unsigned long I = 0; I != Size; I++)
1076       Flags[I] &= ~F;
1077 }
1078                                                                         /*}}}*/
1079 // OrderList::CheckDep - Check a dependency for truth                   /*{{{*/
1080 // ---------------------------------------------------------------------
1081 /* This performs a complete analysis of the dependency wrt to the
1082    current add list. It returns true if after all events are
1083    performed it is still true. This sort of routine can be approximated
1084    by examining the DepCache, however in convoluted cases of provides
1085    this fails to produce a suitable result. */
1086 bool pkgOrderList::CheckDep(DepIterator D)
1087 {
1088    SPtrArray<Version *> List = D.AllTargets();
1089    bool Hit = false;
1090    for (Version **I = List; *I != 0; I++)
1091    {
1092       VerIterator Ver(Cache,*I);
1093       PkgIterator Pkg = Ver.ParentPkg();
1094
1095       /* The meaning of Added and AddPending is subtle. AddPending is
1096          an indication that the package is looping. Because of the
1097          way ordering works Added means the package will be unpacked
1098          before this one and AddPending means after. It is therefore
1099          correct to ignore AddPending in all cases, but that exposes
1100          reverse-ordering loops which should be ignored. */
1101       if (IsFlag(Pkg,Added) == true ||
1102           (IsFlag(Pkg,AddPending) == true && D.Reverse() == true))
1103       {
1104          if (Cache[Pkg].InstallVer != *I)
1105             continue;
1106       }
1107       else
1108          if ((Version *)Pkg.CurrentVer() != *I ||
1109              Pkg.State() != PkgIterator::NeedsNothing)
1110             continue;
1111
1112       /* Conflicts requires that all versions are not present, depends
1113          just needs one */
1114       if (D.IsNegative() == false)
1115       {
1116          // ignore provides by older versions of this package
1117          if (((D.Reverse() == false && Pkg == D.ParentPkg()) ||
1118               (D.Reverse() == true && Pkg == D.TargetPkg())) &&
1119              Cache[Pkg].InstallVer != *I)
1120             continue;
1121
1122          /* Try to find something that does not have the after flag set
1123             if at all possible */
1124          if (IsFlag(Pkg,After) == true)
1125          {
1126             Hit = true;
1127             continue;
1128          }
1129
1130          return true;
1131       }
1132       else
1133       {
1134          if (IsFlag(Pkg,After) == true)
1135             Flag(D.ParentPkg(),After);
1136
1137          return false;
1138       }
1139    }
1140
1141    // We found a hit, but it had the after flag set
1142    if (Hit == true && D->Type == pkgCache::Dep::PreDepends)
1143    {
1144       Flag(D.ParentPkg(),After);
1145       return true;
1146    }
1147
1148    /* Conflicts requires that all versions are not present, depends
1149       just needs one */
1150    if (D->Type == pkgCache::Dep::Conflicts ||
1151        D->Type == pkgCache::Dep::Obsoletes)
1152       return true;
1153    return false;
1154 }
1155                                                                         /*}}}*/