Add support for "dependency-scoped" install-version choices, which match the same install as long as it was done for the same dependency, and use them to inject promotions related to approval user constraints.

Approvals are violated by search steps that choose a different solution
to a dependency than the approved one.  So to represent these in the
condition of a promotion, we have to be able to match installing a
particular version *but only if the install was for a particular dep*.

In other words, install_version choices now have four levels of
specificity:

  (no dep) -> (unscoped) -> (dep-scoped) -> (from-dep-source)

Choices with no dep "contain" any other choice that installs the same
version, and so do choices that are unscoped (but have a dep).  Choices
that are dep-scoped "contain" choices that have the same dep (so no-dep
choices are out, but some unscoped choices can match).  Choices in the
from-dep-source category "contain" choices that have the same dep and
that are also from-dep-source.

This commit adds the code necessary to represent these extra types
of choices, to manipulate them in the resolver, and to parse them in
the log analyzer.  It also uses these new abilities to generate
promotions to the "defer" tier when successors violate a user
constraint.

14 files changed, 253 insertions, 97 deletions

diff --git a/src/generic/apt/aptitude_resolver.cc b/src/generic/apt/aptitude_resolver.cc
index c7bfcb04..e28944d9 100644
--- a/src/generic/apt/aptitude_resolver.cc
+++ b/src/generic/apt/aptitude_resolver.cc
@@ -688,7 +688,7 @@ aptitude_resolver::aptitude_resolver(int step_score,
 
       if(get_initial_state().version_of(p) == curr)
 	{
-	  choice c(choice::make_install_version(curr, dep(), 0));
+	  choice c(choice::make_install_version(curr, 0));
 	  keep_all_solution.insert_or_narrow(c);
 	}
     }
diff --git a/src/generic/problemresolver/choice.h b/src/generic/problemresolver/choice.h
index 688a9ed3..61f6c17b 100644
--- a/src/generic/problemresolver/choice.h
+++ b/src/generic/problemresolver/choice.h
@@ -65,36 +65,44 @@ private:
   // The dependency, if any, associated with this choice.
   //
   // Meaningful for install_version choices and for break_soft_dep
-  // choices.  If type is install_version and from_dep_source is set,
-  // this is part of the "identity" of this object (so it will be used
-  // in equality comparisons, contains() checks, etc); all other
-  // install_version choices include it only for informational
-  // purposes.
+  // choices.  This is part of the "identity" of this object (so it
+  // will be used in equality comparisons).  Normally this is ignored
+  // by "contains" checks, but if one of the choices is
+  // dependency-scoped, it can matter.
   dep d;
 
   // True if the choice was to remove the source of the dependency.
   bool from_dep_source:1;
 
+  // True if the dependency is part of the "identity" of the choice
+  // object.  These dependencies are more specific than choices
+  // without dep scoping and less specific than choices with
+  // from_dep_source set.
+  bool dep_scoped:1;
+
+  // True if the choice *has* an attached dependency at all.
+  bool has_dep:1;
+
   // The type of this choice object.
   type tp:1;
 
   /** \brief The order in which this choice was made.
    */
-  int id:30;
+  int id:28;
 
-  generic_choice(const version &_ver, bool _from_dep_source, const dep &_d, int _id)
-    : ver(_ver), d(_d), from_dep_source(_from_dep_source), tp(install_version), id(_id)
+  generic_choice(const version &_ver, bool _from_dep_source, bool _dep_scoped, bool _has_dep, const dep &_d, int _id)
+    : ver(_ver), d(_d), from_dep_source(_from_dep_source), dep_scoped(_dep_scoped), has_dep(_has_dep), tp(install_version), id(_id)
   {
   }
 
   generic_choice(const dep &_d, int _id)
-    : d(_d), from_dep_source(false), tp(break_soft_dep), id(_id)
+    : d(_d), from_dep_source(false), dep_scoped(true), has_dep(true), tp(break_soft_dep), id(_id)
   {
   }
 
 public:
   generic_choice()
-    : from_dep_source(false), tp(install_version), id(-1)
+    : from_dep_source(false), dep_scoped(false), has_dep(false), tp(install_version), id(-1)
   {
   }
 
@@ -104,12 +112,31 @@ public:
    *  \param d   The dependency that caused this choice.  This is
    *             included for informational purposes only and is
    *             ignored by all operations except get_dep().
+   *  \param dep_scoped   True if this choice only "contains"
+   *                      choices with the same dependency.
    *  \param id  An arbitrary integer associated with this choice.
    *             Ignored by all operations except get_id().
    */
