[Aptitude-devel] r3194 - in branches/aptitude-0.3/aptitude: . src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Sat, 30 Apr 2005 14:50:30 +0000
Author: dburrows
Date: Sat Apr 30 14:50:27 2005
New Revision: 3194
Modified:
branches/aptitude-0.3/aptitude/ChangeLog
branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Basic support for locking out regions of the search space.
Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog (original)
+++ branches/aptitude-0.3/aptitude/ChangeLog Sat Apr 30 14:50:27 2005
@@ -1,3 +1,10 @@
+2005-04-30 Daniel Burrows <dburrows@debian.org>
+
+ * src/generic/problemresolver/problemresolver.h:
+
+ Add basic support for maintaining a list of "forbidden" package
+ versions that varies by solution.
+
2005-04-29 Daniel Burrows <dburrows@debian.org>
* po/POTFILES.in, po/*.po:
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 14:50:27 2005
@@ -48,6 +48,29 @@
#include <iostream>
+/** A dummy iterator that's always an "end" iterator. */
+template<class V>
+struct dummy_end_iterator
+{
+public:
+ /** \return \b true */
+ static bool end() {return true;}
+};
+
+/** Aborts: this iterator is always invalid. */
+template<class V>
+static inline const V &operator*(const dummy_end_iterator<V>&)
+{
+ abort();
+}
+
+/** Aborts. */
+template<class V>
+static inline dummy_end_iterator<V> operator++(dummy_end_iterator<V>&)
+{
+ abort();
+}
+
/** \defgroup problemresolver Aptitude's problem resolver
*
* This is a replacement for the generic apt problem resolver. It
@@ -125,6 +148,14 @@
/** The full list of currently broken dependencies. */
std::set<dep> broken_deps;
+ /** A set of versions that have been "locked out" by this
+ * solution. Primarily used to optimize the common case of
+ * having to "climb a hill" as removals propagate up the
+ * dependency chain. (this allows us to easily force the search
+ * in the direction it has to go)
+ */
+ std::set<version> forbidden_versions;
+
/** The score of this solution. */
int score;
@@ -148,16 +179,28 @@
* \param parent the parent solution
* \param _broken_deps the dependencies that are broken in this partial solution
* \param _score the score of this solution
+ * \param forbidden_iter an APT-style iterator over the set of
+ * newly forbidden versions
* \param _action_score the score not due to broken deps
*/
+ template<class iter>
solution_rep(const action &the_action,
const generic_solution &parent,
const std::set<dep> &_broken_deps,
+ const 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;
+
+ while(!i.end())
+ {
+ forbidden_versions.insert(*i);
+ ++i;
+ }
+
assert(actions.find(the_action.ver.get_package()) == actions.end());
actions[the_action.ver.get_package()] = the_action;
}
@@ -188,9 +231,9 @@
return actions;
}
- std::map<package, action> &get_actions()
+ const std::set<version> &get_forbidden_versions() const
{
- return actions;
+ return forbidden_versions;
}
const action &get_action() {return my_action;}
@@ -218,10 +261,27 @@
public:
generic_solution():real_soln(0) {}
+ /** Create a solution.
+ *
+ * \param a the new action to enqueue
+ *
+ * \param parent the parent of this solution
+ *
+ * \param forbidden_iter an APT-style iterator (i.e., with an end()
+ * method) over the set of newly forbidden versions.
+ *
+ * \param score the total score of this new solution
+ *
+ * \param action_score the portion of score due to actions
+ */
+ template<class iter>
generic_solution(const action &a, const generic_solution &parent,
- const std::set<dep> &broken_deps,
- int score, int action_score)
- :real_soln(new solution_rep(a, parent, broken_deps, score, action_score))
+ const std::set<dep> &broken_deps,
+ const iter &forbidden_iter,
+ int score, int action_score)
+ :real_soln(new solution_rep(a, parent, broken_deps,
+ forbidden_iter,
+ score, action_score))
{
}
@@ -317,6 +377,11 @@
return real_soln->get_actions();
}
+ const std::set<version> &get_forbidden_versions() const
+ {
+ return real_soln->get_forbidden_versions();
+ }
+
/** \return the score of the scolution */
int get_score() const
{
@@ -359,7 +424,22 @@
out << *i;
}
- out<< "];" << get_score();
+ out<< "];";
+
+ if(!get_forbidden_versions().empty())
+ {
+ out << "!!";
+ for(typename std::set<version>::const_iterator i=get_forbidden_versions().begin();
+ i!=get_forbidden_versions().end(); ++i)
+ {
+ if(i!=get_forbidden_versions().begin())
+ out << ", ";
+ out << i->get_name();
+ }
+ out << "!!;";
+ }
+
+ out << get_score();
}
}; // End solution wrapper
@@ -588,13 +668,21 @@
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.
*/
+ template<class iter>
bool try_install(const solution &s,
- const version &v)
+ const version &v,
+ const iter &forbidden_iter)
{
version old_version=s.version_of(v.get_package());
@@ -672,6 +760,7 @@
solution s2=solution(action(v), s,
new_broken,
+ forbidden_iter,
new_score,
new_action_score);
@@ -751,7 +840,7 @@
{
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))
+ if(try_install(s, *vi, d.solvers_begin()))
++count;
}
}
@@ -772,7 +861,7 @@
{
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))
+ if(try_install(s, *si, dummy_end_iterator<version>()))
++count;
}
}