Use the Boost hash table (unordered_set) to implement dep-solver memoization.

This almost eliminates the time we were spending comparing dep solvers
(according to profiling, it's now down to 5% of the run time).  There
are several parts to this commit:

  (1) Making Boost a dependency of aptitude.  This involved changing
      the configure script, writing a README about it, and writing a
      short shell script to verify that the configure script is up to
      date.

  (2) Redesigning the dep-solvers set so that all mutation goes through
      a member function.  The set needs to cache its hash value for the
      sake of speed, and having mutation go through member functions
      lets us invalidate the cache.

  (3) Writing hash functions for the major resolver structures (that
      is: the concrete package, version, dep, and tier objects in both
      implementations, the choice object, and the solver_information
      and dep_solvers objects in the search graph).

  (4) Changing the std::set that we were using to collect identical
      dep_solvers objects to a boost::unordered_set.

9 files changed, 334 insertions, 27 deletions

diff --git a/Makefile.am b/Makefile.am
index 505ea240..870f9ccc 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -27,6 +27,8 @@ pkgdata_DATA = $(TLHELPTXTS) COPYING NEWS FAQ \
 	function_groups function_pkgs aptitude-defaults section-descriptions \
 	$(TLDEFAULTS)
 
+TESTS = check_boost.sh
+
 install-data-local:
 	[ -d $(DESTDIR)$(STATEDIR) ] || $(mkinstalldirs) $(DESTDIR)$(STATEDIR)
 # FIXME: this really ought to use the autoconf directory variables
diff --git a/README.BOOST b/README.BOOST
new file mode 100644
index 00000000..b77e3761
--- /dev/null
+++ b/README.BOOST
@@ -0,0 +1,16 @@
+As of 2009-06-13, aptitude uses Boost.  Boost is a large collection of
+modern C++ libraries providing various utility code and algorithms; it
+should be available from the repositories of any modern Linux
+distribution, or from its home page at <http://www.boost.org>.
+
+The configure test for Boost attempts to verify that the correct
+version is installed by probing each header file that aptitude uses.
+However, it does not check that the header files provide the expected
+functionality; it is conceivable (though unlikely) that some versions
+of Boost would pass the configure check and fail at compile time.
+Running "make check" will verify that the set of headers mentioned in
+the configure script is exactly the same as the set of headers
+included from the source code.
+
+As of 2009-06-13, aptitude is known to compile and run successfully
+against the Debian package of Boost 1.38.1.
\ No newline at end of file
diff --git a/check_boost.sh b/check_boost.sh
new file mode 100755
index 00000000..abf563e2
--- /dev/null
+++ b/check_boost.sh
@@ -0,0 +1,45 @@
+#!/bin/bash -e
+
+# This script is invoked by "make check" to verify that we have
+# correctly declared the exact set of Boost include files that
+# "configure" should look for.
+#
+# Currently, this assumes that every occurrence of "boost/foo.hpp" is
+# significant.  If stray strings that look like that find their way
+# into the source code or configure, we'll have to look at #include
+# lines and/or mark off the section of configure with a tag (and,
+# e.g., use "awk" instead of "grep").
+
+echo "Verifying that the configure check tests the correct set of header files."
+
+BOOST_PATTERN='boost/[a-zA-Z0-9_.-]*\.hpp'
+
+# Check that the source code and the configure check look for the same
+# Boost headers.
+SRC_OCCURRENCES=$((find src -name \*.cc -or -name \*.h -print0; find tests -name \*.cc -or -name \*.h -print0) \
+                  | xargs -0 grep -h --only-matching "$BOOST_PATTERN" | sort -u)
+CONFIGURE_OCCURRENCES=$(grep -h --only-matching "$BOOST_PATTERN" configure.ac | sort -u)
+
+if ! cmp <(echo "$SRC_OCCURRENCES") <(echo "$CONFIGURE_OCCURRENCES")
+then
+    ONLY_SRC=$(comm -2 -3 <(echo "$SRC_OCCURRENCES") <(echo "$CONFIGURE_OCCURRENCES"))
+    ONLY_CONFIG=$(comm -1 -3 <(echo "$SRC_OCCURRENCES") <(echo "$CONFIGURE_OCCURRENCES"))
+    echo "Mismatch in Boost header file declarations."
+    if [ -n "$ONLY_SRC" ]
+    then
+	echo "The following headers occur only in the source code:"
+	echo "$ONLY_SRC"
+    fi
+    if [ -n "$ONLY_CONFIG" ]
+    then
+	echo "The following headers occur only in the configure script:"
+	echo "$ONLY_CONFIG"
+    fi
+
+    echo "*** BOOST CONFIGURE CHECK MISMATCH."
+    echo "*** Please update the configure script to match the source code."
+
+    exit 1
+fi
+
+exit 0
\ No newline at end of file
diff --git a/configure.ac b/configure.ac
index 8191aa80..de1dd510 100644
--- a/configure.ac
+++ b/configure.ac
@@ -52,6 +52,16 @@ PKG_CHECK_MODULES(LOG4CXX, liblog4cxx)
 
 PKG_CHECK_MODULES(VTE, vte)
 
+dnl Check for Boost headers.  Place each one on a line by itself and
+dnl write "dnl" at the end: the "dnl" deletes the newline, and without
+dnl it you'll get an error when you run the configure script.
+AC_CHECK_HEADERS( dnl
+boost/functional/hash.hpp dnl
+boost/unordered_set.hpp dnl
+                  ,
+		  ,
+		  [AC_MSG_FAILURE([Boost install not found, too old, or incomplete; install libboost-dev.])])
+
 HAVE_GTK=1
 AC_ARG_ENABLE(gtk,
 	AS_HELP_STRING(--disable-gtk, [don't compile the GTK+/gtkmm frontend even if the appropriate libraries are available]),
diff --git a/src/generic/apt/aptitude_resolver_universe.h b/src/generic/apt/aptitude_resolver_universe.h
index c3195d0f..4b7623de 100644
--- a/src/generic/apt/aptitude_resolver_universe.h
+++ b/src/generic/apt/aptitude_resolver_universe.h
@@ -26,6 +26,8 @@
 
 #include <cwidget/generic/util/eassert.h>
 
+#include <boost/functional/hash.hpp>
+
 #include "apt.h"
 #include "aptcache.h"
 
@@ -76,6 +78,12 @@ public:
     return pkg->ID;
   }
 
+  std::size_t get_hash_value() const
+  {
+    boost::hash<const pkgCache::Package *> hasher;
+    return hasher(pkg);
+  }
+
   /** \return The name of the package. */
   const char *get_name() const
   {
@@ -115,6 +123,11 @@ public:
   version_iterator versions_begin() const;
 };
 
+inline std::size_t hash_value(const aptitude_resolver_package &p)
+{
+  return p.get_hash_value();
+}
+
 /** \brief Translates a version of an apt package into the abstract
  *  realm.
  *
@@ -206,6 +219,12 @@ public:
     return aptitude_resolver_package(pkg, cache);
   }
 
+  std::size_t get_hash_value() const
+  {
+    boost::hash<const pkgCache::Version *> hasher;
+    return hasher(ver);
+  }
+
   /** \return \b true if this is the same version as other. */
   bool operator==(const aptitude_resolver_version &other) const
   {
@@ -245,6 +264,11 @@ public:
   dep_iterator deps_begin() const;
 };
 
+inline std::size_t hash_value(const aptitude_resolver_version &v)
+{
+  return v.get_hash_value();
+}
+
 inline aptitude_resolver_version aptitude_resolver_package::current_version() const
 {
   // Transmute removed-with-config-files packages into not-installed
@@ -344,6 +368,16 @@ public:
     return start->Type == pkgCache::Dep::Recommends;
   }
 
+  std::size_t get_hash_value() const
+  {
+    std::size_t rval = 0;
+    boost::hash_combine(rval, (const pkgCache::Dependency *)start);
+    if(is_conflict(start->Type))
+      boost::hash_combine(rval, (const pkgCache::Provides *)prv);
+
+    return rval;
+  }
+
   /** \brief Compare two dependencies for equality. */
   bool operator==(const aptitude_resolver_dep &other) const
   {
@@ -419,6 +453,11 @@ public:
   solver_iterator solvers_begin() const;
 };
 
+inline std::size_t hash_value(const aptitude_resolver_dep &d)
+{
+  return d.get_hash_value();
+}
+
 /** \brief Iterate over the versions of a package.
  *
  *  \sa aptitude_resolver_package, aptitude_resolver_version
@@ -961,6 +1000,15 @@ public:
       entries[1] = apt_priority;
     }
 
+    std::size_t get_hash_value() const
+    {
+      std::size_t rval = 0;
+      boost::hash_combine(rval, entries[0]);
+      boost::hash_combine(rval, entries[1]);
+
+      return rval;
+    }
+
     int get_policy() const { return entries[0]; }
     int apt_priority() const { return entries[1]; }
 
@@ -1267,6 +1315,11 @@ public:
   static std::string get_tier_name(const tier &t);
 };
 
+inline std::size_t hash_value(const aptitude_universe::tier &t)
+{
+  return t.get_hash_value();
+}
+
 /** \brief Write an aptitude_resolver_package to the given stream. */
 std::ostream &operator<<(ostream &out, const aptitude_resolver_package &p);
 
diff --git a/src/generic/problemresolver/choice.h b/src/generic/problemresolver/choice.h
index 7b4596df..6405fdf0 100644
--- a/src/generic/problemresolver/choice.h
+++ b/src/generic/problemresolver/choice.h
@@ -26,6 +26,8 @@
 
 #include <generic/util/compare3.h>
 
+#include <boost/functional/hash.hpp>
+
 /** \brief Represents a decision made by the resolver.
  *
  *  This is used to keep track of which choices imply that we end up
@@ -343,8 +345,38 @@ public:
   {
     return d;
   }
+
+  /** \brief Compute a hash value on choices. */
+  std::size_t get_hash_value() const
+  {
+    std::size_t rval = 0;
+    boost::hash_combine(rval, tp);
+    switch(tp)
+      {
+      case install_version:
+	boost::hash_combine(rval, ver);
+	boost::hash_combine(rval, from_dep_source);
+	boost::hash_combine(rval, has_dep);
+
+	if(has_dep)
+	  boost::hash_combine(rval, d);
+	break;
+
+      case break_soft_dep:
+	boost::hash_combine(rval, d);
+	break;
+      }
+
+    return rval;
+  }
 };
 
+template<typename PackageUniverse>
+std::size_t hash_value(const generic_choice<PackageUniverse> &c)
+{
+  return c.get_hash_value();
+}
+
 // Overload compare3 on choices.
 namespace aptitude
 {
diff --git a/src/generic/problemresolver/dummy_universe.h b/src/generic/problemresolver/dummy_universe.h
index f887cc7c..5832c804 100644
--- a/src/generic/problemresolver/dummy_universe.h
+++ b/src/generic/problemresolver/dummy_universe.h
@@ -30,6 +30,8 @@
 #include <cwidget/generic/util/eassert.h>
 #include <cwidget/generic/util/exception.h>
 
+#include <boost/functional/hash.hpp>
+
 /** \brief A package dependency universe
  *
  * 
@@ -314,6 +316,12 @@ public:
 
     typedef wrap_ptr_iter<dummy_version, version> version_iterator;
 
+    std::size_t get_hash_value() const
+    {
+      boost::hash<const dummy_package *> hasher;
+      return hasher(real_package);
+    }
+
     bool operator==(const package &other) const
     {
       return real_package==other.real_package;
@@ -368,6 +376,12 @@ public:
     {
     }
 
+    std::size_t get_hash_value() const
+    {
+      boost::hash<const dummy_version *> hasher;
+      return hasher(real_version);
+    }
+
     bool operator==(const version &other) const
     {
       return real_version==other.real_version;
@@ -433,6 +447,12 @@ public:
       return real_dep->is_soft();
     }
 
+    std::size_t get_hash_value() const
+    {
+      boost::hash<const dummy_dep *> hasher;
+      return hasher(real_dep);
+    }
+
     bool operator==(const dep &other) const
     {
       return real_dep==other.real_dep;
@@ -496,6 +516,12 @@ public:
     {
     }
 
+    std::size_t get_hash_value() const
+    {
+      boost::hash<std::vector<int> > hasher;
+      return hasher(values);
+    }
+
     typedef std::vector<int>::const_iterator const_iterator;
 
     const_iterator begin() const { return values.begin(); }
@@ -678,6 +704,26 @@ public:
   }
 };
 
+inline std::size_t hash_value(const dummy_universe::package &p)
+{
+  return p.get_hash_value();
+}
+
+inline std::size_t hash_value(const dummy_universe::version &v)
+{
+  return v.get_hash_value();
+}
+
+inline std::size_t hash_value(const dummy_universe::dep &d)
+{
+  return d.get_hash_value();
+}
+
+inline std::size_t hash_value(const dummy_universe::tier &t)
+{
+  return t.get_hash_value();
+}
+
 // A refcounting wrapper for a dummy_universe; used to sanitize memory
 // management without copying all over (and because the resolver
 // expects to be able to have a full copy of its argument type)
diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h
index ffe3de98..a5a00d58 100644
--- a/src/generic/problemresolver/problemresolver.h
+++ b/src/generic/problemresolver/problemresolver.h
@@ -70,6 +70,8 @@
 
 #include <generic/util/dense_setset.h>
 
+#include <boost/unordered_set.hpp>
+
 /** \brief Generic problem resolver
  *
  * 
@@ -1062,14 +1064,14 @@ private:
    *  (if every instance of a solver set was changed, that solver set
    *  would be dropped).
    */
-  std::set<typename step::dep_solvers> memoized_dep_solvers;
+  boost::unordered_set<typename step::dep_solvers> memoized_dep_solvers;
 
   typename step::dep_solvers memoize_dep_solvers(const typename step::dep_solvers &solvers)
   {
     // std::set will insert a new element only if it doesn't already
     // contain an element with the same key, which is exactly what we
     // want here.
-    std::pair<typename std::set<typename step::dep_solvers>::const_iterator, bool>
+    std::pair<typename boost::unordered_set<typename step::dep_solvers>::const_iterator, bool>
       insert_result = memoized_dep_solvers.insert(solvers);
 
     if(insert_result.second)
@@ -1616,19 +1618,19 @@ private:
 	      << s.step_num << " that are solved by " << c_general);
   }
 
-  class add_to_choice_list
+  class add_to_structural_reasons
   {
-    imm::list<choice> &target;
+    typename step::dep_solvers &target;
 
   public:
-    add_to_choice_list(imm::list<choice> &_target)
+    add_to_structural_reasons(typename step::dep_solvers &_target)
       : target(_target)
     {
     }
 
     bool operator()(const choice &c) const
     {
-      target.push_front(c);
+      target.add_structural_reason(c);
       return true;
     }
   };
@@ -1703,8 +1705,8 @@ private:
 			<< " in step " << s.step_num
 			<< ", new solvers: " << new_solvers.get_solvers());
 
-	      new_solvers.get_solvers().erase(victim_with_dep);
-	      add_to_choice_list adder(new_solvers.get_structural_reasons());
+	      new_solvers.remove_solver(victim_with_dep);
+	      add_to_structural_reasons adder(new_solvers);
 	      reasons.for_each(adder);
 
 	      // Actually update the solvers of the dep.
@@ -1997,7 +1999,7 @@ private:
     if(found_solvers.isValid())
       {
 	typename step::dep_solvers new_dep_solvers(found_solvers.getVal().second);
-	imm::map<choice, typename step::solver_information, compare_choices_by_effects> &
+	const imm::map<choice, typename step::solver_information, compare_choices_by_effects> &
 	  new_solvers(new_dep_solvers.get_solvers());
 
 	typename imm::map<choice, typename step::solver_information, compare_choices_by_effects>::node
@@ -2021,7 +2023,7 @@ private:
 			     choice_set(),
 			     new_tier_valid,
 			     new_tier_is_deferred);
-	    new_solvers.put(solver_with_dep, new_solver_inf);
+	    new_dep_solvers.set_solver_information(solver_with_dep, new_solver_inf);
 	    s.unresolved_deps.put(solver_dep, memoize_dep_solvers(new_dep_solvers));
 	    LOG_TRACE(logger, "Recomputed the tier of "
 		      << solver << " in the solver list of "
@@ -2170,7 +2172,7 @@ private:
 			  << ": monotonicity violation due to "
 			  << selected);
 		choice reason(choice::make_install_version(selected, -1));
-		solvers.get_structural_reasons().push_front(reason);
+		solvers.add_structural_reason(reason);
 	      }
 
 	    return; // If the package is already modified, abort.
