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