Have the resolver ignore unresolved dependencies that were unresolved before the current run of aptitude started. (Closes: #556042)

This is done by filtering them out of the initial set of dependencies
that the root node is initialized with.

NOTE: I still need to convince myself that we can't somehow end up
reactivating a dependency that should have been skipped.  However,
we might really need to legitimately activate it...something to think
over, anyway.  (I particularly suspect that the weird behavior of
Conflicts might be a problem)

7 files changed, 181 insertions, 29 deletions

diff --git a/src/generic/apt/aptitude_resolver_universe.cc b/src/generic/apt/aptitude_resolver_universe.cc
index d73fb197..33057c1f 100644
--- a/src/generic/apt/aptitude_resolver_universe.cc
+++ b/src/generic/apt/aptitude_resolver_universe.cc
@@ -311,8 +311,6 @@ void aptitude_resolver_version::dep_iterator::normalize()
   // If we ran out of deps, we're done!
 }
 
-
-
 void aptitude_resolver_dep::solver_iterator::normalize()
 {
   if(!is_conflict(dep_lst->Type))
@@ -958,3 +956,23 @@ std::string aptitude_universe::get_tier_name(const tier &t)
 	return ssprintf("%s (%d)", name.c_str(), t.get_policy());
     }
 }
+
+
+bool aptitude_universe::is_candidate_for_initial_set(const aptitude_resolver_dep &d) const
+{
+  if(!d.is_soft())
+    return true;
+
+  if(cache == NULL)
+    return false;
+
+  pkgCache::DepIterator d2(d.get_dep());
+  while(!d2.end() && (d2->CompareOp & pkgCache::Dep::Or))
+    ++d2;
+
+  if(d2.end())
+    return true;
+
+  // Return true only if the dependency is *currently* not broken.
+  return (*cache)[d2] & pkgDepCache::DepGNow;
+}
diff --git a/src/generic/apt/aptitude_resolver_universe.h b/src/generic/apt/aptitude_resolver_universe.h
index c11dd840..69176c64 100644
--- a/src/generic/apt/aptitude_resolver_universe.h
+++ b/src/generic/apt/aptitude_resolver_universe.h
@@ -1367,6 +1367,8 @@ public:
     return broken_dep_iterator(cache);
   }
 
