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