* merged daniel burrows fixes for the auto-mark code

Patches applied:

 * dburrows@debian.org--2005/apt--auto-mark--0--base-0
   tag of michael.vogt@ubuntu.com--2005/apt--auto-mark--0--patch-22

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-1
   doxygenize the new automark stuff

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-2
   Automatically update package markings after every state-changing public operation, and allow users of the dep-cache to group actions into a single action.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-3
   Automatically update package markings after every state-changing public operation, and allow users of the dep-cache to group actions into a single action.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-4
   Make action groups noncopyable

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-5
   Typo fix

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-6
   Add a FromUser flag to MarkKeep.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-7
   Somehow the ActionGroup definition got duplicated; kill the duplicate.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-8
   Cancel the automatic flag on packages that are being kept only if they are garbage.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-9
   Don't clear the 'automatically installed' flag in MarkDelete.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-10
   Add a FromUser flag to MarkInstall, and fix its handling of the Auto flag.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-11
   Only clear the Auto flag on manual changes in MarkKeep.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-12
   Make changes from the internal algorithms automatic.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-13
   Use ActionGroups in algorithms that make lots of changes, and fix a compile error.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-14
   Split the sweep code into a separate routine from pkgMarkUsed

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-15
   Update another call of MarkKeep to indicate that it's automatic.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-16
   Move the mark-and-sweep code into pkgDepCache; call Sweep and document what it and Garbage are for; add a hook that can be used to generate a custom root-set function; move the big blob of regexp stuff into the custom root-set; fix the memory leak in the regexp stuff.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-17
   Make ActionGroup take a reference instead of a pointer to the cache.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-18
   Don't mark already-to-be-deleted packages as garbage, to imitate aptitude's behavior.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-19
   Update apt-get for the new auto-mark protocol.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-20
   Add a setter method for the Auto flag.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-21
   Fix the test in apt-get about what to delete.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-22
   Add a zero-argument mark-and-sweep routine and use it to do a mark-and-sweep on startup (so the garbage flags are initialized properly).

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-23
   Right, Status is 2 for new installs, not 0.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-24
   POT updates.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-25
   Actually initialize group_level to 0.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-26
   Don't make an ActionGroup in Sweep, since there's no point and it also is an infinite loop.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-27
   Add virtual hooks to control whether the garbage collector considers recommends and/or suggests to be strong links.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-28
   Call the progress methods in the right order so we don't generate nonsensical progress notifications.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-29
   Typo fix.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-30
   Make RecommendsImportant default to true in apt, too.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-31
   Add a release() method to action groups.

 * dburrows@debian.org--2005/apt--auto-mark--0--patch-32
   Add an 'autoremove' command that is synonymous to '--auto-remove remove'.

1 files changed, 207 insertions, 5 deletions