+  bool is_candidate_for_initial_set(const dep &d) const;
+
   unsigned long get_version_count() const
   {
     // PackageCount is added to make room for the UNINST versions.
diff --git a/src/generic/problemresolver/dummy_universe.cc b/src/generic/problemresolver/dummy_universe.cc
index 364359d6..74c8519a 100644
--- a/src/generic/problemresolver/dummy_universe.cc
+++ b/src/generic/problemresolver/dummy_universe.cc
@@ -60,8 +60,10 @@ public:
 
 dummy_dep::dummy_dep(dummy_version *_source,
 		     const std::vector<dummy_version *> &_target_set,
-		     unsigned int _ID, bool _soft)
-  :source(_source), target_set(_target_set), ID(_ID), soft(_soft)
+		     unsigned int _ID, bool _soft,
+		     bool _candidate_for_initial_set)
+  :source(_source), target_set(_target_set), ID(_ID), soft(_soft),
+   candidate_for_initial_set(_candidate_for_initial_set)
 {
 
   sort(target_set.begin(), target_set.end(),
@@ -129,7 +131,8 @@ void dummy_universe::add_package(const string &name,
 
 void dummy_universe::add_dep(const string &pkg_name, const string &pkg_ver,
 			     const vector<pair<string, string> > &target_names,
-			     bool is_conflict, bool is_soft)
+			     bool is_conflict, bool is_soft,
+			     bool is_candidate_for_initial_set)
 {
   dummy_package *pkg=find_package_internal(pkg_name);
 
@@ -149,7 +152,8 @@ void dummy_universe::add_dep(const string &pkg_name, const string &pkg_ver,
     deps.push_back(new dummy_dep(pkg->version_from_name(pkg_ver),
 				 vector<dummy_version *>(targets.begin(), targets.end()),
 				 deps.size(),
-				 is_soft));
+				 is_soft,
+				 is_candidate_for_initial_set));
   else
     {
       set<dummy_version *> targets2;
@@ -164,7 +168,8 @@ void dummy_universe::add_dep(const string &pkg_name, const string &pkg_ver,
       deps.push_back(new dummy_dep(pkg->version_from_name(pkg_ver),
 				   vector<dummy_version *>(targets2.begin(), targets2.end()),
 				   deps.size(),
-				   is_soft));
+				   is_soft,
+				   is_candidate_for_initial_set));
     }
 
   dummy_dep *newdep=deps.back();
@@ -188,7 +193,14 @@ ostream &operator<<(ostream &out, const dummy_universe::version &v)
 
 ostream &operator<<(ostream &out, const dummy_universe::dep &d)
 {
-  out << d.get_source() << (d.is_soft() ? " -S> {" : " -> {");
+  out << d.get_source() << " -";
+
+  if(d.is_soft())
+    out << "S";
+  if(d.is_candidate_for_initial_set())
+    out << "?";
+  out << "> {";
+
   for(dummy_universe::dep::solver_iterator i=d.solvers_begin();
       !i.end(); ++i)
     {
@@ -326,13 +338,16 @@ dummy_universe_ref parse_universe_tail(istream &in)
 	  pair<string, string> source=read_pkgverpair(in);
 	  bool is_conflict=false;
 	  bool is_soft = (s == "SOFTDEP");
+	  bool is_candidate_for_initial_set = true;
 
 	  in >> s >> ws;
 
 	  if(s == "!!")
 	    is_conflict=true;
+	  else if(s == "-?>")
+	    is_candidate_for_initial_set = false;
 	  else if(s != "->")
-	    throw ParseError("Expected '->' or '!!', got "+s);
+	    throw ParseError("Expected '->', '-?>', or '!!', got "+s);
 
 	  if(in.eof())
 	    throw ParseError("Expected '<', got EOF");
@@ -371,7 +386,8 @@ dummy_universe_ref parse_universe_tail(istream &in)
 	    }
 
 	  rval.add_dep(source.first, source.second, targets,
-		       is_conflict, is_soft);
+		       is_conflict, is_soft,
+		       is_candidate_for_initial_set);
 	}
       else
 	throw ParseError("Expected PACKAGE, DEP, or SOFTDEP, got "+s);
diff --git a/src/generic/problemresolver/dummy_universe.h b/src/generic/problemresolver/dummy_universe.h
index 5832c804..21c74d2f 100644
--- a/src/generic/problemresolver/dummy_universe.h
+++ b/src/generic/problemresolver/dummy_universe.h
@@ -245,18 +245,24 @@ class dummy_dep
   unsigned int ID;
 
   bool soft;
+  bool candidate_for_initial_set;
 public:
   typedef std::vector<dummy_version *>::const_iterator solver_iterator;
 
   dummy_dep(dummy_version *_source,
 	    const std::vector<dummy_version *> &_target_set,
-	    unsigned int _ID, bool _soft);
+	    unsigned int _ID, bool _soft, bool _candidate_for_initial_set);
 
   bool is_soft() const
   {
     return soft;
   }
 
+  bool is_candidate_for_initial_set() const
+  {
+    return candidate_for_initial_set;
+  }
+
   bool operator==(const dummy_dep &other) const
   {
     return this==&other;
@@ -447,6 +453,11 @@ public:
       return real_dep->is_soft();
     }
 
