apt-pkg/orderlist.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: orderlist.cc,v 1.2 1998/07/12 23:58:28 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    if (Pkg.end() == true || IsFlag(Pkg,Added) == true ||
 406        IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false)
 407       return true;
 408
 409 /* for (int j = 0; j != Depth; j++) cout << ' ';
 410  cout << "Visit " << Pkg.Name() << endl;*/
 411    Depth++;
 412
 413    // Color grey
 414    Flag(Pkg,AddPending);
 415
 416    DepFunc Old = Primary;
 417
 418    // Perform immedate configuration of the package if so flagged.
 419    if (IsFlag(Pkg,Immediate) == true && Primary != &DepUnPackPre)
 420       Primary = &DepUnPackPreD;
 421
 422    bool Res = true;
 423    if (Cache[Pkg].Delete() == false)
 424    {
 425       // Primary
 426       Res &= Res && VisitDeps(Primary,Pkg);
 427       Res &= Res && VisitRDeps(Primary,Pkg);
 428       Res &= Res && VisitRProvides(Primary,Pkg.CurrentVer());
 429       Res &= Res && VisitRProvides(Primary,Cache[Pkg].InstVerIter(Cache));
 430
 431       // RevDep
 432       Res &= Res && VisitRDeps(RevDepends,Pkg);
 433       Res &= Res && VisitRProvides(RevDepends,Pkg.CurrentVer());
 434       Res &= Res && VisitRProvides(RevDepends,Cache[Pkg].InstVerIter(Cache));
 435
 436       // Secondary
 437       Res &= Res && VisitDeps(Secondary,Pkg);
 438       Res &= Res && VisitRDeps(Secondary,Pkg);
 439       Res &= Res && VisitRProvides(Secondary,Pkg.CurrentVer());
 440       Res &= Res && VisitRProvides(Secondary,Cache[Pkg].InstVerIter(Cache));
 441    }
 442    else
 443    {
 444       // RevDep
 445       Res &= Res && VisitRDeps(Remove,Pkg);
 446       Res &= Res && VisitRProvides(Remove,Pkg.CurrentVer());
 447    }
 448
 449    if (IsFlag(Pkg,Added) == false)
 450    {
 451       Flag(Pkg,Added,Added | AddPending);
 452       *End = Pkg;
 453       End++;
 454    }
 455
 456    Primary = Old;
 457    Depth--;
 458
 459 /* for (int j = 0; j != Depth; j++) cout << ' ';
 460    cout << "Leave " << Pkg.Name() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;*/
 461
 462    return true;
 463 }
 464                                                                         /*}}}*/
 465
 466 // OrderList::DepUnPackCrit - Critical UnPacking ordering               /*{{{*/
 467 // ---------------------------------------------------------------------
 468 /* Critical unpacking ordering strives to satisfy Conflicts: and
 469    PreDepends: only. When a prdepends is encountered the Primary
 470    DepFunc is changed to be DepUnPackPreD.
 471
 472    Loops are preprocessed and logged. */
 473 bool pkgOrderList::DepUnPackCrit(DepIterator D)
 474 {
 475    for (; D.end() == false; D++)
 476    {
 477       if (D.Reverse() == true)
 478       {
 479          /* Reverse depenanices are only interested in conflicts,
 480             predepend breakage is ignored here */
 481          if (D->Type != pkgCache::Dep::Conflicts)
 482             continue;
 483
 484          // Duplication elimination, consider only the current version
 485          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 486             continue;
 487
 488          /* For reverse dependencies we wish to check if the
 489             dependency is satisifed in the install state. The
 490             target package (caller) is going to be in the installed
 491             state. */
 492          if (CheckDep(D) == true)
 493             continue;
 494
 495          if (VisitNode(D.ParentPkg()) == false)
 496             return false;
 497       }
 498       else
 499       {
 500          /* Forward critical dependencies MUST be correct before the
 501             package can be unpacked. */
 502          if (D->Type != pkgCache::Dep::Conflicts && D->Type != pkgCache::Dep::PreDepends)
 503             continue;
 504
 505          /* We wish to check if the dep is okay in the now state of the
 506             target package against the install state of this package. */
 507          if (CheckDep(D) == true)
 508          {
 509             /* We want to catch predepends loops with the code below.
 510                Conflicts loops that are Dep OK are ignored */
 511             if (IsFlag(D.TargetPkg(),AddPending) == false ||
 512                 D->Type != pkgCache::Dep::PreDepends)
 513                continue;
 514          }
 515
 516          // This is the loop detection
 517          if (IsFlag(D.TargetPkg(),Added) == true ||
 518              IsFlag(D.TargetPkg(),AddPending) == true)
 519          {
 520             if (IsFlag(D.TargetPkg(),AddPending) == true)
 521                AddLoop(D);
 522             continue;
 523          }
 524
 525          /* Predepends require a special ordering stage, they must have
 526             all dependents installed as well */
 527          DepFunc Old = Primary;
 528          bool Res = false;
 529          if (D->Type == pkgCache::Dep::PreDepends)
 530             Primary = &DepUnPackPreD;
 531          Res = VisitProvides(D);
 532          Primary = Old;
 533          if (Res == false)
 534             return false;
 535       }
 536    }
 537    return true;
 538 }
 539                                                                         /*}}}*/
 540 // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends  /*{{{*/
 541 // ---------------------------------------------------------------------
 542 /* Critical PreDepends (also configure immediate and essential) strives to
 543    ensure not only that all conflicts+predepends are met but that this
 544    package will be immediately configurable when it is unpacked.
 545
 546    Loops are preprocessed and logged. */
 547 bool pkgOrderList::DepUnPackPreD(DepIterator D)
 548 {
 549    if (D.Reverse() == true)
 550       return DepUnPackCrit(D);
 551
 552    for (; D.end() == false; D++)
 553    {
 554       if (D.IsCritical() == false)
 555          continue;
 556
 557       /* We wish to check if the dep is okay in the now state of the
 558          target package against the install state of this package. */
 559       if (CheckDep(D) == true)
 560       {
 561          /* We want to catch predepends loops with the code below.
 562             Conflicts loops that are Dep OK are ignored */
 563          if (IsFlag(D.TargetPkg(),AddPending) == false ||
 564              D->Type != pkgCache::Dep::PreDepends)
 565             continue;
 566       }
 567
 568       // This is the loop detection
 569       if (IsFlag(D.TargetPkg(),Added) == true ||
 570           IsFlag(D.TargetPkg(),AddPending) == true)
 571       {
 572          if (IsFlag(D.TargetPkg(),AddPending) == true)
 573             AddLoop(D);
 574          continue;
 575       }
 576
 577       if (VisitProvides(D) == false)
 578          return false;
 579    }
 580    return true;
 581 }
 582                                                                         /*}}}*/
 583 // OrderList::DepUnPackPre - Critical Predepends ordering               /*{{{*/
 584 // ---------------------------------------------------------------------
 585 /* Critical PreDepends (also configure immediate and essential) strives to
 586    ensure not only that all conflicts+predepends are met but that this
 587    package will be immediately configurable when it is unpacked.
 588
 589    Loops are preprocessed and logged. All loops will be fatal. */
 590 bool pkgOrderList::DepUnPackPre(DepIterator D)
 591 {
 592    if (D.Reverse() == true)
 593       return true;
 594
 595    for (; D.end() == false; D++)
 596    {
 597       /* Only consider the PreDepends or Depends. Depends are only
 598          considered at the lowest depth or in the case of immediate
 599          configure */
 600       if (D->Type != pkgCache::Dep::PreDepends)
 601       {
 602          if (D->Type == pkgCache::Dep::Depends)
 603          {
 604             if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false)
 605                continue;
 606          }
 607          else
 608             continue;
 609       }
 610
 611       /* We wish to check if the dep is okay in the now state of the
 612          target package against the install state of this package. */
 613       if (CheckDep(D) == true)
 614       {
 615          /* We want to catch predepends loops with the code below.
 616             Conflicts loops that are Dep OK are ignored */
 617          if (IsFlag(D.TargetPkg(),AddPending) == false)
 618             continue;
 619       }
 620
 621       // This is the loop detection
 622       if (IsFlag(D.TargetPkg(),Added) == true ||
 623           IsFlag(D.TargetPkg(),AddPending) == true)
 624       {
 625          if (IsFlag(D.TargetPkg(),AddPending) == true)
 626             AddLoop(D);
 627          continue;
 628       }
 629
 630       if (VisitProvides(D) == false)
 631          return false;
 632    }
 633    return true;
 634 }
 635                                                                         /*}}}*/
 636 // OrderList::DepUnPackDep - Reverse dependency considerations          /*{{{*/
 637 // ---------------------------------------------------------------------
 638 /* Reverse dependencies are considered to determine if unpacking this
 639    package will break any existing dependencies. If so then those
 640    packages are ordered before this one so that they are in the
 641    UnPacked state.
 642
 643    The forwards depends loop is designed to bring the packages dependents
 644    close to the package. This helps reduce deconfigure time.
 645
 646    Loops are irrelevent to this. */
 647 bool pkgOrderList::DepUnPackDep(DepIterator D)
 648 {
 649
 650    for (; D.end() == false; D++)
 651       if (D.IsCritical() == true)
 652       {
 653          if (D.Reverse() == true)
 654          {
 655             /* Duplication prevention. We consider rev deps only on
 656                the current version, a not installed package
 657                cannot break */
 658             if (D.ParentPkg()->CurrentVer == 0 ||
 659                 D.ParentPkg().CurrentVer() != D.ParentVer())
 660                continue;
 661
 662             // The dep will not break so it is irrelevent.
 663             if (CheckDep(D) == true)
 664                continue;
 665
 666             if (VisitNode(D.ParentPkg()) == false)
 667                return false;
 668          }
 669          else
 670             if (D->Type == pkgCache::Dep::Depends)
 671                if (VisitProvides(D) == false)
 672                   return false;
 673       }
 674    return true;
 675 }
 676                                                                         /*}}}*/
 677 // OrderList::DepConfigure - Configuration ordering                     /*{{{*/
 678 // ---------------------------------------------------------------------
 679 /* Configuration only ordering orders by the Depends: line only. It
 680    orders configuration so that when a package comes to be configured it's
 681    dependents are configured.
 682
 683    Loops are ingored. Depends loop entry points are chaotic. */
 684 bool pkgOrderList::DepConfigure(DepIterator D)
 685 {
 686    // Never consider reverse configuration dependencies.
 687    if (D.Reverse() == true)
 688       return true;
 689
 690    for (; D.end() == false; D++)
 691       if (D->Type == pkgCache::Dep::Depends)
 692          if (VisitProvides(D) == false)
 693             return false;
 694    return true;
 695 }
 696                                                                         /*}}}*/
 697 // OrderList::DepRemove - Removal ordering                              /*{{{*/
 698 // ---------------------------------------------------------------------
 699 /* Removal visits all reverse depends. It considers if the dependency
 700    of the Now state version to see if it is okay with removing this
 701    package. This check should always fail, but is provided for symetery
 702    with the other critical handlers.
 703
 704    Loops are preprocessed and logged. Removal loops can also be
 705    detected in the critical handler. They are characterized by an
 706    old version of A depending on B but the new version of A conflicting
 707    with B, thus either A or B must break to install. */
 708 bool pkgOrderList::DepRemove(DepIterator D)
 709 {
 710    if (D.Reverse() == false)
 711       return true;
 712    for (; D.end() == false; D++)
 713       if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 714       {
 715          // Duplication elimination, consider the current version only
 716          if (D.ParentPkg().CurrentVer() != D.ParentVer())
 717             continue;
 718
 719          /* We wish to see if the dep on the parent package is okay
 720             in the removed (install) state of the target pkg. */
 721          if (CheckDep(D) == true)
 722          {
 723             // We want to catch loops with the code below.
 724             if (IsFlag(D.ParentPkg(),AddPending) == false)
 725                continue;
 726          }
 727
 728          // This is the loop detection
 729          if (IsFlag(D.ParentPkg(),Added) == true ||
 730              IsFlag(D.ParentPkg(),AddPending) == true)
 731          {
 732             if (IsFlag(D.ParentPkg(),AddPending) == true)
 733                AddLoop(D);
 734             continue;
 735          }
 736
 737          if (VisitNode(D.ParentPkg()) == false)
 738             return false;
 739       }
 740
 741    return true;
 742 }
 743                                                                         /*}}}*/
 744
 745 // OrderList::AddLoop - Add a loop to the loop list                     /*{{{*/
 746 // ---------------------------------------------------------------------
 747 /* We record the loops. This is a relic since loop breaking is done
 748    genericaly as part of the safety routines. */
 749 bool pkgOrderList::AddLoop(DepIterator D)
 750 {
 751    if (LoopCount < 0 || LoopCount >= 20)
 752       return false;
 753
 754    // Skip dups
 755    if (LoopCount != 0)
 756    {
 757       if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() ||
 758           Loops[LoopCount - 1].TargetPkg() == D.ParentPkg())
 759          return true;
 760    }
 761
 762    Loops[LoopCount++] = D;
 763
 764    // Mark the packages as being part of a loop.
 765    Flag(D.TargetPkg(),Loop);
 766    Flag(D.ParentPkg(),Loop);
 767    return true;
 768 }
 769                                                                         /*}}}*/
 770 // OrderList::WipeFlags - Unset the given flags from all packages       /*{{{*/
 771 // ---------------------------------------------------------------------
 772 /* */
 773 void pkgOrderList::WipeFlags(unsigned long F)
 774 {
 775    unsigned long Size = Cache.HeaderP->PackageCount;
 776    for (unsigned long I = 0; I != Size; I++)
 777       Flags[I] &= ~F;
 778 }
 779                                                                         /*}}}*/
 780 // OrderList::CheckDep - Check a dependency for truth                   /*{{{*/
 781 // ---------------------------------------------------------------------
 782 /* This performs a complete analysis of the dependency wrt to the
 783    current add list. It returns true if after all events are
 784    performed it is still true. This sort of routine can be approximated
 785    by examining the DepCache, however in convoluted cases of provides
 786    this fails to produce a suitable result. */
 787 bool pkgOrderList::CheckDep(DepIterator D)
 788 {
 789    Version **List = D.AllTargets();
 790    for (Version **I = List; *I != 0; I++)
 791    {
 792       VerIterator Ver(Cache,*I);
 793       PkgIterator Pkg = Ver.ParentPkg();
 794
 795       /* The meaning of Added and AddPending is subtle. AddPending is
 796          an indication that the package is looping. Because of the
 797          way ordering works Added means the package will be unpacked
 798          before this one and AddPending means after. It is therefore
 799          correct to ignore AddPending in all cases, but that exposes
 800          reverse-ordering loops which should be ignore. */
 801       if (IsFlag(Pkg,Added) == true ||
 802           (IsFlag(Pkg,AddPending) == true && D.Reverse() == true))
 803       {
 804          if (Cache[Pkg].InstallVer != *I)
 805             continue;
 806       }
 807       else
 808          if ((Version *)Pkg.CurrentVer() != *I ||
 809              Pkg.State() != PkgIterator::NeedsNothing)
 810             continue;
 811
 812       delete [] List;
 813
 814       /* Conflicts requires that all versions are not present, depends
 815          just needs one */
 816       if (D->Type != pkgCache::Dep::Conflicts)
 817          return true;
 818       else
 819          return false;
 820    }
 821    delete [] List;
 822
 823    /* Conflicts requires that all versions are not present, depends
 824       just needs one */
 825    if (D->Type == pkgCache::Dep::Conflicts)
 826       return true;
 827    return false;
 828 }
 829                                                                         /*}}}*/