Initial implementation of a tiering system that is both sound and flexible.

The rule in this system is that you can increase tier levels either
by adding positive numbers to them or by lower-bounding them.  Any given
slot in the tier has to be managed using only one of these operations,
but different slots can be managed using different operations.  This
allows support for the new "add to tier" operation, while maintaining
the ability to do the old "increase to level" operation (both for
backwards-compatibility and for supporting pin priorities).

Currently the unit tests fail; this needs to be fixed.

5 files changed, 630 insertions, 321 deletions

diff --git a/src/generic/problemresolver/exceptions.h b/src/generic/problemresolver/exceptions.h
index db27b47f..f680ac8e 100644
--- a/src/generic/problemresolver/exceptions.h
+++ b/src/generic/problemresolver/exceptions.h
@@ -96,13 +96,13 @@ class DoubleRunException : public ProblemResolverError {
   }
 };
 
-/** An exception indicating that something tried to add a negative
+/** An exception indicating that something tried to add a nonpositive
  *  quantity to a tier.
  */
-class NegativeTierAdditionException : public ProblemResolverError {
+class NonPositiveTierAdditionException : public ProblemResolverError {
   std::string errmsg() const
   {
-    return _("Tier increments must be nonnegative.");
+    return _("Tier increments must be strictly positive.");
   }
 };
 
@@ -115,4 +115,14 @@ class TierTooBigException : public ProblemResolverError {
   }
 };
 
+/** An exception indicating that incompatible operations were applied
+ *  to a tier.
+ */
+class TierOperationMismatchException : public ProblemResolverError {
+  std::string errmsg() const
+  {
+    return _("A single tier level was both added and lower-bounded.");
+  }
+};
+
 #endif // EXCEPTIONS_H
diff --git a/src/generic/problemresolver/tier.cc b/src/generic/problemresolver/tier.cc
index 0550d879..c2369d5f 100644
--- a/src/generic/problemresolver/tier.cc
+++ b/src/generic/problemresolver/tier.cc
@@ -22,6 +22,18 @@
 
 #include <iostream>
 
