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
  20 #include <apt-pkg/fileutl.h>
  21 #include <apt-pkg/configuration.h>
  22 #include <apt-pkg/pkgsystem.h>
  23 #include <apt-pkg/tagfile.h>
  24
  25 #include <iostream>
  26 #include <sstream>
  27 #include <apti18n.h>
  28
  29 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :
  30   cache(cache), released(false)
  31 {
  32   ++cache.group_level;
  33 }
  34
  35 void pkgDepCache::ActionGroup::release()
  36 {
  37   if(!released)
  38     {
  39       if(cache.group_level == 0)
  40         std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
  41       else
  42         {
  43           --cache.group_level;
  44
  45           if(cache.group_level == 0)
  46             cache.MarkAndSweep();
  47         }
  48
  49       released = false;
  50     }
  51 }
  52
  53 pkgDepCache::ActionGroup::~ActionGroup()
  54 {
  55   release();
  56 }
  57
  58 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  59 // ---------------------------------------------------------------------
  60 /* */
  61 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  62   group_level(0), Cache(pCache), PkgState(0), DepState(0)
  63 {
  64    delLocalPolicy = 0;
  65    LocalPolicy = Plcy;
  66    if (LocalPolicy == 0)
  67       delLocalPolicy = LocalPolicy = new Policy;
  68 }
  69                                                                         /*}}}*/
  70 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
  71 // ---------------------------------------------------------------------
  72 /* */
  73 pkgDepCache::~pkgDepCache()
  74 {
  75    delete [] PkgState;
  76    delete [] DepState;
  77    delete delLocalPolicy;
  78 }
  79                                                                         /*}}}*/
  80 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
  81 // ---------------------------------------------------------------------
  82 /* This allocats the extension buffers and initializes them. */
  83 bool pkgDepCache::Init(OpProgress *Prog)
  84 {
  85    // Suppress mark updates during this operation (just in case) and
  86    // run a mark operation when Init terminates.
  87    ActionGroup actions(*this);
  88
  89    delete [] PkgState;
  90    delete [] DepState;
  91    PkgState = new StateCache[Head().PackageCount];
  92    DepState = new unsigned char[Head().DependsCount];
  93    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
  94    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
  95
  96    if (Prog != 0)
  97    {
  98       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
  99                             _("Building dependency tree"));
 100       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 101    }
 102
 103    /* Set the current state of everything. In this state all of the
 104       packages are kept exactly as is. See AllUpgrade */
 105    int Done = 0;
 106    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 107    {
 108       if (Prog != 0)
 109          Prog->Progress(Done);
 110
 111       // Find the proper cache slot
 112       StateCache &State = PkgState[I->ID];
 113       State.iFlags = 0;
 114
 115       // Figure out the install version
 116       State.CandidateVer = GetCandidateVer(I);
 117       State.InstallVer = I.CurrentVer();
 118       State.Mode = ModeKeep;
 119
 120       State.Update(I,*this);
 121    }
 122
 123    if (Prog != 0)
 124    {
 125
 126       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 127                             Head().PackageCount,
 128                             _("Building dependency tree"));
 129       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 130    }
 131
 132    Update(Prog);
 133
 134    if(Prog != 0)
 135       Prog->Done();
 136
 137    return true;
 138 }
 139                                                                         /*}}}*/
 140
 141 bool pkgDepCache::readStateFile(OpProgress *Prog)
 142 {
 143    FileFd state_file;
 144    string state = _config->FindDir("Dir::State") + "pkgstates";
 145    if(FileExists(state)) {
 146       state_file.Open(state, FileFd::ReadOnly);
 147       int file_size = state_file.Size();
 148       if(Prog != NULL)
 149          Prog->OverallProgress(0, file_size, 1,
 150                                _("Reading state information"));
 151
 152       pkgTagFile tagfile(&state_file);
 153       pkgTagSection section;
 154       int amt=0;
 155       while(tagfile.Step(section)) {
 156          string pkgname = section.FindS("Package");
 157          pkgCache::PkgIterator pkg=Cache->FindPkg(pkgname);
 158          // Silently ignore unknown packages and packages with no actual
 159          // version.
 160          if(!pkg.end() && !pkg.VersionList().end()) {
 161             short reason = section.FindI("Auto-Installed", 0);
 162             if(reason > 0)
 163                PkgState[pkg->ID].Flags  |= Flag::Auto;
 164             if(_config->FindB("Debug::pkgAutoRemove",false))
 165                std::cout << "Auto-Installed : " << pkgname << std::endl;
 166             amt+=section.size();
 167             if(Prog != NULL)
 168                Prog->OverallProgress(amt, file_size, 1,
 169                                      _("Reading state information"));
 170          }
 171          if(Prog != NULL)
 172             Prog->OverallProgress(file_size, file_size, 1,
 173                                   _("Reading state information"));
 174       }
 175    }
 176
 177    return true;
 178 }
 179
 180 bool pkgDepCache::writeStateFile(OpProgress *prog)
 181 {
 182    FileFd StateFile;
 183    string state = _config->FindDir("Dir::State") + "pkgstates";
 184
 185    if(_config->FindB("Debug::pkgAutoRemove",false))
 186       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 187
 188    if(!StateFile.Open(state, FileFd::WriteEmpty))
 189       return _error->Error(_("Failed to write StateFile %s"),
 190                            state.c_str());
 191
 192    std::ostringstream ostr;
 193    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end();pkg++) {
 194
 195       if(PkgState[pkg->ID].Flags & Flag::Auto) {
 196          if(_config->FindB("Debug::pkgAutoRemove",false))
 197             std::clog << "AutoInstall: " << pkg.Name() << std::endl;
 198          ostr.str(string(""));
 199          ostr << "Package: " << pkg.Name()
 200               << "\nAuto-Installed: 1\n\n";
 201          StateFile.Write(ostr.str().c_str(), ostr.str().size());
 202       }
 203    }
 204    return true;
 205 }
 206
 207 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 208 // ---------------------------------------------------------------------
 209 /* This first checks the dependency against the main target package and
 210    then walks along the package provides list and checks if each provides
 211    will be installed then checks the provides against the dep. Res will be
 212    set to the package which was used to satisfy the dep. */
 213 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 214 {
 215    Res = Dep.TargetPkg();
 216
 217    /* Check simple depends. A depends -should- never self match but
 218       we allow it anyhow because dpkg does. Technically it is a packaging
 219       bug. Conflicts may never self match */
 220    if (Dep.TargetPkg() != Dep.ParentPkg() ||
 221        (Dep->Type != Dep::Conflicts && Dep->Type != Dep::Obsoletes))
 222    {
 223       PkgIterator Pkg = Dep.TargetPkg();
 224       // Check the base package
 225       if (Type == NowVersion && Pkg->CurrentVer != 0)
 226          if (VS().CheckDep(Pkg.CurrentVer().VerStr(),Dep->CompareOp,
 227                                  Dep.TargetVer()) == true)
 228             return true;
 229
 230       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 231          if (VS().CheckDep(PkgState[Pkg->ID].InstVerIter(*this).VerStr(),
 232                                  Dep->CompareOp,Dep.TargetVer()) == true)
 233             return true;
 234
 235       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 236          if (VS().CheckDep(PkgState[Pkg->ID].CandidateVerIter(*this).VerStr(),
 237                                  Dep->CompareOp,Dep.TargetVer()) == true)
 238             return true;
 239    }
 240
 241    if (Dep->Type == Dep::Obsoletes)
 242       return false;
 243
 244    // Check the providing packages
 245    PrvIterator P = Dep.TargetPkg().ProvidesList();
 246    PkgIterator Pkg = Dep.ParentPkg();
 247    for (; P.end() != true; P++)
 248    {
 249       /* Provides may never be applied against the same package if it is
 250          a conflicts. See the comment above. */
 251       if (P.OwnerPkg() == Pkg && Dep->Type == Dep::Conflicts)
 252          continue;
 253
 254       // Check if the provides is a hit
 255       if (Type == NowVersion)
 256       {
 257          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 258             continue;
 259       }
 260
 261       if (Type == InstallVersion)
 262       {
 263          StateCache &State = PkgState[P.OwnerPkg()->ID];
 264          if (State.InstallVer != (Version *)P.OwnerVer())
 265             continue;
 266       }
 267
 268       if (Type == CandidateVersion)
 269       {
 270          StateCache &State = PkgState[P.OwnerPkg()->ID];
 271          if (State.CandidateVer != (Version *)P.OwnerVer())
 272             continue;
 273       }
 274
 275       // Compare the versions.
 276       if (VS().CheckDep(P.ProvideVersion(),Dep->CompareOp,Dep.TargetVer()) == true)
 277       {
 278          Res = P.OwnerPkg();
 279          return true;
 280       }
 281    }
 282
 283    return false;
 284 }
 285                                                                         /*}}}*/
 286 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 287 // ---------------------------------------------------------------------
 288 /* Call with Mult = -1 to preform the inverse opration */
 289 void pkgDepCache::AddSizes(const PkgIterator &Pkg,signed long Mult)
 290 {
 291    StateCache &P = PkgState[Pkg->ID];
 292
 293    if (Pkg->VersionList == 0)
 294       return;
 295
 296    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 297        P.Keep() == true)
 298       return;
 299
 300    // Compute the size data
 301    if (P.NewInstall() == true)
 302    {
 303       iUsrSize += (signed)(Mult*P.InstVerIter(*this)->InstalledSize);
 304       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 305       return;
 306    }
 307
 308    // Upgrading
 309    if (Pkg->CurrentVer != 0 &&
 310        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 311         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 312    {
 313       iUsrSize += (signed)(Mult*((signed)P.InstVerIter(*this)->InstalledSize -
 314                         (signed)Pkg.CurrentVer()->InstalledSize));
 315       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 316       return;
 317    }
 318
 319    // Reinstall
 320    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 321        P.Delete() == false)
 322    {
 323       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 324       return;
 325    }
 326
 327    // Removing
 328    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 329    {
 330       iUsrSize -= (signed)(Mult*Pkg.CurrentVer()->InstalledSize);
 331       return;
 332    }
 333 }
 334                                                                         /*}}}*/
 335 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 336 // ---------------------------------------------------------------------
 337 /* This routine is tricky to use, you must make sure that it is never
 338    called twice for the same package. This means the Remove/Add section
 339    should be as short as possible and not encompass any code that will
 340    calld Remove/Add itself. Remember, dependencies can be circular so
 341    while processing a dep for Pkg it is possible that Add/Remove
 342    will be called on Pkg */
 343 void pkgDepCache::AddStates(const PkgIterator &Pkg,int Add)
 344 {
 345    StateCache &State = PkgState[Pkg->ID];
 346
 347    // The Package is broken
 348    if ((State.DepState & DepInstMin) != DepInstMin)
 349       iBrokenCount += Add;
 350
 351    // Bad state
 352    if (Pkg.State() != PkgIterator::NeedsNothing)
 353       iBadCount += Add;
 354
 355    // Not installed
 356    if (Pkg->CurrentVer == 0)
 357    {
 358       if (State.Mode == ModeDelete &&
 359           (State.iFlags | Purge) == Purge && Pkg.Purge() == false)
 360          iDelCount += Add;
 361
 362       if (State.Mode == ModeInstall)
 363          iInstCount += Add;
 364       return;
 365    }
 366
 367    // Installed, no upgrade
 368    if (State.Status == 0)
 369    {
 370       if (State.Mode == ModeDelete)
 371          iDelCount += Add;
 372       else
 373          if ((State.iFlags & ReInstall) == ReInstall)
 374             iInstCount += Add;
 375
 376       return;
 377    }
 378
 379    // Alll 3 are possible
 380    if (State.Mode == ModeDelete)
 381       iDelCount += Add;
 382    if (State.Mode == ModeKeep)
 383       iKeepCount += Add;
 384    if (State.Mode == ModeInstall)
 385       iInstCount += Add;
 386 }
 387                                                                         /*}}}*/
 388 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 389 // ---------------------------------------------------------------------
 390 /* The or group results are stored in the last item of the or group. This
 391    allows easy detection of the state of a whole or'd group. */
 392 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 393 {
 394    unsigned char Group = 0;
 395
 396    for (DepIterator D = V.DependsList(); D.end() != true; D++)
 397    {
 398       // Build the dependency state.
 399       unsigned char &State = DepState[D->ID];
 400
 401       /* Invert for Conflicts. We have to do this twice to get the
 402          right sense for a conflicts group */
 403       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 404          State = ~State;
 405
 406       // Add to the group if we are within an or..
 407       State &= 0x7;
 408       Group |= State;
 409       State |= Group << 3;
 410       if ((D->CompareOp & Dep::Or) != Dep::Or)
 411          Group = 0;
 412
 413       // Invert for Conflicts
 414       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 415          State = ~State;
 416    }
 417 }
 418                                                                         /*}}}*/
 419 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 420 // ---------------------------------------------------------------------
 421 /* This is used to run over a dependency list and determine the dep
 422    state of the list, filtering it through both a Min check and a Policy
 423    check. The return result will have SetMin/SetPolicy low if a check
 424    fails. It uses the DepState cache for it's computations. */
 425 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 426                                        unsigned char SetMin,
 427                                        unsigned char SetPolicy)
 428 {
 429    unsigned char Dep = 0xFF;
 430
 431    while (D.end() != true)
 432    {
 433       // Compute a single dependency element (glob or)
 434       DepIterator Start = D;
 435       unsigned char State = 0;
 436       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 437       {
 438          State |= DepState[D->ID];
 439          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 440       }
 441
 442       // Minimum deps that must be satisfied to have a working package
 443       if (Start.IsCritical() == true)
 444          if ((State & Check) != Check)
 445             Dep &= ~SetMin;
 446
 447       // Policy deps that must be satisfied to install the package
 448       if (IsImportantDep(Start) == true &&
 449           (State & Check) != Check)
 450          Dep &= ~SetPolicy;
 451    }
 452
 453    return Dep;
 454 }
 455                                                                         /*}}}*/
 456 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 457 // ---------------------------------------------------------------------
 458 /* This is the main dependency computation bit. It computes the 3 main
 459    results for a dependencys, Now, Install and Candidate. Callers must
 460    invert the result if dealing with conflicts. */
 461 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 462 {
 463    unsigned char State = 0;
 464
 465    if (CheckDep(D,NowVersion) == true)
 466       State |= DepNow;
 467    if (CheckDep(D,InstallVersion) == true)
 468       State |= DepInstall;
 469    if (CheckDep(D,CandidateVersion) == true)
 470       State |= DepCVer;
 471
 472    return State;
 473 }
 474                                                                         /*}}}*/
 475 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 476 // ---------------------------------------------------------------------
 477 /* This determines the combined dependency representation of a package
 478    for its two states now and install. This is done by using the pre-generated
 479    dependency information. */
 480 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 481 {
 482    // Empty deps are always true
 483    StateCache &State = PkgState[Pkg->ID];
 484    State.DepState = 0xFF;
 485
 486    // Check the Current state
 487    if (Pkg->CurrentVer != 0)
 488    {
 489       DepIterator D = Pkg.CurrentVer().DependsList();
 490       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 491    }
 492
 493    /* Check the candidate state. We do not compare against the whole as
 494       a candidate state but check the candidate version against the
 495       install states */
 496    if (State.CandidateVer != 0)
 497    {
 498       DepIterator D = State.CandidateVerIter(*this).DependsList();
 499       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 500    }
 501
 502    // Check target state which can only be current or installed
 503    if (State.InstallVer != 0)
 504    {
 505       DepIterator D = State.InstVerIter(*this).DependsList();
 506       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 507    }
 508 }
 509                                                                         /*}}}*/
 510 // DepCache::Update - Figure out all the state information              /*{{{*/
 511 // ---------------------------------------------------------------------
 512 /* This will figure out the state of all the packages and all the
 513    dependencies based on the current policy. */
 514 void pkgDepCache::Update(OpProgress *Prog)
 515 {
 516    iUsrSize = 0;
 517    iDownloadSize = 0;
 518    iDelCount = 0;
 519    iInstCount = 0;
 520    iKeepCount = 0;
 521    iBrokenCount = 0;
 522    iBadCount = 0;
 523
 524    // Perform the depends pass
 525    int Done = 0;
 526    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 527    {
 528       if (Prog != 0 && Done%20 == 0)
 529          Prog->Progress(Done);
 530       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 531       {
 532          unsigned char Group = 0;
 533
 534          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 535          {
 536             // Build the dependency state.
 537             unsigned char &State = DepState[D->ID];
 538             State = DependencyState(D);
 539
 540             // Add to the group if we are within an or..
 541             Group |= State;
 542             State |= Group << 3;
 543             if ((D->CompareOp & Dep::Or) != Dep::Or)
 544                Group = 0;
 545
 546             // Invert for Conflicts
 547             if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 548                State = ~State;
 549          }
 550       }
 551
 552       // Compute the pacakge dependency state and size additions
 553       AddSizes(I);
 554       UpdateVerState(I);
 555       AddStates(I);
 556    }
 557
 558    if (Prog != 0)
 559       Prog->Progress(Done);
 560
 561    readStateFile(Prog);
 562 }
 563                                                                         /*}}}*/
 564 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 565 // ---------------------------------------------------------------------
 566 /* This is a helper for update that only does the dep portion of the scan.
 567    It is mainly meant to scan reverse dependencies. */
 568 void pkgDepCache::Update(DepIterator D)
 569 {
 570    // Update the reverse deps
 571    for (;D.end() != true; D++)
 572    {
 573       unsigned char &State = DepState[D->ID];
 574       State = DependencyState(D);
 575
 576       // Invert for Conflicts
 577       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 578          State = ~State;
 579
 580       RemoveStates(D.ParentPkg());
 581       BuildGroupOrs(D.ParentVer());
 582       UpdateVerState(D.ParentPkg());
 583       AddStates(D.ParentPkg());
 584    }
 585 }
 586                                                                         /*}}}*/
 587 // DepCache::Update - Update the related deps of a package              /*{{{*/
 588 // ---------------------------------------------------------------------
 589 /* This is called whenever the state of a package changes. It updates
 590    all cached dependencies related to this package. */
 591 void pkgDepCache::Update(PkgIterator const &Pkg)
 592 {
 593    // Recompute the dep of the package
 594    RemoveStates(Pkg);
 595    UpdateVerState(Pkg);
 596    AddStates(Pkg);
 597
 598    // Update the reverse deps
 599    Update(Pkg.RevDependsList());
 600
 601    // Update the provides map for the current ver
 602    if (Pkg->CurrentVer != 0)
 603       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 604            P.end() != true; P++)
 605          Update(P.ParentPkg().RevDependsList());
 606
 607    // Update the provides map for the candidate ver
 608    if (PkgState[Pkg->ID].CandidateVer != 0)
 609       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 610            P.end() != true; P++)
 611          Update(P.ParentPkg().RevDependsList());
 612 }
 613
 614                                                                         /*}}}*/
 615
 616 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 617 // ---------------------------------------------------------------------
 618 /* */
 619 void pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser)
 620 {
 621    // Simplifies other routines.
 622    if (Pkg.end() == true)
 623       return;
 624
 625    /* Reject an attempt to keep a non-source broken installed package, those
 626       must be upgraded */
 627    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 628        Pkg.CurrentVer().Downloadable() == false)
 629       return;
 630
 631    /** \todo Can this be moved later in the method? */
 632    ActionGroup group(*this);
 633
 634    /* We changed the soft state all the time so the UI is a bit nicer
 635       to use */
 636    StateCache &P = PkgState[Pkg->ID];
 637    if (Soft == true)
 638       P.iFlags |= AutoKept;
 639    else
 640       P.iFlags &= ~AutoKept;
 641
 642    // Check that it is not already kept
 643    if (P.Mode == ModeKeep)
 644       return;
 645
 646    // We dont even try to keep virtual packages..
 647    if (Pkg->VersionList == 0)
 648       return;
 649
 650    if(FromUser && !P.Marked)
 651      P.Flags &= ~Flag::Auto;
 652    RemoveSizes(Pkg);
 653    RemoveStates(Pkg);
 654
 655    P.Mode = ModeKeep;
 656    if (Pkg->CurrentVer == 0)
 657       P.InstallVer = 0;
 658    else
 659       P.InstallVer = Pkg.CurrentVer();
 660
 661    AddStates(Pkg);
 662
 663    Update(Pkg);
 664
 665    AddSizes(Pkg);
 666 }
 667                                                                         /*}}}*/
 668 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 669 // ---------------------------------------------------------------------
 670 /* */
 671 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge)
 672 {
 673    // Simplifies other routines.
 674    if (Pkg.end() == true)
 675       return;
 676
 677    ActionGroup group(*this);
 678
 679    // Check that it is not already marked for delete
 680    StateCache &P = PkgState[Pkg->ID];
 681    P.iFlags &= ~(AutoKept | Purge);
 682    if (rPurge == true)
 683       P.iFlags |= Purge;
 684
 685    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 686        (Pkg.Purge() == true || rPurge == false))
 687       return;
 688
 689    // We dont even try to delete virtual packages..
 690    if (Pkg->VersionList == 0)
 691       return;
 692
 693    RemoveSizes(Pkg);
 694    RemoveStates(Pkg);
 695
 696    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 697       P.Mode = ModeKeep;
 698    else
 699       P.Mode = ModeDelete;
 700    P.InstallVer = 0;
 701
 702    AddStates(Pkg);
 703    Update(Pkg);
 704    AddSizes(Pkg);
 705 }
 706                                                                         /*}}}*/
 707 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 708 // ---------------------------------------------------------------------
 709 /* */
 710 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 711                               unsigned long Depth, bool FromUser)
 712 {
 713    if (Depth > 100)
 714       return;
 715
 716    // Simplifies other routines.
 717    if (Pkg.end() == true)
 718       return;
 719
 720    ActionGroup group(*this);
 721
 722    /* Check that it is not already marked for install and that it can be
 723       installed */
 724    StateCache &P = PkgState[Pkg->ID];
 725    P.iFlags &= ~AutoKept;
 726    if (P.InstBroken() == false && (P.Mode == ModeInstall ||
 727         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 728    {
 729       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 730          MarkKeep(Pkg, false, FromUser);
 731       return;
 732    }
 733
 734    // See if there is even any possible instalation candidate
 735    if (P.CandidateVer == 0)
 736       return;
 737
 738    // We dont even try to install virtual packages..
 739    if (Pkg->VersionList == 0)
 740       return;
 741
 742    /* Target the candidate version and remove the autoflag. We reset the
 743       autoflag below if this was called recursively. Otherwise the user
 744       should have the ability to de-auto a package by changing its state */
 745    RemoveSizes(Pkg);
 746    RemoveStates(Pkg);
 747
 748    P.Mode = ModeInstall;
 749    P.InstallVer = P.CandidateVer;
 750
 751    if(FromUser)
 752      {
 753        // Set it to manual if it's a new install or cancelling the
 754        // removal of a garbage package.
 755        if(P.Status == 2 || (!Pkg.CurrentVer().end() && !P.Marked))
 756          P.Flags &= ~Flag::Auto;
 757      }
 758    else
 759      {
 760        // Set it to auto if this is a new install.
 761        if(P.Status == 2)
 762          P.Flags |= Flag::Auto;
 763      }
 764    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 765       P.Mode = ModeKeep;
 766
 767    AddStates(Pkg);
 768    Update(Pkg);
 769    AddSizes(Pkg);
 770
 771    if (AutoInst == false)
 772       return;
 773
 774    DepIterator Dep = P.InstVerIter(*this).DependsList();
 775    for (; Dep.end() != true;)
 776    {
 777       // Grok or groups
 778       DepIterator Start = Dep;
 779       bool Result = true;
 780       unsigned Ors = 0;
 781       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
 782       {
 783          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
 784
 785          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
 786             Result = false;
 787       }
 788
 789       // Dep is satisfied okay.
 790       if (Result == false)
 791          continue;
 792
 793       /* Check if this dep should be consider for install. If it is a user
 794          defined important dep and we are installed a new package then
 795          it will be installed. Otherwise we only worry about critical deps */
 796       if (IsImportantDep(Start) == false)
 797          continue;
 798       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false)
 799          continue;
 800
 801       /* If we are in an or group locate the first or that can
 802          succeed. We have already cached this.. */
 803       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 804          Start++;
 805
 806       /* This bit is for processing the possibilty of an install/upgrade
 807          fixing the problem */
 808       SPtrArray<Version *> List = Start.AllTargets();
 809       if ((DepState[Start->ID] & DepCVer) == DepCVer)
 810       {
 811          // Right, find the best version to install..
 812          Version **Cur = List;
 813          PkgIterator P = Start.TargetPkg();
 814          PkgIterator InstPkg(*Cache,0);
 815
 816          // See if there are direct matches (at the start of the list)
 817          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 818          {
 819             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 820             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 821                continue;
 822             InstPkg = Pkg;
 823             break;
 824          }
 825
 826          // Select the highest priority providing package
 827          if (InstPkg.end() == true)
 828          {
 829             pkgPrioSortList(*Cache,Cur);
 830             for (; *Cur != 0; Cur++)
 831             {
 832                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 833                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 834                   continue;
 835                InstPkg = Pkg;
 836                break;
 837             }
 838          }
 839
 840          if (InstPkg.end() == false)
 841            MarkInstall(InstPkg, true, Depth + 1, false);
 842
 843          continue;
 844       }
 845
 846       /* For conflicts we just de-install the package and mark as auto,
 847          Conflicts may not have or groups */
 848       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes)
 849       {
 850          for (Version **I = List; *I != 0; I++)
 851          {
 852             VerIterator Ver(*this,*I);
 853             PkgIterator Pkg = Ver.ParentPkg();
 854
 855             MarkDelete(Pkg);
 856          }
 857          continue;
 858       }
 859    }
 860 }
 861                                                                         /*}}}*/
 862 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 863 // ---------------------------------------------------------------------
 864 /* */
 865 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 866 {
 867    ActionGroup group(*this);
 868
 869    RemoveSizes(Pkg);
 870    RemoveStates(Pkg);
 871
 872    StateCache &P = PkgState[Pkg->ID];
 873    if (To == true)
 874       P.iFlags |= ReInstall;
 875    else
 876       P.iFlags &= ~ReInstall;
 877
 878    AddStates(Pkg);
 879    AddSizes(Pkg);
 880 }
 881                                                                         /*}}}*/
 882 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
 883 // ---------------------------------------------------------------------
 884 /* */
 885 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
 886 {
 887    ActionGroup group(*this);
 888
 889    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
 890    StateCache &P = PkgState[Pkg->ID];
 891
 892    RemoveSizes(Pkg);
 893    RemoveStates(Pkg);
 894
 895    if (P.CandidateVer == P.InstallVer)
 896       P.InstallVer = (Version *)TargetVer;
 897    P.CandidateVer = (Version *)TargetVer;
 898    P.Update(Pkg,*this);
 899
 900    AddStates(Pkg);
 901    Update(Pkg);
 902    AddSizes(Pkg);
 903 }
 904
 905 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
 906 {
 907   StateCache &state = PkgState[Pkg->ID];
 908
 909   ActionGroup group(*this);
 910
 911   if(Auto)
 912     state.Flags |= Flag::Auto;
 913   else
 914     state.Flags &= ~Flag::Auto;
 915 }
 916                                                                         /*}}}*/
 917 // StateCache::Update - Compute the various static display things       /*{{{*/
 918 // ---------------------------------------------------------------------
 919 /* This is called whenever the Candidate version changes. */
 920 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
 921 {
 922    // Some info
 923    VerIterator Ver = CandidateVerIter(Cache);
 924
 925    // Use a null string or the version string
 926    if (Ver.end() == true)
 927       CandVersion = "";
 928    else
 929       CandVersion = Ver.VerStr();
 930
 931    // Find the current version
 932    CurVersion = "";
 933    if (Pkg->CurrentVer != 0)
 934       CurVersion = Pkg.CurrentVer().VerStr();
 935
 936    // Strip off the epochs for display
 937    CurVersion = StripEpoch(CurVersion);
 938    CandVersion = StripEpoch(CandVersion);
 939
 940    // Figure out if its up or down or equal
 941    Status = Ver.CompareVer(Pkg.CurrentVer());
 942    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
 943      Status = 2;
 944 }
 945                                                                         /*}}}*/
 946 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
 947 // ---------------------------------------------------------------------
 948 /* */
 949 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
 950 {
 951    if (Ver == 0)
 952       return 0;
 953
 954    // Strip any epoch
 955    for (const char *I = Ver; *I != 0; I++)
 956       if (*I == ':')
 957          return I + 1;
 958    return Ver;
 959 }
 960                                                                         /*}}}*/
 961
 962 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
 963 // ---------------------------------------------------------------------
 964 /* The default just returns the highest available version that is not
 965    a source and automatic. */
 966 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
 967 {
 968    /* Not source/not automatic versions cannot be a candidate version
 969       unless they are already installed */
 970    VerIterator Last(*(pkgCache *)this,0);
 971
 972    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
 973    {
 974       if (Pkg.CurrentVer() == I)
 975          return I;
 976
 977       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
 978       {
 979          if ((J.File()->Flags & Flag::NotSource) != 0)
 980             continue;
 981
 982          /* Stash the highest version of a not-automatic source, we use it
 983             if there is nothing better */
 984          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
 985          {
 986             if (Last.end() == true)
 987                Last = I;
 988             continue;
 989          }
 990
 991          return I;
 992       }
 993    }
 994
 995    return Last;
 996 }
 997                                                                         /*}}}*/
 998 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
 999 // ---------------------------------------------------------------------
