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