apt-pkg/orderlist.cc

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