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