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