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             // now check if we should consider it a automatic dependency or not
 911             string sec = _config->Find("APT::Never-MarkAuto-Section","");
 912             if(Pkg.Section() && (string(Pkg.Section()) ==  sec))
 913             {
 914                if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 915                   std::clog << "Setting NOT as auto-installed because its a direct dep of a package in section " << sec << std::endl;
 916                MarkInstall(InstPkg,true,Depth + 1, true);
 917             }
 918             else
 919             {
 920                // mark automatic dependency
 921                MarkInstall(InstPkg,true,Depth + 1, false);
 922                // Set the autoflag, after MarkInstall because MarkInstall unsets it
 923                if (P->CurrentVer == 0)
 924                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
 925             }
 926          }
 927          continue;
 928       }
 929
 930       /* For conflicts we just de-install the package and mark as auto,
 931          Conflicts may not have or groups */
 932       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes)
 933       {
 934          for (Version **I = List; *I != 0; I++)
 935          {
 936             VerIterator Ver(*this,*I);
 937             PkgIterator Pkg = Ver.ParentPkg();
 938
 939             MarkDelete(Pkg);
 940          }
 941          continue;
 942       }
 943    }
 944 }
 945                                                                         /*}}}*/
 946 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 947 // ---------------------------------------------------------------------
 948 /* */
 949 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 950 {
 951    ActionGroup group(*this);
 952
 953    RemoveSizes(Pkg);
 954    RemoveStates(Pkg);
 955
 956    StateCache &P = PkgState[Pkg->ID];
 957    if (To == true)
 958       P.iFlags |= ReInstall;
 959    else
 960       P.iFlags &= ~ReInstall;
 961
 962    AddStates(Pkg);
 963    AddSizes(Pkg);
 964 }
 965                                                                         /*}}}*/
 966 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
 967 // ---------------------------------------------------------------------
 968 /* */
 969 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
 970 {
 971    ActionGroup group(*this);
 972
 973    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
 974    StateCache &P = PkgState[Pkg->ID];
 975
 976    RemoveSizes(Pkg);
 977    RemoveStates(Pkg);
 978
 979    if (P.CandidateVer == P.InstallVer)
 980       P.InstallVer = (Version *)TargetVer;
 981    P.CandidateVer = (Version *)TargetVer;
 982    P.Update(Pkg,*this);
 983
 984    AddStates(Pkg);
 985    Update(Pkg);
 986    AddSizes(Pkg);
 987 }
 988
 989 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
 990 {
 991   StateCache &state = PkgState[Pkg->ID];
 992
 993   ActionGroup group(*this);
 994
 995   if(Auto)
 996     state.Flags |= Flag::Auto;
 997   else
 998     state.Flags &= ~Flag::Auto;
 999 }
