Write the backend half of the code to support customizable cost components.

Still needed: a parser, unit tests, documentation, and the final
tying-together code in resolver_manager.

11 files changed, 922 insertions, 61 deletions

diff --git a/src/generic/apt/Makefile.am b/src/generic/apt/Makefile.am
index aadf9bed..319b8305 100644
--- a/src/generic/apt/Makefile.am
+++ b/src/generic/apt/Makefile.am
@@ -23,6 +23,10 @@ libgeneric_apt_a_SOURCES = \
         aptitudepolicy.h    \
         aptitude_resolver.cc \
         aptitude_resolver.h \
+        aptitude_resolver_cost_settings.cc \
+        aptitude_resolver_cost_settings.h \
+        aptitude_resolver_cost_syntax.cc \
+        aptitude_resolver_cost_syntax.h \
         aptitude_resolver_universe.cc \
         aptitude_resolver_universe.h \
         apt_undo_group.cc   \
diff --git a/src/generic/apt/aptitude_resolver.cc b/src/generic/apt/aptitude_resolver.cc
index e6629f38..2598b7cf 100644
--- a/src/generic/apt/aptitude_resolver.cc
+++ b/src/generic/apt/aptitude_resolver.cc
@@ -51,28 +51,37 @@ namespace
   log4cxx::LoggerPtr loggerScores(aptitude::Loggers::getAptitudeResolverScores());
   log4cxx::LoggerPtr loggerTiers(aptitude::Loggers::getAptitudeResolverTiers());
 
-  /** \brief Return a tier that has the same major level as the given
-   *  base tier, but whose subordinate values have been set
-   *  appropriately for the given version.
+  /** \brief If the given version is valid, find its maximum priority
+   *  and return a raise-cost operation for that priority.
    */
-  tier_operation specialize_tier_op(const tier_operation &base,
-				    const pkgCache::VerIterator &ver,
-				    pkgPolicy *policy)
+  tier_operation raise_priority_op(aptitude_resolver_cost_settings &settings,
+                                   const aptitude_resolver_version &ver,
+                                   pkgPolicy *policy,
+                                   aptitude_resolver_cost_settings::component &priority_component)
   {
-    if(ver.end())
-      return base;
-    else
+    if(!settings.is_component_relevant(priority_component))
+      return tier_operation();
+
+    pkgCache::VerIterator apt_ver(ver.get_ver());
+
+    if(!apt_ver.end())
       {
 	int apt_priority = INT_MIN;
-	for(pkgCache::VerFileIterator vf = ver.FileList();
+	for(pkgCache::VerFileIterator vf = apt_ver.FileList();
 	    !vf.end(); ++vf)
 	  {
 	    int pin = policy->GetPriority(vf.File());
 	    apt_priority = std::max(apt_priority, pin);
 	  }
 
-	return base + tier_operation::make_advance_user_level(0, -apt_priority);
+        if(apt_priority > INT_MIN)
+          return settings.raise_cost(priority_component,
+                                     apt_priority);
+        else
+          return tier_operation();
       }
+    else
+      return tier_operation();
   }
 }
 
@@ -715,6 +724,7 @@ aptitude_resolver::aptitude_resolver(int step_score,
 				     int infinity,
 				     int resolution_score,
 				     int future_horizon,
+				     const aptitude_resolver_cost_settings &_cost_settings,
 				     const imm::map<aptitude_resolver_package, aptitude_resolver_version> &initial_installations,
 				     aptitudeDepCache *cache,
 				     pkgPolicy *_policy)
@@ -722,7 +732,8 @@ aptitude_resolver::aptitude_resolver(int step_score,
 					       future_horizon,
 					       initial_installations,
 					       aptitude_universe(cache)),
-   policy(_policy)
+   policy(_policy),
+   cost_settings(_cost_settings)
 {
   using cwidget::util::ref_ptr;
   using aptitude::matching::pattern;
@@ -732,7 +743,11 @@ aptitude_resolver::aptitude_resolver(int step_score,
 	    << ", infinity = " << infinity << ", resolution_score = " << resolution_score
 	    << ", future_horizon = " << future_horizon << ".");
 
-  tier_operation keep_all_tier_op(aptitude_universe::get_keep_all_tier_op());
+  aptitude_resolver_cost_settings::component safety_component =
+    cost_settings.get_or_create_component("safety", aptitude_resolver_cost_settings::maximized);
+
+  int keep_all_level(aptitude_universe::get_keep_all_level());
+  tier_operation keep_all_tier_op(cost_settings.raise_cost(safety_component, keep_all_level));
 
   set_remove_stupid(aptcfg->FindB(PACKAGE "::ProblemResolver::Remove-Stupid-Pairs", true));
 
@@ -1163,12 +1178,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_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());
+  int safe_level(aptitude_universe::get_safe_level());
+  int keep_all_level(aptitude_universe::get_keep_all_level());
+  int remove_level(aptitude_universe::get_remove_level());
+  int break_hold_level(aptitude_universe::get_break_hold_level());
+  int non_default_level(aptitude_universe::get_non_default_level());
+  int remove_essential_level(aptitude_universe::get_remove_essential_level());
 
   LOG_TRACE(loggerScores, "Setting up action scores; score parameters: preserver_score = " << preserve_score
 	    << ", auto_score = " << auto_score << ", remove_score = " << remove_score
@@ -1180,10 +1195,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_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 << ".");
+  LOG_TRACE(loggerTiers, "Setting up action scores; tier parameters: safe_level = " << safe_level
+	    << ", keep_all_level = " << keep_all_level << ", remove_level = " << remove_level
+	    << ", break_hold_level = " << break_hold_level << ", non_default_level = "
+	    << non_default_level << ", remove_essential_level = " << remove_essential_level << ".");
 
   cwidget::util::ref_ptr<aptitude::matching::search_cache>
     search_info(aptitude::matching::search_cache::create());