+    bool is_candidate_for_initial_set() const
+    {
+      return real_dep->is_candidate_for_initial_set();
+    }
+
     std::size_t get_hash_value() const
     {
       boost::hash<const dummy_dep *> hasher;
@@ -676,7 +687,7 @@ public:
    */
   void add_dep(const std::string &pkg_name, const std::string &pkg_ver,
 	       const std::vector<std::pair<std::string, std::string> > &target_names,
-	       bool is_conflict, bool is_soft);
+	       bool is_conflict, bool is_soft, bool candidate_for_initial_set);
 
   std::vector<package>::size_type get_package_count() const
   {
@@ -702,6 +713,11 @@ public:
   {
     return broken_dep_iterator(deps.begin(), deps.end());
   }
+
+  bool is_candidate_for_initial_set(const dep &d) const
+  {
+    return d.is_candidate_for_initial_set();
+  }
 };
 
 inline std::size_t hash_value(const dummy_universe::package &p)
@@ -809,10 +825,10 @@ public:
 
   void add_dep(std::string pkg_name, std::string pkg_ver,
 	       const std::vector<std::pair<std::string, std::string> > &target_names,
-	       bool is_conflict, bool is_soft)
+	       bool is_conflict, bool is_soft, bool candidate_for_initial_set)
   {
     rep->universe->add_dep(pkg_name, pkg_ver,
-			   target_names, is_conflict, is_soft);
+			   target_names, is_conflict, is_soft, candidate_for_initial_set);
   }
 
   package find_package(const std::string &pkg_name) const
@@ -844,6 +860,11 @@ public:
   {
     return rep->universe->broken_begin();
   }
+
+  bool is_candidate_for_initial_set(const dep &d) const
+  {
+    return rep->universe->is_candidate_for_initial_set(d);
+  }
 };
 
 template<class T>
diff --git a/src/generic/problemresolver/dump_universe.h b/src/generic/problemresolver/dump_universe.h
index f2f7a7c4..b5fd2113 100644
--- a/src/generic/problemresolver/dump_universe.h
+++ b/src/generic/problemresolver/dump_universe.h
@@ -1,6 +1,6 @@
 // dump_universe.h                                      -*-c++-*-
 //
-//   Copyright (C) 2005 Daniel Burrows
+//   Copyright (C) 2005, 2009 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
@@ -50,7 +50,10 @@ void dump_universe(const PackageUniverse &world, std::ostream &out)
       else
 	out << "  DEP ";
 
-      out << sp.get_name() << " " << sv.get_name() << " -> < ";
+      out << sp.get_name() << " " << sv.get_name() << " "
+	  << (world.is_candidate_for_initial_set(*d)
+	      ? "->" : "-?>")
+	  << " < ";
 
       for(typename PackageUniverse::dep::solver_iterator t=(*d).solvers_begin();
 	  !t.end(); ++t)
diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h
index 31f9e050..621946f6 100644
--- a/src/generic/problemresolver/problemresolver.h
+++ b/src/generic/problemresolver/problemresolver.h
@@ -292,6 +292,17 @@ static inline dummy_end_iterator<V> operator++(dummy_end_iterator<V>&)
  *  first \ref universe_dep "dependency" (in an arbitrary ordering) in
  *  the universe.
  *
+ *  - <b>bool is_candidate_for_initial_set(const dep &)</b>: returns
+ *    \b true if the dependency should be in the set of dependencies
+ *    the resolver initially sets out to solve.  Dependencies for
+ *    which this returns "false" will not be deliberately solved
+ *    (although they might be coincidentally solved by other changes
+ *    the resolver makes).  This is a member of the universe and not
+ *    the dependency concept because I forsee the program possibly
+ *    wanting to create universes with different behavior in this
+ *    regard at some point in the future.
+ *
+ *
  *  \page universe_package Package concept
  *
  *  A package is simply a unique collection of \ref universe_version