-  static generic_choice make_install_version(const version &ver, const dep &d, int id)
+  static generic_choice make_install_version(const version &ver, bool dep_scoped, const dep &d, int id)
   {
-    return generic_choice(ver, false, d, id);
+    return generic_choice(ver, false, dep_scoped, true, d, id);
+  }
+
+  /** \brief Create a new choice that installs the given version and
+   *  has no attached dependency.
+   *
+   *  \param ver The version that is installed by this choice.
+   *  \param d   The dependency that caused this choice.  This is
+   *             included for informational purposes only and is
+   *             ignored by all operations except get_dep().
+   *  \param dep_scoped   True if this choice only "contains" choices
+   *                      with the same dependency.
+   *  \param id  An arbitrary integer associated with this choice.
+   *             Ignored by all operations except get_id().
+   */
+  static generic_choice make_install_version(const version &ver, int id)
+  {
+    return generic_choice(ver, false, false, false, dep(), id);
   }
 
   /** \brief Create a new choice that installs the given version to
@@ -123,7 +150,7 @@ public:
    */
   static generic_choice make_install_version_from_dep_source(const version &ver, const dep &d, int id)
   {
-    return generic_choice(ver, true, d, id);
+    return generic_choice(ver, true, true, true, d, id);
   }
 
   /** \brief Create a new choice that leaves the given soft dependency
@@ -156,10 +183,16 @@ public:
 	    return false;
 	  else // ver == other.ver
 	    {
-	      if(!from_dep_source)
+	      if(!dep_scoped)
 		return true;
+	      else if(from_dep_source && !other.from_dep_source)
+		return false;
+	      else if(!has_dep && other.has_dep)
+		return true;
+	      else if(has_dep && !other.has_dep)
+		return false;
 	      else
-		return other.from_dep_source && d == other.d;
+		return d == other.d;
 	    }
 
 	case break_soft_dep:
@@ -191,12 +224,20 @@ public:
 	      return false;
 	    else
 	      {
-		if(!from_dep_source && other.from_dep_source)
+		if(!dep_scoped && other.dep_scoped)
+		  return true;
+		else if(dep_scoped && !other.dep_scoped)
+		  return false;
+		else if(!from_dep_source && other.from_dep_source)
 		  return true;
 		else if(from_dep_source && !other.from_dep_source)
 		  return false;
-		else if(!from_dep_source)
-		  return false; // They are equal.
+		else if(!has_dep && other.has_dep)
+		  return true;
+		else if(has_dep && !other.has_dep)
+		  return false;
+		else if(!has_dep)
+		  return false;
 		else
 		  return d < other.d;
 	      }
@@ -225,7 +266,13 @@ public:
 	    if(from_dep_source != other.from_dep_source)
 	      return false;
 
-	    if(!from_dep_source)
+	    if(dep_scoped != other.dep_scoped)
+	      return false;
+
+	    if(has_dep != other.has_dep)
+	      return false;
+
+	    if(!has_dep)
 	      return true;
 	    else
 	      return d == other.d;
@@ -248,12 +295,24 @@ public:
     return ver;
   }
 
+  bool get_dep_scoped() const
+  {
+    eassert(tp == install_version);
+    return dep_scoped;
+  }
+
   bool get_from_dep_source() const
   {
     eassert(tp == install_version);
     return from_dep_source;
   }
 
+  bool get_has_dep() const
+  {
+    eassert(tp == install_version);
+    return has_dep;
+  }
+
   const dep &get_dep() const
   {
     return d;
@@ -267,10 +326,19 @@ inline std::ostream &operator<<(std::ostream &out, const generic_choice<PackageU
     {
     case generic_choice<PackageUniverse>::install_version:
       out << "Install(" << choice.get_ver();
-      if(choice.get_from_dep_source())
-	return out << " [" << choice.get_dep() << "])";
+      if(!choice.get_has_dep())
+	{
+	  out << ")";
+	  return out;
+	}
+      else if(choice.get_from_dep_source())
+	out << " <source: ";
+      else if(choice.get_dep_scoped())
+	out << " <scope: ";
       else
-	return out << ")";
+	out << " <";
+
+      return out << choice.get_dep() << ">)";
 
     case generic_choice<PackageUniverse>::break_soft_dep:
       return out << "Break(" << choice.get_dep() << ")";
diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h
index 584903e2..07e20e40 100644
--- a/src/generic/problemresolver/problemresolver.h
+++ b/src/generic/problemresolver/problemresolver.h
@@ -1992,7 +1992,7 @@ private:
       switch(c.get_type())
 	{
 	case choice::install_version:
-	  rval.insert_or_narrow(choice::make_install_version(c.get_ver(), c.get_dep(), c.get_id()));
+	  rval.insert_or_narrow(choice::make_install_version(c.get_ver(), false, c.get_dep(), c.get_id()));
 	  break;
 
 	case choice::break_soft_dep:
@@ -2095,6 +2095,7 @@ private:
     const std::set<dep> &hardened_deps;
     const std::set<dep> &approved_broken_deps;
     const resolver_initial_state<PackageUniverse> &initial_state;
+    choice_set &reasons;
     log4cxx::LoggerPtr logger;
 
     choice_does_not_break_user_constraint(const std::set<version> &_rejected_versions,
@@ -2102,12 +2103,14 @@ private:
 					  const std::set<dep> &_hardened_deps,
 					  const std::set<dep> &_approved_broken_deps,
 					  const resolver_initial_state<PackageUniverse> &_initial_state,
+					  choice_set &_reasons,
 					  const log4cxx::LoggerPtr &_logger)
       : rejected_versions(_rejected_versions),
 	mandated_versions(_mandated_versions),
 	hardened_deps(_hardened_deps),
 	approved_broken_deps(_approved_broken_deps),
 	initial_state(_initial_state),
+	reasons(_reasons),
 	logger(_logger)
     {
     }
@@ -2137,6 +2140,7 @@ private:
 	    if(rejected_versions.find(ver) != rejected_versions.end())
 	      {
 		LOG_TRACE(logger, c << " is rejected: it installs the rejected version " << ver);
+		reasons.insert_or_narrow(choice::make_install_version(c.get_ver(), c.get_id()));
 		return false;
 	      }
 
@@ -2153,6 +2157,7 @@ private:
 	    if(hardened_deps.find(d) != hardened_deps.end())
 	      {
 		LOG_TRACE(logger, c << " is rejected: it breaks the hardened soft dependency " << d);
+		reasons.insert_or_narrow(choice::make_break_soft_dep(c.get_dep(), c.get_id()));
 		return false;
 	      }
 
@@ -2198,6 +2203,8 @@ private:
 		      {
 			LOG_TRACE(logger, c << " avoids installing the mandated version "
 				  << alternate << " to solve the dependency " << d);
+			reasons.insert_or_narrow(choice::make_install_version(chosen,
+									      true, d, c.get_id()));
 			return false;
 		      }
 		  }
@@ -2216,6 +2223,8 @@ private:
 		      {
 			LOG_TRACE(logger, c << " avoids installing the mandated version "
 				  << solver << " to solve the dependency " << d);
+			reasons.insert_or_narrow(choice::make_install_version(chosen,
+									      true, d, c.get_id()));
 			return false;
 		      }
 		  }
@@ -2250,6 +2259,7 @@ private:
 		      {
 			LOG_TRACE(logger, c << " solves the soft dependency " << rd
 				  << " which was mandated to be broken.");
+			reasons.insert_or_narrow(choice::make_install_version(chosen, true, d, c.get_id()));
 			return false;
 		      }
 		  }
@@ -2267,6 +2277,7 @@ private:
 		      {
 			LOG_TRACE(logger, c << " solves the soft dependency " << rd
 				  << " which was mandated to be broken.");
+			reasons.insert_or_narrow(choice::make_install_version(chosen, true, d, c.get_id()));
 			return false;
 		      }
 		  }
@@ -2294,6 +2305,7 @@ private:
 		   mandated_versions.find(alternate) != mandated_versions.end())
 		  {
 		    LOG_TRACE(logger, c << " fails to install the mandated version " << alternate);
+		    reasons.insert_or_narrow(choice::make_break_soft_dep(d, c.get_id()));
 		    return false;
 		  }
 	      }
@@ -2306,6 +2318,7 @@ private:
 		if(mandated_versions.find(solver) != mandated_versions.end())
 		  {
 		    LOG_TRACE(logger, c << " fails to install the mandated version " << solver);
+		    reasons.insert_or_narrow(choice::make_break_soft_dep(d, c.get_id()));
 		    return false;
 		  }
 	      }
@@ -2322,11 +2335,12 @@ private:
   /** \return \b true if the given solution breaks a constraint
    *  imposed by the user.
    */
