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