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    // Removals should be done after we dealt with essentials
 305    static int const ScoreDelete = _config->FindI("OrderList::Score::Delete", 100);
 306    if (Cache[Pkg].Delete() == true)
 307       return ScoreDelete;
 308
 309    // This should never happen..
 310    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 311       return -1;
 312
 313    static int const ScoreEssential = _config->FindI("OrderList::Score::Essential", 200);
 314    static int const ScoreImmediate = _config->FindI("OrderList::Score::Immediate", 10);
 315    static int const ScorePreDepends = _config->FindI("OrderList::Score::PreDepends", 50);
 316
 317    int Score = 0;
 318    if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 319       Score += ScoreEssential;
 320
 321    if (IsFlag(Pkg,Immediate) == true)
 322       Score += ScoreImmediate;
 323
 324    for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList();
 325         D.end() == false; ++D)
 326       if (D->Type == pkgCache::Dep::PreDepends)
 327       {
 328          Score += ScorePreDepends;
 329          break;
 330       }
 331
 332    // Important Required Standard Optional Extra
 333    if (Cache[Pkg].InstVerIter(Cache)->Priority <= 5)
 334    {
 335       signed short PrioMap[] = {0,5,4,3,1,0};
 336       Score += PrioMap[Cache[Pkg].InstVerIter(Cache)->Priority];
 337    }
 338    return Score;
 339 }
 340                                                                         /*}}}*/
 341 // OrderList::FileCmp - Compare by package file                         /*{{{*/
 342 // ---------------------------------------------------------------------
 343 /* This compares by the package file that the install version is in. */
 344 int pkgOrderList::FileCmp(PkgIterator A,PkgIterator B)
 345 {
 346    if (Cache[A].Delete() == true && Cache[B].Delete() == true)
 347       return 0;
 348    if (Cache[A].Delete() == true)
 349       return -1;
 350    if (Cache[B].Delete() == true)
 351       return 1;
 352
 353    if (Cache[A].InstVerIter(Cache).FileList().end() == true)
 354       return -1;
 355    if (Cache[B].InstVerIter(Cache).FileList().end() == true)
 356       return 1;
 357
 358    pkgCache::PackageFile *FA = Cache[A].InstVerIter(Cache).FileList().File();
 359    pkgCache::PackageFile *FB = Cache[B].InstVerIter(Cache).FileList().File();
 360    if (FA < FB)
 361       return -1;
 362    if (FA > FB)
 363       return 1;
 364    return 0;
 365 }
 366                                                                         /*}}}*/
 367 // BoolCompare - Comparison function for two booleans                   /*{{{*/
 368 // ---------------------------------------------------------------------
 369 /* */
 370 static int BoolCompare(bool A,bool B)
 371 {
 372    if (A == B)
 373       return 0;
 374    if (A == false)
 375       return -1;
 376    return 1;
 377 }
 378                                                                         /*}}}*/
 379 // OrderList::OrderCompareA - Order the installation by op              /*{{{*/
 380 // ---------------------------------------------------------------------
 381 /* This provides a first-pass sort of the list and gives a decent starting
 382     point for further complete ordering. It is used by OrderUnpack only */
 383 int pkgOrderList::OrderCompareA(const void *a, const void *b)
 384 {
 385    PkgIterator A(Me->Cache,*(Package **)a);
 386    PkgIterator B(Me->Cache,*(Package **)b);
 387
 388    // We order packages with a set state toward the front
 389    int Res;
 390    if ((Res = BoolCompare(Me->IsNow(A),Me->IsNow(B))) != 0)
 391       return -1*Res;
 392
 393    // We order missing files to toward the end
 394 /*   if (Me->FileList != 0)
 395    {
 396       if ((Res = BoolCompare(Me->IsMissing(A),
 397                              Me->IsMissing(B))) != 0)
 398          return Res;
 399    }*/
 400
 401    if (A.State() != pkgCache::PkgIterator::NeedsNothing &&
 402        B.State() == pkgCache::PkgIterator::NeedsNothing)
 403       return -1;
 404
 405    if (A.State() == pkgCache::PkgIterator::NeedsNothing &&
 406        B.State() != pkgCache::PkgIterator::NeedsNothing)
 407       return 1;
 408
 409    int ScoreA = Me->Score(A);
 410    int ScoreB = Me->Score(B);
 411
 412    if (ScoreA > ScoreB)
 413       return -1;
 414
 415    if (ScoreA < ScoreB)
 416       return 1;
 417
 418    return strcmp(A.Name(),B.Name());
 419 }
 420                                                                         /*}}}*/
 421 // OrderList::OrderCompareB - Order the installation by source          /*{{{*/
 422 // ---------------------------------------------------------------------
 423 /* This orders by installation source. This is useful to handle
 424    inter-source breaks */
 425 int pkgOrderList::OrderCompareB(const void *a, const void *b)
 426 {
 427    PkgIterator A(Me->Cache,*(Package **)a);
 428    PkgIterator B(Me->Cache,*(Package **)b);
 429
 430    if (A.State() != pkgCache::PkgIterator::NeedsNothing &&
 431        B.State() == pkgCache::PkgIterator::NeedsNothing)
 432       return -1;
 433
 434    if (A.State() == pkgCache::PkgIterator::NeedsNothing &&
 435        B.State() != pkgCache::PkgIterator::NeedsNothing)
 436       return 1;
 437
 438    int F = Me->FileCmp(A,B);
 439    if (F != 0)
 440    {
 441       if (F > 0)
 442          return -1;
 443       return 1;
 444    }
 445
 446    int ScoreA = Me->Score(A);
 447    int ScoreB = Me->Score(B);
 448
 449    if (ScoreA > ScoreB)
 450       return -1;
 451
 452    if (ScoreA < ScoreB)
 453       return 1;
 454
 455    return strcmp(A.Name(),B.Name());
 456 }
 457                                                                         /*}}}*/
 458 // OrderList::VisitDeps - Visit forward install dependencies            /*{{{*/
 459 // ---------------------------------------------------------------------
 460 /* This calls the dependency function for the normal forwards dependencies
 461    of the package */
 462 bool pkgOrderList::VisitDeps(DepFunc F,PkgIterator Pkg)
 463 {
 464    if (F == 0 || Pkg.end() == true || Cache[Pkg].InstallVer == 0)
 465       return true;
 466
 467    return (this->*F)(Cache[Pkg].InstVerIter(Cache).DependsList());
 468 }
 469                                                                         /*}}}*/
 470 // OrderList::VisitRDeps - Visit reverse dependencies                   /*{{{*/
 471 // ---------------------------------------------------------------------
 472 /* This calls the dependency function for all of the normal reverse depends
 473    of the package */
 474 bool pkgOrderList::VisitRDeps(DepFunc F,PkgIterator Pkg)
 475 {
 476    if (F == 0 || Pkg.end() == true)
 477       return true;
 478
 479    return (this->*F)(Pkg.RevDependsList());
 480 }
 481                                                                         /*}}}*/
 482 // OrderList::VisitRProvides - Visit provides reverse dependencies      /*{{{*/
 483 // ---------------------------------------------------------------------
 484 /* This calls the dependency function for all reverse dependencies
 485    generated by the provides line on the package. */
 486 bool pkgOrderList::VisitRProvides(DepFunc F,VerIterator Ver)
 487 {
 488    if (F == 0 || Ver.end() == true)
 489       return true;
 490
 491    bool Res = true;
 492    for (PrvIterator P = Ver.ProvidesList(); P.end() == false; ++P)
 493       Res &= (this->*F)(P.ParentPkg().RevDependsList());
 494    return Res;
 495 }
 496                                                                         /*}}}*/
 497 // OrderList::VisitProvides - Visit all of the providing packages       /*{{{*/
 498 // ---------------------------------------------------------------------
 499 /* This routine calls visit on all providing packages.
 500
 501    If the dependency is negative it first visits packages which are
 502    intended to be removed and after that all other packages.
 503    It does so to avoid situations in which this package is used to
 504    satisfy a (or-group/provides) dependency of another package which
 505    could have been satisfied also by upgrading another package -
 506    otherwise we have more broken packages dpkg needs to auto-
 507    deconfigure and in very complicated situations it even decides
 508    against it! */
 509 bool pkgOrderList::VisitProvides(DepIterator D,bool Critical)
 510 {
 511    SPtrArray<Version *> List = D.AllTargets();
 512    for (Version **I = List; *I != 0; ++I)
 513    {
 514       VerIterator Ver(Cache,*I);
 515       PkgIterator Pkg = Ver.ParentPkg();
 516
 517       if (D.IsNegative() == true && Cache[Pkg].Delete() == false)
 518          continue;
 519
 520       if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
 521          continue;
 522
 523       if (D.IsNegative() == false &&
 524           Cache[Pkg].InstallVer != *I)
 525          continue;
 526
 527       if (D.IsNegative() == true &&
 528           (Version *)Pkg.CurrentVer() != *I)
 529          continue;
 530
 531       // Skip over missing files
 532       if (Critical == false && IsMissing(D.ParentPkg()) == true)
 533          continue;
 534
 535       if (VisitNode(Pkg, "Provides-1") == false)
 536          return false;
 537    }
 538    if (D.IsNegative() == false)
 539       return true;
 540    for (Version **I = List; *I != 0; ++I)
 541    {
 542       VerIterator Ver(Cache,*I);
 543       PkgIterator Pkg = Ver.ParentPkg();
 544
 545       if (Cache[Pkg].Delete() == true)
 546          continue;
 547
 548       if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
 549          continue;
 550
 551       if ((Version *)Pkg.CurrentVer() != *I)
 552          continue;
 553
 554       // Skip over missing files
 555       if (Critical == false && IsMissing(D.ParentPkg()) == true)
 556          continue;
 557
 558       if (VisitNode(Pkg, "Provides-2") == false)
 559          return false;
 560    }
 561
 562    return true;
 563 }
 564                                                                         /*}}}*/
 565 // OrderList::VisitNode - Recursive ordering director                   /*{{{*/
 566 // ---------------------------------------------------------------------
 567 /* This is the core ordering routine. It calls the set dependency
 568    consideration functions which then potentialy call this again. Finite
 569    depth is achieved through the colouring mechinism. */
 570 bool pkgOrderList::VisitNode(PkgIterator Pkg, char const* from)
 571 {
 572    // Looping or irrelevant.
 573    // This should probably trancend not installed packages
 574    if (Pkg.end() == true || IsFlag(Pkg,Added) == true ||
 575        IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false)
 576       return true;
 577
 578    if (Debug == true)
 579    {
 580       for (int j = 0; j != Depth; j++) clog << ' ';
 581       clog << "Visit " << Pkg.FullName() << " from " << from << endl;
 582    }
 583
 584    Depth++;
 585
 586    // Color grey
 587    Flag(Pkg,AddPending);
 588
 589    DepFunc Old = Primary;
 590
 591    // Perform immedate configuration of the package if so flagged.
 592    if (IsFlag(Pkg,Immediate) == true && Primary != &pkgOrderList::DepUnPackPre)
 593       Primary = &pkgOrderList::DepUnPackPreD;
 594
 595    if (IsNow(Pkg) == true)
 596    {
 597       bool Res = true;
 598       if (Cache[Pkg].Delete() == false)
 599       {
 600          // Primary
 601          Res &= Res && VisitDeps(Primary,Pkg);
 602          Res &= Res && VisitRDeps(Primary,Pkg);
 603          Res &= Res && VisitRProvides(Primary,Pkg.CurrentVer());
 604          Res &= Res && VisitRProvides(Primary,Cache[Pkg].InstVerIter(Cache));
 605
 606          // RevDep
 607          Res &= Res && VisitRDeps(RevDepends,Pkg);
 608          Res &= Res && VisitRProvides(RevDepends,Pkg.CurrentVer());
 609          Res &= Res && VisitRProvides(RevDepends,Cache[Pkg].InstVerIter(Cache));
 610
 611          // Secondary
 612          Res &= Res && VisitDeps(Secondary,Pkg);
 613          Res &= Res && VisitRDeps(Secondary,Pkg);
 614          Res &= Res && VisitRProvides(Secondary,Pkg.CurrentVer());
 615          Res &= Res && VisitRProvides(Secondary,Cache[Pkg].InstVerIter(Cache));
 616       }
 617       else
 618       {
 619          // RevDep
 620          Res &= Res && VisitRDeps(Remove,Pkg);
 621          Res &= Res && VisitRProvides(Remove,Pkg.CurrentVer());
 622       }
 623    }
 624
 625    if (IsFlag(Pkg,Added) == false)
 626    {
 627       Flag(Pkg,Added,Added | AddPending);
 628       if (IsFlag(Pkg,After) == true)
 629          *AfterEnd++ = Pkg;
 630       else
 631          *End++ = Pkg;
 632    }
 633
 634    Primary = Old;
 635    Depth--;
 636
 637    if (Debug == true)
 638    {
 639       for (int j = 0; j != Depth; j++) clog << ' ';
 640       clog << "Leave " << Pkg.FullName() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;
 641    }
 642
 643    return true;
 644 }
 645                                                                         /*}}}*/
 646 // OrderList::DepUnPackCrit - Critical UnPacking ordering               /*{{{*/
 647 // ---------------------------------------------------------------------
 648 /* Critical unpacking ordering strives to satisfy Conflicts: and
 649    PreDepends: only. When a prdepends is encountered the Primary
 650    DepFunc is changed to be DepUnPackPreD.
 651
 652    Loops are preprocessed and logged. */
 653 bool pkgOrderList::DepUnPackCrit(DepIterator D)
 654 {
 655    for (; D.end() == false; ++D)
 656    {
 657       if (D.Reverse() == true)
 658       {
 659          /* Reverse depenanices are only interested in conflicts,
 660             predepend breakage is ignored here */
 661          if (D->Type != pkgCache::Dep::Conflicts &&
 662              D->Type != pkgCache::Dep::Obsoletes)
 663             continue;
 664
 665          // Duplication elimination, consider only the current version
 666          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 667             continue;
 668
 669          /* For reverse dependencies we wish to check if the
 670             dependency is satisifed in the install state. The
 671             target package (caller) is going to be in the installed
 672             state. */
 673          if (CheckDep(D) == true)
 674             continue;
 675
 676          if (VisitNode(D.ParentPkg(), "UnPackCrit") == false)
 677             return false;
 678       }
 679       else
 680       {
 681          /* Forward critical dependencies MUST be correct before the
 682             package can be unpacked. */
 683          if (D.IsNegative() == false &&
 684              D->Type != pkgCache::Dep::PreDepends)
 685             continue;
 686
 687          /* We wish to check if the dep is okay in the now state of the
 688             target package against the install state of this package. */
 689          if (CheckDep(D) == true)
 690          {
 691             /* We want to catch predepends loops with the code below.
 692                Conflicts loops that are Dep OK are ignored */
 693             if (IsFlag(D.TargetPkg(),AddPending) == false ||
 694                 D->Type != pkgCache::Dep::PreDepends)
 695                continue;
 696          }
 697
 698          // This is the loop detection
 699          if (IsFlag(D.TargetPkg(),Added) == true ||
 700              IsFlag(D.TargetPkg(),AddPending) == true)
 701          {
 702             if (IsFlag(D.TargetPkg(),AddPending) == true)
 703                AddLoop(D);
 704             continue;
 705          }
 706
 707          /* Predepends require a special ordering stage, they must have
 708             all dependents installed as well */
 709          DepFunc Old = Primary;
 710          bool Res = false;
 711          if (D->Type == pkgCache::Dep::PreDepends)
 712             Primary = &pkgOrderList::DepUnPackPreD;
 713          Res = VisitProvides(D,true);
 714          Primary = Old;
 715          if (Res == false)
 716             return false;
 717       }
 718    }
 719    return true;
 720 }
 721                                                                         /*}}}*/
 722 // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends  /*{{{*/
 723 // ---------------------------------------------------------------------
 724 /* Critical PreDepends (also configure immediate and essential) strives to
 725    ensure not only that all conflicts+predepends are met but that this
 726    package will be immediately configurable when it is unpacked.
 727    Loops are preprocessed and logged. */
 728 bool pkgOrderList::DepUnPackPreD(DepIterator D)
 729 {
 730    if (D.Reverse() == true)
 731       return DepUnPackCrit(D);
 732
 733    for (; D.end() == false; ++D)
 734    {
 735       if (D.IsCritical() == false)
 736          continue;
 737
 738       /* We wish to check if the dep is okay in the now state of the
 739          target package against the install state of this package. */
 740       if (CheckDep(D) == true)
 741       {
 742          /* We want to catch predepends loops with the code below.
 743             Conflicts loops that are Dep OK are ignored */
 744          if (IsFlag(D.TargetPkg(),AddPending) == false ||
 745              D->Type != pkgCache::Dep::PreDepends)
 746             continue;
 747       }
 748
 749       // This is the loop detection
 750       if (IsFlag(D.TargetPkg(),Added) == true ||
 751           IsFlag(D.TargetPkg(),AddPending) == true)
 752       {
 753          if (IsFlag(D.TargetPkg(),AddPending) == true)
 754             AddLoop(D);
 755          continue;
 756       }
 757
 758       if (VisitProvides(D,true) == false)
 759          return false;
 760    }
 761    return true;
 762 }
 763                                                                         /*}}}*/
 764 // OrderList::DepUnPackPre - Critical Predepends ordering               /*{{{*/
 765 // ---------------------------------------------------------------------
 766 /* Critical PreDepends (also configure immediate and essential) strives to
 767    ensure not only that all conflicts+predepends are met but that this
 768    package will be immediately configurable when it is unpacked.
 769
 770    Loops are preprocessed and logged. All loops will be fatal. */
 771 bool pkgOrderList::DepUnPackPre(DepIterator D)
 772 {
 773    if (D.Reverse() == true)
 774       return true;
 775
 776    for (; D.end() == false; ++D)
 777    {
 778       /* Only consider the PreDepends or Depends. Depends are only
 779          considered at the lowest depth or in the case of immediate
 780          configure */
 781       if (D->Type != pkgCache::Dep::PreDepends)
 782       {
 783          if (D->Type == pkgCache::Dep::Depends)
 784          {
 785             if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false)
 786                continue;
 787          }
 788          else
 789             continue;
 790       }
 791
 792       /* We wish to check if the dep is okay in the now state of the
 793          target package against the install state of this package. */
 794       if (CheckDep(D) == true)
 795       {
 796          /* We want to catch predepends loops with the code below.
 797             Conflicts loops that are Dep OK are ignored */
 798          if (IsFlag(D.TargetPkg(),AddPending) == false)
 799             continue;
 800       }
 801
 802       // This is the loop detection
 803       if (IsFlag(D.TargetPkg(),Added) == true ||
 804           IsFlag(D.TargetPkg(),AddPending) == true)
 805       {
 806          if (IsFlag(D.TargetPkg(),AddPending) == true)
 807             AddLoop(D);
 808          continue;
 809       }
 810
 811       if (VisitProvides(D,true) == false)
 812          return false;
 813    }
 814    return true;
 815 }
 816                                                                         /*}}}*/
 817 // OrderList::DepUnPackDep - Reverse dependency considerations          /*{{{*/
 818 // ---------------------------------------------------------------------
 819 /* Reverse dependencies are considered to determine if unpacking this
 820    package will break any existing dependencies. If so then those
 821    packages are ordered before this one so that they are in the
 822    UnPacked state.
 823
 824    The forwards depends loop is designed to bring the packages dependents
 825    close to the package. This helps reduce deconfigure time.
 826
 827    Loops are irrelevant to this. */
 828 bool pkgOrderList::DepUnPackDep(DepIterator D)
 829 {
 830
 831    for (; D.end() == false; ++D)
 832       if (D.IsCritical() == true)
 833       {
 834          if (D.Reverse() == true)
 835          {
 836             /* Duplication prevention. We consider rev deps only on
 837                the current version, a not installed package
 838                cannot break */
 839             if (D.ParentPkg()->CurrentVer == 0 ||
 840                 D.ParentPkg().CurrentVer() != D.ParentVer())
 841                continue;
 842
 843             // The dep will not break so it is irrelevant.
 844             if (CheckDep(D) == true)
 845                continue;
 846
 847             // Skip over missing files
 848             if (IsMissing(D.ParentPkg()) == true)
 849                continue;
 850
 851             if (VisitNode(D.ParentPkg(), "UnPackDep-Parent") == false)
 852                return false;
 853          }
 854          else
 855          {
 856             if (D->Type == pkgCache::Dep::Depends)
 857                if (VisitProvides(D,false) == false)
 858                   return false;
 859
 860             if (D->Type == pkgCache::Dep::DpkgBreaks)
 861             {
 862                if (CheckDep(D) == true)
 863                  continue;
 864
 865                if (VisitNode(D.TargetPkg(), "UnPackDep-Target") == false)
 866                  return false;
 867             }
 868          }
 869       }
 870    return true;
 871 }
 872                                                                         /*}}}*/
 873 // OrderList::DepConfigure - Configuration ordering                     /*{{{*/
 874 // ---------------------------------------------------------------------
 875 /* Configuration only ordering orders by the Depends: line only. It
 876    orders configuration so that when a package comes to be configured it's
 877    dependents are configured.
 878
 879    Loops are ingored. Depends loop entry points are chaotic. */
 880 bool pkgOrderList::DepConfigure(DepIterator D)
 881 {
 882    // Never consider reverse configuration dependencies.
 883    if (D.Reverse() == true)
 884       return true;
 885
 886    for (; D.end() == false; ++D)
 887       if (D->Type == pkgCache::Dep::Depends)
 888          if (VisitProvides(D,false) == false)
 889             return false;
 890    return true;
 891 }
 892                                                                         /*}}}*/
 893 // OrderList::DepRemove - Removal ordering                              /*{{{*/
 894 // ---------------------------------------------------------------------
 895 /* Checks all given dependencies if they are broken by the remove of a
 896    package and if so fix it by visiting another provider or or-group
 897    member to ensure that the dependee keeps working which is especially
 898    important for Immediate packages like e.g. those depending on an
 899    awk implementation. If the dependency can't be fixed with another
 900    package this means an upgrade of the package will solve the problem. */
 901 bool pkgOrderList::DepRemove(DepIterator Broken)
 902 {
 903    if (Broken.Reverse() == false)
 904       return true;
 905
 906    for (; Broken.end() == false; ++Broken)
 907    {
 908       if (Broken->Type != pkgCache::Dep::Depends &&
 909             Broken->Type != pkgCache::Dep::PreDepends)
 910          continue;
 911
 912       PkgIterator BrokenPkg = Broken.ParentPkg();
 913       // uninstalled packages can't break via a remove
 914       if (BrokenPkg->CurrentVer == 0)
 915          continue;
 916
 917       // if its already added, we can't do anything useful
 918       if (IsFlag(BrokenPkg, AddPending) == true || IsFlag(BrokenPkg, Added) == true)
 919          continue;
 920
 921       // if the dependee is going to be removed, visit it now
 922       if (Cache[BrokenPkg].Delete() == true)
 923          return VisitNode(BrokenPkg, "Remove-Dependee");
 924
 925       // The package stays around, so find out how this is possible
 926       for (DepIterator D = BrokenPkg.CurrentVer().DependsList(); D.end() == false;)
 927       {
 928          // only important or-groups need fixing
 929          if (D->Type != pkgCache::Dep::Depends &&
 930                D->Type != pkgCache::Dep::PreDepends)
 931          {
 932             ++D;
 933             continue;
 934          }
 935
 936          // Start is the beginning of the or-group, D is the first one after or
 937          DepIterator Start = D;
 938          bool foundBroken = false;
 939          for (bool LastOR = true; D.end() == false && LastOR == true; ++D)
 940          {
 941             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 942             if (D == Broken)
 943                foundBroken = true;
 944          }
 945
 946          // this or-group isn't the broken one: keep searching
 947          if (foundBroken == false)
 948             continue;
 949
 950          // iterate over all members of the or-group searching for a ready replacement
 951          bool readyReplacement = false;
 952          for (DepIterator OrMember = Start; OrMember != D && readyReplacement == false; ++OrMember)
 953          {
 954             Version ** Replacements = OrMember.AllTargets();
 955             for (Version **R = Replacements; *R != 0; ++R)
 956             {
 957                VerIterator Ver(Cache,*R);
 958                // only currently installed packages can be a replacement
 959                PkgIterator RPkg = Ver.ParentPkg();
 960                if (RPkg.CurrentVer() != Ver)
 961                   continue;
 962
 963                // packages going to be removed can't be a replacement
 964                if (Cache[RPkg].Delete() == true)
 965                   continue;
 966
 967                readyReplacement = true;
 968                break;
 969             }
 970             delete[] Replacements;
 971          }
 972
 973          // something else is ready to take over, do nothing
 974          if (readyReplacement == true)
 975             continue;
 976
 977          // see if we can visit a replacement
 978          bool visitReplacement = false;
 979          for (DepIterator OrMember = Start; OrMember != D && visitReplacement == false; ++OrMember)
 980          {
 981             Version ** Replacements = OrMember.AllTargets();
 982             for (Version **R = Replacements; *R != 0; ++R)
 983             {
 984                VerIterator Ver(Cache,*R);
 985                // consider only versions we plan to install
 986                PkgIterator RPkg = Ver.ParentPkg();
 987                if (Cache[RPkg].Install() == false || Cache[RPkg].InstallVer != Ver)
 988                   continue;
 989
 990                // loops are not going to help us, so don't create them
 991                if (IsFlag(RPkg, AddPending) == true)
 992                   continue;
 993
 994                if (IsMissing(RPkg) == true)
 995                   continue;
 996
 997                visitReplacement = true;
 998                if (IsFlag(BrokenPkg, Immediate) == false)
 999                {
1000                   if (VisitNode(RPkg, "Remove-Rep") == true)
1001                      break;
1002                }
1003                else
1004                {
1005                   Flag(RPkg, Immediate);
1006                   if (VisitNode(RPkg, "Remove-ImmRep") == true)
1007                      break;
1008                }
1009                visitReplacement = false;
1010             }
1011             delete[] Replacements;
1012          }
1013          if (visitReplacement == true)
1014             continue;
1015
1016          // the broken package in current version can't be fixed, so install new version
1017          if (IsMissing(BrokenPkg) == true)
1018             break;
1019
1020          if (VisitNode(BrokenPkg, "Remove-Upgrade") == false)
1021             return false;
1022       }
1023    }
1024
1025    return true;
1026 }
1027                                                                         /*}}}*/
1028 // OrderList::AddLoop - Add a loop to the loop list                     /*{{{*/
1029 // ---------------------------------------------------------------------
1030 /* We record the loops. This is a relic since loop breaking is done
1031    genericaly as part of the safety routines. */
1032 bool pkgOrderList::AddLoop(DepIterator D)
1033 {
1034    if (LoopCount < 0 || LoopCount >= 20)
1035       return false;
1036
1037    // Skip dups
1038    if (LoopCount != 0)
1039    {
1040       if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() ||
1041           Loops[LoopCount - 1].TargetPkg() == D.ParentPkg())
1042          return true;
1043    }
1044
1045    Loops[LoopCount++] = D;
1046
1047    // Mark the packages as being part of a loop.
1048    //Flag(D.TargetPkg(),Loop);
1049    //Flag(D.ParentPkg(),Loop);
1050    /* This is currently disabled because the Loop flag is being used for
1051       loop management in the package manager. Check the orderlist.h file for more info */
1052    return true;
1053 }
1054                                                                         /*}}}*/
1055 // OrderList::WipeFlags - Unset the given flags from all packages       /*{{{*/
1056 // ---------------------------------------------------------------------
1057 /* */
1058 void pkgOrderList::WipeFlags(unsigned long F)
1059 {
1060    unsigned long Size = Cache.Head().PackageCount;
1061    for (unsigned long I = 0; I != Size; I++)
1062       Flags[I] &= ~F;
1063 }
1064                                                                         /*}}}*/
1065 // OrderList::CheckDep - Check a dependency for truth                   /*{{{*/
1066 // ---------------------------------------------------------------------
1067 /* This performs a complete analysis of the dependency wrt to the
1068    current add list. It returns true if after all events are
1069    performed it is still true. This sort of routine can be approximated
1070    by examining the DepCache, however in convoluted cases of provides
1071    this fails to produce a suitable result. */
1072 bool pkgOrderList::CheckDep(DepIterator D)
1073 {
1074    SPtrArray<Version *> List = D.AllTargets();
1075    bool Hit = false;
1076    for (Version **I = List; *I != 0; I++)
1077    {
1078       VerIterator Ver(Cache,*I);
1079       PkgIterator Pkg = Ver.ParentPkg();
1080
1081       /* The meaning of Added and AddPending is subtle. AddPending is
1082          an indication that the package is looping. Because of the
1083          way ordering works Added means the package will be unpacked
1084          before this one and AddPending means after. It is therefore
1085          correct to ignore AddPending in all cases, but that exposes
1086          reverse-ordering loops which should be ignored. */
1087       if (IsFlag(Pkg,Added) == true ||
1088           (IsFlag(Pkg,AddPending) == true && D.Reverse() == true))
1089       {
1090          if (Cache[Pkg].InstallVer != *I)
1091             continue;
1092       }
1093       else
1094          if ((Version *)Pkg.CurrentVer() != *I ||
1095              Pkg.State() != PkgIterator::NeedsNothing)
1096             continue;
1097
1098       /* Conflicts requires that all versions are not present, depends
1099          just needs one */
1100       if (D.IsNegative() == false)
1101       {
1102          // ignore provides by older versions of this package
1103          if (((D.Reverse() == false && Pkg == D.ParentPkg()) ||
1104               (D.Reverse() == true && Pkg == D.TargetPkg())) &&
1105              Cache[Pkg].InstallVer != *I)
1106             continue;
1107
1108          /* Try to find something that does not have the after flag set
1109             if at all possible */
1110          if (IsFlag(Pkg,After) == true)
1111          {
1112             Hit = true;
1113             continue;
1114          }
1115
1116          return true;
1117       }
1118       else
1119       {
1120          if (IsFlag(Pkg,After) == true)
1121             Flag(D.ParentPkg(),After);
1122
1123          return false;
1124       }
1125    }
1126
1127    // We found a hit, but it had the after flag set
1128    if (Hit == true && D->Type == pkgCache::Dep::PreDepends)
1129    {
1130       Flag(D.ParentPkg(),After);
1131       return true;
1132    }
1133
1134    /* Conflicts requires that all versions are not present, depends
1135       just needs one */
1136    if (D->Type == pkgCache::Dep::Conflicts ||
1137        D->Type == pkgCache::Dep::Obsoletes)
1138       return true;
1139    return false;
1140 }
1141                                                                         /*}}}*/