* use mark-and-sweep from aptitude now as GC algorithm

diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
index 5167d11eb06ab560dac546ebd12607795d174211..bed90f5d066f0efc764d9f361429b35865217085 100644 (file)
--- a/apt-pkg/algorithms.cc
+++ b/apt-pkg/algorithms.cc
@@ -20,7 +20,10 @@
 #include <apt-pkg/algorithms.h>
 #include <apt-pkg/error.h>
 #include <apt-pkg/configuration.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-pkg/version.h>
 #include <apt-pkg/sptr.h>
+
     
 #include <apti18n.h>
     
@@ -1248,106 +1251,186 @@ void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
                                                                        /*}}}*/
 
 
-// pkgMarkPkgUsed - Mark used packages as dirty                                /*{{{*/
-// ---------------------------------------------------------------------
-/* Mark all reachable packages as dirty. */
-void pkgMarkPkgUsed(pkgDepCache &Cache, pkgCache::PkgIterator Pkg, 
-                  pkgCache::State::PkgRemoveState DirtLevel)
+// mark a single package in Mark-and-Sweep
+void pkgMarkPackage(pkgDepCache &Cache,
+                   const pkgCache::PkgIterator &pkg,
+                   const pkgCache::VerIterator &ver,
+                   bool follow_recommends,
+                   bool follow_suggests)
 {
-   // If it is not installed, and we are in manual mode, ignore it
-   if ((Pkg->CurrentVer == 0 && Cache[Pkg].Install() == false || Cache[Pkg].Delete() == true) &&
-       DirtLevel == pkgCache::State::RemoveManual) 
+   pkgDepCache::StateCache &state=Cache[pkg];
+   pkgCache::VerIterator candver=state.CandidateVerIter(Cache);
+   pkgCache::VerIterator instver=state.InstVerIter(Cache);
+
+#if 0
+   // If a package was garbage-collected but is now being marked, we
+   // should re-select it 
+   // For cases when a pkg is set to upgrade and this trigger the
+   // removal of a no-longer used dependency.  if the pkg is set to
+   // keep again later it will result in broken deps
+   if(state.Delete() && state.RemoveReason=pkgDepCache::Unused) 
    {
-//      fprintf(stdout,"This one is not installed/virtual %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel);
-      return;
+      if(ver==candver)
+        mark_install(pkg, false, false, NULL);
+      else if(ver==pkg.CurrentVer())
+        MarkKeep(pkg);
+      
+      instver=state.InstVerIter(*this);
    }
+#endif
 
-   // If it is not installed, and it is not virtual, ignore it
-   if ((Pkg->CurrentVer == 0 && Cache[Pkg].Install() == false || Cache[Pkg].Delete() == true) &&
-       Pkg->VersionList != 0)
-   {
-//      fprintf(stdout,"This one is not installed %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel);
+   // Ignore versions other than the InstVer, and ignore packages
+   // that are already going to be removed or just left uninstalled.
+   if(!(ver==instver && !instver.end()))
       return;
-   }
 
-   // If it is similar or more dirty than we are ;-), because we've been here already, don't mark it
-   // This is necessary because virtual packages just relay the current level,
-   // so it may be possible e.g. that this was already seen with ::RemoveSuggested, but
-   // we are ::RemoveRequired
-   if (Cache[Pkg].Dirty() >= DirtLevel) 
-   {
-      //fprintf(stdout,"Seen already %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel);
+   // if we are marked already we are done
+   if(state.Marked)
       return;
-   }
-   
-   // If it is less important than the current DirtLevel, don't mark it
-   if (Cache[Pkg].AutomaticRemove != pkgCache::State::RemoveManual && 
-      Cache[Pkg].AutomaticRemove > DirtLevel) 
+
+   //std::cout << "Setting Marked for: " << pkg.Name() << std::endl;
+   state.Marked=true;
+
+   if(!ver.end())
    {
-//       fprintf(stdout,"We don't need %s %d %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel, Cache[Pkg].Dirty());
-       return;
+     for(pkgCache::DepIterator d=ver.DependsList(); !d.end(); ++d)
+     {
+       if(d->Type==pkgCache::Dep::Depends ||
+          d->Type==pkgCache::Dep::PreDepends ||
+          (follow_recommends &&
+           d->Type==pkgCache::Dep::Recommends) ||
+          (follow_suggests &&
+           d->Type==pkgCache::Dep::Suggests))
+        {
+          // Try all versions of this package.
+          for(pkgCache::VerIterator V=d.TargetPkg().VersionList(); 
+              !V.end(); ++V)
+          {
+             if(_system->VS->CheckDep(V.VerStr(),d->CompareOp, d.TargetVer()))
+             {
+                pkgMarkPackage(Cache, V.ParentPkg(), V, 
+                               follow_recommends, follow_suggests);
+             }
+          }
+          // Now try virtual packages
+          for(pkgCache::PrvIterator prv=d.TargetPkg().ProvidesList(); 
+              !prv.end(); ++prv)
+          {
+             if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp, 
+                                      d.TargetVer()))
+             {
+                pkgMarkPackage(Cache, prv.OwnerPkg(), prv.OwnerVer(),
+                               follow_recommends, follow_suggests);
+             }
+          }
+       }
+     }
    }