+std::ostream &operator<<(std::ostream &out, const level &l)
+{
+  if(l.get_value() == tier_limits::minimum_level)
+    out << "minimum";
+  else if(l.get_value() == tier_limits::maximum_level)
+    out << "maximum";
+  else
+    out << l.get_value();
+
+  return out;
+}
+
 std::ostream &operator<<(std::ostream &out, const tier &t)
 {
   out << "(";
@@ -41,17 +53,7 @@ std::ostream &operator<<(std::ostream &out, const tier &t)
 
   for(tier::user_level_iterator it = t.user_levels_begin();
       it != t.user_levels_end(); ++it)
-    {
-      out << ", ";
-      const int user_level = *it;
-
-      if(user_level == tier_limits::minimum_level)
-	out << "minimum";
-      else if(user_level == tier_limits::maximum_level)
-	out << "maximum";
-      else
-	out << user_level;
-    }
+    out << ", " << *it;
 
   out << ")";
 
diff --git a/src/generic/problemresolver/tier.h b/src/generic/problemresolver/tier.h
index 52f8fb48..02d34266 100644
--- a/src/generic/problemresolver/tier.h
+++ b/src/generic/problemresolver/tier.h
@@ -31,15 +31,240 @@
 
 #include <limits.h>
 
+#include "exceptions.h"
+
+/** \brief Represents one level in a search tier.
+ *
+ *  A search tier is an ordered sequence of levels.  Levels are
+ *  integers that can be modified either by being incremented or by
+ *  being increased to be at least the given value.  However, the two
+ *  operations may not be applied to the same level; attempting to do
+ *  so will raise an exception.  This does not apply to the identity
+ *  of each operation (adding 0 or raising to INT_MIN).
+ *
+ *  The reason for representing levels this way is that it allows the
+ *  resolver to support both "increase the tier to X" and "add X to
+ *  the tier" operations in a sound manner; in particular, this way
+ *  those two operations are both associative and commutative.  (in
+ *  this case, they are associative and commutative in the sense that
+ *  applying both types of operations always errors out)
+ *
+ *  Note: the "increase tier to X" operation is important for
+ *  respecting priorities (there doesn't seem to be an obvious
+ *  alternative there), for backwards-compatibility, and so that the
+ *  resolver can easily become non-optimizing if necessary (e.g., if
+ *  the optimizing version experiences too many performance problems,
+ *  reverting to the old behavior is a simple change to the default
+ *  settings).
+ *
+ *  Note that levels can represent both a tier entry, or a *change* to
+ *  a tier entry.  The "combine" method will either merge two changes
+ *  into a single change, or apply a change to a level.
+ *
+ *  Instead of failing out when two different operations are applied,
+ *  I could instead resolve the conflict by accumulating lower-bounds
+ *  separately from increments and always applying lower-bounds first.
+ *  That would resolve the conflict, but it might produce a somewhat
+ *  unintuitive result for the user.  I've chosen this route because
+ *  at least the behavior is obvious (and I can't think of any use
+ *  case for actually merging lower-bounds and increments).
+ */
+class level
+{
+public:
+  // The level's state; if it's ever been modified, this tracks how it
+  // was modified.
+  enum state_enum { unmodified, added, lower_bounded };
+
+private:
+  // Note: I would use a single iinteger if I thought I could get away
+  // with it.
+
+  // Note 2: the reason for using signed integers is that it makes the
+  // case of policy-priorities-as-tiers a bit clearer.
+
+  int value;
+
+  state_enum state;
+
+  level(int _value, state_enum _state)
+    : value(_value), state(_state)
+  {
+  }
+
+public:
+  /** \brief Create a new level at the minimum tier. */
+  level() : value(INT_MIN), state(unmodified)
+  {
+  }
+
+  /** \brief Create a new level with the given value and state "added". */
+  static level make_added(int value)
+  {
+    return level(value, added);
+  }
+
+  /** \brief Create a new level with the given value and state "lower_bounded." */
+  static level make_lower_bounded(int value)
+  {
+    return level(value, lower_bounded);
+  }
+
+  int get_value() const { return value; }
+  state_enum get_state() const { return state; }
+
+  void increase_tier_to(int new_value)
+  {
+    if(state == added)
+      throw TierOperationMismatchException();
+    else if(new_value != INT_MIN)
+      {
+	if(value < new_value)
+	  value = new_value;
+	state = lower_bounded;
+      }
+  }
+
+  void add(int amt)
+  {
+    if(state == lower_bounded)
+      throw TierOperationMismatchException();
+    else if(amt <= 0)
+      throw NonPositiveTierAdditionException();
+    else if(amt != 0)
+      {
+	value += amt;
+	state = added;
+      }
+  }
+
+  /** \brief Combine two levels and return a new level.
+   *
+   *  If either input level is unmodified, the result is the other
+   *  level.  Otherwise, the two levels must have the same state, and
+   *  the levels are combined according to that state.
+   */
+  static level combine(const level &l1, const level &l2)
+  {
+    if(l1.state == unmodified)
+      return l2;
+    else if(l2.state == unmodified)
+      return l1;
+    else if(l1.state != l2.state)
+      throw TierOperationMismatchException();
+    else if(l1.state == lower_bounded)
+      return level(std::max<int>(l1.value, l2.value), lower_bounded);
+    else // if(l1.state == added)
+      {
+	if(!(l1.value > 0 || l2.value > 0))
+	  throw NonPositiveTierAdditionException();
+	else
+	  return level(l1.value + l2.value, added);
+      }
+  }
+
+  /** \brief Compute the upper bound of two levels.
+   *
+   *  If the levels have incompatible states, throws an exception;
+   *  otherwise, returns a level whose numerical value is the maximum
+   *  of the numerical values of the two input levels and whose type
+   *  is the upper-bound of their types.
+   */
+  static level upper_bound(const level &l1, const level &l2)
+  {
+    if(l1.state == unmodified)
+      return l2;
+    else if(l2.state == unmodified)
+      return l1;
+    else if(l1.state != l2.state)
+      throw TierOperationMismatchException();
+    else
+      return level(std::max<int>(l1.value, l2.value),
+		   l1.state);
+  }
+
+  /** \brief Compute the lower bound of two levels.
+   *
+   *  If the levels have incompatible states, throws an exception; if
+   *  either is "unmodified", returns an unmodified level; otherwise,
+   *  returns a level whose numerical value is the minimum of the
+   *  numerical values of the two input levels and whose type is the
+   *  lower-bound of their types.
+   */
+  static level lower_bound(const level &l1, const level &l2)
+  {
+    if(l1.state == unmodified || l2.state == unmodified)
+      return level();
+    else if(l1.state != l2.state)
+      throw TierOperationMismatchException();
+    else
+      return level(std::min<int>(l1.value, l2.value),
+		   l1.state);
+  }
+
+  /** \brief Compare two levels.
+   *
+   *  Only the value of each level is compared.  The additional
+   *  information is discarded, so this should not be used to build an
+   *  associative data structure where that information might matter.
+   */
+  int compare(const level &other) const
+  {
+    return aptitude::util::compare3(value, other.value);
+  }
+
+  /** \brief Hashes a level object. */
+  std::size_t get_hash_value() const
+  {
+    std::size_t rval = 0;
+
+    boost::hash_combine(rval, value);
+    boost::hash_combine(rval, state);
+
+    return rval;
+  }
+
+  /** \brief Returns \b true if two levels are identical (both value
+   *  and state).
+   */
+  bool operator==(const level &other) const
+  {
+    return value == other.value && state == other.state;
+  }
+};
+
+std::ostream &operator<<(std::ostream &out, const level &l);
+
+inline std::size_t hash_value(const level &l)
+{
+  return l.get_hash_value();
+}
+
+namespace aptitude
+{
+  namespace util
+  {
+    template<>
+    class compare3_f<level>
+    {
+    public:
+      int operator()(const level &t1, const level &t2) const
+      {
+	return t1.compare(t2);
+      }
+    };
+  }
+}
+
 /** \brief Represents the tier of a search node.
  *
  *  The resolver is \e guaranteed to produce solutions in increasing
  *  order by tier.  This is as opposed to score, which is merely used
  *  in a best-effort manner.
  *
- *  A tier is simply a sequence of integers, each of which is known as
- *  a "level".  By convention, each tier in a search should have the
- *  same length; tiers are compared lexicographically.
+ *  A tier is a sequence of levels (as defined above).  By convention,
+ *  each tier in a search should have the same length; tiers are
+ *  compared lexicographically.
  *
  *  The first level in the tier is reserved by the resolver to store
  *  "structural" priorities (for instance, to mark nodes as conflicted
@@ -53,11 +278,12 @@ class tier
   struct tier_impl
   {
     // Level set by the resolver itself to control the search
-    // algorithm.
+    // algorithm.  This is always increased in an upper-bound / cutoff
+    // fashion.
     int structural_level;
 
     // Levels set by client code to customize the search order.
-    std::vector<int> user_levels;
+    std::vector<level> user_levels;
 
     // Cache the hash value.  Initialized during construction.
     std::size_t hash_value;
@@ -98,38 +324,12 @@ class tier
       hash_value = get_hash_value();
     }
 
-    /** \brief Initialize a tier object given its contents and a
-     *         change to the list of user levels (possibly extending
-     *         the list in the process).
-     */
-    template<typename Iterator>
-    tier_impl(int _structural_level,
-	      Iterator user_levels_begin, Iterator user_levels_end,
-	      int change_location,
-	      int new_value)
-      : structural_level(_structural_level),
-	user_levels(user_levels_begin, user_levels_end),
-	hash_value(0)
-    {
-      if(static_cast<std::vector<int>::size_type>(change_location) >= user_levels.size())
-	{
-	  user_levels.reserve(change_location);
-	  user_levels.insert(user_levels.end(),
-			     change_location - user_levels.size(),
-			     INT_MIN);
-	  user_levels.push_back(new_value);
-	}
-      else
-	user_levels[change_location] = new_value;
-      hash_value = get_hash_value();
-    }
-
     std::size_t get_hash_value() const
     {
       std::size_t rval = 0;
 
       boost::hash_combine(rval, structural_level);
-      for(std::vector<int>::const_iterator it = user_levels.begin();
+      for(std::vector<level>::const_iterator it = user_levels.begin();
 	  it != user_levels.end(); ++it)
 	boost::hash_combine(rval, *it);
 
@@ -241,38 +441,10 @@ public:
 					      impl.user_levels.end()));
   }
 