@@ -1191,6 +1206,33 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
   pkgRecords records(*cache);
   const resolver_initial_state<aptitude_universe> &initial_state(get_initial_state());
 
+  aptitude_resolver_cost_settings::component
+    safety_component(cost_settings.get_or_create_component("safety", aptitude_resolver_cost_settings::maximized)),
+    priority_component(cost_settings.get_or_create_component("priority", aptitude_resolver_cost_settings::maximized));
+
+  // Resolve the component of each hint into a side table (since hints
+  // are supposed to be purely syntactic, it would be wrong to store
+  // the component there when we can look it up here with little
+  // cost).
+  std::vector<aptitude_resolver_cost_settings::component> hint_components;
+  for(std::vector<hint>::const_iterator it = hints.begin(); it != hints.end(); ++it)
+    {
+      switch(it->get_type())
+        {
+        case hint::add_to_cost_component:
+          hint_components.push_back(cost_settings.get_or_create_component(it->get_component_name(), aptitude_resolver_cost_settings::additive));
+          break;
+
+        case hint::raise_cost_component:
+          hint_components.push_back(cost_settings.get_or_create_component(it->get_component_name(), aptitude_resolver_cost_settings::maximized));
+          break;
+
+        default:
+          hint_components.push_back(aptitude_resolver_cost_settings::component());
+          break;
+        }
+    }
+
   // Should I stick with APT iterators instead?  This is a bit more
   // convenient, though..
   for(aptitude_universe::package_iterator pi = get_universe().packages_begin();
@@ -1262,6 +1304,21 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
 	      it != hints.end(); ++it)
 	    {
 	      const hint &h(*it);
+              const aptitude_resolver_cost_settings::component
+                &component = hint_components[it - hints.begin()];
+
+              // Bypass hints that are irrelevant.
+              switch(h.get_type())
+                {
+                case hint::add_to_cost_component:
+                case hint::raise_cost_component:
+                  if(!cost_settings.is_component_relevant(component))
+                    continue;
+                  break;
+
+                default:
+                  break;
+                }
 
 	      using aptitude::matching::get_match;
 
@@ -1290,8 +1347,13 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
 	      switch(h.get_type())
 		{
 		case hint::add_to_cost_component:
+                  LOG_DEBUG(loggerScores, "** Adding " << h.get_amt() << " to the cost component \"" << h.get_component_name() << "\" for " << v);
+                  modify_version_tier_op(v, cost_settings.add_to_cost(component, h.get_amt()));
+                  break;
+
 		case hint::raise_cost_component:
-		  LOG_ERROR(loggerScores, "This resolver hint type is not yet implemented.");
+                  LOG_DEBUG(loggerScores, "** Raising the cost component \"" << h.get_component_name() << "\" to " << h.get_amt() << " for " << v);
+                  modify_version_tier_op(v, cost_settings.raise_cost(component, h.get_amt()));
 		  break;
 
 		case hint::reject:
@@ -1316,6 +1378,19 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
 		}
 	    }
 
+          // We only raise the priority component if v is not the
+          // initial version of p, for two reasons: first and
+          // foremost, this was the old behavior, and I don't want to
+          // change the behavior of the code while I'm changing the
+          // mechanism used to set costs.  Less important but also a
+          // consideration: this is a small optimization (since
+          // there's no point in updating the tier operation of the
+          // initial version of a package).
+          if(v != initial_state.version_of(p))
+            modify_version_tier_op(v, raise_priority_op(cost_settings,
+                                                        v, policy,
+                                                        priority_component));
+
 	  // Remember, the initial version is the InstVer.
 	  if(v == initial_state.version_of(p))
 	    {
@@ -1350,11 +1425,10 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
 		  add_version_score(v, keep_score);
 		}
 
-	      tier_operation v_tier_op(specialize_tier_op(safe_tier_op, v.get_ver(), policy));
+              modify_version_tier_op(v, cost_settings.raise_cost(safety_component, safe_level));
 	      LOG_DEBUG(loggerTiers,
-			"** Tier op: " << v_tier_op << " for " << v
+			"** Tier level raised to at least " << safe_level << " for " << v
 			<< " because it is the currently installed version of a package  (" PACKAGE "::ProblemResolver::Safe-Tier)");
-	      modify_version_tier_op(v, v_tier_op);
 	    }
 	  else if(apt_ver.end())
 	    {
@@ -1367,11 +1441,10 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
 		  add_version_score(v, remove_score);
 		}
 
-	      tier_operation v_tier_op(specialize_tier_op(remove_tier_op, v.get_ver(), policy));
+              modify_version_tier_op(v, cost_settings.raise_cost(safety_component, remove_level));
 	      LOG_DEBUG(loggerTiers,
-			"** Tier op: " << v_tier_op << " for " << v
+			"** Tier level raised to at least " << remove_level << " for " << v
 			<< " because it represents the removal of a package (" PACKAGE "::ProblemResolver::Removal-Tier)");