@@ -2188,7 +2190,7 @@ private:
 			  "Not adding " << solver
 			  << ": it is forbidden due to the action "
 			  << reason);
-		solvers.get_structural_reasons().push_front(reason);
+		solvers.add_structural_reason(reason);
 
 		return;
 	      }
@@ -2211,7 +2213,7 @@ private:
 		       choice_set(),
 		       choice_tier_valid,
 		       choice_is_deferred);
-      solvers.get_solvers().put(solver, new_solver_inf);
+      solvers.set_solver_information(solver, new_solver_inf);
     }
 
     // Update the deps-solved-by-choice map (add the dep being
@@ -2467,7 +2469,7 @@ private:
 				new_choices,
 				valid_condition,
 				old_inf.get_is_deferred_listener());
-		      new_solvers.get_solvers().put(solver_with_dep, new_inf);
+		      new_solvers.set_solver_information(solver_with_dep, new_inf);
 
 		      s.unresolved_deps.put(d, resolver.memoize_dep_solvers(new_solvers));
 		      resolver.check_solvers_tier(s, new_solvers);
diff --git a/src/generic/problemresolver/search_graph.h b/src/generic/problemresolver/search_graph.h
index 51c62761..79b9b96f 100644
--- a/src/generic/problemresolver/search_graph.h
+++ b/src/generic/problemresolver/search_graph.h
@@ -34,6 +34,8 @@
 #include <generic/util/immlist.h>
 #include <generic/util/immset.h>
 
