apt-pkg/pkgcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: pkgcache.cc,v 1.33 2001/03/05 02:43:28 jgg 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 managment. 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 #ifdef __GNUG__
  24 #pragma implementation "apt-pkg/pkgcache.h"
  25 #pragma implementation "apt-pkg/cacheiterators.h"
  26 #endif
  27
  28 #include <apt-pkg/pkgcache.h>
  29 #include <apt-pkg/version.h>
  30 #include <apt-pkg/error.h>
  31 #include <apt-pkg/strutl.h>
  32 #include <apt-pkg/configuration.h>
  33
  34 #include <apti18n.h>
  35
  36 #include <string>
  37 #include <sys/stat.h>
  38 #include <unistd.h>
  39
  40 #include <system.h>
  41
  42                                                                         /*}}}*/
  43
  44 // Cache::Header::Header - Constructor                                  /*{{{*/
  45 // ---------------------------------------------------------------------
  46 /* Simply initialize the header */
  47 pkgCache::Header::Header()
  48 {
  49    Signature = 0x98FE76DC;
  50
  51    /* Whenever the structures change the major version should be bumped,
  52       whenever the generator changes the minor version should be bumped. */
  53    MajorVersion = 3;
  54    MinorVersion = 5;
  55    Dirty = false;
  56
  57    HeaderSz = sizeof(pkgCache::Header);
  58    PackageSz = sizeof(pkgCache::Package);
  59    PackageFileSz = sizeof(pkgCache::PackageFile);
  60    VersionSz = sizeof(pkgCache::Version);
  61    DependencySz = sizeof(pkgCache::Dependency);
  62    ProvidesSz = sizeof(pkgCache::Provides);
  63    VerFileSz = sizeof(pkgCache::VerFile);
  64
  65    PackageCount = 0;
  66    VersionCount = 0;
  67    DependsCount = 0;
  68    PackageFileCount = 0;
  69    VerFileCount = 0;
  70    ProvidesCount = 0;
  71    MaxVerFileSize = 0;
  72
  73    FileList = 0;
  74    StringList = 0;
  75    VerSysName = 0;
  76    Architecture = 0;
  77    memset(HashTable,0,sizeof(HashTable));
  78    memset(Pools,0,sizeof(Pools));
  79 }
  80                                                                         /*}}}*/
  81 // Cache::Header::CheckSizes - Check if the two headers have same *sz   /*{{{*/
  82 // ---------------------------------------------------------------------
  83 /* */
  84 bool pkgCache::Header::CheckSizes(Header &Against) const
  85 {
  86    if (HeaderSz == Against.HeaderSz &&
  87        PackageSz == Against.PackageSz &&
  88        PackageFileSz == Against.PackageFileSz &&
  89        VersionSz == Against.VersionSz &&
  90        DependencySz == Against.DependencySz &&
  91        VerFileSz == Against.VerFileSz &&
  92        ProvidesSz == Against.ProvidesSz)
  93       return true;
  94    return false;
  95 }
  96                                                                         /*}}}*/
  97
  98 // Cache::pkgCache - Constructor                                        /*{{{*/
  99 // ---------------------------------------------------------------------
 100 /* */
 101 pkgCache::pkgCache(MMap *Map, bool DoMap) : Map(*Map)
 102 {
 103    if (DoMap == true)
 104       ReMap();
 105 }
 106                                                                         /*}}}*/
 107 // Cache::ReMap - Reopen the cache file                                 /*{{{*/
 108 // ---------------------------------------------------------------------
 109 /* If the file is already closed then this will open it open it. */
 110 bool pkgCache::ReMap()
 111 {
 112    // Apply the typecasts.
 113    HeaderP = (Header *)Map.Data();
 114    PkgP = (Package *)Map.Data();
 115    VerFileP = (VerFile *)Map.Data();
 116    PkgFileP = (PackageFile *)Map.Data();
 117    VerP = (Version *)Map.Data();
 118    ProvideP = (Provides *)Map.Data();
 119    DepP = (Dependency *)Map.Data();
 120    StringItemP = (StringItem *)Map.Data();
 121    StrP = (char *)Map.Data();
 122
 123    if (Map.Size() == 0 || HeaderP == 0)
 124       return _error->Error(_("Empty package cache"));
 125
 126    // Check the header
 127    Header DefHeader;
 128    if (HeaderP->Signature != DefHeader.Signature ||
 129        HeaderP->Dirty == true)
 130       return _error->Error(_("The package cache file is corrupted"));
 131
 132    if (HeaderP->MajorVersion != DefHeader.MajorVersion ||
 133        HeaderP->MinorVersion != DefHeader.MinorVersion ||
 134        HeaderP->CheckSizes(DefHeader) == false)
 135       return _error->Error(_("The package cache file is an incompatible version"));
 136
 137    // Locate our VS..
 138    if (HeaderP->VerSysName == 0 ||
 139        (VS = pkgVersioningSystem::GetVS(StrP + HeaderP->VerSysName)) == 0)
 140       return _error->Error(_("This APT does not support the Versioning System '%s'"),StrP + HeaderP->VerSysName);
 141
 142    // Chcek the arhcitecture
 143    if (HeaderP->Architecture == 0 ||
 144        _config->Find("APT::Architecture") != StrP + HeaderP->Architecture)
 145       return _error->Error(_("The package cache was build for a different architecture"));
 146    return true;
 147 }
 148                                                                         /*}}}*/
 149 // Cache::Hash - Hash a string                                          /*{{{*/
 150 // ---------------------------------------------------------------------
 151 /* This is used to generate the hash entries for the HashTable. With my
 152    package list from bo this function gets 94% table usage on a 512 item
 153    table (480 used items) */
 154 unsigned long pkgCache::sHash(string Str) const
 155 {
 156    unsigned long Hash = 0;
 157    for (const char *I = Str.begin(); I != Str.end(); I++)
 158       Hash = 5*Hash + tolower(*I);
 159    return Hash % _count(HeaderP->HashTable);
 160 }
 161
 162 unsigned long pkgCache::sHash(const char *Str) const
 163 {
 164    unsigned long Hash = 0;
 165    for (const char *I = Str; *I != 0; I++)
 166       Hash = 5*Hash + tolower(*I);
 167    return Hash % _count(HeaderP->HashTable);
 168 }
 169
 170                                                                         /*}}}*/
 171 // Cache::FindPkg - Locate a package by name                            /*{{{*/
 172 // ---------------------------------------------------------------------
 173 /* Returns 0 on error, pointer to the package otherwise */
 174 pkgCache::PkgIterator pkgCache::FindPkg(string Name)
 175 {
 176    // Look at the hash bucket
 177    Package *Pkg = PkgP + HeaderP->HashTable[Hash(Name)];
 178    for (; Pkg != PkgP; Pkg = PkgP + Pkg->NextPackage)
 179    {
 180       if (Pkg->Name != 0 && StrP[Pkg->Name] == Name[0] &&
 181           stringcasecmp(Name.begin(),Name.end(),StrP + Pkg->Name) == 0)
 182          return PkgIterator(*this,Pkg);
 183    }
 184    return PkgIterator(*this,0);
 185 }
 186                                                                         /*}}}*/
 187 // Cache::CompTypeDeb - Return a string describing the compare type     /*{{{*/
 188 // ---------------------------------------------------------------------
 189 /* This returns a string representation of the dependency compare
 190    type in the weird debian style.. */
 191 const char *pkgCache::CompTypeDeb(unsigned char Comp)
 192 {
 193    const char *Ops[] = {"","<=",">=","<<",">>","=","!="};
 194    if ((unsigned)(Comp & 0xF) < 7)
 195       return Ops[Comp & 0xF];
 196    return "";
 197 }
 198                                                                         /*}}}*/
 199 // Cache::CompType - Return a string describing the compare type        /*{{{*/
 200 // ---------------------------------------------------------------------
 201 /* This returns a string representation of the dependency compare
 202    type */
 203 const char *pkgCache::CompType(unsigned char Comp)
 204 {
 205    const char *Ops[] = {"","<=",">=","<",">","=","!="};
 206    if ((unsigned)(Comp & 0xF) < 7)
 207       return Ops[Comp & 0xF];
 208    return "";
 209 }
 210                                                                         /*}}}*/
 211 // Cache::DepType - Return a string describing the dep type             /*{{{*/
 212 // ---------------------------------------------------------------------
 213 /* */
 214 const char *pkgCache::DepType(unsigned char Type)
 215 {
 216    const char *Types[] = {"",_("Depends"),_("PreDepends"),_("Suggests"),
 217                           _("Recommends"),_("Conflicts"),_("Replaces"),
 218                           _("Obsoletes")};
 219    if (Type < 8)
 220       return Types[Type];
 221    return "";
 222 }
 223                                                                         /*}}}*/
 224 // Cache::Priority - Convert a priority value to a string               /*{{{*/
 225 // ---------------------------------------------------------------------
 226 /* */
 227 const char *pkgCache::Priority(unsigned char Prio)
 228 {
 229    const char *Mapping[] = {0,_("important"),_("required"),_("standard"),
 230                             _("optional"),_("extra")};
 231    if (Prio < _count(Mapping))
 232       return Mapping[Prio];
 233    return 0;
 234 }
 235                                                                         /*}}}*/
 236
 237 // Bases for iterator classes                                           /*{{{*/
 238 void pkgCache::VerIterator::_dummy() {}
 239 void pkgCache::DepIterator::_dummy() {}
 240 void pkgCache::PrvIterator::_dummy() {}
 241                                                                         /*}}}*/
 242 // PkgIterator::operator ++ - Postfix incr                              /*{{{*/
 243 // ---------------------------------------------------------------------
 244 /* This will advance to the next logical package in the hash table. */
 245 void pkgCache::PkgIterator::operator ++(int)
 246 {
 247    // Follow the current links
 248    if (Pkg != Owner->PkgP)
 249       Pkg = Owner->PkgP + Pkg->NextPackage;
 250
 251    // Follow the hash table
 252    while (Pkg == Owner->PkgP && (HashIndex+1) < (signed)_count(Owner->HeaderP->HashTable))
 253    {
 254       HashIndex++;
 255       Pkg = Owner->PkgP + Owner->HeaderP->HashTable[HashIndex];
 256    }
 257 };
 258                                                                         /*}}}*/
 259 // PkgIterator::State - Check the State of the package                  /*{{{*/
 260 // ---------------------------------------------------------------------
 261 /* By this we mean if it is either cleanly installed or cleanly removed. */
 262 pkgCache::PkgIterator::OkState pkgCache::PkgIterator::State() const
 263 {
 264    if (Pkg->InstState == pkgCache::State::ReInstReq ||
 265        Pkg->InstState == pkgCache::State::HoldReInstReq)
 266       return NeedsUnpack;
 267
 268    if (Pkg->CurrentState == pkgCache::State::UnPacked ||
 269        Pkg->CurrentState == pkgCache::State::HalfConfigured)
 270       return NeedsConfigure;
 271
 272    if (Pkg->CurrentState == pkgCache::State::HalfInstalled ||
 273        Pkg->InstState != pkgCache::State::Ok)
 274       return NeedsUnpack;
 275
 276    return NeedsNothing;
 277 }
 278                                                                         /*}}}*/
 279 // DepIterator::IsCritical - Returns true if the dep is important       /*{{{*/
 280 // ---------------------------------------------------------------------
 281 /* Currently critical deps are defined as depends, predepends and
 282    conflicts. */
 283 bool pkgCache::DepIterator::IsCritical()
 284 {
 285    if (Dep->Type == pkgCache::Dep::Conflicts ||
 286        Dep->Type == pkgCache::Dep::Obsoletes ||
 287        Dep->Type == pkgCache::Dep::Depends ||
 288        Dep->Type == pkgCache::Dep::PreDepends)
 289       return true;
 290    return false;
 291 }
 292                                                                         /*}}}*/
 293 // DepIterator::SmartTargetPkg - Resolve dep target pointers w/provides /*{{{*/
 294 // ---------------------------------------------------------------------
 295 /* This intellegently looks at dep target packages and tries to figure
 296    out which package should be used. This is needed to nicely handle
 297    provide mapping. If the target package has no other providing packages
 298    then it returned. Otherwise the providing list is looked at to
 299    see if there is one one unique providing package if so it is returned.
 300    Otherwise true is returned and the target package is set. The return
 301    result indicates whether the node should be expandable
 302
 303    In Conjunction with the DepCache the value of Result may not be
 304    super-good since the policy may have made it uninstallable. Using
 305    AllTargets is better in this case. */
 306 bool pkgCache::DepIterator::SmartTargetPkg(PkgIterator &Result)
 307 {
 308    Result = TargetPkg();
 309
 310    // No provides at all
 311    if (Result->ProvidesList == 0)
 312       return false;
 313
 314    // There is the Base package and the providing ones which is at least 2
 315    if (Result->VersionList != 0)
 316       return true;
 317
 318    /* We have to skip over indirect provisions of the package that
 319       owns the dependency. For instance, if libc5-dev depends on the
 320       virtual package libc-dev which is provided by libc5-dev and libc6-dev
 321       we must ignore libc5-dev when considering the provides list. */
 322    PrvIterator PStart = Result.ProvidesList();
 323    for (; PStart.end() != true && PStart.OwnerPkg() == ParentPkg(); PStart++);
 324
 325    // Nothing but indirect self provides
 326    if (PStart.end() == true)
 327       return false;
 328
 329    // Check for single packages in the provides list
 330    PrvIterator P = PStart;
 331    for (; P.end() != true; P++)
 332    {
 333       // Skip over self provides
 334       if (P.OwnerPkg() == ParentPkg())
 335          continue;
 336       if (PStart.OwnerPkg() != P.OwnerPkg())
 337          break;
 338    }
 339
 340    Result = PStart.OwnerPkg();
 341
 342    // Check for non dups
 343    if (P.end() != true)
 344       return true;
 345
 346    return false;
 347 }
 348                                                                         /*}}}*/
 349 // DepIterator::AllTargets - Returns the set of all possible targets    /*{{{*/
 350 // ---------------------------------------------------------------------
 351 /* This is a more useful version of TargetPkg() that follows versioned
 352    provides. It includes every possible package-version that could satisfy
 353    the dependency. The last item in the list has a 0. The resulting pointer
 354    must be delete [] 'd */
 355 pkgCache::Version **pkgCache::DepIterator::AllTargets()
 356 {
 357    Version **Res = 0;
 358    unsigned long Size =0;
 359    while (1)
 360    {
 361       Version **End = Res;
 362       PkgIterator DPkg = TargetPkg();
 363
 364       // Walk along the actual package providing versions
 365       for (VerIterator I = DPkg.VersionList(); I.end() == false; I++)
 366       {
 367          if (Owner->VS->CheckDep(I.VerStr(),Dep->CompareOp,TargetVer()) == false)
 368             continue;
 369
 370          if ((Dep->Type == pkgCache::Dep::Conflicts ||
 371               Dep->Type == pkgCache::Dep::Obsoletes) &&
 372              ParentPkg() == I.ParentPkg())
 373             continue;
 374
 375          Size++;
 376          if (Res != 0)
 377             *End++ = I;
 378       }
 379
 380       // Follow all provides
 381       for (PrvIterator I = DPkg.ProvidesList(); I.end() == false; I++)
 382       {
 383          if (Owner->VS->CheckDep(I.ProvideVersion(),Dep->CompareOp,TargetVer()) == false)
 384             continue;
 385
 386          if ((Dep->Type == pkgCache::Dep::Conflicts ||
 387               Dep->Type == pkgCache::Dep::Obsoletes) &&
 388              ParentPkg() == I.OwnerPkg())
 389             continue;
 390
 391          Size++;
 392          if (Res != 0)
 393             *End++ = I.OwnerVer();
 394       }
 395
 396       // Do it again and write it into the array
 397       if (Res == 0)
 398       {
 399          Res = new Version *[Size+1];
 400          Size = 0;
 401       }
 402       else
 403       {
 404          *End = 0;
 405          break;
 406       }
 407    }
 408
 409    return Res;
 410 }
 411                                                                         /*}}}*/
 412 // DepIterator::GlobOr - Compute an OR group                            /*{{{*/
 413 // ---------------------------------------------------------------------
 414 /* This Takes an iterator, iterates past the current dependency grouping
 415    and returns Start and End so that so End is the final element
 416    in the group, if End == Start then D is End++ and End is the
 417    dependency D was pointing to. Use in loops to iterate sensibly. */
 418 void pkgCache::DepIterator::GlobOr(DepIterator &Start,DepIterator &End)
 419 {
 420    // Compute a single dependency element (glob or)
 421    Start = *this;
 422    End = *this;
 423    for (bool LastOR = true; end() == false && LastOR == true;)
 424    {
 425       LastOR = (Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 426       (*this)++;
 427       if (LastOR == true)
 428          End = (*this);
 429    }
 430 }
 431                                                                         /*}}}*/
 432 // VerIterator::CompareVer - Fast version compare for same pkgs         /*{{{*/
 433 // ---------------------------------------------------------------------
 434 /* This just looks over the version list to see if B is listed before A. In
 435    most cases this will return in under 4 checks, ver lists are short. */
 436 int pkgCache::VerIterator::CompareVer(const VerIterator &B) const
 437 {
 438    // Check if they are equal
 439    if (*this == B)
 440       return 0;
 441    if (end() == true)
 442       return -1;
 443    if (B.end() == true)
 444       return 1;
 445
 446    /* Start at A and look for B. If B is found then A > B otherwise
 447       B was before A so A < B */
 448    VerIterator I = *this;
 449    for (;I.end() == false; I++)
 450       if (I == B)
 451          return 1;
 452    return -1;
 453 }
 454                                                                         /*}}}*/
 455 // VerIterator::Downloadable - Checks if the version is downloadable    /*{{{*/
 456 // ---------------------------------------------------------------------
 457 /* */
 458 bool pkgCache::VerIterator::Downloadable() const
 459 {
 460    VerFileIterator Files = FileList();
 461    for (; Files.end() == false; Files++)
 462       if ((Files.File()->Flags & pkgCache::Flag::NotSource) != pkgCache::Flag::NotSource)
 463          return true;
 464    return false;
 465 }
 466                                                                         /*}}}*/
 467 // VerIterator::Automatic - Check if this version is 'automatic'        /*{{{*/
 468 // ---------------------------------------------------------------------
 469 /* This checks to see if any of the versions files are not NotAutomatic.
 470    True if this version is selectable for automatic installation. */
 471 bool pkgCache::VerIterator::Automatic() const
 472 {
 473    VerFileIterator Files = FileList();
 474    for (; Files.end() == false; Files++)
 475       if ((Files.File()->Flags & pkgCache::Flag::NotAutomatic) != pkgCache::Flag::NotAutomatic)
 476          return true;
 477    return false;
 478 }
 479                                                                         /*}}}*/
 480 // VerIterator::NewestFile - Return the newest file version relation    /*{{{*/
 481 // ---------------------------------------------------------------------
 482 /* This looks at the version numbers associated with all of the sources
 483    this version is in and returns the highest.*/
 484 pkgCache::VerFileIterator pkgCache::VerIterator::NewestFile() const
 485 {
 486    VerFileIterator Files = FileList();
 487    VerFileIterator Highest = Files;
 488    for (; Files.end() == false; Files++)
 489    {
 490       if (Owner->VS->CmpReleaseVer(Files.File().Version(),Highest.File().Version()) > 0)
 491          Highest = Files;
 492    }
 493
 494    return Highest;
 495 }
 496                                                                         /*}}}*/
 497 // VerIterator::RelStr - Release description string                     /*{{{*/
 498 // ---------------------------------------------------------------------
 499 /* This describes the version from a release-centric manner. The output is a
 500    list of Label:Version/Archive */
 501 string pkgCache::VerIterator::RelStr()
 502 {
 503    bool First = true;
 504    string Res;
 505    for (pkgCache::VerFileIterator I = this->FileList(); I.end() == false; I++)
 506    {
 507       // Do not print 'not source' entries'
 508       pkgCache::PkgFileIterator File = I.File();
 509       if ((File->Flags & pkgCache::Flag::NotSource) == pkgCache::Flag::NotSource)
 510          continue;
 511
 512       // See if we have already printed this out..
 513       bool Seen = false;
 514       for (pkgCache::VerFileIterator J = this->FileList(); I != J; J++)
 515       {
 516          pkgCache::PkgFileIterator File2 = J.File();
 517          if (File2->Label == 0 || File->Label == 0)
 518             continue;
 519
 520          if (strcmp(File.Label(),File2.Label()) != 0)
 521             continue;
 522
 523          if (File2->Version == File->Version)
 524          {
 525             Seen = true;
 526             break;
 527          }
 528          if (File2->Version == 0 || File->Version == 0)
 529             break;
 530          if (strcmp(File.Version(),File2.Version()) == 0)
 531             Seen = true;
 532       }
 533
 534       if (Seen == true)
 535          continue;
 536
 537       if (First == false)
 538          Res += ", ";
 539       else
 540          First = false;
 541
 542       if (File->Label != 0)
 543          Res = Res + File.Label() + ':';
 544
 545       if (File->Archive != 0)
 546       {
 547          if (File->Version == 0)
 548             Res += File.Archive();
 549          else
 550             Res = Res + File.Version() + '/' +  File.Archive();
 551       }
 552       else
 553       {
 554          // No release file, print the host name that this came from
 555          if (File->Site == 0 || File.Site()[0] == 0)
 556             Res += "localhost";
 557          else
 558             Res += File.Site();
 559       }
 560    }
 561    return Res;
 562 }
 563                                                                         /*}}}*/
 564 // PkgFileIterator::IsOk - Checks if the cache is in sync with the file /*{{{*/
 565 // ---------------------------------------------------------------------
 566 /* This stats the file and compares its stats with the ones that were
 567    stored during generation. Date checks should probably also be
 568    included here. */
 569 bool pkgCache::PkgFileIterator::IsOk()
 570 {
 571    struct stat Buf;
 572    if (stat(FileName(),&Buf) != 0)
 573       return false;
 574
 575    if (Buf.st_size != (signed)File->Size || Buf.st_mtime != File->mtime)
 576       return false;
 577
 578    return true;
 579 }
 580                                                                         /*}}}*/