+}
 
-   // Mark it as used
-   Cache.SetDirty(Pkg, DirtLevel);
-       
-   //fprintf(stdout,"We keep %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel);
 
-   // We are a virtual package
-   if (Pkg->VersionList == 0)
+bool pkgMarkUsed(pkgDepCache &Cache)
+{
+   bool follow_recommends;
+   bool follow_suggests;
+
+   // init the states
+   for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p)
    {
-//      fprintf(stdout,"We are virtual %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel);
-      for (pkgCache::PrvIterator Prv = Pkg.ProvidesList(); ! Prv.end(); ++Prv)
-        pkgMarkPkgUsed (Cache, Prv.OwnerPkg(), DirtLevel);
-      return;
+      Cache[p].Marked=false;
+      Cache[p].Garbage=false;
    }
 
-   // Depending on the type of dependency, follow it
-   for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); ! D.end(); ++D) 
-   {
-//      fprintf(stdout,"We depend on %s %s\n", D.TargetPkg().Name(), D.DepType());
+   // init vars
+   follow_recommends=_config->FindB("APT::AutoRemove::RecommendsImportant",false);
+   follow_suggests=_config->FindB("APT::AutoRemove::SuggestsImportend", false);
 
-      switch(D->Type) 
+
+   // do the mark part
+   for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p)
+   {
+      if(Cache[p].InstallReason==pkgDepCache::Manual ||
+        (p->Flags & pkgCache::Flag::Essential))
       {
-        case pkgCache::Dep::Depends:
-        case pkgCache::Dep::PreDepends:
-           pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveRequired);
-           break;
-        case pkgCache::Dep::Recommends:
-            pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveRecommended);
-           break;
-         case pkgCache::Dep::Suggests:
-            pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveSuggested);
-           break;
-        case pkgCache::Dep::Conflicts:
-        case pkgCache::Dep::Replaces:
-        case pkgCache::Dep::Obsoletes:
-           // We don't handle these here
-           break;
+        if(Cache[p].Keep() && !p.CurrentVer().end())
+           pkgMarkPackage(Cache, p, p.CurrentVer(),
+                          follow_recommends, follow_suggests);
+        else if(Cache[p].Install())
+           pkgMarkPackage(Cache, p, Cache[p].InstVerIter(Cache),
+                          follow_recommends, follow_suggests);
       }
    }
-//   fprintf(stdout,"We keep %s %d %d <END>\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel);
-}
-                                                                       /*}}}*/
 
-bool pkgMarkUsed(pkgDepCache &Cache)
-{
-   // debug only
-   if(_config->FindI("Debug::pkgAutoRemove",false) == true)
-     for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg)
-        if(!Cache[Pkg].Dirty() && Cache[Pkg].AutomaticRemove > 0)
-          std::clog << "has auto-remove information: " << Pkg.Name() 
-                    << " " << (int)Cache[Pkg].AutomaticRemove 
-                    << std::endl;
-
-   // init with defaults
-   for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg)
-      Cache.SetDirty(Pkg, pkgCache::State::RemoveUnknown);
-
-   // go recursive over the cache
-   for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg) 
-      pkgMarkPkgUsed (Cache, Pkg, pkgCache::State::RemoveManual);
 
