diff options
author | Daniel Burrows <dburrows@debian.org> | 2010-04-08 22:37:54 -0700 |
---|---|---|
committer | Daniel Burrows <dburrows@debian.org> | 2010-04-08 22:37:54 -0700 |
commit | 1d46e66bab8d97c39f07e562a8bb2dacd7e68c6e (patch) | |
tree | b6dfc422d68405c8bd60dbea9097c56dfcd35606 | |
parent | b766839fd98b8c6d3eeea24788c321d285404d91 (diff) | |
download | aptitude-1d46e66bab8d97c39f07e562a8bb2dacd7e68c6e.tar.gz |
Yank out the "tier" type and just use operations instead.
Although the concept of a "tier" is useful (to distinguish changes
in the tier from the things being changed), the actual data type isn't
needed. We can just store an operation that computes the tier of a
step given a minimal tier.
Throwing out tier objects yields several benefits. It makes the code
somewhat simpler by reducing the number of complex object types
floating around. It will make it easier to clean up the nomenclature
by talking about costs instead of tiers. And it will make it easier
to impose a "cost ceiling", just by virtue of making the cost-tracking
subsystem simpler.
-rw-r--r-- | src/generic/problemresolver/Makefile.am | 1 | ||||
-rw-r--r-- | src/generic/problemresolver/problemresolver.h | 151 | ||||
-rw-r--r-- | src/generic/problemresolver/promotion_set.h | 61 | ||||
-rw-r--r-- | src/generic/problemresolver/search_graph.h | 16 | ||||
-rw-r--r-- | src/generic/problemresolver/solution.h | 16 | ||||
-rw-r--r-- | src/generic/problemresolver/tier.cc | 27 | ||||
-rw-r--r-- | src/generic/problemresolver/tier.h | 289 | ||||
-rw-r--r-- | src/generic/problemresolver/tier_limits.cc | 6 | ||||
-rw-r--r-- | src/generic/problemresolver/tier_limits.h | 6 | ||||
-rw-r--r-- | src/generic/problemresolver/tier_operation.cc | 33 | ||||
-rw-r--r-- | src/generic/problemresolver/tier_operation.h | 17 | ||||
-rw-r--r-- | tests/test_resolver.cc | 135 |
12 files changed, 78 insertions, 680 deletions
diff --git a/src/generic/problemresolver/Makefile.am b/src/generic/problemresolver/Makefile.am index bb7a1798..f64997e3 100644 --- a/src/generic/problemresolver/Makefile.am +++ b/src/generic/problemresolver/Makefile.am @@ -16,7 +16,6 @@ libgeneric_problemresolver_a_SOURCES = \ problemresolver.h \ promotion_set.h sanity_check_universe.h \ search_graph.h solution.h \ - tier.cc tier.h \ tier_limits.cc tier_limits.h \ tier_operation.cc tier_operation.h diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h index 1d79c100..62609701 100644 --- a/src/generic/problemresolver/problemresolver.h +++ b/src/generic/problemresolver/problemresolver.h @@ -548,14 +548,15 @@ public: */ bool finished; - /** \brief The search tier of the next solution to consider. + /** \brief The search tier operation of the next solution to + * consider. */ - tier current_tier; + tier_operation current_tier_op; queue_counts() : open(0), closed(0), deferred(0), conflicts(0), promotions(0), finished(false), - current_tier(tier_limits::minimum_tier) + current_tier_op() { } }; @@ -604,10 +605,9 @@ private: // Note that *lower* tiers come "before" higher tiers, hence the // reversed comparison there. - if(step1.effective_step_tier < step2.effective_step_tier) - return true; - else if(step2.effective_step_tier < step1.effective_step_tier) - return false; + int tier_op_cmp = step1.final_step_tier_op.compare(step2.final_step_tier_op); + if(tier_op_cmp != 0) + return tier_op_cmp < 0; else if(step2.score < step1.score) return true; else if(step1.score < step2.score) @@ -846,23 +846,6 @@ private: /** \brief Counts how many steps are deferred. */ int num_deferred; - /** \brief The current minimum search tier. - * - * Solutions generated below this tier are discarded. Defaults to - * minimum_tier. - */ - tier minimum_search_tier; - - /** \brief The current maximum search tier. - * - * Solutions generated above this tier are placed into deferred. - * This is advanced automatically when the current tier is - * exhausted; it can also be advanced manually by the user. - * - * Defaults to minimum_tier. - */ - tier maximum_search_tier; - /** Solutions generated "in the future", stored by reference to * their step numbers. * @@ -1285,7 +1268,7 @@ private: non_incipient); if(non_incipient.get_has_value() && - s.effective_step_tier < non_incipient.get_value().get_tier()) + s.final_step_tier_op < non_incipient.get_value().get_tier()) LOG_ERROR(logger, "In step " << s.step_num << ": the embedded promotion " << non_incipient.get_value() << " was not applied."); else @@ -1294,7 +1277,7 @@ private: promotions.find_highest_promotion_for(s.actions); if(found_promotion != promotions.end() && - s.effective_step_tier < found_promotion->get_tier()) + s.final_step_tier_op < found_promotion->get_tier()) LOG_ERROR(logger, "In step " << s.step_num << ": the embedded promotion " << *found_promotion << " was not applied."); } @@ -1356,27 +1339,15 @@ private: #endif } - /** \return \b true if the given tier is one that should cause - * solvers and search steps to be discarded. - */ - bool is_discard_tier(const tier &t) const - { - return - t.get_structural_level() >= tier_limits::already_generated_structural_level; - } - /** \return \b true if the given tier operation will always cause - * the given step to be discarded. + * any step to be discarded. * * \param op the operation to test. - * - * \param s the step to test; is_discard_op returns \b true iff - * applying the tier operation to this step's base tier - * results in a discarding tier. */ - bool is_discard_op(const tier_operation &op, const step &s) const + bool is_discard_op(const tier_operation &op) const { - return is_discard_tier(op.apply(s.base_step_tier)); + return + op.get_structural_level() >= tier_limits::already_generated_structural_level; } /** \return \b true if the given step is "irrelevant": that is, @@ -1386,8 +1357,8 @@ private: */ bool irrelevant(const step &s) { - const tier &s_tier = s.effective_step_tier; - if(is_discard_tier(s_tier)) + const tier_operation &s_tier = s.final_step_tier_op; + if(is_discard_op(s_tier)) { LOG_TRACE(logger, "Step " << s.step_num << " is irrelevant: its tier " << s_tier << " indicates it should be discarded."); return true; @@ -1405,14 +1376,14 @@ private: } /** \brief Adjust the tier of a step, keeping everything consistent. */ - void set_step_tier(int step_num, - const tier &t) + void set_base_step_tier_op(int step_num, + const tier_operation &t_op) { step &s(graph.get_step(step_num)); - s.base_step_tier = t; + s.base_step_tier_op = t_op; - update_effective_step_tier(step_num); + update_final_step_tier_op(step_num); } /** \brief Update the operation that computes the *effective* tier @@ -1427,42 +1398,42 @@ private: s.effective_step_tier_op = t_op; - update_effective_step_tier(step_num); + update_final_step_tier_op(step_num); } /** \brief Update the effective tier of a step. * - * This should only be invoked by set_base_step_tier and + * This should only be invoked by set_base_step_tier_op and * set_effective_step_tier_op. It recomputes the effective tier * from its components and performs any follow-up work that's * needed to enforce consistency. */ - void update_effective_step_tier(int step_num) + void update_final_step_tier_op(int step_num) { step &s(graph.get_step(step_num)); - tier new_effective_step_tier = - s.effective_step_tier_op.apply(s.base_step_tier); + tier_operation new_final_step_tier_op = + s.effective_step_tier_op + s.base_step_tier_op; - if(s.effective_step_tier == new_effective_step_tier) + if(s.final_step_tier_op == new_final_step_tier_op) return; - if(s.is_blessed_solution && is_discard_tier(new_effective_step_tier)) + if(s.is_blessed_solution && is_discard_op(new_final_step_tier_op)) { LOG_TRACE(logger, "Step " << s.step_num - << " is a blessed solution; ignoring the attempt to promote it to tier " << new_effective_step_tier); + << " is a blessed solution; ignoring the attempt to promote it to tier " << new_final_step_tier_op); return; } - LOG_TRACE(logger, "Setting the effective tier of step " << step_num - << " to " << new_effective_step_tier); + LOG_TRACE(logger, "Setting the final tier of step " << step_num + << " to " << new_final_step_tier_op); bool was_in_pending = (pending.erase(step_num) > 0); bool was_in_pending_future_solutions = (pending_future_solutions.erase(step_num) > 0); - if(s.effective_step_tier >= tier_limits::defer_tier && - !is_discard_tier(s.effective_step_tier)) + if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level && + !is_discard_op(s.final_step_tier_op)) { if(was_in_pending) --num_deferred; @@ -1470,7 +1441,7 @@ private: --num_deferred; } - s.effective_step_tier = new_effective_step_tier; + s.final_step_tier_op = new_final_step_tier_op; if(was_in_pending) @@ -1479,15 +1450,15 @@ private: pending_future_solutions.insert(step_num); - if(s.effective_step_tier >= tier_limits::defer_tier && - !is_discard_tier(s.effective_step_tier)) + if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level && + !is_discard_op(s.final_step_tier_op)) { if(was_in_pending) ++num_deferred; if(was_in_pending_future_solutions) ++num_deferred; } - else if(s.effective_step_tier < tier_limits::defer_tier) + else if(s.final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level) { // Clear the "finished" flag if this is now a pending // candidate. @@ -2495,7 +2466,7 @@ private: bool operator()(const promotion &p) const { if(blessed) - return !resolver.is_discard_op(p.get_tier_op(), s); + return !resolver.is_discard_op(p.get_tier_op() + s.base_step_tier_op); else return true; } @@ -2845,8 +2816,8 @@ private: */ void recompute_effective_step_tier_op(step &s) { - LOG_TRACE(logger, "Recomputing the effective tier operation of step " << s.step_num - << " (was " << s.effective_step_tier << ")"); + LOG_TRACE(logger, "Recomputing the final tier operation of step " << s.step_num + << " (was " << s.final_step_tier_op << ")"); tier_operation new_tier_op(tier_limits::minimum_op); s.unresolved_deps.for_each(find_dep_tier_op_upper_bound(new_tier_op, *this)); @@ -2953,7 +2924,7 @@ private: // checks whether t_op consists only of maximizing operations that // are below the current search tier, in which case there's no // point in saving it. - if(t_op.apply(get_current_search_tier()) == get_current_search_tier() && + if(t_op + get_current_search_tier() == get_current_search_tier() && s.effective_step_tier_op.is_above_or_equal(t_op)) return; @@ -3125,7 +3096,7 @@ private: // to the point that the solver should be ejected, or the tier // should just be bumped up a bit. Either way, we might end up // changing the tier of the whole step. - if(is_discard_op(new_tier_op, s)) + if(is_discard_op(new_tier_op + s.base_step_tier_op)) { // \todo this throws away information about whether we're at // the already-generated tier. This isn't that important, @@ -3536,9 +3507,9 @@ private: output.action_score = parent.action_score; output.score = parent.score; output.reason = c; - output.base_step_tier = c_op.apply(parent.base_step_tier); + output.base_step_tier_op = c_op + parent.base_step_tier_op; output.effective_step_tier_op = tier_operation(); - output.effective_step_tier = output.effective_step_tier_op.apply(output.base_step_tier); + output.final_step_tier_op = output.effective_step_tier_op + output.base_step_tier_op; output.is_deferred_listener = build_is_deferred_listener(c); output.unresolved_deps = parent.unresolved_deps; output.unresolved_deps_by_num_solvers = parent.unresolved_deps_by_num_solvers; @@ -3634,10 +3605,10 @@ private: extend_score_to_new_step(output, c); LOG_TRACE(logger, "Generated step " << output.step_num - << " (" << output.actions.size() << " actions): " << output.actions << ";T" << output.effective_step_tier + << " (" << output.actions.size() << " actions): " << output.actions << ";T" << output.final_step_tier_op << "S" << output.score); - if(is_discard_tier(output.effective_step_tier)) + if(is_discard_op(output.final_step_tier_op)) ++num_deferred; pending.insert(output.step_num); @@ -3777,8 +3748,6 @@ public: solver_executing(false), solver_cancelled(false), pending(step_goodness_compare(graph)), num_deferred(0), - minimum_search_tier(tier_limits::minimum_tier), - maximum_search_tier(tier_limits::minimum_tier), pending_future_solutions(step_goodness_compare(graph)), closed(), promotions(_universe, *this), @@ -4228,7 +4197,7 @@ public: counts.conflicts = promotions.conflicts_size(); counts.promotions = promotions.size() - counts.conflicts; counts.finished = finished; - counts.current_tier = get_current_search_tier(); + counts.current_tier_op = get_current_search_tier(); } /** If no resolver is running, run through the deferred list and @@ -4249,12 +4218,12 @@ public: * solution that would be considered (or minimum_search_tier if * pending is empty). */ - const tier &get_current_search_tier() const + tier_operation get_current_search_tier() const { if(pending.empty()) - return tier_limits::minimum_tier; + return tier_operation(); else - return graph.get_step(*pending.begin()).effective_step_tier; + return graph.get_step(*pending.begin()).final_step_tier_op; } private: @@ -4265,7 +4234,7 @@ private: { return !pending.empty() && - graph.get_step(*pending.begin()).effective_step_tier < tier_limits::defer_tier; + graph.get_step(*pending.begin()).final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level; } /** \brief Returns \b true if the pending future solutions queue @@ -4275,7 +4244,7 @@ private: { return !pending_future_solutions.empty() && - graph.get_step(*pending_future_solutions.begin()).effective_step_tier < tier_limits::defer_tier; + graph.get_step(*pending_future_solutions.begin()).final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level; } // Counts how many action hits existed in a promotion, allowing up @@ -4461,10 +4430,10 @@ private: step &s = graph.get_step(step_num); LOG_INFO(logger, "Examining step " << step_num - << " (" << s.actions.size() << " actions): " << s.actions << ";T" << s.effective_step_tier + << " (" << s.actions.size() << " actions): " << s.actions << ";T" << s.final_step_tier_op << "S" << s.score); - if(s.effective_step_tier >= tier_limits::defer_tier) + if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level) { LOG_ERROR(logger, "Internal error: the tier of step " << s.step_num @@ -4487,7 +4456,7 @@ private: } // The step might have been promoted to the defer tier by // check_for_new_promotions. - else if(s.effective_step_tier >= tier_limits::defer_tier) + else if(s.final_step_tier_op.get_structural_level() >= tier_limits::defer_structural_level) { LOG_DEBUG(logger, "Skipping newly deferred step " << s.step_num); // Stick it back into the open queue. @@ -4504,7 +4473,7 @@ private: if(s.unresolved_deps.empty()) { LOG_INFO(logger, " --- Found solution at step " << s.step_num - << ": " << s.actions << ";T" << s.effective_step_tier + << ": " << s.actions << ";T" << s.final_step_tier_op << "S" << s.score); // Remember this solution, so we don't try to return it @@ -4528,7 +4497,7 @@ private: // was a forced dependency and we should process that // successor before returning. if(s.first_child != -1 && graph.get_step(s.first_child).is_last_child && - graph.get_step(s.first_child).effective_step_tier < tier_limits::defer_tier) + graph.get_step(s.first_child).final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level) { LOG_TRACE(logger, "Following forced dependency resolution from step " << step_num << " to step " << s.first_child); @@ -4614,9 +4583,9 @@ public: if(initial_broken.empty()) root.score += weights.full_solution_score; - root.base_step_tier = tier_limits::minimum_tier; + root.base_step_tier_op = tier_operation(); root.effective_step_tier_op = tier_operation(); - root.effective_step_tier = tier_limits::minimum_tier; + root.final_step_tier_op = tier_operation(); root.promotion_queue_location = promotion_queue_tail; for(typename imm::set<dep>::const_iterator it = initial_broken.begin(); @@ -4624,7 +4593,7 @@ public: add_unresolved_dep(root, *it); LOG_TRACE(logger, "Inserting the root at step " << root.step_num - << " with tier " << root.effective_step_tier); + << " with tier " << root.final_step_tier_op); pending.insert(root.step_num); } @@ -4686,14 +4655,14 @@ public: { int best_future_solution = *pending_future_solutions.begin(); step &best_future_solution_step = graph.get_step(best_future_solution); - if(best_future_solution_step.effective_step_tier < tier_limits::defer_tier) + if(best_future_solution_step.final_step_tier_op.get_structural_level() < tier_limits::defer_structural_level) { sanity_check_not_deferred(best_future_solution_step); solution rval(best_future_solution_step.actions, initial_state, best_future_solution_step.score, - best_future_solution_step.effective_step_tier); + best_future_solution_step.final_step_tier_op); LOG_INFO(logger, " *** Converged after " << odometer << " steps."); diff --git a/src/generic/problemresolver/promotion_set.h b/src/generic/problemresolver/promotion_set.h index 29397748..c90dec0f 100644 --- a/src/generic/problemresolver/promotion_set.h +++ b/src/generic/problemresolver/promotion_set.h @@ -1647,67 +1647,6 @@ private: choices.for_each(find_results_f); } - /** \brief Predicate testing whether an entry reference refers to - * something in a particular tier. - */ - struct entry_ref_in_tier_pred - { - tier selected_tier; - - entry_ref_in_tier_pred(const tier &_selected_tier) - : selected_tier(_selected_tier) - { - } - - bool operator()(entry_ref r) const - { - return r->p.get_tier() == selected_tier; - } - }; - - /** \brief Predicate testing whether an entry reference refers to - * something between two tiers. - */ - struct entry_ref_between_tiers_pred - { - tier begin_tier, end_tier; - - /** \brief Create a new entry_ref_in_tier_pred. - * - * \param _begin_tier The first tier to select. - * \param _end_tier The first tier to *not* select. - */ - entry_ref_between_tiers_pred(const tier &_begin_tier, const tier &_end_tier) - : begin_tier(_begin_tier), end_tier(_end_tier) - { - } - - bool operator()(entry_ref r) const - { - const tier &r_tier(r->p.get_tier()); - - return r_tier >= begin_tier && r_tier < end_tier; - } - }; - - /** \brief Predicate testing whether an entry reference is strictly - * below a particular tier. - */ - struct entry_ref_strictly_below_tier_pred - { - tier selected_tier; - - entry_ref_strictly_below_tier_pred(const tier &_selected_tier) - : selected_tier(_selected_tier) - { - } - - bool operator()(entry_ref r) const - { - return r->p.get_tier() < selected_tier; - } - }; - /** \brief Collect the versions and soft dependencies related * to a single choice. */ diff --git a/src/generic/problemresolver/search_graph.h b/src/generic/problemresolver/search_graph.h index c99de55c..a467e0ad 100644 --- a/src/generic/problemresolver/search_graph.h +++ b/src/generic/problemresolver/search_graph.h @@ -790,12 +790,13 @@ public: */ int action_score; - /** \brief The true tier of this step. + /** \brief The tier operation induced by the actions performed at + * this step. * * This is the tier *before* any forward-looking operations are * applied to it. */ - tier base_step_tier; + tier_operation base_step_tier_op; /** \brief The cumulative effect of all forward-looking operations * applied to this step. @@ -809,12 +810,13 @@ public: */ tier_operation effective_step_tier_op; - /** \brief The effective tier of this step. + /** \brief The tier of this step after taking into account + * knowledge about the available solutions to its dependencies. * * This tier is step_tier combined with any inferred tier * operations, and is used to sort the step in the search queue. */ - tier effective_step_tier; + tier_operation final_step_tier_op; /** \brief A side-effecting expression that fires when the most * recently added action becomes deferred or un-deferred. @@ -1790,11 +1792,11 @@ private: { bool operator()(const promotion &p) const { - const tier &p_tier(p.get_tier()); + const tier_operation &p_tier_op(p.get_tier_op()); return - p_tier >= tier_limits::defer_tier && - p_tier < tier_limits::already_generated_tier; + p_tier_op.get_structural_level() >= tier_limits::defer_structural_level && + p_tier_op.get_structural_level() < tier_limits::already_generated_structural_level; } }; diff --git a/src/generic/problemresolver/solution.h b/src/generic/problemresolver/solution.h index 23c57f42..538314fa 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.h" +#include "tier_operation.h" /** \brief The solution class for the problem resolver. * @@ -294,7 +294,7 @@ private: * Informational only; not considered when comparing solutions by * identity. */ - tier sol_tier; + tier_operation sol_tier_op; /** The reference count of this solution. */ mutable unsigned int refcount; @@ -307,10 +307,10 @@ private: solution_rep(const choice_set &_choices, const resolver_initial_state<PackageUniverse> &_initial_state, int _score, - const tier &_sol_tier) + const tier_operation &_sol_tier_op) : initial_state(_initial_state), choices(_choices), score(_score), - sol_tier(_sol_tier), + sol_tier_op(_sol_tier_op), refcount(1) { } @@ -326,7 +326,7 @@ private: } int get_score() const {return score;} - const tier &get_tier() const { return sol_tier; } + const tier_operation &get_tier() const { return sol_tier_op; } version version_of(const package &pkg) const { @@ -394,8 +394,8 @@ public: generic_solution(const choice_set &choices, const resolver_initial_state<PackageUniverse> &initial_state, int score, - const tier &sol_tier) - : real_soln(new solution_rep(choices, initial_state, score, sol_tier)) + const tier_operation &sol_tier_op) + : real_soln(new solution_rep(choices, initial_state, score, sol_tier_op)) { } @@ -487,7 +487,7 @@ public: } /** \return The tier at which this solution was calculated. */ - const tier &get_tier() const + const tier_operation &get_tier() const { return real_soln->get_tier(); } diff --git a/src/generic/problemresolver/tier.cc b/src/generic/problemresolver/tier.cc index c2369d5f..8ef840c2 100644 --- a/src/generic/problemresolver/tier.cc +++ b/src/generic/problemresolver/tier.cc @@ -33,30 +33,3 @@ std::ostream &operator<<(std::ostream &out, const level &l) return out; } - -std::ostream &operator<<(std::ostream &out, const tier &t) -{ - out << "("; - - const int t_structural_level = t.get_structural_level(); - - if(t_structural_level == tier_limits::conflict_structural_level) - out << "conflict"; - else if(t_structural_level == tier_limits::already_generated_structural_level) - out << "already-generated"; - else if(t_structural_level == tier_limits::defer_structural_level) - out << "defer"; - else if(t_structural_level == tier_limits::minimum_level) - out << "minimum"; - else - out << t_structural_level; - - for(tier::user_level_iterator it = t.user_levels_begin(); - it != t.user_levels_end(); ++it) - out << ", " << *it; - - out << ")"; - - return out; -} - diff --git a/src/generic/problemresolver/tier.h b/src/generic/problemresolver/tier.h index f608c7cb..b358078d 100644 --- a/src/generic/problemresolver/tier.h +++ b/src/generic/problemresolver/tier.h @@ -271,293 +271,4 @@ namespace aptitude } } -/** \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 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 - * or deferred); to make things simpler for client code that doesn't - * care about this information, that level is stored and accessed - * separately from the main list. - */ -class tier -{ - /** \brief The object that actually stores the tier data. */ - struct tier_impl - { - // Level set by the resolver itself to control the search - // 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<level> user_levels; - - // Cache the hash value. Initialized during construction. - std::size_t hash_value; - - /** \brief Initialize a tier object from a collection of user levels. - * - * The structural level is set to INT_MIN. - */ - template<typename Iterator> - tier_impl(Iterator user_levels_begin, Iterator user_levels_end) - : structural_level(INT_MIN), - user_levels(user_levels_begin, user_levels_end), - hash_value(0) - { - hash_value = get_hash_value(); - } - - /** \brief Initialize a tier object with no user levels. - * - * This will be the smallest tier in its structural level. - */ - tier_impl(int _structural_level) - : structural_level(_structural_level), - user_levels(), - hash_value(0) - { - hash_value = get_hash_value(); - } - - /** \brief Initialize a tier object given its contents. */ - template<typename Iterator> - tier_impl(int _structural_level, - Iterator user_levels_begin, Iterator user_levels_end) - : structural_level(_structural_level), - user_levels(user_levels_begin, user_levels_end), - hash_value(0) - { - 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<level>::const_iterator it = user_levels.begin(); - it != user_levels.end(); ++it) - boost::hash_combine(rval, *it); - - return rval; - } - - bool operator==(const tier_impl &other) const - { - return - structural_level == other.structural_level && - user_levels == other.user_levels; - } - - bool operator!=(const tier_impl &other) const - { - return - structural_level != other.structural_level || - user_levels != other.user_levels; - } - }; - - class tier_impl_hasher - { - public: - std::size_t operator()(const tier_impl &impl) const - { - return impl.hash_value; - } - }; - - typedef boost::shared_ptr<tier_impl> tier_impl_ref; - - tier_impl_ref impl_ref; - - tier(const tier_impl_ref &_impl_ref) - : impl_ref(_impl_ref) - { - } - - const tier_impl &get_impl() const - { - return *impl_ref; - } - -public: - /** \brief A default-constructed tier is the smallest possible tier. */ - tier() - : impl_ref(boost::make_shared<tier_impl>(INT_MIN)) - { - } - - /** \brief Create a new tier object with structural level INT_MIN. - * - * \param user_level_begin The beginning of a range of levels to - * insert into the user level list. - * - * \param user_level_end The end of a range of levels to insert - * into the user level list. - */ - template<typename Iterator> - tier(Iterator user_levels_begin, Iterator user_levels_end) - : impl_ref(boost::make_shared<tier_impl>(user_levels_begin, user_levels_end)) - { - } - - /** \brief Create a new tier object with the given structural level - * and no user levels. - * - * The new tier will be the smallest tier in its structural level. - */ - tier(int structural_level) - : impl_ref(boost::make_shared<tier_impl>(structural_level)) - { - } - - /** \brief Create a new tier object. - * - * \param structural_level The structural level to store in the new - * level object. - * - * \param user_level_begin The beginning of a range of levels to - * insert into the user level list. - * - * \param user_level_end The end of a range of levels to insert - * into the user level list. - */ - template<typename Iterator> - tier(int structural_level, - Iterator user_levels_begin, Iterator user_levels_end) - : impl_ref(boost::make_shared<tier_impl>(structural_level, user_levels_begin, user_levels_end)) - { - } - - /** \brief Create a new tier object in which this object's - * structural level has been modified. - * - * \param new_structural_level The structural level of the new - * level object. - * - * \return a tier object with the same user levels as this object - * and the given structural level. - */ - tier set_structural_level(int new_structural_level) const - { - const tier_impl &impl(get_impl()); - - return tier(boost::make_shared<tier_impl>(new_structural_level, - impl.user_levels.begin(), - impl.user_levels.end())); - } - - /** \brief Retrieve the value of the structural level slot. */ - int get_structural_level() const { return get_impl().structural_level; } - - typedef std::vector<level>::const_iterator user_level_iterator; - - /** \brief Get a reference to the first user level as a - * random-access iterator. - */ - user_level_iterator user_levels_begin() const { return get_impl().user_levels.begin(); } - /** \brief Get a reference to the end of the user level list as a - * random-access iterator. - */ - user_level_iterator user_levels_end() const { return get_impl().user_levels.end(); } - - /** \brief Retrieve one user level from this tier. */ - 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(); } - - std::size_t get_hash_value() const - { - return get_impl().hash_value; - } - - tier &operator=(const tier &other) - { - impl_ref = other.impl_ref; - - 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()); - const tier_impl &other_impl(other.get_impl()); - - using aptitude::util::compare3; - - const int cmp = compare3(impl.structural_level, other_impl.structural_level); - if(cmp != 0) - return cmp; - else - return compare3(impl.user_levels, other_impl.user_levels); - } - - bool operator==(const tier &other) const - { - return compare(other) == 0; - } - - bool operator!=(const tier &other) const - { - return compare(other) != 0; - } - - bool operator<(const tier &other) const - { - return compare(other) < 0; - } - - bool operator<=(const tier &other) const - { - return compare(other) <= 0; - } - - bool operator>(const tier &other) const - { - return compare(other) > 0; - } - - bool operator>=(const tier &other) const - { - return compare(other) >= 0; - } -}; - -inline std::size_t hash_value(const tier &t) -{ - return t.get_hash_value(); -} - -namespace aptitude -{ - namespace util - { - template<> - class compare3_f<tier> - { - public: - int operator()(const tier &t1, const tier &t2) const - { - return t1.compare(t2); - } - }; - } -} - -std::ostream &operator<<(std::ostream &, const tier &t); - #endif // TIER_H diff --git a/src/generic/problemresolver/tier_limits.cc b/src/generic/problemresolver/tier_limits.cc index 495f895f..02ce4b6b 100644 --- a/src/generic/problemresolver/tier_limits.cc +++ b/src/generic/problemresolver/tier_limits.cc @@ -26,12 +26,6 @@ const int tier_limits::defer_structural_level; const int tier_limits::already_generated_structural_level; const int tier_limits::minimum_level; -const tier tier_limits::maximum_tier(tier_limits::maximum_level); -const tier tier_limits::conflict_tier(tier_limits::conflict_structural_level); -const tier tier_limits::already_generated_tier(tier_limits::already_generated_structural_level); -const tier tier_limits::defer_tier(tier_limits::defer_structural_level); -const tier tier_limits::minimum_tier(tier_limits::minimum_level); - const tier_operation tier_limits::increase_to_maximum_op(tier_operation::make_advance_structural_level(maximum_level)); const tier_operation tier_limits::increase_to_conflict_op(tier_operation::make_advance_structural_level(conflict_structural_level)); const tier_operation tier_limits::increase_to_already_generated_op(tier_operation::make_advance_structural_level(already_generated_structural_level)); diff --git a/src/generic/problemresolver/tier_limits.h b/src/generic/problemresolver/tier_limits.h index 567d5ea1..0f7b8e4d 100644 --- a/src/generic/problemresolver/tier_limits.h +++ b/src/generic/problemresolver/tier_limits.h @@ -55,12 +55,6 @@ public: */ static const int minimum_level = INT_MIN; - static const tier maximum_tier; - static const tier conflict_tier; - static const tier already_generated_tier; - static const tier defer_tier; - static const tier minimum_tier; - /** \brief Tier operations that just increase the structural level. */ // @{ diff --git a/src/generic/problemresolver/tier_operation.cc b/src/generic/problemresolver/tier_operation.cc index 180c0825..e5907f96 100644 --- a/src/generic/problemresolver/tier_operation.cc +++ b/src/generic/problemresolver/tier_operation.cc @@ -59,39 +59,6 @@ tier_operation::op_impl::op_impl(const op_impl &op1, const op_impl &op2, combine actions.insert(actions.end(), it2, op2.actions.end()); } -tier tier_operation::op_impl::apply(const tier &t) const -{ - 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()); - - if(!actions.empty()) - { - // 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); - } - } - - return tier(out_structural_level, - out_user_levels.begin(), - out_user_levels.end()); -} - bool tier_operation::op_impl::is_above_or_equal(const op_impl &other) const { std::vector<std::pair<level_index, level> >::const_iterator diff --git a/src/generic/problemresolver/tier_operation.h b/src/generic/problemresolver/tier_operation.h index aac1dd19..f5e05642 100644 --- a/src/generic/problemresolver/tier_operation.h +++ b/src/generic/problemresolver/tier_operation.h @@ -163,14 +163,6 @@ class tier_operation 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 Compare two operations by their identity. */ int compare(const op_impl &other) const; @@ -342,15 +334,6 @@ public: return impl_flyweight != other.impl_flyweight; } - /** \brief Apply this operation to a tier. - * - * \param t The tier that this operation should modify. - */ - 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 diff --git a/tests/test_resolver.cc b/tests/test_resolver.cc index 032de0b2..664fddff 100644 --- a/tests/test_resolver.cc +++ b/tests/test_resolver.cc @@ -200,7 +200,6 @@ class ResolverTest : public CppUnit::TestFixture CPPUNIT_TEST(testInitialSetExclusion); CPPUNIT_TEST(testSimpleResolution); CPPUNIT_TEST(testSimpleBreakSoftDep); - CPPUNIT_TEST(testTiers); CPPUNIT_TEST(testTierEffects); CPPUNIT_TEST(testTierOperations); CPPUNIT_TEST(testInitialState); @@ -842,98 +841,6 @@ private: 3 * step_score + unfixed_soft_score + full_solution_score); } - void testTiers() - { - log4cxx::LoggerPtr logger(log4cxx::Logger::getLogger("test.resolver.testTiers")); - LOG_TRACE(logger, "Entering testTiers"); - - const level n50 = level::make_lower_bounded(50); - level n50_100[2] = { level::make_lower_bounded(50), - level::make_lower_bounded(100) }; - - // Instantiate 4 tier objects and make sure they're properly - // ordered; instantiate them twice to ensure there's no special - // behavior relying on things being the same object instance. - std::vector<tier> tiers; - tiers.push_back(tier()); - tiers.push_back(tier(&n50, (&n50) + 1)); - tiers.push_back(tier(tier_limits::minimum_level, n50_100, n50_100 + 2)); - tiers.push_back(tier(tier_limits::maximum_level)); - - std::vector<tier> tiers2; - tiers2.push_back(tier()); - tiers2.push_back(tier(&n50, (&n50) + 1)); - tiers2.push_back(tier(tier_limits::minimum_level, n50_100, n50_100 + 2)); - tiers2.push_back(tier(tier_limits::maximum_level)); - - std::vector<std::string> tier_renderings; - tier_renderings.push_back("(minimum)"); - tier_renderings.push_back("(minimum, 50)"); - tier_renderings.push_back("(minimum, 50, 100)"); - tier_renderings.push_back("(conflict)"); - - std::vector<std::string> tier_renderings_with_400_at_1; - tier_renderings_with_400_at_1.push_back("(minimum, minimum, 400)"); - tier_renderings_with_400_at_1.push_back("(minimum, 50, 400)"); - tier_renderings_with_400_at_1.push_back("(minimum, 50, 400)"); - tier_renderings_with_400_at_1.push_back("(conflict, minimum, 400)"); - - for(std::size_t i = 0; i < tiers.size(); ++i) - { - const tier &t1 = tiers[i]; - const std::string s1 = boost::lexical_cast<std::string>(t1); - - const tier t1_with_400_at_1 = tier_operation::make_advance_user_level(1, 400).apply(t1); - const std::string s1_with_400_at_1 = - boost::lexical_cast<std::string>(t1_with_400_at_1); - - CPPUNIT_ASSERT_EQUAL(tier_renderings_with_400_at_1[i], - s1_with_400_at_1); - - CPPUNIT_ASSERT_MESSAGE(s1 + " < " + s1_with_400_at_1, t1 < t1_with_400_at_1); - CPPUNIT_ASSERT_MESSAGE(s1 + " <= " + s1_with_400_at_1, t1 <= t1_with_400_at_1); - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " == " + s1_with_400_at_1 + ")", !(t1 == t1_with_400_at_1)); - CPPUNIT_ASSERT_MESSAGE(s1 + " != " + s1_with_400_at_1, t1 != t1_with_400_at_1); - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " >= " + s1_with_400_at_1 + ")", !(t1 >= t1_with_400_at_1)); - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " > " + s1_with_400_at_1 + ")", !(t1 > t1_with_400_at_1)); - - for(std::size_t j = 0; j < tiers.size(); ++j) - { - const tier &t2 = tiers[j]; - - const std::string s2 = boost::lexical_cast<std::string>(t2); - - CPPUNIT_ASSERT_EQUAL(tier_renderings[i], s1); - CPPUNIT_ASSERT_EQUAL(tier_renderings[j], s2); - - if(i < j) - CPPUNIT_ASSERT_MESSAGE(s1 + " < " + s2, t1 < t2); - else - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " < " + s2 + ")", !(t1 < t2)); - - if(i == j) - CPPUNIT_ASSERT_MESSAGE(s1 + " == " + s2, t1 == t2); - else - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " == " + s2 + ")", !(t1 == t2)); - - if(i <= j) - CPPUNIT_ASSERT_MESSAGE(s1 + " <= " + s2, t1 <= t2); - else - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " <= " + s2 + ")", !(t1 <= t2)); - - if(i >= j) - CPPUNIT_ASSERT_MESSAGE(s1 + " >= " + s2, t1 >= t2); - else - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " >= " + s2 + ")", !(t1 >= t2)); - - if(i > j) - CPPUNIT_ASSERT_MESSAGE(s1 + " > " + s2, t1 > t2); - else - CPPUNIT_ASSERT_MESSAGE("!(" + s1 + " > " + s2 + ")", !(t1 > t2)); - } - } - } - void testTierEffects() { log4cxx::LoggerPtr logger(log4cxx::Logger::getLogger("test.resolver.testTierEffects")); @@ -1267,13 +1174,6 @@ private: CPPUNIT_ASSERT_THROW(tier_operation::make_add_to_user_level(1, INT_MAX) + tier_operation::make_add_to_user_level(1, 5), TierTooBigException); - { - const level biggest_tier_level = level::make_added(INT_MAX); - tier biggest_singleton_tier = tier(&biggest_tier_level, (&biggest_tier_level) + 1); - - CPPUNIT_ASSERT_THROW(tier_operation::make_add_to_user_level(0, 1).apply(biggest_singleton_tier), - TierTooBigException); - } // Test rendering the initial operations: std::vector<std::string> op_renderings; @@ -1281,40 +1181,9 @@ private: op_renderings.push_back("(nop, add: 2, add: 4)"); op_renderings.push_back("(nop, add: 1, nop, advance: 5)"); - LOG_TRACE(logger, "Testing the results of applying operations to tiers."); - // Input tiers and the tiers we expect to see after applying each operation. - tier t1(4); - const level t1_op1_user_levels_begin[2] = { level::make_added(2), - level::make_added(4) }; - const level t1_op2_user_levels_begin[3] = { level::make_added(1), - level(), - level::make_added(5) }; - const level *t1_op1_user_levels_end = t1_op1_user_levels_begin + sizeof(t1_op1_user_levels_begin) / sizeof(t1_op1_user_levels_begin[0]); - const level *t1_op2_user_levels_end = t1_op2_user_levels_begin + sizeof(t1_op2_user_levels_begin) / sizeof(t1_op2_user_levels_begin[0]); - - std::vector<tier> expected_tiers_1; - - expected_tiers_1.push_back(tier(100)); - expected_tiers_1.push_back(tier(4, t1_op1_user_levels_begin, t1_op1_user_levels_end)); - expected_tiers_1.push_back(tier(4, t1_op2_user_levels_begin, t1_op2_user_levels_end)); - - const level t2_user_levels_begin[3] = { level(), level::make_added(2), level::make_lower_bounded(-10) }; - const level *t2_user_levels_end = t2_user_levels_begin + sizeof(t2_user_levels_begin) / sizeof(t2_user_levels_begin[0]); - tier t2(-32, t2_user_levels_begin, t2_user_levels_end); - - const level t2_op1_user_levels_begin[3] = { level::make_added(2), level::make_added(6), level::make_lower_bounded(-10) }; - const level *t2_op1_user_levels_end = t2_op1_user_levels_begin + sizeof(t2_op1_user_levels_begin) / sizeof(t2_op1_user_levels_begin[0]); - - const level t2_op2_user_levels_begin[3] = { level::make_added(1), level::make_added(2), level::make_lower_bounded(5) }; - const level *t2_op2_user_levels_end = t2_op2_user_levels_begin + sizeof(t2_op2_user_levels_begin) / sizeof(t2_op2_user_levels_begin[0]); - - std::vector<tier> expected_tiers_2; - expected_tiers_2.push_back(tier(100, t2_user_levels_begin, t2_user_levels_end)); - expected_tiers_2.push_back(tier(-32, t2_op1_user_levels_begin, t2_op1_user_levels_end)); - expected_tiers_2.push_back(tier(-32, t2_op2_user_levels_begin, t2_op2_user_levels_end)); - LOG_TRACE(logger, "Testing sums, lubs, and glbs of three tiers."); + LOG_TRACE(logger, "Testing sums, lubs, and glbs of three tier operations."); // Combined values. Each vector is a matrix where [i][j] contains // the combination of entries i and j for i<=j. Combined values @@ -1373,8 +1242,6 @@ private: const tier_operation &op1(ops[i]); CPPUNIT_ASSERT_EQUAL(op_renderings[i], boost::lexical_cast<std::string>(op1)); - CPPUNIT_ASSERT_EQUAL(expected_tiers_1[i], op1.apply(t1)); - CPPUNIT_ASSERT_EQUAL(expected_tiers_2[i], op1.apply(t2)); for(std::size_t j = 0; j < ops.size(); ++j) { |