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