-   
+   // do the sweep
+   for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p)
+  {
+     pkgDepCache::StateCache &state=Cache[p];
+
+     if(!state.Marked)
+     {
+       // mark installed but not yet marked stuff as garbage
+       if(p->CurrentVer != 0) {
+          state.Garbage=true;
+          std::cout << "Garbage: " << p.Name() << std::endl;
+       }
+
+#if 0   // mvo: the below bits still needs to be ported
+
+       // Be sure not to re-delete already deleted packages.
+       if(delete_unused && (!p.CurrentVer().end() || state.Install()) &&
+          !state.Delete())
+       {
+             bool do_delete=true;
+
+             // If the package is being upgraded, check if we're
+             // losing a versioned dep.  If the dependency matches
+             // the previous version and not the new version, keep
+             // the package back instead of removing it.
+             if(!p.CurrentVer().end() && state.Install())
+               {
+                 const char *vs=p.CurrentVer().VerStr();
+
+                 // Check direct revdeps only.  THIS ASSUMES NO
+                 // VERSIONED PROVIDES, but Debian probably won't
+                 // have them for ages if ever.
+                 for(pkgCache::DepIterator revdep=p.RevDependsList();
+                     !revdep.end(); ++revdep)
+                   {
+                     pkgCache::PkgIterator depender=revdep.ParentPkg();
+                     // Find which version of the depending package
+                     // will be installed.
+                     pkgCache::VerIterator instver=(*this)[depender].InstVerIter(*this);
+
+                     // Only pay attention to strong positive
+                     // dependencies whose parents will be installed.
+                     if(revdep.ParentVer()==instver &&
+                        (revdep->Type==pkgCache::Dep::Depends ||
+                         revdep->Type==pkgCache::Dep::PreDepends ||
+                         (revdep->Type==pkgCache::Dep::Recommends &&
+                          follow_recommends)))
+                       {
+                         // If the previous version matched, cancel the
+                         // deletion.  (note that I assume that the new
+                         // version does NOT match; otherwise it would
+                         // not be unused!)
+                         if(_system->VS->CheckDep(vs,
+                                                  revdep->CompareOp,
+                                                  revdep.TargetVer()))
+                           {
+                             mark_keep(p, false, false, undo);
+                             do_delete=false;
+                             break;
+                           }
+                       }
+                   }
+               }
+
+             if(do_delete)
+               mark_delete(p, false, true, undo);
+           }
+#endif
+     }
+  }
    return true;
 }

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index e30baa4b282c2bc2366cfbcbefdba4a9e3d0f92f..52b43d83d2d1d8dd8ed135d67aa1cce241767762 100644 (file)
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -78,9 +78,7 @@ bool pkgDepCache::Init(OpProgress *Prog)
       // Find the proper cache slot
       StateCache &State = PkgState[I->ID];
       State.iFlags = 0;
-      State.DirtyState = pkgCache::State::RemoveUnknown;
-      //State.AutomaticRemove = I->AutomaticRemove;
-      State.AutomaticRemove = pkgCache::State::RemoveUnknown;
+      State.InstallReason = Manual;
 
       // Figure out the install version
       State.CandidateVer = GetCandidateVer(I);
@@ -116,7 +114,7 @@ bool pkgDepCache::readStateFile(OpProgress *Prog)
       state_file.Open(state, FileFd::ReadOnly);
       int file_size = state_file.Size();
       Prog->OverallProgress(0, file_size, 1, 
-                           _("Reading extended state information"));
+                           _("Reading state information"));
 
       pkgTagFile tagfile(&state_file);
       pkgTagSection section;
@@ -127,16 +125,17 @@ bool pkgDepCache::readStateFile(OpProgress *Prog)
         // Silently ignore unknown packages and packages with no actual
         // version.
         if(!pkg.end() && !pkg.VersionList().end()) {
-           short reason = section.FindI("Remove-Reason", 
-                                        pkgCache::State::RemoveManual);
-           PkgState[pkg->ID].AutomaticRemove = reason;
-           //std::cout << "Set: " << pkgname << " to " << reason << std::endl;
+           short reason = section.FindI("Install-Reason",pkgDepCache::Manual);
+           PkgState[pkg->ID].InstallReason = (ChangedReason)reason;
+           if(_config->FindB("Debug::pkgAutoRemove",false))
+              std::cout << "Install-Reason for: " << pkgname 
+                        << " is " << reason << std::endl;
            amt+=section.size();
            Prog->OverallProgress(amt, file_size, 1, 
-                                 _("Reading extended state information"));
+                                 _("Reading state information"));
         }
         Prog->OverallProgress(file_size, file_size, 1, 
-                              _("Reading extended state information"));
+                              _("Reading state information"));
       }
    }
 
