apt-pkg/orderlist.cc

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