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 #include <apt-pkg/depcache.h>
  12 #include <apt-pkg/version.h>
  13 #include <apt-pkg/error.h>
  14 #include <apt-pkg/sptr.h>
  15 #include <apt-pkg/algorithms.h>
  16
  17 #include <apt-pkg/fileutl.h>
  18 #include <apt-pkg/strutl.h>
  19 #include <apt-pkg/configuration.h>
  20 #include <apt-pkg/aptconfiguration.h>
  21 #include <apt-pkg/pkgsystem.h>
  22 #include <apt-pkg/tagfile.h>
  23
  24 #include <iostream>
  25 #include <sstream>
  26 #include <set>
  27
  28 #include <sys/stat.h>
  29
  30 #include <apti18n.h>
  31                                                                         /*}}}*/
  32 // helper for Install-Recommends-Sections and Never-MarkAuto-Sections   /*{{{*/
  33 static bool
  34 ConfigValueInSubTree(const char* SubTree, const char *needle)
  35 {
  36    Configuration::Item const *Opts;
  37    Opts = _config->Tree(SubTree);
  38    if (Opts != 0 && Opts->Child != 0)
  39    {
  40       Opts = Opts->Child;
  41       for (; Opts != 0; Opts = Opts->Next)
  42       {
  43          if (Opts->Value.empty() == true)
  44             continue;
  45          if (strcmp(needle, Opts->Value.c_str()) == 0)
  46             return true;
  47       }
  48    }
  49    return false;
  50 }
  51                                                                         /*}}}*/
  52 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :             /*{{{*/
  53   cache(cache), released(false)
  54 {
  55   ++cache.group_level;
  56 }
  57
  58 void pkgDepCache::ActionGroup::release()
  59 {
  60   if(!released)
  61     {
  62       if(cache.group_level == 0)
  63         std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
  64       else
  65         {
  66           --cache.group_level;
  67
  68           if(cache.group_level == 0)
  69             cache.MarkAndSweep();
  70         }
  71
  72       released = false;
  73     }
  74 }
  75
  76 pkgDepCache::ActionGroup::~ActionGroup()
  77 {
  78   release();
  79 }
  80                                                                         /*}}}*/
  81 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  82 // ---------------------------------------------------------------------
  83 /* */
  84 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  85   group_level(0), Cache(pCache), PkgState(0), DepState(0)
  86 {
  87    DebugMarker = _config->FindB("Debug::pkgDepCache::Marker", false);
  88    DebugAutoInstall = _config->FindB("Debug::pkgDepCache::AutoInstall", false);
  89    delLocalPolicy = 0;
  90    LocalPolicy = Plcy;
  91    if (LocalPolicy == 0)
  92       delLocalPolicy = LocalPolicy = new Policy;
  93 }
  94                                                                         /*}}}*/
  95 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
  96 // ---------------------------------------------------------------------
  97 /* */
  98 pkgDepCache::~pkgDepCache()
  99 {
 100    delete [] PkgState;
 101    delete [] DepState;
 102    delete delLocalPolicy;
 103 }
 104                                                                         /*}}}*/
 105 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
 106 // ---------------------------------------------------------------------
 107 /* This allocats the extension buffers and initializes them. */
 108 bool pkgDepCache::Init(OpProgress *Prog)
 109 {
 110    // Suppress mark updates during this operation (just in case) and
 111    // run a mark operation when Init terminates.
 112    ActionGroup actions(*this);
 113
 114    delete [] PkgState;
 115    delete [] DepState;
 116    PkgState = new StateCache[Head().PackageCount];
 117    DepState = new unsigned char[Head().DependsCount];
 118    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
 119    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
 120
 121    if (Prog != 0)
 122    {
 123       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 124                             _("Building dependency tree"));
 125       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 126    }
 127
 128    /* Set the current state of everything. In this state all of the
 129       packages are kept exactly as is. See AllUpgrade */
 130    int Done = 0;
 131    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 132    {
 133       if (Prog != 0 && Done%20 == 0)
 134          Prog->Progress(Done);
 135
 136       // Find the proper cache slot
 137       StateCache &State = PkgState[I->ID];
 138       State.iFlags = 0;
 139
 140       // Figure out the install version
 141       State.CandidateVer = GetCandidateVer(I);
 142       State.InstallVer = I.CurrentVer();
 143       State.Mode = ModeKeep;
 144
 145       State.Update(I,*this);
 146    }
 147
 148    if (Prog != 0)
 149    {
 150
 151       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 152                             Head().PackageCount,
 153                             _("Building dependency tree"));
 154       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 155    }
 156
 157    Update(Prog);
 158
 159    if(Prog != 0)
 160       Prog->Done();
 161
 162    return true;
 163 }
 164                                                                         /*}}}*/
 165 bool pkgDepCache::readStateFile(OpProgress *Prog)                       /*{{{*/
 166 {
 167    FileFd state_file;
 168    string const state = _config->FindDir("Dir::State") + "extended_states";
 169    if(FileExists(state)) {
 170       state_file.Open(state, FileFd::ReadOnly);
 171       int const file_size = state_file.Size();
 172       if(Prog != NULL)
 173          Prog->OverallProgress(0, file_size, 1,
 174                                _("Reading state information"));
 175
 176       pkgTagFile tagfile(&state_file);
 177       pkgTagSection section;
 178       int amt = 0;
 179       bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 180       while(tagfile.Step(section)) {
 181          string const pkgname = section.FindS("Package");
 182          string pkgarch = section.FindS("Architecture");
 183          if (pkgarch.empty() == true)
 184             pkgarch = "any";
 185          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 186          // Silently ignore unknown packages and packages with no actual version.
 187          if(pkg.end() == true || pkg->VersionList == 0)
 188             continue;
 189
 190          short const reason = section.FindI("Auto-Installed", 0);
 191          if(reason > 0)
 192          {
 193             PkgState[pkg->ID].Flags |= Flag::Auto;
 194             if (unlikely(debug_autoremove))
 195                std::cout << "Auto-Installed : " << pkg.FullName() << std::endl;
 196             if (pkgarch == "any")
 197             {
 198                pkgCache::GrpIterator G = pkg.Group();
 199                for (pkg = G.NextPkg(pkg); pkg.end() != true; pkg = G.NextPkg(pkg))
 200                   if (pkg->VersionList != 0)
 201                      PkgState[pkg->ID].Flags |= Flag::Auto;
 202             }
 203          }
 204          amt += section.size();
 205          if(Prog != NULL)
 206             Prog->OverallProgress(amt, file_size, 1,
 207                                   _("Reading state information"));
 208       }
 209       if(Prog != NULL)
 210          Prog->OverallProgress(file_size, file_size, 1,
 211                                _("Reading state information"));
 212    }
 213
 214    return true;
 215 }
 216                                                                         /*}}}*/
 217 bool pkgDepCache::writeStateFile(OpProgress *prog, bool InstalledOnly)  /*{{{*/
 218 {
 219    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 220
 221    if(debug_autoremove)
 222       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 223
 224    FileFd StateFile;
 225    string const state = _config->FindDir("Dir::State") + "extended_states";
 226
 227    // if it does not exist, create a empty one
 228    if(!FileExists(state))
 229    {
 230       StateFile.Open(state, FileFd::WriteEmpty);
 231       StateFile.Close();
 232    }
 233
 234    // open it
 235    if(!StateFile.Open(state, FileFd::ReadOnly))
 236       return _error->Error(_("Failed to open StateFile %s"),
 237                            state.c_str());
 238
 239    FILE *OutFile;
 240    string const outfile = state + ".tmp";
 241    if((OutFile = fopen(outfile.c_str(),"w")) == NULL)
 242       return _error->Error(_("Failed to write temporary StateFile %s"),
 243                            outfile.c_str());
 244
 245    // first merge with the existing sections
 246    pkgTagFile tagfile(&StateFile);
 247    pkgTagSection section;
 248    std::set<string> pkgs_seen;
 249    const char *nullreorderlist[] = {0};
 250    while(tagfile.Step(section)) {
 251          string const pkgname = section.FindS("Package");
 252          string pkgarch = section.FindS("Architecture");
 253          if (pkgarch.empty() == true)
 254             pkgarch = "native";
 255          // Silently ignore unknown packages and packages with no actual
 256          // version.
 257          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 258          if(pkg.end() || pkg.VersionList().end())
 259             continue;
 260          StateCache const &P = PkgState[pkg->ID];
 261          bool newAuto = (P.Flags & Flag::Auto);
 262          // skip not installed or now-removed ones if requested
 263          if (InstalledOnly && (
 264              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 265              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 266          {
 267             // The section is obsolete if it contains no other tag
 268             unsigned int const count = section.Count();
 269             if (count < 2 ||
 270                 (count == 2 && section.Exists("Auto-Installed")) ||
 271                 (count == 3 && section.Exists("Auto-Installed") && section.Exists("Architecture")))
 272                continue;
 273             else
 274                newAuto = false;
 275          }
 276          if(_config->FindB("Debug::pkgAutoRemove",false))
 277             std::clog << "Update existing AutoInstall info: "
 278                       << pkg.FullName() << std::endl;
 279          TFRewriteData rewrite[3];
 280          rewrite[0].Tag = "Architecture";
 281          rewrite[0].Rewrite = pkg.Arch();
 282          rewrite[0].NewTag = 0;
 283          rewrite[1].Tag = "Auto-Installed";
 284          rewrite[1].Rewrite = newAuto ? "1" : "0";
 285          rewrite[1].NewTag = 0;
 286          rewrite[2].Tag = 0;
 287          TFRewrite(OutFile, section, nullreorderlist, rewrite);
 288          fprintf(OutFile,"\n");
 289          pkgs_seen.insert(pkg.FullName());
 290    }
 291
 292    // then write the ones we have not seen yet
 293    std::ostringstream ostr;
 294    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end(); pkg++) {
 295       StateCache const &P = PkgState[pkg->ID];
 296       if(P.Flags & Flag::Auto) {
 297          if (pkgs_seen.find(pkg.FullName()) != pkgs_seen.end()) {
 298             if(debug_autoremove)
 299                std::clog << "Skipping already written " << pkg.FullName() << std::endl;
 300             continue;
 301          }
 302          // skip not installed ones if requested
 303          if (InstalledOnly && (
 304              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 305              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 306             continue;
 307          const char* const pkgarch = pkg.Arch();
 308          if (strcmp(pkgarch, "all") == 0)
 309             continue;
 310          if(debug_autoremove)
 311             std::clog << "Writing new AutoInstall: " << pkg.FullName() << std::endl;
 312          ostr.str(string(""));
 313          ostr << "Package: " << pkg.Name()
 314               << "\nArchitecture: " << pkgarch
 315               << "\nAuto-Installed: 1\n\n";
 316          fprintf(OutFile,"%s",ostr.str().c_str());
 317       }
 318    }
 319    fclose(OutFile);
 320
 321    // move the outfile over the real file and set permissions
 322    rename(outfile.c_str(), state.c_str());
 323    chmod(state.c_str(), 0644);
 324
 325    return true;
 326 }
 327                                                                         /*}}}*/
 328 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 329 // ---------------------------------------------------------------------
 330 /* This first checks the dependency against the main target package and
 331    then walks along the package provides list and checks if each provides
 332    will be installed then checks the provides against the dep. Res will be
 333    set to the package which was used to satisfy the dep. */
 334 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 335 {
 336    Res = Dep.TargetPkg();
 337
 338    /* Check simple depends. A depends -should- never self match but
 339       we allow it anyhow because dpkg does. Technically it is a packaging
 340       bug. Conflicts may never self match */
 341    if (Dep.TargetPkg() != Dep.ParentPkg() ||
 342        (Dep->Type != Dep::Conflicts && Dep->Type != Dep::DpkgBreaks && Dep->Type != Dep::Obsoletes))
 343    {
 344       PkgIterator Pkg = Dep.TargetPkg();
 345       // Check the base package
 346       if (Type == NowVersion && Pkg->CurrentVer != 0)
 347          if (VS().CheckDep(Pkg.CurrentVer().VerStr(),Dep->CompareOp,
 348                                  Dep.TargetVer()) == true)
 349             return true;
 350
 351       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 352          if (VS().CheckDep(PkgState[Pkg->ID].InstVerIter(*this).VerStr(),
 353                                  Dep->CompareOp,Dep.TargetVer()) == true)
 354             return true;
 355
 356       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 357          if (VS().CheckDep(PkgState[Pkg->ID].CandidateVerIter(*this).VerStr(),
 358                                  Dep->CompareOp,Dep.TargetVer()) == true)
 359             return true;
 360    }
 361
 362    if (Dep->Type == Dep::Obsoletes)
 363       return false;
 364
 365    // Check the providing packages
 366    PrvIterator P = Dep.TargetPkg().ProvidesList();
 367    PkgIterator Pkg = Dep.ParentPkg();
 368    for (; P.end() != true; P++)
 369    {
 370       /* Provides may never be applied against the same package if it is
 371          a conflicts. See the comment above. */
 372       if (P.OwnerPkg() == Pkg &&
 373           (Dep->Type == Dep::Conflicts || Dep->Type == Dep::DpkgBreaks))
 374          continue;
 375
 376       // Check if the provides is a hit
 377       if (Type == NowVersion)
 378       {
 379          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 380             continue;
 381       }
 382
 383       if (Type == InstallVersion)
 384       {
 385          StateCache &State = PkgState[P.OwnerPkg()->ID];
 386          if (State.InstallVer != (Version *)P.OwnerVer())
 387             continue;
 388       }
 389
 390       if (Type == CandidateVersion)
 391       {
 392          StateCache &State = PkgState[P.OwnerPkg()->ID];
 393          if (State.CandidateVer != (Version *)P.OwnerVer())
 394             continue;
 395       }
 396
 397       // Compare the versions.
 398       if (VS().CheckDep(P.ProvideVersion(),Dep->CompareOp,Dep.TargetVer()) == true)
 399       {
 400          Res = P.OwnerPkg();
 401          return true;
 402       }
 403    }
 404
 405    return false;
 406 }
 407                                                                         /*}}}*/
 408 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 409 // ---------------------------------------------------------------------
 410 /* Call with Mult = -1 to preform the inverse opration */
 411 void pkgDepCache::AddSizes(const PkgIterator &Pkg,signed long Mult)
 412 {
 413    StateCache &P = PkgState[Pkg->ID];
 414
 415    if (Pkg->VersionList == 0)
 416       return;
 417
 418    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 419        P.Keep() == true)
 420       return;
 421
 422    // Compute the size data
 423    if (P.NewInstall() == true)
 424    {
 425       iUsrSize += (signed)(Mult*P.InstVerIter(*this)->InstalledSize);
 426       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 427       return;
 428    }
 429
 430    // Upgrading
 431    if (Pkg->CurrentVer != 0 &&
 432        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 433         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 434    {
 435       iUsrSize += (signed)(Mult*((signed)P.InstVerIter(*this)->InstalledSize -
 436                         (signed)Pkg.CurrentVer()->InstalledSize));
 437       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 438       return;
 439    }
 440
 441    // Reinstall
 442    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 443        P.Delete() == false)
 444    {
 445       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 446       return;
 447    }
 448
 449    // Removing
 450    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 451    {
 452       iUsrSize -= (signed)(Mult*Pkg.CurrentVer()->InstalledSize);
 453       return;
 454    }
 455 }
 456                                                                         /*}}}*/
 457 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 458 // ---------------------------------------------------------------------
 459 /* This routine is tricky to use, you must make sure that it is never
 460    called twice for the same package. This means the Remove/Add section
 461    should be as short as possible and not encompass any code that will
 462    calld Remove/Add itself. Remember, dependencies can be circular so
 463    while processing a dep for Pkg it is possible that Add/Remove
 464    will be called on Pkg */
 465 void pkgDepCache::AddStates(const PkgIterator &Pkg,int Add)
 466 {
 467    StateCache &State = PkgState[Pkg->ID];
 468
 469    // The Package is broken (either minimal dep or policy dep)
 470    if ((State.DepState & DepInstMin) != DepInstMin)
 471       iBrokenCount += Add;
 472    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 473       iPolicyBrokenCount += Add;
 474
 475    // Bad state
 476    if (Pkg.State() != PkgIterator::NeedsNothing)
 477       iBadCount += Add;
 478
 479    // Not installed
 480    if (Pkg->CurrentVer == 0)
 481    {
 482       if (State.Mode == ModeDelete &&
 483           (State.iFlags | Purge) == Purge && Pkg.Purge() == false)
 484          iDelCount += Add;
 485
 486       if (State.Mode == ModeInstall)
 487          iInstCount += Add;
 488       return;
 489    }
 490
 491    // Installed, no upgrade
 492    if (State.Status == 0)
 493    {
 494       if (State.Mode == ModeDelete)
 495          iDelCount += Add;
 496       else
 497          if ((State.iFlags & ReInstall) == ReInstall)
 498             iInstCount += Add;
 499
 500       return;
 501    }
 502
 503    // Alll 3 are possible
 504    if (State.Mode == ModeDelete)
 505       iDelCount += Add;
 506    if (State.Mode == ModeKeep)
 507       iKeepCount += Add;
 508    if (State.Mode == ModeInstall)
 509       iInstCount += Add;
 510 }
 511                                                                         /*}}}*/
 512 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 513 // ---------------------------------------------------------------------
 514 /* The or group results are stored in the last item of the or group. This
 515    allows easy detection of the state of a whole or'd group. */
 516 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 517 {
 518    unsigned char Group = 0;
 519
 520    for (DepIterator D = V.DependsList(); D.end() != true; D++)
 521    {
 522       // Build the dependency state.
 523       unsigned char &State = DepState[D->ID];
 524
 525       /* Invert for Conflicts. We have to do this twice to get the
 526          right sense for a conflicts group */
 527       if (D->Type == Dep::Conflicts ||
 528           D->Type == Dep::DpkgBreaks ||
 529           D->Type == Dep::Obsoletes)
 530          State = ~State;
 531
 532       // Add to the group if we are within an or..
 533       State &= 0x7;
 534       Group |= State;
 535       State |= Group << 3;
 536       if ((D->CompareOp & Dep::Or) != Dep::Or)
 537          Group = 0;
 538
 539       // Invert for Conflicts
 540       if (D->Type == Dep::Conflicts ||
 541           D->Type == Dep::DpkgBreaks ||
 542           D->Type == Dep::Obsoletes)
 543          State = ~State;
 544    }
 545 }
 546                                                                         /*}}}*/
 547 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 548 // ---------------------------------------------------------------------
 549 /* This is used to run over a dependency list and determine the dep
 550    state of the list, filtering it through both a Min check and a Policy
 551    check. The return result will have SetMin/SetPolicy low if a check
 552    fails. It uses the DepState cache for it's computations. */
 553 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 554                                        unsigned char SetMin,
 555                                        unsigned char SetPolicy)
 556 {
 557    unsigned char Dep = 0xFF;
 558
 559    while (D.end() != true)
 560    {
 561       // Compute a single dependency element (glob or)
 562       DepIterator Start = D;
 563       unsigned char State = 0;
 564       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 565       {
 566          State |= DepState[D->ID];
 567          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 568       }
 569
 570       // Minimum deps that must be satisfied to have a working package
 571       if (Start.IsCritical() == true)
 572          if ((State & Check) != Check)
 573             Dep &= ~SetMin;
 574
 575       // Policy deps that must be satisfied to install the package
 576       if (IsImportantDep(Start) == true &&
 577           (State & Check) != Check)
 578          Dep &= ~SetPolicy;
 579    }
 580
 581    return Dep;
 582 }
 583                                                                         /*}}}*/
 584 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 585 // ---------------------------------------------------------------------
 586 /* This is the main dependency computation bit. It computes the 3 main
 587    results for a dependencys, Now, Install and Candidate. Callers must
 588    invert the result if dealing with conflicts. */
 589 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 590 {
 591    unsigned char State = 0;
 592
 593    if (CheckDep(D,NowVersion) == true)
 594       State |= DepNow;
 595    if (CheckDep(D,InstallVersion) == true)
 596       State |= DepInstall;
 597    if (CheckDep(D,CandidateVersion) == true)
 598       State |= DepCVer;
 599
 600    return State;
 601 }
 602                                                                         /*}}}*/
 603 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 604 // ---------------------------------------------------------------------
 605 /* This determines the combined dependency representation of a package
 606    for its two states now and install. This is done by using the pre-generated
 607    dependency information. */
 608 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 609 {
 610    // Empty deps are always true
 611    StateCache &State = PkgState[Pkg->ID];
 612    State.DepState = 0xFF;
 613
 614    // Check the Current state
 615    if (Pkg->CurrentVer != 0)
 616    {
 617       DepIterator D = Pkg.CurrentVer().DependsList();
 618       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 619    }
 620
 621    /* Check the candidate state. We do not compare against the whole as
 622       a candidate state but check the candidate version against the
 623       install states */
 624    if (State.CandidateVer != 0)
 625    {
 626       DepIterator D = State.CandidateVerIter(*this).DependsList();
 627       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 628    }
 629
 630    // Check target state which can only be current or installed
 631    if (State.InstallVer != 0)
 632    {
 633       DepIterator D = State.InstVerIter(*this).DependsList();
 634       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 635    }
 636 }
 637                                                                         /*}}}*/
 638 // DepCache::RemovePseudoInstalledPkg - MultiArch helper for Update()   /*{{{*/
 639 // ---------------------------------------------------------------------
 640 /* We "install" arch all packages for all archs if it is installed. Many
 641    of these will be broken. This method will look at these broken Pkg and
 642    "remove" it. */
 643 bool pkgDepCache::RemovePseudoInstalledPkg(PkgIterator &Pkg, std::set<unsigned long> &recheck) {
 644    if (unlikely(Pkg->CurrentVer == 0))
 645       return false;
 646
 647    VerIterator V = Pkg.CurrentVer();
 648    if (V->MultiArch != Version::All)
 649       return false;
 650
 651    // Never ever kill an "all" package - they have no dependency so they can't be broken
 652    if (strcmp(Pkg.Arch(),"all") == 0)
 653       return false;
 654
 655    unsigned char const CurDepState = VersionState(V.DependsList(),DepInstall,DepInstMin,DepInstPolicy);
 656    if ((CurDepState & DepInstMin) == DepInstMin) {
 657       // okay, the package isn't broken, but is the package also required?
 658       // If it has no real dependencies, no installed rdepends and doesn't
 659       // provide something of value, we will kill it as not required.
 660       // These pseudopackages have otherwise interesting effects if they get
 661       // a new dependency in a newer version…
 662       for (pkgCache::DepIterator D = V.DependsList();
 663            D.end() != true; ++D)
 664          if (D.IsCritical() == true && D.ParentPkg()->Group != Pkg->Group)
 665             return false;
 666       for (DepIterator D = Pkg.RevDependsList(); D.end() != true; ++D)
 667       {
 668          if (D.IsCritical() == false)
 669             continue;
 670          PkgIterator const P = D.ParentPkg();
 671          if (P->Group == Pkg->Group)
 672             continue;
 673          if (P->CurrentVer != 0)
 674             return false;
 675       }
 676       for (PrvIterator Prv = V.ProvidesList(); Prv.end() != true; Prv++)
 677          for (DepIterator d = Prv.ParentPkg().RevDependsList();
 678               d.end() != true; ++d)
 679          {
 680             PkgIterator const P = d.ParentPkg();
 681             if (P->CurrentVer != 0 &&
 682                 P->Group != Pkg->Group)
 683                return false;
 684          }
 685    }
 686
 687    // Dependencies for this arch all package are not statisfied
 688    // so we installed it only for our convenience: get right of it now.
 689    RemoveSizes(Pkg);
 690    RemoveStates(Pkg);
 691
 692    Pkg->CurrentVer = 0;
 693    PkgState[Pkg->ID].InstallVer = 0;
 694
 695    AddStates(Pkg);
 696    Update(Pkg);
 697    AddSizes(Pkg);
 698
 699    // After the remove previously satisfied pseudo pkg could be now
 700    // no longer satisfied, so we need to recheck the reverse dependencies
 701    for (DepIterator d = Pkg.RevDependsList(); d.end() != true; ++d)
 702    {
 703       PkgIterator const P = d.ParentPkg();
 704       if (P->CurrentVer != 0)
 705          recheck.insert(P.Index());
 706    }
 707
 708    for (DepIterator d = V.DependsList(); d.end() != true; ++d)
 709    {
 710       PkgIterator const P = d.TargetPkg();
 711       for (PrvIterator Prv = P.ProvidesList(); Prv.end() != true; ++Prv)
 712       {
 713          PkgIterator const O = Prv.OwnerPkg();
 714          if (O->CurrentVer != 0)
 715             recheck.insert(O.Index());
 716       }
 717
 718       if (P->CurrentVer != 0)
 719          recheck.insert(P.Index());
 720    }
 721
 722    for (PrvIterator Prv = V.ProvidesList(); Prv.end() != true; Prv++)
 723    {
 724       for (DepIterator d = Prv.ParentPkg().RevDependsList();
 725            d.end() != true; ++d)
 726       {
 727          PkgIterator const P = d.ParentPkg();
 728          if (P->CurrentVer == 0)
 729             continue;
 730
 731             recheck.insert(P.Index());
 732       }
 733    }
 734
 735
 736    return true;
 737 }
 738                                                                         /*}}}*/
 739 // DepCache::Update - Figure out all the state information              /*{{{*/
 740 // ---------------------------------------------------------------------
 741 /* This will figure out the state of all the packages and all the
 742    dependencies based on the current policy. */
 743 void pkgDepCache::Update(OpProgress *Prog)
 744 {
 745    iUsrSize = 0;
 746    iDownloadSize = 0;
 747    iDelCount = 0;
 748    iInstCount = 0;
 749    iKeepCount = 0;
 750    iBrokenCount = 0;
 751    iBadCount = 0;
 752
 753    std::set<unsigned long> recheck;
 754
 755    // Perform the depends pass
 756    int Done = 0;
 757    bool const checkMultiArch = APT::Configuration::getArchitectures().size() > 1;
 758    unsigned long killed = 0;
 759    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 760    {
 761       if (Prog != 0 && Done%20 == 0)
 762          Prog->Progress(Done);
 763       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 764       {
 765          unsigned char Group = 0;
 766
 767          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 768          {
 769             // Build the dependency state.
 770             unsigned char &State = DepState[D->ID];
 771             State = DependencyState(D);
 772
 773             // Add to the group if we are within an or..
 774             Group |= State;
 775             State |= Group << 3;
 776             if ((D->CompareOp & Dep::Or) != Dep::Or)
 777                Group = 0;
 778
 779             // Invert for Conflicts
 780             if (D->Type == Dep::Conflicts ||
 781                 D->Type == Dep::DpkgBreaks ||
 782                 D->Type == Dep::Obsoletes)
 783                State = ~State;
 784          }
 785       }
 786
 787       // Compute the package dependency state and size additions
 788       AddSizes(I);
 789       UpdateVerState(I);
 790       AddStates(I);
 791
 792       if (checkMultiArch != true || I->CurrentVer == 0)
 793          continue;
 794
 795       VerIterator const V = I.CurrentVer();
 796       if (V->MultiArch != Version::All)
 797          continue;
 798
 799       recheck.insert(I.Index());
 800       --Done; // no progress if we need to recheck the package
 801    }
 802
 803    if (checkMultiArch == true) {
 804       /* FIXME: recheck breaks proper progress reporting as we don't know
 805                 how many packages we need to recheck. To lower the effect
 806                 a bit we increase with a kill, but we should do something more clever… */
 807       for(std::set<unsigned long>::const_iterator p = recheck.begin();
 808           p != recheck.end(); ++p) {
 809          if (Prog != 0 && Done%20 == 0)
 810             Prog->Progress(Done);
 811          PkgIterator P = PkgIterator(*Cache, Cache->PkgP + *p);
 812          if (RemovePseudoInstalledPkg(P, recheck) == true) {
 813             ++killed;
 814             ++Done;
 815          }
 816          recheck.erase(p);
 817       }
 818
 819       /* Okay, we have killed a great amount of pseudopackages -
 820          we have killed so many that we have now arch "all" packages
 821          without an installed pseudo package, but we NEED an installed
 822          pseudo package, so we will search now for a pseudo package
 823          we can install without breaking everything. */
 824       for (GrpIterator G = Cache->GrpBegin(); G.end() != true; ++G)
 825       {
 826          PkgIterator P = G.FindPkg("all");
 827          if (P.end() == true)
 828             continue;
 829          if (P->CurrentVer == 0)
 830             continue;
 831          bool installed = false;
 832          for (P = G.FindPkg("any"); P.end() != true; P = G.NextPkg(P))
 833          {
 834             if (strcmp(P.Arch(), "all") == 0)
 835                continue;
 836             if (P->CurrentVer == 0)
 837                continue;
 838             installed = true;
 839             break;
 840          }
 841          if (installed == false)
 842             recheck.insert(G.Index());
 843       }
 844       std::vector<std::string> Archs = APT::Configuration::getArchitectures();
 845       bool checkChanged = false;
 846       do {
 847          for(std::set<unsigned long>::const_iterator g = recheck.begin();
 848              g != recheck.end(); ++g) {
 849             GrpIterator G = GrpIterator(*Cache, Cache->GrpP + *g);
 850             VerIterator allV = G.FindPkg("all").CurrentVer();
 851             for (std::vector<std::string>::const_iterator a = Archs.begin();
 852                  a != Archs.end(); ++a)
 853             {
 854                PkgIterator P = G.FindPkg(*a);
 855                if (P.end() == true) continue;
 856                for (VerIterator V = P.VersionList(); V.end() != true; ++V)
 857                {
 858                   if (allV->Hash != V->Hash ||
 859                       strcmp(allV.VerStr(),V.VerStr()) != 0)
 860                      continue;
 861                   unsigned char const CurDepState = VersionState(V.DependsList(),DepInstall,DepInstMin,DepInstPolicy);
 862                   if ((CurDepState & DepInstMin) != DepInstMin)
 863                      break; // we found the correct version, but it is broken. Better try another arch or later again
 864                   RemoveSizes(P);
 865                   RemoveStates(P);
 866                   P->CurrentVer = V.Index();
 867                   PkgState[P->ID].InstallVer = V;
 868                   AddStates(P);
 869                   Update(P);
 870                   AddSizes(P);
 871                   checkChanged = true;
 872                   break;
 873                }
 874             }
 875             recheck.erase(g);
 876          }
 877       } while (checkChanged == true && recheck.empty() == false);
 878
 879       if (_config->FindB("Debug::MultiArchKiller", false) == true)
 880          for(std::set<unsigned long>::const_iterator g = recheck.begin();
 881              g != recheck.end(); ++g)
 882             std::cout << "No pseudo package for »" << GrpIterator(*Cache, Cache->GrpP + *g).Name() << "« installed" << std::endl;
 883    }
 884
 885    if (Prog != 0)
 886       Prog->Progress(Done);
 887
 888    readStateFile(Prog);
 889 }
 890                                                                         /*}}}*/
 891 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 892 // ---------------------------------------------------------------------
 893 /* This is a helper for update that only does the dep portion of the scan.
 894    It is mainly meant to scan reverse dependencies. */
 895 void pkgDepCache::Update(DepIterator D)
 896 {
 897    // Update the reverse deps
 898    for (;D.end() != true; D++)
 899    {
 900       unsigned char &State = DepState[D->ID];
 901       State = DependencyState(D);
 902
 903       // Invert for Conflicts
 904       if (D->Type == Dep::Conflicts ||
 905           D->Type == Dep::DpkgBreaks ||
 906           D->Type == Dep::Obsoletes)
 907          State = ~State;
 908
 909       RemoveStates(D.ParentPkg());
 910       BuildGroupOrs(D.ParentVer());
 911       UpdateVerState(D.ParentPkg());
 912       AddStates(D.ParentPkg());
 913    }
 914 }
 915                                                                         /*}}}*/
 916 // DepCache::Update - Update the related deps of a package              /*{{{*/
 917 // ---------------------------------------------------------------------
 918 /* This is called whenever the state of a package changes. It updates
 919    all cached dependencies related to this package. */
 920 void pkgDepCache::Update(PkgIterator const &Pkg)
 921 {
 922    // Recompute the dep of the package
 923    RemoveStates(Pkg);
 924    UpdateVerState(Pkg);
 925    AddStates(Pkg);
 926
 927    // Update the reverse deps
 928    Update(Pkg.RevDependsList());
 929
 930    // Update the provides map for the current ver
 931    if (Pkg->CurrentVer != 0)
 932       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 933            P.end() != true; P++)
 934          Update(P.ParentPkg().RevDependsList());
 935
 936    // Update the provides map for the candidate ver
 937    if (PkgState[Pkg->ID].CandidateVer != 0)
 938       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 939            P.end() != true; P++)
 940          Update(P.ParentPkg().RevDependsList());
 941 }
 942                                                                         /*}}}*/
 943 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 944 // ---------------------------------------------------------------------
 945 /* */
 946 void pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 947                            unsigned long Depth)
 948 {
 949    // Simplifies other routines.
 950    if (Pkg.end() == true)
 951       return;
 952
 953    /* Reject an attempt to keep a non-source broken installed package, those
 954       must be upgraded */
 955    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 956        Pkg.CurrentVer().Downloadable() == false)
 957       return;
 958
 959    /** \todo Can this be moved later in the method? */
 960    ActionGroup group(*this);
 961
 962    /* We changed the soft state all the time so the UI is a bit nicer
 963       to use */
 964    StateCache &P = PkgState[Pkg->ID];
 965    if (Soft == true)
 966       P.iFlags |= AutoKept;
 967    else
 968       P.iFlags &= ~AutoKept;
 969
 970    // Check that it is not already kept
 971    if (P.Mode == ModeKeep)
 972       return;
 973
 974    // We dont even try to keep virtual packages..
 975    if (Pkg->VersionList == 0)
 976       return;
 977 #if 0 // reseting the autoflag here means we lose the
 978       // auto-mark information if a user selects a package for removal
 979       // but changes  his mind then and sets it for keep again
 980       // - this makes sense as default when all Garbage dependencies
 981       //   are automatically marked for removal (as aptitude does).
 982       //   setting a package for keep then makes it no longer autoinstalled
 983       //   for all other use-case this action is rather suprising
 984    if(FromUser && !P.Marked)
 985      P.Flags &= ~Flag::Auto;
 986 #endif
 987
 988    if (DebugMarker == true)
 989       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 990
 991    RemoveSizes(Pkg);
 992    RemoveStates(Pkg);
 993
 994    P.Mode = ModeKeep;
 995    if (Pkg->CurrentVer == 0)
 996       P.InstallVer = 0;
 997    else
 998       P.InstallVer = Pkg.CurrentVer();
 999
