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