diff --git a/apt-pkg/depcache.h b/apt-pkg/depcache.h
index 619daf8f6..fd935c268 100644
--- a/apt-pkg/depcache.h
+++ b/apt-pkg/depcache.h
@@ -1,4 +1,4 @@
-// -*- mode: cpp; mode: fold -*-
+// -*- mode: c++; mode: fold -*-
 // Description								/*{{{*/
 // $Id: depcache.h,v 1.14 2001/02/20 07:03:17 jgg Exp $
 /* ######################################################################
@@ -45,9 +45,71 @@
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/progress.h>
 
+#include <regex.h>
+
+#include <vector>
+
 class pkgDepCache : protected pkgCache::Namespace
 {
    public:
+
+   /** \brief An arbitrary predicate on packages. */
+   class InRootSetFunc
+   {
+   public:
+     virtual bool InRootSet(const pkgCache::PkgIterator &pkg) {return false;};
+     virtual ~InRootSetFunc() {};
+   };
+
+   private:
+   /** \brief Mark a single package and all its unmarked important
+    *  dependencies during mark-and-sweep.
+    *
+    *  Recursively invokes itself to mark all dependencies of the
+    *  package.
+    *
+    *  \param pkg The package to mark.
+    *
+    *  \param ver The version of the package that is to be marked.
+    *
+    *  \param follow_recommends If \b true, recommendations of the
+    *  package will be recursively marked.
+    *
+    *  \param follow_suggests If \b true, suggestions of the package
+    *  will be recursively marked.
+    */
+   void MarkPackage(const pkgCache::PkgIterator &pkg,
+		    const pkgCache::VerIterator &ver,
+		    bool follow_recommends,
+		    bool follow_suggests);
+
+   /** \brief Update the Marked field of all packages.
+    *
+    *  Each package's StateCache::Marked field will be set to \b true
+    *  if and only if it can be reached from the root set.  By
+    *  default, the root set consists of the set of manually installed
+    *  or essential packages, but it can be extended using the
+    *  parameter #rootFunc.
+    *
+    *  \param rootFunc A callback that can be used to add extra
+    *  packages to the root set.
+    *
+    *  \return \b false if an error occured.
+    */
+   bool MarkRequired(InRootSetFunc &rootFunc);
+
+   /** \brief Set the StateCache::Garbage flag on all packages that
+    *  should be removed.
+    *
+    *  Packages that were not marked by the last call to #MarkRequired
+    *  are tested to see whether they are actually garbage.  If so,
+    *  they are marked as such.
+    *
+    *  \return \b false if an error occured.
+    */
+   bool Sweep();
+
+   public:
    
    // These flags are used in DepState
    enum DepFlags {DepNow = (1 << 0),DepInstall = (1 << 1),DepCVer = (1 << 2),
@@ -64,6 +126,83 @@ class pkgDepCache : protected pkgCache::Namespace
    enum VersionTypes {NowVersion, InstallVersion, CandidateVersion};
    enum ModeList {ModeDelete = 0, ModeKeep = 1, ModeInstall = 2};
 
+   /** \brief Represents an active action group.
+    *
+    *  An action group is a group of actions that are currently being
+    *  performed.  While an active group is active, certain routine
+    *  clean-up actions that would normally be performed after every
+    *  cache operation are delayed until the action group is
+    *  completed.  This is necessary primarily to avoid inefficiencies
+    *  when modifying a large number of packages at once.
+    *
+    *  This class represents an active action group.  Creating an
+    *  instance will create an action group; destroying one will
+    *  destroy the corresponding action group.
+    *
+    *  The following operations are suppressed by this class:
+    *
+    *    - Keeping the Marked and Garbage flags up to date.
+    *
+    *  \note This can be used in the future to easily accumulate
+    *  atomic actions for undo or to display "what apt did anyway";
+    *  e.g., change the counter of how many action groups are active
+    *  to a std::set of pointers to them and use those to store
+    *  information about what happened in a group in the group.
+    */
+   class ActionGroup
+   {
+       pkgDepCache &cache;
+
+       bool released;
+
+       /** Action groups are noncopyable. */
+       ActionGroup(const ActionGroup &other);
+   public:
+       /** \brief Create a new ActionGroup.
+	*
+	*  \param cache The cache that this ActionGroup should
+	*  manipulate.
+	*
+	*  As long as this object exists, no automatic cleanup
+	*  operations will be undertaken.
+	*/
+       ActionGroup(pkgDepCache &cache);
+
+       /** \brief Clean up the action group before it is destroyed.
+        *
+        *  If it is destroyed later, no second cleanup wil be run.
+	*/
+       void release();
+
+       /** \brief Destroy the action group.
+	*
+	*  If this is the last action group, the automatic cache
+	*  cleanup operations will be undertaken.
+	*/
+       ~ActionGroup();
+   };
+
+   /** \brief Returns \b true for packages matching a regular
+    *  expression in APT::NeverAutoRemove.
+    */
+   class DefaultRootSetFunc : public InRootSetFunc
+   {
+     std::vector<regex_t *> rootSetRegexp;
+     bool constructedSuccessfully;
+
+   public:
+     DefaultRootSetFunc();
+     ~DefaultRootSetFunc();
+
+     /** \return \b true if the class initialized successfully, \b
+      *  false otherwise.  Used to avoid throwing an exception, since
+      *  APT classes generally don't.
+      */
+     bool wasConstructedSuccessfully() const { return constructedSuccessfully; }
+
+     bool InRootSet(const pkgCache::PkgIterator &pkg);
+   };
+
    struct StateCache
    {
       // Epoch stripped text versions of the two version fields
@@ -80,8 +219,15 @@ class pkgDepCache : protected pkgCache::Namespace
       unsigned short Flags;
       unsigned short iFlags;           // Internal flags
 
-      // mark and sweep flags
+      /** \brief \b true if this package can be reached from the root set. */
       bool Marked;
+
+      /** \brief \b true if this package is unused and should be removed.
+       *
+       *  This differs from !#Marked, because it is possible that some
+       *  unreachable packages will be protected from becoming
+       *  garbage.
+       */
       bool Garbage;
 
       // Various tree indicators
@@ -124,6 +270,14 @@ class pkgDepCache : protected pkgCache::Namespace
       
       virtual ~Policy() {};
    };
+
+   private:
+   /** The number of open "action groups"; certain post-action
+    *  operations are suppressed if this number is > 0.
+    */
+   int group_level;
+
+   friend class ActionGroup;
      
    protected:
 
@@ -187,13 +341,61 @@ class pkgDepCache : protected pkgCache::Namespace
    inline StateCache &operator [](PkgIterator const &I) {return PkgState[I->ID];};
    inline unsigned char &operator [](DepIterator const &I) {return DepState[I->ID];};
 
-   // Manipulators
-   void MarkKeep(PkgIterator const &Pkg,bool Soft = false);
+   /** \return A function identifying packages in the root set other
+    *  than manually installed packages and essential packages, or \b
+    *  NULL if an error occurs.
+    *
+    *  \todo Is this the best place for this function?  Perhaps the
+    *  settings for mark-and-sweep should be stored in a single
+    *  external class?
+    */
+   virtual InRootSetFunc *GetRootSetFunc();
+
+   /** \return \b true if the garbage collector should follow recommendations.
+    */
+   virtual bool MarkFollowsRecommends();
+
+   /** \return \b true if the garbage collector should follow suggestions.
+    */
+   virtual bool MarkFollowsSuggests();
+
+   /** \brief Update the Marked and Garbage fields of all packages.
+    *
+    *  This routine is implicitly invoked after all state manipulators
+    *  and when an ActionGroup is destroyed.  It invokes #MarkRequired
+    *  and #Sweep to do its dirty work.
+    *
+    *  \param rootFunc A predicate that returns \b true for packages
+    *  that should be added to the root set.
+    */
+   bool MarkAndSweep(InRootSetFunc &rootFunc)
+   {
+     return MarkRequired(rootFunc) && Sweep();
+   }
+
+   bool MarkAndSweep()
+   {
+     std::auto_ptr<InRootSetFunc> f(GetRootSetFunc());
+     if(f.get() != NULL)
+       return MarkAndSweep(*f.get());
+     else
+       return false;
+   }
+
+   /** \name State Manipulators
+    */
+   // @{
+   void MarkKeep(PkgIterator const &Pkg, bool Soft = false,
+		 bool FromUser = true);
    void MarkDelete(PkgIterator const &Pkg,bool Purge = false);
    void MarkInstall(PkgIterator const &Pkg,bool AutoInst = true,
-		    unsigned long Depth = 0);
+		    unsigned long Depth = 0, bool FromUser = true);
    void SetReInstall(PkgIterator const &Pkg,bool To);
    void SetCandidateVersion(VerIterator TargetVer);
+
+   /** Set the "is automatically installed" flag of Pkg. */
+   void MarkAuto(const PkgIterator &Pkg, bool Auto);
+   // @}
    
    // This is for debuging
    void Update(OpProgress *Prog = 0);