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