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