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