-  /** \brief Create a new tier object in which one of this object's
-   *  user levels has been modified.
-   *
-   *  \param location A zero-based index into the list of user levels.
-   *
-   *  \param new_value The new level to store in the list in that
-   *                   location.
-   *
-   *  If location is greater than or equal to get_num_user_levels(),
-   *  the user level list is automatically extended to the appropriate
-   *  length.  Intervening levels are set to
-   *  tier_limits::minimum_tier.
-   *
-   *  \return a tier object with the same structural level as this
-   *          object whose user levels are identical to this object's,
-   *          except that the level in slot "location" has been set to
-   *          new_value.
-   */
-  tier set_user_level(int location, int new_value) const
-  {
-    const tier_impl &impl(get_impl());
-
-    return tier(boost::make_shared<tier_impl>(impl.structural_level,
-					      impl.user_levels.begin(),
-					      impl.user_levels.end(),
-					      location, new_value));
-  }
-
   /** \brief Retrieve the value of the structural level slot. */
   int get_structural_level() const { return get_impl().structural_level; }
 
-  typedef std::vector<int>::const_iterator user_level_iterator;
+  typedef std::vector<level>::const_iterator user_level_iterator;
 
   /** \brief Get a reference to the first user level as a
    *  random-access iterator.
@@ -284,7 +456,7 @@ public:
   user_level_iterator user_levels_end() const { return get_impl().user_levels.end(); }
 
   /** \brief Retrieve one user level from this tier. */
-  int get_user_level(int index) const { return get_impl().user_levels[index]; }
+  const level &get_user_level(int index) const { return get_impl().user_levels[index]; }
 
   /** \brief Retrieve the number of user levels in this tier. */
   std::size_t get_num_user_levels() const { return get_impl().user_levels.size(); }