-  bool breaks_user_constraint(const solution &s) const
+  bool breaks_user_constraint(const solution &s,
+			      choice_set &reasons) const
   {
     choice_does_not_break_user_constraint f(user_rejected, user_mandated,
 					    user_hardened, user_approved_broken,
-					    initial_state, logger);
+					    initial_state, reasons, logger);
 
     bool does_not_break_user_constraint = s.get_choices().for_each(f);
     return !does_not_break_user_constraint;
@@ -2383,7 +2397,8 @@ private:
 
 		++j;
 
-		if(!breaks_user_constraint(get_step(*i).sol))
+		choice_set dummy;
+		if(!breaks_user_constraint(get_step(*i).sol, dummy))
 		  {
 		    LOG_DEBUG(logger, "Step " << *i << " is no longer deferred, placing it back on the open queue.");
 
@@ -2409,7 +2424,8 @@ private:
 
 	++j;
 
-	if(!breaks_user_constraint(get_step(*i).sol))
+	choice_set dummy;
+	if(!breaks_user_constraint(get_step(*i).sol, dummy))
 	  {
 	    LOG_DEBUG(logger, "Step " << *i << " is no longer deferred, placing it back on the open queue.");
 
@@ -2523,18 +2539,23 @@ private:
       // Shouldn't happen: we should have caught irrelevant solutions
       // earlier in the process.
       LOG_WARN(logger, "Unexpectedly irrelevant solution " << s);
-    else if(breaks_user_constraint(s))
-      {
-	// TODO: accumulate a promotion describing the breakage and
-	// backpropagate it.
-	LOG_WARN(logger, "Deferring rejected solution " << s);
-	defer_step(defer_tier, step_num);
-      }
     else
       {
-	LOG_TRACE(logger, "Enqueuing " << s);
+	choice_set defer_reason;
+	if(breaks_user_constraint(s, defer_reason))
+	  {
+	    LOG_WARN(logger, "Deferring rejected solution " << s);
+	    // Add a singleton promotion here?
+	    promotion defer_promotion(defer_reason, defer_tier);
+	    schedule_promotion_propagation(step_num, defer_promotion);
+	    defer_step(defer_tier, step_num);
+	  }
+	else
+	  {
+	    LOG_TRACE(logger, "Enqueuing " << s);
 
-	open.push(step_num);
+	    open.push(step_num);
+	  }
       }
   }
 
@@ -2578,7 +2599,7 @@ private:
 		  "Discarding " << v
 		  << ": monotonicity violation");
 
