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
 671       /* check if any ImportantDep() (but not Critial) where added
 672        * since we installed the thing
 673        */
 674       bool isNewImportantDep = false;
 675       if(IsImportantDep(Start) && !Start.IsCritical())
 676       {
 677          bool found=false;
 678          VerIterator instVer = Pkg.CurrentVer();
 679          for (DepIterator D = instVer.DependsList(); !D.end(); D++)
 680          {
 681             //FIXME: deal better with or-groups(?)
 682             DepIterator LocalStart = D;
 683
 684             if(IsImportantDep(Dep) && Start.TargetPkg() == D.TargetPkg())
 685                found=true;
 686          }
 687          // this is a new dep if it was not found to be already
 688          // a important dep of the installed pacakge
 689          isNewImportantDep = !found;
 690       }
 691       if(isNewImportantDep)
 692          if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 693             std::clog << "new important dependency: "
 694                       << Start.TargetPkg().Name() << std::endl;
 695
 696       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false && !isNewImportantDep)
 697          continue;
 698
 699       /* If we are in an or group locate the first or that can
 700          succeed. We have already cached this.. */
 701       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 702          Start++;
 703
 704       /* This bit is for processing the possibilty of an install/upgrade
 705          fixing the problem */
 706       SPtrArray<Version *> List = Start.AllTargets();
 707       if ((DepState[Start->ID] & DepCVer) == DepCVer)
 708       {
 709          // Right, find the best version to install..
 710          Version **Cur = List;
 711          PkgIterator P = Start.TargetPkg();
 712          PkgIterator InstPkg(*Cache,0);
 713
 714          // See if there are direct matches (at the start of the list)
 715          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 716          {
 717             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 718             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 719                continue;
 720             InstPkg = Pkg;
 721             break;
 722          }
 723
 724          // Select the highest priority providing package
 725          if (InstPkg.end() == true)
 726          {
 727             pkgPrioSortList(*Cache,Cur);
 728             for (; *Cur != 0; Cur++)
 729             {
 730                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 731                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 732                   continue;
 733                InstPkg = Pkg;
 734                break;
 735             }
 736          }
 737
 738          if (InstPkg.end() == false)
 739          {
 740             if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 741                std::clog << "Installing " << InstPkg.Name()
 742                          << " as dep of " << Pkg.Name()
 743                          << std::endl;
 744             MarkInstall(InstPkg,true,Depth + 1);
 745
 746             // Set the autoflag, after MarkInstall because MarkInstall unsets it
 747             if (P->CurrentVer == 0)
 748                PkgState[InstPkg->ID].Flags |= Flag::Auto;
 749          }
 750
 751          continue;
 752       }
 753
 754       /* For conflicts we just de-install the package and mark as auto,
 755          Conflicts may not have or groups */
 756       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes)
 757       {
 758          for (Version **I = List; *I != 0; I++)
 759          {
 760             VerIterator Ver(*this,*I);
 761             PkgIterator Pkg = Ver.ParentPkg();
 762
 763             MarkDelete(Pkg);
 764             PkgState[Pkg->ID].Flags |= Flag::Auto;
 765          }
 766          continue;
 767       }
 768    }
 769 }
 770                                                                         /*}}}*/
 771 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 772 // ---------------------------------------------------------------------
 773 /* */
 774 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 775 {
 776    RemoveSizes(Pkg);
 777    RemoveStates(Pkg);
 778
 779    StateCache &P = PkgState[Pkg->ID];
 780    if (To == true)
 781       P.iFlags |= ReInstall;
 782    else
 783       P.iFlags &= ~ReInstall;
 784
 785    AddStates(Pkg);
 786    AddSizes(Pkg);
 787 }
 788                                                                         /*}}}*/
 789 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
 790 // ---------------------------------------------------------------------
 791 /* */
 792 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
 793 {
 794    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
 795    StateCache &P = PkgState[Pkg->ID];
 796
 797    RemoveSizes(Pkg);
 798    RemoveStates(Pkg);
 799
 800    if (P.CandidateVer == P.InstallVer)
 801       P.InstallVer = (Version *)TargetVer;
 802    P.CandidateVer = (Version *)TargetVer;
 803    P.Update(Pkg,*this);
 804
 805    AddStates(Pkg);
 806    Update(Pkg);
 807    AddSizes(Pkg);
 808 }
 809                                                                         /*}}}*/
 810 // StateCache::Update - Compute the various static display things       /*{{{*/
 811 // ---------------------------------------------------------------------
 812 /* This is called whenever the Candidate version changes. */
 813 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
 814 {
 815    // Some info
 816    VerIterator Ver = CandidateVerIter(Cache);
 817
 818    // Use a null string or the version string
 819    if (Ver.end() == true)
 820       CandVersion = "";
 821    else
 822       CandVersion = Ver.VerStr();
 823
 824    // Find the current version
 825    CurVersion = "";
 826    if (Pkg->CurrentVer != 0)
 827       CurVersion = Pkg.CurrentVer().VerStr();
 828
 829    // Strip off the epochs for display
 830    CurVersion = StripEpoch(CurVersion);
 831    CandVersion = StripEpoch(CandVersion);
 832
 833    // Figure out if its up or down or equal
 834    Status = Ver.CompareVer(Pkg.CurrentVer());
 835    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
 836      Status = 2;
 837 }
 838                                                                         /*}}}*/
 839 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
 840 // ---------------------------------------------------------------------
 841 /* */
 842 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
 843 {
 844    if (Ver == 0)
 845       return 0;
 846
 847    // Strip any epoch
 848    for (const char *I = Ver; *I != 0; I++)
 849       if (*I == ':')
 850          return I + 1;
 851    return Ver;
 852 }
 853                                                                         /*}}}*/
 854
 855 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
 856 // ---------------------------------------------------------------------
 857 /* The default just returns the highest available version that is not
 858    a source and automatic. */
 859 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
 860 {
 861    /* Not source/not automatic versions cannot be a candidate version
 862       unless they are already installed */
 863    VerIterator Last(*(pkgCache *)this,0);
 864
 865    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
 866    {
 867       if (Pkg.CurrentVer() == I)
 868          return I;
 869
 870       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
 871       {
 872          if ((J.File()->Flags & Flag::NotSource) != 0)
 873             continue;
 874
 875          /* Stash the highest version of a not-automatic source, we use it
 876             if there is nothing better */
 877          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
 878          {
 879             if (Last.end() == true)
 880                Last = I;
 881             continue;
 882          }
 883
 884          return I;
 885       }
 886    }
 887
 888    return Last;
 889 }
 890                                                                         /*}}}*/
 891 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
 892 // ---------------------------------------------------------------------
 893 /* */
 894 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
 895 {
 896    if(Dep.IsCritical())
 897       return true;
 898    else if(Dep->Type == pkgCache::Dep::Recommends)
 899       return  _config->FindB("APT::Install-Recommends", false);
 900    else if(Dep->Type == pkgCache::Dep::Suggests)
 901      return _config->FindB("APT::Install-Suggests", false);
 902
 903    return false;
 904 }
 905                                                                         /*}}}*/