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