apt-pkg/orderlist.cc

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