-	      modify_version_tier_op(v, v_tier_op);
 	    }
 	  else if(apt_ver == (*cache)[p.get_pkg()].CandidateVerIter(*cache))
 	    {
@@ -1396,11 +1469,10 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
 		    }
 		}
 
-	      tier_operation v_tier_op(specialize_tier_op(safe_tier_op, v.get_ver(), policy));
+              modify_version_tier_op(v, cost_settings.raise_cost(safety_component, safe_level));
 	      LOG_DEBUG(loggerTiers,
-			"** Tier operation: " << v_tier_op << " for " << v
+			"** Tier level raised to at least " << safe_level << " for " << v
 			<< " because it is the default install version of a package (" PACKAGE "::ProblemResolver::Safe-Tier).");
-	      modify_version_tier_op(v, v_tier_op);
 	    }
 	  else
 	    // We know that:
@@ -1416,11 +1488,10 @@ 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_operation v_tier_op(specialize_tier_op(non_default_tier_op, v.get_ver(), policy));
+              modify_version_tier_op(v, cost_settings.raise_cost(safety_component, non_default_level));
 	      LOG_DEBUG(loggerTiers,
-			"** Tier op: " << v_tier_op << " for " << v
+			"** Tier level raised to at least " << non_default_level << " for " << v
 			<< " because it is a non-default version (" PACKAGE "::ProblemResolver::Non-Default-Tier).");
-	      modify_version_tier_op(v, v_tier_op);
 	    }
 
 	  // This logic is slightly duplicated in resolver_manger.cc,
@@ -1439,11 +1510,10 @@ void aptitude_resolver::add_action_scores(int preserve_score, int auto_score,
 		  reject_version(v);
 		}
 
-	      tier_operation v_tier_op(specialize_tier_op(break_hold_tier_op, v.get_ver(), policy));
+              modify_version_tier_op(v, cost_settings.raise_cost(safety_component, break_hold_level));
 	      LOG_DEBUG(loggerTiers,
-			"** Tier op: " << v_tier_op << " for " << v
+			"** Tier level raised to at least " << break_hold_level << " for " << v
 			<< " because it breaks a hold/forbid (" PACKAGE "::ProblemResolver::Break-Hold-Tier).");
-	      modify_version_tier_op(v, v_tier_op);
 	    }
 
 	  // In addition, add the essential-removal score:
@@ -1461,11 +1531,10 @@ 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_operation v_tier_op(specialize_tier_op(remove_essential_tier_op, v.get_ver(), policy));
+              modify_version_tier_op(v, cost_settings.raise_cost(safety_component, remove_essential_level));
 	      LOG_DEBUG(loggerTiers,
-			"** Tier op: " << v_tier_op << " for " << v
+			"** Tier level raised to at least " << remove_essential_level << " for " << v
 			<< " because it represents removing an essential package.");
-	      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 d970c3a9..c37e566d 100644
--- a/src/generic/apt/aptitude_resolver.h
+++ b/src/generic/apt/aptitude_resolver.h
@@ -25,6 +25,7 @@
 #ifndef APTITUDE_RESOLVER_H
 #define APTITUDE_RESOLVER_H
 
+#include "aptitude_resolver_cost_settings.h"
 #include "aptitude_resolver_universe.h"
 
 #include <generic/apt/matching/pattern.h>
@@ -64,6 +65,8 @@ class aptitude_resolver:public generic_problem_resolver<aptitude_universe>
   choice_set keep_all_solution;
   pkgPolicy *policy;
 
+  aptitude_resolver_cost_settings cost_settings;
+
   void add_full_replacement_score(const pkgCache::VerIterator &src,
 				  const pkgCache::PkgIterator &real_target,
 				  const pkgCache::VerIterator &provider,
@@ -288,7 +291,8 @@ public:
 
     hint(hint_type _type, int _amt,
 	 const cwidget::util::ref_ptr<aptitude::matching::pattern> &_target,
-	 version_selection _selection, const std::string &_component_name)
+	 version_selection _selection,
+         const std::string &_component_name)
       : type(_type), amt(_amt),
 	target(_target), selection(_selection), component_name()
     {
@@ -429,6 +433,7 @@ public:
 		    int infinity,
 		    int resolution_score,
 		    int future_horizon,
+		    const aptitude_resolver_cost_settings &_cost_settings,
 		    const imm::map<aptitude_resolver_package, aptitude_resolver_version> &initial_installations,
 		    aptitudeDepCache *cache,
 		    pkgPolicy *_policy);