@@ -145,9 +144,6 @@ bool pkgDepCache::readStateFile(OpProgress *Prog)
 
 bool pkgDepCache::writeStateFile(OpProgress *prog)
 {
-   // FIXME: this function needs to be called inside the commit()
-   // of the package manager. so after 
-
    FileFd StateFile;
    string state = _config->FindDir("Dir::State") + "pkgstates";
 
@@ -160,20 +156,20 @@ bool pkgDepCache::writeStateFile(OpProgress *prog)
 
       // clear out no longer installed pkg
       if(PkgState[pkg->ID].Delete() || pkg.CurrentVer() == NULL) 
-        PkgState[pkg->ID].AutomaticRemove = pkgCache::State::RemoveUnknown;
+        PkgState[pkg->ID].InstallReason = Manual;
 
       // check if we have new information
       if(PkgState[pkg->ID].Flags & pkgCache::Flag::Auto) {
         if(_config->FindI("Debug::pkgAutoRemove",false))
            std::clog << "pkg: " << pkg.Name() << " is auto-dep" << std::endl;
-        PkgState[pkg->ID].AutomaticRemove = pkgCache::State::RemoveRequired;
+        PkgState[pkg->ID].InstallReason = Libapt;
       }
 
-      if(PkgState[pkg->ID].AutomaticRemove != pkgCache::State::RemoveUnknown) {
+      if(PkgState[pkg->ID].InstallReason != Manual) {
         ostr.str(string(""));
-        ostr << "Package: " << pkg.Name()
-             << "\nRemove-Reason: "
-             << (int)(PkgState[pkg->ID].AutomaticRemove) << "\n\n";
+        ostr << "Package: " << pkg.Name() 
+             << "\nInstall-Reason: "
+             << (int)(PkgState[pkg->ID].InstallReason) << "\n\n";
         StateFile.Write(ostr.str().c_str(), ostr.str().size());
       }
    }
@@ -841,15 +837,6 @@ void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
    AddSizes(Pkg);
 }
                                                                        /*}}}*/
-// DepCache::SetDirty - Switch the package between dirty states                /*{{{*/
-// ---------------------------------------------------------------------
-/* */
-void pkgDepCache::SetDirty(PkgIterator const &Pkg, pkgCache::State::PkgRemoveState To)
-{
-   StateCache &P = PkgState[Pkg->ID];
-   P.DirtyState = To;
-}
-                                                                       /*}}}*/
 // DepCache::SetCandidateVersion - Change the candidate version                /*{{{*/
 // ---------------------------------------------------------------------
 /* */

diff --git a/apt-pkg/depcache.h b/apt-pkg/depcache.h
index e02ed72f04885421f6c1fbbc2c80000f63f0ca42..c91e09ab3dca0d9fb7698c105ceaf5e720632693 100644 (file)
--- a/apt-pkg/depcache.h
+++ b/apt-pkg/depcache.h
@@ -63,6 +63,10 @@ class pkgDepCache : protected pkgCache::Namespace
       
    enum VersionTypes {NowVersion, InstallVersion, CandidateVersion};
    enum ModeList {ModeDelete = 0, ModeKeep = 1, ModeInstall = 2};
