[Aptitude-devel] r3196 - in branches/aptitude-0.3/aptitude: . src/generic/problemresolver

Daniel Burrows dburrows@costa.debian.org
Sat, 30 Apr 2005 16:55:45 +0000


Author: dburrows
Date: Sat Apr 30 16:55:39 2005
New Revision: 3196

Modified:
   branches/aptitude-0.3/aptitude/ChangeLog
   branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Detect and immediately perform 'forced installs'.

Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog	(original)
+++ branches/aptitude-0.3/aptitude/ChangeLog	Sat Apr 30 16:55:39 2005
@@ -2,6 +2,13 @@
 
 	* src/generic/problemresolver/problemresolver.h:
 
+	  When generating the successors of a solution, detect "forced"
+	  installs (i.e., installs which must be in any successor
+	  solution, such as deps that have only one solver) and perform
+	  them immediately.
+
+	* src/generic/problemresolver/problemresolver.h:
+
 	  Actually drop attempts to install "forbidden" package versions.
 
 	* src/generic/problemresolver/problemresolver.h:

Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h	(original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h	Sat Apr 30 16:55:39 2005
@@ -183,26 +183,25 @@
      *         newly forbidden versions
      *  \param _action_score the score not due to broken deps
      */
-    template<class iter>
-    solution_rep(const action &the_action,
+    template<class forbid_iter, class action_iter>
+    solution_rep(const action_iter &abegin,
+		 const action_iter &aend,
 		 const generic_solution &parent,
 		 const std::set<dep> &_broken_deps,
-		 const iter &forbidden_iter,
+		 const forbid_iter &forbidden_iter,
 		 int _score, int _action_score)
       :actions(parent.get_actions()), broken_deps(_broken_deps),
        score(_score), action_score(_action_score),
        refcount(1)
     {
-      iter i=forbidden_iter;
+      for(forbid_iter i=forbidden_iter; !i.end(); ++i)
+	forbidden_versions.insert(*i);
 
-      while(!i.end())
+      for(action_iter a=abegin; a!=aend; ++a)
 	{
-	  forbidden_versions.insert(*i);
-	  ++i;
+	  assert(actions.find(a->ver.get_package()) == actions.end());
+	  actions[a->ver.get_package()] = *a;
 	}
-
-      assert(actions.find(the_action.ver.get_package()) == actions.end());
-      actions[the_action.ver.get_package()] = the_action;
     }
 
     /** Construct a solution with \b no action, the given set of
@@ -263,7 +262,7 @@
 
   /** Create a solution.
    *
-   * \param a the new action to enqueue
+   * \param [abegin,aend) the new actions to enqueue
    *
    * \param parent the parent of this solution
    *
@@ -274,12 +273,15 @@
    *
    * \param action_score the portion of score due to actions
    */
-  template<class iter>
-  generic_solution(const action &a, const generic_solution &parent,
+  template<class forbid_iter, class action_iter>
+  generic_solution(const action_iter &abegin,
+		   const action_iter &aend,
+		   const generic_solution &parent,
 		   const std::set<dep> &broken_deps,
-		   const iter &forbidden_iter,
+		   const forbid_iter &forbidden_iter,
 		   int score, int action_score)
-    :real_soln(new solution_rep(a, parent, broken_deps,
+    :real_soln(new solution_rep(abegin, aend,
+				parent, broken_deps,
 				forbidden_iter,
 				score, action_score))
   {
@@ -434,7 +436,7 @@
 	  {
 	    if(i!=get_forbidden_versions().begin())
 	      out << ", ";
-	    out << i->get_name();
+	    out << i->get_package().get_name() << " " << i->get_name();
 	  }
 	out << "!!;";
       }
@@ -620,21 +622,30 @@
   {
     /** The solution this is based on. */
     solution s;
-    /** The version to installed. */
-    version ver;
+    /** More stuff to install */
+    std::map<package, version> installations;
   public:
-    partial_solution (const solution &_s, const version &_ver)
-      :s(_s), ver(_ver)
+    partial_solution (const solution &_s)
+      :s(_s)
     {
     }
 
+    void install(const package &p, const version &v)
+    {
+      assert(installations.find(p) == installations.end());
+
+      installations[p]=v;
+    }
+
     /** \return the currently installed version of the given
      *	package.
      */
     version version_of(const package &pkg) const
     {
-      if(pkg == ver.get_package())
-	return ver;
+      typename std::map<package, version>::const_iterator found=installations.find(pkg);
+
+      if(found!=installations.end())
+	return found->second;
       else
 	return s.version_of(pkg);
     }
@@ -665,49 +676,46 @@
 		  i->get_actions().begin(), i->get_actions().end()))
 	return true;
 
+    if(s.get_score() < minimum_score)
+      {
+	if(debug)
+	  std::cout << "Not generating solution (infinite badness " << s.get_score() << "<" << minimum_score << ")" << std::endl;
+	return true;
+      }
+
     return false;
   }
 
-
-  /** Enqueues a single successor node to the given solution by
-   *  installing the given package version.
-   *
-   *  \param s the predecessor of the new solution
-   *  \param v the version to install
-   *  \param forbidden_iter an APT-style iterator over a set
-   *  of versions that should be forbidden.
-   *
-   *  \return \b true if the new solution was not in the closed set.
+  /** Generates a successor to s by performing the actions
+   *  [abegin,aend).
    */
-  template<class iter>
-  bool try_install(const solution &s,
-		   const version &v,
-		   const iter &forbidden_iter)
+  template<class forbid_iter, class a_iter>
+  solution do_install(const solution &s,
+		      const a_iter &abegin, const a_iter &aend,
+		      const forbid_iter &forbidden_iter)
   {
-    if(s.get_forbidden_versions().find(v) != s.get_forbidden_versions().end())
-      {
-	if(debug)
-	  std::cout << "Discarding forbidden version " << v.get_name() << std::endl;
-
-	return false;
-      }
+    int new_action_score=s.get_action_score();
+    partial_solution tmpsol(s);
+    std::set<dep> new_broken;
 
-    version old_version=s.version_of(v.get_package());
+    for(a_iter a=abegin; a!=aend; ++a)
+      {
+	const version &v=a->ver;
+	version old_version=s.version_of(v.get_package());
 
-    assert(old_version == v.get_package().current_version() &&
-	   old_version != v);
+	assert(old_version == v.get_package().current_version() &&
+	       old_version != v);
 
-    int new_action_score=s.get_action_score();
+	new_action_score+=step_score;
 
-    new_action_score+=step_score;
+	assert(v.get_id()<universe.get_version_count());
+	new_action_score+=version_scores[v.get_id()];
+	assert(v.get_package().current_version().get_id()<universe.get_version_count());
+	new_action_score-=version_scores[v.get_package().current_version().get_id()];
 
-    assert(v.get_id()<universe.get_version_count());
-    new_action_score+=version_scores[v.get_id()];
-    assert(v.get_package().current_version().get_id()<universe.get_version_count());
-    new_action_score-=version_scores[v.get_package().current_version().get_id()];
+	tmpsol.install(v.get_package(), v);
+      }
 
-    partial_solution S(s, v);
-    std::set<dep> new_broken;
     // Check all revdeps of the old AND new package versions, and all
     // previously broken deps.  Is there any way to speed this up?
     // For instance, by keeping a cache of already-examined deps.
@@ -726,51 +734,62 @@
     // *either* the reverse list of v *or* the reverse list of
     // old_version.
 
-    int new_score=new_action_score;
 
-    for(typename version::revdep_iterator rd=old_version.revdeps_begin();
-	!rd.end() && (broken_score>0 || new_score>=minimum_score);
-	++rd)
-      if((*rd).broken_under(S))
-	{
-	  new_broken.insert(*rd);
-	  new_score+=broken_score;
-	}
+    // Note: I *think* it *might* be OK, if installing multiple
+    // versions at once, to merge this loop with the above (think of
+    // installing one version after another..); however, as I'm not
+    // entirely certain and it's a relatively small optimization, I'm
+    // taking the safe route and checking *all* versions.
+    for(a_iter a=abegin; a!=aend; ++a)
+      {
+	const version &v=a->ver;
+	version old_version=s.version_of(v.get_package());
 
-    for(typename version::revdep_iterator rd=v.revdeps_begin();
-	!rd.end() && (broken_score>0 || new_score>=minimum_score);
-	++rd)
-      if((*rd).broken_under(S))
-	{
-	  new_broken.insert(*rd);
-	  new_score+=broken_score;
-	}
+	for(typename version::revdep_iterator rd=old_version.revdeps_begin();
+	    !rd.end(); ++rd)
+	  if((*rd).broken_under(tmpsol))
+	    new_broken.insert(*rd);
+
+	for(typename version::revdep_iterator rd=v.revdeps_begin();
+	    !rd.end(); ++rd)
+	  if((*rd).broken_under(tmpsol))
+	    new_broken.insert(*rd);
+      }
 
     const std::set<dep> &old_broken=s.get_broken();
     for(typename std::set<dep>::const_iterator bd=old_broken.begin();
-	bd!=old_broken.end() && (broken_score>0 || new_score>=minimum_score);
-	++bd)
-      if((*bd).broken_under(S))
-	{
-	  new_broken.insert(*bd);
-	  new_score+=broken_score;
-	}
+	bd!=old_broken.end(); ++bd)
+      if((*bd).broken_under(tmpsol))
+	new_broken.insert(*bd);
+
+    int new_score=new_action_score+broken_score*new_broken.size();
 
     if(new_broken.size() == 0)
       new_score+=full_solution_score;
 
-    if(new_score < minimum_score)
-      {
-	if(debug)
-	  std::cout << "Not generating solution (infinite badness " << new_score << "<" << minimum_score << ")" << std::endl;
-	return true;
-      }
+    return solution(abegin, aend, s,
+		    new_broken,
+		    forbidden_iter,
+		    new_score,
+		    new_action_score);
+  }
 
-    solution s2=solution(action(v), s,
-			 new_broken,
-			 forbidden_iter,
-			 new_score,
-			 new_action_score);
+  /** Enqueues a single successor node to the given solution by
+   *  installing the given package version.
+   *
+   *  \param s the predecessor of the new solution
+   *  \param v the version to install
+   *  \param forbidden_iter an APT-style iterator over a set
+   *  of versions that should be forbidden.
+   *
+   *  \return \b true if the new solution was not in the closed set.
+   */
+  template<class forbid_iter, class action_iter>
+  bool try_install(const solution &s,
+		   const action_iter &abegin, const action_iter &aend,
+		   const forbid_iter &forbidden_iter)
+  {
+    solution s2=do_install(s, abegin, aend, forbidden_iter);
 
     if(!irrelevant(s2))
       {
@@ -846,9 +865,20 @@
 	    !vi.end(); ++vi)
 	  if(*vi != source_version)
 	    {
+	      if(s.get_forbidden_versions().find(*vi) != s.get_forbidden_versions().end())
+		{
+		  if(debug)
+		    std::cout << "Discarding forbidden version "
+			      << (*vi).get_name() << std::endl;
+
+		  continue;
+		}
+
 	      if(debug)
 		std::cout << "  Trying to resolve " << d << " by installing " << (*vi).get_package().get_name() << " version " << (*vi).get_name() << std::endl;
-	      if(try_install(s, *vi, d.solvers_begin()))
+
+	      action act(*vi);
+	      if(try_install(s, &act, (&act)+1, d.solvers_begin()))
 		++count;
 	    }
       }
@@ -867,14 +897,148 @@
 	if(sol_ver != sol_ver.get_package().current_version() &&
 	   s.get_actions().find(sol_ver.get_package())==s.get_actions().end())
 	  {
+	    if(s.get_forbidden_versions().find(sol_ver) != s.get_forbidden_versions().end())
+	      {
+		if(debug)
+		  std::cout << "Discarding forbidden version "
+			    << sol_ver.get_name() << std::endl;
+
+		continue;
+	      }
+
 	    if(debug)
 	      std::cout << "  Trying to resolve " << d << " by installing " << (*si).get_package().get_name() << " version " << (*si).get_name() << std::endl;
-	    if(try_install(s, *si, dummy_end_iterator<version>()))
+
+	    action act(*si);
+	    if(try_install(s, &act, (&act)+1, dummy_end_iterator<version>()))
 	      ++count;
 	  }
       }
   }
 
