apt-pkg/depcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: depcache.cc,v 1.25 2001/05/27 05:36:04 jgg Exp $
   4 /* ######################################################################
   5
   6    Dependency Cache - Caches Dependency information.
   7
   8    ##################################################################### */
   9                                                                         /*}}}*/
  10 // Include Files                                                        /*{{{*/
  11 #ifdef __GNUG__
  12 #pragma implementation "apt-pkg/depcache.h"
  13 #endif
  14 #include <apt-pkg/depcache.h>
  15 #include <apt-pkg/version.h>
  16 #include <apt-pkg/error.h>
  17 #include <apt-pkg/sptr.h>
  18 #include <apt-pkg/algorithms.h>
  19 #include <apt-pkg/configuration.h>
  20 #include <apti18n.h>
  21                                                                         /*}}}*/
  22
  23 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  24 // ---------------------------------------------------------------------
  25 /* */
  26 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  27                 Cache(pCache), PkgState(0), DepState(0)
  28 {
  29    delLocalPolicy = 0;
  30    LocalPolicy = Plcy;
  31    if (LocalPolicy == 0)
  32       delLocalPolicy = LocalPolicy = new Policy;
  33 }
  34                                                                         /*}}}*/
  35 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
  36 // ---------------------------------------------------------------------
  37 /* */
  38 pkgDepCache::~pkgDepCache()
  39 {
  40    delete [] PkgState;
  41    delete [] DepState;
  42    delete delLocalPolicy;
  43 }
  44                                                                         /*}}}*/
  45 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
  46 // ---------------------------------------------------------------------
  47 /* This allocats the extension buffers and initializes them. */
  48 bool pkgDepCache::Init(OpProgress *Prog)
  49 {
  50    delete [] PkgState;
  51    delete [] DepState;
  52    PkgState = new StateCache[Head().PackageCount];
  53    DepState = new unsigned char[Head().DependsCount];
  54    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
  55    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
  56
  57    if (Prog != 0)
  58    {
  59       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
  60                             _("Building dependency tree"));
  61       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
  62    }
  63
  64    /* Set the current state of everything. In this state all of the
  65       packages are kept exactly as is. See AllUpgrade */
  66    int Done = 0;
  67    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
  68    {
  69       if (Prog != 0)
  70          Prog->Progress(Done);
  71
  72       // Find the proper cache slot
  73       StateCache &State = PkgState[I->ID];
  74       State.iFlags = 0;
  75
  76       // Figure out the install version
  77       State.CandidateVer = GetCandidateVer(I);
  78       State.InstallVer = I.CurrentVer();
  79       State.Mode = ModeKeep;
  80
  81       State.Update(I,*this);
  82    }
  83
  84    if (Prog != 0)
  85    {
  86
  87       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
  88                             Head().PackageCount,
  89                             _("Building dependency tree"));
  90       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
  91    }
  92
  93    Update(Prog);
  94
  95    if(Prog != 0)
  96       Prog->Done();
  97
  98    return true;
  99 }
 100                                                                         /*}}}*/
 101
 102 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 103 // ---------------------------------------------------------------------
 104 /* This first checks the dependency against the main target package and
 105    then walks along the package provides list and checks if each provides
 106    will be installed then checks the provides against the dep. Res will be
 107    set to the package which was used to satisfy the dep. */
 108 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 109 {
 110    Res = Dep.TargetPkg();
 111
 112    /* Check simple depends. A depends -should- never self match but
 113       we allow it anyhow because dpkg does. Technically it is a packaging
 114       bug. Conflicts may never self match */
 115    if (Dep.TargetPkg() != Dep.ParentPkg() ||
 116        (Dep->Type != Dep::Conflicts && Dep->Type != Dep::Obsoletes))
 117    {
 118       PkgIterator Pkg = Dep.TargetPkg();
 119       // Check the base package
 120       if (Type == NowVersion && Pkg->CurrentVer != 0)
 121          if (VS().CheckDep(Pkg.CurrentVer().VerStr(),Dep->CompareOp,
 122                                  Dep.TargetVer()) == true)
 123             return true;
 124
 125       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 126          if (VS().CheckDep(PkgState[Pkg->ID].InstVerIter(*this).VerStr(),
 127                                  Dep->CompareOp,Dep.TargetVer()) == true)
 128             return true;
 129
 130       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 131          if (VS().CheckDep(PkgState[Pkg->ID].CandidateVerIter(*this).VerStr(),
 132                                  Dep->CompareOp,Dep.TargetVer()) == true)
 133             return true;
 134    }
 135
 136    if (Dep->Type == Dep::Obsoletes)
 137       return false;
 138
 139    // Check the providing packages
 140    PrvIterator P = Dep.TargetPkg().ProvidesList();
 141    PkgIterator Pkg = Dep.ParentPkg();
 142    for (; P.end() != true; P++)
 143    {
 144       /* Provides may never be applied against the same package if it is
 145          a conflicts. See the comment above. */
 146       if (P.OwnerPkg() == Pkg && Dep->Type == Dep::Conflicts)
 147          continue;
 148
 149       // Check if the provides is a hit
 150       if (Type == NowVersion)
 151       {
 152          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 153             continue;
 154       }
 155
 156       if (Type == InstallVersion)
 157       {
 158          StateCache &State = PkgState[P.OwnerPkg()->ID];
 159          if (State.InstallVer != (Version *)P.OwnerVer())
 160             continue;
 161       }
 162
 163       if (Type == CandidateVersion)
 164       {
 165          StateCache &State = PkgState[P.OwnerPkg()->ID];
 166          if (State.CandidateVer != (Version *)P.OwnerVer())
 167             continue;
 168       }
 169
 170       // Compare the versions.
 171       if (VS().CheckDep(P.ProvideVersion(),Dep->CompareOp,Dep.TargetVer()) == true)
 172       {
 173          Res = P.OwnerPkg();
 174          return true;
 175       }
 176    }
 177
 178    return false;
 179 }
 180                                                                         /*}}}*/
 181 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 182 // ---------------------------------------------------------------------
 183 /* Call with Mult = -1 to preform the inverse opration */
 184 void pkgDepCache::AddSizes(const PkgIterator &Pkg,signed long Mult)
 185 {
 186    StateCache &P = PkgState[Pkg->ID];
 187
 188    if (Pkg->VersionList == 0)
 189       return;
 190
 191    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 192        P.Keep() == true)
 193       return;
 194
 195    // Compute the size data
 196    if (P.NewInstall() == true)
 197    {
 198       iUsrSize += (signed)(Mult*P.InstVerIter(*this)->InstalledSize);
 199       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 200       return;
 201    }
 202
 203    // Upgrading
 204    if (Pkg->CurrentVer != 0 &&
 205        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 206         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 207    {
 208       iUsrSize += (signed)(Mult*((signed)P.InstVerIter(*this)->InstalledSize -
 209                         (signed)Pkg.CurrentVer()->InstalledSize));
 210       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 211       return;
 212    }
 213
 214    // Reinstall
 215    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 216        P.Delete() == false)
 217    {
 218       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 219       return;
 220    }
 221
 222    // Removing
 223    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 224    {
 225       iUsrSize -= (signed)(Mult*Pkg.CurrentVer()->InstalledSize);
 226       return;
 227    }
 228 }
 229                                                                         /*}}}*/
 230 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 231 // ---------------------------------------------------------------------
 232 /* This routine is tricky to use, you must make sure that it is never
 233    called twice for the same package. This means the Remove/Add section
 234    should be as short as possible and not encompass any code that will
 235    calld Remove/Add itself. Remember, dependencies can be circular so
 236    while processing a dep for Pkg it is possible that Add/Remove
 237    will be called on Pkg */
 238 void pkgDepCache::AddStates(const PkgIterator &Pkg,int Add)
 239 {
 240    StateCache &State = PkgState[Pkg->ID];
 241
 242    // The Package is broken
 243    if ((State.DepState & DepInstMin) != DepInstMin)
 244       iBrokenCount += Add;
 245
 246    // Bad state
 247    if (Pkg.State() != PkgIterator::NeedsNothing)
 248       iBadCount += Add;
 249
 250    // Not installed
 251    if (Pkg->CurrentVer == 0)
 252    {
 253       if (State.Mode == ModeDelete &&
 254           (State.iFlags | Purge) == Purge && Pkg.Purge() == false)
 255          iDelCount += Add;
 256
 257       if (State.Mode == ModeInstall)
 258          iInstCount += Add;
 259       return;
 260    }
 261
 262    // Installed, no upgrade
 263    if (State.Status == 0)
 264    {
 265       if (State.Mode == ModeDelete)
 266          iDelCount += Add;
 267       else
 268          if ((State.iFlags & ReInstall) == ReInstall)
 269             iInstCount += Add;
 270
 271       return;
 272    }
 273
 274    // Alll 3 are possible
 275    if (State.Mode == ModeDelete)
 276       iDelCount += Add;
 277    if (State.Mode == ModeKeep)
 278       iKeepCount += Add;
 279    if (State.Mode == ModeInstall)
 280       iInstCount += Add;
 281 }
 282                                                                         /*}}}*/
 283 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 284 // ---------------------------------------------------------------------
 285 /* The or group results are stored in the last item of the or group. This
 286    allows easy detection of the state of a whole or'd group. */
 287 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 288 {
 289    unsigned char Group = 0;
 290
 291    for (DepIterator D = V.DependsList(); D.end() != true; D++)
 292    {
 293       // Build the dependency state.
 294       unsigned char &State = DepState[D->ID];
 295
 296       /* Invert for Conflicts. We have to do this twice to get the
 297          right sense for a conflicts group */
 298       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 299          State = ~State;
 300
 301       // Add to the group if we are within an or..
 302       State &= 0x7;
 303       Group |= State;
 304       State |= Group << 3;
 305       if ((D->CompareOp & Dep::Or) != Dep::Or)
 306          Group = 0;
 307
 308       // Invert for Conflicts
 309       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 310          State = ~State;
 311    }
 312 }
 313                                                                         /*}}}*/
 314 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 315 // ---------------------------------------------------------------------
 316 /* This is used to run over a dependency list and determine the dep
 317    state of the list, filtering it through both a Min check and a Policy
 318    check. The return result will have SetMin/SetPolicy low if a check
 319    fails. It uses the DepState cache for it's computations. */
 320 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 321                                        unsigned char SetMin,
 322                                        unsigned char SetPolicy)
 323 {
 324    unsigned char Dep = 0xFF;
 325
 326    while (D.end() != true)
 327    {
 328       // Compute a single dependency element (glob or)
 329       DepIterator Start = D;
 330       unsigned char State = 0;
 331       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 332       {
 333          State |= DepState[D->ID];
 334          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 335       }
 336
 337       // Minimum deps that must be satisfied to have a working package
 338       if (Start.IsCritical() == true)
 339          if ((State & Check) != Check)
 340             Dep &= ~SetMin;
 341
 342       // Policy deps that must be satisfied to install the package
 343       if (IsImportantDep(Start) == true &&
 344           (State & Check) != Check)
 345          Dep &= ~SetPolicy;
 346    }
 347
 348    return Dep;
 349 }
 350                                                                         /*}}}*/
 351 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 352 // ---------------------------------------------------------------------
 353 /* This is the main dependency computation bit. It computes the 3 main
 354    results for a dependencys, Now, Install and Candidate. Callers must
 355    invert the result if dealing with conflicts. */
 356 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 357 {
 358    unsigned char State = 0;
 359
 360    if (CheckDep(D,NowVersion) == true)
 361       State |= DepNow;
 362    if (CheckDep(D,InstallVersion) == true)
 363       State |= DepInstall;
 364    if (CheckDep(D,CandidateVersion) == true)
 365       State |= DepCVer;
 366
 367    return State;
 368 }
 369                                                                         /*}}}*/
 370 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 371 // ---------------------------------------------------------------------
 372 /* This determines the combined dependency representation of a package
 373    for its two states now and install. This is done by using the pre-generated
 374    dependency information. */
 375 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 376 {
 377    // Empty deps are always true
 378    StateCache &State = PkgState[Pkg->ID];
 379    State.DepState = 0xFF;
 380
 381    // Check the Current state
 382    if (Pkg->CurrentVer != 0)
 383    {
 384       DepIterator D = Pkg.CurrentVer().DependsList();
 385       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 386    }
 387
 388    /* Check the candidate state. We do not compare against the whole as
 389       a candidate state but check the candidate version against the
 390       install states */
 391    if (State.CandidateVer != 0)
 392    {
 393       DepIterator D = State.CandidateVerIter(*this).DependsList();
 394       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 395    }
 396
 397    // Check target state which can only be current or installed
 398    if (State.InstallVer != 0)
 399    {
 400       DepIterator D = State.InstVerIter(*this).DependsList();
 401       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 402    }
 403 }
 404                                                                         /*}}}*/
 405 // DepCache::Update - Figure out all the state information              /*{{{*/
 406 // ---------------------------------------------------------------------
 407 /* This will figure out the state of all the packages and all the
 408    dependencies based on the current policy. */
 409 void pkgDepCache::Update(OpProgress *Prog)
 410 {
 411    iUsrSize = 0;
 412    iDownloadSize = 0;
 413    iDelCount = 0;
 414    iInstCount = 0;
 415    iKeepCount = 0;
 416    iBrokenCount = 0;
 417    iBadCount = 0;
 418
 419    // Perform the depends pass
 420    int Done = 0;
 421    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 422    {
 423       if (Prog != 0 && Done%20 == 0)
 424          Prog->Progress(Done);
 425       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 426       {
 427          unsigned char Group = 0;
 428
 429          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 430          {
 431             // Build the dependency state.
 432             unsigned char &State = DepState[D->ID];
 433             State = DependencyState(D);
 434
 435             // Add to the group if we are within an or..
 436             Group |= State;
 437             State |= Group << 3;
 438             if ((D->CompareOp & Dep::Or) != Dep::Or)
 439                Group = 0;
 440
 441             // Invert for Conflicts
 442             if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 443                State = ~State;
 444          }
 445       }
 446
 447       // Compute the pacakge dependency state and size additions
 448       AddSizes(I);
 449       UpdateVerState(I);
 450       AddStates(I);
 451    }
 452
 453    if (Prog != 0)
 454       Prog->Progress(Done);
 455 }
 456                                                                         /*}}}*/
 457 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 458 // ---------------------------------------------------------------------
 459 /* This is a helper for update that only does the dep portion of the scan.
 460    It is mainly ment to scan reverse dependencies. */
 461 void pkgDepCache::Update(DepIterator D)
 462 {
 463    // Update the reverse deps
 464    for (;D.end() != true; D++)
 465    {
 466       unsigned char &State = DepState[D->ID];
 467       State = DependencyState(D);
 468
 469       // Invert for Conflicts
 470       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 471          State = ~State;
 472
 473       RemoveStates(D.ParentPkg());
 474       BuildGroupOrs(D.ParentVer());
 475       UpdateVerState(D.ParentPkg());
 476       AddStates(D.ParentPkg());
 477    }
 478 }
 479                                                                         /*}}}*/
 480 // DepCache::Update - Update the related deps of a package              /*{{{*/
 481 // ---------------------------------------------------------------------
 482 /* This is called whenever the state of a package changes. It updates
 483    all cached dependencies related to this package. */
 484 void pkgDepCache::Update(PkgIterator const &Pkg)
 485 {
 486    // Recompute the dep of the package
 487    RemoveStates(Pkg);
 488    UpdateVerState(Pkg);
 489    AddStates(Pkg);
 490
 491    // Update the reverse deps
 492    Update(Pkg.RevDependsList());
 493
 494    // Update the provides map for the current ver
 495    if (Pkg->CurrentVer != 0)
 496       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 497            P.end() != true; P++)
 498          Update(P.ParentPkg().RevDependsList());
 499
 500    // Update the provides map for the candidate ver
 501    if (PkgState[Pkg->ID].CandidateVer != 0)
 502       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 503            P.end() != true; P++)
 504          Update(P.ParentPkg().RevDependsList());
 505 }
 506
 507                                                                         /*}}}*/
 508
 509 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 510 // ---------------------------------------------------------------------
 511 /* */
 512 void pkgDepCache::MarkKeep(PkgIterator const &Pkg,bool Soft)
 513 {
 514    // Simplifies other routines.
 515    if (Pkg.end() == true)
 516       return;
 517
 518    /* Reject an attempt to keep a non-source broken installed package, those
 519       must be upgraded */
 520    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 521        Pkg.CurrentVer().Downloadable() == false)
 522       return;
 523
 524    /* We changed the soft state all the time so the UI is a bit nicer
 525       to use */
 526    StateCache &P = PkgState[Pkg->ID];
 527    if (Soft == true)
 528       P.iFlags |= AutoKept;
 529    else
 530       P.iFlags &= ~AutoKept;
 531
 532    // Check that it is not already kept
 533    if (P.Mode == ModeKeep)
 534       return;
 535
 536    // We dont even try to keep virtual packages..
 537    if (Pkg->VersionList == 0)
 538       return;
 539
 540    P.Flags &= ~Flag::Auto;
 541    RemoveSizes(Pkg);
 542    RemoveStates(Pkg);
 543
 544    P.Mode = ModeKeep;
 545    if (Pkg->CurrentVer == 0)
 546       P.InstallVer = 0;
 547    else
 548       P.InstallVer = Pkg.CurrentVer();
 549
 550    AddStates(Pkg);
 551
 552    Update(Pkg);
 553
 554    AddSizes(Pkg);
 555 }
 556                                                                         /*}}}*/
 557 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 558 // ---------------------------------------------------------------------
 559 /* */
 560 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge)
 561 {
 562    // Simplifies other routines.
 563    if (Pkg.end() == true)
 564       return;
 565
 566    // Check that it is not already marked for delete
 567    StateCache &P = PkgState[Pkg->ID];
 568    P.iFlags &= ~(AutoKept | Purge);
 569    if (rPurge == true)
 570       P.iFlags |= Purge;
 571
 572    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 573        (Pkg.Purge() == true || rPurge == false))
 574       return;
 575
 576    // We dont even try to delete virtual packages..
 577    if (Pkg->VersionList == 0)
 578       return;
 579
 580    RemoveSizes(Pkg);
 581    RemoveStates(Pkg);
 582
 583    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 584       P.Mode = ModeKeep;
 585    else
 586       P.Mode = ModeDelete;
 587    P.InstallVer = 0;
 588    P.Flags &= Flag::Auto;
 589
 590    AddStates(Pkg);
 591    Update(Pkg);
 592    AddSizes(Pkg);
 593 }
 594                                                                         /*}}}*/
 595 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 596 // ---------------------------------------------------------------------
 597 /* */
 598 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 599                               unsigned long Depth)
 600 {
 601    if (Depth > 100)
 602       return;
 603
 604    // Simplifies other routines.
 605    if (Pkg.end() == true)
 606       return;
 607
 608    /* Check that it is not already marked for install and that it can be
 609       installed */
 610    StateCache &P = PkgState[Pkg->ID];
 611    P.iFlags &= ~AutoKept;
 612    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
 613        (P.Mode == ModeInstall ||
 614         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 615    {
 616       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 617          MarkKeep(Pkg);
 618       return;
 619    }
 620
 621    // See if there is even any possible instalation candidate
 622    if (P.CandidateVer == 0)
 623       return;
 624    // We dont even try to install virtual packages..
 625    if (Pkg->VersionList == 0)
 626       return;
 627    /* Target the candidate version and remove the autoflag. We reset the
 628       autoflag below if this was called recursively. Otherwise the user
 629       should have the ability to de-auto a package by changing its state */
 630    RemoveSizes(Pkg);
 631    RemoveStates(Pkg);
 632
 633    P.Mode = ModeInstall;
 634    P.InstallVer = P.CandidateVer;
 635    P.Flags &= ~Flag::Auto;
 636    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 637       P.Mode = ModeKeep;
 638
 639    AddStates(Pkg);
 640    Update(Pkg);
 641    AddSizes(Pkg);
 642
 643    if (AutoInst == false)
 644       return;
 645
 646    DepIterator Dep = P.InstVerIter(*this).DependsList();
 647    for (; Dep.end() != true;)
 648    {
 649       // Grok or groups
 650       DepIterator Start = Dep;
 651       bool Result = true;
 652       unsigned Ors = 0;
 653       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
 654       {
 655          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
 656
 657          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
 658             Result = false;
 659       }
 660
 661       // Dep is satisfied okay.
 662       if (Result == false)
 663          continue;
 664
 665       /* Check if this dep should be consider for install. If it is a user
 666          defined important dep and we are installed a new package then
 667          it will be installed. Otherwise we only worry about critical deps */
 668       if (IsImportantDep(Start) == false)
 669          continue;
 670       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false)
 671          continue;
 672
 673       /* If we are in an or group locate the first or that can
 674          succeed. We have already cached this.. */
 675       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 676          Start++;
 677
 678       /* This bit is for processing the possibilty of an install/upgrade
 679          fixing the problem */
 680       SPtrArray<Version *> List = Start.AllTargets();
 681       if ((DepState[Start->ID] & DepCVer) == DepCVer)
 682       {
 683          // Right, find the best version to install..
 684          Version **Cur = List;
 685          PkgIterator P = Start.TargetPkg();
 686          PkgIterator InstPkg(*Cache,0);
 687
 688          // See if there are direct matches (at the start of the list)
 689          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 690          {
 691             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 692             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 693                continue;
 694             InstPkg = Pkg;
 695             break;
 696          }
 697
 698          // Select the highest priority providing package
 699          if (InstPkg.end() == true)
 700          {
 701             pkgPrioSortList(*Cache,Cur);
 702             for (; *Cur != 0; Cur++)
 703             {
 704                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 705                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 706                   continue;
 707                InstPkg = Pkg;
 708                break;
 709             }
 710          }
 711
 712          if (InstPkg.end() == false)
 713          {
 714             if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 715                std::clog << "Installing " << InstPkg.Name()
 716                          << " as dep of " << Pkg.Name()
 717                          << std::endl;
 718             MarkInstall(InstPkg,true,Depth + 1);
 719
 720             // Set the autoflag, after MarkInstall because MarkInstall unsets it
 721             if (P->CurrentVer == 0)
 722                PkgState[InstPkg->ID].Flags |= Flag::Auto;
 723          }
 724
 725          continue;
 726       }
 727
 728       /* For conflicts we just de-install the package and mark as auto,
 729          Conflicts may not have or groups */
 730       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes)
 731       {
 732          for (Version **I = List; *I != 0; I++)
 733          {
 734             VerIterator Ver(*this,*I);
 735             PkgIterator Pkg = Ver.ParentPkg();
 736
 737             MarkDelete(Pkg);
 738             PkgState[Pkg->ID].Flags |= Flag::Auto;
 739          }
 740          continue;
 741       }
 742    }
 743 }
 744                                                                         /*}}}*/
 745 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 746 // ---------------------------------------------------------------------
 747 /* */
 748 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 749 {
 750    RemoveSizes(Pkg);
 751    RemoveStates(Pkg);
 752
 753    StateCache &P = PkgState[Pkg->ID];
 754    if (To == true)
 755       P.iFlags |= ReInstall;
 756    else
 757       P.iFlags &= ~ReInstall;
 758
 759    AddStates(Pkg);
 760    AddSizes(Pkg);
 761 }
 762                                                                         /*}}}*/
 763 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
 764 // ---------------------------------------------------------------------
 765 /* */
 766 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
 767 {
 768    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
 769    StateCache &P = PkgState[Pkg->ID];
 770
 771    RemoveSizes(Pkg);
 772    RemoveStates(Pkg);
 773
 774    if (P.CandidateVer == P.InstallVer)
 775       P.InstallVer = (Version *)TargetVer;
 776    P.CandidateVer = (Version *)TargetVer;
 777    P.Update(Pkg,*this);
 778
 779    AddStates(Pkg);
 780    Update(Pkg);
 781    AddSizes(Pkg);
 782 }
 783                                                                         /*}}}*/
 784 // StateCache::Update - Compute the various static display things       /*{{{*/
 785 // ---------------------------------------------------------------------
 786 /* This is called whenever the Candidate version changes. */
 787 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
 788 {
 789    // Some info
 790    VerIterator Ver = CandidateVerIter(Cache);
 791
 792    // Use a null string or the version string
 793    if (Ver.end() == true)
 794       CandVersion = "";
 795    else
 796       CandVersion = Ver.VerStr();
 797
 798    // Find the current version
 799    CurVersion = "";
 800    if (Pkg->CurrentVer != 0)
 801       CurVersion = Pkg.CurrentVer().VerStr();
 802
 803    // Strip off the epochs for display
 804    CurVersion = StripEpoch(CurVersion);
 805    CandVersion = StripEpoch(CandVersion);
 806
 807    // Figure out if its up or down or equal
 808    Status = Ver.CompareVer(Pkg.CurrentVer());
 809    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
 810      Status = 2;
 811 }
 812                                                                         /*}}}*/
 813 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
 814 // ---------------------------------------------------------------------
 815 /* */
 816 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
 817 {
 818    if (Ver == 0)
 819       return 0;
 820
 821    // Strip any epoch
 822    for (const char *I = Ver; *I != 0; I++)
 823       if (*I == ':')
 824          return I + 1;
 825    return Ver;
 826 }
 827                                                                         /*}}}*/
 828
 829 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
 830 // ---------------------------------------------------------------------
 831 /* The default just returns the highest available version that is not
 832    a source and automatic. */
 833 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
 834 {
 835    /* Not source/not automatic versions cannot be a candidate version
 836       unless they are already installed */
 837    VerIterator Last(*(pkgCache *)this,0);
 838
 839    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
 840    {
 841       if (Pkg.CurrentVer() == I)
 842          return I;
 843
 844       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
 845       {
 846          if ((J.File()->Flags & Flag::NotSource) != 0)
 847             continue;
 848
 849          /* Stash the highest version of a not-automatic source, we use it
 850             if there is nothing better */
 851          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
 852          {
 853             if (Last.end() == true)
 854                Last = I;
 855             continue;
 856          }
 857
 858          return I;
 859       }
 860    }
 861
 862    return Last;
 863 }
 864                                                                         /*}}}*/
 865 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
 866 // ---------------------------------------------------------------------
 867 /* */
 868 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
 869 {
 870    if(Dep.IsCritical())
 871       return true;
 872    else if(Dep->Type == pkgCache::Dep::Recommends)
 873       return  _config->FindB("APT::Install-Recommends", false);
 874    else if(Dep->Type == pkgCache::Dep::Suggests)
 875      return _config->FindB("APT::Install-Suggests", false);
 876
 877    return false;
 878 }
 879                                                                         /*}}}*/