@@ -3649,13 +3660,26 @@ public:
       {
 	dep d(*di);
 
-	if(d.broken_under(initial_state))
+	if(!universe.is_candidate_for_initial_set(d))
+	  {
+	    // This test is slow and only used for logging:
+	    if(LOG4CXX_UNLIKELY(logger->isTraceEnabled()))
+	      {
+		if(!d.broken_under(initial_state))
+		  LOG_TRACE(logger, "Not using " << d
+			    << " as an initially broken dependency because it is flagged as a dependency that shouldn't be in the initial set.");
+	      }
+	  }
+	else if(d.broken_under(initial_state))
 	  {
 	    if(!d.broken_under(empty_step))
 	      LOG_ERROR(logger, "Internal error: the dependency "
 			<< d << " is claimed to be broken, but it doesn't appear to be broken in the initial state.");
 	    else
-	      initial_broken.insert(d);
+	      {
+		LOG_INFO(logger, "Initially broken dependency: " << d);
+		initial_broken.insert(d);
+	      }
 	  }
       }
   }
diff --git a/tests/test_resolver.cc b/tests/test_resolver.cc
index d4bc8ce9..3fb488d5 100644
--- a/tests/test_resolver.cc
+++ b/tests/test_resolver.cc
@@ -75,8 +75,10 @@ const char *dummy_universe_4 = "\
 UNIVERSE [ \
   PACKAGE a < v1 v2 v3 > v1 \
   PACKAGE b < v1 v2 v3 > v1 \
+  PACKAGE c < v1 > v1 \
 \
-  SOFTDEP a v1 -> < b v2  b v3 > \
+  SOFTDEP a v2 -> < b v2  b v3 > \
+  DEP c v1 -> < a v2 > \
 ]";
 
 // Similar -- the non-soft dependency is needed because altering the
@@ -92,10 +94,25 @@ UNIVERSE [ \
 // Used to test breaking and hardening a soft dependency.
 const char *dummy_universe_5 = "\
 UNIVERSE [ \
+  PACKAGE a < v1 v2 > v1 \
+  PACKAGE b < v1 v2 v3 > v1 \
+  PACKAGE c < v1 > v1 \
+\
+  SOFTDEP a v2 -> < b v2 > \
+  DEP c v1 -> < a v2 > \
+]";
+
+// Check that the resolver doesn't wander off and try to fix soft
+// dependencies that aren't broken to start with.  The "-?>" tells the
+// resolver to not place the dependency in the initial set.
+const char *dummy_universe_6 = "\
+UNIVERSE [ \
   PACKAGE a < v1 > v1 \
   PACKAGE b < v1 v2 v3 > v1 \
+  PACKAGE c < v1 v2 > v1 \
 \
-  SOFTDEP a v1 -> < b v2 > \
+  DEP a v1 -> < c v2 > \
+  SOFTDEP a v1 -?> < b v2  b v3 > \
 ]";
 
 // Done this way so meaningful line numbers are generated.
@@ -168,6 +185,7 @@ class ResolverTest : public CppUnit::TestFixture
   CPPUNIT_TEST(testMandateDepSource);
   CPPUNIT_TEST(testHardenDependency);
   CPPUNIT_TEST(testApproveBreak);
+  CPPUNIT_TEST(testInitialSetExclusion);
   CPPUNIT_TEST(testSimpleResolution);
   CPPUNIT_TEST(testSimpleBreakSoftDep);
   CPPUNIT_TEST(testTiers);
@@ -400,6 +418,7 @@ private:
 
     choice_set expected_solution;
     expected_solution.insert_or_narrow(choice::make_install_version(b.version_from_name("v3"), 0));
+    expected_solution.insert_or_narrow(choice::make_install_version(a.version_from_name("v2"), 1));
     assertSameEffect(expected_solution, sol.get_choices());
 
     try
@@ -419,6 +438,7 @@ private:
 
 	    choice_set expected_solution2;
 	    expected_solution2.insert_or_narrow(choice::make_install_version(b.version_from_name("v2"), 0));
+	    expected_solution2.insert_or_narrow(choice::make_install_version(a.version_from_name("v2"), 1));
 	    assertSameEffect(expected_solution2, sol.get_choices());
 	  }
 	catch(NoMoreSolutions)
