apt-pkg/orderlist.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: orderlist.cc,v 1.14 2001/05/07 05:49:43 jgg Exp $
   4 /* ######################################################################
   5
   6    Order List - Represents and Manipulates an ordered list of packages.
   7
   8    A list of packages can be ordered by a number of conflicting criteria
   9    each given a specific priority. Each package also has a set of flags
  10    indicating some useful things about it that are derived in the
  11    course of sorting. The pkgPackageManager class uses this class for
  12    all of it's installation ordering needs.
  13
  14    This is a modified version of Manoj's Routine B. It consists of four
  15    independent ordering algorithms that can be applied at for different
  16    points in the ordering. By appling progressivly fewer ordering
  17    operations it is possible to give each consideration it's own
  18    priority and create an order that satisfies the lowest applicable
  19    consideration.
  20
  21    The rules for unpacking ordering are:
  22     1) Unpacking ignores Depends: on all packages
  23     2) Unpacking requires Conflicts: on -ALL- packages to be satisfied
  24     3) Unpacking requires PreDepends: on this package only to be satisfied
  25     4) Removing requires that no packages depend on the package to be
  26        removed.
  27
  28    And the rule for configuration ordering is:
  29     1) Configuring requires that the Depends: of the package be satisfied
  30        Conflicts+PreDepends are ignored because unpacking says they are
  31        already correct [exageration, it does check but we need not be
  32        concerned]
  33
  34    And some features that are valuable for unpacking ordering.
  35      f1) Unpacking a new package should advoid breaking dependencies of
  36          configured packages
  37      f2) Removal should not require a force, corrolory of f1
  38      f3) Unpacking should order by depends rather than fall back to random
  39          ordering.
  40
  41    Each of the features can be enabled in the sorting routine at an
  42    arbitrary priority to give quite abit of control over the final unpacking
  43    order.
  44
  45    The rules listed above may never be violated and are called Critical.
  46    When a critical rule is violated then a loop condition is recorded
  47    and will have to be delt with in the caller.
  48
  49    The ordering keeps two lists, the main list and the 'After List'. The
  50    purpose of the after list is to allow packages to be delayed. This is done
  51    by setting the after flag on the package. Any package which requires this
  52    package to be ordered before will inherit the after flag and so on. This
  53    is used for CD swap ordering where all packages on a second CD have the
  54    after flag set. This forces them and all their dependents to be ordered
  55    toward the end.
  56
  57    There are complications in this algorithm when presented with cycles.
  58    For all known practical cases it works, all cases where it doesn't work
  59    is fixable by tweaking the package descriptions. However, it should be
  60    possible to impove this further to make some better choices when
  61    presented with cycles.
  62
  63    ##################################################################### */
  64                                                                         /*}}}*/
  65 // Include Files                                                        /*{{{*/
  66 #include <apt-pkg/orderlist.h>
  67 #include <apt-pkg/depcache.h>
  68 #include <apt-pkg/error.h>
  69 #include <apt-pkg/version.h>
  70 #include <apt-pkg/sptr.h>
  71 #include <apt-pkg/configuration.h>
  72
  73 #include <iostream>
  74                                                                         /*}}}*/
  75
  76 using namespace std;
  77
  78 pkgOrderList *pkgOrderList::Me = 0;
  79
  80 // OrderList::pkgOrderList - Constructor                                /*{{{*/
  81 // ---------------------------------------------------------------------
  82 /* */
  83 pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache)
  84 {
  85    FileList = 0;
  86    Primary = 0;
  87    Secondary = 0;
  88    RevDepends = 0;
  89    Remove = 0;
  90    LoopCount = -1;
  91    Debug = _config->FindB("Debug::pkgOrderList",false);
  92
  93    /* Construct the arrays, egcs 1.0.1 bug requires the package count
  94       hack */
  95    unsigned long Size = Cache.Head().PackageCount;
  96    Flags = new unsigned short[Size];
  97    End = List = new Package *[Size];
  98    memset(Flags,0,sizeof(*Flags)*Size);
  99 }
 100                                                                         /*}}}*/
 101 // OrderList::~pkgOrderList - Destructor                                /*{{{*/
 102 // ---------------------------------------------------------------------
 103 /* */
 104 pkgOrderList::~pkgOrderList()
 105 {
 106    delete [] List;
 107    delete [] Flags;
 108 }
 109                                                                         /*}}}*/
 110 // OrderList::IsMissing - Check if a file is missing                    /*{{{*/
 111 // ---------------------------------------------------------------------
 112 /* */
 113 bool pkgOrderList::IsMissing(PkgIterator Pkg)
 114 {
 115    // Skip packages to erase
 116    if (Cache[Pkg].Delete() == true)
 117       return false;
 118
 119    // Skip Packages that need configure only.
 120    if ((Pkg.State() == pkgCache::PkgIterator::NeedsConfigure ||
 121         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)) == 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 bool pkgOrderList::VisitProvides(DepIterator D,bool Critical)
 500 {
 501    SPtrArray<Version *> List = D.AllTargets();
 502    for (Version **I = List; *I != 0; I++)
 503    {
 504       VerIterator Ver(Cache,*I);
 505       PkgIterator Pkg = Ver.ParentPkg();
 506
 507       if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing)
 508          continue;
 509
 510       if (D.IsNegative() == false &&
 511           Cache[Pkg].InstallVer != *I)
 512          continue;
 513
 514       if (D.IsNegative() == true &&
 515           (Version *)Pkg.CurrentVer() != *I)
 516          continue;
 517
 518       // Skip over missing files
 519       if (Critical == false && IsMissing(D.ParentPkg()) == true)
 520          continue;
 521
 522       if (VisitNode(Pkg) == false)
 523          return false;
 524    }
 525    return true;
 526 }
 527                                                                         /*}}}*/
 528 // OrderList::VisitNode - Recursive ordering director                   /*{{{*/
 529 // ---------------------------------------------------------------------
 530 /* This is the core ordering routine. It calls the set dependency
 531    consideration functions which then potentialy call this again. Finite
 532    depth is achived through the colouring mechinism. */
 533 bool pkgOrderList::VisitNode(PkgIterator Pkg)
 534 {
 535    // Looping or irrelevent.
 536    // This should probably trancend not installed packages
 537    if (Pkg.end() == true || IsFlag(Pkg,Added) == true ||
 538        IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false)
 539       return true;
 540
 541    if (Debug == true)
 542    {
 543       for (int j = 0; j != Depth; j++) clog << ' ';
 544       clog << "Visit " << Pkg.FullName() << endl;
 545    }
 546
 547    Depth++;
 548
 549    // Color grey
 550    Flag(Pkg,AddPending);
 551
 552    DepFunc Old = Primary;
 553
 554    // Perform immedate configuration of the package if so flagged.
 555    if (IsFlag(Pkg,Immediate) == true && Primary != &pkgOrderList::DepUnPackPre)
 556       Primary = &pkgOrderList::DepUnPackPreD;
 557
 558    if (IsNow(Pkg) == true)
 559    {
 560       bool Res = true;
 561       if (Cache[Pkg].Delete() == false)
 562       {
 563          // Primary
 564          Res &= Res && VisitDeps(Primary,Pkg);
 565          Res &= Res && VisitRDeps(Primary,Pkg);
 566          Res &= Res && VisitRProvides(Primary,Pkg.CurrentVer());
 567          Res &= Res && VisitRProvides(Primary,Cache[Pkg].InstVerIter(Cache));
 568
 569          // RevDep
 570          Res &= Res && VisitRDeps(RevDepends,Pkg);
 571          Res &= Res && VisitRProvides(RevDepends,Pkg.CurrentVer());
 572          Res &= Res && VisitRProvides(RevDepends,Cache[Pkg].InstVerIter(Cache));
 573
 574          // Secondary
 575          Res &= Res && VisitDeps(Secondary,Pkg);
 576          Res &= Res && VisitRDeps(Secondary,Pkg);
 577          Res &= Res && VisitRProvides(Secondary,Pkg.CurrentVer());
 578          Res &= Res && VisitRProvides(Secondary,Cache[Pkg].InstVerIter(Cache));
 579       }
 580       else
 581       {
 582          // RevDep
 583          Res &= Res && VisitRDeps(Remove,Pkg);
 584          Res &= Res && VisitRProvides(Remove,Pkg.CurrentVer());
 585       }
 586    }
 587
 588    if (IsFlag(Pkg,Added) == false)
 589    {
 590       Flag(Pkg,Added,Added | AddPending);
 591       if (IsFlag(Pkg,After) == true)
 592          *AfterEnd++ = Pkg;
 593       else
 594          *End++ = Pkg;
 595    }
 596
 597    Primary = Old;
 598    Depth--;
 599
 600    if (Debug == true)
 601    {
 602       for (int j = 0; j != Depth; j++) clog << ' ';
 603       clog << "Leave " << Pkg.FullName() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;
 604    }
 605
 606    return true;
 607 }
 608                                                                         /*}}}*/
 609 // OrderList::DepUnPackCrit - Critical UnPacking ordering               /*{{{*/
 610 // ---------------------------------------------------------------------
 611 /* Critical unpacking ordering strives to satisfy Conflicts: and
 612    PreDepends: only. When a prdepends is encountered the Primary
 613    DepFunc is changed to be DepUnPackPreD.
 614
 615    Loops are preprocessed and logged. */
 616 bool pkgOrderList::DepUnPackCrit(DepIterator D)
 617 {
 618    for (; D.end() == false; ++D)
 619    {
 620       if (D.Reverse() == true)
 621       {
 622          /* Reverse depenanices are only interested in conflicts,
 623             predepend breakage is ignored here */
 624          if (D->Type != pkgCache::Dep::Conflicts &&
 625              D->Type != pkgCache::Dep::Obsoletes)
 626             continue;
 627
 628          // Duplication elimination, consider only the current version
 629          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 630             continue;
 631
 632          /* For reverse dependencies we wish to check if the
 633             dependency is satisifed in the install state. The
 634             target package (caller) is going to be in the installed
 635             state. */
 636          if (CheckDep(D) == true)
 637             continue;
 638
 639          if (VisitNode(D.ParentPkg()) == false)
 640             return false;
 641       }
 642       else
 643       {
 644          /* Forward critical dependencies MUST be correct before the
 645             package can be unpacked. */
 646          if (D.IsNegative() == false &&
 647              D->Type != pkgCache::Dep::PreDepends)
 648             continue;
 649
 650          /* We wish to check if the dep is okay in the now state of the
 651             target package against the install state of this package. */
 652          if (CheckDep(D) == true)
 653          {
 654             /* We want to catch predepends loops with the code below.
 655                Conflicts loops that are Dep OK are ignored */
 656             if (IsFlag(D.TargetPkg(),AddPending) == false ||
 657                 D->Type != pkgCache::Dep::PreDepends)
 658                continue;
 659          }
 660
 661          // This is the loop detection
 662          if (IsFlag(D.TargetPkg(),Added) == true ||
 663              IsFlag(D.TargetPkg(),AddPending) == true)
 664          {
 665             if (IsFlag(D.TargetPkg(),AddPending) == true)
 666                AddLoop(D);
 667             continue;
 668          }
 669
 670          /* Predepends require a special ordering stage, they must have
 671             all dependents installed as well */
 672          DepFunc Old = Primary;
 673          bool Res = false;
 674          if (D->Type == pkgCache::Dep::PreDepends)
 675             Primary = &pkgOrderList::DepUnPackPreD;
 676          Res = VisitProvides(D,true);
 677          Primary = Old;
 678          if (Res == false)
 679             return false;
 680       }
 681    }
 682    return true;
 683 }
 684                                                                         /*}}}*/
 685 // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends  /*{{{*/
 686 // ---------------------------------------------------------------------
 687 /* Critical PreDepends (also configure immediate and essential) strives to
 688    ensure not only that all conflicts+predepends are met but that this
 689    package will be immediately configurable when it is unpacked.
 690    Loops are preprocessed and logged. */
 691 bool pkgOrderList::DepUnPackPreD(DepIterator D)
 692 {
 693    if (D.Reverse() == true)
 694       return DepUnPackCrit(D);
 695
 696    for (; D.end() == false; ++D)
 697    {
 698       if (D.IsCritical() == false)
 699          continue;
 700
 701       /* We wish to check if the dep is okay in the now state of the
 702          target package against the install state of this package. */
 703       if (CheckDep(D) == true)
 704       {
 705          /* We want to catch predepends loops with the code below.
 706             Conflicts loops that are Dep OK are ignored */
 707          if (IsFlag(D.TargetPkg(),AddPending) == false ||
 708              D->Type != pkgCache::Dep::PreDepends)
 709             continue;
 710       }
 711
 712       // This is the loop detection
 713       if (IsFlag(D.TargetPkg(),Added) == true ||
 714           IsFlag(D.TargetPkg(),AddPending) == true)
 715       {
 716          if (IsFlag(D.TargetPkg(),AddPending) == true)
 717             AddLoop(D);
 718          continue;
 719       }
 720
 721       if (VisitProvides(D,true) == false)
 722          return false;
 723    }
 724    return true;
 725 }
 726                                                                         /*}}}*/
 727 // OrderList::DepUnPackPre - Critical Predepends ordering               /*{{{*/
 728 // ---------------------------------------------------------------------
 729 /* Critical PreDepends (also configure immediate and essential) strives to
 730    ensure not only that all conflicts+predepends are met but that this
 731    package will be immediately configurable when it is unpacked.
 732
 733    Loops are preprocessed and logged. All loops will be fatal. */
 734 bool pkgOrderList::DepUnPackPre(DepIterator D)
 735 {
 736    if (D.Reverse() == true)
 737       return true;
 738
 739    for (; D.end() == false; ++D)
 740    {
 741       /* Only consider the PreDepends or Depends. Depends are only
 742          considered at the lowest depth or in the case of immediate
 743          configure */
 744       if (D->Type != pkgCache::Dep::PreDepends)
 745       {
 746          if (D->Type == pkgCache::Dep::Depends)
 747          {
 748             if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false)
 749                continue;
 750          }
 751          else
 752             continue;
 753       }
 754
 755       /* We wish to check if the dep is okay in the now state of the
 756          target package against the install state of this package. */
 757       if (CheckDep(D) == true)
 758       {
 759          /* We want to catch predepends loops with the code below.
 760             Conflicts loops that are Dep OK are ignored */
 761          if (IsFlag(D.TargetPkg(),AddPending) == false)
 762             continue;
 763       }
 764
 765       // This is the loop detection
 766       if (IsFlag(D.TargetPkg(),Added) == true ||
 767           IsFlag(D.TargetPkg(),AddPending) == true)
 768       {
 769          if (IsFlag(D.TargetPkg(),AddPending) == true)
 770             AddLoop(D);
 771          continue;
 772       }
 773
 774       if (VisitProvides(D,true) == false)
 775          return false;
 776    }
 777    return true;
 778 }
 779                                                                         /*}}}*/
 780 // OrderList::DepUnPackDep - Reverse dependency considerations          /*{{{*/
 781 // ---------------------------------------------------------------------
 782 /* Reverse dependencies are considered to determine if unpacking this
 783    package will break any existing dependencies. If so then those
 784    packages are ordered before this one so that they are in the
 785    UnPacked state.
 786
 787    The forwards depends loop is designed to bring the packages dependents
 788    close to the package. This helps reduce deconfigure time.
 789
 790    Loops are irrelevent to this. */
 791 bool pkgOrderList::DepUnPackDep(DepIterator D)
 792 {
 793
 794    for (; D.end() == false; ++D)
 795       if (D.IsCritical() == true)
 796       {
 797          if (D.Reverse() == true)
 798          {
 799             /* Duplication prevention. We consider rev deps only on
 800                the current version, a not installed package
 801                cannot break */
 802             if (D.ParentPkg()->CurrentVer == 0 ||
 803                 D.ParentPkg().CurrentVer() != D.ParentVer())
 804                continue;
 805
 806             // The dep will not break so it is irrelevent.
 807             if (CheckDep(D) == true)
 808                continue;
 809
 810             // Skip over missing files
 811             if (IsMissing(D.ParentPkg()) == true)
 812                continue;
 813
 814             if (VisitNode(D.ParentPkg()) == false)
 815                return false;
 816          }
 817          else
 818          {
 819             if (D->Type == pkgCache::Dep::Depends)
 820                if (VisitProvides(D,false) == false)
 821                   return false;
 822
 823             if (D->Type == pkgCache::Dep::DpkgBreaks)
 824             {
 825                if (CheckDep(D) == true)
 826                  continue;
 827
 828                if (VisitNode(D.TargetPkg()) == false)
 829                  return false;
 830             }
 831          }
 832       }
 833    return true;
 834 }
 835                                                                         /*}}}*/
 836 // OrderList::DepConfigure - Configuration ordering                     /*{{{*/
 837 // ---------------------------------------------------------------------
 838 /* Configuration only ordering orders by the Depends: line only. It
 839    orders configuration so that when a package comes to be configured it's
 840    dependents are configured.
 841
 842    Loops are ingored. Depends loop entry points are chaotic. */
 843 bool pkgOrderList::DepConfigure(DepIterator D)
 844 {
 845    // Never consider reverse configuration dependencies.
 846    if (D.Reverse() == true)
 847       return true;
 848
 849    for (; D.end() == false; ++D)
 850       if (D->Type == pkgCache::Dep::Depends)
 851          if (VisitProvides(D,false) == false)
 852             return false;
 853    return true;
 854 }
 855                                                                         /*}}}*/
 856 // OrderList::DepRemove - Removal ordering                              /*{{{*/
 857 // ---------------------------------------------------------------------
 858 /* Removal visits all reverse depends. It considers if the dependency
 859    of the Now state version to see if it is okay with removing this
 860    package. This check should always fail, but is provided for symetery
 861    with the other critical handlers.
 862
 863    Loops are preprocessed and logged. Removal loops can also be
 864    detected in the critical handler. They are characterized by an
 865    old version of A depending on B but the new version of A conflicting
 866    with B, thus either A or B must break to install. */
 867 bool pkgOrderList::DepRemove(DepIterator D)
 868 {
 869    if (D.Reverse() == false)
 870       return true;
 871    for (; D.end() == false; ++D)
 872       if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 873       {
 874          // Duplication elimination, consider the current version only
 875          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 876             continue;
 877
 878          /* We wish to see if the dep on the parent package is okay
 879             in the removed (install) state of the target pkg. */
 880          bool tryFixDeps = false;
 881          if (CheckDep(D) == true)
 882          {
 883             // We want to catch loops with the code below.
 884             if (IsFlag(D.ParentPkg(),AddPending) == false)
 885                continue;
 886          }
 887          else
 888             tryFixDeps = true;
 889
 890          // This is the loop detection
 891          if (IsFlag(D.ParentPkg(),Added) == true ||
 892              IsFlag(D.ParentPkg(),AddPending) == true)
 893          {
 894             if (IsFlag(D.ParentPkg(),AddPending) == true)
 895                AddLoop(D);
 896             continue;
 897          }
 898
 899          if (tryFixDeps == true)
 900          {
 901             for (pkgCache::DepIterator F = D.ParentPkg().CurrentVer().DependsList();
 902                  F.end() == false; ++F)
 903             {
 904                if (F->Type != pkgCache::Dep::Depends && F->Type != pkgCache::Dep::PreDepends)
 905                   continue;
 906                // Check the Providers
 907                if (F.TargetPkg()->ProvidesList != 0)
 908                {
 909                   pkgCache::PrvIterator Prov = F.TargetPkg().ProvidesList();
 910                   for (; Prov.end() == false; ++Prov)
 911                   {
 912                      pkgCache::PkgIterator const P = Prov.OwnerPkg();
 913                      if (IsFlag(P, InList) == true &&
 914                          IsFlag(P, AddPending) == true &&
 915                          IsFlag(P, Added) == false &&
 916                          Cache[P].InstallVer == 0)
 917                         break;
 918                   }
 919                   if (Prov.end() == false)
 920                      for (pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList();
 921                           Prv.end() == false; ++Prv)
 922                      {
 923                         pkgCache::PkgIterator const P = Prv.OwnerPkg();
 924                         if (IsFlag(P, InList) == true &&
 925                             IsFlag(P, AddPending) == false &&
 926                             Cache[P].InstallVer != 0 &&
 927                             VisitNode(P) == true)
 928                         {
 929                            Flag(P, Immediate);
 930                            tryFixDeps = false;
 931                            break;
 932                         }
 933                      }
 934                   if (tryFixDeps == false)
 935                      break;
 936                }
 937
 938                // Check for Or groups
 939                if ((F->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or)
 940                   continue;
 941                // Lets see if the package is part of the Or group
 942                pkgCache::DepIterator S = F;
 943                for (; S.end() == false; ++S)
 944                {
 945                   if (S.TargetPkg() == D.TargetPkg())
 946                      break;
 947                   if ((S->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or ||
 948                       CheckDep(S)) // Or group is satisfied by another package
 949                      for (;S.end() == false; ++S);
 950                }
 951                if (S.end() == true)
 952                   continue;
 953                // skip to the end of the or group
 954                for (;S.end() == false && (S->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; ++S);
 955                ++S;
 956                // The soon to be removed is part of the Or group
 957                // start again in the or group and find something which will serve as replacement
 958                for (; F.end() == false && F != S; ++F)
 959                {
 960                   if (IsFlag(F.TargetPkg(), InList) == true &&
 961                       IsFlag(F.TargetPkg(), AddPending) == false &&
 962                       Cache[F.TargetPkg()].InstallVer != 0 &&
 963                       VisitNode(F.TargetPkg()) == true)
 964                   {
 965                      Flag(F.TargetPkg(), Immediate);
 966                      tryFixDeps = false;
 967                      break;
 968                   }
 969                   else if (F.TargetPkg()->ProvidesList != 0)
 970                   {
 971                      pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList();
 972                      for (; Prv.end() == false; ++Prv)
 973                      {
 974                         if (IsFlag(Prv.OwnerPkg(), InList) == true &&
 975                             IsFlag(Prv.OwnerPkg(), AddPending) == false &&
 976                             Cache[Prv.OwnerPkg()].InstallVer != 0 &&
 977                             VisitNode(Prv.OwnerPkg()) == true)
 978                         {
 979                            Flag(Prv.OwnerPkg(), Immediate);
 980                            tryFixDeps = false;
 981                            break;
 982                         }
 983                      }
 984                      if (Prv.end() == false)
 985                         break;
 986                   }
 987                }
 988                if (tryFixDeps == false)
 989                   break;
 990             }
 991          }
 992
 993          // Skip over missing files
 994          if (IsMissing(D.ParentPkg()) == true)
 995             continue;
 996
 997          if (VisitNode(D.ParentPkg()) == false)
 998             return false;
 999       }
1000
1001    return true;
1002 }
1003                                                                         /*}}}*/
1004 // OrderList::AddLoop - Add a loop to the loop list                     /*{{{*/
1005 // ---------------------------------------------------------------------
1006 /* We record the loops. This is a relic since loop breaking is done
1007    genericaly as part of the safety routines. */
1008 bool pkgOrderList::AddLoop(DepIterator D)
1009 {
1010    if (LoopCount < 0 || LoopCount >= 20)
1011       return false;
1012
1013    // Skip dups
1014    if (LoopCount != 0)
1015    {
1016       if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() ||
1017           Loops[LoopCount - 1].TargetPkg() == D.ParentPkg())
1018          return true;
1019    }
1020
1021    Loops[LoopCount++] = D;
1022
1023    // Mark the packages as being part of a loop.
1024    Flag(D.TargetPkg(),Loop);
1025    Flag(D.ParentPkg(),Loop);
1026    return true;
1027 }
1028                                                                         /*}}}*/
1029 // OrderList::WipeFlags - Unset the given flags from all packages       /*{{{*/
1030 // ---------------------------------------------------------------------
1031 /* */
1032 void pkgOrderList::WipeFlags(unsigned long F)
1033 {
1034    unsigned long Size = Cache.Head().PackageCount;
1035    for (unsigned long I = 0; I != Size; I++)
1036       Flags[I] &= ~F;
1037 }
1038                                                                         /*}}}*/
1039 // OrderList::CheckDep - Check a dependency for truth                   /*{{{*/
1040 // ---------------------------------------------------------------------
1041 /* This performs a complete analysis of the dependency wrt to the
1042    current add list. It returns true if after all events are
1043    performed it is still true. This sort of routine can be approximated
1044    by examining the DepCache, however in convoluted cases of provides
1045    this fails to produce a suitable result. */
1046 bool pkgOrderList::CheckDep(DepIterator D)
1047 {
1048    SPtrArray<Version *> List = D.AllTargets();
1049    bool Hit = false;
1050    for (Version **I = List; *I != 0; I++)
1051    {
1052       VerIterator Ver(Cache,*I);
1053       PkgIterator Pkg = Ver.ParentPkg();
1054
1055       /* The meaning of Added and AddPending is subtle. AddPending is
1056          an indication that the package is looping. Because of the
1057          way ordering works Added means the package will be unpacked
1058          before this one and AddPending means after. It is therefore
1059          correct to ignore AddPending in all cases, but that exposes
1060          reverse-ordering loops which should be ignored. */
1061       if (IsFlag(Pkg,Added) == true ||
1062           (IsFlag(Pkg,AddPending) == true && D.Reverse() == true))
1063       {
1064          if (Cache[Pkg].InstallVer != *I)
1065             continue;
1066       }
1067       else
1068          if ((Version *)Pkg.CurrentVer() != *I ||
1069              Pkg.State() != PkgIterator::NeedsNothing)
1070             continue;
1071
1072       /* Conflicts requires that all versions are not present, depends
1073          just needs one */
1074       if (D.IsNegative() == false)
1075       {
1076          // ignore provides by older versions of this package
1077          if (((D.Reverse() == false && Pkg == D.ParentPkg()) ||
1078               (D.Reverse() == true && Pkg == D.TargetPkg())) &&
1079              Cache[Pkg].InstallVer != *I)
1080             continue;
1081
1082          /* Try to find something that does not have the after flag set
1083             if at all possible */
1084          if (IsFlag(Pkg,After) == true)
1085          {
1086             Hit = true;
1087             continue;
1088          }
1089
1090          return true;
1091       }
1092       else
1093       {
1094          if (IsFlag(Pkg,After) == true)
1095             Flag(D.ParentPkg(),After);
1096
1097          return false;
1098       }
1099    }
1100
1101    // We found a hit, but it had the after flag set
1102    if (Hit == true && D->Type == pkgCache::Dep::PreDepends)
1103    {
1104       Flag(D.ParentPkg(),After);
1105       return true;
1106    }
1107
1108    /* Conflicts requires that all versions are not present, depends
1109       just needs one */
1110    if (D->Type == pkgCache::Dep::Conflicts ||
1111        D->Type == pkgCache::Dep::Obsoletes)
1112       return true;
1113    return false;
1114 }
1115                                                                         /*}}}*/