apt-pkg/depcache.cc

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