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