apt-pkg/pkgcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: pkgcache.cc,v 1.37 2003/02/10 01:40:58 doogie Exp $
   4 /* ######################################################################
   5
   6    Package Cache - Accessor code for the cache
   7
   8    Please see doc/apt-pkg/cache.sgml for a more detailed description of
   9    this format. Also be sure to keep that file up-to-date!!
  10
  11    This is the general utility functions for cache management. They provide
  12    a complete set of accessor functions for the cache. The cacheiterators
  13    header contains the STL-like iterators that can be used to easially
  14    navigate the cache as well as seemlessly dereference the mmap'd
  15    indexes. Use these always.
  16
  17    The main class provides for ways to get package indexes and some
  18    general lookup functions to start the iterators.
  19
  20    ##################################################################### */
  21                                                                         /*}}}*/
  22 // Include Files                                                        /*{{{*/
  23 #include<config.h>
  24
  25 #include <apt-pkg/pkgcache.h>
  26 #include <apt-pkg/policy.h>
  27 #include <apt-pkg/version.h>
  28 #include <apt-pkg/error.h>
  29 #include <apt-pkg/strutl.h>
  30 #include <apt-pkg/configuration.h>
  31 #include <apt-pkg/aptconfiguration.h>
  32 #include <apt-pkg/mmap.h>
  33 #include <apt-pkg/macros.h>
  34
  35 #include <stddef.h>
  36 #include <string.h>
  37 #include <ostream>
  38 #include <vector>
  39 #include <string>
  40 #include <sys/stat.h>
  41
  42 #include <apti18n.h>
  43                                                                         /*}}}*/
  44
  45 using std::string;
  46
  47
  48 // Cache::Header::Header - Constructor                                  /*{{{*/
  49 // ---------------------------------------------------------------------
  50 /* Simply initialize the header */
  51 pkgCache::Header::Header()
  52 {
  53    Signature = 0x98FE76DC;
  54
  55    /* Whenever the structures change the major version should be bumped,
  56       whenever the generator changes the minor version should be bumped. */
  57    MajorVersion = 8;
  58 #if (APT_PKG_MAJOR >= 4 && APT_PKG_MINOR >= 13)
  59    MinorVersion = 2;
  60 #else
  61    MinorVersion = 1;
  62 #endif
  63    Dirty = false;
  64
  65    HeaderSz = sizeof(pkgCache::Header);
  66    GroupSz = sizeof(pkgCache::Group);
  67    PackageSz = sizeof(pkgCache::Package);
  68    PackageFileSz = sizeof(pkgCache::PackageFile);
  69    VersionSz = sizeof(pkgCache::Version);
  70    DescriptionSz = sizeof(pkgCache::Description);
  71    DependencySz = sizeof(pkgCache::Dependency);
  72    ProvidesSz = sizeof(pkgCache::Provides);
  73    VerFileSz = sizeof(pkgCache::VerFile);
  74    DescFileSz = sizeof(pkgCache::DescFile);
  75
  76    GroupCount = 0;
  77    PackageCount = 0;
  78    VersionCount = 0;
  79    DescriptionCount = 0;
  80    DependsCount = 0;
  81    PackageFileCount = 0;
  82    VerFileCount = 0;
  83    DescFileCount = 0;
  84    ProvidesCount = 0;
  85    MaxVerFileSize = 0;
  86    MaxDescFileSize = 0;
  87
  88    FileList = 0;
  89    StringList = 0;
  90    VerSysName = 0;
  91    Architecture = 0;
  92    memset(PkgHashTable,0,sizeof(PkgHashTable));
  93    memset(GrpHashTable,0,sizeof(GrpHashTable));
  94    memset(Pools,0,sizeof(Pools));
  95
  96    CacheFileSize = 0;
  97 }
  98                                                                         /*}}}*/
  99 // Cache::Header::CheckSizes - Check if the two headers have same *sz   /*{{{*/
 100 // ---------------------------------------------------------------------
 101 /* */
 102 bool pkgCache::Header::CheckSizes(Header &Against) const
 103 {
 104    if (HeaderSz == Against.HeaderSz &&
 105        GroupSz == Against.GroupSz &&
 106        PackageSz == Against.PackageSz &&
 107        PackageFileSz == Against.PackageFileSz &&
 108        VersionSz == Against.VersionSz &&
 109        DescriptionSz == Against.DescriptionSz &&
 110        DependencySz == Against.DependencySz &&
 111        VerFileSz == Against.VerFileSz &&
 112        DescFileSz == Against.DescFileSz &&
 113        ProvidesSz == Against.ProvidesSz)
 114       return true;
 115    return false;
 116 }
 117                                                                         /*}}}*/
 118
 119 // Cache::pkgCache - Constructor                                        /*{{{*/
 120 // ---------------------------------------------------------------------
 121 /* */
 122 pkgCache::pkgCache(MMap *Map, bool DoMap) : Map(*Map)
 123 {
 124    // call getArchitectures() with cached=false to ensure that the
 125    // architectures cache is re-evaulated. this is needed in cases
 126    // when the APT::Architecture field changes between two cache creations
 127    MultiArchEnabled = APT::Configuration::getArchitectures(false).size() > 1;
 128    if (DoMap == true)
 129       ReMap();
 130 }
 131                                                                         /*}}}*/
 132 // Cache::ReMap - Reopen the cache file                                 /*{{{*/
 133 // ---------------------------------------------------------------------
 134 /* If the file is already closed then this will open it open it. */
 135 bool pkgCache::ReMap(bool const &Errorchecks)
 136 {
 137    // Apply the typecasts.
 138    HeaderP = (Header *)Map.Data();
 139    GrpP = (Group *)Map.Data();
 140    PkgP = (Package *)Map.Data();
 141    VerFileP = (VerFile *)Map.Data();
 142    DescFileP = (DescFile *)Map.Data();
 143    PkgFileP = (PackageFile *)Map.Data();
 144    VerP = (Version *)Map.Data();
 145    DescP = (Description *)Map.Data();
 146    ProvideP = (Provides *)Map.Data();
 147    DepP = (Dependency *)Map.Data();
 148    StringItemP = (StringItem *)Map.Data();
 149    StrP = (char *)Map.Data();
 150
 151    if (Errorchecks == false)
 152       return true;
 153
 154    if (Map.Size() == 0 || HeaderP == 0)
 155       return _error->Error(_("Empty package cache"));
 156
 157    // Check the header
 158    Header DefHeader;
 159    if (HeaderP->Signature != DefHeader.Signature ||
 160        HeaderP->Dirty == true)
 161       return _error->Error(_("The package cache file is corrupted"));
 162
 163    if (HeaderP->MajorVersion != DefHeader.MajorVersion ||
 164        HeaderP->MinorVersion != DefHeader.MinorVersion ||
 165        HeaderP->CheckSizes(DefHeader) == false)
 166       return _error->Error(_("The package cache file is an incompatible version"));
 167
 168    if (Map.Size() < HeaderP->CacheFileSize)
 169       return _error->Error(_("The package cache file is corrupted, it is too small"));
 170
 171    // Locate our VS..
 172    if (HeaderP->VerSysName == 0 ||
 173        (VS = pkgVersioningSystem::GetVS(StrP + HeaderP->VerSysName)) == 0)
 174       return _error->Error(_("This APT does not support the versioning system '%s'"),StrP + HeaderP->VerSysName);
 175
 176    // Chcek the arhcitecture
 177    if (HeaderP->Architecture == 0 ||
 178        _config->Find("APT::Architecture") != StrP + HeaderP->Architecture)
 179       return _error->Error(_("The package cache was built for a different architecture"));
 180    return true;
 181 }
 182                                                                         /*}}}*/
 183 // Cache::Hash - Hash a string                                          /*{{{*/
 184 // ---------------------------------------------------------------------
 185 /* This is used to generate the hash entries for the HashTable. With my
 186    package list from bo this function gets 94% table usage on a 512 item
 187    table (480 used items) */
 188 unsigned long pkgCache::sHash(const string &Str) const
 189 {
 190    unsigned long Hash = 0;
 191    for (string::const_iterator I = Str.begin(); I != Str.end(); ++I)
 192       Hash = 41 * Hash + tolower_ascii(*I);
 193    return Hash % _count(HeaderP->PkgHashTable);
 194 }
 195
 196 unsigned long pkgCache::sHash(const char *Str) const
 197 {
 198    unsigned long Hash = tolower_ascii(*Str);
 199    for (const char *I = Str + 1; *I != 0; ++I)
 200       Hash = 41 * Hash + tolower_ascii(*I);
 201    return Hash % _count(HeaderP->PkgHashTable);
 202 }
 203                                                                         /*}}}*/
 204 // Cache::SingleArchFindPkg - Locate a package by name                  /*{{{*/
 205 // ---------------------------------------------------------------------
 206 /* Returns 0 on error, pointer to the package otherwise
 207    The multiArch enabled methods will fallback to this one as it is (a bit)
 208    faster for single arch environments and realworld is mostly singlearch… */
 209 pkgCache::PkgIterator pkgCache::SingleArchFindPkg(const string &Name)
 210 {
 211    // Look at the hash bucket
 212    Package *Pkg = PkgP + HeaderP->PkgHashTable[Hash(Name)];
 213    for (; Pkg != PkgP; Pkg = PkgP + Pkg->NextPackage)
 214    {
 215       if (unlikely(Pkg->Name == 0))
 216          continue;
 217
 218       int const cmp = strcasecmp(Name.c_str(), StrP + Pkg->Name);
 219       if (cmp == 0)
 220          return PkgIterator(*this, Pkg);
 221       else if (cmp < 0)
 222          break;
 223    }
 224    return PkgIterator(*this,0);
 225 }
 226                                                                         /*}}}*/
 227 // Cache::FindPkg - Locate a package by name                            /*{{{*/
 228 // ---------------------------------------------------------------------
 229 /* Returns 0 on error, pointer to the package otherwise */
 230 pkgCache::PkgIterator pkgCache::FindPkg(const string &Name) {
 231         size_t const found = Name.find(':');
 232         if (found == string::npos)
 233         {
 234                 if (MultiArchCache() == false)
 235                         return SingleArchFindPkg(Name);
 236                 else
 237                         return FindPkg(Name, "native");
 238         }
 239         string const Arch = Name.substr(found+1);
 240         /* Beware: This is specialcased to handle pkg:any in dependencies as
 241            these are linked to virtual pkg:any named packages with all archs.
 242            If you want any arch from a given pkg, use FindPkg(pkg,arch) */
 243         if (Arch == "any")
 244                 return FindPkg(Name, "any");
 245         return FindPkg(Name.substr(0, found), Arch);
 246 }
 247                                                                         /*}}}*/
 248 // Cache::FindPkg - Locate a package by name                            /*{{{*/
 249 // ---------------------------------------------------------------------
 250 /* Returns 0 on error, pointer to the package otherwise */
 251 pkgCache::PkgIterator pkgCache::FindPkg(const string &Name, string const &Arch) {
 252         if (MultiArchCache() == false && Arch != "none") {
 253                 if (Arch == "native" || Arch == "all" || Arch == "any" ||
 254                     Arch == NativeArch())
 255                         return SingleArchFindPkg(Name);
 256                 else
 257                         return PkgIterator(*this,0);
 258         }
 259         /* We make a detour via the GrpIterator here as
 260            on a multi-arch environment a group is easier to
 261            find than a package (less entries in the buckets) */
 262         pkgCache::GrpIterator Grp = FindGrp(Name);
 263         if (Grp.end() == true)
 264                 return PkgIterator(*this,0);
 265
 266         return Grp.FindPkg(Arch);
 267 }
 268                                                                         /*}}}*/
 269 // Cache::FindGrp - Locate a group by name                              /*{{{*/
 270 // ---------------------------------------------------------------------
 271 /* Returns End-Pointer on error, pointer to the group otherwise */
 272 pkgCache::GrpIterator pkgCache::FindGrp(const string &Name) {
 273         if (unlikely(Name.empty() == true))
 274                 return GrpIterator(*this,0);
 275
 276         // Look at the hash bucket for the group
 277         Group *Grp = GrpP + HeaderP->GrpHashTable[sHash(Name)];
 278         for (; Grp != GrpP; Grp = GrpP + Grp->Next) {
 279                 if (unlikely(Grp->Name == 0))
 280                    continue;
 281
 282                 int const cmp = strcasecmp(Name.c_str(), StrP + Grp->Name);
 283                 if (cmp == 0)
 284                         return GrpIterator(*this, Grp);
 285                 else if (cmp < 0)
 286                         break;
 287         }
 288
 289         return GrpIterator(*this,0);
 290 }
 291                                                                         /*}}}*/
 292 // Cache::CompTypeDeb - Return a string describing the compare type     /*{{{*/
 293 // ---------------------------------------------------------------------
 294 /* This returns a string representation of the dependency compare
 295    type in the weird debian style.. */
 296 const char *pkgCache::CompTypeDeb(unsigned char Comp)
 297 {
 298    const char * const Ops[] = {"","<=",">=","<<",">>","=","!="};
 299    if (unlikely((unsigned)(Comp & 0xF) >= sizeof(Ops)/sizeof(Ops[0])))
 300       return "";
 301    return Ops[Comp & 0xF];
 302 }
 303                                                                         /*}}}*/
 304 // Cache::CompType - Return a string describing the compare type        /*{{{*/
 305 // ---------------------------------------------------------------------
 306 /* This returns a string representation of the dependency compare
 307    type */
 308 const char *pkgCache::CompType(unsigned char Comp)
 309 {
 310    const char * const Ops[] = {"","<=",">=","<",">","=","!="};
 311    if (unlikely((unsigned)(Comp & 0xF) >= sizeof(Ops)/sizeof(Ops[0])))
 312       return "";
 313    return Ops[Comp & 0xF];
 314 }
 315                                                                         /*}}}*/
 316 // Cache::DepType - Return a string describing the dep type             /*{{{*/
 317 // ---------------------------------------------------------------------
 318 /* */
 319 const char *pkgCache::DepType(unsigned char Type)
 320 {
 321    const char *Types[] = {"",_("Depends"),_("PreDepends"),_("Suggests"),
 322                           _("Recommends"),_("Conflicts"),_("Replaces"),
 323                           _("Obsoletes"),_("Breaks"), _("Enhances")};
 324    if (Type < sizeof(Types)/sizeof(*Types))
 325       return Types[Type];
 326    return "";
 327 }
 328                                                                         /*}}}*/
 329 // Cache::Priority - Convert a priority value to a string               /*{{{*/
 330 // ---------------------------------------------------------------------
 331 /* */
 332 const char *pkgCache::Priority(unsigned char Prio)
 333 {
 334    const char *Mapping[] = {0,_("important"),_("required"),_("standard"),
 335                             _("optional"),_("extra")};
 336    if (Prio < _count(Mapping))
 337       return Mapping[Prio];
 338    return 0;
 339 }
 340                                                                         /*}}}*/
 341 // GrpIterator::FindPkg - Locate a package by arch                      /*{{{*/
 342 // ---------------------------------------------------------------------
 343 /* Returns an End-Pointer on error, pointer to the package otherwise */
 344 pkgCache::PkgIterator pkgCache::GrpIterator::FindPkg(string Arch) const {
 345         if (unlikely(IsGood() == false || S->FirstPackage == 0))
 346                 return PkgIterator(*Owner, 0);
 347
 348         /* If we accept any package we simply return the "first"
 349            package in this group (the last one added). */
 350         if (Arch == "any")
 351                 return PkgIterator(*Owner, Owner->PkgP + S->FirstPackage);
 352
 353         char const* const myArch = Owner->NativeArch();
 354         /* Most of the time the package for our native architecture is
 355            the one we add at first to the cache, but this would be the
 356            last one we check, so we do it now. */
 357         if (Arch == "native" || Arch == myArch || Arch == "all") {
 358                 pkgCache::Package *Pkg = Owner->PkgP + S->LastPackage;
 359                 if (strcasecmp(myArch, Owner->StrP + Pkg->Arch) == 0)
 360                         return PkgIterator(*Owner, Pkg);
 361                 Arch = myArch;
 362         }
 363
 364         /* Iterate over the list to find the matching arch
 365            unfortunately this list includes "package noise"
 366            (= different packages with same calculated hash),
 367            so we need to check the name also */
 368         for (pkgCache::Package *Pkg = PackageList(); Pkg != Owner->PkgP;
 369              Pkg = Owner->PkgP + Pkg->NextPackage) {
 370                 if (S->Name == Pkg->Name &&
 371                     stringcasecmp(Arch, Owner->StrP + Pkg->Arch) == 0)
 372                         return PkgIterator(*Owner, Pkg);
 373                 if ((Owner->PkgP + S->LastPackage) == Pkg)
 374                         break;
 375         }
 376
 377         return PkgIterator(*Owner, 0);
 378 }
 379                                                                         /*}}}*/
 380 // GrpIterator::FindPreferredPkg - Locate the "best" package            /*{{{*/
 381 // ---------------------------------------------------------------------
 382 /* Returns an End-Pointer on error, pointer to the package otherwise */
 383 pkgCache::PkgIterator pkgCache::GrpIterator::FindPreferredPkg(bool const &PreferNonVirtual) const {
 384         pkgCache::PkgIterator Pkg = FindPkg("native");
 385         if (Pkg.end() == false && (PreferNonVirtual == false || Pkg->VersionList != 0))
 386                 return Pkg;
 387
 388         std::vector<std::string> const archs = APT::Configuration::getArchitectures();
 389         for (std::vector<std::string>::const_iterator a = archs.begin();
 390              a != archs.end(); ++a) {
 391                 Pkg = FindPkg(*a);
 392                 if (Pkg.end() == false && (PreferNonVirtual == false || Pkg->VersionList != 0))
 393                         return Pkg;
 394         }
 395         // packages without an architecture
 396         Pkg = FindPkg("none");
 397         if (Pkg.end() == false && (PreferNonVirtual == false || Pkg->VersionList != 0))
 398                 return Pkg;
 399
 400         if (PreferNonVirtual == true)
 401                 return FindPreferredPkg(false);
 402         return PkgIterator(*Owner, 0);
 403 }
 404                                                                         /*}}}*/
 405 // GrpIterator::NextPkg - Locate the next package in the group          /*{{{*/
 406 // ---------------------------------------------------------------------
 407 /* Returns an End-Pointer on error, pointer to the package otherwise.
 408    We can't simply ++ to the next as the next package of the last will
 409    be from a different group (with the same hash value) */
 410 pkgCache::PkgIterator pkgCache::GrpIterator::NextPkg(pkgCache::PkgIterator const &LastPkg) const {
 411         if (unlikely(IsGood() == false || S->FirstPackage == 0 ||
 412             LastPkg.end() == true))
 413                 return PkgIterator(*Owner, 0);
 414
 415         if (S->LastPackage == LastPkg.Index())
 416                 return PkgIterator(*Owner, 0);
 417
 418         return PkgIterator(*Owner, Owner->PkgP + LastPkg->NextPackage);
 419 }
 420                                                                         /*}}}*/
 421 // GrpIterator::operator ++ - Postfix incr                              /*{{{*/
 422 // ---------------------------------------------------------------------
 423 /* This will advance to the next logical group in the hash table. */
 424 void pkgCache::GrpIterator::operator ++(int)
 425 {
 426    // Follow the current links
 427    if (S != Owner->GrpP)
 428       S = Owner->GrpP + S->Next;
 429
 430    // Follow the hash table
 431    while (S == Owner->GrpP && (HashIndex+1) < (signed)_count(Owner->HeaderP->GrpHashTable))
 432    {
 433       HashIndex++;
 434       S = Owner->GrpP + Owner->HeaderP->GrpHashTable[HashIndex];
 435    }
 436 }
 437                                                                         /*}}}*/
 438 // PkgIterator::operator ++ - Postfix incr                              /*{{{*/
 439 // ---------------------------------------------------------------------
 440 /* This will advance to the next logical package in the hash table. */
 441 void pkgCache::PkgIterator::operator ++(int)
 442 {
 443    // Follow the current links
 444    if (S != Owner->PkgP)
 445       S = Owner->PkgP + S->NextPackage;
 446
 447    // Follow the hash table
 448    while (S == Owner->PkgP && (HashIndex+1) < (signed)_count(Owner->HeaderP->PkgHashTable))
 449    {
 450       HashIndex++;
 451       S = Owner->PkgP + Owner->HeaderP->PkgHashTable[HashIndex];
 452    }
 453 }
 454                                                                         /*}}}*/
 455 // PkgIterator::State - Check the State of the package                  /*{{{*/
 456 // ---------------------------------------------------------------------
 457 /* By this we mean if it is either cleanly installed or cleanly removed. */
 458 pkgCache::PkgIterator::OkState pkgCache::PkgIterator::State() const
 459 {
 460    if (S->InstState == pkgCache::State::ReInstReq ||
 461        S->InstState == pkgCache::State::HoldReInstReq)
 462       return NeedsUnpack;
 463
 464    if (S->CurrentState == pkgCache::State::UnPacked ||
 465        S->CurrentState == pkgCache::State::HalfConfigured)
 466       // we leave triggers alone complettely. dpkg deals with
 467       // them in a hard-to-predict manner and if they get
 468       // resolved by dpkg before apt run dpkg --configure on
 469       // the TriggersPending package dpkg returns a error
 470       //Pkg->CurrentState == pkgCache::State::TriggersAwaited
 471       //Pkg->CurrentState == pkgCache::State::TriggersPending)
 472       return NeedsConfigure;
 473
 474    if (S->CurrentState == pkgCache::State::HalfInstalled ||
 475        S->InstState != pkgCache::State::Ok)
 476       return NeedsUnpack;
 477
 478    return NeedsNothing;
 479 }
 480                                                                         /*}}}*/
 481 // PkgIterator::CandVersion - Returns the candidate version string      /*{{{*/
 482 // ---------------------------------------------------------------------
 483 /* Return string representing of the candidate version. */
 484 const char *
 485 pkgCache::PkgIterator::CandVersion() const
 486 {
 487   //TargetVer is empty, so don't use it.
 488   VerIterator version = pkgPolicy(Owner).GetCandidateVer(*this);
 489   if (version.IsGood())
 490     return version.VerStr();
 491   return 0;
 492 }
 493                                                                         /*}}}*/
 494 // PkgIterator::CurVersion - Returns the current version string         /*{{{*/
 495 // ---------------------------------------------------------------------
 496 /* Return string representing of the current version. */
 497 const char *
 498 pkgCache::PkgIterator::CurVersion() const
 499 {
 500   VerIterator version = CurrentVer();
 501   if (version.IsGood())
 502     return CurrentVer().VerStr();
 503   return 0;
 504 }
 505                                                                         /*}}}*/
 506 // ostream operator to handle string representation of a package        /*{{{*/
 507 // ---------------------------------------------------------------------
 508 /* Output name < cur.rent.version -> candid.ate.version | new.est.version > (section)
 509    Note that the characters <|>() are all literal above. Versions will be omitted
 510    if they provide no new information (e.g. there is no newer version than candidate)
 511    If no version and/or section can be found "none" is used. */
 512 std::ostream&
 513 operator<<(std::ostream& out, pkgCache::PkgIterator Pkg)
 514 {
 515    if (Pkg.end() == true)
 516       return out << "invalid package";
 517
 518    string current = string(Pkg.CurVersion() == 0 ? "none" : Pkg.CurVersion());
 519    string candidate = string(Pkg.CandVersion() == 0 ? "none" : Pkg.CandVersion());
 520    string newest = string(Pkg.VersionList().end() ? "none" : Pkg.VersionList().VerStr());
 521
 522    out << Pkg.Name() << " [ " << Pkg.Arch() << " ] < " << current;
 523    if (current != candidate)
 524       out << " -> " << candidate;
 525    if ( newest != "none" && candidate != newest)
 526       out << " | " << newest;
 527    if (Pkg->VersionList == 0)
 528       out << " > ( none )";
 529    else
 530       out << " > ( " << string(Pkg.VersionList().Section()==0?"unknown":Pkg.VersionList().Section()) << " )";
 531    return out;
 532 }
 533                                                                         /*}}}*/
 534 // PkgIterator::FullName - Returns Name and (maybe) Architecture        /*{{{*/
 535 // ---------------------------------------------------------------------
 536 /* Returns a name:arch string */
 537 std::string pkgCache::PkgIterator::FullName(bool const &Pretty) const
 538 {
 539    string fullname = Name();
 540    if (Pretty == false ||
 541        (strcmp(Arch(), "all") != 0 &&
 542         strcmp(Owner->NativeArch(), Arch()) != 0))
 543       return fullname.append(":").append(Arch());
 544    return fullname;
 545 }
 546                                                                         /*}}}*/
 547 // DepIterator::IsCritical - Returns true if the dep is important       /*{{{*/
 548 // ---------------------------------------------------------------------
 549 /* Currently critical deps are defined as depends, predepends and
 550    conflicts (including dpkg's Breaks fields). */
 551 bool pkgCache::DepIterator::IsCritical() const
 552 {
 553    if (IsNegative() == true ||
 554        S->Type == pkgCache::Dep::Depends ||
 555        S->Type == pkgCache::Dep::PreDepends)
 556       return true;
 557    return false;
 558 }
 559                                                                         /*}}}*/
 560 // DepIterator::IsNegative - Returns true if the dep is a negative one  /*{{{*/
 561 // ---------------------------------------------------------------------
 562 /* Some dependencies are positive like Depends and Recommends, others
 563    are negative like Conflicts which can and should be handled differently */
 564 bool pkgCache::DepIterator::IsNegative() const
 565 {
 566    return S->Type == Dep::DpkgBreaks ||
 567           S->Type == Dep::Conflicts ||
 568           S->Type == Dep::Obsoletes;
 569 }
 570                                                                         /*}}}*/
 571 // DepIterator::SmartTargetPkg - Resolve dep target pointers w/provides /*{{{*/
 572 // ---------------------------------------------------------------------
 573 /* This intellegently looks at dep target packages and tries to figure
 574    out which package should be used. This is needed to nicely handle
 575    provide mapping. If the target package has no other providing packages
 576    then it returned. Otherwise the providing list is looked at to
 577    see if there is one one unique providing package if so it is returned.
 578    Otherwise true is returned and the target package is set. The return
 579    result indicates whether the node should be expandable
 580
 581    In Conjunction with the DepCache the value of Result may not be
 582    super-good since the policy may have made it uninstallable. Using
 583    AllTargets is better in this case. */
 584 bool pkgCache::DepIterator::SmartTargetPkg(PkgIterator &Result) const
 585 {
 586    Result = TargetPkg();
 587
 588    // No provides at all
 589    if (Result->ProvidesList == 0)
 590       return false;
 591
 592    // There is the Base package and the providing ones which is at least 2
 593    if (Result->VersionList != 0)
 594       return true;
 595
 596    /* We have to skip over indirect provisions of the package that
 597       owns the dependency. For instance, if libc5-dev depends on the
 598       virtual package libc-dev which is provided by libc5-dev and libc6-dev
 599       we must ignore libc5-dev when considering the provides list. */
 600    PrvIterator PStart = Result.ProvidesList();
 601    for (; PStart.end() != true && PStart.OwnerPkg() == ParentPkg(); ++PStart);
 602
 603    // Nothing but indirect self provides
 604    if (PStart.end() == true)
 605       return false;
 606
 607    // Check for single packages in the provides list
 608    PrvIterator P = PStart;
 609    for (; P.end() != true; ++P)
 610    {
 611       // Skip over self provides
 612       if (P.OwnerPkg() == ParentPkg())
 613          continue;
 614       if (PStart.OwnerPkg() != P.OwnerPkg())
 615          break;
 616    }
 617
 618    Result = PStart.OwnerPkg();
 619
 620    // Check for non dups
 621    if (P.end() != true)
 622       return true;
 623
 624    return false;
 625 }
 626                                                                         /*}}}*/
 627 // DepIterator::AllTargets - Returns the set of all possible targets    /*{{{*/
 628 // ---------------------------------------------------------------------
 629 /* This is a more useful version of TargetPkg() that follows versioned
 630    provides. It includes every possible package-version that could satisfy
 631    the dependency. The last item in the list has a 0. The resulting pointer
 632    must be delete [] 'd */
 633 pkgCache::Version **pkgCache::DepIterator::AllTargets() const
 634 {
 635    Version **Res = 0;
 636    unsigned long Size =0;
 637    while (1)
 638    {
 639       Version **End = Res;
 640       PkgIterator DPkg = TargetPkg();
 641
 642       // Walk along the actual package providing versions
 643       for (VerIterator I = DPkg.VersionList(); I.end() == false; ++I)
 644       {
 645          if (IsIgnorable(I.ParentPkg()) == true)
 646             continue;
 647          if (IsSatisfied(I) == false)
 648             continue;
 649
 650          Size++;
 651          if (Res != 0)
 652             *End++ = I;
 653       }
 654
 655       // Follow all provides
 656       for (PrvIterator I = DPkg.ProvidesList(); I.end() == false; ++I)
 657       {
 658          if (IsIgnorable(I) == true)
 659             continue;
 660          if (IsSatisfied(I) == false)
 661             continue;
 662
 663          Size++;
 664          if (Res != 0)
 665             *End++ = I.OwnerVer();
 666       }
 667
 668       // Do it again and write it into the array
 669       if (Res == 0)
 670       {
 671          Res = new Version *[Size+1];
 672          Size = 0;
 673       }
 674       else
 675       {
 676          *End = 0;
 677          break;
 678       }
 679    }
 680
 681    return Res;
 682 }
 683                                                                         /*}}}*/
 684 // DepIterator::GlobOr - Compute an OR group                            /*{{{*/
 685 // ---------------------------------------------------------------------
 686 /* This Takes an iterator, iterates past the current dependency grouping
 687    and returns Start and End so that so End is the final element
 688    in the group, if End == Start then D is End++ and End is the
 689    dependency D was pointing to. Use in loops to iterate sensibly. */
 690 void pkgCache::DepIterator::GlobOr(DepIterator &Start,DepIterator &End)
 691 {
 692    // Compute a single dependency element (glob or)
 693    Start = *this;
 694    End = *this;
 695    for (bool LastOR = true; end() == false && LastOR == true;)
 696    {
 697       LastOR = (S->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 698       (*this)++;
 699       if (LastOR == true)
 700          End = (*this);
 701    }
 702 }
 703                                                                         /*}}}*/
 704 // DepIterator::IsIgnorable - should this packag/providr be ignored?    /*{{{*/
 705 // ---------------------------------------------------------------------
 706 /* Deps like self-conflicts should be ignored as well as implicit conflicts
 707    on virtual packages. */
 708 bool pkgCache::DepIterator::IsIgnorable(PkgIterator const &/*Pkg*/) const
 709 {
 710    if (IsNegative() == false)
 711       return false;
 712
 713    pkgCache::PkgIterator PP = ParentPkg();
 714    pkgCache::PkgIterator PT = TargetPkg();
 715    if (PP->Group != PT->Group)
 716       return false;
 717    // self-conflict
 718    if (PP == PT)
 719       return true;
 720    pkgCache::VerIterator PV = ParentVer();
 721    // ignore group-conflict on a M-A:same package - but not our implicit dependencies
 722    // so that we can have M-A:same packages conflicting with their own real name
 723    if ((PV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 724    {
 725       // Replaces: ${self}:other ( << ${binary:Version})
 726       if (S->Type == pkgCache::Dep::Replaces && S->CompareOp == pkgCache::Dep::Less && strcmp(PV.VerStr(), TargetVer()) == 0)
 727          return false;
 728       // Breaks: ${self}:other (!= ${binary:Version})
 729       if (S->Type == pkgCache::Dep::DpkgBreaks && S->CompareOp == pkgCache::Dep::NotEquals && strcmp(PV.VerStr(), TargetVer()) == 0)
 730          return false;
 731       return true;
 732    }
 733
 734    return false;
 735 }
 736 bool pkgCache::DepIterator::IsIgnorable(PrvIterator const &Prv) const
 737 {
 738    if (IsNegative() == false)
 739       return false;
 740
 741    PkgIterator const Pkg = ParentPkg();
 742    /* Provides may never be applied against the same package (or group)
 743       if it is a conflicts. See the comment above. */
 744    if (Prv.OwnerPkg()->Group == Pkg->Group)
 745       return true;
 746    // Implicit group-conflicts should not be applied on providers of other groups
 747    if (Pkg->Group == TargetPkg()->Group && Prv.OwnerPkg()->Group != Pkg->Group)
 748       return true;
 749
 750    return false;
 751 }
 752                                                                         /*}}}*/
 753 // DepIterator::IsMultiArchImplicit - added by the cache generation     /*{{{*/
 754 // ---------------------------------------------------------------------
 755 /* MultiArch can be translated to SingleArch for an resolver and we did so,
 756    by adding dependencies to help the resolver understand the problem, but
 757    sometimes it is needed to identify these to ignore them… */
 758 bool pkgCache::DepIterator::IsMultiArchImplicit() const
 759 {
 760    if (ParentPkg()->Arch != TargetPkg()->Arch &&
 761        (S->Type == pkgCache::Dep::Replaces ||
 762         S->Type == pkgCache::Dep::DpkgBreaks ||
 763         S->Type == pkgCache::Dep::Conflicts))
 764       return true;
 765    return false;
 766 }
 767                                                                         /*}}}*/
 768 // DepIterator::IsSatisfied - check if a version satisfied the dependency /*{{{*/
 769 bool pkgCache::DepIterator::IsSatisfied(VerIterator const &Ver) const
 770 {
 771    return Owner->VS->CheckDep(Ver.VerStr(),S->CompareOp,TargetVer());
 772 }
 773 bool pkgCache::DepIterator::IsSatisfied(PrvIterator const &Prv) const
 774 {
 775    return Owner->VS->CheckDep(Prv.ProvideVersion(),S->CompareOp,TargetVer());
 776 }
 777                                                                         /*}}}*/
 778 // ostream operator to handle string representation of a dependecy      /*{{{*/
 779 // ---------------------------------------------------------------------
 780 /* */
 781 std::ostream& operator<<(std::ostream& out, pkgCache::DepIterator D)
 782 {
 783    if (D.end() == true)
 784       return out << "invalid dependency";
 785
 786    pkgCache::PkgIterator P = D.ParentPkg();
 787    pkgCache::PkgIterator T = D.TargetPkg();
 788
 789    out << (P.end() ? "invalid pkg" : P.FullName(false)) << " " << D.DepType()
 790         << " on ";
 791    if (T.end() == true)
 792       out << "invalid pkg";
 793    else
 794       out << T;
 795
 796    if (D->Version != 0)
 797       out << " (" << D.CompType() << " " << D.TargetVer() << ")";
 798
 799    return out;
 800 }
 801                                                                         /*}}}*/
 802 // VerIterator::CompareVer - Fast version compare for same pkgs         /*{{{*/
 803 // ---------------------------------------------------------------------
 804 /* This just looks over the version list to see if B is listed before A. In
 805    most cases this will return in under 4 checks, ver lists are short. */
 806 int pkgCache::VerIterator::CompareVer(const VerIterator &B) const
 807 {
 808    // Check if they are equal
 809    if (*this == B)
 810       return 0;
 811    if (end() == true)
 812       return -1;
 813    if (B.end() == true)
 814       return 1;
 815
 816    /* Start at A and look for B. If B is found then A > B otherwise
 817       B was before A so A < B */
 818    VerIterator I = *this;
 819    for (;I.end() == false; ++I)
 820       if (I == B)
 821          return 1;
 822    return -1;
 823 }
 824                                                                         /*}}}*/
 825 // VerIterator::Downloadable - Checks if the version is downloadable    /*{{{*/
 826 // ---------------------------------------------------------------------
 827 /* */
 828 APT_PURE bool pkgCache::VerIterator::Downloadable() const
 829 {
 830    VerFileIterator Files = FileList();
 831    for (; Files.end() == false; ++Files)
 832       if ((Files.File()->Flags & pkgCache::Flag::NotSource) != pkgCache::Flag::NotSource)
 833          return true;
 834    return false;
 835 }
 836                                                                         /*}}}*/
 837 // VerIterator::Automatic - Check if this version is 'automatic'        /*{{{*/
 838 // ---------------------------------------------------------------------
 839 /* This checks to see if any of the versions files are not NotAutomatic.
 840    True if this version is selectable for automatic installation. */
 841 APT_PURE bool pkgCache::VerIterator::Automatic() const
 842 {
 843    VerFileIterator Files = FileList();
 844    for (; Files.end() == false; ++Files)
 845       // Do not check ButAutomaticUpgrades here as it is kind of automatic…
 846       if ((Files.File()->Flags & pkgCache::Flag::NotAutomatic) != pkgCache::Flag::NotAutomatic)
 847          return true;
 848    return false;
 849 }
 850                                                                         /*}}}*/
 851 // VerIterator::NewestFile - Return the newest file version relation    /*{{{*/
 852 // ---------------------------------------------------------------------
 853 /* This looks at the version numbers associated with all of the sources
 854    this version is in and returns the highest.*/
 855 pkgCache::VerFileIterator pkgCache::VerIterator::NewestFile() const
 856 {
 857    VerFileIterator Files = FileList();
 858    VerFileIterator Highest = Files;
 859    for (; Files.end() == false; ++Files)
 860    {
 861       if (Owner->VS->CmpReleaseVer(Files.File().Version(),Highest.File().Version()) > 0)
 862          Highest = Files;
 863    }
 864
 865    return Highest;
 866 }
 867                                                                         /*}}}*/
 868 // VerIterator::RelStr - Release description string                     /*{{{*/
 869 // ---------------------------------------------------------------------
 870 /* This describes the version from a release-centric manner. The output is a
 871    list of Label:Version/Archive */
 872 string pkgCache::VerIterator::RelStr() const
 873 {
 874    bool First = true;
 875    string Res;
 876    for (pkgCache::VerFileIterator I = this->FileList(); I.end() == false; ++I)
 877    {
 878       // Do not print 'not source' entries'
 879       pkgCache::PkgFileIterator File = I.File();
 880       if ((File->Flags & pkgCache::Flag::NotSource) == pkgCache::Flag::NotSource)
 881          continue;
 882
 883       // See if we have already printed this out..
 884       bool Seen = false;
 885       for (pkgCache::VerFileIterator J = this->FileList(); I != J; ++J)
 886       {
 887          pkgCache::PkgFileIterator File2 = J.File();
 888          if (File2->Label == 0 || File->Label == 0)
 889             continue;
 890
 891          if (strcmp(File.Label(),File2.Label()) != 0)
 892             continue;
 893
 894          if (File2->Version == File->Version)
 895          {
 896             Seen = true;
 897             break;
 898          }
 899          if (File2->Version == 0 || File->Version == 0)
 900             break;
 901          if (strcmp(File.Version(),File2.Version()) == 0)
 902             Seen = true;
 903       }
 904
 905       if (Seen == true)
 906          continue;
 907
 908       if (First == false)
 909          Res += ", ";
 910       else
 911          First = false;
 912
 913       if (File->Label != 0)
 914          Res = Res + File.Label() + ':';
 915
 916       if (File->Archive != 0)
 917       {
 918          if (File->Version == 0)
 919             Res += File.Archive();
 920          else
 921             Res = Res + File.Version() + '/' +  File.Archive();
 922       }
 923       else
 924       {
 925          // No release file, print the host name that this came from
 926          if (File->Site == 0 || File.Site()[0] == 0)
 927             Res += "localhost";
 928          else
 929             Res += File.Site();
 930       }
 931    }
 932    if (S->ParentPkg != 0)
 933       Res.append(" [").append(Arch()).append("]");
 934    return Res;
 935 }
 936                                                                         /*}}}*/
 937 // VerIterator::MultiArchType - string representing MultiArch flag      /*{{{*/
 938 const char * pkgCache::VerIterator::MultiArchType() const
 939 {
 940    if ((S->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 941       return "same";
 942    else if ((S->MultiArch & pkgCache::Version::Foreign) == pkgCache::Version::Foreign)
 943       return "foreign";
 944    else if ((S->MultiArch & pkgCache::Version::Allowed) == pkgCache::Version::Allowed)
 945       return "allowed";
 946    return "none";
 947 }
 948                                                                         /*}}}*/
 949 // PkgFileIterator::IsOk - Checks if the cache is in sync with the file /*{{{*/
 950 // ---------------------------------------------------------------------
 951 /* This stats the file and compares its stats with the ones that were
 952    stored during generation. Date checks should probably also be
 953    included here. */
 954 bool pkgCache::PkgFileIterator::IsOk()
 955 {
 956    struct stat Buf;
 957    if (stat(FileName(),&Buf) != 0)
 958       return false;
 959
 960    if (Buf.st_size != (signed)S->Size || Buf.st_mtime != S->mtime)
 961       return false;
 962
 963    return true;
 964 }
 965                                                                         /*}}}*/
 966 // PkgFileIterator::RelStr - Return the release string                  /*{{{*/
 967 // ---------------------------------------------------------------------
 968 /* */
 969 string pkgCache::PkgFileIterator::RelStr()
 970 {
 971    string Res;
 972    if (Version() != 0)
 973       Res = Res + (Res.empty() == true?"v=":",v=") + Version();
 974    if (Origin() != 0)
 975       Res = Res + (Res.empty() == true?"o=":",o=")  + Origin();
 976    if (Archive() != 0)
 977       Res = Res + (Res.empty() == true?"a=":",a=")  + Archive();
 978    if (Codename() != 0)
 979       Res = Res + (Res.empty() == true?"n=":",n=")  + Codename();
 980    if (Label() != 0)
 981       Res = Res + (Res.empty() == true?"l=":",l=")  + Label();
 982    if (Component() != 0)
 983       Res = Res + (Res.empty() == true?"c=":",c=")  + Component();
 984    if (Architecture() != 0)
 985       Res = Res + (Res.empty() == true?"b=":",b=")  + Architecture();
 986    return Res;
 987 }
 988                                                                         /*}}}*/
 989 // VerIterator::TranslatedDescription - Return the a DescIter for locale/*{{{*/
 990 // ---------------------------------------------------------------------
 991 /* return a DescIter for the current locale or the default if none is
 992  * found
 993  */
 994 pkgCache::DescIterator pkgCache::VerIterator::TranslatedDescription() const
 995 {
 996    std::vector<string> const lang = APT::Configuration::getLanguages();
 997    for (std::vector<string>::const_iterator l = lang.begin();
 998         l != lang.end(); ++l)
 999    {
1000       pkgCache::DescIterator Desc = DescriptionList();
1001       for (; Desc.end() == false; ++Desc)
1002          if (*l == Desc.LanguageCode())
1003             break;
1004       if (Desc.end() == true)
1005       {
1006          if (*l == "en")
1007          {
1008             Desc = DescriptionList();
1009             for (; Desc.end() == false; ++Desc)
1010                if (strcmp(Desc.LanguageCode(), "") == 0)
1011                   break;
1012             if (Desc.end() == true)
1013                continue;
1014          }
1015          else
1016             continue;
1017       }
1018       return Desc;
1019    }
1020    for (pkgCache::DescIterator Desc = DescriptionList();
1021         Desc.end() == false; ++Desc)
1022       if (strcmp(Desc.LanguageCode(), "") == 0)
1023          return Desc;
1024    return DescriptionList();
1025 }
1026
1027                                                                         /*}}}*/
1028 // PrvIterator::IsMultiArchImplicit - added by the cache generation     /*{{{*/
1029 // ---------------------------------------------------------------------
1030 /* MultiArch can be translated to SingleArch for an resolver and we did so,
1031    by adding provides to help the resolver understand the problem, but
1032    sometimes it is needed to identify these to ignore them… */
1033 bool pkgCache::PrvIterator::IsMultiArchImplicit() const
1034 {
1035    pkgCache::PkgIterator const Owner = OwnerPkg();
1036    pkgCache::PkgIterator const Parent = ParentPkg();
1037    if (strcmp(Owner.Arch(), Parent.Arch()) != 0 || Owner->Name == Parent->Name)
1038       return true;
1039    return false;
1040 }
1041                                                                         /*}}}*/