summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Burrows <dburrows@debian.org>2010-03-05 19:09:50 -0800
committerDaniel Burrows <dburrows@debian.org>2010-03-05 19:09:50 -0800
commit58b44d3be06d1e2156c93039fc2a80cf4cecb7e1 (patch)
tree5e2c6ed76e8d3260abbd1e668f9f295eb18f6a7a
parent60c099c45c50d44432af03010f6027054de22c2a (diff)
downloadaptitude-58b44d3be06d1e2156c93039fc2a80cf4cecb7e1.tar.gz
Overhaul the resolver to distinguish between tiers and changes to tiers; this is the first step towards being able to minimize the number of changes meeting a criterion.
The biggest change for this is that the new cost objects (tier operations) are not totally ordered, so various places that used to take a maximum now take a least-upper-bound instead; similarly for minimum and greatest-lower-bound. Still to do: find a sound way to allow the resolver to add together costs instead of upper-bounding them: "this change will force us to remove 10 packages". The new code seems to be a little too slow -- probably it lost some optimizations by accident. It does seem to be correct, though.
Diffstat
-rw-r--r--configure.ac1
-rw-r--r--src/generic/apt/aptitude_resolver.cc117
-rw-r--r--src/generic/apt/aptitude_resolver.h35
-rw-r--r--src/generic/apt/aptitude_resolver_universe.cc138
-rw-r--r--src/generic/apt/aptitude_resolver_universe.h23
-rw-r--r--src/generic/problemresolver/problemresolver.h740
-rw-r--r--src/generic/problemresolver/promotion_set.h666
-rw-r--r--src/generic/problemresolver/search_graph.h117
-rw-r--r--src/generic/problemresolver/tier.h15
-rw-r--r--src/generic/problemresolver/tier_limits.cc12
-rw-r--r--src/generic/problemresolver/tier_limits.h11
-rw-r--r--src/generic/util/compare3.h18
-rw-r--r--src/gtk/resolver.cc8
-rw-r--r--src/solution_fragment.cc1
-rw-r--r--tests/Makefile.am3
-rw-r--r--tests/test_promotion_set.cc315
-rw-r--r--tests/test_resolver.cc35
-rw-r--r--tests/test_resolver_hints.cc25
18 files changed, 1035 insertions, 1245 deletions
diff --git a/configure.ac b/configure.ac
index d19e35ac..ab270b4d 100644
--- a/configure.ac
+++ b/configure.ac
@@ -89,6 +89,7 @@ boost/shared_ptr.hpp dnl
boost/test/unit_test.hpp dnl
boost/unordered_map.hpp dnl
boost/unordered_set.hpp dnl
+boost/variant.hpp dnl
boost/weak_ptr.hpp dnl
,
,
diff --git a/src/generic/apt/aptitude_resolver.cc b/src/generic/apt/aptitude_resolver.cc
index a7b3801d..874b6199 100644
--- a/src/generic/apt/aptitude_resolver.cc
+++ b/src/generic/apt/aptitude_resolver.cc
@@ -55,9 +55,9 @@ namespace
* base tier, but whose subordinate values have been set
* appropriately for the given version.
*/
- tier specialize_tier(const tier &base,
- const pkgCache::VerIterator &ver,
- pkgPolicy *policy)
+ tier_operation specialize_tier_op(const tier_operation &base,
+ const pkgCache::VerIterator &ver,
+ pkgPolicy *policy)
{
if(ver.end())
return base;
@@ -71,7 +71,7 @@ namespace
apt_priority = std::max(apt_priority, pin);
}
- return tier_operation::make_advance_user_level(0, -apt_priority).apply(base);
+ return base + tier_operation::make_advance_user_level(0, -apt_priority);
}
}
}
@@ -190,8 +190,8 @@ std::ostream &operator<<(std::ostream &out, const aptitude_resolver::hint &hint)
out << "tweak(" << hint.get_score() << ")";
break;
- case aptitude_resolver::hint::increase_tier_to:
- out << "increase-tier-to(" << hint.get_tier() << ")";
+ case aptitude_resolver::hint::compose_tier_op:
+ out << "increase-tier-to(" << hint.get_tier_op().get_user_level(0) << ")";
break;
default:
@@ -412,18 +412,15 @@ int aptitude_resolver::hint::compare(const hint &other) const
}
else
{
- if(type == increase_tier_to)
+ if(type == compose_tier_op)
{
- if(tier_val < other.tier_val)
- {
- TRACE_HINTS_INEQUAL(-1, "[tier]");
- return -1;
- }
- else if(other.tier_val < tier_val)
- {
- TRACE_HINTS_INEQUAL(1, "[tier]");
- return 1;
- }
+ int cmp = tier_op_val.compare(other.tier_op_val);
+ if(cmp < 0)
+ TRACE_HINTS_INEQUAL(-1, "[tier]");
+ else if(cmp > 0)
+ TRACE_HINTS_INEQUAL(1, "[tier]");
+
+ return cmp;
}
const int selection_compare = selection.compare(other.selection);
@@ -474,7 +471,7 @@ bool aptitude_resolver::hint::parse(const std::string &hint, aptitude_resolver::
while(start != hint.end() && isspace(*start))
++start;
- tier parsed_tier;
+ tier_operation parsed_tier_op;
if(action == "increase-tier-to")
{
if(start == hint.end())
@@ -496,7 +493,7 @@ bool aptitude_resolver::hint::parse(const std::string &hint, aptitude_resolver::
while(start != hint.end() && isspace(*start))
++start;
- parsed_tier = aptitude_universe::parse_tier(tier_number);
+ parsed_tier_op = tier_operation::make_advance_user_level(0, aptitude_universe::parse_level(tier_number));
}
if(start == hint.end())
@@ -625,7 +622,7 @@ bool aptitude_resolver::hint::parse(const std::string &hint, aptitude_resolver::
else if(action == "approve")
out = make_mandate(target, selection);
else if(action == "increase-tier-to")
- out = make_increase_tier_to(target, selection, parsed_tier);
+ out = make_compose_tier_op(target, selection, parsed_tier_op);
else
{
unsigned long score_tweak = 0;
@@ -674,7 +671,7 @@ aptitude_resolver::aptitude_resolver(int step_score,
<< ", infinity = " << infinity << ", resolution_score = " << resolution_score
<< ", future_horizon = " << future_horizon << ".");
- tier keep_all_tier(aptitude_universe::get_keep_all_tier());
+ tier_operation keep_all_tier_op(aptitude_universe::get_keep_all_tier_op());
set_remove_stupid(aptcfg->FindB(PACKAGE "::ProblemResolver::Remove-Stupid-Pairs", true));
@@ -701,12 +698,12 @@ aptitude_resolver::aptitude_resolver(int step_score,
if(discardNullSolution)
{
LOG_DEBUG(loggerScores, "Rejecting the solution that reverts all the user's actions (" << keep_all_solution << ")");
- add_promotion(keep_all_solution, tier_limits::conflict_tier);
+ add_promotion(keep_all_solution, tier_limits::increase_to_conflict_op);
}
- else if(tier_limits::minimum_tier < keep_all_tier)
+ else if(keep_all_tier_op != tier_operation())
{
- LOG_DEBUG(loggerTiers, "Promoting the solution that reverts all the user's actions (" << keep_all_solution << ") to tier " << keep_all_tier);
- add_promotion(keep_all_solution, keep_all_tier);
+ LOG_DEBUG(loggerTiers, "Promoting the solution that reverts all the user's actions (" << keep_all_solution << ") to tier " << keep_all_tier_op);
+ add_promotion(keep_all_solution, keep_all_tier_op);
}
}
else
@@ -1105,12 +1102,12 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
const std::map<package, bool> &initial_state_manual_flags,
const std::vector<hint> &hints)
{
- tier safe_tier(aptitude_universe::get_safe_tier());
- tier keep_all_tier(aptitude_universe::get_keep_all_tier());
- tier remove_tier(aptitude_universe::get_remove_tier());
- tier break_hold_tier(aptitude_universe::get_break_hold_tier());
- tier non_default_tier(aptitude_universe::get_non_default_tier());
- tier remove_essential_tier(aptitude_universe::get_remove_essential_tier());
+ tier_operation safe_tier_op(aptitude_universe::get_safe_tier_op());
+ tier_operation keep_all_tier_op(aptitude_universe::get_keep_all_tier_op());
+ tier_operation remove_tier_op(aptitude_universe::get_remove_tier_op());
+ tier_operation break_hold_tier_op(aptitude_universe::get_break_hold_tier_op());
+ tier_operation non_default_tier_op(aptitude_universe::get_non_default_tier_op());
+ tier_operation remove_essential_tier_op(aptitude_universe::get_remove_essential_tier_op());
LOG_TRACE(loggerScores, "Setting up action scores; score parameters: preserver_score = " << preserve_score
<< ", auto_score = " << auto_score << ", remove_score = " << remove_score
@@ -1122,10 +1119,10 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
<< ", break_hold_score = " << break_hold_score
<< ", allow_break_holds_and_forbids = " << (allow_break_holds_and_forbids ? "true" : "false")
<< ", default_resolution_score = " << default_resolution_score);
- LOG_TRACE(loggerTiers, "Setting up action scores; tier parameters: safe_tier = " << safe_tier
- << ", keep_all_tier = " << keep_all_tier << ", remove_tier = " << remove_tier
- << ", break_hold_tier = " << break_hold_tier << ", non_default_tier = "
- << non_default_tier << ", remove_essential_tier = " << remove_essential_tier << ".");
+ LOG_TRACE(loggerTiers, "Setting up action scores; tier parameters: safe_tier_op = " << safe_tier_op
+ << ", keep_all_tier_op = " << keep_all_tier_op << ", remove_tier_op = " << remove_tier_op
+ << ", break_hold_tier_op = " << break_hold_tier_op << ", non_default_tier_op = "
+ << non_default_tier_op << ", remove_essential_tier_op = " << remove_essential_tier_op << ".");
cwidget::util::ref_ptr<aptitude::matching::search_cache>
search_info(aptitude::matching::search_cache::create());
@@ -1231,13 +1228,13 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
// OK, apply the hint.
switch(h.get_type())
{
- case hint::increase_tier_to:
+ case hint::compose_tier_op:
{
- tier v_tier(specialize_tier(h.get_tier(),
- v.get_ver(),
- policy));
- LOG_DEBUG(loggerTiers, "** Tier: " << v_tier << " for " << v << " due to the hint " << h);
- set_version_min_tier(v, v_tier);
+ tier_operation v_tier_op(specialize_tier_op(h.get_tier_op(),
+ v.get_ver(),
+ policy));
+ LOG_DEBUG(loggerTiers, "** Tier op: " << v_tier_op << " for " << v << " due to the hint " << h);
+ modify_version_tier_op(v, v_tier_op);
}
break;
@@ -1283,7 +1280,7 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
add_version_score(v, auto_score);
}
- // No change to the tier in this case.
+ // No change to the tier operation in this case.
}
// Ok, if this version is selected it'll be a change.
else if(apt_ver == p.get_pkg().CurrentVer())
@@ -1297,11 +1294,11 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
add_version_score(v, keep_score);
}
- tier v_tier(specialize_tier(safe_tier, v.get_ver(), policy));
+ tier_operation v_tier_op(specialize_tier_op(safe_tier_op, v.get_ver(), policy));
LOG_DEBUG(loggerTiers,
- "** Tier: " << v_tier << " for " << v
+ "** Tier op: " << v_tier_op << " for " << v
<< " because it is the currently installed version of a package (" PACKAGE "::ProblemResolver::Safe-Tier)");
- set_version_min_tier(v, v_tier);
+ modify_version_tier_op(v, v_tier_op);
}
else if(apt_ver.end())
{
@@ -1314,11 +1311,11 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
add_version_score(v, remove_score);
}
- tier v_tier(specialize_tier(remove_tier, v.get_ver(), policy));
+ tier_operation v_tier_op(specialize_tier_op(remove_tier_op, v.get_ver(), policy));
LOG_DEBUG(loggerTiers,
- "** Tier: " << v_tier << " for " << v
+ "** Tier op: " << v_tier_op << " for " << v
<< " because it represents the removal of a package (" PACKAGE "::ProblemResolver::Removal-Tier)");
- set_version_min_tier(v, v_tier);
+ modify_version_tier_op(v, v_tier_op);
}
else if(apt_ver == (*cache)[p.get_pkg()].CandidateVerIter(*cache))
{
@@ -1343,11 +1340,11 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
}
}
- tier v_tier(specialize_tier(safe_tier, v.get_ver(), policy));
+ tier_operation v_tier_op(specialize_tier_op(safe_tier_op, v.get_ver(), policy));
LOG_DEBUG(loggerTiers,
- "** Tier: " << v_tier << " for " << v
+ "** Tier operation: " << v_tier_op << " for " << v
<< " because it is the default install version of a package (" PACKAGE "::ProblemResolver::Safe-Tier).");
- set_version_min_tier(v, v_tier);
+ modify_version_tier_op(v, v_tier_op);
}
else
// We know that:
@@ -1363,11 +1360,11 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
<< " because it is a non-default version (" PACKAGE "::ProblemResolver::NonDefaultScore).");
add_version_score(v, non_default_score);
- tier v_tier(specialize_tier(non_default_tier, v.get_ver(), policy));
+ tier_operation v_tier_op(specialize_tier_op(non_default_tier_op, v.get_ver(), policy));
LOG_DEBUG(loggerTiers,
- "** Tier: " << v_tier << " for " << v
+ "** Tier op: " << v_tier_op << " for " << v
<< " because it is a non-default version (" PACKAGE "::ProblemResolver::Non-Default-Tier).");
- set_version_min_tier(v, v_tier);
+ modify_version_tier_op(v, v_tier_op);
}
// This logic is slightly duplicated in resolver_manger.cc,
@@ -1386,11 +1383,11 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
reject_version(v);
}
- tier v_tier(specialize_tier(break_hold_tier, v.get_ver(), policy));
+ tier_operation v_tier_op(specialize_tier_op(break_hold_tier_op, v.get_ver(), policy));
LOG_DEBUG(loggerTiers,
- "** Tier: " << v_tier << " for " << v
+ "** Tier op: " << v_tier_op << " for " << v
<< " because it breaks a hold/forbid (" PACKAGE "::ProblemResolver::Break-Hold-Tier).");
- set_version_min_tier(v, v_tier);
+ modify_version_tier_op(v, v_tier_op);
}
// In addition, add the essential-removal score:
@@ -1408,11 +1405,11 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
"** Rejecting " << v << " because it represents removing an essential package.");
reject_version(v);
- tier v_tier(specialize_tier(remove_essential_tier, v.get_ver(), policy));
+ tier_operation v_tier_op(specialize_tier_op(remove_essential_tier_op, v.get_ver(), policy));
LOG_DEBUG(loggerTiers,
- "** Tier: " << v_tier << " for " << v
+ "** Tier op: " << v_tier_op << " for " << v
<< " because it represents removing an essential package.");
- set_version_min_tier(v, v_tier);
+ modify_version_tier_op(v, v_tier_op);
}
// Look for a conflicts/provides/replaces.
diff --git a/src/generic/apt/aptitude_resolver.h b/src/generic/apt/aptitude_resolver.h
index 50d35c6f..a732504b 100644
--- a/src/generic/apt/aptitude_resolver.h
+++ b/src/generic/apt/aptitude_resolver.h
@@ -1,7 +1,7 @@
// aptitude_resolver.h -*-c++-*-
//
//
-// Copyright (C) 2005, 2008-2009 Daniel Burrows
+// Copyright (C) 2005, 2008-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
@@ -82,9 +82,10 @@ public:
enum hint_type
{
/** \brief A hint that one or more package versions should
- * have their tier increased.
+ * have their tier operations composed with this hint's
+ * operation.
*/
- increase_tier_to,
+ compose_tier_op,
/** \brief A hint that one or more package versions should be
* rejected.
*/
@@ -276,46 +277,46 @@ public:
private:
hint_type type;
int score;
- tier tier_val;
+ tier_operation tier_op_val;
cwidget::util::ref_ptr<aptitude::matching::pattern> target;
version_selection selection;
- hint(hint_type _type, int _score, tier _tier_val,
+ hint(hint_type _type, int _score, tier_operation _tier_op_val,
const cwidget::util::ref_ptr<aptitude::matching::pattern> &_target,
version_selection _selection)
- : type(_type), score(_score), tier_val(_tier_val),
+ : type(_type), score(_score), tier_op_val(_tier_op_val),
target(_target), selection(_selection)
{
}
public:
hint()
- : type((hint_type)-1), score(-1), tier_val(), target(NULL), selection()
+ : type((hint_type)-1), score(-1), tier_op_val(), target(NULL), selection()
{
}
~hint();
/** \brief Create a hint that increases the tier of a version. */
- static hint make_increase_tier_to(const cwidget::util::ref_ptr<aptitude::matching::pattern> &target,
- const version_selection &selection,
- tier tier_val)
+ static hint make_compose_tier_op(const cwidget::util::ref_ptr<aptitude::matching::pattern> &target,
+ const version_selection &selection,
+ tier_operation tier_op_val)
{
- return hint(increase_tier_to, 0, tier_val, target, selection);
+ return hint(compose_tier_op, 0, tier_op_val, target, selection);
}
/** \brief Create a hint that rejects a version or versions of a package. */
static hint make_reject(const cwidget::util::ref_ptr<aptitude::matching::pattern> &target,
const version_selection &selection)
{
- return hint(reject, 0, tier(), target, selection);
+ return hint(reject, 0, tier_operation(), target, selection);
}
/** \brief Create a hint that mandates a version or versions of a package. */
static hint make_mandate(const cwidget::util::ref_ptr<aptitude::matching::pattern> &target,
const version_selection &selection)
{
- return hint(mandate, 0, tier(), target, selection);
+ return hint(mandate, 0, tier_operation(), target, selection);
}
/** \brief Create a hint that adjusts the score of a package. */
@@ -323,7 +324,7 @@ public:
const version_selection &selection,
int score)
{
- return hint(tweak_score, score, tier(), target, selection);
+ return hint(tweak_score, score, tier_operation(), target, selection);
}
/** \brief Parse a resolver hint definition.
@@ -385,10 +386,10 @@ public:
*/
int get_score() const { return score; }
- /** \brief For tier-tweaking hints, get the tier associated with
- * the hint.
+ /** \brief For tier operation changing hints, get the tier
+ * operation associated with the hint.
*/
- const tier &get_tier() const { return tier_val; }
+ const tier_operation &get_tier_op() const { return tier_op_val; }
/** \brief Return the pattern identifying the package or packages
* to be adjusted.
diff --git a/src/generic/apt/aptitude_resolver_universe.cc b/src/generic/apt/aptitude_resolver_universe.cc
index 97f6ba23..c3e483cd 100644
--- a/src/generic/apt/aptitude_resolver_universe.cc
+++ b/src/generic/apt/aptitude_resolver_universe.cc
@@ -802,158 +802,62 @@ std::ostream &operator<<(ostream &out, const aptitude_resolver_dep &d)
}
-tier aptitude_universe::parse_tier(const std::string &s)
+int aptitude_universe::parse_level(const std::string &s)
{
typedef generic_problem_resolver<aptitude_universe> aptitude_resolver;
if(s == "conflict")
- return tier_limits::conflict_tier;
+ // Note that this is slightly broken (it should send it to the
+ // conflict tier, not just a high level) -- but the whole tier
+ // configuration system needs to be rewritten anyway.
+ return tier_limits::conflict_structural_level;
else if(s == "minimum" || s == "")
- return tier_limits::minimum_tier;
+ return tier_limits::minimum_level;
else
{
char *endptr;
- level n = level::make_lower_bounded(static_cast<int>(strtol(s.c_str(), &endptr, 0)));
+ int n = static_cast<int>(strtol(s.c_str(), &endptr, 0));
if(*endptr != '\0')
{
std::string msg(ssprintf(N_("Invalid search tier \"%s\" (not \"conflict\", \"minimum\", or an integer)."), s.c_str()));
LOG_ERROR(Loggers::getAptitudeResolverTiers(), msg);
_error->Error(_(msg.c_str()));
- return tier_limits::minimum_tier;
+ return tier_limits::minimum_level;
}
else
- {
- return tier(tier_limits::minimum_level,
- &n, (&n) + 1);
- }
+ return n;
}
}
-tier aptitude_universe::get_safe_tier()
+tier_operation aptitude_universe::get_safe_tier_op()
{
- return parse_tier(aptcfg->Find(PACKAGE "::ProblemResolver::Safe-Tier", "10000"));
+ return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Safe-Tier", "10000")));
}
-tier aptitude_universe::get_keep_all_tier()
+tier_operation aptitude_universe::get_keep_all_tier_op()
{
- return parse_tier(aptcfg->Find(PACKAGE "::ProblemResolver::Keep-All-Tier", "20000"));
+ return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Keep-All-Tier", "20000")));
}
-tier aptitude_universe::get_remove_tier()
+tier_operation aptitude_universe::get_remove_tier_op()
{
- return parse_tier(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Tier", "10000"));
+ return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Tier", "10000")));
}
-tier aptitude_universe::get_break_hold_tier()
+tier_operation aptitude_universe::get_break_hold_tier_op()
{
- return parse_tier(aptcfg->Find(PACKAGE "::ProblemResolver::Break-Hold-Tier", "40000"));
+ return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Break-Hold-Tier", "40000")));
}
-tier aptitude_universe::get_non_default_tier()
+tier_operation aptitude_universe::get_non_default_tier_op()
{
- return parse_tier(aptcfg->Find(PACKAGE "::ProblemResolver::Non-Default-Tier", "50000"));
+ return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Non-Default-Tier", "50000")));
}
-tier aptitude_universe::get_remove_essential_tier()
+tier_operation aptitude_universe::get_remove_essential_tier_op()
{
- return parse_tier(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Essential-Tier", "60000"));
+ return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Essential-Tier", "60000")));
}
-void aptitude_universe::get_named_tiers(std::vector<std::pair<tier, std::string> > &out)
-{
- out.push_back(std::make_pair(get_safe_tier(), _("Safe actions")));
- out.push_back(std::make_pair(get_keep_all_tier(), _("Cancel all user actions")));
- out.push_back(std::make_pair(get_remove_tier(), _("Remove packages")));
- out.push_back(std::make_pair(get_break_hold_tier(), _("Modify held packages")));
- out.push_back(std::make_pair(get_non_default_tier(), _("Install versions from non-default sources")));
- out.push_back(std::make_pair(get_remove_essential_tier(), _("Remove essential packages")));
-
- const Configuration::Item *tree = aptcfg->Tree(PACKAGE "::ProblemResolver::Tier-Names");
-
- if(tree == NULL)
- return;
-
- for(const Configuration::Item *item = tree->Child; item != NULL; item = item->Next)
- {
- // Each sub-tree should have a Name and a Tier value.
- bool has_name = false, has_tier = false;
- std::string item_name;
- tier item_tier;
- for(Configuration::Item const *sub_item = item->Child; sub_item != NULL; sub_item = sub_item->Next)
- {
- if(stringcasecmp(sub_item->Tag, "Name") == 0)
- {
- has_name = true;
- item_name = sub_item->Value;
- }
- else if(stringcasecmp(sub_item->Tag, "Tier") == 0)
- {
- has_tier = true;
- item_tier = parse_tier(sub_item->Value);
- }
- }
-
- if(has_name && has_tier)
- out.push_back(std::make_pair(item_tier, item_name));
- else
- {
- if(has_name)
- LOG_ERROR(Loggers::getAptitudeResolverTiers(),
- ssprintf(_("The tier \"%s\", configured in %s::ProblemResolver::Tier-Names, is missing a Tier entry."),
- item_name.c_str(), PACKAGE));
- else if(has_tier)
- {
- if(item_tier.get_num_user_levels() < 1)
- LOG_ERROR(Loggers::getAptitudeResolverTiers(),
- "A tier is lacking both a name and a value.");
- else
- LOG_ERROR(Loggers::getAptitudeResolverTiers(),
- ssprintf(_("The tier %d, configured in %s::ProblemResolver::Tier-Names, is missing a Name entry."),
- item_tier.get_user_level(0).get_value(), PACKAGE));
- }
- else
- ; // Assume this is junk that got in accidentally.
- }
- }
-}
-
-std::string aptitude_universe::get_tier_name(const tier &t)
-{
- typedef generic_problem_resolver<aptitude_universe> aptitude_resolver;
- if(t >= tier_limits::conflict_tier)
- return "Unsolvable search nodes"; // Should never happen in a returned solution.
- else if(t >= tier_limits::already_generated_tier)
- return "Already generated solutions"; // Should never happen in a returned solution.
- else if(t >= tier_limits::defer_tier)
- return "Deferred search nodes"; // Should never happen in a returned solution.
- else if(t.get_num_user_levels() == 0)
- return "Initial tier";
- else
- {
- std::vector<std::pair<tier, std::string> > named_tiers;
- get_named_tiers(named_tiers);
-
- std::string name;
- for(std::vector<std::pair<tier, std::string> >::const_iterator it =
- named_tiers.begin(); it != named_tiers.end(); ++it)
- {
- if(it->first.get_num_user_levels() > 0 &&
- it->first.get_user_level(0) == t.get_user_level(0) &&
- t >= it->first)
- {
- if(!name.empty())
- name += ", ";
- name += it->second;
- }
- }
-
- if(name.empty())
- return ssprintf("%d", t.get_user_level(0).get_value());
- else
- return ssprintf("%s (%d)", name.c_str(), t.get_user_level(0).get_value());
- }
-}
-
-
bool aptitude_universe::is_candidate_for_initial_set(const aptitude_resolver_dep &d) const
{
if(!d.is_soft())
diff --git a/src/generic/apt/aptitude_resolver_universe.h b/src/generic/apt/aptitude_resolver_universe.h
index 95f40f44..04ec87ac 100644
--- a/src/generic/apt/aptitude_resolver_universe.h
+++ b/src/generic/apt/aptitude_resolver_universe.h
@@ -32,6 +32,7 @@
#include "aptcache.h"
#include <generic/problemresolver/tier.h>
+#include <generic/problemresolver/tier_operation.h>
#include <limits.h>
@@ -1299,23 +1300,15 @@ public:
}
// Configuration helper -- should this be somewhere better?
- static tier parse_tier(const std::string &s);
+ static int parse_level(const std::string &s);
// Configuration fetchers.
- static tier get_safe_tier();
- static tier get_keep_all_tier();
- static tier get_remove_tier();
- static tier get_break_hold_tier();
- static tier get_non_default_tier();
- static tier get_remove_essential_tier();
-
- /** \brief Retrieve the tiers that the user has assigned
- * names to.
- */
- static void get_named_tiers(std::vector<std::pair<tier, std::string> > &out);
-
- /** \brief Return a string description of the given tier. */
- static std::string get_tier_name(const tier &t);
+ static tier_operation get_safe_tier_op();
+ static tier_operation get_keep_all_tier_op();
+ static tier_operation get_remove_tier_op();
+ static tier_operation get_break_hold_tier_op();
+ static tier_operation get_non_default_tier_op();
+ static tier_operation get_remove_essential_tier_op();
};
/** \brief Write an aptitude_resolver_package to the given stream. */
diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h
index 19da60f3..b04793d3 100644
--- a/src/generic/problemresolver/problemresolver.h
+++ b/src/generic/problemresolver/problemresolver.h
@@ -59,6 +59,7 @@
#include "search_graph.h"
#include "tier.h"
#include "tier_limits.h"
+#include "tier_operation.h"
#include "log4cxx/consoleappender.h"
#include "log4cxx/logger.h"
@@ -577,8 +578,8 @@ private:
typedef ExtractPackageId PackageHash;
- /** Compares steps according to their "goodness": their tier, then
- * thier score, then their contents.
+ /** Compares steps according to their "goodness": their effective
+ * tier, then thier score, then their contents.
*
* The comparisons are reversed, so better solutions compare
* "below" worse ones.
@@ -603,9 +604,9 @@ private:
// Note that *lower* tiers come "before" higher tiers, hence the
// reversed comparison there.
- if(step1.step_tier < step2.step_tier)
+ if(step1.effective_step_tier < step2.effective_step_tier)
return true;
- else if(step2.step_tier < step1.step_tier)
+ else if(step2.effective_step_tier < step1.effective_step_tier)
return false;
else if(step2.score < step1.score)
return true;
@@ -904,7 +905,7 @@ private:
* solution might get a higher tier if we can prove that it will
* eventually have one anyway).
*/
- tier *version_tiers;
+ tier_operation *version_tier_ops;
/** \brief Used to track whether a single choice is approved or
* rejected.
@@ -1106,9 +1107,9 @@ private:
// (the alternative is to expand the types of choices we can
// handle, but that would impose costs on the rest of the
// program for a feature that would never be used)
- promotion p(choice_set(), tier_limits::defer_tier,
+ promotion p(choice_set(), tier_limits::increase_to_defer_op,
get_child());
- resolver.increase_solver_tier_everywhere_with_dep(deferred_choice, p);
+ resolver.increase_solver_tier_op_everywhere_with_dep(deferred_choice, p);
}
}
};
@@ -1279,7 +1280,7 @@ private:
non_incipient);
if(non_incipient.get_has_value() &&
- s.step_tier < non_incipient.get_value().get_tier())
+ s.effective_step_tier < 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
@@ -1288,7 +1289,7 @@ private:
promotions.find_highest_promotion_for(s.actions);
if(found_promotion != promotions.end() &&
- s.step_tier < found_promotion->get_tier())
+ s.effective_step_tier < found_promotion->get_tier())
LOG_ERROR(logger, "In step " << s.step_num << ": the embedded promotion "
<< *found_promotion << " was not applied.");
}
@@ -1355,7 +1356,7 @@ private:
*/
bool irrelevant(const step &s)
{
- const tier &s_tier = s.step_tier;
+ const tier &s_tier = s.effective_step_tier;
if(s_tier >= tier_limits::conflict_tier)
{
LOG_TRACE(logger, "Step " << s.step_num << " is irrelevant: it contains a conflict.");
@@ -1384,25 +1385,60 @@ private:
{
step &s(graph.get_step(step_num));
- if(s.step_tier == t)
+ s.base_step_tier = t;
+
+ update_effective_step_tier(step_num);
+ }
+
+ /** \brief Update the operation that computes the *effective* tier
+ * of a step.
+ *
+ * Updates the effective tier itself as a side effect.
+ */
+ void set_effective_step_tier_op(int step_num,
+ const tier_operation &t_op)
+ {
+ step &s(graph.get_step(step_num));
+
+ s.effective_step_tier_op = t_op;
+
+ update_effective_step_tier(step_num);
+ }
+
+ /** \brief Update the effective tier of a step.
+ *
+ * This should only be invoked by set_base_step_tier 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)
+ {
+ step &s(graph.get_step(step_num));
+
+ tier new_effective_step_tier =
+ s.effective_step_tier_op.apply(s.base_step_tier);
+
+ if(s.effective_step_tier == new_effective_step_tier)
return;
- if(s.is_blessed_solution && t >= tier_limits::already_generated_tier)
+ if(s.is_blessed_solution &&
+ new_effective_step_tier >= tier_limits::already_generated_tier)
{
LOG_TRACE(logger, "Step " << s.step_num
- << " is a blessed solution; ignoring the attempt to promote it to tier " << t);
+ << " is a blessed solution; ignoring the attempt to promote it to tier " << new_effective_step_tier);
return;
}
- LOG_TRACE(logger, "Setting the tier of step " << step_num
- << " to " << t);
+ LOG_TRACE(logger, "Setting the effective tier of step " << step_num
+ << " to " << new_effective_step_tier);
bool was_in_pending = (pending.erase(step_num) > 0);
bool was_in_pending_future_solutions = (pending_future_solutions.erase(step_num) > 0);
- if(s.step_tier >= tier_limits::defer_tier &&
- s.step_tier < tier_limits::already_generated_tier)
+ if(s.effective_step_tier >= tier_limits::defer_tier &&
+ s.effective_step_tier < tier_limits::already_generated_tier)
{
if(was_in_pending)
--num_deferred;
@@ -1410,7 +1446,7 @@ private:
--num_deferred;
}
- s.step_tier = t;
+ s.effective_step_tier = new_effective_step_tier;
if(was_in_pending)
@@ -1419,15 +1455,15 @@ private:
pending_future_solutions.insert(step_num);
- if(s.step_tier >= tier_limits::defer_tier &&
- s.step_tier < tier_limits::already_generated_tier)
+ if(s.effective_step_tier >= tier_limits::defer_tier &&
+ s.effective_step_tier < tier_limits::already_generated_tier)
{
if(was_in_pending)
++num_deferred;
if(was_in_pending_future_solutions)
++num_deferred;
}
- else if(s.step_tier < tier_limits::defer_tier)
+ else if(s.effective_step_tier < tier_limits::defer_tier)
{
// Clear the "finished" flag if this is now a pending
// candidate.
@@ -1688,8 +1724,9 @@ private:
p.get_choices().for_each(find_promotion_f);
}
- /** \brief For each promotion hit, increase its tier in a solver set
- * if it's incipient and in an action set if it's not.
+ /** \brief For each match of a promotion, increase the tier
+ * operation in a solver set if it's incipient; increase the
+ * effective tier operation if it's not.
*/
class do_process_promotion
{
@@ -1705,13 +1742,14 @@ private:
void incipient(int step_num, const choice &solver) const
{
- resolver.increase_solver_tier(resolver.graph.get_step(step_num),
- p, solver);
+ resolver.increase_solver_tier_op(resolver.graph.get_step(step_num),
+ p, solver);
}
void active(int step_num) const
{
- resolver.set_step_tier(step_num, p.get_tier());
+ step &s = graph.get_step(step_num);
+ resolver.increase_effective_step_tier_op(s, p);
resolver.graph.schedule_promotion_propagation(step_num, p);
}
};
@@ -1734,17 +1772,17 @@ private:
// time.
//
// Only solvers whose tier equals the given tier are recomputed.
- class recompute_solver_tier_for_dep
+ class recompute_solver_tier_op_for_dep
{
generic_problem_resolver &resolver;
step &s;
- const tier &t;
+ const tier_operation &t_op;
public:
- recompute_solver_tier_for_dep(generic_problem_resolver &_resolver,
+ recompute_solver_tier_op_for_dep(generic_problem_resolver &_resolver,
step &_s,
- const tier &_t)
- : resolver(_resolver), s(_s), t(_t)
+ const tier_operation &_t_op)
+ : resolver(_resolver), s(_s), t_op(_t_op)
{
}
@@ -1753,7 +1791,7 @@ private:
{
for(typename imm::list<dep>::const_iterator it = deps.begin();
it != deps.end(); ++it)
- resolver.recompute_solver_tier(s, *it, solver, t);
+ resolver.recompute_solver_tier_op(s, *it, solver, t_op.get_structural_level());
return true;
}
@@ -1761,16 +1799,28 @@ private:
/** \brief For each promotion hit, recompute the solver tier if it's
* an incipient promotion and the step tier otherwise.
+ *
+ * The associated tier operation is used as a filter. While it's
+ * hard in general to tell if a promotion affected a step (without
+ * actually tracking the set of promotions that touched it), we can
+ * be sure that if a promotion affected a step, the structural tier
+ * of the step was increased to the structural tier of the
+ * promotion. Thus, if the step's structural tier is *below* that
+ * of the promotion, it couldn't have been affected by the
+ * promotion and hence doesn't need to be recomputed.
+ *
+ * (that's a useful heuristic because most of the promotions that
+ * we'll retract promote to the deferral tier)
*/
class recompute_tier_hits
{
generic_problem_resolver &resolver;
- const tier &t;
+ const tier_operation &t_op;
public:
recompute_tier_hits(generic_problem_resolver &_resolver,
- const tier &_t)
- : resolver(_resolver), t(_t)
+ const tier_operation &_t_op)
+ : resolver(_resolver), t_op(_t_op)
{
}
@@ -1778,21 +1828,22 @@ private:
{
step &s(resolver.graph.get_step(step_num));
- recompute_solver_tier_for_dep
- recompute_solver_tier_f(resolver, s, t);
+ recompute_solver_tier_op_for_dep
+ recompute_solver_tier_op_f(resolver, s, t_op);
s.deps_solved_by_choice.for_each_key_contained_in(solver,
- recompute_solver_tier_f);
+ recompute_solver_tier_op_f);
}
void active(int step_num) const
{
step &s(resolver.graph.get_step(step_num));
- // The promotion could only have affected the step's tier if the
- // step's tier is at least as high.
- if(s.step_tier >= t)
- resolver.recompute_step_tier(resolver.graph.get_step(step_num));
+ // The promotion could only have affected the step's effective
+ // tier if the effective tier's structural level is at least as
+ // high.
+ if(s.effective_step_tier_op.get_structural_level() >= t_op.get_structural_level())
+ resolver.recompute_effective_step_tier_op(resolver.graph.get_step(step_num));
}
};
@@ -1800,7 +1851,7 @@ private:
{
LOG_TRACE(logger, "Retracting all tier assignments that might be linked to " << p);
- for_each_promotion_hit(p, recompute_tier_hits(*this, p.get_tier()));
+ for_each_promotion_hit(p, recompute_tier_hits(*this, p.get_tier_op()));
}
@@ -2001,7 +2052,7 @@ private:
}
// Rescan the solvers, maybe updating the step's tier.
- resolver.check_solvers_tier(s, new_solvers);
+ resolver.check_solvers_tier_op(s, new_solvers);
}
else
LOG_TRACE(logger, "The dependency " << d
@@ -2267,14 +2318,14 @@ private:
return rval;
}
- class invoke_recompute_solver_tier
+ class invoke_recompute_solver_tier_op
{
generic_problem_resolver &resolver;
const dep &d;
public:
- invoke_recompute_solver_tier(generic_problem_resolver &_resolver,
- const dep &_d)
+ invoke_recompute_solver_tier_op(generic_problem_resolver &_resolver,
+ const dep &_d)
: resolver(_resolver),
d(_d)
{
@@ -2287,9 +2338,9 @@ private:
step &s(resolver.graph.get_step(step_num));
if(how == search_graph::choice_mapping_action)
- resolver.recompute_step_tier(s);
+ resolver.recompute_effective_step_tier_op(s);
else
- resolver.recompute_solver_tier(s, d, c);
+ resolver.recompute_solver_tier_op(s, d, c);
return true;
}
@@ -2305,30 +2356,29 @@ private:
{
LOG_TRACE(logger, "The choice " << deferral_choice << " is no longer deferred; recomputing its tier in all steps.");
- invoke_recompute_solver_tier recompute_f(*this, deferral_dep);
+ invoke_recompute_solver_tier_op recompute_f(*this, deferral_dep);
graph.for_each_step_related_to_choice_with_dep(deferral_choice,
deferral_dep,
recompute_f);
}
- /** \brief Recompute the solver of a single tier in the given
- * step.
- *
- * The tier is only recomputed if it equals check_tier.
- * recompute_solver_tier() is used to retract promotions; if the
- * tier of the solver is not equal to the tier of the promotion
- * (passed as check_tier), then another promotion must have
- * elevated the tier even farther, so there's no need to recompute
- * it.
+ /** \brief Recompute the tier operation of a single solver in the
+ * given step.
*
- * check_tier and do_check_tier are a bit hacky, but they avoid
- * having to have two instantiations of this code.
+ * Previous versions of this code would only recompute the tier
+ * operation if it was equal to the tier of the promotion being
+ * retracted. However, with the introduction of partially ordered
+ * tiers, upper-bounding, and nonidempotent operations, this isn't
+ * sound any more. There is exactly one case where it's definitely
+ * safe, though: tier operations that don't change anything but the
+ * structural tier. Not coincidentally, this is also the only type
+ * of operation that gets retracted.
*/
- void recompute_solver_tier(step &s,
- const dep &solver_dep,
- const choice &solver,
- const tier &check_tier = tier_limits::minimum_tier,
- bool do_check_tier = false)
+ void recompute_solver_tier_op(step &s,
+ const dep &solver_dep,
+ const choice &solver,
+ const int &check_structural_level = tier_limits::minimum_level,
+ bool do_check_structural_level = false)
{
typename imm::map<dep, typename step::flyweight_dep_solvers>::node
found_solvers(s.unresolved_deps.lookup(solver_dep));
@@ -2344,17 +2394,21 @@ private:
<< " is listed in the reverse index for step "
<< s.step_num << " as a solver for "
<< solver_dep << ", but it doesn't appear in that step.");
- else if(!do_check_tier || found_solver->get_tier() == check_tier)
+ else if(!do_check_structural_level ||
+ (found_solver->get_tier_op().get_structural_level() == check_structural_level &&
+ !found_solver->get_tier_op().get_has_user_level_changes()))
{
- tier new_tier;
+ tier_operation new_tier_op;
cwidget::util::ref_ptr<expression_box<bool> > new_tier_is_deferred;
cwidget::util::ref_ptr<expression<bool> > new_tier_valid;
choice solver_with_dep(solver.copy_and_set_dep(solver_dep));
- get_solver_tier(solver_with_dep,
- new_tier, new_tier_is_deferred, new_tier_valid);
+ get_solver_intrinsic_promotion_with_deferrals(solver_with_dep,
+ new_tier_op,
+ new_tier_is_deferred,
+ new_tier_valid);
typename step::solver_information
- new_solver_inf(new_tier,
+ new_solver_inf(new_tier_op,
choice_set(),
new_tier_valid,
new_tier_is_deferred);
@@ -2376,7 +2430,7 @@ private:
//
// \todo Only do this if the tier went down, and just do a
// local recomputation otherwise?
- recompute_step_tier(s);
+ recompute_effective_step_tier_op(s);
}
}
}
@@ -2401,7 +2455,7 @@ private:
bool operator()(const promotion &p) const
{
if(blessed)
- return p.get_tier() < tier_limits::already_generated_tier;
+ return p.get_tier_op().get_structural_level() < tier_limits::already_generated_structural_level;
else
return true;
}
@@ -2437,45 +2491,71 @@ private:
for(typename boost::unordered_map<choice, promotion>::const_iterator it =
triggered_promotions.begin();
it != triggered_promotions.end(); ++it)
- increase_solver_tier(s, it->second, it->first);
+ increase_solver_tier_op(s, it->second, it->first);
+ }
+
+ tier_operation get_intrinsic_solver_op(const choice &c)
+ {
+ switch(c.get_type())
+ {
+ case choice::install_version:
+ return version_tier_ops[c.get_ver().get_id()];
+
+ case choice::break_soft_dep:
+ // \todo Store tier operations corresponding to breaking
+ // soft deps.
+ return tier_operation();
+
+ default:
+ LOG_ERROR(logger, "get_intrinsic_solver_op: bad choice type: " << c);
+ return tier_operation();
+ }
}
/** \brief Compute the basic tier information of a choice.
*
- * This is the tier it will have unless it's hit by a promotion.
+ * This is the tier it will have unless it's hit by a promotion,
+ * along with information about conditions on its tier.
*/
- void get_solver_tier(const choice &c,
- tier &out_tier,
- cwidget::util::ref_ptr<expression_box<bool> > &out_c_is_deferred,
- cwidget::util::ref_ptr<expression<bool> > &out_tier_valid)
+ void get_solver_intrinsic_promotion_with_deferrals(const choice &c,
+ tier_operation &out_tier_op,
+ cwidget::util::ref_ptr<expression_box<bool> > &out_c_is_deferred,
+ cwidget::util::ref_ptr<expression<bool> > &out_tier_valid)
{
// Right now only deferrals can be retracted; other tier
// assignments are immutable.
out_c_is_deferred = build_is_deferred_listener(c);
- out_tier = tier_limits::minimum_tier;
+ out_tier_op = tier_operation();
if(out_c_is_deferred->get_value())
{
- out_tier = tier_limits::defer_tier;
+ out_tier_op = tier_limits::increase_to_defer_op;
out_tier_valid = out_c_is_deferred->get_child();
}
else
{
out_tier_valid = cwidget::util::ref_ptr<expression<bool> >();
- switch(c.get_type())
- {
- case choice::install_version:
- out_tier = version_tiers[c.get_ver().get_id()];
- break;
-
- case choice::break_soft_dep:
- // \todo Have a tier based on breaking soft deps?
- out_tier = tier_limits::minimum_tier;
- break;
- }
+ out_tier_op = get_intrinsic_solver_op(c);
}
}
+ /** \brief Get the intrinsic tier operation of a single solver.
+ *
+ * Currently a convenience wrapper for
+ * get_solver_intrinsic_promotion.
+ */
+ tier_operation get_solver_intrinsic_op_with_deferrals(const choice &c)
+ {
+ tier_operation rval;
+ cwidget::util::ref_ptr<expression_box<bool> > dummy_is_deferred;
+ cwidget::util::ref_ptr<expression<bool> > dummy_tier_valid;
+
+ get_solver_intrinsic_promotion_with_deferrals(c, rval,
+ dummy_is_deferred, dummy_tier_valid);
+
+ return rval;
+ }
+
/** \brief Add a solver to a list of dependency solvers for a
* particular step.
*
@@ -2558,16 +2638,16 @@ private:
// The choice is added with its intrinsic tier to start with.
// Later, in step 6 of the update algorithm, we'll find promotions
// that include the new solvers and update tiers appropriately.
- tier choice_tier;
+ tier_operation choice_tier_op;
cwidget::util::ref_ptr<expression_box<bool> > choice_is_deferred;
cwidget::util::ref_ptr<expression<bool> > choice_tier_valid;
- get_solver_tier(solver, choice_tier, choice_is_deferred, choice_tier_valid);
+ get_solver_intrinsic_promotion_with_deferrals(solver, choice_tier_op, choice_is_deferred, choice_tier_valid);
LOG_TRACE(logger, "Adding the solver " << solver
- << " with initial tier " << choice_tier);
+ << " with initial tier operation " << choice_tier_op);
{
typename step::solver_information
- new_solver_inf(choice_tier,
+ new_solver_inf(choice_tier_op,
choice_set(),
choice_tier_valid,
choice_is_deferred);
@@ -2589,104 +2669,129 @@ private:
graph.bind_choice(solver, s.step_num, d);
}
- /** \brief Find the smallest tier out of the solvers of a single
- * dependency.
+ /** \brief Compute the greatest lower bound of the tier operations
+ * of the solvers of a single dependency.
*/
- class find_solvers_tier
+ class find_solvers_tier_op_lower_bound
{
- tier &output_tier;
+ maybe<tier_operation> &output_tier_op;
public:
- find_solvers_tier(tier &_output_tier)
- : output_tier(_output_tier)
+ find_solvers_tier_op_lower_bound(maybe<tier_operation> &_output_tier_op)
+ : output_tier_op(_output_tier_op)
{
- output_tier = tier_limits::maximum_tier;
+ output_tier_op = maybe<tier_operation>();
}
bool operator()(const std::pair<choice, typename step::solver_information> &p) const
{
- const tier &p_tier(p.second.get_tier());
- if(p_tier < output_tier)
- output_tier = p_tier;
+ const tier_operation &p_tier_op(p.second.get_tier_op());
+
+ if(output_tier_op.get_has_value())
+ output_tier_op = tier_operation::greatest_lower_bound(output_tier_op.get_value(),
+ p_tier_op);
+ else
+ output_tier_op = p_tier_op;
return true;
}
};
- /** \brief Find the largest tier of any dependency. */
- class find_largest_dep_tier
+ /** \brief Compute the upper bound of the lower bound of each
+ * dependency's tier operations.
+ *
+ * \note In principle, it should sometimes be possible to \e
+ * compose tiers instead of upper-bounding them, yielding stronger
+ * results (and better promotions). However, it's not safe to do
+ * that unless we're sure that the tiers don't result from
+ * "overlapping subcases", and trying to compute precisely, or even
+ * somewhat imprecisely, when that's the case seems to be NP-hard
+ * (related to independent set).
+ */
+ class find_dep_tier_op_upper_bound
{
- tier &output_tier;
+ tier_operation &output_tier_op;
generic_problem_resolver &resolver;
public:
- find_largest_dep_tier(tier &_output_tier, generic_problem_resolver &_resolver)
- : output_tier(_output_tier), resolver(_resolver)
+ find_dep_tier_op_upper_bound(tier_operation &_output_tier_op,
+ generic_problem_resolver &_resolver)
+ : output_tier_op(_output_tier_op), resolver(_resolver)
{
}
bool operator()(const std::pair<dep, typename step::dep_solvers> &p) const
{
- tier dep_tier;
+ maybe<tier_operation> dep_tier_op;
- p.second.for_each_solver(find_solvers_tier(dep_tier));
+ p.second.for_each_solver(find_solvers_tier_op_lower_bound(dep_tier_op));
- if(output_tier < dep_tier)
+ tier_operation new_output_tier_op =
+ dep_tier_op.get_has_value()
+ ? tier_operation::least_upper_bound(output_tier_op, dep_tier_op.get_value())
+ : output_tier_op;
+
+ if(output_tier_op != new_output_tier_op)
{
- LOG_TRACE(resolver.logger, "Updating the tier from "
- << output_tier << " to "
- << dep_tier << " for the dependency " << p.first);
- output_tier = dep_tier;
+ LOG_TRACE(resolver.logger, "Updating the tier operation from "
+ << output_tier_op << " to "
+ << new_output_tier_op << " for the dependency " << p.first);
+ output_tier_op = new_output_tier_op;
}
return true;
}
};
- // Look for deferrals and increase the target tier to the deferral
- // tier if necessary.
+ // Look for deferrals and increase the target tier operation to the
+ // deferral tier if necessary.
class find_deferrals
{
- tier &output_tier;
+ tier_operation &output_tier_op;
generic_problem_resolver &resolver;
public:
- find_deferrals(tier &_output_tier,
+ find_deferrals(tier_operation &_output_tier_op,
generic_problem_resolver &_resolver)
- : output_tier(_output_tier), resolver(_resolver)
+ : output_tier_op(_output_tier_op), resolver(_resolver)
{
}
bool operator()(const choice &c) const
{
- tier rval(tier_limits::minimum_tier);
+ tier_operation choice_op;
switch(c.get_type())
{
case choice::install_version:
- rval = resolver.version_tiers[c.get_ver().get_id()];
+ choice_op = resolver.version_tier_ops[c.get_ver().get_id()];
break;
default:
break;
}
- if(rval < tier_limits::defer_tier &&
- resolver.build_is_deferred_listener(c)->get_value())
- rval = tier_limits::defer_tier;
+ if(resolver.build_is_deferred_listener(c)->get_value())
+ choice_op = tier_operation::least_upper_bound(tier_limits::increase_to_defer_op,
+ choice_op);
+
+ const tier_operation new_output_tier_op =
+ tier_operation::least_upper_bound(output_tier_op, choice_op);
- if(output_tier < rval)
+ if(output_tier_op != new_output_tier_op)
{
- LOG_TRACE(resolver.logger, "Updating the tier from " << output_tier << " to " << rval
+ LOG_TRACE(resolver.logger, "Updating the tier operation from "
+ << output_tier_op << " to "
+ << new_output_tier_op
<< " for the action " << c);
- output_tier = rval;
+ output_tier_op = new_output_tier_op;
}
return true;
}
};
- /** \brief Recompute a step's tier from scratch.
+ /** \brief Recompute a step's effective tier from scratch.
*
* It is assumed that all the solvers in the step have the correct
* tier; the recomputation is based on them.
@@ -2694,58 +2799,66 @@ private:
* This is a bit of a sledgehammer. The places where this is used
* could be tuned to not need it; currently I'm just hoping it's
* invoked few enough times to not matter.
+ *
+ * (this could be done incrementally using the accumulation
+ * abilities of imm::set/imm::map; however, as noted above, I hope
+ * that this isn't invoked often enough for that to matter)
*/
- void recompute_step_tier(step &s)
+ void recompute_effective_step_tier_op(step &s)
{
- LOG_TRACE(logger, "Recomputing the tier of step " << s.step_num
- << " (was " << s.step_tier << ")");
+ LOG_TRACE(logger, "Recomputing the effective tier operation of step " << s.step_num
+ << " (was " << s.effective_step_tier << ")");
- tier new_tier(tier_limits::minimum_tier);
- s.unresolved_deps.for_each(find_largest_dep_tier(new_tier, *this));
+ tier_operation new_tier_op(tier_limits::minimum_op);
+ s.unresolved_deps.for_each(find_dep_tier_op_upper_bound(new_tier_op, *this));
// In addition to checking solvers, we need to check the action
// set. Look for existing promotions *and* for deferred entries.
- s.actions.for_each(find_deferrals(new_tier, *this));
+ //
+ // \todo Since this doesn't just find deferrals, it's really badly
+ // named. The name should be changed to something like
+ // "find_deferrals_and_promotions".
+ s.actions.for_each(find_deferrals(new_tier_op, *this));
- typename promotion_set::const_iterator found_promotion =
- promotions.find_highest_promotion_for(s.actions);
+ tier_operation found_promotion =
+ promotions.find_highest_promotion_tier_op(s.actions);
- if(found_promotion != promotions.end())
+ if(found_promotion != tier_operation())
{
- const promotion &p(*found_promotion);
+ tier_operation new_new_tier_op =
+ tier_operation::least_upper_bound(new_tier_op,
+ found_promotion);
- if(new_tier < p.get_tier())
+ if(new_new_tier_op != new_tier_op)
{
- LOG_TRACE(logger, "Updating the tier from "
- << new_tier << " to " << p.get_tier()
- << " for the promotion " << p);
- new_tier = p.get_tier();
+ LOG_TRACE(logger, "Updating the tier operation from "
+ << new_tier_op << " to "
+ << new_new_tier_op
+ << " for a promotion.");
+ new_tier_op = new_new_tier_op;
}
}
- LOG_TRACE(logger, "Recomputed the tier of step " << s.step_num
- << " (was " << s.step_tier << ", now " << new_tier << ")");
-
- set_step_tier(s.step_num, new_tier);
+ set_effective_step_tier_op(s.step_num, new_tier_op);
}
- // Calculate the tier of a dep-solvers set.
+ // Calculate the tier operation of a dep-solvers set.
class calculate_tier
{
- tier &output_tier;
+ tier_operation &output_tier_op;
public:
- calculate_tier(tier &_output_tier)
- : output_tier(_output_tier)
+ calculate_tier(tier_operation &_output_tier_op)
+ : output_tier_op(_output_tier_op)
{
- output_tier = tier_limits::maximum_tier;
+ output_tier_op = tier_limits::increase_to_maximum_op;
}
bool operator()(const std::pair<choice, typename step::solver_information> &entry) const
{
- if(entry.second.get_tier() < output_tier)
- // Maybe we have a new, lower tier.
- output_tier = entry.second.get_tier();
+ output_tier_op =
+ tier_operation::greatest_lower_bound(entry.second.get_tier_op(),
+ output_tier_op);
return true;
}
@@ -2773,9 +2886,9 @@ private:
// Correctness here depends on the fact that the reason set is
// pre-generalized (the solver itself is already removed).
output_reasons.insert_or_narrow(entry.second.get_reasons());
- cwidget::util::ref_ptr<expression<bool> > tier_valid(entry.second.get_tier_valid());
- if(tier_valid.valid())
- output_valid_conditions.push_back(tier_valid);
+ cwidget::util::ref_ptr<expression<bool> > tier_op_valid(entry.second.get_tier_op_valid());
+ if(tier_op_valid.valid())
+ output_valid_conditions.push_back(tier_op_valid);
return true;
}
@@ -2788,18 +2901,21 @@ private:
*
* If the set is empty, this just inserts a conflict.
*/
- void check_solvers_tier(step &s, const typename step::dep_solvers &solvers)
+ void check_solvers_tier_op(step &s, const typename step::dep_solvers &solvers)
{
- tier t;
+ tier_operation t_op;
choice_set reasons;
std::vector<cwidget::util::ref_ptr<expression<bool> > > valid_conditions;
- solvers.for_each_solver(calculate_tier(t));
+ solvers.for_each_solver(calculate_tier(t_op));
// If no promotion would be emitted and the step tier wouldn't be
- // changed, don't do anything.
- if(get_current_search_tier() >= t &&
- s.step_tier >= t)
+ // changed, don't do anything. The "apply" test effectively
+ // 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() &&
+ tier_operation::least_upper_bound(s.effective_step_tier_op, t_op) == s.effective_step_tier_op)
return;
solvers.for_each_solver(build_promotion(reasons, valid_conditions));
@@ -2834,48 +2950,47 @@ private:
}
- if(get_current_search_tier() < t)
- {
- promotion p(reasons, t, valid_condition);
- LOG_TRACE(logger, "Emitting a new promotion " << p
- << " at step " << s.step_num);
-
- add_promotion(s.step_num, p);
- }
+ promotion p(reasons, t_op, valid_condition);
+ LOG_TRACE(logger, "Emitting a new promotion " << p
+ << " at step " << s.step_num);
- if(s.step_tier < t)
- set_step_tier(s.step_num, t);
+ add_promotion(s.step_num, p);
+ increase_effective_step_tier_op(s, p);
}
- /** \brief Increases the tier of a single step. */
- void increase_step_tier(step &s,
- const promotion &p)
+ /** \brief Increases the effective tier of a single step. */
+ void increase_effective_step_tier_op(step &s,
+ const promotion &p)
{
- const tier &p_tier(p.get_tier());
+ const tier_operation &p_tier_op(p.get_tier_op());
- if(s.step_tier < p_tier)
- set_step_tier(s.step_num, p_tier);
+ tier_operation new_effective_step_tier_op =
+ tier_operation::least_upper_bound(p_tier_op, s.effective_step_tier_op);
+
+ set_effective_step_tier_op(s.step_num, new_effective_step_tier_op);
}
// Increases the tier of each dependency in each dependency list
// this is applied to. Helper for increase_solver_tier.
- struct do_increase_solver_tier
+ struct do_increase_solver_tier_op
{
step &s;
- const tier &new_tier;
+ const tier_operation &new_tier_op;
const choice_set &new_choices;
const cwidget::util::ref_ptr<expression<bool> > &valid_condition;
generic_problem_resolver &resolver;
log4cxx::LoggerPtr logger;
public:
- do_increase_solver_tier(step &_s,
- const tier &_new_tier,
- const choice_set &_new_choices,
- const cwidget::util::ref_ptr<expression<bool> > &_valid_condition,
- generic_problem_resolver &_resolver,
- const log4cxx::LoggerPtr &_logger)
- : s(_s), new_tier(_new_tier), new_choices(_new_choices),
+ do_increase_solver_tier_op(step &_s,
+ const tier_operation &_new_tier_op,
+ const choice_set &_new_choices,
+ const cwidget::util::ref_ptr<expression<bool> > &_valid_condition,
+ generic_problem_resolver &_resolver,
+ const log4cxx::LoggerPtr &_logger)
+ : s(_s),
+ new_tier_op(_new_tier_op),
+ new_choices(_new_choices),
valid_condition(_valid_condition),
resolver(_resolver),
logger(_logger)
@@ -2914,14 +3029,17 @@ private:
const typename step::solver_information &old_inf =
*solver_found;
- // Don't do anything if the tier won't increase.
- // Empirically, the resolver was wasting lots of
- // time and memory increasing tiers when the solver
- // tiers hadn't actually changed.
- if(old_inf.get_tier() < new_tier)
+ // Don't do anything if the tier operation won't
+ // increase. Empirically, the resolver was wasting
+ // lots of time and memory increasing tiers when the
+ // solver tiers hadn't actually changed.
+ tier_operation updated_solver_tier_op =
+ tier_operation::least_upper_bound(old_inf.get_tier_op(),
+ new_tier_op);
+ if(old_inf.get_tier_op() != updated_solver_tier_op)
{
typename step::solver_information
- new_inf(new_tier,
+ new_inf(updated_solver_tier_op,
new_choices,
valid_condition,
old_inf.get_is_deferred_listener());
@@ -2930,10 +3048,10 @@ private:
typename step::flyweight_dep_solvers
memoized_new_solvers(new_solvers);
s.unresolved_deps.put(d, memoized_new_solvers);
- resolver.check_solvers_tier(s, new_solvers);
+ resolver.check_solvers_tier_op(s, new_solvers);
- LOG_TRACE(logger, "Increased the tier of "
- << solver_with_dep << " to " << new_tier
+ LOG_TRACE(logger, "Increased the tier operation of "
+ << solver_with_dep << " to " << updated_solver_tier_op
<< " in the solvers list of "
<< d << " in step " << s.step_num
<< " with the reason set " << new_choices
@@ -2952,20 +3070,20 @@ private:
/** \brief Increase the tier of a solver (for instance, because a
* new incipient promotion was detected).
*/
- void increase_solver_tier(step &s,
- const promotion &p,
- const choice &solver)
+ void increase_solver_tier_op(step &s,
+ const promotion &p,
+ const choice &solver)
{
LOG_TRACE(logger, "Applying the promotion " << p
<< " to the solver " << solver
<< " in the step " << s.step_num);
- const tier &new_tier(p.get_tier());
+ const tier_operation &new_tier_op(p.get_tier_op());
// There are really two cases here: either the tier was increased
// 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(new_tier >= tier_limits::conflict_tier ||
- new_tier >= tier_limits::already_generated_tier)
+ if(new_tier_op.get_structural_level() >= tier_limits::conflict_structural_level ||
+ new_tier_op.get_structural_level() >= tier_limits::already_generated_structural_level)
{
// \todo this throws away information about whether we're at
// the already-generated tier. This isn't that important,
@@ -2985,33 +3103,36 @@ private:
const cwidget::util::ref_ptr<expression<bool> > &
valid_condition(p.get_valid_condition());
- LOG_TRACE(logger, "Increasing the tier of " << solver
- << " to " << new_tier << " in all solver lists in step "
+ LOG_TRACE(logger, "Increasing the tier operation of " << solver
+ << " to " << new_tier_op << " in all solver lists in step "
<< s.step_num << " with the reason set " << new_choices);
- do_increase_solver_tier
- do_increase_solver_tier_f(s, new_tier, new_choices,
- valid_condition,
- *this,
- logger);
+ do_increase_solver_tier_op
+ do_increase_solver_tier_op_f(s,
+ new_tier_op,
+ new_choices,
+ valid_condition,
+ *this,
+ logger);
- s.deps_solved_by_choice.for_each_key_contained_in(solver,
- do_increase_solver_tier_f);
+ s.deps_solved_by_choice.for_each_key_contained_in(solver,
+ do_increase_solver_tier_op_f);
}
}
- /** \brief Increase the tier of each solver that it's applied to.
+ /** \brief Increase the tier operation of each solver that it's
+ * applied to.
*/
- class do_increase_solver_tier_everywhere
+ class do_increase_solver_tier_op_everywhere
{
generic_problem_resolver &r;
const choice &solver;
const promotion &p;
public:
- do_increase_solver_tier_everywhere(generic_problem_resolver &_r,
- const choice &_solver,
- const promotion &_p)
+ do_increase_solver_tier_op_everywhere(generic_problem_resolver &_r,
+ const choice &_solver,
+ const promotion &_p)
: r(_r), solver(_solver), p(_p)
{
}
@@ -3025,33 +3146,33 @@ private:
switch(tp)
{
case search_graph::choice_mapping_solver:
- r.increase_solver_tier(s, p, solver);
+ r.increase_solver_tier_op(s, p, solver);
break;
case search_graph::choice_mapping_action:
- r.increase_step_tier(s, p);
+ r.increase_effective_step_tier_op(s, p);
}
return true;
}
};
- /** \brief Increase the tier of a solver everywhere it appears with
- * the same dependency: that is, both in solver lists and in action
- * sets.
+ /** \brief Increase the tier operation of a solver everywhere it
+ * appears with the same dependency: that is, both in solver lists
+ * and in action sets.
*/
- void increase_solver_tier_everywhere_with_dep(const choice &solver,
- const promotion &p)
+ void increase_solver_tier_op_everywhere_with_dep(const choice &solver,
+ const promotion &p)
{
LOG_TRACE(logger, "Increasing the tier of " << solver
<< " according to the promotion " << p
<< " in all active steps.");
- do_increase_solver_tier_everywhere
- increase_solver_tier_everywhere_f(*this, solver, p);
+ do_increase_solver_tier_op_everywhere
+ increase_solver_tier_op_everywhere_f(*this, solver, p);
graph.for_each_step_related_to_choice_with_dep(solver,
solver.get_dep(),
- increase_solver_tier_everywhere_f);
+ increase_solver_tier_op_everywhere_f);
}
class do_find_promotions_for_solver
@@ -3144,7 +3265,7 @@ private:
s.unresolved_deps_by_num_solvers.insert(std::make_pair(num_solvers, d));
find_promotions_for_dep_solvers(s, d);
- check_solvers_tier(s, solvers);
+ check_solvers_tier_op(s, solvers);
}
/** \brief Find all the dependencies that are unresolved in step s
@@ -3235,7 +3356,7 @@ private:
for(typename boost::unordered_map<choice, promotion>::const_iterator it =
output.begin(); it != output.end(); ++it)
- increase_solver_tier(s, it->second, it->first);
+ increase_solver_tier_op(s, it->second, it->first);
}
/** \brief Update a step's score to compute its successor, given
@@ -3310,11 +3431,14 @@ private:
/** \brief Fill in a new step with a successor of the parent step
* generated by performing the given action.
+ *
+ * \param parent The parent step.
+ * \param output The new step that will be filled in.
+ * \param c_original The choice that was used to create this step.
*/
void generate_single_successor(const step &parent,
step &output,
- const choice &c_original,
- const tier &output_tier)
+ const choice &c_original)
{
// First, verify that there are no un-discharged promotions in the
// parent step. Normally this won't be true, since we check the
@@ -3344,6 +3468,14 @@ private:
choice c(c_original);
c.set_id(parent.actions.size());
+ // The intrinsic operation just includes the solver itself. The
+ // intrinsic *promotion*, on the other hand, includes information
+ // about whether it's deferred. The intrinsic promotion isn't
+ // taken into account right here; later, we'll recompute the
+ // effective tier operation from scratch and include the intrinsic
+ // promotion when we do.
+ tier_operation c_op = get_intrinsic_solver_op(c);
+
// Copy all the state information over so we can work in-place on
// the output set.
output.actions = parent.actions;
@@ -3360,7 +3492,9 @@ private:
output.action_score = parent.action_score;
output.score = parent.score;
output.reason = c;
- output.step_tier = output_tier;
+ output.base_step_tier = c_op.apply(parent.base_step_tier);
+ output.effective_step_tier_op = tier_operation();
+ output.effective_step_tier = output.effective_step_tier_op.apply(output.base_step_tier);
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;
@@ -3370,9 +3504,12 @@ private:
LOG_TRACE(logger, "Generating a successor to step " << parent.step_num
- << " for the action " << c << " with tier "
- << output_tier << " and outputting to step " << output.step_num);
+ << " for the action " << c
+ << " with intrinsic tier operation " << c_op
+ << " and outputting to step " << output.step_num);
+ // We need a dependency to correctly generate the deferral
+ // information.
if(c.get_type() == choice::install_version && !c.get_has_dep())
LOG_ERROR(logger, "No dependency attached to the choice " << c
<< " used to generate step " << output.step_num
@@ -3382,6 +3519,19 @@ private:
// will be used below (in steps 3, 4, 5, 6 and 7).
output.actions.insert_or_narrow(c);
+ // Rescan the solvers list to find the new tier operation. I
+ // could also handle this incrementally using the powers of
+ // immset. However, I think it's probably not worth it: doing
+ // that would make this case cheaper, but increasing a solver in
+ // an existing step would become pricier (and we do that a lot
+ // more often). On the other hand: if combining operations
+ // becomes more sophisticated, it might be necessary to always do
+ // it incrementally *anyway*.
+ //
+ // Of course, this must be performed after we update the action
+ // set (above).
+ recompute_effective_step_tier_op(output);
+
// Don't do this, because it isn't necessary and will cause
// trouble.
//
@@ -3418,11 +3568,12 @@ private:
// 5. Find newly unsatisfied dependencies. For each one that's
// not in the unresolved map, add it to the unresolved map with
- // its solvers paired with their intrinsic tiers. Structurally
- // forbidden solvers are not added to the solvers list; instead,
- // they are used to create the initial list of forcing reasons.
- // Also, insert the dependency into the by-num-solvers list and
- // insert it into the reverse index for each one of its solvers.
+ // its solvers paired with their intrinsic tier operations.
+ // Structurally forbidden solvers are not added to the solvers
+ // list; instead, they are used to create the initial list of
+ // forcing reasons. Also, insert the dependency into the
+ // by-num-solvers list and insert it into the reverse index for
+ // each one of its solvers.
//
// This also processes the incipient promotions that are completed
// by each solver of a dependency. \todo If the solvers were
@@ -3439,11 +3590,11 @@ private:
extend_score_to_new_step(output, c);
LOG_TRACE(logger, "Generated step " << output.step_num
- << " (" << output.actions.size() << " actions): " << output.actions << ";T" << output.step_tier
+ << " (" << output.actions.size() << " actions): " << output.actions << ";T" << output.effective_step_tier
<< "S" << output.score);
- if(output.step_tier >= tier_limits::defer_tier &&
- output.step_tier < tier_limits::already_generated_tier)
+ if(output.effective_step_tier >= tier_limits::defer_tier &&
+ output.effective_step_tier < tier_limits::already_generated_tier)
++num_deferred;
pending.insert(output.step_num);
@@ -3473,7 +3624,6 @@ private:
resolver.graph.get_last_step().is_last_child = false;
const choice &solver(solver_pair.first);
- const typename step::solver_information &inf(solver_pair.second);
step &parent = resolver.graph.get_step(parent_step_num);
step &output = resolver.graph.add_step();
@@ -3482,11 +3632,13 @@ private:
parent.first_child = output.step_num;
output.is_last_child = true;
+ // It would be nice to save a promotion lookup later by passing
+ // the solver tier along here. However, that runs into some
+ // tricky issues with separating the intrinsic and extrinsic
+ // operations on the solver.
resolver.generate_single_successor(parent,
output,
- solver,
- std::max<tier>(inf.get_tier(),
- parent.step_tier));
+ solver);
return true;
}
@@ -3586,7 +3738,7 @@ public:
closed(),
promotions(_universe, *this),
promotion_queue_tail(new promotion_queue_entry(0, 0)),
- version_tiers(new tier[_universe.get_version_count()])
+ version_tier_ops(new tier_operation[_universe.get_version_count()])
{
LOG_DEBUG(logger, "Creating new problem resolver: step_score = " << _step_score
<< ", broken_score = " << _broken_score
@@ -3596,9 +3748,6 @@ public:
<< ", future_horizon = " << _future_horizon
<< ", initial_state = " << _initial_state);
- for(unsigned int i = 0; i < _universe.get_version_count(); ++i)
- version_tiers[i] = tier_limits::minimum_tier;
-
// Used for sanity-checking below.
choice_set empty_choice_set;
choice_set_installation empty_step(empty_choice_set,
@@ -3636,7 +3785,7 @@ public:
~generic_problem_resolver()
{
- delete[] version_tiers;
+ delete[] version_tier_ops;
}
/** \brief Get the dependencies that were initially broken in this
@@ -3733,14 +3882,16 @@ public:
return initial_state;
}
- /** \brief Manually promote the given set of choices to the given tier.
+ /** \brief Apply the given operation to search nodes that include
+ * the given set of choices.
*
* If tier is defer_tier, the promotion will be lost when the user
* changes the set of rejected packages.
*/
- void add_promotion(const choice_set &choices, const tier &promotion_tier)
+ void add_promotion(const choice_set &choices,
+ const tier_operation &promotion_tier_op)
{
- add_promotion(promotion(choices, promotion_tier));
+ add_promotion(promotion(choices, promotion_tier_op));
}
/** Tells the resolver how highly to value a particular package
@@ -3763,29 +3914,31 @@ public:
weights.version_scores[ver.get_id()]+=score;
}
- /** \brief Set the tier of a version.
+ /** \brief Set the tier operation of a version.
*
- * Adding this version to a solution with a lower tier will
- * increase the solution's tier to the given value.
+ * Overrides any previous tier operation that was set on this
+ * version. Should not be called once dependency resolution is
+ * running, or you'll get inconsistent results.
*/
- void set_version_tier(const version &ver, const tier &t)
+ void set_version_tier_op(const version &ver, const tier_operation &t_op)
{
eassert(ver.get_id() < universe.get_version_count());
- version_tiers[ver.get_id()] = t;
+ version_tier_ops[ver.get_id()] = t_op;
}
- /** \brief Set the tier of a version to at least the given value.
+ /** \brief Combine the given tier operation with the operation of
+ * the given version.
*
- * If the tier is less than t, it will be increased to t; otherwise
- * it will be left unchanged.
+ * Should not be called once dependency resolution is running, or
+ * you'll get inconsistent results.
*/
- void set_version_min_tier(const version &ver, const tier &t)
+ void modify_version_tier_op(const version &ver,
+ const tier_operation &t_op)
{
eassert(ver.get_id() < universe.get_version_count());
- tier &version_tier = version_tiers[ver.get_id()];
+ tier_operation &version_tier_op = version_tier_ops[ver.get_id()];
- if(version_tier < t)
- version_tier = t;
+ version_tier_op = version_tier_op + t_op;
}
/** \return the score of the version ver. */
@@ -4027,7 +4180,7 @@ public:
counts.open = pending.size();
counts.closed = closed.size();
counts.deferred = get_num_deferred();
- counts.conflicts = promotions.tier_size_above(tier_limits::conflict_tier);
+ counts.conflicts = promotions.conflicts_size();
counts.promotions = promotions.size() - counts.conflicts;
counts.finished = finished;
counts.current_tier = get_current_search_tier();
@@ -4056,7 +4209,7 @@ public:
if(pending.empty())
return tier_limits::minimum_tier;
else
- return graph.get_step(*pending.begin()).step_tier;
+ return graph.get_step(*pending.begin()).effective_step_tier;
}
private:
@@ -4067,7 +4220,7 @@ private:
{
return
!pending.empty() &&
- graph.get_step(*pending.begin()).step_tier < tier_limits::defer_tier;
+ graph.get_step(*pending.begin()).effective_step_tier < tier_limits::defer_tier;
}
/** \brief Returns \b true if the pending future solutions queue
@@ -4077,7 +4230,7 @@ private:
{
return
!pending_future_solutions.empty() &&
- graph.get_step(*pending_future_solutions.begin()).step_tier < tier_limits::defer_tier;
+ graph.get_step(*pending_future_solutions.begin()).effective_step_tier < tier_limits::defer_tier;
}
// Counts how many action hits existed in a promotion, allowing up
@@ -4116,10 +4269,11 @@ private:
/** \brief Apply a single promotion to a single step. */
void apply_promotion(step &s, const promotion &p)
{
- if(!(s.step_tier < p.get_tier()))
+ if(tier_operation::least_upper_bound(s.effective_step_tier_op,
+ p.get_tier_op()) == s.effective_step_tier_op)
LOG_TRACE(logger, "Not applying " << p
- << " to step " << s.step_num << ": the step tier "
- << s.step_tier << " is not below the promotion tier.");
+ << " to step " << s.step_num << ": the step tier operation "
+ << s.effective_step_tier_op << " is above the promotion tier operation.");
else
{
LOG_TRACE(logger, "Testing the promotion " << p
@@ -4139,7 +4293,7 @@ private:
{
LOG_TRACE(logger, "Step " << s.step_num
<< " contains " << p << " as an active promotion.");
- set_step_tier(s.step_num, p.get_tier());
+ increase_effective_step_tier_op(s, p);
}
else if(action_hits + 1 < p_size)
LOG_TRACE(logger, "Step " << s.step_num
@@ -4157,7 +4311,7 @@ private:
<< " contains " << p
<< " as an incipient promotion for the choice "
<< *mismatch << ".");
- increase_solver_tier(s, p, *mismatch);
+ increase_solver_tier_op(s, p, *mismatch);
}
}
}
@@ -4233,7 +4387,7 @@ private:
const promotion &p(non_incipient_promotion.get_value());
LOG_TRACE(logger, "Found a new promotion in the action set of step "
<< step_num << ": " << p);
- increase_step_tier(s, p);
+ increase_effective_step_tier_op(s, p);
}
// Note that some promotions might be generated as a result of
@@ -4245,7 +4399,7 @@ private:
for(typename boost::unordered_map<choice, promotion>::const_iterator it =
incipient_promotions.begin();
it != incipient_promotions.end(); ++it)
- increase_solver_tier(s, it->second, it->first);
+ increase_solver_tier_op(s, it->second, it->first);
}
}
@@ -4263,10 +4417,10 @@ private:
step &s = graph.get_step(step_num);
LOG_INFO(logger, "Examining step " << step_num
- << " (" << s.actions.size() << " actions): " << s.actions << ";T" << s.step_tier
+ << " (" << s.actions.size() << " actions): " << s.actions << ";T" << s.effective_step_tier
<< "S" << s.score);
- if(s.step_tier >= tier_limits::defer_tier)
+ if(s.effective_step_tier >= tier_limits::defer_tier)
{
LOG_ERROR(logger, "Internal error: the tier of step "
<< s.step_num
@@ -4289,7 +4443,7 @@ private:
}
// The step might have been promoted to the defer tier by
// check_for_new_promotions.
- else if(s.step_tier >= tier_limits::defer_tier)
+ else if(s.effective_step_tier >= tier_limits::defer_tier)
{
LOG_DEBUG(logger, "Skipping newly deferred step " << s.step_num);
// Stick it back into the open queue.
@@ -4306,7 +4460,7 @@ private:
if(s.unresolved_deps.empty())
{
LOG_INFO(logger, " --- Found solution at step " << s.step_num
- << ": " << s.actions << ";T" << s.step_tier
+ << ": " << s.actions << ";T" << s.effective_step_tier
<< "S" << s.score);
// Remember this solution, so we don't try to return it
@@ -4316,7 +4470,7 @@ private:
it != s.actions.end(); ++it)
generalized_actions.insert_or_narrow(it->generalize());
promotion already_generated_promotion(generalized_actions,
- tier_limits::already_generated_tier);
+ tier_limits::increase_to_already_generated_op);
add_promotion(step_num, already_generated_promotion);
s.is_blessed_solution = true;
@@ -4330,7 +4484,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).step_tier < tier_limits::defer_tier)
+ graph.get_step(s.first_child).effective_step_tier < tier_limits::defer_tier)
{
LOG_TRACE(logger, "Following forced dependency resolution from step "
<< step_num << " to step " << s.first_child);
@@ -4416,7 +4570,9 @@ public:
if(initial_broken.empty())
root.score += weights.full_solution_score;
- root.step_tier = tier_limits::minimum_tier;
+ root.base_step_tier = tier_limits::minimum_tier;
+ root.effective_step_tier_op = tier_operation();
+ root.effective_step_tier = tier_limits::minimum_tier;
root.promotion_queue_location = promotion_queue_tail;
for(typename imm::set<dep>::const_iterator it = initial_broken.begin();
@@ -4424,7 +4580,7 @@ public:
add_unresolved_dep(root, *it);
LOG_TRACE(logger, "Inserting the root at step " << root.step_num
- << " with tier " << root.step_tier);
+ << " with tier " << root.effective_step_tier);
pending.insert(root.step_num);
}
@@ -4486,14 +4642,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.step_tier < tier_limits::defer_tier)
+ if(best_future_solution_step.effective_step_tier < tier_limits::defer_tier)
{
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.step_tier);
+ best_future_solution_step.effective_step_tier);
LOG_INFO(logger, " *** Converged after " << odometer << " steps.");
diff --git a/src/generic/problemresolver/promotion_set.h b/src/generic/problemresolver/promotion_set.h
index 3518c7ae..d1df17c1 100644
--- a/src/generic/problemresolver/promotion_set.h
+++ b/src/generic/problemresolver/promotion_set.h
@@ -40,12 +40,15 @@
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>
+#include <boost/variant.hpp>
#include "choice.h"
#include "choice_indexed_map.h"
#include "choice_set.h"
#include "incremental_expression.h"
#include "tier.h"
+#include "tier_limits.h"
+#include "tier_operation.h"
/** \brief Represents a tier promotion: the knowledge that
* a set of choices forces a solution to a higher tier.
@@ -59,7 +62,7 @@ public:
private:
choice_set choices;
- tier promotion_tier;
+ tier_operation promotion_tier_operation;
// An expression that is "true" when this promotion is valid and
// "false" otherwise; it is NULL if the promotion is universally
// valid. Invalid promotions are culled from the promotion set.
@@ -71,36 +74,96 @@ private:
public:
generic_promotion()
- : choices(), promotion_tier(), valid_condition()
+ : choices(), promotion_tier_operation(), valid_condition()
{
}
/** \brief Create a new promotion. */
- generic_promotion(const choice_set &_choices, const tier &_promotion_tier)
- : choices(_choices), promotion_tier(_promotion_tier), valid_condition()
+ generic_promotion(const choice_set &_choices, const tier_operation &_promotion_tier_operation)
+ : choices(_choices), promotion_tier_operation(_promotion_tier_operation), valid_condition()
{
}
/** \brief Create a new promotion with a validity condition. */
generic_promotion(const choice_set &_choices,
- const tier &_promotion_tier,
+ const tier_operation &_promotion_tier_operation,
const cwidget::util::ref_ptr<expression<bool> > &_valid_condition)
: choices(_choices),
- promotion_tier(_promotion_tier),
+ promotion_tier_operation(_promotion_tier_operation),
valid_condition(_valid_condition)
{
}
const choice_set &get_choices() const { return choices; }
- const tier &get_tier() const { return promotion_tier; }
+ const tier_operation &get_tier_op() const { return promotion_tier_operation; }
const cwidget::util::ref_ptr<expression<bool> > &get_valid_condition() const { return valid_condition; }
+ /** \brief Return a promotion representing both of the
+ * input promotions.
+ *
+ * The output promotion's tier is the least upper bound of the
+ * input promotions' tiers. If only one promotion was required to
+ * achieve this upper bound, then a promotion that is sufficient
+ * will be selected and returned directly. Otherwise, a new
+ * promotion will be created -- most likely expanding the trigger
+ * sets and validity conditions of the input promotions in the
+ * process.
+ */
+ static generic_promotion least_upper_bound(const generic_promotion &p1,
+ const generic_promotion &p2)
+ {
+ const tier_operation &p1_op(p1.get_tier_op());
+ const tier_operation &p2_op(p2.get_tier_op());
+
+ tier_operation new_op =
+ tier_operation::least_upper_bound(p1_op, p2_op);
+
+ // If the least upper bound has the same content as one of the two
+ // promotions, return that promotion directly.
+ if(new_op == p1_op)
+ return p1;
+ else if(new_op == p2_op)
+ return p2;
+
+ // Otherwise we'll have to construct a new combined promotion,
+ // being careful with regard to validity conditions and triggers.
+
+ const choice_set &p1_choices(p1.get_choices());
+ const choice_set &p2_choices(p2.get_choices());
+
+ const cwidget::util::ref_ptr<expression<bool> > &p1_valid(p1.get_valid_condition());
+ const cwidget::util::ref_ptr<expression<bool> > &p2_valid(p2.get_valid_condition());
+
+ choice_set new_choices;
+
+ // Minor optimization: I "know" that the current implementation of
+ // insert_or_narrow means that it's potentially more efficient to
+ // start with the larger set and incorporate the smaller one.
+ if(p1_choices.size() > p2_choices.size())
+ {
+ new_choices = p1_choices;
+ new_choices.insert_or_narrow(p2_choices);
+ }
+ else
+ {
+ new_choices = p2_choices;
+ new_choices.insert_or_narrow(p2_choices);
+ }
+
+ // Note that this will compute a somewhat inefficient validity
+ // condition when applied across several expressions.
+ cwidget::util::ref_ptr<expression<bool> > new_valid =
+ and_e::create(p1_valid, p2_valid);
+
+ return generic_promotion(new_choices, new_op, new_valid);
+ }
+
int compare(const generic_promotion &other) const
{
using aptitude::util::compare3;
const int promotion_cmp =
- compare3(promotion_tier, other.promotion_tier);
+ compare3(promotion_tier_operation, other.promotion_tier_operation);
if(promotion_cmp != 0)
return promotion_cmp;
@@ -115,7 +178,7 @@ public:
bool operator==(const generic_promotion &other) const
{
- if(promotion_tier != other.promotion_tier)
+ if(promotion_tier_operation != other.promotion_tier_operation)
return false;
if(!(choices == other.choices))
@@ -126,7 +189,7 @@ public:
bool operator!=(const generic_promotion &other) const
{
- if(promotion_tier != other.promotion_tier)
+ if(promotion_tier_operation != other.promotion_tier_operation)
return true;
if(!(choices == other.choices))
@@ -156,7 +219,7 @@ namespace aptitude
template<typename PackageUniverse>
std::ostream &operator<<(std::ostream &out, const generic_promotion<PackageUniverse> &p)
{
- out << "(T" << p.get_tier() << ": " << p.get_choices();
+ out << "(T" << p.get_tier_op() << ": " << p.get_choices();
if(p.get_valid_condition().valid())
// Output p.get_valid_condition() if it isn't null.
@@ -177,7 +240,7 @@ class promotion_set_callbacks
};
/** \brief Represents a set of "promotions": mappings from sets of
- * choices to tiers of the search space.
+ * choices to tier operations implied by those choices.
*
* Wraps up the various customizations of dense_setset for this case.
*
@@ -189,23 +252,17 @@ class promotion_set_callbacks
* tier it matches (this requires indexing on version OR
* dependency, depending on what type of choice we have).
*
- * 2. We also want to be able to prune the structure of all entries
- * below a particular tier, or to yank out the contents of a
- * range of tiers entirely (used when deferrals are removed, or
- * when we advance to a new tier and want to get rid of cruft
- * from the previous tier).
- *
- * 3. When a new tier promotion is inserted, it should override any
+ * 2. When a new tier promotion is inserted, it should override any
* lower promotions that it is a subset of or equal to, but not
* higher ones. Conversely, if a new tier promotion contains an
* existing promotion that has a higher tier, it should not be
* inserted.
*
- * 4. We need to be able to learn which promotions would match a
+ * 3. We need to be able to learn which promotions would match a
* step with a single extra choice, and what that choice is.
* This is used to update the solver status of a step.
-
- * 5. We need to be able to learn which promotions containing a
+ *
+ * 4. We need to be able to learn which promotions containing a
* particular choice would match a step with a single extra
* choice, and one choice that should be contained in the result.
* This is used to update the solver status when generating a
@@ -220,6 +277,10 @@ class promotion_set_callbacks
* the structure of choices (e.g., it indexes choices to break soft
* dependencies differently from choices to install versions).
*
+ * Iterators on the promotion set are stable (erasing an iterator
+ * will of course invalidate it, but other iterators will still be
+ * valid).
+ *
* \sa generic_choice, generic_choice_set
*/
template<typename PackageUniverse>
@@ -281,8 +342,9 @@ private:
}
};
- typedef typename std::list<entry>::const_iterator entry_const_ref;
- typedef typename std::list<entry>::iterator entry_ref;
+ typedef std::list<entry> entries_holder;
+ typedef typename entries_holder::const_iterator entry_const_ref;
+ typedef typename entries_holder::iterator entry_ref;
/** \brief An expression that ejects a promotion from its parent set
* when that promotion becomes invalid.
@@ -338,16 +400,12 @@ private:
}
};
- /** \brief Stores the promotions that exist, organized by tier.
- *
- * This map is maintained so that it has no empty entries.
+ /** \brief Stores the promotions that exist. */
+ entries_holder entries;
- * Lists are used so that we can store stable references to
- * entries.
- */
- std::map<tier, std::list<entry> > entries;
-
- unsigned int num_promotions;
+ // The number of promotions that would produce a conflict. Used
+ // only for the sake of display.
+ unsigned int num_conflicts;
/** \brief An entry in the index related to install_version entries.
*
@@ -489,86 +547,28 @@ private:
{
promotion p(victim->p);
- // First, find the promotion's tier.
- const typename std::map<tier, std::list<entry> >::iterator
- found = entries.find(p.get_tier());
- if(found == entries.end())
- LOG_ERROR(logger, "Can't eject " << p << ": its tier cannot be located.");
- else
- {
- erase(iterator(found, entries.end(), victim));
- callbacks.promotion_retracted(p);
- }
+ erase(iterator(victim));
+ callbacks.promotion_retracted(p);
}
public:
typedef unsigned int size_type;
- size_type size() const { return num_promotions; }
- size_type tier_size(const tier &selected_tier) const
- {
- typename std::map<tier, std::list<entry> >::const_iterator found =
- entries.find(selected_tier);
- if(found == entries.end())
- return 0;
- else
- return found->second.size();
- }
-
- size_type tier_size_above(const tier &selected_tier) const
- {
- size_type rval = 0;
-
- typename std::map<tier, std::list<entry> >::const_iterator first =
- entries.lower_bound(selected_tier);
- for(typename std::map<tier, std::list<entry> >::const_iterator it = first;
- it != entries.end(); ++it)
- rval += it->second.size();
-
- return rval;
- }
+ size_type size() const { return entries.size(); }
+ size_type conflicts_size() const { return num_conflicts; }
private:
- template<typename tier_iter, typename entry_iter>
+ // The iterators on this set hide the entry objects and other
+ // metadata, returning only the promotions.
+ template<typename entry_iter>
class iterator_base
{
- // This is the only place where it's awkward to have a
- // map-of-lists be the canonical location where all the entries in
- // this object are stored.
- tier_iter entries_it;
- // The end iterator for the map -- necessary so that we know
- // whether it's safe to start walking down the current list.
- tier_iter entries_end;
-
- // The current entry in the current list.
- entry_iter entry_list_it;
+ entry_iter entry_it;
friend class generic_promotion_set;
// This overload is used for non-end iterators.
- iterator_base(tier_iter _entries_it,
- tier_iter _entries_end,
- entry_iter _entry_list_it)
- : entries_it(_entries_it),
- entries_end(_entries_end),
- entry_list_it(_entry_list_it)
- {
- // Should never happen; this is pure defensiveness.
- while(entries_it != entries_end &&
- entry_list_it == entries_it->second.end())
- {
- LOG_ERROR(aptitude::Loggers::getAptitudeResolverSearchTiers(), "Empty tier in promotion set!");
-
- ++entries_it;
- if(entries_it != entries_end)
- entry_list_it = entries_it->second.begin();
- }
- }
-
- // This overload is used only to create an end iterator.
- iterator_base(tier_iter _entries_it,
- tier_iter _entries_end)
- : entries_it(_entries_it),
- entries_end(_entries_end)
+ iterator_base(entry_iter _entry_it)
+ : entry_it(_entry_it)
{
}
@@ -579,99 +579,56 @@ private:
const promotion &operator*() const
{
- eassert(entries_it != entries_end);
-
- return entry_list_it->p;
+ return entry_it->p;
}
const promotion *operator->() const
{
- eassert(entries_it != entries_end);
-
- return &entry_list_it->p;
+ return &entry_it->p;
}
iterator_base &operator++()
{
- eassert(entries_it != entries_end);
-
- ++entry_list_it;
- bool first = true;
- while(entries_it != entries_end &&
- entry_list_it == entries_it->second.end())
- {
- if(first)
- first = false;
- else
- LOG_ERROR(aptitude::Loggers::getAptitudeResolverSearchTiers(), "Empty tier in promotion set!");
-
- ++entries_it;
- if(entries_it != entries_end)
- entry_list_it = entries_it->second.begin();
- }
+ ++entry_it;
return *this;
}
- template<typename other_tier_iter, typename other_entry_iter>
- bool operator==(const iterator_base<other_tier_iter, other_entry_iter> &other) const
+ template<typename other_entry_iter>
+ bool operator==(const iterator_base<other_entry_iter> &other) const
{
- eassert(entries_end == other.entries_end);
-
- if(entries_it != other.entries_it)
- return false;
- else if(entries_it == entries_end)
- return true; // Don't compare the list iterators if they're
- // invalid.
- else
- return entry_list_it == other.entry_list_it;
+ return entry_it == other.entry_it;
}
- template<typename other_tier_iter, typename other_entry_iter>
- bool operator!=(const iterator_base<other_tier_iter, other_entry_iter> &other) const
+ template<typename other_entry_iter>
+ bool operator!=(const iterator_base<other_entry_iter> &other) const
{
- eassert(entries_end == other.entries_end);
-
- if(entries_it != other.entries_it)
- return true;
- else if(entries_it == entries_end)
- return false; // Don't compare the list iterators if they're
- // invalid.
- else
- return entry_list_it == other.entry_list_it;
+ return entry_it != other.entry_it;
}
};
public:
- typedef iterator_base<typename std::map<tier, std::list<entry> >::const_iterator,
- typename std::list<entry>::const_iterator> const_iterator;
+ typedef iterator_base<typename entries_holder::const_iterator> const_iterator;
- typedef iterator_base<typename std::map<tier, std::list<entry> >::iterator,
- typename std::list<entry>::iterator> iterator;
+ typedef iterator_base<typename entries_holder::iterator> iterator;
const_iterator begin() const
{
- if(entries.empty())
- return end();
- else
- return const_iterator(entries.begin(), entries.end(), entries.begin()->second.begin());
+ return const_iterator(entries.begin());
}
iterator begin()
{
- if(entries.empty())
- return end();
- else
- return const_iterator(entries.begin(), entries.end(), entries.begin()->second.begin());
+ return iterator(entries.begin());
}
const_iterator end() const
{
- return const_iterator(entries.end(), entries.end());
+ return const_iterator(entries.end());
}
iterator end()
{
- return iterator(entries.end(), entries.end());
+ return iterator(entries.end());
}
void erase(const iterator &victim)
@@ -681,32 +638,16 @@ public:
LOG_ERROR(logger, "Can't erase an end iterator.");
return;
}
-
- const promotion &p(victim->p);
-
- // First, find the promotion's tier.
- const typename std::map<tier, std::list<entry> >::iterator
- found = victim.entries_it;
- if(found == entries.end())
- LOG_ERROR(logger, "Can't eject " << p << ": its tier cannot be located.");
else
{
- std::list<entry> &tier_entries(found->second);
+ const promotion &p(*victim);
LOG_TRACE(logger, "Ejecting promotion: " << p);
- // Remove the promotion from the reverse indices.
p.get_choices().for_each(drop_choice(install_version_index,
break_soft_dep_index,
- victim));
- // Drop it from the tier.
- tier_entries.erase(victim);
+ victim.entry_it));
- if(tier_entries.empty())
- {
- LOG_TRACE(logger, "The tier " << found->first
- << " is now empty, removing it.");
- entries.erase(found);
- }
+ entries.erase(victim.entry_it);
}
}
@@ -923,26 +864,37 @@ private:
// two distinct elements (no two choices in a search node can match
// each other).
//
- // This returns an arbitrary element that has the highest possible
- // search tier. We don't return all elements because we don't need
- // to (this represents testing whether a set matches an existing
+ // This computes the upper bound of all the elements that were
+ // matched. We don't return all elements because we don't need to
+ // (this represents testing whether a set matches an existing
// promotion). NB: the only reason for returning a promotion
// pointer rather than a boolean is so that we can provide
// diagnostic logging.
- struct find_entry_subset_op
+ class find_entry_subset_op
{
- // The return value. Needs to be mutable because the traversal
- // routine uses a const reference. (I think maybe it shouldn't
- // use a const reference: that should be fixed)
- mutable entry_ref return_value_ref;
- // Set to true if the return value is meaningful. Mutable for the
- // same reason as return_value_ref.
- mutable bool was_set;
+ // A collection of conditions under which the returned promotion
+ // is true. Each intersected promotion's validity condition is
+ // thrown in here.
+ mutable std::vector<cwidget::util::ref_ptr<expression<bool> > > rval_valid_conditions;
+ // The tier operation to return.
+ mutable tier_operation rval_op;
+
log4cxx::LoggerPtr logger;
+ public:
find_entry_subset_op(const log4cxx::LoggerPtr &_logger)
- : was_set(false), logger(_logger)
+ : logger(_logger)
+ {
+ }
+
+ const std::vector<cwidget::util::ref_ptr<expression<bool> > > &get_rval_valid_conditions() const
{
+ return rval_valid_conditions;
+ }
+
+ const tier_operation &get_rval_op() const
+ {
+ return rval_op;
}
bool operator()(entry_ref r) const
@@ -951,26 +903,23 @@ private:
{
if(r->hit_count == r->p.get_choices().size())
{
- if(!was_set ||
- return_value_ref->p.get_tier() < r->p.get_tier())
+ tier_operation new_op =
+ tier_operation::least_upper_bound(r->p.get_tier_op(), rval_op);
+
+ if(new_op != rval_op)
{
- if(was_set)
- LOG_DEBUG(logger, "find_entry_subset_op: resetting the hit count for "
- << r->p << " to 0 and returning it (highest tier: "
- << return_value_ref->p.get_tier() << " -> " << r->p.get_tier());
- else
- LOG_DEBUG(logger, "find_entry_subset_op: resetting the hit count for "
- << r->p << " to 0 and returning it (new highest tier: "
- << r->p.get_tier());
+ LOG_DEBUG(logger, "find_entry_subset_op: resetting the hit count for "
+ << r->p << " to 0 and incorporating it into the result (return value: "
+ << rval_op << " -> " << new_op);
- return_value_ref = r;
- was_set = true;
+ rval_op = new_op;
+ rval_valid_conditions.push_back(r->p.get_valid_condition());
}
else
LOG_TRACE(logger, "find_entry_subset_op: resetting the hit count for "
- << r->p << " to 0, but not returning it, because its tier "
- << r->p.get_tier() << " is lower than the current highest tier "
- << return_value_ref->p.get_tier());
+ << r->p << " to 0, but not incorporating it into the result, because its tier operation "
+ << r->p.get_tier_op() << " is lower than the current highest tier operation "
+ << rval_op);
}
else
LOG_TRACE(logger, "find_entry_subset_op: " << r->p
@@ -989,27 +938,29 @@ private:
}
};
- /** \brief Retrieve all the supersets of the input set: entries that
- * contain elements which are all contained within entries of the
- * input set, and whose tiers are not higher than the input set's
- * tier.
+ /** \brief Retrieve all the supersets of the input set: entries
+ * whose trigger sets are supersets of the input promotion, and
+ * whose tier operations are less than or equal to the input set's
+ * tier operation (bearing mind that tier operations are only
+ * partially ordered).
*
* As a side effect, resets all hit counts to 0.
*
* This is used to purge redundant entries when a new entry is
* inserted.
*/
- struct find_entry_supersets_op
+ class find_entry_supersets_op
{
// Where to store the output entry references.
std::vector<entry_ref> &output_entries;
// How many hits to require from each entry we process.
unsigned int required_hits;
- // The maximum tier to return; entries with a higher tier will be
- // ignored.
- tier maximum_tier;
+ // Tier operations smaller than or equal to this limit are not
+ // returned:
+ tier_operation maximum_tier_operation;
log4cxx::LoggerPtr logger;
+ public:
/** \brief Create a find-supersets operation.
*
* \param _output_entries The location in which to place the
@@ -1018,18 +969,18 @@ private:
* that we are searching for supersets
* of; only entries with this many hits
* are returned.
- * \param _maximum_tier The maximum tier to examine; only entries
- * at this tier or lower are returned.
+ * \param _maximum_tier_operation The maximum tier to examine; only entries
+ * with this tier operation or lower are returned.
* \param _logger The logger to use to write messages
* about this process.
*/
find_entry_supersets_op(std::vector<entry_ref> &_output_entries,
unsigned int _required_hits,
- const tier &_maximum_tier,
+ const tier_operation &_maximum_tier_operation,
const log4cxx::LoggerPtr &_logger)
: output_entries(_output_entries),
required_hits(_required_hits),
- maximum_tier(_maximum_tier),
+ maximum_tier_operation(_maximum_tier_operation),
logger(_logger)
{
}
@@ -1038,12 +989,13 @@ private:
{
if(r->active)
{
- if(maximum_tier < r->p.get_tier())
+ if(tier_operation::greatest_lower_bound(maximum_tier_operation,
+ r->p.get_tier_op()) != r->p.get_tier_op())
{
LOG_DEBUG(logger, "find_entry_supersets_op: resetting the hit count for "
- << r->p << " to 0, but not returning it, because its tier "
- << r->p.get_tier() << " is above the maximum tier "
- << maximum_tier);
+ << r->p << " to 0, but not returning it, because its tier operation "
+ << r->p.get_tier_op() << " is not below the maximum tier operation "
+ << maximum_tier_operation);
}
else if(r->hit_count == required_hits)
{
@@ -1070,14 +1022,14 @@ private:
};
public:
- /** \brief Find a highest tier promotion that is a subset of the
- * given set of choices.
+ /** \brief Compute the upper bound of all the promotions contained
+ * in the given set of choices.
*
* Implements requirement (1).
*/
- const_iterator find_highest_promotion_for(const choice_set &choices) const
+ tier_operation find_highest_promotion_tier_op(const choice_set &choices) const
{
- LOG_TRACE(logger, "Entering find_highest_promotion_for(" << choices << ")");
+ LOG_TRACE(logger, "Entering find_highest_promotion_tier_op(" << choices << ")");
traverse_intersections<increment_entry_count_op>
increment_f(*this, true, increment_entry_count_op(logger));
@@ -1090,27 +1042,7 @@ public:
// need to reset all the counters to 0 for the next run.
choices.for_each(find_result_f);
- if(!find_result.was_set)
- return end();
- else
- {
- const entry_ref result_entry(find_result.return_value_ref);
- const tier &result_tier = result_entry->p.get_tier();
- typename std::map<tier, std::list<entry> >::const_iterator tier_found =
- entries.find(result_tier);
- if(tier_found == entries.end())
- {
- LOG_ERROR(logger, "Unable to find tier " << result_tier << " even though we just found an entry in it!");
- return end();
- }
- else
- {
- LOG_TRACE(logger, "find_highest_promotion_for: For the set " << choices << ", returning an iterator to " << result_entry->p);
- // Assume that result_entry is in this list, since if it
- // isn't, something is very wrong.
- return const_iterator(tier_found, entries.end(), result_entry);
- }
- }
+ return find_result.get_rval_op();
}
/** \brief A functor that, when applied to a Boolean value,
@@ -1139,8 +1071,9 @@ public:
* This is initialized with a promotion, the output domain, and an
* output location, then invoked with various choices. For each of
* the choices that is contained in the output domain, the
- * corresponding cell in the output map is updated if the new
- * promotion is higher than the old one.
+ * corresponding cell in the output map is updated to the upper
+ * bound of the promotion it stores and the update object's
+ * promotion.
*
* Normally the choices this is invoked on represent the choices in
* the promotion.
@@ -1172,8 +1105,9 @@ public:
if(found.first == found.second)
output.insert(found.first, std::make_pair(c, p));
- else if(found.first->second.get_tier() < p.get_tier())
- found.first->second = p;
+ else
+ found.first->second =
+ promotion::least_upper_bound(found.first->second, p);
}
return true;
@@ -1220,20 +1154,11 @@ public:
}
else if(r->hit_count == r->p.get_choices().size())
{
- bool hit = true;
if(output_non_incipient.get_has_value())
- {
- if(output_non_incipient.get_value().get_tier() >= r->p.get_tier())
- hit = false;
- }
-
- if(hit)
- {
- LOG_DEBUG(logger, "find_incipient_entry_subset_op: updating the non-incipient output value to " << r->p << " and resetting its hit count to 0.");
- output_non_incipient = r->p;
- }
-
- output_non_incipient = maybe<promotion>(r->p);
+ output_non_incipient =
+ promotion::least_upper_bound(output_non_incipient.get_value(), r->p);
+ else
+ output_non_incipient = r->p;
}
else
LOG_DEBUG(logger, "find_incipient_entry_subset_op: " << r->p << " is not an incipient promotion; resetting its hit count to 0 and not returning it.");
@@ -1251,8 +1176,9 @@ public:
/** \brief A function object that, for each choice it is applied to,
* adds an entry to the given output set for the choice if there is
* a single-element promotion containing that choice. If an entry
- * already exists, it is updated only if the new promotion is to a
- * higher tier.
+ * already exists, it is updated only if the new promotion is not
+ * less than or equal to the current one (i.e., it is larger or
+ * unrelated).
*/
template<typename T>
class find_unary_promotions
@@ -1294,8 +1220,9 @@ public:
if(found.first == found.second)
output.insert(found.first, std::make_pair(p_c, p));
- else if(found.first->second.get_tier() < p.get_tier())
- found.first->second = p;
+ else
+ found.first->second =
+ promotion::least_upper_bound(p, found.first->second);
}
}
}
@@ -1340,7 +1267,7 @@ public:
boost::unordered_map<choice, promotion> &output_incipient,
maybe<promotion> &output_non_incipient) const
{
- LOG_TRACE(logger, "Entering find_highest_incipient_promotion_for(" << choices << ", " << output_domain << ")");
+ LOG_TRACE(logger, "Entering find_highest_incipient_promotions(" << choices << ", " << output_domain << ")");
traverse_intersections<increment_entry_count_op>
increment_f(*this, true, increment_entry_count_op(logger));
@@ -1528,9 +1455,11 @@ public:
* given set of choices *and* that contains the given choice.
*
* Implements requirement (1).
+ *
+ * Returns a default-initialized promotion if nothing was found.
*/
- const_iterator find_highest_promotion_containing(const choice_set &choices,
- const choice &c) const
+ promotion find_highest_promotion_containing(const choice_set &choices,
+ const choice &c) const
{
LOG_TRACE(logger, "Entering find_highest_promotion_containing(" << choices << ", " << c << ")");
@@ -1538,8 +1467,8 @@ public:
if(index_entries == NULL || index_entries->empty())
{
- LOG_TRACE(logger, "find_highest_promotion_containing: There are no index entries for " << c << "; returning an end iterator.");
- return end();
+ LOG_TRACE(logger, "find_highest_promotion_containing: There are no index entries for " << c << "; returning a minimal promotion.");
+ return promotion();
}
else
{
@@ -1558,8 +1487,7 @@ public:
LOG_TRACE(logger, "find_highest_promotion_containing: Matching indexed entries for " << c << " to the local index.");
- bool found_anything = false;
- entry_ref highest_entry;
+ promotion rval;
for(typename std::vector<entry_ref>::const_iterator it = index_entries->begin();
it != index_entries->end(); ++it)
{
@@ -1576,47 +1504,18 @@ public:
p.get_choices().for_each(all_choices_found_f);
if(contains_match)
{
- if(!found_anything)
+ promotion upper_bound = promotion::least_upper_bound(rval, p);
+ if(upper_bound.get_tier_op() != rval.get_tier_op())
{
- LOG_TRACE(logger, "find_highest_promotion_containing: found the first match: " << p);
- found_anything = true;
- highest_entry = *it;
- }
- else if(highest_entry->p.get_tier() >= p.get_tier())
- LOG_TRACE(logger, "find_highest_promotion_containing: found a match " << p
- << ", but its tier is lower than the existing match ("
- << p.get_tier() << " vs " << highest_entry->p.get_tier());
- else
- {
- LOG_TRACE(logger, "find_highest_promotion_containing: found a new highest match: " << p
- << " (previous tier was " << highest_entry->p.get_tier());
- highest_entry = *it;
+ LOG_TRACE(logger, "find_highest_promotion_containing: found a new promotion: " << p
+ << " (previous promotion was " << rval
+ << ", new is " << upper_bound << ")");
+ rval = upper_bound;
}
}
}
- if(!found_anything)
- {
- LOG_TRACE(logger, "find_highest_promotion_containing: no matches found; returning an end iterator.");
- return end();
- }
- else
- {
- const tier &highest_entry_tier = highest_entry->p.get_tier();
- typename std::map<tier, std::list<entry> >::const_iterator tier_found =
- entries.find(highest_entry_tier);
-
- if(tier_found == entries.end())
- {
- LOG_ERROR(logger, "Unable to find tier " << highest_entry_tier << " even though we just found an entry in it!");
- return end();
- }
- else
- {
- LOG_TRACE(logger, "find_highest_promotion_containing: returning a reference to " << highest_entry->p);
- return const_iterator(tier_found, entries.end(), highest_entry);
- }
- }
+ return rval;
}
}
@@ -1688,8 +1587,6 @@ public:
LOG_TRACE(logger, "find_highest_incipient_promotion_containing: Matching indexed entries for " << c << " to the local index.");
- bool found_anything = false;
- entry_ref highest_entry;
for(typename std::vector<entry_ref>::const_iterator it = index_entries->begin();
it != index_entries->end(); ++it)
{
@@ -1713,7 +1610,6 @@ public:
update_incipient_output<T> updater(p, output_domain, output);
LOG_TRACE(logger, "find_highest_incipient_promotion_containing: found a match: " << p);
p.get_choices().for_each(updater);
- found_anything = true;
}
}
}
@@ -1743,7 +1639,7 @@ private:
find_results_f(*this, false,
find_entry_supersets_op(output,
p.get_choices().size(),
- p.get_tier(),
+ p.get_tier_op(),
logger));
const choice_set &choices(p.get_choices());
@@ -1987,75 +1883,6 @@ private:
}
}
-public:
- /** \brief Remove all the promotions whose tier is greater than or
- * equal to begin_tier, and strictly less than end_tier.
- *
- * Implements requirement (2).
- */
- void remove_between_tiers(const tier &begin_tier, const tier &end_tier)
- {
- LOG_DEBUG(logger, "Removing all promotions between tiers " << begin_tier << " and " << end_tier);
-
- typename std::map<tier, std::list<entry> >::iterator start =
- entries.lower_bound(begin_tier);
-
- typename std::map<tier, std::list<entry> >::iterator stop =
- entries.lower_bound(end_tier);
-
- // Collect the versions and soft dependencies related to each
- // choice in the selected tiers.
- boost::unordered_set<version> installed_versions;
- boost::unordered_set<dep> broken_soft_deps;
-
- int num_promotions_erased = 0;
- for(typename std::map<tier, std::list<entry> >::iterator it = start;
- it != stop; ++it)
- {
- collect_indexers(it->second,
- installed_versions,
- broken_soft_deps,
- logger);
-
- num_promotions_erased += it->second.size();
- }
-
- // Now zap all the index entries in these tiers.
- drop_install_version_index_entries(installed_versions,
- entry_ref_between_tiers_pred(begin_tier, end_tier));
- drop_broken_soft_dep_index_entries(broken_soft_deps,
- entry_ref_between_tiers_pred(begin_tier, end_tier));
-
- // Delete the tiers.
- entries.erase(start, stop);
- num_promotions -= num_promotions_erased;
-
- LOG_TRACE(logger, "Removed tiers " << begin_tier
- << " through " << end_tier
- << ", dropping " << num_promotions_erased << " promotions.");
- }
-
- /** \brief Remove all the promotions below the given tier.
- *
- * Implements requirement (2).
- */
- void remove_below_tier(const tier &min_tier)
- {
- LOG_DEBUG(logger, "Removing all promotions below tier " << min_tier);
-
- if(entries.size() > 0)
- {
- // Note: we have to copy this instead of taking a reference
- // because the source will be deleted, and the callee assumes
- // that the ending tier is valid even after the deletion takes
- // place.
- const tier curr_min_tier(entries.begin()->first);
- if(curr_min_tier < min_tier)
- remove_between_tiers(curr_min_tier, min_tier);
- }
- }
-
-private:
/** \brief Function object that inserts choices into the index
* structures one at a time.
*/
@@ -2170,9 +1997,9 @@ private:
*/
struct entry_ref_in_dropped_set_pred
{
- const boost::unordered_set<entry *> &dropped_set;
+ const boost::unordered_set<const entry *> &dropped_set;
- entry_ref_in_dropped_set_pred(const boost::unordered_set<entry *> &_dropped_set)
+ entry_ref_in_dropped_set_pred(const boost::unordered_set<const entry *> &_dropped_set)
: dropped_set(_dropped_set)
{
}
@@ -2187,24 +2014,31 @@ public:
/** \brief Insert a promotion into this set.
*
* The promotion will not be inserted if an existing promotion of
- * the same tier or higher is a subset of it; otherwise, it will be
- * inserted and all existing promotions of the same tier or lower
- * that are supersets of the new promotion will be removed.
+ * the same tier operation or higher is a subset of it; otherwise,
+ * it will be inserted and all existing promotions of the same tier
+ * operation or lower that are supersets of the new promotion will
+ * be removed. (promotions with an unrelated tier operation are
+ * unaffected)
*
* \return an iterator pointing at the new promotion if one was
* actually inserted, or an end iterator otherwise.
*/
iterator insert(const promotion &p)
{
- const tier &p_tier = p.get_tier();
+ const tier_operation &p_tier_op = p.get_tier_op();
const choice_set &choices = p.get_choices();
LOG_DEBUG(logger, "Inserting " << p << " into the promotion set.");
- const const_iterator highest(find_highest_promotion_for(choices));
- if(highest != end() && highest->get_tier() >= p_tier)
+ // Note that we can suppress adding a promotion if there are
+ // several promotions that would jointly imply it. e.g., if the
+ // set {a, b} has a promotion (0, +1) and {b, c} has a promotion
+ // (+1, 0), we don't need to store a promotion for {a, b, c} with
+ // the operation (+1, +1), as it wouldn't add any information.
+ const tier_operation highest(find_highest_promotion_tier_op(choices));
+ if(tier_operation::least_upper_bound(highest, p_tier_op) == highest)
{
- LOG_INFO(logger, "Canceling the insertion of " << p << ": it is redundant with the existing promotion " << *highest);
+ LOG_INFO(logger, "Canceling the insertion of " << p << ": it is redundant with the existing or inferred promotion " << highest);
return end();
}
else
@@ -2230,7 +2064,7 @@ public:
// Note: This relies on knowing that pointers to entries are
// stable as long as we don't modify the lists that contain
// them.
- boost::unordered_set<entry *> superseded_entries_set;
+ boost::unordered_set<const entry *> superseded_entries_set;
for(typename std::vector<entry_ref>::const_iterator it = superseded_entries.begin();
it != superseded_entries.end(); ++it)
superseded_entries_set.insert(&**it);
@@ -2247,46 +2081,20 @@ public:
{
entry_ref ent(*it);
LOG_TRACE(logger, "Removing " << ent->p);
- const tier removed_tier = ent->p.get_tier();
- typename std::map<tier, std::list<entry> >::iterator found =
- entries.find(removed_tier);
- if(found == entries.end())
- LOG_ERROR(logger, "Tier " << removed_tier << " has gone missing!");
- else
- {
- typename std::list<entry>::size_type initial_size(found->second.size());
- found->second.erase(ent);
- if(found->second.size() + 1 != initial_size)
- LOG_ERROR(logger, "Inconsistency after removing entry: the size should have decreased to " << initial_size - 1 << ", but instead it is now " << found->second.size());
+ if(ent->p.get_tier_op().get_structural_level() >= tier_limits::conflict_structural_level)
+ --num_conflicts;
- if(found->second.empty())
- {
- LOG_DEBUG(logger, "Tier " << removed_tier << " is empty, deleting it.");
- entries.erase(found);
- }
- }
+ entries.erase(ent);
}
- num_promotions -= superseded_entries.size();
- LOG_TRACE(logger, "Inserting " << p << " into tier " << p_tier);
-
- // Find the tier list. Use a roundabout means instead of
- // operator[] so we can log when we allocate a new tier.
- typename std::map<tier, std::list<entry> >::iterator p_tier_found = entries.find(p_tier);
-
- if(p_tier_found == entries.end())
- {
- LOG_DEBUG(logger, "Allocating initial structures for tier " << p_tier);
- p_tier_found = entries.insert(p_tier_found, std::make_pair(p_tier, std::list<entry>()));
- }
+ LOG_TRACE(logger, "Inserting " << p);
// Insert the new entry into the list of entries in this tier.
- std::list<entry> &p_tier_entries = p_tier_found->second;
const entry_ref new_entry =
- p_tier_entries.insert(p_tier_entries.end(),
- entry(p));
- ++num_promotions;
+ entries.insert(entries.end(), entry(p));
+ if(p.get_tier_op().get_structural_level() >= tier_limits::conflict_structural_level)
+ ++num_conflicts;
LOG_TRACE(logger, "Building index entries for " << p);
p.get_choices().for_each(make_index_entries(new_entry,
@@ -2294,7 +2102,7 @@ public:
break_soft_dep_index,
logger));
- return iterator(p_tier_found, entries.end(), new_entry);
+ return iterator(new_entry);
}
}
@@ -2303,7 +2111,7 @@ public:
{
entries.clear();
break_soft_dep_index.clear();
- num_promotions = 0;
+ num_conflicts = 0;
for(int i = 0; i < num_versions; ++i)
{
delete install_version_index[i];
@@ -2315,7 +2123,7 @@ public:
promotion_set_callbacks<PackageUniverse> &_callbacks)
: logger(aptitude::Loggers::getAptitudeResolverSearchTiers()),
callbacks(_callbacks),
- num_promotions(0),
+ num_conflicts(0),
num_versions(u.get_version_count()),
install_version_index(new install_version_index_entry*[num_versions])
{
diff --git a/src/generic/problemresolver/search_graph.h b/src/generic/problemresolver/search_graph.h
index 98db85e8..dde09e6f 100644
--- a/src/generic/problemresolver/search_graph.h
+++ b/src/generic/problemresolver/search_graph.h
@@ -30,6 +30,7 @@
#include "solution.h"
#include "tier.h"
#include "tier_limits.h"
+#include "tier_operation.h"
#include <generic/util/compare3.h>
#include <generic/util/immlist.h>
@@ -127,29 +128,29 @@ private:
boost::flyweights::hashed_factory<hash_choice_set_with_hash> >
choice_set_flyweight;
- tier t;
+ tier_operation t_op;
choice_set_flyweight reasons;
- cwidget::util::ref_ptr<expression<bool> > tier_valid;
+ cwidget::util::ref_ptr<expression<bool> > tier_operation_valid;
cwidget::util::ref_ptr<expression_box<bool> > is_deferred_listener;
public:
generic_solver_information()
- : t(tier_limits::minimum_tier),
+ : t_op(),
reasons(),
- tier_valid(),
+ tier_operation_valid(),
is_deferred_listener()
{
}
/** \brief Create a new solver_information.
*
- * \param _t The tier of the associated solver.
+ * \param _t_op The tier operation of the associated solver.
* \param _reason The reasons for the solver's tier (other than
* the solver itself).
- * \param _tier_valid
+ * \param _tier_operation valid
* A pure expression indicating whether the tier
- * of this solver is valid. Used to create
- * promotions.
+ * operation of this solver is valid. Used to
+ * create promotions.
* \param _is_deferred_listener
* A side-effecting expression whose sub-expression
* is true exactly when this solver violates a
@@ -157,18 +158,18 @@ public:
* here to ensure that the expression remains alive
* while this solver exists.
*/
- generic_solver_information(const tier &_t,
+ generic_solver_information(const tier_operation &_t_op,
const choice_set &_reasons,
- const cwidget::util::ref_ptr<expression<bool> > &_tier_valid,
+ const cwidget::util::ref_ptr<expression<bool> > &_tier_operation_valid,
const cwidget::util::ref_ptr<expression_box<bool> > &_is_deferred_listener)
- : t(_t), reasons(_reasons),
- tier_valid(_tier_valid),
+ : t_op(_t_op), reasons(_reasons),
+ tier_operation_valid(_tier_operation_valid),
is_deferred_listener(_is_deferred_listener)
{
}
/** \brief Retrieve the tier of the associated solver. */
- const tier &get_tier() const { return t; }
+ const tier_operation &get_tier_op() const { return t_op; }
/** \brief Retrieve the reason that this solver has the tier
* that it does.
@@ -179,9 +180,9 @@ public:
* tier is valid (if true, the tier is always valid).
*/
const cwidget::util::ref_ptr<expression<bool> > &
- get_tier_valid() const
+ get_tier_op_valid() const
{
- return tier_valid;
+ return tier_operation_valid;
}
/** \brief Retrieve the listener that tracks whether the solver
@@ -208,9 +209,9 @@ public:
std::size_t get_hash_value() const
{
std::size_t rval = 0;
- boost::hash_combine(rval, tier_valid.unsafe_get_ref());
+ boost::hash_combine(rval, tier_operation_valid.unsafe_get_ref());
boost::hash_combine(rval, is_deferred_listener.unsafe_get_ref());
- boost::hash_combine(rval, t);
+ boost::hash_combine(rval, t_op);
boost::hash_combine(rval, reasons.get().get_hash());
return rval;
@@ -226,9 +227,9 @@ public:
*/
int compare(const generic_solver_information &other) const
{
- if(tier_valid < other.tier_valid)
+ if(tier_operation_valid < other.tier_operation_valid)
return -1;
- else if(other.tier_valid < tier_valid)
+ else if(other.tier_operation_valid < tier_operation_valid)
return -1;
else if(is_deferred_listener < other.is_deferred_listener)
return -1;
@@ -236,11 +237,11 @@ public:
return 1;
else
{
- const int tier_compare =
- aptitude::util::compare3<tier>(t, other.t);
+ const int tier_operation_compare =
+ aptitude::util::compare3<tier_operation>(t_op, other.t_op);
- if(tier_compare != 0)
- return tier_compare;
+ if(tier_operation_compare != 0)
+ return tier_operation_compare;
else
return aptitude::util::compare3<choice_set>(reasons.get().get_choices(), other.reasons.get().get_choices());
}
@@ -789,8 +790,31 @@ public:
*/
int action_score;
- /** \brief The tier of this step. */
- tier step_tier;
+ /** \brief The true tier of this step.
+ *
+ * This is the tier *before* any forward-looking operations are
+ * applied to it.
+ */
+ tier base_step_tier;
+
+ /** \brief The cumulative effect of all forward-looking operations
+ * applied to this step.
+ *
+ * Unlike base_step_tier, this can decrease from step to step
+ * (which is why it's separated; it needs to be recomputed for
+ * each step). This could be computed incrementally, but the
+ * natural way of doing that would require making a frequent
+ * operation (increasing this value) expensive to make an
+ * infrequent operation (creating a new step) less expensive.
+ */
+ tier_operation effective_step_tier_op;
+
+ /** \brief The effective tier of this step.
+ *
+ * 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;
/** \brief A side-effecting expression that fires when the most
* recently added action becomes deferred or un-deferred.
@@ -1478,9 +1502,11 @@ private:
// Returns "true" if anything was generated. We care because we
// need to know whether to queue the parent of the parent for
// propagation.
+ //
+ // Here t_op is the operation we're currently building.
template<typename AddPromotion>
bool add_child_promotions(int parentNum, int childNum, bool has_new_promotion,
- const choice_set &choices, const tier &t,
+ const choice_set &choices, const tier_operation &t_op,
const AddPromotion &addPromotion)
{
// Where to insert any promotions we run into.
@@ -1489,7 +1515,7 @@ private:
? parentNum
: parent.canonical_clone);
const step &canonicalParent = get_step(canonicalParentNum);
- const std::vector<promotion> &canonicalParentPromotionsList = get_promotions_list(parent);
+ const std::vector<promotion> &canonicalParentPromotionsList = get_promotions_list(canonicalParent);
if(canonicalParentNum == parentNum)
LOG_TRACE(logger, "Propagating promotions from the step " << childNum
@@ -1532,7 +1558,6 @@ private:
(it - canonicalChildPromotionsList.begin()) >= (signed)child.promotions_list_first_new_promotion;
choice_set new_choices(choices);
- tier new_tier(t);
const promotion &p(*it);
choice_set p_choices(p.get_choices());
@@ -1545,30 +1570,26 @@ private:
// Strip out the child's link before merging with the existing
// choice set.
p_choices.remove_overlaps(child.reason);
- const tier &p_tier(p.get_tier());
+ const tier_operation &p_tier_op(p.get_tier_op());
// Augment the choice set with these new choices. Narrowing
// is appropriate: anything matching the promotion should
// match all the choices we found.
new_choices.insert_or_narrow(p_choices);
- if(p_tier < new_tier)
- new_tier = p_tier;
- if(canonicalParent.step_tier >= new_tier)
- // No point in generating a promotion whose tier is below
- // the parent's tier.
- {
- LOG_TRACE(logger, "Not backpropagating this promotion: its tier, "
- << new_tier
- << " is not above the tier of step "
- << canonicalParentNum << ", "
- << canonicalParent.step_tier);
- continue;
- }
+ const tier_operation new_tier_op =
+ tier_operation::least_upper_bound(p_tier_op, t_op);
+ // TODO: We used to throw out promotions that were below their
+ // parent's tier. In the new system this *might* correspond
+ // to having a tier operation less than or equal to the
+ // parent's amalgamated tier operation. I'm not 100% sure of
+ // this, and it would require having access to the amalgamated
+ // operation, something I'm not going to code up since this
+ // routine is currently dead.
if(child.is_last_child)
{
- promotion new_promotion(new_choices, new_tier);
+ promotion new_promotion(new_choices, new_tier_op);
// Emit a new promotion.
addPromotion(canonicalParentNum, new_promotion);
@@ -1587,7 +1608,7 @@ private:
bool generated_anything =
add_child_promotions(parentNum, childNum + 1,
new_has_new_promotion,
- new_choices, new_tier,
+ new_choices, new_tier_op,
addPromotion);
rval = rval || generated_anything;
@@ -1616,7 +1637,7 @@ private:
if(add_child_promotions(stepNum, parentStep.first_child,
false, parentStep.successor_constraints,
- tier_limits::maximum_tier,
+ tier_limits::increase_to_maximum_op,
addPromotion))
{
if(parentStep.parent != -1)
@@ -1886,13 +1907,13 @@ public:
template<typename PackageUniverse>
std::ostream &operator<<(std::ostream &out, const generic_solver_information<PackageUniverse> &info)
{
- out << "(" << info.get_tier()
+ out << "(" << info.get_tier_op()
<< ":" << info.get_reasons();
- if(info.get_tier_valid().valid())
+ if(info.get_tier_op_valid().valid())
{
out << "; V: ";
- info.get_tier_valid()->dump(out);
+ info.get_tier_op_valid()->dump(out);
}
if(info.get_is_deferred_listener().valid())
diff --git a/src/generic/problemresolver/tier.h b/src/generic/problemresolver/tier.h
index 02d34266..d18dea6c 100644
--- a/src/generic/problemresolver/tier.h
+++ b/src/generic/problemresolver/tier.h
@@ -125,19 +125,6 @@ public:
}
}
- 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
@@ -158,6 +145,8 @@ public:
{
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);
}
diff --git a/src/generic/problemresolver/tier_limits.cc b/src/generic/problemresolver/tier_limits.cc
index e8c9a5b0..495f895f 100644
--- a/src/generic/problemresolver/tier_limits.cc
+++ b/src/generic/problemresolver/tier_limits.cc
@@ -20,8 +20,20 @@
#include "tier_limits.h"
+const int tier_limits::maximum_level;
+const int tier_limits::conflict_structural_level;
+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));
+const tier_operation tier_limits::increase_to_defer_op(tier_operation::make_advance_structural_level(defer_structural_level));
+const tier_operation tier_limits::minimum_op;
diff --git a/src/generic/problemresolver/tier_limits.h b/src/generic/problemresolver/tier_limits.h
index 7f895fac..567d5ea1 100644
--- a/src/generic/problemresolver/tier_limits.h
+++ b/src/generic/problemresolver/tier_limits.h
@@ -22,6 +22,7 @@
#define TIER_LIMITS_H
#include "tier.h"
+#include "tier_operation.h"
class tier_limits
{
@@ -59,6 +60,16 @@ public:
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.
+ */
+ // @{
+ static const tier_operation increase_to_maximum_op;
+ static const tier_operation increase_to_conflict_op;
+ static const tier_operation increase_to_already_generated_op;
+ static const tier_operation increase_to_defer_op;
+ static const tier_operation minimum_op;
+ // @}
};
#endif
diff --git a/src/generic/util/compare3.h b/src/generic/util/compare3.h
index b030403f..b87b9f2b 100644
--- a/src/generic/util/compare3.h
+++ b/src/generic/util/compare3.h
@@ -27,6 +27,9 @@ namespace std
template<typename Iterator>
class iterator_traits;
+ template<typename T1, typename T2>
+ class pair;
+
template<typename T, typename Alloc>
class list;
@@ -310,6 +313,21 @@ namespace aptitude
};
// Comparison operators for common STL types.
+ template<typename T1, typename T2>
+ class compare3_f<std::pair<T1, T2> >
+ {
+ public:
+ int operator()(const std::pair<T1, T2> &p1,
+ const std::pair<T1, T2> &p2) const
+ {
+ const int cmp1 = compare3(p1.first, p2.first);
+ if(cmp1 != 0)
+ return cmp1;
+ else
+ return compare3(p1.second, p2.second);
+ }
+ };
+
template<typename T, typename Alloc>
class compare3_f<std::list<T, Alloc> >
: public compare3_f_container<std::list<T, Alloc> >
diff --git a/src/gtk/resolver.cc b/src/gtk/resolver.cc
index 1ecd866a..ee7f1d5a 100644
--- a/src/gtk/resolver.cc
+++ b/src/gtk/resolver.cc
@@ -1,6 +1,6 @@
// resolver.cc
//
-// Copyright 1999-2009 Daniel Burrows
+// Copyright 1999-2010 Daniel Burrows
// Copyright 2008 Obey Arthur Liu
//
// This program is free software; you can redistribute it and/or modify
@@ -2104,11 +2104,9 @@ namespace gui
solution_view->set_model(store, get_resolver());
solution_view->get_treeview()->expand_all();
- const std::string tier_name(aptitude_universe::get_tier_name(displayed_solution.get_tier()));
- pResolverStatus->set_markup(ssprintf(_("Solution %s of %s (tier %s)."),
+ pResolverStatus->set_markup(ssprintf(_("Solution %s of %s."),
largenum(index).c_str(),
- largenum(state.generated_solutions).c_str(),
- Glib::Markup::escape_text(tier_name).c_str()));
+ largenum(state.generated_solutions).c_str()));
}
else
LOG_TRACE(Loggers::getAptitudeGtkResolver(),
diff --git a/src/solution_fragment.cc b/src/solution_fragment.cc
index a5e85d81..bf951d4c 100644
--- a/src/solution_fragment.cc
+++ b/src/solution_fragment.cc
@@ -502,7 +502,6 @@ cw::fragment *solution_fragment_with_ids(const aptitude_solution &sol,
}
ids_column.append_newline();
- fragments.push_back(cw::fragf(_("Tier: %s"), aptitude_universe::get_tier_name(sol.get_tier()).c_str()));
if(ids == NULL)
return flowbox(cw::sequence_fragment(fragments));
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 9f75a753..a279992b 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -27,7 +27,8 @@ test_promotion_set.o test_resolver_hints.o: $(top_srcdir)/src/generic/problemres
# way...
cppunit_test_SOURCES = \
cppunit_test_main.cc \
- test_choice.cc \
+ test_resolver.cc
+#test_choice.cc \
test_choice_set.cc \
test_config_pusher.cc \
test_dense_setset.cc \
diff --git a/tests/test_promotion_set.cc b/tests/test_promotion_set.cc
index 19ef5bc7..4f4d79d6 100644
--- a/tests/test_promotion_set.cc
+++ b/tests/test_promotion_set.cc
@@ -66,8 +66,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
CPPUNIT_TEST_SUITE(Promotion_SetTest);
CPPUNIT_TEST(testFindHighestPromotion);
- CPPUNIT_TEST(testRemoveBetweenTiers);
- CPPUNIT_TEST(testRemoveBelowTier);
+ CPPUNIT_TEST(testErase);
CPPUNIT_TEST_SUITE_END();
@@ -104,23 +103,17 @@ class Promotion_SetTest : public CppUnit::TestFixture
return rval;
}
- static tier make_tier(int first_user_level)
+ static tier_operation make_tier_op(int first_user_level)
{
- level l(level::make_lower_bounded(first_user_level));
-
- return tier(tier_limits::minimum_level,
- &l,
- (&l) + 1);
+ return
+ tier_operation::make_advance_user_level(0, first_user_level);
}
- static tier make_tier(int first_user_level, int second_user_level)
+ static tier_operation make_tier_op(int first_user_level, int second_user_level)
{
- level user_levels[2] = { level::make_lower_bounded(first_user_level),
- level::make_lower_bounded(second_user_level) };
-
- return tier(tier_limits::minimum_level,
- user_levels,
- user_levels + 2);
+ return
+ tier_operation::make_advance_user_level(0, first_user_level) +
+ tier_operation::make_advance_user_level(1, second_user_level);
}
static void make_test_promotions(const dummy_universe_ref &u,
@@ -172,7 +165,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
choice_set p1_choices;
p1_choices.insert_or_narrow(make_install_version_from_dep_source(av1, av2d1));
- promotion p1(p1_choices, make_tier(100));
+ promotion p1(p1_choices, make_tier_op(100));
expected_promotions.insert(p1);
promotions.insert(p1);
CPPUNIT_ASSERT_EQUAL(expected_promotions, get_promotions(promotions));
@@ -183,7 +176,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
p2_choices.insert_or_narrow(make_install_version(av1));
p2_choices.insert_or_narrow(make_install_version(bv2));
p2_choices.insert_or_narrow(make_install_version(cv3));
- promotion p2(p2_choices, make_tier(50));
+ promotion p2(p2_choices, make_tier_op(50));
expected_promotions.insert(p2);
promotions.insert(p2);
CPPUNIT_ASSERT_EQUAL(expected_promotions, get_promotions(promotions));
@@ -193,7 +186,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
choice_set p3_choices;
p3_choices.insert_or_narrow(make_install_version(av1));
p3_choices.insert_or_narrow(make_install_version(bv2));
- promotion p3(p3_choices, make_tier(75));
+ promotion p3(p3_choices, make_tier_op(75));
expected_promotions.insert(p3);
expected_promotions.erase(p2);
promotions.insert(p3);
@@ -205,7 +198,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
p4_choices.insert_or_narrow(make_install_version(av1));
p4_choices.insert_or_narrow(make_install_version(bv2));
p4_choices.insert_or_narrow(make_install_version(cv1));
- promotion p4(p4_choices, make_tier(10));
+ promotion p4(p4_choices, make_tier_op(10));
promotions.insert(p4);
CPPUNIT_ASSERT_EQUAL(expected_promotions, get_promotions(promotions));
CPPUNIT_ASSERT_EQUAL(expected_promotions.size(), promotions.size());
@@ -213,7 +206,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
choice_set p5_choices;
p5_choices.insert_or_narrow(make_install_version(bv2));
- promotion p5(p5_choices, make_tier(30));
+ promotion p5(p5_choices, make_tier_op(30));
expected_promotions.insert(p5);
promotions.insert(p5);
CPPUNIT_ASSERT_EQUAL(expected_promotions, get_promotions(promotions));
@@ -222,7 +215,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
choice_set p6_choices;
p6_choices.insert_or_narrow(make_break_soft_dep(bv2d1));
- promotion p6(p6_choices, make_tier(125));
+ promotion p6(p6_choices, make_tier_op(125));
expected_promotions.insert(p6);
promotions.insert(p6);
CPPUNIT_ASSERT_EQUAL(expected_promotions.size(), promotions.size());
@@ -232,7 +225,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
choice_set p7_choices;
p7_choices.insert_or_narrow(make_install_version(cv3));
p7_choices.insert_or_narrow(make_break_soft_dep(bv2d1));
- promotion p7(p7_choices, make_tier(125, 10));
+ promotion p7(p7_choices, make_tier_op(125, 10));
expected_promotions.insert(p7);
promotions.insert(p7);
std::cout << expected_promotions << std::endl;
@@ -244,7 +237,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
choice_set p8_choices;
p8_choices.insert_or_narrow(make_install_version_from_dep_source(bv3, bv2d1));
p8_choices.insert_or_narrow(make_install_version(cv2));
- promotion p8(p8_choices, make_tier(50));
+ promotion p8(p8_choices, make_tier_op(50));
expected_promotions.insert(p8);
promotions.insert(p8);
CPPUNIT_ASSERT_EQUAL(expected_promotions, get_promotions(promotions));
@@ -335,26 +328,23 @@ public:
choice_set expected1_choices;
expected1_choices.insert_or_narrow(make_install_version(cv3));
expected1_choices.insert_or_narrow(make_break_soft_dep(bv2d1));
- promotion expected1(expected1_choices, make_tier(125, 10));
+ promotion expected1(expected1_choices, make_tier_op(125, 10));
- dummy_promotion_set::const_iterator found = p.find_highest_promotion_for(search1);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected1, *found);
+ tier_operation found_op = p.find_highest_promotion_tier_op(search1);
+ CPPUNIT_ASSERT_EQUAL(expected1.get_tier_op(), found_op);
- dummy_promotion_set::const_iterator found2 =
+ promotion found2 =
p.find_highest_promotion_containing(search1, make_install_version(av1));
- CPPUNIT_ASSERT(found2 == p.end());
+ CPPUNIT_ASSERT(found2 == promotion());
found2 = p.find_highest_promotion_containing(search1, make_install_version(bv3));
- CPPUNIT_ASSERT(found2 == p.end());
+ CPPUNIT_ASSERT(found2 == promotion());
found2 = p.find_highest_promotion_containing(search1, make_install_version(cv3));
- CPPUNIT_ASSERT(found2 != p.end());
- CPPUNIT_ASSERT_EQUAL(expected1, *found2);
+ CPPUNIT_ASSERT_EQUAL(expected1, found2);
found2 = p.find_highest_promotion_containing(search1, make_break_soft_dep(bv2d1));
- CPPUNIT_ASSERT(found2 != p.end());
- CPPUNIT_ASSERT_EQUAL(expected1, *found2);
+ CPPUNIT_ASSERT_EQUAL(expected1, found2);
// Incipient search: (Install(a v1), Install(b v3),
// Install(c v3)) + {Break(b v2 -> <c v2>)})
@@ -466,9 +456,9 @@ public:
search2.insert_or_narrow(make_install_version(av1));
search2.insert_or_narrow(make_install_version(bv1));
- CPPUNIT_ASSERT(p.find_highest_promotion_for(search2) == p.end());
- CPPUNIT_ASSERT(p.find_highest_promotion_containing(search2, make_install_version(av1)) == p.end());
- CPPUNIT_ASSERT(p.find_highest_promotion_containing(search2, make_install_version(bv1)) == p.end());
+ CPPUNIT_ASSERT(p.find_highest_promotion_tier_op(search2) == tier_operation());
+ CPPUNIT_ASSERT(p.find_highest_promotion_containing(search2, make_install_version(av1)) == promotion());
+ CPPUNIT_ASSERT(p.find_highest_promotion_containing(search2, make_install_version(bv1)) == promotion());
// Third search: (Break(b v2 -> <c v2>))
//
@@ -479,15 +469,13 @@ public:
search3.insert_or_narrow(make_break_soft_dep(bv2d1));
choice_set expected_choices3 = search3;
- promotion expected3(expected_choices3, make_tier(125));
+ promotion expected3(expected_choices3, make_tier_op(125));
- found = p.find_highest_promotion_for(search3);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected3, *found);
+ found_op = p.find_highest_promotion_tier_op(search3);
+ CPPUNIT_ASSERT_EQUAL(expected3.get_tier_op(), found_op);
- found = p.find_highest_promotion_containing(search3, make_break_soft_dep(bv2d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected3, *found);
+ found2 = p.find_highest_promotion_containing(search3, make_break_soft_dep(bv2d1));
+ CPPUNIT_ASSERT_EQUAL(expected3, found2);
// Fourth search: (Install(a v1 [a v3 -> <>]), Install(b v2))
//
@@ -503,19 +491,16 @@ public:
choice_set expected_choices4;
expected_choices4.insert_or_narrow(make_install_version(av1));
expected_choices4.insert_or_narrow(make_install_version(bv2));
- promotion expected4(expected_choices4, make_tier(75));
+ promotion expected4(expected_choices4, make_tier_op(75));
- found = p.find_highest_promotion_for(search4);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected4, *found);
+ found_op = p.find_highest_promotion_tier_op(search4);
+ CPPUNIT_ASSERT_EQUAL(expected4.get_tier_op(), found_op);
- found = p.find_highest_promotion_containing(search4, make_install_version_from_dep_source(av1, av3d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected4, *found);
+ found2 = p.find_highest_promotion_containing(search4, make_install_version_from_dep_source(av1, av3d1));
+ CPPUNIT_ASSERT_EQUAL(expected4, found2);
- found = p.find_highest_promotion_containing(search4, make_install_version(bv2));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected4, *found);
+ found2 = p.find_highest_promotion_containing(search4, make_install_version(bv2));
+ CPPUNIT_ASSERT_EQUAL(expected4, found2);
// Fifth search: (Install(a v1 [a v2 -> <>]), Install(b v2))
@@ -530,15 +515,13 @@ public:
choice_set expected_choices5;
expected_choices5.insert_or_narrow(make_install_version_from_dep_source(av1, av2d1));
- promotion expected5(expected_choices5, make_tier(100));
+ promotion expected5(expected_choices5, make_tier_op(100));
- found = p.find_highest_promotion_for(search5);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected5, *found);
+ found_op = p.find_highest_promotion_tier_op(search5);
+ CPPUNIT_ASSERT_EQUAL(expected5.get_tier_op(), found_op);
- found = p.find_highest_promotion_containing(search5, make_install_version_from_dep_source(av1, av2d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected5, *found);
+ found2 = p.find_highest_promotion_containing(search5, make_install_version_from_dep_source(av1, av2d1));
+ CPPUNIT_ASSERT_EQUAL(expected5, found2);
// Incipient search: (Install(b v2)) + {Install(a v1 [a v2 -> <>])}
choice_set search5_incipient1;
@@ -594,10 +577,9 @@ public:
choice_set expected_choices5_2;
expected_choices5_2.insert_or_narrow(make_install_version(av1));
expected_choices5_2.insert_or_narrow(make_install_version(bv2));
- promotion expected5_2(expected_choices5_2, make_tier(75));
- found = p.find_highest_promotion_containing(search5, make_install_version(bv2));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected5_2, *found);
+ promotion expected5_2(expected_choices5_2, make_tier_op(75));
+ found2 = p.find_highest_promotion_containing(search5, make_install_version(bv2));
+ CPPUNIT_ASSERT_EQUAL(expected5_2, found2);
// Incipient search: (Install(a v1)) + {Install(b v2)}
choice_set search5_incipient2;
@@ -635,9 +617,9 @@ public:
search6.insert_or_narrow(make_install_version(bv3));
search6.insert_or_narrow(make_install_version(cv2));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_for(search6));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(search6, make_install_version(bv3)));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(search6, make_install_version(cv2)));
+ CPPUNIT_ASSERT(tier_operation() == p.find_highest_promotion_tier_op(search6));
+ CPPUNIT_ASSERT(promotion() == p.find_highest_promotion_containing(search6, make_install_version(bv3)));
+ CPPUNIT_ASSERT(promotion() == p.find_highest_promotion_containing(search6, make_install_version(cv2)));
// Check that we can match (Install(bv3 [bv2 -> <c v2>], cv2))
// instead.
@@ -645,22 +627,19 @@ public:
search7.insert_or_narrow(make_install_version_from_dep_source(bv3, bv2d1));
search7.insert_or_narrow(make_install_version(cv2));
- promotion expected7(search7, make_tier(50));
+ promotion expected7(search7, make_tier_op(50));
- found = p.find_highest_promotion_for(search7);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected7, *found);
+ found_op = p.find_highest_promotion_tier_op(search7);
+ CPPUNIT_ASSERT_EQUAL(expected7.get_tier_op(), found_op);
- found = p.find_highest_promotion_containing(search7, make_install_version_from_dep_source(bv3, bv2d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected7, *found);
+ found2 = p.find_highest_promotion_containing(search7, make_install_version_from_dep_source(bv3, bv2d1));
+ CPPUNIT_ASSERT_EQUAL(expected7, found2);
- found = p.find_highest_promotion_containing(search7, make_install_version(cv2));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected7, *found);
+ found2 = p.find_highest_promotion_containing(search7, make_install_version(cv2));
+ CPPUNIT_ASSERT_EQUAL(expected7, found2);
}
- void testRemoveBetweenTiers()
+ void testErase()
{
dummy_universe_ref u(parseUniverse(dummy_universe_1));
dummy_promotion_set_callbacks callbacks;
@@ -691,8 +670,20 @@ public:
// Remove tiers 50 and (125, 10), and make sure they don't show up
// in the results.
- p.remove_between_tiers(make_tier(50), make_tier(100));
- p.remove_between_tiers(make_tier(125, 10), make_tier(500));
+ {
+ dummy_promotion_set::iterator it = p.begin(), next = it;
+
+ while(it != p.end())
+ {
+ ++next;
+
+ if(it->get_tier_op() == make_tier_op(50) ||
+ it->get_tier_op() == make_tier_op(125, 10))
+ p.erase(it);
+
+ it = next;
+ }
+ }
// Check that the size and contents (when iterating) of the
// promotion set are maintained correctly.
@@ -700,7 +691,7 @@ public:
imm::set<promotion> expected_promotions;
choice_set p1_choices;
p1_choices.insert_or_narrow(make_install_version_from_dep_source(av1, av2d1));
- promotion p1(p1_choices, make_tier(100));
+ promotion p1(p1_choices, make_tier_op(100));
expected_promotions.insert(p1);
p.insert(p1);
@@ -708,20 +699,20 @@ public:
choice_set p2_choices;
p2_choices.insert_or_narrow(make_install_version(av1));
p2_choices.insert_or_narrow(make_install_version(bv2));
- promotion p2(p2_choices, make_tier(75));
+ promotion p2(p2_choices, make_tier_op(75));
expected_promotions.insert(p2);
p.insert(p2);
choice_set p3_choices;
p3_choices.insert_or_narrow(make_install_version(bv2));
- promotion p3(p3_choices, make_tier(30));
+ promotion p3(p3_choices, make_tier_op(30));
expected_promotions.insert(p3);
p.insert(p3);
choice_set p4_choices;
p4_choices.insert_or_narrow(make_break_soft_dep(bv2d1));
- promotion p4(p4_choices, make_tier(125));
+ promotion p4(p4_choices, make_tier_op(125));
expected_promotions.insert(p4);
p.insert(p4);
@@ -744,24 +735,22 @@ public:
choice_set expected_choices1;
expected_choices1.insert_or_narrow(make_break_soft_dep(bv2d1));
- promotion expected1(expected_choices1, make_tier(125));
+ promotion expected1(expected_choices1, make_tier_op(125));
- dummy_promotion_set::const_iterator found = p.find_highest_promotion_for(search1);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected1, *found);
+ tier_operation found_op = p.find_highest_promotion_tier_op(search1);
+ CPPUNIT_ASSERT_EQUAL(expected1.get_tier_op(), found_op);
- found = p.find_highest_promotion_containing(search1, make_install_version(av1));
- CPPUNIT_ASSERT(found == p.end());
+ promotion found_p = p.find_highest_promotion_containing(search1, make_install_version(av1));
+ CPPUNIT_ASSERT(found_p == promotion());
- found = p.find_highest_promotion_containing(search1, make_install_version(bv3));
- CPPUNIT_ASSERT(found == p.end());
+ found_p = p.find_highest_promotion_containing(search1, make_install_version(bv3));
+ CPPUNIT_ASSERT(found_p == promotion());
- found = p.find_highest_promotion_containing(search1, make_install_version(cv3));
- CPPUNIT_ASSERT(found == p.end());
+ found_p = p.find_highest_promotion_containing(search1, make_install_version(cv3));
+ CPPUNIT_ASSERT(found_p == promotion());
- found = p.find_highest_promotion_containing(search1, make_break_soft_dep(bv2d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(expected1, *found);
+ found_p = p.find_highest_promotion_containing(search1, make_break_soft_dep(bv2d1));
+ CPPUNIT_ASSERT_EQUAL(expected1, found_p);
// Nothing should match the tier-50 promotion.
@@ -770,133 +759,9 @@ public:
search2.insert_or_narrow(make_install_version_from_dep_source(bv3, bv2d1));
search2.insert_or_narrow(make_install_version(cv2));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_for(search2));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(search2, make_install_version_from_dep_source(bv3, bv2d1)));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(search2, make_install_version(cv2)));
- }
-
- void testRemoveBelowTier()
- {
- dummy_universe_ref u(parseUniverse(dummy_universe_1));
- dummy_promotion_set_callbacks callbacks;
- dummy_promotion_set p(u, callbacks);
-
- package a(u.find_package("a"));
- package b(u.find_package("b"));
- package c(u.find_package("c"));
-
- version av1(a.version_from_name("v1"));
- version av2(a.version_from_name("v2"));
- version av3(a.version_from_name("v3"));
-
- version bv1(b.version_from_name("v1"));
- version bv2(b.version_from_name("v2"));
- version bv3(b.version_from_name("v3"));
-
- version cv1(c.version_from_name("v1"));
- version cv2(c.version_from_name("v2"));
- version cv3(c.version_from_name("v3"));
-
- dep av1d1(*av1.deps_begin());
- dep bv2d1(*bv2.deps_begin());
- dep av2d1(*av2.deps_begin());
- dep av3d1(*av3.deps_begin());
-
- make_test_promotions(u, p);
-
- // Remove everything below (and including) tier 75.
- p.remove_below_tier(make_tier(76));
-
- // We expect {(T100: Install(a v1 [a v2 -> <>])),
- // (T125: Break(b v2 -> <c v2>)),
- // (T(125, 10): Install(c v3), Break(b v2 -> c v2))}
- //
- // The previously available promotions
- // (T75: Install(a v1, b v2)),
- // (T50: Install(b v3 [b v2 -> <c v2>], cv2)), and
- // (T30: Install(b v2))
- // should be gone.
- imm::set<promotion> expected;
- choice_set p1_choices;
- p1_choices.insert_or_narrow(make_install_version_from_dep_source(av1, av2d1));
- promotion p1(p1_choices, make_tier(100));
- expected.insert(p1);
-
- choice_set p2_choices;
- p2_choices.insert_or_narrow(make_break_soft_dep(bv2d1));
- promotion p2(p2_choices, make_tier(125));
- expected.insert(p2);
-
- choice_set p3_choices;
- p3_choices.insert_or_narrow(make_install_version(cv3));
- p3_choices.insert_or_narrow(make_break_soft_dep(bv2d1));
- promotion p3(p3_choices, make_tier(125, 10));
- expected.insert(p3);
-
-
- // Unexpected promotions. These should match nothing.
- choice_set up1_choices;
- up1_choices.insert_or_narrow(make_install_version(av1));
- up1_choices.insert_or_narrow(make_install_version(bv2));
-
- choice_set up2_choices;
- up2_choices.insert_or_narrow(make_install_version(bv2));
-
- choice_set up3_choices;
- up3_choices.insert_or_narrow(make_install_version_from_dep_source(bv3, bv2d1));
- up3_choices.insert_or_narrow(make_install_version(cv2));
-
- // Check that the new size of the set is correct.
- CPPUNIT_ASSERT_EQUAL(expected.size(), p.size());
- CPPUNIT_ASSERT_EQUAL(expected.size(), empirical_promotions_size(p));
- CPPUNIT_ASSERT_EQUAL(expected, get_promotions(p));
-
- // Check that each remaining promotion is reachable via the find_*
- // methods.
- dummy_promotion_set::const_iterator found;
-
- found = p.find_highest_promotion_for(p1_choices);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(p1, *found);
-
- found = p.find_highest_promotion_containing(p1_choices, make_install_version_from_dep_source(av1, av2d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(p1, *found);
-
-
- found = p.find_highest_promotion_for(p2_choices);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(p2, *found);
-
- found = p.find_highest_promotion_containing(p2_choices, make_break_soft_dep(bv2d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(p2, *found);
-
-
- found = p.find_highest_promotion_for(p3_choices);
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(p3, *found);
-
- found = p.find_highest_promotion_containing(p3_choices, make_install_version(cv3));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(p3, *found);
-
- found = p.find_highest_promotion_containing(p3_choices, make_break_soft_dep(bv2d1));
- CPPUNIT_ASSERT(found != p.end());
- CPPUNIT_ASSERT_EQUAL(p3, *found);
-
- // Check that the unexpected promotions are unreachable.
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_for(up1_choices));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(up1_choices, make_install_version(av1)));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(up1_choices, make_install_version(bv2)));
-
-
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_for(up2_choices));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(up2_choices, make_install_version(bv2)));
-
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_for(up3_choices));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(up3_choices, make_install_version_from_dep_source(bv3, bv2d1)));
- CPPUNIT_ASSERT(p.end() == p.find_highest_promotion_containing(up3_choices, make_install_version(cv2)));
+ CPPUNIT_ASSERT(tier_operation() == p.find_highest_promotion_tier_op(search2));
+ CPPUNIT_ASSERT(promotion() == p.find_highest_promotion_containing(search2, make_install_version_from_dep_source(bv3, bv2d1)));
+ CPPUNIT_ASSERT(promotion() == p.find_highest_promotion_containing(search2, make_install_version(cv2)));
}
};
diff --git a/tests/test_resolver.cc b/tests/test_resolver.cc
index 0df0be01..34305763 100644
--- a/tests/test_resolver.cc
+++ b/tests/test_resolver.cc
@@ -998,10 +998,8 @@ private:
r.set_version_score(av2, 1000);
r.set_version_score(bv2, -100);
r.set_version_score(cv2, -100);
- level av2_user_level = level::make_lower_bounded(100);
- r.set_version_min_tier(av2, tier(tier_limits::minimum_level,
- &av2_user_level,
- (&av2_user_level) + 1));
+ r.set_version_tier_op(av2,
+ tier_operation::make_advance_user_level(0, 100));
solution sol;
try
@@ -1061,9 +1059,20 @@ private:
std::vector<tier_operation> ops;
ops.push_back(tier_operation::make_advance_structural_level(100));
ops.push_back(tier_operation::make_add_to_user_level(0, 2) +
- tier_operation::make_add_to_user_level(0, 4));
+ tier_operation::make_add_to_user_level(1, 4));
ops.push_back(tier_operation::make_add_to_user_level(0, 1) +
- tier_operation::make_add_to_user_level(2, 5));
+ tier_operation::make_advance_user_level(2, 5));
+
+ LOG_TRACE(logger, "Checking that converting operations to strings works.");
+
+ CPPUNIT_ASSERT_EQUAL(std::string("(advance: 100)"),
+ boost::lexical_cast<std::string>(ops[0]));
+ CPPUNIT_ASSERT_EQUAL(std::string("(nop, add: 2, add: 4)"),
+ boost::lexical_cast<std::string>(ops[1]));
+ CPPUNIT_ASSERT_EQUAL(std::string("(nop, add: 1, nop, advance: 5)"),
+ boost::lexical_cast<std::string>(ops[2]));
+
+ LOG_TRACE(logger, "Checking that instantiating illegal operations fails.");
// Test that instantiating illegal operations fails.
CPPUNIT_ASSERT_THROW(tier_operation::make_add_to_user_level(0, 0),
@@ -1075,6 +1084,8 @@ private:
CPPUNIT_ASSERT_THROW(tier_operation::make_advance_user_level(-1, 5),
std::out_of_range);
+ LOG_TRACE(logger, "Testing that combining incompatible operations fails.");
+
// Test that combining incompatible operations fails. Also, take
// the opportunity to test a few additional operation
// combinations.
@@ -1098,6 +1109,8 @@ private:
CPPUNIT_ASSERT_THROW(tier_operation::greatest_lower_bound(incompatible1, ops[1]),
TierOperationMismatchException);
+ LOG_TRACE(logger, "Checking the outcome of some particular operation compositions.");
+
CPPUNIT_ASSERT_EQUAL(std::string("(nop, add: 3, advance: 6, advance: 5)"),
boost::lexical_cast<std::string>(incompatible1 + ops[2]));
CPPUNIT_ASSERT_EQUAL(std::string("(nop, add: 2, advance: 6, advance: 5)"),
@@ -1105,6 +1118,8 @@ private:
CPPUNIT_ASSERT_EQUAL(std::string("(nop, add: 1, nop, advance: 3)"),
boost::lexical_cast<std::string>(tier_operation::greatest_lower_bound(incompatible1, ops[2])));
+ LOG_TRACE(logger, "Testing out-of-bounds operations.");
+
// Test out-of-bound operations.
CPPUNIT_ASSERT_THROW(tier_operation::make_add_to_user_level(1, INT_MAX) +
tier_operation::make_add_to_user_level(1, 5),
@@ -1116,6 +1131,8 @@ 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),
@@ -1143,10 +1160,12 @@ private:
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(4));
+ 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.");
+
// Combined values. Each vector is a matrix where [i][j] contains
// the combination of entries i and j for i<=j. Combined values
// are stored as strings to avoid any bias from passing through
@@ -1164,7 +1183,7 @@ private:
lubs[1][1] = op_renderings[1];
lubs[1][2] = "(nop, add: 2, add: 4, advance: 5)";
- lubs[2][0] = lubs[2][0];
+ lubs[2][0] = lubs[0][2];
lubs[2][1] = lubs[1][2];
lubs[2][2] = op_renderings[2];
diff --git a/tests/test_resolver_hints.cc b/tests/test_resolver_hints.cc
index 2ab82f6a..a1ead827 100644
--- a/tests/test_resolver_hints.cc
+++ b/tests/test_resolver_hints.cc
@@ -32,12 +32,9 @@ namespace
{
typedef aptitude_resolver::hint hint;
- tier make_tier(int first_user_level)
+ tier_operation make_tier_op(int first_user_level)
{
- level l(level::make_lower_bounded(first_user_level));
- return tier(tier_limits::minimum_level,
- &l,
- (&l) + 1);
+ return tier_operation::make_advance_user_level(0, first_user_level);
}
struct test
@@ -85,17 +82,17 @@ namespace
test("reject ?task(desktop) <>4.0", hint::make_reject(pattern::make_task("desktop"),
hint::version_selection::make_version(hint::version_selection::not_equal_to, "4.0"))),
test("increase-tier-to 100 wesnoth <5.0.0",
- hint::make_increase_tier_to(pattern::make_exact_name("wesnoth"),
- hint::version_selection::make_version(hint::version_selection::less_than, "5.0.0"),
- make_tier(100))),
+ hint::make_compose_tier_op(pattern::make_exact_name("wesnoth"),
+ hint::version_selection::make_version(hint::version_selection::less_than, "5.0.0"),
+ make_tier_op(100))),
test("increase-tier-to 500 xroach",
- hint::make_increase_tier_to(pattern::make_exact_name("xroach"),
- hint::version_selection::make_inst(),
- make_tier(500))),
+ hint::make_compose_tier_op(pattern::make_exact_name("xroach"),
+ hint::version_selection::make_inst(),
+ make_tier_op(500))),
test("increase-tier-to 800 xroach",
- hint::make_increase_tier_to(pattern::make_exact_name("xroach"),
- hint::version_selection::make_inst(),
- make_tier(800))),
+ hint::make_compose_tier_op(pattern::make_exact_name("xroach"),
+ hint::version_selection::make_inst(),
+ make_tier_op(800))),
};
const int num_resolver_tests =
sizeof(resolver_tests) / sizeof(resolver_tests[0]);
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 08:16:39 +0000