@@ -437,9 +457,9 @@ private:
 	  {
 	    try
 	      {
-		dep av1d1 = *a.version_from_name("v1").deps_begin();
-		r.harden(av1d1);
-		r.unharden(av1d1);
+		dep av2d1 = *a.version_from_name("v2").deps_begin();
+		r.harden(av2d1);
+		r.unharden(av2d1);
 
 		sol = r.find_next_solution(1000, NULL);
 		LOG_ERROR(logger, "Got an extra solution: " << sol);
@@ -558,9 +578,9 @@ private:
 
     package a = u.find_package("a");
     package b = u.find_package("b");
-    dep av1d1(*a.version_from_name("v1").deps_begin());
+    dep av2d1(*a.version_from_name("v2").deps_begin());
 
-    r.harden(av1d1);
+    r.harden(av2d1);
     solution sol;
     try
       {
@@ -574,7 +594,8 @@ private:
       }
 
     choice_set expected_solution;
-    expected_solution.insert_or_narrow(choice::make_install_version(b.version_from_name("v2"), 0));
+    expected_solution.insert_or_narrow(choice::make_install_version(a.version_from_name("v2"), 0));
+    expected_solution.insert_or_narrow(choice::make_install_version(b.version_from_name("v2"), 1));
     assertSameEffect(expected_solution, sol.get_choices());
 
     try
@@ -606,9 +627,56 @@ private:
 
     package a = u.find_package("a");
     package b = u.find_package("b");
-    dep av1d1(*a.version_from_name("v1").deps_begin());
+    dep av2d1(*a.version_from_name("v2").deps_begin());
+
+    r.approve_break(av2d1);
+    solution sol;
+    try
+      {
+	sol = r.find_next_solution(1000, NULL);
+	LOG_TRACE(logger, "Got first solution: " << sol);
+      }
+    catch(NoMoreSolutions)
+      {
+	LOG_ERROR(logger, "Expected exactly one solution, got none.");
+	CPPUNIT_FAIL("Expected exactly one solution, got none.");
+      }
+
+    choice_set expected_solution;
+    expected_solution.insert_or_narrow(choice::make_break_soft_dep(av2d1, 0));
+    expected_solution.insert_or_narrow(choice::make_install_version(a.version_from_name("v2"), 1));
+    assertSameEffect(expected_solution, sol.get_choices());
+
+    try
+      {
+	sol = r.find_next_solution(1000, NULL);
+      }
+    catch(NoMoreSolutions)
+      {
+	LOG_TRACE(logger, "Success: only one solution was found.");
+	return;
+      }
+
+    LOG_ERROR(logger, "Found an unexpected solution: " << sol);
+    CPPUNIT_FAIL("Expected exactly one solution, got two.");
+  }
+
+  // Test that excluding dependencies from the set to solve works.
+  void testInitialSetExclusion()
+  {
+    log4cxx::LoggerPtr logger(log4cxx::Logger::getLogger("test.resolver.testInitialSetExclusion"));
+
+    LOG_TRACE(logger, "Entering testInitialSetExclusion.");
+
+    dummy_universe_ref u = parseUniverse(dummy_universe_6);
+    dummy_resolver r(10, -300, -100, 100000, 50000, 50,
+		     imm::map<dummy_universe::package, dummy_universe::version>(),
+		     u);
+
+    package a = u.find_package("a");
+    package b = u.find_package("b");
+    package c = u.find_package("c");
 
-    r.approve_break(av1d1);
     solution sol;
     try
       {
@@ -622,7 +690,7 @@ private:
       }
 
     choice_set expected_solution;
-    expected_solution.insert_or_narrow(choice::make_break_soft_dep(av1d1, 0));
+    expected_solution.insert_or_narrow(choice::make_install_version(c.version_from_name("v2"), 1));
     assertSameEffect(expected_solution, sol.get_choices());
 
     try