apt-pkg/orderlist.cc

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