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