diff options
17 files changed, 281 insertions, 343 deletions
diff --git a/src/generic/apt/aptitude_resolver.cc b/src/generic/apt/aptitude_resolver.cc index 60fa01da..fb7c06b1 100644 --- a/src/generic/apt/aptitude_resolver.cc +++ b/src/generic/apt/aptitude_resolver.cc @@ -33,7 +33,7 @@ #include <generic/apt/matching/pattern.h> #include <generic/apt/matching/serialize.h> -#include <generic/problemresolver/tier_operation.h> +#include <generic/problemresolver/cost.h> #include <cwidget/generic/util/ssprintf.h> diff --git a/src/generic/apt/aptitude_resolver_cost_settings.h b/src/generic/apt/aptitude_resolver_cost_settings.h index d506e928..1aaec1c5 100644 --- a/src/generic/apt/aptitude_resolver_cost_settings.h +++ b/src/generic/apt/aptitude_resolver_cost_settings.h @@ -23,7 +23,7 @@ #include "aptitude_resolver_cost_types.h" -#include <generic/problemresolver/tier_operation.h> +#include <generic/problemresolver/cost.h> #include <boost/shared_ptr.hpp> #include <vector> diff --git a/src/generic/apt/aptitude_resolver_universe.h b/src/generic/apt/aptitude_resolver_universe.h index c29451c1..b5aecfc1 100644 --- a/src/generic/apt/aptitude_resolver_universe.h +++ b/src/generic/apt/aptitude_resolver_universe.h @@ -31,8 +31,7 @@ #include "apt.h" #include "aptcache.h" -#include <generic/problemresolver/tier.h> -#include <generic/problemresolver/tier_operation.h> +#include <generic/problemresolver/cost.h> #include <limits.h> diff --git a/src/generic/problemresolver/Makefile.am b/src/generic/problemresolver/Makefile.am index f64997e3..21031b7b 100644 --- a/src/generic/problemresolver/Makefile.am +++ b/src/generic/problemresolver/Makefile.am @@ -9,14 +9,15 @@ noinst_PROGRAMS=test test_LDADD = $(top_builddir)/src/generic/util/libgeneric-util.a libgeneric-problemresolver.a libgeneric_problemresolver_a_SOURCES = \ - choice.h choice_indexed_map.h choice_set.h dump_universe.h \ + choice.h choice_indexed_map.h choice_set.h \ + cost.cc cost.h \ + cost_limits.cc cost_limits.h \ + dump_universe.h \ exceptions.h \ dummy_universe.cc dummy_universe.h \ incremental_expression.cc incremental_expression.h \ problemresolver.h \ promotion_set.h sanity_check_universe.h \ - search_graph.h solution.h \ - tier_limits.cc tier_limits.h \ - tier_operation.cc tier_operation.h + search_graph.h solution.h test_SOURCES=test.cc diff --git a/src/generic/problemresolver/tier_operation.cc b/src/generic/problemresolver/cost.cc index e5907f96..01c18812 100644 --- a/src/generic/problemresolver/tier_operation.cc +++ b/src/generic/problemresolver/cost.cc @@ -1,4 +1,4 @@ -/** \file tier_operation.cc */ +/** \file cost.cc */ // Copyright (C) 2010 Daniel Burrows @@ -18,10 +18,23 @@ // the Free Software Foundation, Inc., 59 Temple Place - Suite 330, // Boston, MA 02111-1307, USA. -#include "tier_operation.h" +#include "cost.h" +#include "cost_limits.h" #include <ostream> +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; +} + 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)) diff --git a/src/generic/problemresolver/tier_operation.h b/src/generic/problemresolver/cost.h index f5e05642..80242a64 100644 --- a/src/generic/problemresolver/tier_operation.h +++ b/src/generic/problemresolver/cost.h @@ -1,4 +1,4 @@ -/** \file tier_operation.h */ // -*-c++-*- +/** \file cost.h */ // -*-c++-*- // Copyright (C) 2010 Daniel Burrows // @@ -17,16 +17,254 @@ // the Free Software Foundation, Inc., 59 Temple Place - Suite 330, // Boston, MA 02111-1307, USA. -#ifndef TIER_OPERATION_H -#define TIER_OPERATION_H +#ifndef COST_H +#define COST_H #include "exceptions.h" -#include "tier.h" + +#include <generic/util/compare3.h> #include <iosfwd> #include <stdexcept> #include <boost/flyweight.hpp> +/** \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; } + + /** \brief Test whether this level is greater than or equal to the + * given other level under the natural partial ordering of levels. + */ + bool is_above_or_equal(const level &other) const + { + if(other.state == unmodified) + return true; + else if(state != other.state) + return false; + else + switch(state) + { + case unmodified: + return true; + + case added: + case lower_bounded: + return value >= other.value; + } + + // Fall-through in case the case statement missed something; + // outside the case so that the compiler checks that all enum + // values are handled. + return false; + } + + 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; + } + } + + /** \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 if(l1.value > INT_MAX - l2.value) + throw TierTooBigException(); + 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 A tier operation describes how any solution's tier will * change as a result of adding a choice. diff --git a/src/generic/problemresolver/tier_limits.cc b/src/generic/problemresolver/cost_limits.cc index 02ce4b6b..b2662171 100644 --- a/src/generic/problemresolver/tier_limits.cc +++ b/src/generic/problemresolver/cost_limits.cc @@ -1,4 +1,4 @@ -/** \file tier_limits.cc */ +/** \file cost_limits.cc */ // Copyright (C) 2010 Daniel Burrows @@ -18,7 +18,7 @@ // the Free Software Foundation, Inc., 59 Temple Place - Suite 330, // Boston, MA 02111-1307, USA. -#include "tier_limits.h" +#include "cost_limits.h" const int tier_limits::maximum_level; const int tier_limits::conflict_structural_level; diff --git a/src/generic/problemresolver/tier_limits.h b/src/generic/problemresolver/cost_limits.h index 0f7b8e4d..74636830 100644 --- a/src/generic/problemresolver/tier_limits.h +++ b/src/generic/problemresolver/cost_limits.h @@ -1,4 +1,4 @@ -/** \file tier_limits.h */ // -*-c++-*- +/** \file cost_limits.h */ // -*-c++-*- // Copyright (C) 2009-2010 Daniel Burrows @@ -21,8 +21,7 @@ #ifndef TIER_LIMITS_H #define TIER_LIMITS_H -#include "tier.h" -#include "tier_operation.h" +#include "cost.h" class tier_limits { diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h index 62609701..53e7c991 100644 --- a/src/generic/problemresolver/problemresolver.h +++ b/src/generic/problemresolver/problemresolver.h @@ -57,9 +57,8 @@ #include "solution.h" #include "resolver_undo.h" #include "search_graph.h" -#include "tier.h" -#include "tier_limits.h" -#include "tier_operation.h" +#include "cost.h" +#include "cost_limits.h" #include "log4cxx/consoleappender.h" #include "log4cxx/logger.h" diff --git a/src/generic/problemresolver/promotion_set.h b/src/generic/problemresolver/promotion_set.h index c90dec0f..b40cce69 100644 --- a/src/generic/problemresolver/promotion_set.h +++ b/src/generic/problemresolver/promotion_set.h @@ -46,9 +46,8 @@ #include "choice_indexed_map.h" #include "choice_set.h" #include "incremental_expression.h" -#include "tier.h" -#include "tier_limits.h" -#include "tier_operation.h" +#include "cost.h" +#include "cost_limits.h" /** \brief Represents a tier promotion: the knowledge that * a set of choices forces a solution to a higher tier. diff --git a/src/generic/problemresolver/search_graph.h b/src/generic/problemresolver/search_graph.h index a467e0ad..c6301eb4 100644 --- a/src/generic/problemresolver/search_graph.h +++ b/src/generic/problemresolver/search_graph.h @@ -28,9 +28,8 @@ #include "choice_set.h" #include "promotion_set.h" #include "solution.h" -#include "tier.h" -#include "tier_limits.h" -#include "tier_operation.h" +#include "cost.h" +#include "cost_limits.h" #include <generic/util/compare3.h> #include <generic/util/immlist.h> diff --git a/src/generic/problemresolver/solution.h b/src/generic/problemresolver/solution.h index 538314fa..4a42eeb6 100644 --- a/src/generic/problemresolver/solution.h +++ b/src/generic/problemresolver/solution.h @@ -31,7 +31,7 @@ #include <generic/util/refcounted_base.h> #include "choice.h" #include "choice_set.h" -#include "tier_operation.h" +#include "cost.h" /** \brief The solution class for the problem resolver. * diff --git a/src/generic/problemresolver/tier.cc b/src/generic/problemresolver/tier.cc deleted file mode 100644 index 8ef840c2..00000000 --- a/src/generic/problemresolver/tier.cc +++ /dev/null @@ -1,35 +0,0 @@ -/** \file tier.cc */ - -// Copyright (C) 2010 Daniel Burrows -// -// This program is free software; you can redistribute it and/or -// modify it under the terms of the GNU General Public License as -// published by the Free Software Foundation; either version 2 of the -// License, or (at your option) any later version. -// -// This program is distributed in the hope that it will be useful, but -// WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -// General Public License for more details. -// -// You should have received a copy of the GNU General Public License -// along with this program; see the file COPYING. If not, write to -// the Free Software Foundation, Inc., 59 Temple Place - Suite 330, -// Boston, MA 02111-1307, USA. - -#include "tier.h" -#include "tier_limits.h" - -#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; -} diff --git a/src/generic/problemresolver/tier.h b/src/generic/problemresolver/tier.h deleted file mode 100644 index b358078d..00000000 --- a/src/generic/problemresolver/tier.h +++ /dev/null @@ -1,274 +0,0 @@ -/** \file tier.h */ // -*-c++-*- - -// Copyright (C) 2010 Daniel Burrows - -// This program is free software; you can redistribute it and/or -// modify it under the terms of the GNU General Public License as -// published by the Free Software Foundation; either version 2 of the -// License, or (at your option) any later version. -// -// This program is distributed in the hope that it will be useful, but -// WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -// General Public License for more details. -// -// You should have received a copy of the GNU General Public License -// along with this program; see the file COPYING. If not, write to -// the Free Software Foundation, Inc., 59 Temple Place - Suite 330, -// Boston, MA 02111-1307, USA. - -#ifndef TIER_H -#define TIER_H - -#include <generic/util/compare3.h> - -#include <boost/functional/hash.hpp> -#include <boost/make_shared.hpp> -#include <boost/shared_ptr.hpp> - -#include <iosfwd> -#include <vector> - -#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; } - - /** \brief Test whether this level is greater than or equal to the - * given other level under the natural partial ordering of levels. - */ - bool is_above_or_equal(const level &other) const - { - if(other.state == unmodified) - return true; - else if(state != other.state) - return false; - else - switch(state) - { - case unmodified: - return true; - - case added: - case lower_bounded: - return value >= other.value; - } - - // Fall-through in case the case statement missed something; - // outside the case so that the compiler checks that all enum - // values are handled. - return false; - } - - 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; - } - } - - /** \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 if(l1.value > INT_MAX - l2.value) - throw TierTooBigException(); - 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); - } - }; - } -} - -#endif // TIER_H diff --git a/tests/test_promotion_set.cc b/tests/test_promotion_set.cc index 4f4d79d6..51f1b746 100644 --- a/tests/test_promotion_set.cc +++ b/tests/test_promotion_set.cc @@ -19,7 +19,7 @@ #include <generic/problemresolver/dummy_universe.h> #include <generic/problemresolver/promotion_set.h> -#include <generic/problemresolver/tier_limits.h> +#include <generic/problemresolver/cost_limits.h> #include <cppunit/extensions/HelperMacros.h> diff --git a/tests/test_resolver.cc b/tests/test_resolver.cc index 664fddff..48754f15 100644 --- a/tests/test_resolver.cc +++ b/tests/test_resolver.cc @@ -21,8 +21,8 @@ #include <generic/problemresolver/dummy_universe.h> #include <generic/problemresolver/problemresolver.h> -#include <generic/problemresolver/tier_limits.h> -#include <generic/problemresolver/tier_operation.h> +#include <generic/problemresolver/cost_limits.h> +#include <generic/problemresolver/cost.h> #include <cppunit/extensions/HelperMacros.h> diff --git a/tests/test_resolver_hints.cc b/tests/test_resolver_hints.cc index 3b7e05b6..b4ca2cb4 100644 --- a/tests/test_resolver_hints.cc +++ b/tests/test_resolver_hints.cc @@ -21,8 +21,8 @@ #include <generic/apt/aptitude_resolver.h> -#include <generic/problemresolver/tier.h> -#include <generic/problemresolver/tier_limits.h> +#include <generic/problemresolver/cost.h> +#include <generic/problemresolver/cost_limits.h> #include <cppunit/extensions/HelperMacros.h> |