-	out_choice = choice::make_install_version(inst, dep(), -1);
+	out_choice = choice::make_install_version(inst, -1);
 	return false;
       }
     else
@@ -2835,7 +2856,7 @@ private:
 	if(from_dep_source)
 	  new_choice = choice::make_install_version_from_dep_source(v, d, newid);
 	else
-	  new_choice = choice::make_install_version(v, d, newid);
+	  new_choice = choice::make_install_version(v, false, d, newid);
 
 	// Speculatively form the new set of actions; doing this
 	// rather than forming the whole solution allows us to avoid
@@ -2911,7 +2932,7 @@ private:
 		    // and not to the set of excluded versions, we can
 		    // use the wider version, thus promoting more
 		    // search nodes.
-		    choice promotion_s_c(choice::make_install_version(v, d, newid));
+		    choice promotion_s_c(choice::make_install_version(v, false, d, newid));
 		    promotion_s.insert_or_narrow(promotion_s_c);
 		    successor_promotion = promotion(promotion_s, ver_tier);
 		  }
@@ -3016,7 +3037,7 @@ private:
       {
 	if(source_was_modified)
 	  {
-	    choice change_source(choice::make_install_version(source, dep(), -1));
+	    choice change_source(choice::make_install_version(source, -1));
 	    if(successor_constraints != NULL)
 	      successor_constraints->insert_or_narrow(change_source);
 	    subpromotion_choices.insert_or_narrow(change_source);
@@ -3913,12 +3934,18 @@ public:
 	    defer_step(s_tier, curr_step_num);
 	    continue;
 	  }
-	else if(breaks_user_constraint(s))
+	else
 	  {
-	    LOG_DEBUG(logger, "Deferring rejected solution " << s);
+	    choice_set defer_reason;
+	    if(breaks_user_constraint(s, defer_reason))
+	      {
+		LOG_DEBUG(logger, "Deferring rejected solution " << s);
 
-	    defer_step(defer_tier, curr_step_num);
-	    continue;
+		promotion defer_promotion(defer_reason, defer_tier);
+		schedule_promotion_propagation(curr_step_num, defer_promotion);
+		defer_step(defer_tier, curr_step_num);
+		continue;
+	      }
 	  }
 
 	closed.insert(s);
@@ -4000,10 +4027,13 @@ public:
 	    solution tmp = get_step(tmp_step).sol;
 	    future_solutions.pop();
 
-	    if(breaks_user_constraint(tmp))
+	    choice_set defer_reason;
+	    if(breaks_user_constraint(tmp, defer_reason))
 	      {
 		LOG_TRACE(logger, "Deferring the future solution " << tmp);
 		deferred_future_solutions.insert(tmp_step);
+		promotion defer_promotion(defer_reason, defer_tier);
+		schedule_promotion_propagation(tmp_step, defer_promotion);
 	      }
 	    else
 	      rval = tmp;
diff --git a/src/generic/problemresolver/solution.h b/src/generic/problemresolver/solution.h
index 747e03be..a0779efe 100644
--- a/src/generic/problemresolver/solution.h
+++ b/src/generic/problemresolver/solution.h
@@ -912,7 +912,7 @@ private:
       if(version == initial_state.version_of(version.get_package()))
 	any_is_current = true;
 
-      output.insert_or_narrow(choice::make_install_version(version, dep(), 0));
+      output.insert_or_narrow(choice::make_install_version(version, false, dep(), 0));
 
       return true;
     }
diff --git a/tests/test_choice.cc b/tests/test_choice.cc
index b30c8c43..bc193a15 100644
--- a/tests/test_choice.cc
+++ b/tests/test_choice.cc
@@ -64,7 +64,12 @@ class Choice_Test : public CppUnit::TestFixture
   // routines that use a dummy value.
   static choice make_install_version(const version &v)
   {
-    return choice::make_install_version(v, dep(), -1);
+    return choice::make_install_version(v, -1);
+  }
+
+  static choice make_install_version(const version &v, bool dep_scoped, const dep &d)
+  {
+    return choice::make_install_version(v, dep_scoped, d, -1);
   }
 
   static choice make_install_version_from_dep_source(const version &v, const dep &d)
@@ -105,6 +110,8 @@ public:
 
     const choice cav1 = make_install_version(av1);
     const choice cav1av2d1 = make_install_version_from_dep_source(av1, av2d1);
+    const choice cav1av2d1_scoped = make_install_version(av1, true, av2d1);
+    const choice cav1av2d1_unscoped = make_install_version(av1, false, av2d1);
     const choice cav1av3d1 = make_install_version_from_dep_source(av1, av3d1);
     const choice cav2 = make_install_version(av2);
     const choice cbv1 = make_install_version(bv1);
@@ -114,6 +121,8 @@ public:
     // Check that all the containment relations here are correct.
     CPPUNIT_ASSERT(cav1.contains(cav1));
     CPPUNIT_ASSERT(cav1.contains(cav1av2d1));