diff --git a/src/generic/apt/aptitude_resolver_cost_settings.cc b/src/generic/apt/aptitude_resolver_cost_settings.cc
new file mode 100644
index 00000000..5fd30326
--- /dev/null
+++ b/src/generic/apt/aptitude_resolver_cost_settings.cc
@@ -0,0 +1,351 @@
+/** \file aptitude_resolver_cost_settings.cc */
+
+// Copyright (C) 2010 Daniel Burrows
+
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License as
+// published by the Free Software Foundation; either version 2 of the
+// License, or (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; see the file COPYING.  If not, write to
+// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+// Boston, MA 02111-1307, USA.
+
+#include "aptitude_resolver_cost_settings.h"
+
+
+#include "aptitude_resolver.h"
+#include "aptitude_resolver_cost_syntax.h"
+
+#include <boost/format.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+#include <boost/multi_index/random_access_index.hpp>
+#include <boost/optional.hpp>
+
+using namespace boost::multi_index;
+
+// This code acts as a frontend that interprets the cost language for
+// the resolver.  It type-checks costs to ensure that they don't go
+// wrong at "runtime", it drops costs that aren't used by the final
+// cost expression, and it pushes costs through to the components they
+// actually modify.  For instance, if the first cost component is
+// "removals + canceled-upgrades", any addition to "removals" or
+// "canceled-upgrades" will actually modify that level in the
+// resolver.
+
+class aptitude_resolver_cost_settings::settings_impl
+{
+  /** \brief Used to track the effect of a named component.
+   */
+  class component_effect
+  {
+    int id; // The component index.
+    int multiplier; // How much to multiply settings to this component
+                    // by.
+  public:
+    component_effect(int _id, int _multiplier)
+      : id(_id), multiplier(_multiplier)
+    {
+    }
+
+    int get_id() const { return id; }
+    int get_multiplier() const { return multiplier; }
+  };
+
+  class entry
+  {
+    std::string name;
+    // If the type doesn't have a value, it's because the component
+    // hasn't been seen in a typed context yet, so its type is
+    // "bottom".
+    boost::optional<component_type> type;
+    // The actual cost components that are modified by this entry.
+    std::vector<component_effect> effects;
+
+  public:
+    entry(const std::string &_name,
+          const boost::optional<component_type> &_type,
+          const std::vector<component_effect> &_effects)
+      : name(_name),
+        type(_type),
+        effects(_effects)
+    {
+    }
+
+    const std::string &get_name() const { return name; }
+    const boost::optional<component_type> &get_type() const { return type; }
+    void set_type(const boost::optional<component_type> &new_type)
+    {
+      type = new_type;
+    }
+    const std::vector<component_effect> &get_effects() const { return effects; }
+    std::vector<component_effect> &get_effects() { return effects; }
+  };
+
+  // Modifying functor used to add an effect to an entry.
+  class add_effect_f
+  {
+    component_effect new_effect;
+  public:
+    add_effect_f(const component_effect &_new_effect)
+      : new_effect(_new_effect)
+    {
+    }
+
+    void operator()(entry &e) const
+    {
+      e.get_effects().push_back(new_effect);
+    }
+  };
+
+  // Combine the target value's component type with the incoming type,
+  // throwing an error if they're incompatible.
+  class merge_types_f
+  {
+    boost::optional<component_type> type;
+    std::string name;
+
+  public:
+    merge_types_f(const boost::optional<component_type> &_type)
+      : type(_type)
+    {
+    }
+
+    void operator()(entry &e) const
+    {
+      if(type)
+        {
+          if(!e.get_type())
+            e.set_type(type);
+          else if(type != e.get_type())
+            throw CostTypeCheckFailure((boost::format(_("Conflicting types for the cost component %s."))
+                                        % e.get_name()).str());
+        }
+    }
+  };
+
+  // Tags for the entry holder.
+  class name_t;
+  class ordered_t;
+
+  typedef multi_index_container<
+    entry,
+    indexed_by<
+      random_access<tag<ordered_t> >,
+      hashed_unique<tag<name_t>,
+                    const_mem_fun<entry,
+                                  const std::string &,
+                                  &entry::get_name> > > >
+  entry_holder;
+
+  typedef entry_holder::index<name_t>::type by_name_index;
+  typedef entry_holder::index<ordered_t>::type ordered_index;
+
+  entry_holder entries;
+
+  boost::shared_ptr<std::vector<cost_component_structure> > settings;
+
+public:
+  explicit settings_impl(const boost::shared_ptr<std::vector<cost_component_structure> > &_settings)
+    : settings(_settings)
+  {
+    // Every time a cost component is named in the given settings
+    // object, we look it up (creating it if it doesn't exist), check
+    // that it has the appropriate type, and link it to the
+    // corresponding entry in this object.
+
+    by_name_index &by_name = entries.get<name_t>();
+    ordered_index &ordered = entries.get<ordered_t>();
+
+    int component_idx = 0;
+    for(std::vector<cost_component_structure>::const_iterator
+          settings_it = settings->begin(); settings_it != settings->end(); ++settings_it)
+      {
+        cost_component_structure::op op = settings_it->get_combining_op();
+        std::vector<cost_component_structure::entry> &component =
+          *settings_it->get_entries();
+
+        boost::optional<component_type> type;
+        switch(op)
+          {
+          case cost_component_structure::combine_add:
+            type = additive;
+            break;
+
+          case cost_component_structure::combine_max:
+            type = maximized;
+            break;
+
+          case cost_component_structure::combine_none:
+            type = boost::optional<component_type>();
+            break;
+
+          default:
+            throw CostTypeCheckFailure("Internal error: invalid cost component operation code.");
+          }
+
+        for(std::vector<cost_component_structure::entry>::const_iterator
+              component_it = component.begin(); component_it != component.end(); ++component_it)
+          {
+            // Unpack this piece of the component.
+            const std::string &name = component_it->get_name();
+            int scaling_factor = component_it->get_scaling_factor();
+
+            component_effect effect(component_idx, scaling_factor);
+
+            by_name_index::iterator found = by_name.find(name);
+            if(found == by_name.end())
+              {
+                std::vector<component_effect> effects;
+                effects.push_back(effect);
+
+                ordered.push_back(entry(name, type, effects));
+              }
+            else
+              {
+                by_name.modify(found, merge_types_f(type));
+                by_name.modify(found, add_effect_f(effect));
+              }
+          }
+
+        ++component_idx;
+      }
+  }
+
+  component get_or_create_component(const std::string &name,
+                                    component_type type)
+  {
+    // Look the component up by name.  If it doesn't exist, we can go
+    // ahead and create it.  If it does exist, we need to check that
+    // the types match.  In either case, if no "real" cost component
+    // is affected by the named component, a component ID of -1 is
+    // returned (indicating that the component has no real effect).
+
+    by_name_index &by_name = entries.get<name_t>();
+    by_name_index::iterator found = by_name.find(name);
+
+    if(found == by_name.end())
+      {
+        by_name.insert(entry(name, type, std::vector<component_effect>()));
+        return component(-1);
+      }
+    else
+      {
+        ordered_index &ordered = entries.get<ordered_t>();
+        ordered_index::iterator found_ordered = entries.project<ordered_t>(found);
+        component rval(found->get_effects().empty() ? -1 : found_ordered - ordered.begin());
+
+        by_name.modify(found, merge_types_f(type));
+
+        return rval;
+      }
+  }
+
+  tier_operation add_to_cost(const component &component,
+                             int amt)
+  {
+    // Ignore irrelevant components.
+    if(component.id < 0)
+      return tier_operation();
+
+    // Sanity-check that the component's type is additive, then add
+    // the given value to each target cost component.
+
+    ordered_index &ordered = entries.get<ordered_t>();
+
+    if((unsigned int)component.id >= ordered.size())
+      throw CostTypeCheckFailure("Internal error: mismatch between component ID and the number of components.");
+
+    ordered.modify(ordered.begin() + component.id, merge_types_f(additive));
+
+    const entry &e = ordered[component.id];
+    tier_operation rval;
+    for(std::vector<component_effect>::const_iterator it = e.get_effects().begin();
+        it != e.get_effects().end(); ++it)
+      {
+        tier_operation op =
+          tier_operation::make_add_to_user_level(it->get_id(), amt * it->get_multiplier());
+
+        rval = rval + op;
+      }
+
+    return rval;
+  }
+
+  tier_operation raise_cost(const component &component,
+                            int amt)
+  {
+    // Ignore irrelevant components.
+    if(component.id < 0)
+      return tier_operation();
+
+    // Sanity-check that the component's type is additive, then add
+    // the given value to each target cost component.
+
+    ordered_index &ordered = entries.get<ordered_t>();
+
+    if((unsigned int)component.id >= ordered.size())
+      throw CostTypeCheckFailure("Internal error: mismatch between component ID and the number of components.");
+
+    ordered.modify(ordered.begin() + component.id, merge_types_f(maximized));
+
+    tier_operation rval;
+    const entry &e = ordered[component.id];
+    for(std::vector<component_effect>::const_iterator it = e.get_effects().begin();
+        it != e.get_effects().end(); ++it)
+      {
+        tier_operation op =
+          tier_operation::make_advance_user_level(it->get_id(), amt * it->get_multiplier());
+
+        rval = rval + op;
+      }
+
+    return rval;
+  }
+
+  void dump(std::ostream &out) const
+  {
+    dump_settings(out, settings);
+  }
+};
+
+aptitude_resolver_cost_settings::aptitude_resolver_cost_settings(const boost::shared_ptr<std::vector<cost_component_structure> > &settings)
+  : impl(new settings_impl(settings))
+{
+}
+
+aptitude_resolver_cost_settings::~aptitude_resolver_cost_settings()
+{
+}
+
+void aptitude_resolver_cost_settings::dump(std::ostream &out) const
+{
+  impl->dump(out);
+}
+
+aptitude_resolver_cost_settings::component
+aptitude_resolver_cost_settings::get_or_create_component(const std::string &name,
+                                                         component_type type)
+{
+  return impl->get_or_create_component(name, type);
+}
+
+tier_operation aptitude_resolver_cost_settings::add_to_cost(const component &component,
+                                                            int amt)
+{
+  return impl->add_to_cost(component, amt);
+}
+
+tier_operation aptitude_resolver_cost_settings::raise_cost(const component &component,
+                                                           int amt)
+{
+  return impl->raise_cost(component, amt);
+}
diff --git a/src/generic/apt/aptitude_resolver_cost_settings.h b/src/generic/apt/aptitude_resolver_cost_settings.h
new file mode 100644
index 00000000..d506e928
--- /dev/null
+++ b/src/generic/apt/aptitude_resolver_cost_settings.h
@@ -0,0 +1,163 @@
+/** \file aptitude_resolver_cost_settings.h */ // -*-c++
+
+
+// Copyright (C) 2010 Daniel Burrows
+
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License as
+// published by the Free Software Foundation; either version 2 of the
+// License, or (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; see the file COPYING.  If not, write to
+// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+// Boston, MA 02111-1307, USA.
+
+#ifndef APTITUDE_RESOLVER_COST_SETTINGS_H
+#define APTITUDE_RESOLVER_COST_SETTINGS_H
+
+#include "aptitude_resolver_cost_types.h"
+
+#include <generic/problemresolver/tier_operation.h>
+
+#include <boost/shared_ptr.hpp>
+#include <vector>
+
+class aptitude_resolver;
+class aptitude_resolver_version;
+
+/** \brief Core data structure for keeping track of which cost
+ *  components are active and how they interact.
+ *
+ *  Only active cost components have their costs actually registered
+ *  in the resolver.  Also, this class knows how to parse and
+ *  serialize the set of registered components.
+ */
+class aptitude_resolver_cost_settings
+{
+  // Hide the implementation.
+  class settings_impl;
+
+  boost::shared_ptr<settings_impl> impl;
+public:
+  /** \brief Reference to a single cost component.
+   *
+   *  Used to avoid unnecessary string lookups.
+   */
+  class component
+  {
+    // I use an integer instead of an iterator to avoid forcing every
+    // other module to know the type of this object's internal
+    // container.
+    //
+    // Note: internally, -1 is used to indicate that a component
+    // doesn't affect any component of the resolver's cost structure.
+    // These components are *also* stored in the settings object, to
+    // ensure that they're used consistently, but they have no effect
+    // on any resolver cost.
+    int id;
+
+    friend class aptitude_resolver_cost_settings;
+
+    component(int _id)
+      : id(_id)
+    {
+    }
+
+  public:
+    component()
+      : id(-1)
+    {
+    }
+
+    component(const component &other)
+      : id(other.id)
+    {
+    }
+
+    component &operator=(const component &other)
+    {
+      id = other.id;
+      return *this;
+    }
+
+    // I don't implement a full complement of comparison / hash
+    // operators because they aren't needed yet.
+  };
+
+  /** \brief Possible cost component types. */
+  enum component_type
+    {
+      /** \brief The type of components that can be added together. */
+      additive,
+      /** \brief The type of components that can be increased stepwise
+       *         via max().
+       */
+      maximized
+    };
+
+  /** \brief Validate the given cost settings and construct a cost
+   *  settings object from it.
+   *
+   *  \param settings  The components of the cost.
+   */
+  explicit aptitude_resolver_cost_settings(const boost::shared_ptr<std::vector<cost_component_structure> > &settings);
+  ~aptitude_resolver_cost_settings();
+
+  /** \brief Test whether the given component is relevant to the cost
+   *  settings.
+   *
+   *  If this returns \b false, then modifying this component has no
+   *  effect; can be used to short-circuit some matching logic.
+   */
+  bool is_component_relevant(const component &component) const
+  {
+    return component.id >= 0;
+  }
+
+  /** \brief Write these settings to an ostream. */
+  void dump(std::ostream &out) const;
+
+  /** \brief Get or create a cost component.
+   *
+   *  \param name  The string that the returned component
+   *               is bound to.
+   *  \param type  The type of the returned component.
+   *
+   *  \throws CostTypeCheckFailure if this component has already been
+   *  instantiated with an incompatible type.
+   *
+   *  \note this may modify the type of an existing component if its
+   *  type couldn't be inferred from the cost settings string.
+   */
+  component get_or_create_component(const std::string &name,
+				    component_type type);
+
+  /** \brief Get a tier operation that adds a value to a cost component.
+   *
+   *  The cost component must have type "additive".
+   */
+  tier_operation add_to_cost(const component &component,
+                             int amt);
+
+  /** \brief Get a tier operation that raises a cost component to an
+   *  upper bound.
+   *
+   *  The cost component must have type "maximized".
+   */
+  tier_operation raise_cost(const component &component,
+                            int amt);
+};
+
+inline std::ostream &operator<<(std::ostream &out, const aptitude_resolver_cost_settings &settings)
+{
+  settings.dump(out);
+  return out;
+}
+
+#endif // APTITUDE_RESOLVER_COST_SETTINGS_H
diff --git a/src/generic/apt/aptitude_resolver_cost_syntax.cc b/src/generic/apt/aptitude_resolver_cost_syntax.cc
new file mode 100644
index 00000000..8a5fb040
--- /dev/null
+++ b/src/generic/apt/aptitude_resolver_cost_syntax.cc
@@ -0,0 +1,80 @@
+/** \file aptitude_resolver_cost_syntax.cc */
+
+
+// Copyright (C) 2010 Daniel Burrows
+
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License as
+// published by the Free Software Foundation; either version 2 of the
+// License, or (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; see the file COPYING.  If not, write to
+// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+// Boston, MA 02111-1307, USA.
+
+#include "aptitude_resolver_cost_syntax.h"
+
+#include <ostream>
+
+void dump_settings(std::ostream &out, const boost::shared_ptr<std::vector<cost_component_structure> > &settings)
+{
+  bool first_component = true;
+  for(std::vector<cost_component_structure>::const_iterator
+        settings_it = settings->begin(); settings_it != settings->end(); ++settings_it)
+    {
+      const std::vector<cost_component_structure::entry> &entries =
+        *settings_it->get_entries();
+
+      if(entries.empty())
+        continue;
+
+      if(first_component)
+        first_component = false;
+      else
+        out << ", ";
+
+      if(settings_it->get_combining_op() == cost_component_structure::combine_max)
+        out << "max(";
+
+      bool first_entry = true;
+      for(std::vector<cost_component_structure::entry>::const_iterator
+            entries_it = entries.begin(); entries_it != entries.end();
+          ++entries_it)
+        {
+          if(entries_it->get_scaling_factor() == 0)
+            continue;
+
+          if(first_entry)
+            first_entry = false;
+          else switch(settings_it->get_combining_op())
+                 {
+                 case cost_component_structure::combine_add:
+                   out << " + ";
+                   break;
+
+                 case cost_component_structure::combine_max:
+                   out << ", ";
+                   break;
+
+                 default:
+                   // Should never happen.
+                   out << " ";
+                   break;
+                 }
+
+          if(entries_it->get_scaling_factor() != 1)
+            out << entries_it->get_scaling_factor() << "*";
+          out << entries_it->get_name();
+        }
+
+      if(settings_it->get_combining_op() == cost_component_structure::combine_max)
+        out << ")";
+    }
+}
+
diff --git a/src/generic/apt/aptitude_resolver_cost_syntax.h b/src/generic/apt/aptitude_resolver_cost_syntax.h
new file mode 100644
index 00000000..cbe99731
--- /dev/null
+++ b/src/generic/apt/aptitude_resolver_cost_syntax.h
@@ -0,0 +1,43 @@
+/** \file aptitude_resolver_cost_syntax.h */     // -*-c++-*-
+
+// Copyright (C) 2010 Daniel Burrows
+
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License as
+// published by the Free Software Foundation; either version 2 of the
+// License, or (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; see the file COPYING.  If not, write to
+// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+// Boston, MA 02111-1307, USA.
+
+#ifndef APTITUDE_RESOLVER_COST_SYNTAX_H
+#define APTITUDE_RESOLVER_COST_SYNTAX_H
+
+#include "aptitude_resolver_cost_types.h"
+
+#include <boost/shared_ptr.hpp>
+#include <vector>
+
+/** \brief Parse a settings string.
+ *
+ *  Throws a cwidget::util::Exception if parsing failed.
+ */
+boost::shared_ptr<std::vector<cost_component_structure> >
+parse_cost_settings(const std::string settings);
+
+/** \brief Write some settings to a stream.
+ *
+ *  This is the inverse of parse_cost_settings.
+ */
+void dump_settings(std::ostream &out, const boost::shared_ptr<std::vector<cost_component_structure> > &settings);
+
+
+#endif // APTITUDE_RESOLVER_COST_SYNTAX_H
+
diff --git a/src/generic/apt/aptitude_resolver_cost_types.h b/src/generic/apt/aptitude_resolver_cost_types.h
new file mode 100644
index 00000000..95099a58
--- /dev/null
+++ b/src/generic/apt/aptitude_resolver_cost_types.h
@@ -0,0 +1,126 @@
+/** \file aptitude_resolver_cost_types.h */   // -*-c++-*-
+
+
+// Copyright (C) 2010 Daniel Burrows
+
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License as
+// published by the Free Software Foundation; either version 2 of the
+// License, or (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; see the file COPYING.  If not, write to
+// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+// Boston, MA 02111-1307, USA.
+
+#ifndef APTITUDE_RESOLVER_COST_TYPES_H
+#define APTITUDE_RESOLVER_COST_TYPES_H
+
+#include <boost/shared_ptr.hpp>
+
+#include <cwidget/generic/util/exception.h>
+
+#include <string>
+
+class CostTypeCheckFailure : public cwidget::util::Exception
+{
+  std::string msg;
+
+public:
+  CostTypeCheckFailure(const std::string &_msg)
+    : msg(_msg)
+  {
+  }
+
+  std::string errmsg() const { return msg; }
+};
+
+/** \brief A representation of the syntactic structure of a single
+ *  cost component.
+ *
+ *  Could be used to round-trip cost definitions between a settings
+ *  object and the GUI.
+ *
+ *  Each cost component is a list of sub-components combined with
+ *  either max() or "+".  Sub-components can be multiplied by a
+ *  scaling factor.
+ */
+class cost_component_structure
+{
+public:
+  /** \brief The operator used to combine sub-components. */
+  enum op
+    {
+      /** \brief Combine sub-components with "+". */
+      combine_add,
+
+      /** \brief Combine sub-components with "max()". */
+      combine_max,
+
+      /** \brief Sub-components can't be combined.
+       *
+       *  Corresponds to a situation where there is only one
+       *  sub-component, so there isn't a combining operation that we
+       *  could use to infer the sub-component's type.  It is an error
+       *  to have more than one sub-component in this case.
+       */
+      combine_none,
+    };
+
+  /** \brief Represents one entry in the cost component. */
+  class entry
+  {
+    std::string name;
+    int scaling_factor;
+
+  public:
+    entry(const std::string &_name, int _scaling_factor)
+      : name(_name),
+        scaling_factor(_scaling_factor)
+    {
+    }
+
+    const std::string &get_name() const { return name; }
+    int get_scaling_factor() const { return scaling_factor; }
+  };
+
+private:
+  op combining_op;
+  boost::shared_ptr<std::vector<entry> > entries;
+
+public:
+  cost_component_structure(op _combining_op,
+                           const std::vector<entry> &_entries)
+    : combining_op(_combining_op),
+      entries(new std::vector<entry>(_entries))
+  {
+  }
+
+  template<typename Iter>
+  cost_component_structure(op _combining_op, Iter begin, Iter end)
+    : combining_op(_combining_op),
+      entries(new std::vector<entry>(begin, end))
+  {
+  }
+
+  /** \brief Retrieve the operation used to combine the entries of
+   *  this component.
+   */
+  op get_combining_op() const
+  {
+    return combining_op;
+  }
+
+  /** \brief Retrieve the entries of this component. */
+  const boost::shared_ptr<std::vector<entry> > &get_entries() const
+  {
+    return entries;
+  }
+};
+
+#endif // APTITUDE_RESOLVER_COST_TYPES_H
diff --git a/src/generic/apt/aptitude_resolver_universe.cc b/src/generic/apt/aptitude_resolver_universe.cc
index 24e1a409..d3d85d01 100644
--- a/src/generic/apt/aptitude_resolver_universe.cc
+++ b/src/generic/apt/aptitude_resolver_universe.cc
@@ -830,34 +830,34 @@ int aptitude_universe::parse_level(const std::string &s)
     }
 }
 
