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