+    CPPUNIT_ASSERT(cav1.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(cav1.contains(cav1av2d1_unscoped));
     CPPUNIT_ASSERT(cav1.contains(cav1av3d1));
     CPPUNIT_ASSERT(!cav1.contains(cav2));
     CPPUNIT_ASSERT(!cav1.contains(cbv1));
@@ -122,14 +131,38 @@ public:
 
     CPPUNIT_ASSERT(!cav1av2d1.contains(cav1));
     CPPUNIT_ASSERT(cav1av2d1.contains(cav1av2d1));
+    CPPUNIT_ASSERT(!cav1av2d1.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(!cav1av2d1.contains(cav1av2d1_unscoped));
     CPPUNIT_ASSERT(!cav1av2d1.contains(cav1av3d1));
     CPPUNIT_ASSERT(!cav1av2d1.contains(cav2));
     CPPUNIT_ASSERT(!cav1av2d1.contains(cbv1));
     CPPUNIT_ASSERT(!cav1av2d1.contains(cav1d1));
     CPPUNIT_ASSERT(!cav1av2d1.contains(cav2d1));
 
+    CPPUNIT_ASSERT(!cav1av2d1_scoped.contains(cav1));
+    CPPUNIT_ASSERT(cav1av2d1_scoped.contains(cav1av2d1));
+    CPPUNIT_ASSERT(cav1av2d1_scoped.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(cav1av2d1_scoped.contains(cav1av2d1_unscoped));
+    CPPUNIT_ASSERT(!cav1av2d1_scoped.contains(cav1av3d1));
+    CPPUNIT_ASSERT(!cav1av2d1_scoped.contains(cav2));
+    CPPUNIT_ASSERT(!cav1av2d1_scoped.contains(cbv1));
+    CPPUNIT_ASSERT(!cav1av2d1_scoped.contains(cav1d1));
+    CPPUNIT_ASSERT(!cav1av2d1_scoped.contains(cav2d1));
+
+    CPPUNIT_ASSERT(cav1av2d1_unscoped.contains(cav1));
+    CPPUNIT_ASSERT(cav1av2d1_unscoped.contains(cav1av2d1));
+    CPPUNIT_ASSERT(cav1av2d1_unscoped.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(cav1av2d1_unscoped.contains(cav1av2d1_unscoped));
+    CPPUNIT_ASSERT(cav1av2d1_unscoped.contains(cav1av3d1));
+    CPPUNIT_ASSERT(!cav1av2d1_unscoped.contains(cav2));
+    CPPUNIT_ASSERT(!cav1av2d1_unscoped.contains(cbv1));
+    CPPUNIT_ASSERT(!cav1av2d1_unscoped.contains(cav1d1));
+    CPPUNIT_ASSERT(!cav1av2d1_unscoped.contains(cav2d1));
+
     CPPUNIT_ASSERT(!cav1av3d1.contains(cav1));
     CPPUNIT_ASSERT(!cav1av3d1.contains(cav1av2d1));
+    CPPUNIT_ASSERT(!cav1av3d1.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(!cav1av3d1.contains(cav1av2d1_unscoped));
     CPPUNIT_ASSERT(cav1av3d1.contains(cav1av3d1));
     CPPUNIT_ASSERT(!cav1av3d1.contains(cav2));
     CPPUNIT_ASSERT(!cav1av3d1.contains(cbv1));
@@ -140,6 +173,8 @@ public:
 
     CPPUNIT_ASSERT(!cav2.contains(cav1));
     CPPUNIT_ASSERT(!cav2.contains(cav1av2d1));
+    CPPUNIT_ASSERT(!cav2.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(!cav2.contains(cav1av2d1_unscoped));
     CPPUNIT_ASSERT(!cav2.contains(cav1av3d1));
     CPPUNIT_ASSERT(cav2.contains(cav2));
     CPPUNIT_ASSERT(!cav2.contains(cbv1));
@@ -148,6 +183,8 @@ public:
 
     CPPUNIT_ASSERT(!cbv1.contains(cav1));
     CPPUNIT_ASSERT(!cbv1.contains(cav1av2d1));
+    CPPUNIT_ASSERT(!cbv1.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(!cbv1.contains(cav1av2d1_unscoped));
     CPPUNIT_ASSERT(!cbv1.contains(cav1av3d1));
     CPPUNIT_ASSERT(!cbv1.contains(cav2));
     CPPUNIT_ASSERT(cbv1.contains(cbv1));
@@ -156,6 +193,8 @@ public:
 
     CPPUNIT_ASSERT(!cav1d1.contains(cav1));
     CPPUNIT_ASSERT(!cav1d1.contains(cav1av2d1));
+    CPPUNIT_ASSERT(!cav1d1.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(!cav1d1.contains(cav1av2d1_unscoped));
     CPPUNIT_ASSERT(!cav1d1.contains(cav1av3d1));
     CPPUNIT_ASSERT(!cav1d1.contains(cav2));
     CPPUNIT_ASSERT(!cav1d1.contains(cbv1));
@@ -164,6 +203,8 @@ public:
 
     CPPUNIT_ASSERT(!cav2d1.contains(cav1));
     CPPUNIT_ASSERT(!cav2d1.contains(cav1av2d1));
+    CPPUNIT_ASSERT(!cav2d1.contains(cav1av2d1_scoped));
+    CPPUNIT_ASSERT(!cav2d1.contains(cav1av2d1_unscoped));
     CPPUNIT_ASSERT(!cav2d1.contains(cav1av3d1));
     CPPUNIT_ASSERT(!cav2d1.contains(cav2));
     CPPUNIT_ASSERT(!cav2d1.contains(cbv1));
diff --git a/tests/test_choice_set.cc b/tests/test_choice_set.cc
index 041137c5..103d034c 100644
--- a/tests/test_choice_set.cc
+++ b/tests/test_choice_set.cc
@@ -140,7 +140,7 @@ class Choice_Set_Test : public CppUnit::TestFixture
   // routines that use a dummy value.
   static choice make_install_version(const version &v)
   {
-    return choice::make_install_version(v, dep(), -1);
+    return choice::make_install_version(v, -1);
   }
 
   static choice make_install_version_from_dep_source(const version &v, const dep &d)
diff --git a/tests/test_promotion_set.cc b/tests/test_promotion_set.cc
index 07002c37..a44fd363 100644
--- a/tests/test_promotion_set.cc
+++ b/tests/test_promotion_set.cc
@@ -223,7 +223,7 @@ class Promotion_SetTest : public CppUnit::TestFixture
   // routines that use a dummy value.
   static choice make_install_version(const version &v)
   {
-    return choice::make_install_version(v, dep(), -1);
+    return choice::make_install_version(v, -1);
   }
 
   static choice make_install_version_from_dep_source(const version &v, const dep &d)
diff --git a/tests/test_resolver.cc b/tests/test_resolver.cc
index 89a9755f..32049dbf 100644
--- a/tests/test_resolver.cc
+++ b/tests/test_resolver.cc
@@ -206,14 +206,14 @@ private:
       u_broken.insert(*bi);
 
     choice c1(choice::make_install_version(u.find_package("a").version_from_name("v1"),
-					   d1, 49));
+					   false, d1, 49));
     choice c2(choice::make_install_version(u.find_package("a").version_from_name("v1"),
-					   d2, 21));
+					   false, d2, 21));
     choice c3(choice::make_install_version(u.find_package("a").version_from_name("v2"),
-					   d1, 49));
+					   false, d1, 49));
 
     choice c4(choice::make_install_version(u.find_package("c").version_from_name("v3"),
-					   d2, 21));
+					   false, d2, 21));
 
     choice c5(choice::make_break_soft_dep(d1, 443));
 
