[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;
}