1000    AddStates(Pkg);
1001
1002    Update(Pkg);
1003
1004    AddSizes(Pkg);
1005 }
1006                                                                         /*}}}*/
1007 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
1008 // ---------------------------------------------------------------------
1009 /* */
1010 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
1011                              unsigned long Depth, bool FromUser)
1012 {
1013    // Simplifies other routines.
1014    if (Pkg.end() == true)
1015       return;
1016
1017    ActionGroup group(*this);
1018
1019    // Check that it is not already marked for delete
1020    StateCache &P = PkgState[Pkg->ID];
1021    P.iFlags &= ~(AutoKept | Purge);
1022    if (rPurge == true)
1023       P.iFlags |= Purge;
1024
1025    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
1026        (Pkg.Purge() == true || rPurge == false))
1027       return;
1028
1029    // We dont even try to delete virtual packages..
1030    if (Pkg->VersionList == 0)
1031       return;
1032
1033    // check if we are allowed to install the package
1034    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
1035       return;
1036
1037    if (DebugMarker == true)
1038       std::clog << OutputInDepth(Depth) << "MarkDelete " << Pkg << " FU=" << FromUser << std::endl;
1039
1040    RemoveSizes(Pkg);
1041    RemoveStates(Pkg);
1042
1043    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
1044       P.Mode = ModeKeep;
1045    else
1046       P.Mode = ModeDelete;
1047    P.InstallVer = 0;
1048
1049    AddStates(Pkg);
1050    Update(Pkg);
1051    AddSizes(Pkg);
1052
1053    // if we remove the pseudo package, we also need to remove the "real"
1054    if (Pkg->CurrentVer != 0 && Pkg.CurrentVer().Pseudo() == true)
1055       MarkDelete(Pkg.Group().FindPkg("all"), rPurge, Depth+1, FromUser);
1056 }
1057                                                                         /*}}}*/
1058 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
1059 // ---------------------------------------------------------------------
1060 /* The default implementation just honors dpkg hold
1061    But an application using this library can override this method
1062    to control the MarkDelete behaviour */
1063 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
1064                               unsigned long Depth, bool FromUser)
1065 {
1066    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1067    {
1068       if (DebugMarker == true)
1069          std::clog << OutputInDepth(Depth) << "Hold prevents MarkDelete of " << Pkg << " FU=" << FromUser << std::endl;
1070       return false;
1071    }
1072    return true;
1073 }
1074                                                                         /*}}}*/
1075 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
1076 // ---------------------------------------------------------------------
1077 /* */
1078 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
1079                               unsigned long Depth, bool FromUser,
1080                               bool ForceImportantDeps)
1081 {
1082    if (Depth > 100)
1083       return;
1084
1085    // Simplifies other routines.
1086    if (Pkg.end() == true)
1087       return;
1088
1089    ActionGroup group(*this);
1090
1091    /* Check that it is not already marked for install and that it can be
1092       installed */
1093    StateCache &P = PkgState[Pkg->ID];
1094    P.iFlags &= ~AutoKept;
1095    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1096        (P.Mode == ModeInstall ||
1097         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1098    {
1099       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1100          MarkKeep(Pkg, false, FromUser, Depth+1);
1101       return;
1102    }
1103
1104    // See if there is even any possible instalation candidate
1105    if (P.CandidateVer == 0)
1106       return;
1107    // We dont even try to install virtual packages..
1108    if (Pkg->VersionList == 0)
1109       return;
1110
1111    // check if we are allowed to install the package
1112    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1113       return;
1114
1115    /* Target the candidate version and remove the autoflag. We reset the
1116       autoflag below if this was called recursively. Otherwise the user
1117       should have the ability to de-auto a package by changing its state */
1118    RemoveSizes(Pkg);
1119    RemoveStates(Pkg);
1120
1121    P.Mode = ModeInstall;
1122    P.InstallVer = P.CandidateVer;
1123
1124    if(FromUser)
1125      {
1126        // Set it to manual if it's a new install or cancelling the
1127        // removal of a garbage package.
1128        if(P.Status == 2 || (!Pkg.CurrentVer().end() && !P.Marked))
1129          P.Flags &= ~Flag::Auto;
1130      }
1131    else
1132      {
1133        // Set it to auto if this is a new install.
1134        if(P.Status == 2)
1135          P.Flags |= Flag::Auto;
1136      }
1137    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1138       P.Mode = ModeKeep;
1139
1140    AddStates(Pkg);
1141    Update(Pkg);
1142    AddSizes(Pkg);
1143
1144    if (AutoInst == false)
1145       return;
1146
1147    if (DebugMarker == true)
1148       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1149
1150    DepIterator Dep = P.InstVerIter(*this).DependsList();
1151    for (; Dep.end() != true;)
1152    {
1153       // Grok or groups
1154       DepIterator Start = Dep;
1155       bool Result = true;
1156       unsigned Ors = 0;
1157       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
1158       {
1159          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1160
1161          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1162             Result = false;
1163       }
1164
1165       // Dep is satisfied okay.
1166       if (Result == false)
1167          continue;
1168
1169       /* Check if this dep should be consider for install. If it is a user
1170          defined important dep and we are installed a new package then
1171          it will be installed. Otherwise we only check for important
1172          deps that have changed from the installed version
1173       */
1174       if (IsImportantDep(Start) == false)
1175          continue;
1176
1177       /* Check if any ImportantDep() (but not Critical) were added
1178        * since we installed the package.  Also check for deps that
1179        * were satisfied in the past: for instance, if a version
1180        * restriction in a Recommends was tightened, upgrading the
1181        * package should follow that Recommends rather than causing the
1182        * dependency to be removed. (bug #470115)
1183        */
1184       bool isNewImportantDep = false;
1185       bool isPreviouslySatisfiedImportantDep = false;
1186       if(!ForceImportantDeps && !Start.IsCritical())
1187       {
1188          bool found=false;
1189          VerIterator instVer = Pkg.CurrentVer();
1190          if(!instVer.end())
1191          {
1192            for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
1193              {
1194                //FIXME: deal better with or-groups(?)
1195                DepIterator LocalStart = D;
1196
1197                if(IsImportantDep(D) && !D.IsCritical() &&
1198                   Start.TargetPkg() == D.TargetPkg())
1199                  {
1200                    if(!isPreviouslySatisfiedImportantDep)
1201                      {
1202                        DepIterator D2 = D;
1203                        while((D2->CompareOp & Dep::Or) != 0)
1204                          ++D2;
1205
1206                        isPreviouslySatisfiedImportantDep =
1207                          (((*this)[D2] & DepGNow) != 0);
1208                      }
1209
1210                    found=true;
1211                  }
1212              }
1213             // this is a new dep if it was not found to be already
1214             // a important dep of the installed pacakge
1215             isNewImportantDep = !found;
1216          }
1217       }
1218       if(isNewImportantDep)
1219          if(DebugAutoInstall == true)
1220             std::clog << OutputInDepth(Depth) << "new important dependency: "
1221                       << Start.TargetPkg().Name() << std::endl;
1222       if(isPreviouslySatisfiedImportantDep)
1223         if(DebugAutoInstall == true)
1224           std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1225                     << Start.TargetPkg().Name() << std::endl;
1226
1227       // skip important deps if the package is already installed
1228       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
1229           && !isNewImportantDep && !isPreviouslySatisfiedImportantDep
1230           && !ForceImportantDeps)
1231          continue;
1232
1233       /* If we are in an or group locate the first or that can
1234          succeed. We have already cached this.. */
1235       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
1236          Start++;
1237
1238       /* This bit is for processing the possibilty of an install/upgrade
1239          fixing the problem */
1240       SPtrArray<Version *> List = Start.AllTargets();
1241       if (Start->Type != Dep::DpkgBreaks &&
1242           (DepState[Start->ID] & DepCVer) == DepCVer)
1243       {
1244          // Right, find the best version to install..
1245          Version **Cur = List;
1246          PkgIterator P = Start.TargetPkg();
1247          PkgIterator InstPkg(*Cache,0);
1248
1249          // See if there are direct matches (at the start of the list)
1250          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
1251          {
1252             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1253             if (PkgState[Pkg->ID].CandidateVer != *Cur)
1254                continue;
1255             InstPkg = Pkg;
1256             break;
1257          }
1258
1259          // Select the highest priority providing package
1260          if (InstPkg.end() == true)
1261          {
1262             pkgPrioSortList(*Cache,Cur);
1263             for (; *Cur != 0; Cur++)
1264             {
1265                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1266                if (PkgState[Pkg->ID].CandidateVer != *Cur)
1267                   continue;
1268                InstPkg = Pkg;
1269                break;
1270             }
1271          }
1272
1273          if (InstPkg.end() == false)
1274          {
1275             if(DebugAutoInstall == true)
1276                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1277                          << " as " << Start.DepType() << " of " << Pkg.Name()
1278                          << std::endl;
1279             // now check if we should consider it a automatic dependency or not
1280             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1281             {
1282                if(DebugAutoInstall == true)
1283                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1284                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1285                MarkInstall(InstPkg,true,Depth + 1, true);
1286             }
1287             else
1288             {
1289                // mark automatic dependency
1290                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1291                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1292                if (P->CurrentVer == 0)
1293                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1294             }
1295          }
1296          continue;
1297       }
1298
1299       /* For conflicts we just de-install the package and mark as auto,
1300          Conflicts may not have or groups.  For dpkg's Breaks we try to
1301          upgrade the package. */
1302       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
1303           Start->Type == Dep::DpkgBreaks)
1304       {
1305          for (Version **I = List; *I != 0; I++)
1306          {
1307             VerIterator Ver(*this,*I);
1308             PkgIterator Pkg = Ver.ParentPkg();
1309
1310             if (Start->Type != Dep::DpkgBreaks)
1311                MarkDelete(Pkg,false,Depth + 1, false);
1312             else if (PkgState[Pkg->ID].CandidateVer != *I)
1313                MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1314          }
1315          continue;
1316       }
1317    }
1318 }
1319                                                                         /*}}}*/
1320 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1321 // ---------------------------------------------------------------------
1322 /* The default implementation just honors dpkg hold
1323    But an application using this library can override this method
1324    to control the MarkInstall behaviour */
1325 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1326                               unsigned long Depth, bool FromUser)
1327 {
1328    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1329    {
1330       if (DebugMarker == true)
1331          std::clog << OutputInDepth(Depth) << "Hold prevents MarkInstall of " << Pkg << " FU=" << FromUser << std::endl;
1332       return false;
1333    }
1334    return true;
1335 }
1336                                                                         /*}}}*/
1337 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1338 // ---------------------------------------------------------------------
1339 /* */
1340 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1341 {
1342    ActionGroup group(*this);
1343
1344    RemoveSizes(Pkg);
1345    RemoveStates(Pkg);
1346
1347    StateCache &P = PkgState[Pkg->ID];
1348    if (To == true)
1349       P.iFlags |= ReInstall;
1350    else
1351       P.iFlags &= ~ReInstall;
1352
1353    AddStates(Pkg);
1354    AddSizes(Pkg);
1355 }
1356                                                                         /*}}}*/
1357 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1358 // ---------------------------------------------------------------------
1359 /* */
1360 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1361 {
1362    ActionGroup group(*this);
1363
1364    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1365    StateCache &P = PkgState[Pkg->ID];
1366
1367    RemoveSizes(Pkg);
1368    RemoveStates(Pkg);
1369
1370    if (P.CandidateVer == P.InstallVer)
1371       P.InstallVer = (Version *)TargetVer;
1372    P.CandidateVer = (Version *)TargetVer;
1373    P.Update(Pkg,*this);
1374
1375    AddStates(Pkg);
1376    Update(Pkg);
1377    AddSizes(Pkg);
1378 }
1379
1380 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1381 {
1382   StateCache &state = PkgState[Pkg->ID];
1383
1384   ActionGroup group(*this);
1385
1386   if(Auto)
1387     state.Flags |= Flag::Auto;
1388   else
1389     state.Flags &= ~Flag::Auto;
1390 }
1391                                                                         /*}}}*/
1392 // StateCache::Update - Compute the various static display things       /*{{{*/
1393 // ---------------------------------------------------------------------
1394 /* This is called whenever the Candidate version changes. */
1395 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1396 {
1397    // Some info
1398    VerIterator Ver = CandidateVerIter(Cache);
1399
1400    // Use a null string or the version string
1401    if (Ver.end() == true)
1402       CandVersion = "";
1403    else
1404       CandVersion = Ver.VerStr();
1405
1406    // Find the current version
1407    CurVersion = "";
1408    if (Pkg->CurrentVer != 0)
1409       CurVersion = Pkg.CurrentVer().VerStr();
1410
1411    // Strip off the epochs for display
1412    CurVersion = StripEpoch(CurVersion);
1413    CandVersion = StripEpoch(CandVersion);
1414
1415    // Figure out if its up or down or equal
1416    Status = Ver.CompareVer(Pkg.CurrentVer());
1417    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1418      Status = 2;
1419 }
1420                                                                         /*}}}*/
1421 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1422 // ---------------------------------------------------------------------
1423 /* */
1424 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1425 {
1426    if (Ver == 0)
1427       return 0;
1428
1429    // Strip any epoch
1430    for (const char *I = Ver; *I != 0; I++)
1431       if (*I == ':')
1432          return I + 1;
1433    return Ver;
1434 }
1435                                                                         /*}}}*/
1436 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1437 // ---------------------------------------------------------------------
1438 /* The default just returns the highest available version that is not
1439    a source and automatic. */
1440 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1441 {
1442    /* Not source/not automatic versions cannot be a candidate version
1443       unless they are already installed */
1444    VerIterator Last(*(pkgCache *)this,0);
1445
1446    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1447    {
1448       if (Pkg.CurrentVer() == I)
1449          return I;
1450
1451       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1452       {
1453          if ((J.File()->Flags & Flag::NotSource) != 0)
1454             continue;
1455
1456          /* Stash the highest version of a not-automatic source, we use it
1457             if there is nothing better */
1458          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1459          {
1460             if (Last.end() == true)
1461                Last = I;
1462             continue;
1463          }
1464
1465          return I;
1466       }
1467    }
1468
1469    return Last;
1470 }
1471                                                                         /*}}}*/
1472 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1473 // ---------------------------------------------------------------------
1474 /* */
1475 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1476 {
1477    if(Dep.IsCritical())
1478       return true;
1479    else if(Dep->Type == pkgCache::Dep::Recommends)
1480    {
1481       if ( _config->FindB("APT::Install-Recommends", false))
1482          return true;
1483       // we suport a special mode to only install-recommends for certain
1484       // sections
1485       // FIXME: this is a meant as a temporarly solution until the
1486       //        recommends are cleaned up
1487       const char *sec = Dep.ParentVer().Section();
1488       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1489          return true;
1490    }
1491    else if(Dep->Type == pkgCache::Dep::Suggests)
1492      return _config->FindB("APT::Install-Suggests", false);
1493
1494    return false;
1495 }
1496                                                                         /*}}}*/
1497 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()                   /*{{{*/
1498   : constructedSuccessfully(false)
1499 {
1500   Configuration::Item const *Opts;
1501   Opts = _config->Tree("APT::NeverAutoRemove");
1502   if (Opts != 0 && Opts->Child != 0)
1503     {
1504       Opts = Opts->Child;
1505       for (; Opts != 0; Opts = Opts->Next)
1506         {
1507           if (Opts->Value.empty() == true)
1508             continue;
1509
1510           regex_t *p = new regex_t;
1511           if(regcomp(p,Opts->Value.c_str(),
1512                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1513             {
1514               regfree(p);
1515               delete p;
1516               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1517               return;
1518             }
1519
1520           rootSetRegexp.push_back(p);
1521         }
1522     }
1523
1524   constructedSuccessfully = true;
1525 }
1526                                                                         /*}}}*/
1527 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()                  /*{{{*/
1528 {
1529   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1530     {
1531       regfree(rootSetRegexp[i]);
1532       delete rootSetRegexp[i];
1533     }
1534 }
1535                                                                         /*}}}*/
1536 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg) /*{{{*/
1537 {
1538    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1539       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1540          return true;
1541
1542    return false;
1543 }
1544                                                                         /*}}}*/
1545 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1546 {
1547   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1548   if(f->wasConstructedSuccessfully())
1549     return f;
1550   else
1551     {
1552       delete f;
1553       return NULL;
1554     }
1555 }
1556                                                                         /*}}}*/
1557 bool pkgDepCache::MarkFollowsRecommends()
1558 {
1559   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1560 }
1561
1562 bool pkgDepCache::MarkFollowsSuggests()
1563 {
1564   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1565 }
1566
1567 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1568 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1569 {
1570    bool follow_recommends;
1571    bool follow_suggests;
1572    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1573
1574    // init the states
1575    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1576    {
1577       PkgState[p->ID].Marked  = false;
1578       PkgState[p->ID].Garbage = false;
1579
1580       // debug output
1581       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1582          std::clog << "AutoDep: " << p.FullName() << std::endl;
1583    }
1584
1585    // init vars
1586    follow_recommends = MarkFollowsRecommends();
1587    follow_suggests   = MarkFollowsSuggests();
1588
1589
1590
1591    // do the mark part, this is the core bit of the algorithm
1592    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1593    {
1594       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1595           (p->Flags & Flag::Essential) ||
1596           userFunc.InRootSet(p))
1597
1598       {
1599          // the package is installed (and set to keep)
1600          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1601             MarkPackage(p, p.CurrentVer(),
1602                         follow_recommends, follow_suggests);
1603          // the package is to be installed
1604          else if(PkgState[p->ID].Install())
1605             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1606                         follow_recommends, follow_suggests);
1607       }
1608    }
1609
1610    return true;
1611 }
1612                                                                         /*}}}*/
1613 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1614 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1615                               const pkgCache::VerIterator &ver,
1616                               bool const &follow_recommends,
1617                               bool const &follow_suggests)
1618 {
1619    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1620
1621    // if we are marked already we are done
1622    if(state.Marked)
1623       return;
1624
1625    VerIterator const currver = pkg.CurrentVer();
1626    VerIterator const candver = state.CandidateVerIter(*this);
1627    VerIterator const instver = state.InstVerIter(*this);
1628
1629 #if 0
1630    // If a package was garbage-collected but is now being marked, we
1631    // should re-select it
1632    // For cases when a pkg is set to upgrade and this trigger the
1633    // removal of a no-longer used dependency.  if the pkg is set to
1634    // keep again later it will result in broken deps
1635    if(state.Delete() && state.RemoveReason = Unused)
1636    {
1637       if(ver==candver)
1638          mark_install(pkg, false, false, NULL);
1639       else if(ver==pkg.CurrentVer())
1640          MarkKeep(pkg, false, false);
1641
1642       instver=state.InstVerIter(*this);
1643    }
1644 #endif
1645
1646    // For packages that are not going to be removed, ignore versions
1647    // other than the InstVer.  For packages that are going to be
1648    // removed, ignore versions other than the current version.
1649    if(!(ver == instver && !instver.end()) &&
1650       !(ver == currver && instver.end() && !ver.end()))
1651       return;
1652
1653    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1654
1655    if(debug_autoremove)
1656      {
1657        std::clog << "Marking: " << pkg.FullName();
1658        if(!ver.end())
1659          std::clog << " " << ver.VerStr();
1660        if(!currver.end())
1661          std::clog << ", Curr=" << currver.VerStr();
1662        if(!instver.end())
1663          std::clog << ", Inst=" << instver.VerStr();
1664        std::clog << std::endl;
1665      }
1666
1667    state.Marked=true;
1668
1669    if(ver.end() == true)
1670       return;
1671
1672    // If the version belongs to a Multi-Arch all package
1673    // we will mark all others in this Group with this version also
1674    // Beware: We compare versions here the lazy way: string comparision
1675    // this is bad if multiple repositories provide different versions
1676    // of the package with an identical version number - but even in this
1677    // case the dependencies are likely the same.
1678    if (ver->MultiArch == pkgCache::Version::All &&
1679         strcmp(ver.Arch(true), "all") == 0)
1680    {
1681       GrpIterator G = pkg.Group();
1682       const char* const VerStr = ver.VerStr();
1683       for (PkgIterator P = G.FindPkg("any");
1684            P.end() != true; P = G.NextPkg(P))
1685       {
1686          for (VerIterator V = P.VersionList();
1687               V.end() != true; ++V)
1688          {
1689             if (strcmp(VerStr, V.VerStr()) != 0)
1690                continue;
1691             MarkPackage(P, V, follow_recommends, follow_suggests);
1692             break;
1693          }
1694       }
1695    }
1696
1697      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1698      {
1699         if(d->Type == Dep::Depends ||
1700            d->Type == Dep::PreDepends ||
1701            (follow_recommends &&
1702             d->Type == Dep::Recommends) ||
1703            (follow_suggests &&
1704             d->Type == Dep::Suggests))
1705         {
1706            // Try all versions of this package.
1707            for(VerIterator V = d.TargetPkg().VersionList();
1708                !V.end(); ++V)
1709            {
1710               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1711               {
1712                 if(debug_autoremove)
1713                   {
1714                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1715                               << " " << d.ParentVer().VerStr() << " "
1716                               << d.DepType() << " " << d.TargetPkg().FullName();
1717                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1718                       {
1719                         std::clog << " (" << d.CompType() << " "
1720                                   << d.TargetVer() << ")";
1721                       }
1722                     std::clog << std::endl;
1723                   }
1724                  MarkPackage(V.ParentPkg(), V,
1725                              follow_recommends, follow_suggests);
1726               }
1727            }
1728            // Now try virtual packages
1729            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1730                !prv.end(); ++prv)
1731            {
1732               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1733                                        d.TargetVer()))
1734               {
1735                 if(debug_autoremove)
1736                   {
1737                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1738                               << d.ParentVer().VerStr() << " "
1739                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1740                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1741                       {
1742                         std::clog << " (" << d.CompType() << " "
1743                                   << d.TargetVer() << ")";
1744                       }
1745                     std::clog << ", provided by "
1746                               << prv.OwnerPkg().FullName() << " "
1747                               << prv.OwnerVer().VerStr()
1748                               << std::endl;
1749                   }
1750
1751                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1752                              follow_recommends, follow_suggests);
1753               }
1754            }
1755         }
1756      }
1757 }
1758                                                                         /*}}}*/
1759 bool pkgDepCache::Sweep()                                               /*{{{*/
1760 {
1761    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1762
1763    // do the sweep
1764    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1765    {
1766      StateCache &state=PkgState[p->ID];
1767
1768      // skip required packages
1769      if (!p.CurrentVer().end() &&
1770          (p.CurrentVer()->Priority == pkgCache::State::Required))
1771         continue;
1772
1773      // if it is not marked and it is installed, it's garbage
1774      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1775      {
1776         state.Garbage=true;
1777         if(debug_autoremove)
1778            std::cout << "Garbage: " << p.FullName() << std::endl;
1779      }
1780   }
1781
1782    return true;
1783 }
1784                                                                         /*}}}*/