@@ -255,7 +255,7 @@ private:
     assertLtInequivalent(s0, s7, solcmp);
 
     assertLtEquivalent(s1, s1, solcmp);
-    assertLtEquivalent(s1, s2, solcmp);
+    assertLtInequivalent(s1, s2, solcmp);
     assertLtInequivalent(s1, s3, solcmp);
     assertLtInequivalent(s1, s4, solcmp);
     assertLtInequivalent(s1, s5, solcmp);
@@ -330,11 +330,11 @@ private:
     version cv2 = c.version_from_name("v2");
 
     choice_set av1_choices;
-    av1_choices.insert_or_narrow(choice::make_install_version(bv2, dep(), 0));
-    av1_choices.insert_or_narrow(choice::make_install_version(cv2, dep(), 0));
+    av1_choices.insert_or_narrow(choice::make_install_version(bv2, 0));
+    av1_choices.insert_or_narrow(choice::make_install_version(cv2, 0));
 
     choice_set av2_choices;
-    av2_choices.insert_or_narrow(choice::make_install_version(av2, dep(), 0));
+    av2_choices.insert_or_narrow(choice::make_install_version(av2, 0));
 
     // Verify that without a tier we get the shorter solution first.
     // Without this we aren't testing anything!
diff --git a/tools/resolver-visualize/DotRender.hs b/tools/resolver-visualize/DotRender.hs
index 269bb81d..3ad043e8 100644
--- a/tools/resolver-visualize/DotRender.hs
+++ b/tools/resolver-visualize/DotRender.hs
@@ -19,7 +19,7 @@ inBounds params n = let first = maybe 0 id (firstStep params) in
                     n >= first && maybe True (\max -> n < first + max) (maxSteps params)
 
 choiceText :: LinkChoice -> String
-choiceText (LinkChoice (InstallVersion ver _ _)) = "Install " ++ pp ver
+choiceText (LinkChoice (InstallVersion ver _)) = "Install " ++ pp ver
 choiceText (LinkChoice (BreakSoftDep d)) = "Break " ++ pp d
 choiceText Unknown = "(...)"
 
diff --git a/tools/resolver-visualize/Main.hs b/tools/resolver-visualize/Main.hs
index ab82181c..b6a12ca2 100755
--- a/tools/resolver-visualize/Main.hs
+++ b/tools/resolver-visualize/Main.hs
@@ -607,21 +607,17 @@ entryColumnScore (AlreadyGeneratedStep { entrySol = sol })              = show $
 entryColumnScore (NoStep { entrySol = sol })                            = show $ solScore sol
 entryColumnScore (Error {})                                             = ""
 
+linkChoiceDepText :: LinkChoice -> String
+linkChoiceDepText (LinkChoice (InstallVersion { choiceVerDepInfo = Just di })) =
+    pp (depInfoDep di)
+linkChoiceDepText _ = ""
+
 entryColumnDep :: TreeViewEntry -> String
 entryColumnDep (Root {}) = ""