1000 /* */
1001 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1002 {
1003    return Dep.IsCritical();
1004 }
1005                                                                         /*}}}*/
1006
1007 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()
1008   : constructedSuccessfully(false)
1009 {
1010   Configuration::Item const *Opts;
1011   Opts = _config->Tree("APT::NeverAutoRemove");
1012   if (Opts != 0 && Opts->Child != 0)
1013     {
1014       Opts = Opts->Child;
1015       for (; Opts != 0; Opts = Opts->Next)
1016         {
1017           if (Opts->Value.empty() == true)
1018             continue;
1019
1020           regex_t *p = new regex_t;
1021           if(regcomp(p,Opts->Value.c_str(),
1022                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1023             {
1024               regfree(p);
1025               delete p;
1026               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1027               return;
1028             }
1029
1030           rootSetRegexp.push_back(p);
1031         }
1032     }
1033
1034   constructedSuccessfully = true;
1035 }
1036
1037 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()
1038 {
1039   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1040     {
1041       regfree(rootSetRegexp[i]);
1042       delete rootSetRegexp[i];
1043     }
1044 }
1045
1046
1047 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg)
1048 {
1049    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1050       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1051          return true;
1052
1053    return false;
1054 }
1055
1056 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()
1057 {
1058   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1059   if(f->wasConstructedSuccessfully())
1060     return f;
1061   else
1062     {
1063       delete f;
1064       return NULL;
1065     }
1066 }
1067
1068 bool pkgDepCache::MarkFollowsRecommends()
1069 {
1070   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1071 }
1072
1073 bool pkgDepCache::MarkFollowsSuggests()
1074 {
1075   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1076 }
1077
1078 // the main mark algorithm
1079 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1080 {
1081    bool follow_recommends;
1082    bool follow_suggests;
1083
1084    // init the states
1085    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1086    {
1087       PkgState[p->ID].Marked  = false;
1088       PkgState[p->ID].Garbage = false;
1089
1090       // debug output
1091       if(_config->FindB("Debug::pkgAutoRemove",false)
1092          && PkgState[p->ID].Flags & Flag::Auto)
1093          std::clog << "AutoDep: " << p.Name() << std::endl;
1094    }
1095
1096    // init vars
1097    follow_recommends = MarkFollowsRecommends();
1098    follow_suggests   = MarkFollowsSuggests();
1099
1100
1101
1102    // do the mark part, this is the core bit of the algorithm
1103    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1104    {
1105       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1106           (p->Flags & Flag::Essential) ||
1107           userFunc.InRootSet(p))
1108
1109       {
1110          // the package is installed (and set to keep)
1111          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1112             MarkPackage(p, p.CurrentVer(),
1113                         follow_recommends, follow_suggests);
1114          // the package is to be installed
1115          else if(PkgState[p->ID].Install())
1116             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1117                         follow_recommends, follow_suggests);
1118       }
1119    }
1120
1121    return true;
1122 }
1123
1124 // mark a single package in Mark-and-Sweep
1125 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1126                               const pkgCache::VerIterator &ver,
1127                               bool follow_recommends,
1128                               bool follow_suggests)
1129 {
1130    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1131    VerIterator candver            = state.CandidateVerIter(*this);
1132    VerIterator instver            = state.InstVerIter(*this);
1133
1134 #if 0
1135    // If a package was garbage-collected but is now being marked, we
1136    // should re-select it
1137    // For cases when a pkg is set to upgrade and this trigger the
1138    // removal of a no-longer used dependency.  if the pkg is set to
1139    // keep again later it will result in broken deps
1140    if(state.Delete() && state.RemoveReason = Unused)
1141    {
1142       if(ver==candver)
1143          mark_install(pkg, false, false, NULL);
1144       else if(ver==pkg.CurrentVer())
1145          MarkKeep(pkg, false, false);
1146
1147       instver=state.InstVerIter(*this);
1148    }
1149 #endif
1150
1151    // Ignore versions other than the InstVer, and ignore packages
1152    // that are already going to be removed or just left uninstalled.
1153    if(!(ver == instver && !instver.end()))
1154       return;
1155
1156    // if we are marked already we are done
1157    if(state.Marked)
1158       return;
1159
1160    //std::cout << "Setting Marked for: " << pkg.Name() << std::endl;
1161    state.Marked=true;
1162
1163    if(!ver.end())
1164    {
1165      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1166      {
1167         if(d->Type == Dep::Depends ||
1168            d->Type == Dep::PreDepends ||
1169            (follow_recommends &&
1170             d->Type == Dep::Recommends) ||
1171            (follow_suggests &&
1172             d->Type == Dep::Suggests))
1173         {
1174            // Try all versions of this package.
1175            for(VerIterator V = d.TargetPkg().VersionList();
1176                !V.end(); ++V)
1177            {
1178               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1179               {
1180                  MarkPackage(V.ParentPkg(), V,
1181                              follow_recommends, follow_suggests);
1182               }
1183            }
1184            // Now try virtual packages
1185            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1186                !prv.end(); ++prv)
1187            {
1188               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1189                                        d.TargetVer()))
1190               {
1191                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1192                              follow_recommends, follow_suggests);
1193               }
1194            }
1195         }
1196      }
1197    }
1198 }
1199
1200 bool pkgDepCache::Sweep()
1201 {
1202    // do the sweep
1203    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1204   {
1205      StateCache &state=PkgState[p->ID];
1206
1207      // if it is not marked and it is installed, it's garbage
1208      if(!state.Marked && (!p.CurrentVer().end() || state.Install()) &&
1209         !state.Delete())
1210      {
1211         state.Garbage=true;
1212         if(_config->FindB("Debug::pkgAutoRemove",false))
1213            std::cout << "Garbage: " << p.Name() << std::endl;
1214      }
1215   }
1216
1217    return true;
1218 }