-tier_operation aptitude_universe::get_safe_tier_op()
+int aptitude_universe::get_safe_level()
 {
-  return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Safe-Tier", "10000")));
+  return parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Safe-Tier", "10000"));
 }
 
-tier_operation aptitude_universe::get_keep_all_tier_op()
+int aptitude_universe::get_keep_all_level()
 {
-  return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Keep-All-Tier", "20000")));
+  return parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Keep-All-Tier", "20000"));
 }
 
-tier_operation aptitude_universe::get_remove_tier_op()
+int aptitude_universe::get_remove_level()
 {
-  return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Tier", "10000")));
+  return parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Tier", "10000"));
 }
 
-tier_operation aptitude_universe::get_break_hold_tier_op()
+int aptitude_universe::get_break_hold_level()
 {
-  return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Break-Hold-Tier", "40000")));
+  return parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Break-Hold-Tier", "40000"));
 }
 
-tier_operation aptitude_universe::get_non_default_tier_op()
+int aptitude_universe::get_non_default_level()
 {
-  return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Non-Default-Tier", "50000")));
+  return parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Non-Default-Tier", "50000"));
 }
 
-tier_operation aptitude_universe::get_remove_essential_tier_op()
+int aptitude_universe::get_remove_essential_level()
 {
-  return tier_operation::make_advance_user_level(0, parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Essential-Tier", "60000")));
+  return parse_level(aptcfg->Find(PACKAGE "::ProblemResolver::Remove-Essential-Tier", "60000"));
 }
 
 bool aptitude_universe::is_candidate_for_initial_set(const aptitude_resolver_dep &d) const
diff --git a/src/generic/apt/aptitude_resolver_universe.h b/src/generic/apt/aptitude_resolver_universe.h
index 04ec87ac..c29451c1 100644
--- a/src/generic/apt/aptitude_resolver_universe.h
+++ b/src/generic/apt/aptitude_resolver_universe.h
@@ -1303,12 +1303,12 @@ public:
   static int parse_level(const std::string &s);
 
   // Configuration fetchers.
-  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();
+  static int get_safe_level();
+  static int get_keep_all_level();
+  static int get_remove_level();
+  static int get_break_hold_level();
+  static int get_non_default_level();
+  static int get_remove_essential_level();
 };
 
 /** \brief Write an aptitude_resolver_package to the given stream. */