-entryColumnDep (Step { entryChoice = choice }) =
-    case choice of
-      LinkChoice (InstallVersion { choiceVerReason = Just d }) -> pp d
-      _ -> ""
+entryColumnDep (Step { entryChoice = choice }) = linkChoiceDepText choice
 entryColumnDep (Horizon { }) = ""
-entryColumnDep (AlreadyGeneratedStep { entryChoice = choice }) =
-    case choice of
-      LinkChoice (InstallVersion { choiceVerReason = Just d }) -> pp d
-      _ -> ""
-entryColumnDep (NoStep { entryChoice = choice }) =
-    case choice of
-      LinkChoice (InstallVersion { choiceVerReason = Just d }) -> pp d
-      _ -> ""
+entryColumnDep (AlreadyGeneratedStep { entryChoice = choice }) = linkChoiceDepText choice
+entryColumnDep (NoStep { entryChoice = choice }) = linkChoiceDepText choice
 entryColumnDep (Error { entryErrorText = err }) = ""
 
 renderTreeView :: Params -> [ProcessingStep] -> TreeViewStore -> IO ()
@@ -661,7 +657,7 @@ makeChronStep step =
                         Just (ParentLink { parentLinkAction = LinkChoice c }) -> Just c
                         _ -> Nothing
         dep         = case choice of
-                        Just (InstallVersion { choiceVerReason = maybeDep }) -> maybeDep
+                        Just (InstallVersion { choiceVerDepInfo = maybeDi }) -> fmap depInfoDep maybeDi
                         _ -> Nothing in
     numChoices `seq` brokenDeps `seq` stepNum `seq` children `seq` height `seq` subtreeSize `seq` step `seq` tier `seq` score `seq`
     choice `seq` parent `seq` dep `seq`
diff --git a/tools/resolver-visualize/Resolver/Log.hs b/tools/resolver-visualize/Resolver/Log.hs
index 49aa1a51..86717aa3 100644
--- a/tools/resolver-visualize/Resolver/Log.hs
+++ b/tools/resolver-visualize/Resolver/Log.hs
@@ -566,8 +566,7 @@ processTryingResolutionLine source matches =
        let fromDep = (fst (matches!3) /= (-1))
            c = InstallVersion {
                  choiceVer = v,
-                 choiceVerReason = (Just d),
-                 choiceFromDepSource = (Just fromDep)
+                 choiceVerDepInfo = Just (FromSource d)
                }
            lc = LinkChoice c
        d `seq` v `seq` c `seq` lc `seq`
@@ -765,8 +764,9 @@ forceEverything a =
       forceSol sol = ()
       forcePromotion p = ()
       forceDep (Dep source solvers isSoft) = forceMap forceVersion solvers `seq` forceVersion source `seq` isSoft `seq` ()
-      forceChoice (InstallVersion ver dep fromDepSource) =
-          forceVersion ver `seq` forceMaybe forceDep dep `seq` forceMaybe id fromDepSource `seq` ()
+      forceDepInfo di = forceDep (depInfoDep di) `seq` ()
+      forceChoice (InstallVersion ver depInfo) =
+          forceVersion ver `seq` forceMaybe forceDepInfo depInfo `seq` ()
       forceChoice (BreakSoftDep dep) =
           forceDep dep `seq` ()
       forceVersion (Version p name) =
diff --git a/tools/resolver-visualize/Resolver/Parse.hs b/tools/resolver-visualize/Resolver/Parse.hs
index f815a48e..ff28ba4b 100644
--- a/tools/resolver-visualize/Resolver/Parse.hs
+++ b/tools/resolver-visualize/Resolver/Parse.hs
@@ -121,16 +121,23 @@ instance Internable Dep where
            deps' `seq` (pkgName $ verPkg $ depSource rval) `seq` (verName $ depSource rval)
                  `seq` (seqList $ depSolvers rval) `seq` return rval
 
