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