apt-pkg/orderlist.cc

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