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->FindFile("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::clog << "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->FindFile("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       while(recheck.empty() == false)
 808          for (std::set<unsigned long>::const_iterator p = recheck.begin();
 809              p != recheck.end(); ++p) {
 810             if (Prog != 0 && Done%20 == 0)
 811                Prog->Progress(Done);
 812             PkgIterator P = PkgIterator(*Cache, Cache->PkgP + *p);
 813             if (RemovePseudoInstalledPkg(P, recheck) == true) {
 814                ++killed;
 815                ++Done;
 816             }
 817             recheck.erase(p);
 818          }
 819
 820       /* Okay, we have killed a great amount of pseudopackages -
 821          we have killed so many that we have now arch "all" packages
 822          without an installed pseudo package, but we NEED an installed
 823          pseudo package, so we will search now for a pseudo package
 824          we can install without breaking everything. */
 825       for (GrpIterator G = Cache->GrpBegin(); G.end() != true; ++G)
 826       {
 827          PkgIterator P = G.FindPkg("all");
 828          if (P.end() == true)
 829             continue;
 830          if (P->CurrentVer == 0)
 831             continue;
 832          bool installed = false;
 833          for (P = G.FindPkg("any"); P.end() != true; P = G.NextPkg(P))
 834          {
 835             if (strcmp(P.Arch(), "all") == 0)
 836                continue;
 837             if (P->CurrentVer == 0)
 838                continue;
 839             installed = true;
 840             break;
 841          }
 842          if (installed == false)
 843             recheck.insert(G.Index());
 844       }
 845
 846       while (recheck.empty() != true)
 847       {
 848          std::set<unsigned long>::const_iterator g = recheck.begin();
 849          unsigned long const G = *g;
 850          recheck.erase(g);
 851          if (unlikely(ReInstallPseudoForGroup(G, recheck) == false))
 852             _error->Warning(_("Internal error, group '%s' has no installable pseudo package"), GrpIterator(*Cache, Cache->GrpP + *g).Name());
 853       }
 854    }
 855
 856    if (Prog != 0)
 857       Prog->Progress(Done);
 858
 859    readStateFile(Prog);
 860 }
 861                                                                         /*}}}*/
 862 // DepCache::ReInstallPseudoForGroup - MultiArch helper for Update()    /*{{{*/
 863 // ---------------------------------------------------------------------
 864 /* RemovePseudoInstalledPkg() is very successful. It even kills packages
 865    to an amount that no pseudo package is left, but we need a pseudo package
 866    for upgrading senarios so we need to reinstall one pseudopackage which
 867    doesn't break everything. Thankfully we can't have architecture depending
 868    negative dependencies so this problem is already eliminated */
 869 bool pkgDepCache::ReInstallPseudoForGroup(pkgCache::PkgIterator const &P, std::set<unsigned long> &recheck)
 870 {
 871    if (P->CurrentVer != 0)
 872       return true;
 873    // recursive call for packages which provide this package
 874    for (pkgCache::PrvIterator Prv = P.ProvidesList(); Prv.end() != true; ++Prv)
 875       ReInstallPseudoForGroup(Prv.OwnerPkg(), recheck);
 876    // check if we actually need to look at this group
 877    unsigned long const G = P->Group;
 878    std::set<unsigned long>::const_iterator Pi = recheck.find(G);
 879    if (Pi == recheck.end())
 880       return true;
 881    recheck.erase(Pi); // remove here, so we can't fall into an endless loop
 882    if (unlikely(ReInstallPseudoForGroup(G, recheck) == false))
 883    {
 884       recheck.insert(G);
 885       return false;
 886    }
 887    return true;
 888 }
 889 bool pkgDepCache::ReInstallPseudoForGroup(unsigned long const &G, std::set<unsigned long> &recheck)
 890 {
 891    std::vector<std::string> static const Archs = APT::Configuration::getArchitectures();
 892    pkgCache::GrpIterator Grp(*Cache, Cache->GrpP + G);
 893    if (unlikely(Grp.end() == true))
 894       return false;
 895    for (std::vector<std::string>::const_iterator a = Archs.begin();
 896         a != Archs.end(); ++a)
 897    {
 898       pkgCache::PkgIterator P = Grp.FindPkg(*a);
 899       if (P.end() == true)
 900          continue;
 901       pkgCache::VerIterator allV = Grp.FindPkg("all").CurrentVer();
 902       for (VerIterator V = P.VersionList(); V.end() != true; ++V)
 903       {
 904          // search for the same version as the all package
 905          if (allV->Hash != V->Hash || strcmp(allV.VerStr(),V.VerStr()) != 0)
 906             continue;
 907          unsigned char const CurDepState = VersionState(V.DependsList(),DepInstall,DepInstMin,DepInstPolicy);
 908          // If it is broken, try to install dependencies first before retry
 909          if ((CurDepState & DepInstMin) != DepInstMin)
 910          {
 911             for (pkgCache::DepIterator D = V.DependsList(); D.end() != true; ++D)
 912             {
 913                if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends)
 914                   continue;
 915                ReInstallPseudoForGroup(D.TargetPkg(), recheck);
 916             }
 917             unsigned char const CurDepState = VersionState(V.DependsList(),DepInstall,DepInstMin,DepInstPolicy);
 918             // if package ist still broken… try another arch
 919             if ((CurDepState & DepInstMin) != DepInstMin)
 920                break;
 921          }
 922          // dependencies satisfied: reinstall the package
 923          RemoveSizes(P);
 924          RemoveStates(P);
 925          P->CurrentVer = V.Index();
 926          PkgState[P->ID].InstallVer = V;
 927          AddStates(P);
 928          Update(P);
 929          AddSizes(P);
 930          return true;
 931       }
 932    }
 933    return false;
 934 }
 935                                                                         /*}}}*/
 936 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 937 // ---------------------------------------------------------------------
 938 /* This is a helper for update that only does the dep portion of the scan.
 939    It is mainly meant to scan reverse dependencies. */
 940 void pkgDepCache::Update(DepIterator D)
 941 {
 942    // Update the reverse deps
 943    for (;D.end() != true; D++)
 944    {
 945       unsigned char &State = DepState[D->ID];
 946       State = DependencyState(D);
 947
 948       // Invert for Conflicts
 949       if (D->Type == Dep::Conflicts ||
 950           D->Type == Dep::DpkgBreaks ||
 951           D->Type == Dep::Obsoletes)
 952          State = ~State;
 953
 954       RemoveStates(D.ParentPkg());
 955       BuildGroupOrs(D.ParentVer());
 956       UpdateVerState(D.ParentPkg());
 957       AddStates(D.ParentPkg());
 958    }
 959 }
 960                                                                         /*}}}*/
 961 // DepCache::Update - Update the related deps of a package              /*{{{*/
 962 // ---------------------------------------------------------------------
 963 /* This is called whenever the state of a package changes. It updates
 964    all cached dependencies related to this package. */
 965 void pkgDepCache::Update(PkgIterator const &Pkg)
 966 {
 967    // Recompute the dep of the package
 968    RemoveStates(Pkg);
 969    UpdateVerState(Pkg);
 970    AddStates(Pkg);
 971
 972    // Update the reverse deps
 973    Update(Pkg.RevDependsList());
 974
 975    // Update the provides map for the current ver
 976    if (Pkg->CurrentVer != 0)
 977       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 978            P.end() != true; P++)
 979          Update(P.ParentPkg().RevDependsList());
 980
 981    // Update the provides map for the candidate ver
 982    if (PkgState[Pkg->ID].CandidateVer != 0)
 983       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 984            P.end() != true; P++)
 985          Update(P.ParentPkg().RevDependsList());
 986 }
 987                                                                         /*}}}*/
 988 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 989 // ---------------------------------------------------------------------
 990 /* */
 991 void pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 992                            unsigned long Depth)
 993 {
 994    // Simplifies other routines.
 995    if (Pkg.end() == true)
 996       return;
 997
 998    /* Reject an attempt to keep a non-source broken installed package, those
 999       must be upgraded */
1000    if (Pkg.State() == PkgIterator::NeedsUnpack &&
1001        Pkg.CurrentVer().Downloadable() == false)
1002       return;
1003
1004    /** \todo Can this be moved later in the method? */
1005    ActionGroup group(*this);
1006
1007    /* We changed the soft state all the time so the UI is a bit nicer
1008       to use */
1009    StateCache &P = PkgState[Pkg->ID];
1010    if (Soft == true)
1011       P.iFlags |= AutoKept;
1012    else
1013       P.iFlags &= ~AutoKept;
1014
1015    // Check that it is not already kept
1016    if (P.Mode == ModeKeep)
1017       return;
1018
1019    // We dont even try to keep virtual packages..
1020    if (Pkg->VersionList == 0)
1021       return;
1022 #if 0 // reseting the autoflag here means we lose the
1023       // auto-mark information if a user selects a package for removal
1024       // but changes  his mind then and sets it for keep again
1025       // - this makes sense as default when all Garbage dependencies
1026       //   are automatically marked for removal (as aptitude does).
1027       //   setting a package for keep then makes it no longer autoinstalled
1028       //   for all other use-case this action is rather suprising
1029    if(FromUser && !P.Marked)
1030      P.Flags &= ~Flag::Auto;
1031 #endif
1032
1033    if (DebugMarker == true)
1034       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
1035
1036    RemoveSizes(Pkg);
1037    RemoveStates(Pkg);
1038
1039    P.Mode = ModeKeep;
1040    if (Pkg->CurrentVer == 0)
1041       P.InstallVer = 0;
1042    else
1043       P.InstallVer = Pkg.CurrentVer();
1044
1045    AddStates(Pkg);
1046
1047    Update(Pkg);
1048
1049    AddSizes(Pkg);
1050 }
1051                                                                         /*}}}*/
1052 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
1053 // ---------------------------------------------------------------------
1054 /* */
1055 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
1056                              unsigned long Depth, bool FromUser)
1057 {
1058    // Simplifies other routines.
1059    if (Pkg.end() == true)
1060       return;
1061
1062    ActionGroup group(*this);
1063
1064    // Check that it is not already marked for delete
1065    StateCache &P = PkgState[Pkg->ID];
1066    P.iFlags &= ~(AutoKept | Purge);
1067    if (rPurge == true)
1068       P.iFlags |= Purge;
1069
1070    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
1071        (Pkg.Purge() == true || rPurge == false))
1072       return;
1073
1074    // We dont even try to delete virtual packages..
1075    if (Pkg->VersionList == 0)
1076       return;
1077
1078    // check if we are allowed to install the package
1079    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
1080       return;
1081
1082    if (DebugMarker == true)
1083       std::clog << OutputInDepth(Depth) << "MarkDelete " << Pkg << " FU=" << FromUser << std::endl;
1084
1085    RemoveSizes(Pkg);
1086    RemoveStates(Pkg);
1087
1088    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
1089       P.Mode = ModeKeep;
1090    else
1091       P.Mode = ModeDelete;
1092    P.InstallVer = 0;
1093
1094    AddStates(Pkg);
1095    Update(Pkg);
1096    AddSizes(Pkg);
1097
1098    // if we remove the pseudo package, we also need to remove the "real"
1099    if (Pkg->CurrentVer != 0 && Pkg.CurrentVer().Pseudo() == true)
1100       MarkDelete(Pkg.Group().FindPkg("all"), rPurge, Depth+1, FromUser);
1101 }
1102                                                                         /*}}}*/
1103 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
1104 // ---------------------------------------------------------------------
1105 /* The default implementation just honors dpkg hold
1106    But an application using this library can override this method
1107    to control the MarkDelete behaviour */
1108 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
1109                               unsigned long Depth, bool FromUser)
1110 {
1111    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1112    {
1113       if (DebugMarker == true)
1114          std::clog << OutputInDepth(Depth) << "Hold prevents MarkDelete of " << Pkg << " FU=" << FromUser << std::endl;
1115       return false;
1116    }
1117    return true;
1118 }
1119                                                                         /*}}}*/
1120 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
1121 // ---------------------------------------------------------------------
1122 /* */
1123 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
1124                               unsigned long Depth, bool FromUser,
1125                               bool ForceImportantDeps)
1126 {
1127    if (Depth > 100)
1128       return;
1129
1130    // Simplifies other routines.
1131    if (Pkg.end() == true)
1132       return;
1133
1134    ActionGroup group(*this);
1135
1136    /* Check that it is not already marked for install and that it can be
1137       installed */
1138    StateCache &P = PkgState[Pkg->ID];
1139    P.iFlags &= ~AutoKept;
1140    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1141        (P.Mode == ModeInstall ||
1142         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1143    {
1144       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1145          MarkKeep(Pkg, false, FromUser, Depth+1);
1146       return;
1147    }
1148
1149    // See if there is even any possible instalation candidate
1150    if (P.CandidateVer == 0)
1151       return;
1152    // We dont even try to install virtual packages..
1153    if (Pkg->VersionList == 0)
1154       return;
1155
1156    // check if we are allowed to install the package
1157    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1158       return;
1159
1160    /* Target the candidate version and remove the autoflag. We reset the
1161       autoflag below if this was called recursively. Otherwise the user
1162       should have the ability to de-auto a package by changing its state */
1163    RemoveSizes(Pkg);
1164    RemoveStates(Pkg);
1165
1166    P.Mode = ModeInstall;
1167    P.InstallVer = P.CandidateVer;
1168
1169    if(FromUser)
1170      {
1171        // Set it to manual if it's a new install or cancelling the
1172        // removal of a garbage package.
1173        if(P.Status == 2 || (!Pkg.CurrentVer().end() && !P.Marked))
1174          P.Flags &= ~Flag::Auto;
1175      }
1176    else
1177      {
1178        // Set it to auto if this is a new install.
1179        if(P.Status == 2)
1180          P.Flags |= Flag::Auto;
1181      }
1182    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1183       P.Mode = ModeKeep;
1184
1185    AddStates(Pkg);
1186    Update(Pkg);
1187    AddSizes(Pkg);
1188
1189    if (AutoInst == false)
1190       return;
1191
1192    if (DebugMarker == true)
1193       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1194
1195    DepIterator Dep = P.InstVerIter(*this).DependsList();
1196    for (; Dep.end() != true;)
1197    {
1198       // Grok or groups
1199       DepIterator Start = Dep;
1200       bool Result = true;
1201       unsigned Ors = 0;
1202       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
1203       {
1204          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1205
1206          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1207             Result = false;
1208       }
1209
1210       // Dep is satisfied okay.
1211       if (Result == false)
1212          continue;
1213
1214       /* Check if this dep should be consider for install. If it is a user
1215          defined important dep and we are installed a new package then
1216          it will be installed. Otherwise we only check for important
1217          deps that have changed from the installed version
1218       */
1219       if (IsImportantDep(Start) == false)
1220          continue;
1221
1222       /* Check if any ImportantDep() (but not Critical) were added
1223        * since we installed the package.  Also check for deps that
1224        * were satisfied in the past: for instance, if a version
1225        * restriction in a Recommends was tightened, upgrading the
1226        * package should follow that Recommends rather than causing the
1227        * dependency to be removed. (bug #470115)
1228        */
1229       bool isNewImportantDep = false;
1230       bool isPreviouslySatisfiedImportantDep = false;
1231       if(!ForceImportantDeps && !Start.IsCritical())
1232       {
1233          bool found=false;
1234          VerIterator instVer = Pkg.CurrentVer();
1235          if(!instVer.end())
1236          {
1237            for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
1238              {
1239                //FIXME: deal better with or-groups(?)
1240                DepIterator LocalStart = D;
1241
1242                if(IsImportantDep(D) && !D.IsCritical() &&
1243                   Start.TargetPkg() == D.TargetPkg())
1244                  {
1245                    if(!isPreviouslySatisfiedImportantDep)
1246                      {
1247                        DepIterator D2 = D;
1248                        while((D2->CompareOp & Dep::Or) != 0)
1249                          ++D2;
1250
1251                        isPreviouslySatisfiedImportantDep =
1252                          (((*this)[D2] & DepGNow) != 0);
1253                      }
1254
1255                    found=true;
1256                  }
1257              }
1258             // this is a new dep if it was not found to be already
1259             // a important dep of the installed pacakge
1260             isNewImportantDep = !found;
1261          }
1262       }
1263       if(isNewImportantDep)
1264          if(DebugAutoInstall == true)
1265             std::clog << OutputInDepth(Depth) << "new important dependency: "
1266                       << Start.TargetPkg().Name() << std::endl;
1267       if(isPreviouslySatisfiedImportantDep)
1268         if(DebugAutoInstall == true)
1269           std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1270                     << Start.TargetPkg().Name() << std::endl;
1271
1272       // skip important deps if the package is already installed
1273       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
1274           && !isNewImportantDep && !isPreviouslySatisfiedImportantDep
1275           && !ForceImportantDeps)
1276          continue;
1277
1278       /* If we are in an or group locate the first or that can
1279          succeed. We have already cached this.. */
1280       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
1281          Start++;
1282
1283       /* This bit is for processing the possibilty of an install/upgrade
1284          fixing the problem */
1285       SPtrArray<Version *> List = Start.AllTargets();
1286       if (Start->Type != Dep::DpkgBreaks &&
1287           (DepState[Start->ID] & DepCVer) == DepCVer)
1288       {
1289          // Right, find the best version to install..
1290          Version **Cur = List;
1291          PkgIterator P = Start.TargetPkg();
1292          PkgIterator InstPkg(*Cache,0);
1293
1294          // See if there are direct matches (at the start of the list)
1295          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
1296          {
1297             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1298             if (PkgState[Pkg->ID].CandidateVer != *Cur)
1299                continue;
1300             InstPkg = Pkg;
1301             break;
1302          }
1303
1304          // Select the highest priority providing package
1305          if (InstPkg.end() == true)
1306          {
1307             pkgPrioSortList(*Cache,Cur);
1308             for (; *Cur != 0; Cur++)
1309             {
1310                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1311                if (PkgState[Pkg->ID].CandidateVer != *Cur)
1312                   continue;
1313                InstPkg = Pkg;
1314                break;
1315             }
1316          }
1317
1318          if (InstPkg.end() == false)
1319          {
1320             if(DebugAutoInstall == true)
1321                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1322                          << " as " << Start.DepType() << " of " << Pkg.Name()
1323                          << std::endl;
1324             // now check if we should consider it a automatic dependency or not
1325             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1326             {
1327                if(DebugAutoInstall == true)
1328                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1329                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1330                MarkInstall(InstPkg,true,Depth + 1, true);
1331             }
1332             else
1333             {
1334                // mark automatic dependency
1335                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1336                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1337                if (P->CurrentVer == 0)
1338                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1339             }
1340          }
1341          continue;
1342       }
1343
1344       /* For conflicts we just de-install the package and mark as auto,
1345          Conflicts may not have or groups.  For dpkg's Breaks we try to
1346          upgrade the package. */
1347       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
1348           Start->Type == Dep::DpkgBreaks)
1349       {
1350          for (Version **I = List; *I != 0; I++)
1351          {
1352             VerIterator Ver(*this,*I);
1353             PkgIterator Pkg = Ver.ParentPkg();
1354
1355             if (Start->Type != Dep::DpkgBreaks)
1356                MarkDelete(Pkg,false,Depth + 1, false);
1357             else if (PkgState[Pkg->ID].CandidateVer != *I)
1358                MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1359          }
1360          continue;
1361       }
1362    }
1363 }
1364                                                                         /*}}}*/
1365 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1366 // ---------------------------------------------------------------------
1367 /* The default implementation just honors dpkg hold
1368    But an application using this library can override this method
1369    to control the MarkInstall behaviour */
1370 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1371                               unsigned long Depth, bool FromUser)
1372 {
1373    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1374    {
1375       if (DebugMarker == true)
1376          std::clog << OutputInDepth(Depth) << "Hold prevents MarkInstall of " << Pkg << " FU=" << FromUser << std::endl;
1377       return false;
1378    }
1379    return true;
1380 }
1381                                                                         /*}}}*/
1382 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1383 // ---------------------------------------------------------------------
1384 /* */
1385 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1386 {
1387    ActionGroup group(*this);
1388
1389    RemoveSizes(Pkg);
1390    RemoveStates(Pkg);
1391
1392    StateCache &P = PkgState[Pkg->ID];
1393    if (To == true)
1394       P.iFlags |= ReInstall;
1395    else
1396       P.iFlags &= ~ReInstall;
1397
1398    AddStates(Pkg);
1399    AddSizes(Pkg);
1400 }
1401                                                                         /*}}}*/
1402 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1403 // ---------------------------------------------------------------------
1404 /* */
1405 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1406 {
1407    ActionGroup group(*this);
1408
1409    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1410    StateCache &P = PkgState[Pkg->ID];
1411
1412    RemoveSizes(Pkg);
1413    RemoveStates(Pkg);
1414
1415    if (P.CandidateVer == P.InstallVer)
1416       P.InstallVer = (Version *)TargetVer;
1417    P.CandidateVer = (Version *)TargetVer;
1418    P.Update(Pkg,*this);
1419
1420    AddStates(Pkg);
1421    Update(Pkg);
1422    AddSizes(Pkg);
1423 }
1424
1425 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1426 {
1427   StateCache &state = PkgState[Pkg->ID];
1428
1429   ActionGroup group(*this);
1430
1431   if(Auto)
1432     state.Flags |= Flag::Auto;
1433   else
1434     state.Flags &= ~Flag::Auto;
1435 }
1436                                                                         /*}}}*/
1437 // StateCache::Update - Compute the various static display things       /*{{{*/
1438 // ---------------------------------------------------------------------
1439 /* This is called whenever the Candidate version changes. */
1440 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1441 {
1442    // Some info
1443    VerIterator Ver = CandidateVerIter(Cache);
1444
1445    // Use a null string or the version string
1446    if (Ver.end() == true)
1447       CandVersion = "";
1448    else
1449       CandVersion = Ver.VerStr();
1450
1451    // Find the current version
1452    CurVersion = "";
1453    if (Pkg->CurrentVer != 0)
1454       CurVersion = Pkg.CurrentVer().VerStr();
1455
1456    // Strip off the epochs for display
1457    CurVersion = StripEpoch(CurVersion);
1458    CandVersion = StripEpoch(CandVersion);
1459
1460    // Figure out if its up or down or equal
1461    Status = Ver.CompareVer(Pkg.CurrentVer());
1462    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1463      Status = 2;
1464 }
1465                                                                         /*}}}*/
1466 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1467 // ---------------------------------------------------------------------
1468 /* */
1469 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1470 {
1471    if (Ver == 0)
1472       return 0;
1473
1474    // Strip any epoch
1475    for (const char *I = Ver; *I != 0; I++)
1476       if (*I == ':')
1477          return I + 1;
1478    return Ver;
1479 }
1480                                                                         /*}}}*/
1481 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1482 // ---------------------------------------------------------------------
1483 /* The default just returns the highest available version that is not
1484    a source and automatic. */
1485 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1486 {
1487    /* Not source/not automatic versions cannot be a candidate version
1488       unless they are already installed */
1489    VerIterator Last(*(pkgCache *)this,0);
1490
1491    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1492    {
1493       if (Pkg.CurrentVer() == I)
1494          return I;
1495
1496       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1497       {
1498          if ((J.File()->Flags & Flag::NotSource) != 0)
1499             continue;
1500
1501          /* Stash the highest version of a not-automatic source, we use it
1502             if there is nothing better */
1503          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1504          {
1505             if (Last.end() == true)
1506                Last = I;
1507             continue;
1508          }
1509
1510          return I;
1511       }
1512    }
1513
1514    return Last;
1515 }
1516                                                                         /*}}}*/
1517 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1518 // ---------------------------------------------------------------------
1519 /* */
1520 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1521 {
1522    if(Dep.IsCritical())
1523       return true;
1524    else if(Dep->Type == pkgCache::Dep::Recommends)
1525    {
1526       if ( _config->FindB("APT::Install-Recommends", false))
1527          return true;
1528       // we suport a special mode to only install-recommends for certain
1529       // sections
1530       // FIXME: this is a meant as a temporarly solution until the
1531       //        recommends are cleaned up
1532       const char *sec = Dep.ParentVer().Section();
1533       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1534          return true;
1535    }
1536    else if(Dep->Type == pkgCache::Dep::Suggests)
1537      return _config->FindB("APT::Install-Suggests", false);
1538
1539    return false;
1540 }
1541                                                                         /*}}}*/
1542 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()                   /*{{{*/
1543   : constructedSuccessfully(false)
1544 {
1545   Configuration::Item const *Opts;
1546   Opts = _config->Tree("APT::NeverAutoRemove");
1547   if (Opts != 0 && Opts->Child != 0)
1548     {
1549       Opts = Opts->Child;
1550       for (; Opts != 0; Opts = Opts->Next)
1551         {
1552           if (Opts->Value.empty() == true)
1553             continue;
1554
1555           regex_t *p = new regex_t;
1556           if(regcomp(p,Opts->Value.c_str(),
1557                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1558             {
1559               regfree(p);
1560               delete p;
1561               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1562               return;
1563             }
1564
1565           rootSetRegexp.push_back(p);
1566         }
1567     }
1568
1569   constructedSuccessfully = true;
1570 }
1571                                                                         /*}}}*/
1572 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()                  /*{{{*/
1573 {
1574   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1575     {
1576       regfree(rootSetRegexp[i]);
1577       delete rootSetRegexp[i];
1578     }
1579 }
1580                                                                         /*}}}*/
1581 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg) /*{{{*/
1582 {
1583    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1584       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1585          return true;
1586
1587    return false;
1588 }
1589                                                                         /*}}}*/
1590 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1591 {
1592   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1593   if(f->wasConstructedSuccessfully())
1594     return f;
1595   else
1596     {
1597       delete f;
1598       return NULL;
1599     }
1600 }
1601                                                                         /*}}}*/
1602 bool pkgDepCache::MarkFollowsRecommends()
1603 {
1604   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1605 }
1606
1607 bool pkgDepCache::MarkFollowsSuggests()
1608 {
1609   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1610 }
1611
1612 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1613 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1614 {
1615    bool follow_recommends;
1616    bool follow_suggests;
1617    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1618
1619    // init the states
1620    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1621    {
1622       PkgState[p->ID].Marked  = false;
1623       PkgState[p->ID].Garbage = false;
1624
1625       // debug output
1626       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1627          std::clog << "AutoDep: " << p.FullName() << std::endl;
1628    }
1629
1630    // init vars
1631    follow_recommends = MarkFollowsRecommends();
1632    follow_suggests   = MarkFollowsSuggests();
1633
1634
1635
1636    // do the mark part, this is the core bit of the algorithm
1637    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1638    {
1639       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1640           (p->Flags & Flag::Essential) ||
1641           userFunc.InRootSet(p) ||
1642           // be nice even then a required package violates the policy (#583517)
1643           // and do the full mark process also for required packages
1644           (p.CurrentVer().end() != true &&
1645            p.CurrentVer()->Priority == pkgCache::State::Required))
1646       {
1647          // the package is installed (and set to keep)
1648          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1649             MarkPackage(p, p.CurrentVer(),
1650                         follow_recommends, follow_suggests);
1651          // the package is to be installed
1652          else if(PkgState[p->ID].Install())
1653             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1654                         follow_recommends, follow_suggests);
1655       }
1656    }
1657
1658    return true;
1659 }
1660                                                                         /*}}}*/
1661 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1662 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1663                               const pkgCache::VerIterator &ver,
1664                               bool const &follow_recommends,
1665                               bool const &follow_suggests)
1666 {
1667    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1668
1669    // if we are marked already we are done
1670    if(state.Marked)
1671       return;
1672
1673    VerIterator const currver = pkg.CurrentVer();
1674    VerIterator const candver = state.CandidateVerIter(*this);
1675    VerIterator const instver = state.InstVerIter(*this);
1676
1677 #if 0
1678    // If a package was garbage-collected but is now being marked, we
1679    // should re-select it
1680    // For cases when a pkg is set to upgrade and this trigger the
1681    // removal of a no-longer used dependency.  if the pkg is set to
1682    // keep again later it will result in broken deps
1683    if(state.Delete() && state.RemoveReason = Unused)
1684    {
1685       if(ver==candver)
1686          mark_install(pkg, false, false, NULL);
1687       else if(ver==pkg.CurrentVer())
1688          MarkKeep(pkg, false, false);
1689
1690       instver=state.InstVerIter(*this);
1691    }
1692 #endif
1693
1694    // For packages that are not going to be removed, ignore versions
1695    // other than the InstVer.  For packages that are going to be
1696    // removed, ignore versions other than the current version.
1697    if(!(ver == instver && !instver.end()) &&
1698       !(ver == currver && instver.end() && !ver.end()))
1699       return;
1700
1701    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1702
1703    if(debug_autoremove)
1704      {
1705        std::clog << "Marking: " << pkg.FullName();
1706        if(!ver.end())
1707          std::clog << " " << ver.VerStr();
1708        if(!currver.end())
1709          std::clog << ", Curr=" << currver.VerStr();
1710        if(!instver.end())
1711          std::clog << ", Inst=" << instver.VerStr();
1712        std::clog << std::endl;
1713      }
1714
1715    state.Marked=true;
1716
1717    if(ver.end() == true)
1718       return;
1719
1720    // If the version belongs to a Multi-Arch all package
1721    // we will mark all others in this Group with this version also
1722    if (ver->MultiArch == pkgCache::Version::All &&
1723         strcmp(ver.Arch(true), "all") == 0)
1724    {
1725       GrpIterator G = pkg.Group();
1726       const char* const VerStr = ver.VerStr();
1727       for (PkgIterator P = G.FindPkg("any");
1728            P.end() != true; P = G.NextPkg(P))
1729       {
1730          for (VerIterator V = P.VersionList();
1731               V.end() != true; ++V)
1732          {
1733             if (ver->Hash != V->Hash ||
1734                 strcmp(VerStr, V.VerStr()) != 0)
1735                continue;
1736             MarkPackage(P, V, follow_recommends, follow_suggests);
1737             break;
1738          }
1739       }
1740    }
1741
1742      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1743      {
1744         if(d->Type == Dep::Depends ||
1745            d->Type == Dep::PreDepends ||
1746            (follow_recommends &&
1747             d->Type == Dep::Recommends) ||
1748            (follow_suggests &&
1749             d->Type == Dep::Suggests))
1750         {
1751            // Try all versions of this package.
1752            for(VerIterator V = d.TargetPkg().VersionList();
1753                !V.end(); ++V)
1754            {
1755               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1756               {
1757                 if(debug_autoremove)
1758                   {
1759                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1760                               << " " << d.ParentVer().VerStr() << " "
1761                               << d.DepType() << " " << d.TargetPkg().FullName();
1762                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1763                       {
1764                         std::clog << " (" << d.CompType() << " "
1765                                   << d.TargetVer() << ")";
1766                       }
1767                     std::clog << std::endl;
1768                   }
1769                  MarkPackage(V.ParentPkg(), V,
1770                              follow_recommends, follow_suggests);
1771               }
1772            }
1773            // Now try virtual packages
1774            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1775                !prv.end(); ++prv)
1776            {
1777               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1778                                        d.TargetVer()))
1779               {
1780                 if(debug_autoremove)
1781                   {
1782                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1783                               << d.ParentVer().VerStr() << " "
1784                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1785                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1786                       {
1787                         std::clog << " (" << d.CompType() << " "
1788                                   << d.TargetVer() << ")";
1789                       }
1790                     std::clog << ", provided by "
1791                               << prv.OwnerPkg().FullName() << " "
1792                               << prv.OwnerVer().VerStr()
1793                               << std::endl;
1794                   }
1795
1796                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1797                              follow_recommends, follow_suggests);
1798               }
1799            }
1800         }
1801      }
1802 }
1803                                                                         /*}}}*/
1804 bool pkgDepCache::Sweep()                                               /*{{{*/
1805 {
1806    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1807
1808    // do the sweep
1809    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1810    {
1811      StateCache &state=PkgState[p->ID];
1812
1813      // skip required packages
1814      if (!p.CurrentVer().end() &&
1815          (p.CurrentVer()->Priority == pkgCache::State::Required))
1816         continue;
1817
1818      // if it is not marked and it is installed, it's garbage
1819      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1820      {
1821         state.Garbage=true;
1822         if(debug_autoremove)
1823            std::clog << "Garbage: " << p.FullName() << std::endl;
1824      }
1825   }
1826
1827    return true;
1828 }
1829                                                                         /*}}}*/