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