+
+   // Flags for the GC
+   enum ChangedReason {Manual, UserAuto, Libapt, FromResolver, PkgIsUnused};
+
    struct StateCache
    {
       // Epoch stripped text versions of the two version fields
@@ -79,9 +83,13 @@ class pkgDepCache : protected pkgCache::Namespace
       unsigned short Flags;
       unsigned short iFlags;           // Internal flags
 
-      // Traversal status and state for automatic removal
-      unsigned char DirtyState;
-      unsigned char AutomaticRemove;
+      // mark and sweep flags
+      ChangedReason InstallReason;
+#if 0
+      ChangedReason RemoveReason;
+#endif
+      bool Marked;
+      bool Garbage;
 
       // Various tree indicators
       signed char Status;              // -1,0,1,2
@@ -103,7 +111,6 @@ class pkgDepCache : protected pkgCache::Namespace
       inline bool NowBroken() const {return (DepState & DepNowMin) != DepNowMin;};
       inline bool InstBroken() const {return (DepState & DepInstMin) != DepInstMin;};
       inline bool Install() const {return Mode == ModeInstall;};
-      inline unsigned char Dirty() const {return DirtyState;};
       inline VerIterator InstVerIter(pkgCache &Cache)
                 {return VerIterator(Cache,InstallVer);};
       inline VerIterator CandidateVerIter(pkgCache &Cache)
@@ -194,7 +201,6 @@ class pkgDepCache : protected pkgCache::Namespace
                    unsigned long Depth = 0);
    void SetReInstall(PkgIterator const &Pkg,bool To);
    void SetCandidateVersion(VerIterator TargetVer);
-   void SetDirty(PkgIterator const &Pkg, pkgCache::State::PkgRemoveState To);
    
    // This is for debuging
    void Update(OpProgress *Prog = 0);

diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h
index 083f20ac2ac2926d54e15d03e88482b653b7c027..b07951dfb8fbf26710c8790cd73af87e30c38f3d 100644 (file)
--- a/apt-pkg/pkgcache.h
+++ b/apt-pkg/pkgcache.h
@@ -75,7 +75,6 @@ class pkgCache
       enum PkgInstState {Ok=0,ReInstReq=1,HoldInst=2,HoldReInstReq=3};
       enum PkgCurrentState {NotInstalled=0,UnPacked=1,HalfConfigured=2,
           HalfInstalled=4,ConfigFiles=5,Installed=6};
-      enum PkgRemoveState {RemoveUnknown=0, RemoveManual=1,RemoveSuggested=2,RemoveRecommended=3,RemoveRequired=4};
    };
    
    struct Flag

diff --git a/cmdline/apt-get.cc b/cmdline/apt-get.cc
index 0236d7e77af5f17dbfa203def5e2b4ff3c97e305..9d97f8756eb9abf5f91e6ef9100bcba426891267 100644 (file)
--- a/cmdline/apt-get.cc
+++ b/cmdline/apt-get.cc
@@ -1374,12 +1374,11 @@ bool DoAutomaticRemove(CacheFile &Cache)
    // look over the cache to see what can be removed
    for (pkgCache::PkgIterator Pkg = Cache->PkgBegin(); ! Pkg.end(); ++Pkg)
    {
-      if (! Cache[Pkg].Dirty() &&
+      if (Cache[Pkg].Garbage &&
           (Pkg->CurrentVer != 0 && Cache[Pkg].Install() == false && 
           Cache[Pkg].Delete() == false))
       {
-         fprintf(stdout,"We could delete %s %d\n", 
-                Pkg.Name(), Cache[Pkg].AutomaticRemove);
+         fprintf(stdout,"We could delete %s\n", Pkg.Name());
          Cache->MarkDelete(Pkg,_config->FindB("APT::Get::Purge",false));
       }
    }

diff --git a/debian/changelog b/debian/changelog
index 78559fd56aab5979c0bae899b093fc7e5aa5f67a..11e1a6282b3ce1f41519fe1e8714dd0d306c07e7 100644 (file)
--- a/debian/changelog
+++ b/debian/changelog
@@ -14,8 +14,11 @@ apt (0.6.38ubuntu1mvo1) unstable; urgency=low
       the patch, thanks to Colin Watson for testing it.
     - better report network timeouts from the methods to the acuire code, 
       only timeout once per sources.list line 
-
- -- Michael Vogt <michael.vogt@ubuntu.com>  Tue, 28 Jun 2005 11:18:24 +0200
+    - started to port the great automatic dependency mangement code from
+      aptitude over to apt (thanks dburrows for answering my silly 
+      questions and your great help!)
+  
+ -- 
 
 apt (0.6.38ubuntu1) breezy; urgency=low