+#include <boost/functional/hash.hpp>
+
 // solver_information and dep_solvers are top-level declarations so
 // they can easily get an operator<< that works.
 
@@ -47,6 +49,7 @@ class generic_solver_information
 {
 public:
   typedef typename PackageUniverse::tier tier;
+  typedef generic_choice<PackageUniverse> choice;
   typedef generic_choice_set<PackageUniverse> choice_set;
   typedef generic_tier_limits<PackageUniverse> tier_limits;
 
@@ -56,6 +59,23 @@ private:
   cwidget::util::ref_ptr<expression<bool> > tier_valid;
   cwidget::util::ref_ptr<expression_box<bool> > is_deferred_listener;
 
+  class combine_reason_hashes
+  {
+    std::size_t &target;
+  public:
+    combine_reason_hashes(std::size_t &_target)
+      : target(_target)
+    {
+    }
+
+    bool operator()(const choice &c) const
+    {
+      boost::hash_combine(target, c);
+
+      return true;
+    }
+  };
+
 public:
   generic_solver_information()
     : t(tier_limits::minimum_tier),
@@ -129,6 +149,17 @@ public:
       return cwidget::util::ref_ptr<expression<bool> >();
   }
 
+  std::size_t get_hash_value() const
+  {
+    std::size_t rval = 0;
+    boost::hash_combine(rval, tier_valid.unsafe_get_ref());
+    boost::hash_combine(rval, is_deferred_listener.unsafe_get_ref());
+    boost::hash_combine(rval, t);
+    reasons.for_each(combine_reason_hashes(rval));
+
+    return rval;
+  }
+
   /** \brief Compare two solver_information objects.
    *
    *  solver_informations are compared according to their fields.
@@ -170,6 +201,12 @@ public:
   }
 };
 
+template<typename PackageUniverse>
+std::size_t hash_value(const generic_solver_information<PackageUniverse> &inf)
+{
+  return inf.get_hash_value();
+}
+
 /** \brief A structure that tracks the state of the solvers of a
  *  dependency.
  */