@@ -301,6 +473,10 @@ public:
     return *this;
   }
 
+  /** \brief Compare two tiers.
+   *
+   *  Tiers are compared lexicographically, ignoring level states.
+   */
   int compare(const tier &other) const
   {
     const tier_impl &impl(get_impl());
diff --git a/src/generic/problemresolver/tier_operation.cc b/src/generic/problemresolver/tier_operation.cc
index bca6a764..8d8ac5fc 100644
--- a/src/generic/problemresolver/tier_operation.cc
+++ b/src/generic/problemresolver/tier_operation.cc
@@ -22,186 +22,200 @@
 
 #include <ostream>
 
-void tier_operation::normalize()
+tier_operation::op_impl::op_impl(const op_impl &op1, const op_impl &op2, combine_tag)
+  : structural_level(std::max<int>(op1.structural_level,
+				   op2.structural_level))
 {
-  if(add_levels.get_num_user_levels() > 0 &&
-     add_levels.get_user_level(add_levels.get_num_user_levels() - 1) == 0)
-    {
-      tier::user_level_iterator
-        begin = add_levels.user_levels_begin(),
-        end = add_levels.user_levels_end();
-
-      while(end > begin && end[-1] == 0)
-        --end;
+  // Straightforward merge (why doesn't STL have a merge that lets
+  // you combine equivalent elements instead of just copying one
+  // of them to the output?
+  std::vector<std::pair<level_index, level> >::const_iterator
+    it1 = op1.actions.begin(), it2 = op2.actions.begin();
 
-      add_levels = tier(add_levels.get_structural_level(), begin, end);
+  while(it1 != op1.actions.end() && it2 != op2.actions.end())
+    {
+      if(it1->first < it2->first)
+	{
+	  actions.push_back(*it1);
+	  ++it1;
+	}
+      else if(it2->first < it1->first)
+	{
+	  actions.push_back(*it2);
+	  ++it2;
+	}
+      else
+	{
+	  actions.push_back(std::make_pair(it1->first,
+					   level::combine(it1->second, it2->second)));
+	  ++it1;
+	  ++it2;
+	}
     }
+
+  if(it1 != op1.actions.end())
+    actions.insert(actions.end(), it1, op1.actions.end());
+  else if(it2 != op2.actions.end())
+    actions.insert(actions.end(), it2, op2.actions.end());
 }
 
-tier tier_operation::levelwise_maximum(const tier &t1, const tier &t2)
+tier tier_operation::op_impl::apply(const tier &t) const
 {
-  const int out_structural_level =
-    std::max<int>(t1.get_structural_level(),
-                  t2.get_structural_level());
-
-  std::vector<int> out_user_levels;
-  out_user_levels.reserve(std::max<std::size_t>(t1.get_num_user_levels(),
-                                                t2.get_num_user_levels()));
-
-  tier::user_level_iterator
-    it1 = t1.user_levels_begin(),
-    it2 = t2.user_levels_begin();
-
-  const tier::user_level_iterator
-    end1 = t1.user_levels_end(),
-    end2 = t2.user_levels_end();
+  int out_structural_level =
+    std::max<int>(t.get_structural_level(), structural_level);
+  std::vector<level> out_user_levels(t.user_levels_begin(), t.user_levels_end());
 
-  while(it1 != end1 && it2 != end2)
+  if(!actions.empty())
     {
-      out_user_levels.push_back(std::max<int>(*it1, *it2));
-      ++it1;
-      ++it2;
+      // If the actions array will modify slots off the end of the
+      // tier's list of levels, we first pre-extend that list.
+      if(out_user_levels.size() <= actions.back().first)
+	{
+	  level_index
+	    gap_size = actions.back().first + 1 - out_user_levels.size();
+
+	  out_user_levels.insert(out_user_levels.end(),
+				 gap_size,
+				 level());
+	}
+
+      for(std::vector<std::pair<level_index, level> >::const_iterator it =
+	    actions.begin(); it != actions.end(); ++it)
+	{
+	  level &target(out_user_levels[it->first]);
+	  target = level::combine(target, it->second);
+	}
     }
 
-  if(it1 != end1)
-    out_user_levels.insert(out_user_levels.end(),
-                           it1, end1);
-  else if(it2 != end2)
-    out_user_levels.insert(out_user_levels.end(),
-                           it2, end2);
-
   return tier(out_structural_level,
-              out_user_levels.begin(),
-              out_user_levels.end());
+	      out_user_levels.begin(),
+	      out_user_levels.end());
 }
 
-tier tier_operation::levelwise_minimum(const tier &t1, const tier &t2)
+void tier_operation::op_impl::dump(std::ostream &out) const
 {
-  const int out_structural_level =
-    std::min<int>(t1.get_structural_level(),
-                  t2.get_structural_level());
-
-  std::vector<int> out_user_levels;
-  out_user_levels.reserve(std::min<std::size_t>(t1.get_num_user_levels(),
-                                                t2.get_num_user_levels()));
-
-  tier::user_level_iterator
-    it1 = t1.user_levels_begin(),
-    it2 = t2.user_levels_begin();
-
-  const tier::user_level_iterator
-    end1 = t1.user_levels_end(),
-    end2 = t2.user_levels_end();
-
-  while(it1 != end1 && it2 != end2)
+  out << "(";
+  if(structural_level != INT_MIN)
+    out << "advance: " << structural_level;
+  else
+    out << "nop";
+
+  std::size_t column = 0;
+  for(std::vector<std::pair<level_index, level> >::const_iterator
+	it = actions.begin(); it != actions.end(); ++it)
     {
-      out_user_levels.push_back(std::min<int>(*it1, *it2));
-      ++it1;
-      ++it2;
+      out << ", ";
+
+      while(column < it->first)
+	{
+	  out << "nop, ";
+	  ++column;
+	}
+
+      switch(it->second.get_state())
+	{
+	case level::added:
+	  out << "add: ";
+	  break;
+	case level::lower_bounded:
+	  out << "advance: ";
+	  break;
+	case level::unmodified:
+	  // Shouldn't happen:
+	  out << "(unmodified): ";
+	  break;
+	}
+      out << it->second.get_value();
     }
 
-  return tier(out_structural_level,
-              out_user_levels.begin(),
-              out_user_levels.end());
-}
-
-inline int tier_operation::safe_add_levels(int l1, int l2)
-{
-  if(l1 < 0 && l2 < 0)
-    throw NegativeTierAdditionException();
-
-  // Check for overflow.
-  //
-  // If one level is nonnegative, we can only overflow if both are
-  // strictly positive.
-  if(l1 > 0 && l2 > 0 &&
-     l1 > (INT_MAX - l2))
-    throw TierTooBigException();
-
-  return l1 + l2;
+  out << ")";
 }
 
-tier tier_operation::levelwise_add(const tier &t1, const tier &t2)
+tier_operation::op_impl::op_impl(const op_impl &op1, const op_impl &op2, upper_bound_tag)
+  : structural_level(std::max<int>(op1.structural_level,
+				   op2.structural_level))
 {
-  int out_structural_level =
-    safe_add_levels(t1.get_structural_level(), t2.get_structural_level());
-
-  std::vector<int> out_user_levels;
+  actions.reserve(std::max<std::size_t>(op1.actions.size(), op2.actions.size()));
 
-  tier::user_level_iterator
-    it1 = t1.user_levels_begin(),
-    it2 = t2.user_levels_begin();
+  std::vector<std::pair<level_index, level> >::const_iterator
+    it1 = op1.actions.begin(),
+    it2 = op2.actions.begin();
 
-  const tier::user_level_iterator
-    end1 = t1.user_levels_end(),
-    end2 = t2.user_levels_end();
+  const std::vector<std::pair<level_index, level> >::const_iterator
+    end1 = op1.actions.end(),
+    end2 = op2.actions.end();
 
   while(it1 != end1 && it2 != end2)
-   {
-     out_user_levels.push_back(safe_add_levels(*it1, *it2));
-     ++it1;
-     ++it2;
-   }
+    {
+      const std::pair<level_index, level> &p1 = *it1, &p2 = *it2;
+
+      if(p1.first < p2.first)
+	{
+	  actions.push_back(p1);
+	  ++it1;
+	}
+      else if(p2.first < p1.first)
+	{
+	  actions.push_back(p2);
+	  ++it2;
+	}
+      else
+	{
+	  actions.push_back(std::make_pair(p1.first,
+					   level::upper_bound(p1.second, p2.second)));
+	  ++it1;
+	  ++it2;
+	}
+    }
 
   if(it1 != end1)
-    out_user_levels.insert(out_user_levels.end(),
-                           it1, end1);
+    actions.insert(actions.end(),
+		   it1, end1);
   else if(it2 != end2)
-    out_user_levels.insert(out_user_levels.end(),
-                           it2, end2);
-
-  return tier(out_structural_level,
-              out_user_levels.begin(),
-              out_user_levels.end());
-}
-
-tier_operation tier_operation::least_upper_bound(const tier_operation &op1,
-                                                 const tier_operation &op2)
-{
-  return tier_operation(levelwise_maximum(op1.add_levels,
-                                          op2.add_levels));
-}
-
-tier_operation tier_operation::greatest_lower_bound(const tier_operation &op1,
-                                                    const tier_operation &op2)
-{
-  return tier_operation(levelwise_minimum(op1.add_levels,
-                                          op2.add_levels));
+    actions.insert(actions.end(),
+		   it2, end2);
 }
 
-tier_operation tier_operation::operator+(const tier_operation &other) const
+tier_operation::op_impl::op_impl(const op_impl &op1, const op_impl &op2, lower_bound_tag)
+  : structural_level(std::min<int>(op1.structural_level,
+				   op2.structural_level))
 {
-  return tier_operation(levelwise_add(add_levels,
-                                      other.add_levels));
-}
+  std::vector<std::pair<level_index, level> >::const_iterator
+    it1 = op1.actions.begin(),
+    it2 = op2.actions.begin();
 
-tier tier_operation::apply(const tier &t) const
-{
-  return levelwise_add(t, add_levels);
-}
+  const std::vector<std::pair<level_index, level> >::const_iterator
+    end1 = op1.actions.end(),
+    end2 = op2.actions.end();
 
-void tier_operation::dump(std::ostream &out) const
-{
-  out << "(";
-
-  if(add_levels != tier(0))
+  while(it1 != end1 && it2 != end2)
     {
-      out << "add: " << add_levels;
+      const std::pair<level_index, level> &p1 = *it1, &p2 = *it2;
+
+      if(p1.first < p2.first)
+	++it1;
+      else if(p2.first < p1.first)
+	++it2;
+      else
+	{
+	  actions.push_back(std::make_pair(p1.first,
+					   level::lower_bound(p1.second, p2.second)));
+	  ++it1;
+	  ++it2;
+	}
     }
-
-  out << ")";
 }
 
-int tier_operation::compare(const tier_operation &other) const
+tier_operation tier_operation::least_upper_bound(const tier_operation &op1,
+                                                 const tier_operation &op2)
 {
-  // This comparison is correct only because we pre-normalize the
-  // object to discard trailing zeroes.
-  return aptitude::util::compare3(add_levels, other.add_levels);
+  return tier_operation(op1, op2, upper_bound_tag());
 }
 
-std::size_t tier_operation::get_hash_value() const
+tier_operation tier_operation::greatest_lower_bound(const tier_operation &op1,
+                                                    const tier_operation &op2)
 {
-  return hash_value(add_levels);
+  return tier_operation(op1, op2, lower_bound_tag());
 }
 
 std::size_t hash_value(const tier_operation &op)
diff --git a/src/generic/problemresolver/tier_operation.h b/src/generic/problemresolver/tier_operation.h
index 697745e0..e3ae3759 100644
--- a/src/generic/problemresolver/tier_operation.h
+++ b/src/generic/problemresolver/tier_operation.h
@@ -25,6 +25,8 @@
 
 #include <iosfwd>
 
+#include <boost/flyweight.hpp>
+
 /** \brief A tier operation describes how any solution's tier will
  * change as a result of adding a choice.
  *
@@ -42,103 +44,221 @@
  */
 class tier_operation
 {
-  // We use tiers internally to store the list of levels to modify,
-  // because the information that each component of the operation
-  // stores is exactly isomorphic to a tier.
-
-  // Values that this operation should add to a tier's level.
-  //
-  // Each level in this tier must be a nonnegative integer; if not,
-  // constructing the operation will throw an exception.
-  tier add_levels;
-
-  tier_operation(const tier &_add_levels)
-    : add_levels(_add_levels)
-  {
-    if(add_levels.get_structural_level() < 0)
-      throw NegativeTierAdditionException();
-
-    const std::size_t add_levels_size(add_levels.get_num_user_levels());
-    for(std::size_t i = 0; i < add_levels_size; ++i)
-      {
-	if(add_levels.get_user_level(i) < 0)
-	  throw NegativeTierAdditionException();
-      }
-
-    normalize();
-  }
+  // These classes are used to disambiguate constructors.
+  class combine_tag { };
+  class lower_bound_tag { };
+  class upper_bound_tag { };
 
-  /** \brief Compute the levelwise maximum of two tiers.
-   *
-   *  The output is a tier in which each level is equal to the maximum
-   *  of the corresponding entries in the input tiers.  Unpaired
-   *  levels (in the event that one of the tiers is longer than the
-   *  other) are assumed to equal tier_limits::minimum_level, with the
-   *  effect that the longer tier's elements are copied unchanged.
-   *
-   *  This function is implemented here instead of in tier.h because
-   *  tier operations require exactly this behavior and nothing else
-   *  does.
+  // \todo Should have an abstracted "key"" that covers the 3 ways of
+  // instantiating this object.  Also, should cache the hash value to
+  // avoid recomputing it over and over.
+  class op_impl
+  {
+    typedef std::vector<level>::size_type level_index;
+
+    // The value that a target tier's structural level should be
+    // increased to.
+    int structural_level;
+
+    // The operation is a collection of pairs giving level operations
+    // and the level's location in the tier vector.  Storing tier
+    // operations this way lets us save a little memory, considering
+    // that most operations will probably modify only a few tiers.
+    //
+    // This vector is always sorted, and level numbers are unique.
+    std::vector<std::pair<level_index, level> > actions;
+
+  public:
+    /** \brief Create a blank tier operation. */
+    op_impl()
+      : structural_level(INT_MIN)
+    {
+    }
+
+    /** \brief Create a tier operation that modifies the structural
+     *	level of the tier.
+     */
+    explicit op_impl(int _structural_level)
+      : structural_level(_structural_level)
+    {
+    }
+
+    /** \brief Create a tier operation that modifies a single level of
+     *	the tier.
+     */
+    op_impl(int index, const level &l)
+      : structural_level(INT_MIN)
+    {
+      if(l.get_state() == level::added &&
+	 l.get_value() <= 0)
+	throw NonPositiveTierAdditionException();
+
+      actions.push_back(std::make_pair(index, l));
+    }
+
+    /** \brief Create a tier operation that combines two other operations. */
+    op_impl(const op_impl &op1, const op_impl &op2, combine_tag);
+
+    /** \brief Create a new operation that computes the lower bound of
+     *  two input operations.
+     */
+    op_impl(const op_impl &op1, const op_impl &op2, lower_bound_tag);
+
+    /** \brief Create a new operation that computes the upper bound of
+     *  two input operations.
+     */
+    op_impl(const op_impl &op1, const op_impl &op2, upper_bound_tag);
+
+    /** \brief Compute a hash on this tier operation.
+     *
+     *  \note Relies on the fact that the level's hash includes
+     *  whether it's an addition or a lower-bound.
+     */
+    std::size_t get_hash_value() const
+    {
+      std::size_t rval = 0;
+
+      boost::hash_combine(rval, structural_level);
+      boost::hash_combine(rval, actions);
+
+      return rval;
+    }
+
+    /** \brief Test two tier operations for equality.
+     *
+     *  \note Relies on the fact that the level's equality comparison
+     *  returns "true" only when the two levels have the same state.
+     */
+    bool operator==(const op_impl &other) const
+    {
+      return
+	structural_level == other.structural_level &&
+	actions == other.actions;
+    }
+
+    /** \brief Apply the operation to the tier.
+     *
+     *  Each level is combined with the corresponding level in the
+     *  target tier.  If there is no corresponding level, it is copied
+     *  directly (which is exactly the desired behavior).
+     */
+    tier apply(const tier &t) const;
+
+    /** \brief Dump this operation to a stream. */
+    void dump(std::ostream &out) const;
+  };
+
+  class op_impl_hasher
+  {
+  public:
+    std::size_t operator()(const op_impl &op) const
+    {
+      return op.get_hash_value();
+    }
+  };
+
+  typedef boost::flyweight<op_impl,
+			   boost::flyweights::hashed_factory<op_impl_hasher> >
+  op_impl_flyweight;
+
+  op_impl_flyweight impl_flyweight;
+
+  const op_impl &get_impl() const { return impl_flyweight.get(); }
+
+  /** \brief Create a tier operation that modifies the structural
+   *	level of the tier.
    */
-  static tier levelwise_maximum(const tier &t1, const tier &t2);
+  explicit tier_operation(int structural_level)
+    : impl_flyweight(op_impl(structural_level))
+  {
+  }
 
-  /** \brief Compute the levelwise minimum of two tiers.
-   *
-   *  The output is a tier in which each level is equal to the minimum
-   *  of the corresponding entries in the input tiers.  Unpaired
-   *  levels (in the event that one of the tiers is longer than the
-   *  other) are assumed to equal tier_limits::maximum_level, with the
-   *  effect that the longer tier's elements are discarded.
-   *
-   *  This function is implemented here instead of in tier.h because
-   *  tier operations require exactly this behavior and nothing else
-   *  does.
+  /** \brief Create a tier operation that combines two other
+   *  operations.
    */
-  static tier levelwise_minimum(const tier &t1, const tier &t2);
+  tier_operation(const tier_operation &op1,
+		 const tier_operation &op2)
+    : impl_flyweight(op_impl(op1.get_impl(), op2.get_impl(),
+			     combine_tag()))
+  {
+  }
 
-  /** \brief Safely add two tier levels.
-   *
-   *  Checks that at least one operand is nonnegative and that the
-   *  result won't overflow.
+  /** \brief Create a tier operation that modifies a single level of
+   *  the tier.
    */
-  static int safe_add_levels(int l1, int l2);
+  tier_operation(int index, const level &l)
+    : impl_flyweight(op_impl(index, l))
+  {
+  }
 
-  /** \brief Compute the levelwise sum of two tiers.
-   *
-   *  The output is a tier in which each level is equal to the sum of
-   *  the corresponding levels in the input tiers.  If one tier is
-   *  longer than the other, the missing levels are assumed to be 0.
+  /** \brief Create a new operation that computes the lower bound of
+   *  two input operations.
    */
-  static tier levelwise_add(const tier &t1, const tier &t2);
+  tier_operation(const tier_operation &op1, const tier_operation &op2, lower_bound_tag)
+    : impl_flyweight(op_impl(op1.get_impl(), op2.get_impl(),
+			     lower_bound_tag()))
+  {
+  }
 
-  /** \brief Rewrite equivalent values to a canonical form.
-   *
-   *  The drops trailing zeros from add_levels.
+  /** \brief Create a new operation that computes the upper bound of
+   *  two input operations.
    */
-  void normalize();
+  tier_operation(const tier_operation &op1, const tier_operation &op2, upper_bound_tag)
+    : impl_flyweight(op_impl(op1.get_impl(), op2.get_impl(),
+			     upper_bound_tag()))
+  {
+  }
 
 public:
   /** \brief Create the identity tier operation: an operation with no
    *  effect.
    */
   tier_operation()
-    : add_levels(0)
+    : impl_flyweight(op_impl())
   {
   }
 
-  /** \brief Create a tier operation that adds a value to each level
-   *  in the target.
+  /** \brief Create a tier operation that increases the structural
+   *  level of its target to a particular value.
    *
-   *  \param increments The values to add to affected tiers.  The
-   *  value at each level is added to the corresponding level in the
-   *  target; the values must be nonnegative.  If the target is longer
-   *  than increments, the extra levels are unaffected; if the target
-   *  is shorter, the extra levels of increments are added to
-   *  tier_limits::minimum_level and then appended to the target tier.
+   *  \param structural_level The structural level that the resulting
+   *  operation will increase affected tiers to; tiers at a higher
+   *  structural level are unaffected.
    */
-  static tier_operation make_add_to_levels(const tier &increments)
+  static tier_operation make_advance_structural_level(int structural_level)
   {
-    return tier_operation(increments);
+    return tier_operation(structural_level);
+  }
+
+  /** \brief Create a tier operation that increases a single user
+   *  level of its target to a particular value.
+   *
+   *  \param index The index within the user tier list of the level
+   *               that is to be modified.
+   *
+   *  \param value The value that the resulting operation will
+   *               increase affected user levels to; higher user
+   *               levels are unaffected.
+   */
+  static tier_operation make_advance_user_level(int index,
+						int value)
+  {
+    return tier_operation(index, level::make_lower_bounded(value));
+  }
+
+  /** \brief Create a tier operation that adds a fixed value to a
+   *  single user level.
+   *
+   *  \param index The index within the user tier list of the level
+   *               that is to be modified.
+   *
+   *  \param value The value that the resulting operation will add to
+   *               affected user levels.
+   */
+  static tier_operation make_add_to_user_level(int index,
+					       int value)
+  {
+    return tier_operation(index, level::make_added(value));
   }
 
   /** \brief Compute the least upper bound of two tier operations.
@@ -163,57 +283,44 @@ public:
    *  The composition of tier operations is both associative and
    *  commutative.
    */
-  tier_operation operator+(const tier_operation &other) const;
+  tier_operation operator+(const tier_operation &other) const
+  {
+    return tier_operation(*this, other);
+  }
 
   /** \brief Test whether two operations have the same effect. */
   bool operator==(const tier_operation &other) const
   {
-    return compare(other) == 0;
+    return impl_flyweight == other.impl_flyweight;
   }
 
   /** \brief Test whether two operations don't have the same effect. */
   bool operator!=(const tier_operation &other) const
   {
-    return compare(other) != 0;
+    return impl_flyweight != other.impl_flyweight;
   }
 
-  /** \brief Arbitrary ordering on tier operations.
-   *
-   *  This ordering is NOT the partial ordering of the tier operation
-   *  lattice; it's a total ordering of tier operations that can be
-   *  used to place them into data structures that require entries to
-   *  be ordered.
-   */
-  int compare(const tier_operation &other) const;
-
   /** \brief Apply this operation to a tier.
    *
    *  \param t  The tier that this operation should modify.
    */
-  tier apply(const tier &t) const;
+  tier apply(const tier &t) const
+  {
+    return get_impl().apply(t);
+  }
 
   /** \brief Write a description of a tier operation to an ostream.
    */
-  void dump(std::ostream &out) const;
-
-  std::size_t get_hash_value() const;
-};
+  void dump(std::ostream &out) const
+  {
+    get_impl().dump(out);
+  }
 
-namespace aptitude
-{
-  namespace util
+  std::size_t get_hash_value() const
   {
-    template<>
-    class compare3_f<tier_operation>
-    {
-    public:
-      int operator()(const tier_operation &op1, const tier_operation &op2) const
-      {
-	return op1.compare(op2);
-      }
-    };
+    return get_impl().get_hash_value();
   }
-}
+};
 
 std::size_t hash_value(const tier_operation &op);