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