+  /** Generate "forced" successors -- those successors which are
+   *  logically required by the existing dependencies.
+   *
+   *  \return \b true iff the dependency can't be resolved at all
+   *
+   *  \param s the solution to try.
+   *
+   *  \param d the dep to test.
+   *
+   *  \param actions an out parameter -- any generated forced
+   *  successor will be pushed onto this list.
+   *
+   *  \param toforbid an out parameter -- includes additional
+   *  forbidden versions over what's forbidden by s.
+   */
+  bool generate_forced_successor(const solution &s,
+				 const dep &d,
+				 std::set<action> &actions,
+				 std::set<version> &toforbid)
+  {
+    version v;
+    version source_version=d.get_source();
+    package source_package=source_version.get_package();
+    bool found=false, from_source=false;
+
+    if(debug)
+      {
+	std::cout << "Testing whether " << d << " is a forced dependency." << std::endl;
+      }
+
+    // If the source of the dependency was not modified and is
+    // presently installed, try installing a *different version*.
+    if(source_version == source_package.current_version())
+      {
+	for(typename package::version_iterator vi=source_package.versions_begin();
+	    !vi.end(); ++vi)
+	  // Note that testing against toforbid is strictly a
+	  // performance hack (it would be caught in the next cycle if
+	  // we didn't do it here, but why not use the information
+	  // ASAP?)
+	  if(*vi != source_version &&
+	     s.get_forbidden_versions().find(*vi) == s.get_forbidden_versions().end() &&
+	     toforbid.find(*vi)==toforbid.end())
+	    {
+	      if(found)
+		return false;
+	      found=true;
+	      from_source=true;
+	      v=*vi;
+	    }
+      }
+
+    for(typename dep::solver_iterator si=d.solvers_begin();
+	!si.end(); ++si)
+      {
+	version sol_ver=*si;
+
+	if(sol_ver != sol_ver.get_package().current_version() &&
+	   s.get_actions().find(sol_ver.get_package())==s.get_actions().end() &&
+	   s.get_forbidden_versions().find(sol_ver) == s.get_forbidden_versions().end() &&
+	   toforbid.find(sol_ver)==toforbid.end())
+	  {
+	    if(found)
+	      return false;
+	    found=true;
+	    v=sol_ver;
+	  }
+      }
+
+    if(found)
+      {
+	if(debug)
+	    std::cout << "Forced resolution of " << d
+		      << " by installing " << v.get_package().get_name()
+		      << " version " << v.get_name() << std::endl;
+
+	if(from_source)
+	  for(typename dep::solver_iterator si=d.solvers_begin();
+	      !si.end(); ++si)
+	    toforbid.insert(*si);
+
+	actions.insert(action(v));
+
+	return false;
+      }
+    else
+      {
+	if(debug)
+	  std::cout << "Discarding solution: unsolvable dependency " << d << std::endl;
+
+	return true;
+      }
+  }
+
+  /** Convert a [begin,end) pair to a single APT-style iterator.
+   */
+  template<class iter, class target>
+  class apt_iter_wrapper
+  {
+    iter curr, the_end;
+  public:
+    apt_iter_wrapper(const iter &_begin, const iter &_end)
+      :curr(_begin), the_end(_end)
+    {
+    }
+
+    bool end() const
+    {
+      return curr==the_end;
+    }
+
+    apt_iter_wrapper &operator++()
+    {
+      ++curr;
+      return *this;
+    }
+
+    const target &operator*() const
+    {
+      return *curr;
+    }
+  };
+
   /** Processes the given solution by enqueuing its successor nodes
    *  (if any are available).
    */
@@ -883,6 +1047,25 @@
     // How many solutions have been generated?
     unsigned int sols=0;
 
+    std::set<action> forced_actions;
+    std::set<version> forced_forbidden_versions;
+
+
+    for(typename std::set<dep>::const_iterator bi=s.get_broken().begin();
+	bi!=s.get_broken().end(); ++bi)
+      if(generate_forced_successor(s, *bi,
+				   forced_actions,
+				   forced_forbidden_versions))
+	return;
+
+    if(!forced_actions.empty())
+      {
+	try_install(s,
+		    forced_actions.begin(), forced_actions.end(),
+		    apt_iter_wrapper<typename std::set<version>::const_iterator, version>(forced_forbidden_versions.begin(), forced_forbidden_versions.end()));
+	return;
+      }
+
     for(typename std::set<dep>::const_iterator bi=s.get_broken().begin();
 	bi!=s.get_broken().end() && (sols==0 || sols<max_successors); ++bi)
       generate_successors(s, *bi, sols);
@@ -1078,6 +1261,8 @@
 	else
 	  process_solution(s);
 
+	std::cout << "Done generating successors." << std::endl;
+
 	--max_steps;
       }