diff --git a/src/generic/apt/resolver_manager.cc b/src/generic/apt/resolver_manager.cc
index 1ea2d3ac..597887cf 100644
--- a/src/generic/apt/resolver_manager.cc
+++ b/src/generic/apt/resolver_manager.cc
@@ -22,6 +22,7 @@
 #include <aptitude.h>
 #include "apt.h"
 #include "aptitude_resolver.h"
+#include "aptitude_resolver_cost_settings.h"
 #include "aptitude_resolver_universe.h"
 #include "config_signal.h"
 #include "dump_packages.h"
@@ -892,12 +893,31 @@ void resolver_manager::create_resolver()
   // resolver will actually remove packages rather than leaving their
   // Recommends: field unsatisfied!
 
+
+
+  // TODO: this should be parsed from a configuration setting.  This
+  // hardcoding is just a placeholder until I write the parser code.
+  boost::shared_ptr<std::vector<cost_component_structure> > cost_components(new std::vector<cost_component_structure>);
+
+  std::vector<cost_component_structure::entry> level0;
+  level0.push_back(cost_component_structure::entry("safety", 1));
+  cost_components->push_back(cost_component_structure(cost_component_structure::combine_none, level0));
+
+  std::vector<cost_component_structure::entry> level1;
+  level1.push_back(cost_component_structure::entry("priority", 1));
+  cost_components->push_back(cost_component_structure(cost_component_structure::combine_none, level1));
+
+  aptitude_resolver_cost_settings cost_settings(cost_components);
+
+
+
   resolver=new aptitude_resolver(aptcfg->FindI(PACKAGE "::ProblemResolver::StepScore", 70),
 				 aptcfg->FindI(PACKAGE "::ProblemResolver::BrokenScore", -100),
 				 aptcfg->FindI(PACKAGE "::ProblemResolver::UnfixedSoftScore", -200),
 				 aptcfg->FindI(PACKAGE "::ProblemResolver::Infinity", 1000000),
 				 aptcfg->FindI(PACKAGE "::ProblemResolver::ResolutionScore", 50),
 				 aptcfg->FindI(PACKAGE "::ProblemResolver::FutureHorizon", 50),
+                                 cost_settings,
 				 initial_installations,
 				 (*cache_file),
 				 cache_file->Policy);