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