1000                                                                         /*}}}*/
1001 // StateCache::Update - Compute the various static display things       /*{{{*/
1002 // ---------------------------------------------------------------------
1003 /* This is called whenever the Candidate version changes. */
1004 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1005 {
1006    // Some info
1007    VerIterator Ver = CandidateVerIter(Cache);
1008
1009    // Use a null string or the version string
1010    if (Ver.end() == true)
1011       CandVersion = "";
1012    else
1013       CandVersion = Ver.VerStr();
1014
1015    // Find the current version
1016    CurVersion = "";
1017    if (Pkg->CurrentVer != 0)
1018       CurVersion = Pkg.CurrentVer().VerStr();
1019
1020    // Strip off the epochs for display
1021    CurVersion = StripEpoch(CurVersion);
1022    CandVersion = StripEpoch(CandVersion);
1023
1024    // Figure out if its up or down or equal
1025    Status = Ver.CompareVer(Pkg.CurrentVer());
1026    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1027      Status = 2;
1028 }
1029                                                                         /*}}}*/
1030 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1031 // ---------------------------------------------------------------------
1032 /* */
1033 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1034 {
1035    if (Ver == 0)
1036       return 0;
1037
1038    // Strip any epoch
1039    for (const char *I = Ver; *I != 0; I++)
1040       if (*I == ':')
1041          return I + 1;
1042    return Ver;
1043 }
1044                                                                         /*}}}*/
1045
1046 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1047 // ---------------------------------------------------------------------
1048 /* The default just returns the highest available version that is not
1049    a source and automatic. */
1050 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1051 {
1052    /* Not source/not automatic versions cannot be a candidate version
1053       unless they are already installed */
1054    VerIterator Last(*(pkgCache *)this,0);
1055
1056    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1057    {
1058       if (Pkg.CurrentVer() == I)
1059          return I;
1060
1061       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1062       {
1063          if ((J.File()->Flags & Flag::NotSource) != 0)
1064             continue;
1065
1066          /* Stash the highest version of a not-automatic source, we use it
1067             if there is nothing better */
1068          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1069          {
1070             if (Last.end() == true)
1071                Last = I;
1072             continue;
1073          }
1074
1075          return I;
1076       }
1077    }
1078
1079    return Last;
1080 }
1081                                                                         /*}}}*/
1082 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1083 // ---------------------------------------------------------------------
1084 /* */
1085 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1086 {
1087    return Dep.IsCritical();
1088 }
1089                                                                         /*}}}*/
1090
1091 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()
1092   : constructedSuccessfully(false)
1093 {
1094   Configuration::Item const *Opts;
1095   Opts = _config->Tree("APT::NeverAutoRemove");
1096   if (Opts != 0 && Opts->Child != 0)
1097     {
1098       Opts = Opts->Child;
1099       for (; Opts != 0; Opts = Opts->Next)
1100         {
1101           if (Opts->Value.empty() == true)
1102             continue;
1103
1104           regex_t *p = new regex_t;
1105           if(regcomp(p,Opts->Value.c_str(),
1106                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1107             {
1108               regfree(p);
1109               delete p;
1110               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1111               return;
1112             }
1113
1114           rootSetRegexp.push_back(p);
1115         }
1116     }
1117
1118   constructedSuccessfully = true;
1119 }
1120
1121 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()
1122 {
1123   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1124     {
1125       regfree(rootSetRegexp[i]);
1126       delete rootSetRegexp[i];
1127     }
1128 }
1129
1130
1131 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg)
1132 {
1133    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1134       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1135          return true;
1136
1137    return false;
1138 }
1139
1140 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()
1141 {
1142   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1143   if(f->wasConstructedSuccessfully())
1144     return f;
1145   else
1146     {
1147       delete f;
1148       return NULL;
1149     }
1150 }
1151
1152 bool pkgDepCache::MarkFollowsRecommends()
1153 {
1154   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1155 }
1156
1157 bool pkgDepCache::MarkFollowsSuggests()
1158 {
1159   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1160 }
1161
1162 // the main mark algorithm
1163 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1164 {
1165    bool follow_recommends;
1166    bool follow_suggests;
1167
1168    // init the states
1169    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1170    {
1171       PkgState[p->ID].Marked  = false;
1172       PkgState[p->ID].Garbage = false;
1173
1174       // debug output
1175       if(_config->FindB("Debug::pkgAutoRemove",false)
1176          && PkgState[p->ID].Flags & Flag::Auto)
1177          std::clog << "AutoDep: " << p.Name() << std::endl;
1178    }
1179
1180    // init vars
1181    follow_recommends = MarkFollowsRecommends();
1182    follow_suggests   = MarkFollowsSuggests();
1183
1184
1185
1186    // do the mark part, this is the core bit of the algorithm
1187    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1188    {
1189       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1190           (p->Flags & Flag::Essential) ||
1191           userFunc.InRootSet(p))
1192
1193       {
1194          // the package is installed (and set to keep)
1195          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1196             MarkPackage(p, p.CurrentVer(),
1197                         follow_recommends, follow_suggests);
1198          // the package is to be installed
1199          else if(PkgState[p->ID].Install())
1200             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1201                         follow_recommends, follow_suggests);
1202       }
1203    }
1204
1205    return true;
1206 }
1207
1208 // mark a single package in Mark-and-Sweep
1209 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1210                               const pkgCache::VerIterator &ver,
1211                               bool follow_recommends,
1212                               bool follow_suggests)
1213 {
1214    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1215    VerIterator candver            = state.CandidateVerIter(*this);
1216    VerIterator instver            = state.InstVerIter(*this);
1217
1218 #if 0
1219    // If a package was garbage-collected but is now being marked, we
1220    // should re-select it
1221    // For cases when a pkg is set to upgrade and this trigger the
1222    // removal of a no-longer used dependency.  if the pkg is set to
1223    // keep again later it will result in broken deps
1224    if(state.Delete() && state.RemoveReason = Unused)
1225    {
1226       if(ver==candver)
1227          mark_install(pkg, false, false, NULL);
1228       else if(ver==pkg.CurrentVer())
1229          MarkKeep(pkg, false, false);
1230
1231       instver=state.InstVerIter(*this);
1232    }
1233 #endif
1234
1235    // Ignore versions other than the InstVer, and ignore packages
1236    // that are already going to be removed or just left uninstalled.
1237    if(!(ver == instver && !instver.end()))
1238       return;
1239
1240    // if we are marked already we are done
1241    if(state.Marked)
1242       return;
1243
1244    //std::cout << "Setting Marked for: " << pkg.Name() << std::endl;
1245    state.Marked=true;
1246
1247    if(!ver.end())
1248    {
1249      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1250      {
1251         if(d->Type == Dep::Depends ||
1252            d->Type == Dep::PreDepends ||
1253            (follow_recommends &&
1254             d->Type == Dep::Recommends) ||
1255            (follow_suggests &&
1256             d->Type == Dep::Suggests))
1257         {
1258            // Try all versions of this package.
1259            for(VerIterator V = d.TargetPkg().VersionList();
1260                !V.end(); ++V)
1261            {
1262               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1263               {
1264                  MarkPackage(V.ParentPkg(), V,
1265                              follow_recommends, follow_suggests);
1266               }
1267            }
1268            // Now try virtual packages
1269            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1270                !prv.end(); ++prv)
1271            {
1272               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1273                                        d.TargetVer()))
1274               {
1275                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1276                              follow_recommends, follow_suggests);
1277               }
1278            }
1279         }
1280      }
1281    }
1282 }
1283
1284 bool pkgDepCache::Sweep()
1285 {
1286    // do the sweep
1287    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1288   {
1289      StateCache &state=PkgState[p->ID];
1290
1291      // skip required packages
1292      if (!p.CurrentVer().end() &&
1293          (p.CurrentVer()->Priority == pkgCache::State::Required))
1294         continue;
1295
1296      // if it is not marked and it is installed, it's garbage
1297      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1298      {
1299         state.Garbage=true;
1300         if(_config->FindB("Debug::pkgAutoRemove",false))
1301            std::cout << "Garbage: " << p.Name() << std::endl;
1302      }
1303   }
1304
1305    return true;
1306 }