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