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