apt-pkg/depcache.cc

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