+instance Internable ChoiceDepInfo where
+    intern depInfo =
+        do let dep = depInfoDep depInfo
+           dep' <- intern dep
+           let rval = depInfo { depInfoDep = dep' }
+           dep' `seq` rval `seq` return rval
+
 instance Internable Choice where
-    intern c@(InstallVersion ver reason fromDepSource) =
+    intern c@(InstallVersion ver depInfo) =
         do ver'     <- intern ver
-           reason'  <- maybeIntern reason
+           depInfo' <- maybeIntern depInfo
            st       <- getState
            let choices           = internedChoices st
-               (choices', rval)  = doIntern choices c (InstallVersion ver' reason' fromDepSource)
+               (choices', rval)  = doIntern choices c (InstallVersion ver' depInfo')
            putState st { internedChoices = choices' }
-           choices' `seq` (verPkg $ choiceVer rval) `seq` (choiceVerReason rval)
-                    `seq` (choiceFromDepSource rval) `seq` return rval
+           choices' `seq` (verPkg $ choiceVer rval)
+                    `seq` depInfo' `seq` return rval
     intern c@(BreakSoftDep dep) =
         do dep'     <- intern dep
            st       <- getState
@@ -269,22 +276,32 @@ depWithoutTerminators terminators =
 dep :: Parser Dep
 dep = depWithoutTerminators []
 
--- | A choice is either Install(ver) or Break(dep)
+-- | A choice is either Install(ver) or Break(dep); versions can have
+-- [dep] after them (old-style from-dep-source), or <dep> (new-style
+-- unscoped, or <"source:" dep> / <"scope:" dep> (new-style
+-- from-dep-source or scoped).
 choice :: Parser Choice
 choice = (lexeme $ do installChoice <|> breakDepChoice) <?> "choice"
     where installChoice = do try (symbol "Install")
                              parens $ do
                                v <- versionWithoutTerminators [rightParen]
                                v `seq` ((do d <- squares dep
-                                            let fromDepSource = Just True
-                                                reason        = Just d
-                                            (d `seq` fromDepSource `seq` reason `seq`
+                                            let reason  = FromSource d
+                                                depInfo = Just reason
+                                            (d `seq` reason `seq` depInfo `seq`
                                              (intern InstallVersion { choiceVer = v,
-                                                                      choiceVerReason = reason,
-                                                                      choiceFromDepSource = fromDepSource }))) <|>
+                                                                      choiceVerDepInfo = depInfo }))) <|>
+                                        (angles $ do k <- ((try (symbol "source:") >> return FromSource) <|>
+                                                           (try (symbol "scope:") >> return Scoped) <|>
+                                                           (return Unscoped))
+                                                     d <- dep
+                                                     let reason  = k d
+                                                         depInfo = Just reason
+                                                     d `seq` reason `seq` depInfo `seq`
+                                                           (intern InstallVersion { choiceVer = v,
+                                                                                    choiceVerDepInfo = depInfo })) <|>
                                         (intern InstallVersion { choiceVer = v,
-                                                                 choiceVerReason = Nothing,
-                                                                 choiceFromDepSource = Nothing }))
+                                                                 choiceVerDepInfo = Nothing }))
           breakDepChoice = do try (symbol "Break")
                               d <- parens dep
                               d `seq` intern $ BreakSoftDep { choiceDep = d }
@@ -342,8 +359,7 @@ solution = do installVersionChoices <- solutionInstalls
                  v <- lexeme $ readCharsTill [comma, rightAngle]
                  return $ InstallVersion { choiceVer = Version { verPkg = p,
                                                                  verName = BS.pack v },
-                                           choiceVerReason = Nothing,
-                                           choiceFromDepSource = Nothing }
+                                           choiceVerDepInfo = Nothing }
           solutionUnresolvedSoftDeps =
               do spaces
                  (do try (symbol "<!")
diff --git a/tools/resolver-visualize/Resolver/PrettyPrint.hs b/tools/resolver-visualize/Resolver/PrettyPrint.hs
index 303e3396..1c94bd88 100644
--- a/tools/resolver-visualize/Resolver/PrettyPrint.hs
+++ b/tools/resolver-visualize/Resolver/PrettyPrint.hs
@@ -21,7 +21,11 @@ instance PP Dep where
                                    ppS src . (arrow++) . (\x -> foldr (++) x $ intersperse ", " $ map pp solvers) . ('}':)
 
 instance PP Choice where
-    ppS (InstallVersion ver _ _) = ("Install "++) . ppS ver
+    ppS (InstallVersion ver di) = ("Install "++) . case di of
+                                                     Nothing             -> ppS ver
+                                                     Just (Unscoped _)   -> ppS ver
+                                                     Just (Scoped d)     -> ("<scope: "++) . ppS d . (">"++)
+                                                     Just (FromSource d) -> ("<source: "++) . ppS d . (">"++)
     ppS (BreakSoftDep d) = ("Break "++) . ppS d
 
 instance PP Promotion where
diff --git a/tools/resolver-visualize/Resolver/Types.hs b/tools/resolver-visualize/Resolver/Types.hs
index 1191205e..8428dd8c 100644
--- a/tools/resolver-visualize/Resolver/Types.hs
+++ b/tools/resolver-visualize/Resolver/Types.hs
@@ -5,6 +5,7 @@ module Resolver.Types(
                       Package(..),
                       Version(..),
                       Dep(..),
+                      ChoiceDepInfo(..),
                       Choice(..),
                       Solution(..),
                       FastSolution(fastSol, fastSolHash),
@@ -61,6 +62,10 @@ data Dep = Dep { -- | The version that declares this dependency.
                  depIsSoft :: Bool}
          deriving(Ord, Eq, Show)
 
+data ChoiceDepInfo = Unscoped   { depInfoDep :: Dep }
+                   | Scoped     { depInfoDep :: Dep }
+                   | FromSource { depInfoDep :: Dep }
+              deriving(Ord, Eq, Show)
 
 -- | Represents a choice made by the dependency resolver.
 data Choice = InstallVersion { -- | The version to install.
@@ -69,11 +74,7 @@ data Choice = InstallVersion { -- | The version to install.
                                -- installation.
                                --
                                -- Will be Nothing if it is not known.
-                               choiceVerReason :: Maybe Dep,
-                               -- | True if this choice was made to
-                               -- alter the source of the dependency.
-                               -- Nothing if it is not known.
-                               choiceFromDepSource :: Maybe Bool }
+                               choiceVerDepInfo :: Maybe ChoiceDepInfo }
             -- ^ Install a single version.
             -- | Leave a soft dependency unresolved.
             | BreakSoftDep { -- | The dependency that was not