@@ -183,18 +220,84 @@ public:
 private:
   imm::map<choice, generic_solver_information<PackageUniverse>, compare_choices_by_effects> solvers;
   imm::list<choice> structural_reasons;
+  mutable std::size_t hash_cache;
+  mutable bool hash_dirty;
+
+  class hash_choices
+  {
+    std::size_t &hash_val;
+  public:
+    hash_choices(std::size_t &_hash_val)
+      : hash_val(_hash_val)
+    {
+    }
+
+    bool operator()(const std::pair<choice, generic_solver_information<PackageUniverse> > &p) const
+    {
+      boost::hash_combine(hash_val, p);
+
+      return true;
+    }
+  };
 
 public:
   generic_dep_solvers()
   {
   }
 
-  /** \brief Return the outstanding solvers of this dependency and
-   *  the current state of each one.
-   */
-  imm::map<choice, generic_solver_information<PackageUniverse>, compare_choices_by_effects> &get_solvers()
+  generic_dep_solvers(const imm::map<choice, generic_solver_information<PackageUniverse>, compare_choices_by_effects> &_solvers,
+		      const imm::list<choice> &_structural_reasons)
+    : solvers(_solvers), structural_reasons(_structural_reasons),
+      hash_dirty(true)
   {
-    return solvers;
+  }
+
+  std::size_t get_hash_value() const
+  {
+    if(hash_dirty)
+      {
+	hash_cache = 0;
+	// Correctness of just iterating the solver set relies on the
+	// fact that imm::map places keys in sorted order.
+	solvers.for_each(hash_choices(hash_cache));
+	// Try to avoid any confusion caused by mixing the structural
+	// reasons with the solvers.
+	boost::hash_combine(hash_cache, 987654321);
+	for(typename imm::list<choice>::const_iterator it = structural_reasons.begin();
+	    it != structural_reasons.end(); ++it)
+	  boost::hash_combine(hash_cache, *it);
+
+	hash_dirty = false;
+      }
+
+    return hash_cache;
+  }
+
+  /** \brief Manipulators. */
+
+  // @{
+  void add_structural_reason(const choice &c)
+  {
+    hash_dirty = true;
+    structural_reasons.push_front(c);
+  }
+
+  void set_solver_information(const choice &c, const generic_solver_information<PackageUniverse> &solver)
+  {
+    hash_dirty = true;
+    solvers.put(c, solver);
+  }
+
+  void remove_solver(const choice &c)
+  {
+    hash_dirty = true;
+    solvers.erase(c);
+  }
+  // @}
+
+  bool operator==(const generic_dep_solvers &other) const
+  {
+    return solvers == other.solvers && structural_reasons == other.structural_reasons;
   }
 
   /** \brief Return the outstanding solvers of this dependency and
@@ -208,14 +311,6 @@ public:
   /** \brief Return the reasons that the set of solvers for this
    *  dependency was narrowed.
    */
-  imm::list<choice> &get_structural_reasons()
-  {
-    return structural_reasons;
-  }
-
-  /** \brief Return the reasons that the set of solvers for this
-   *  dependency was narrowed.
-   */
   const imm::list<choice> &get_structural_reasons() const
   {
     return structural_reasons;
@@ -242,6 +337,12 @@ public:
   }
 };
 
+template<typename PackageUniverse>
+std::size_t hash_value(const generic_dep_solvers<PackageUniverse> &dep_solvers)
+{
+  return dep_solvers.get_hash_value();
+}
+
 /** \brief Represents the current search graph.
  *
  *  This structure and its operations track all the visited search